Instruction cache behavior and branch prediction

Patent metadata

Field	Value
Publication number	US-2022019435-A1
Application number	US-202016933197-A
Country	US
Kind code	A1
Filing date	Jul 20, 2020
Priority date	Jul 20, 2020
Publication date	Jan 20, 2022
Grant date	—

Abstract

Instruction cache behavior and branch prediction are used to improve the functionality of a computing device by profiling branching instructions in an instruction cache to identify likelihoods of proceeding to a plurality of targets from the branching instructions; identifying a hot path in the instruction cache based on the identified likelihoods; and rearranging the plurality of targets relative to one another and associated branching instructions so that a first branching instruction that has a higher likelihood of proceeding to a first hot target than to a first cold target and that previously flowed to the first cold target and jumped to the first hot target instead flows to the first hot target and jumps to the first cold target.

First claim

1 . A computer-implemented method comprising:
identifying a branching instruction associated with:
an origin instruction;
a cold target; and
a hot target located after the cold target in an instruction cache, wherein, based on historical data, the branching instruction is more likely to proceed to the hot target than to the cold target at execution based on a routing condition;
swapping an order of the cold target and the hot target in the instruction cache; and reversing the routing condition.

2 . The computer-implemented method of claim 1 , further comprising:
in response to determining that the cold target flows to the hot target at execution, inserting a jump instruction from to the hot target in the instruction cache after the swapped cold target.

3 . The computer-implemented method of claim 1 , wherein execution of the branching instruction originally jumps to the hot target when the routing condition is a first one of true or false and originally flows to the cold target when the routing condition is a second one of true or false; and
wherein after swapping the order and reversing the routing condition, the execution of the branching instruction jumps to the cold target when the routing condition is the second one of true or false and flows to the hot target when the routing condition is the first one of true or false.

4 . The computer-implemented method of claim 1 , further comprising after swapping the order of the cold target and the hot target in the instruction cache and reversing the routing condition:
executing instructions held in the instruction cache; continuously monitoring execution of the instructions held in the instruction cache; in response to determining that the branching instruction is more likely to proceed to the cold target than the hot target:
reclassifying the cold target as a new hot target;
reclassifying the hot target as a new cold target;
swapping a new order of the new cold target and the new hot target in the instruction cache; and
reversing the routing condition.

5 . The computer-implemented method of claim 1 , wherein identifying the branching instruction further comprises determining that a difference in likelihood of proceeding to the hot target than to the cold target exceeds a user defined threshold.

6 . The computer-implemented method of claim 1 , wherein the hot target is a first instruction in a hot block and the cold target is a first instruction in a cold block, wherein the cold target is initially located at a first address located in the instruction cache directly after a branch address where the branching instruction is located in the instruction cache, and wherein swapping the order of the cold target and the hot target in the instruction cache further comprises:
relocating the hot block in the instruction cache to begin with the hot target located at the first address; and relocating the cold block in the instruction cache to begin with the cold target located at a second address.

7 . The computer-implemented method of claim 6 , wherein the hot block and the cold block are of equal size, wherein after swapping the hot target and the cold target, the cold block begins where the hot block initially was located and the hot block begins where the cold block initially was located.

8 . The computer-implemented method of claim 1 , wherein the branching instruction is determined to be more likely to proceed to the hot target than to the cold target at execution based on an analysis of trace indexes of C2 generated instructions over a plurality of iterations of the C2 generated instructions.

9 . A computer-implemented method, comprising:
identifying a branching instruction associated with:
a cold block starting with a cold target that the branching instruction flows to when a routing condition is a first one of true or false; and
a hot block located before the branching instruction in an instruction cache that starts at a hot target that flows to a subsequent instruction and that the branching instruction jumps to when the routing condition is a second one of true or false, wherein, based on historical data, the branching instruction is more likely to proceed to the hot target than to the cold target at execution;
inserting a space between the branching instruction and the cold target; inserting a duplicate hot block and a jump instruction in the space, wherein the duplicate hot block flows to the jump instruction and the jump instruction jumps to the subsequent instruction; and reversing the routing condition in the branching instruction to flow to the duplicate hot block when the routing condition is the second one of true or false and to jump to the cold target when the routing condition is the first one of true or false.

10 . The computer-implemented method of claim 9 , further comprising after inserting the duplicate hot block and the jump instruction and reversing the routing condition:
executing instructions held in the instruction cache; continuously monitoring execution of the instructions held in the instruction cache; in response to determining that the branching instruction is more likely to proceed to the cold target than the hot target:
reclassifying the cold target as a new hot target;
reclassifying the hot target as a new cold target;
removing the duplicate hot block and the jump condition; and
reversing the routing condition.

11 . The computer-implemented method of claim 9 , wherein identifying the branching instruction further comprises determining that a difference in likelihood of proceeding to the hot target than to the cold target exceeds a user defined threshold.

12 . The computer-implemented method of claim 9 , wherein duplicating the hot target includes duplicating a plurality of instructions including the hot target and instructions located between the hot target and the subsequent instruction.

13 . The computer-implemented method of claim 9 , wherein the branching instruction is determined to be more likely to proceed to the hot target than to the cold target at execution based on an analysis of trace indexes of C2-generated instructions.

14 . A computer-implemented method, comprising:
profiling branching instructions in an instruction cache to identify likelihoods of proceeding to a plurality of targets from the branching instructions; identifying a hot path in the instruction cache based on the identified likelihoods; and rearranging the plurality of targets relative to one another and associated branching instructions so that a first branching instruction that has a higher likelihood of proceeding to a first hot target than to a first cold target and that previously flowed to the first cold target and jumped to the first hot target instead flows to the first hot target and jumps to the first cold target.

15 . The computer-implemented method of claim 14 , wherein rearranging the plurality of targets is performed just in time for execution of instructions in the instruction cache, wherein a second branching instruction that flows to a second cold target and jumps to a second hot target remains unaffected by the rearranging so that the second branching instruction that flows to the second cold target and jumps to the second hot target based on the second branching instruction having a lower priority below a cutoff threshold for just in time execution.

16 . The computer-implemented method of claim 15 , wherein the first branching instruction has a higher priority for rearrangement than the second branching instruction based on a greater likelihood of the first branch

Assignees

• IBM

Inventors

• Liu Yang
• Wang Ting
• Li Qi
• Zhang Qing
• Haochen Gui
• Guo Xiao Ping
• Zeng Xiao Hua
• Wang Yangming
• Li Yi
• Li Hua Qing
• Fei Fei

Classifications

• G06F9/30058 Primary

  Conditional branch instructions · CPC title

• G06F2212/1016

  Performance improvement · CPC title

• G06F12/0875

  with dedicated cache, e.g. instruction or stack · CPC title

• G06F2212/452

  Instruction code · CPC title

• G06F12/0897

  with two or more cache hierarchy levels (with multilevel cache hierarchies G06F12/0811) · CPC title