Method and apparatus for precalculating a direct branch partial target address during a misprediction correction process

Patent metadata

Field	Value
Publication number	US-9489204-B2
Application number	US-201313842835-A
Country	US
Kind code	B2
Filing date	Mar 15, 2013
Priority date	Mar 15, 2013
Publication date	Nov 8, 2016
Grant date	Nov 8, 2016

Abstract

An example method of storing a partial target address in an instruction cache includes receiving a branch instruction. The method also includes predicting a direction of the branch instruction as being not taken. The method further includes calculating a destination address based on executing the branch instruction. The method also includes determining a partial target address using the destination address. The method further includes in response to the predicted direction of the branch instruction changing from not taken to taken, replacing an offset in an instruction cache with the partial target address.

First claim

What is claimed is:

1. A method of storing a partial target address in an instruction cache, comprising:
receiving a branch instruction from an instruction cache;
predicting a direction of the branch instruction as being not taken;
calculating a destination address based on executing the branch instruction;
determining a partial target address using the destination address; and
in response to the predicted direction of the branch instruction changing from not taken to taken, replacing an offset in the branch instruction in the instruction cache with the partial target address.

2. The method of claim 1 , further comprising: in response to the predicted direction of the branch instruction changing from taken to not taken, replacing the partial target address in the branch instruction in the instruction cache with the offset.

3. The method of claim 1 , further comprising:
in response to replacing the offset in the branch instruction in the instruction cache with the partial target address, setting a bit in the branch instruction; and
when the bit is set in the branch instruction and the predicted direction of the branch instruction changes from not taken to taken, using the partial target address in the branch instruction in the instruction cache.

4. The method of claim 1 , wherein receiving the branch instruction comprises receiving a conditional jump instruction.

5. The method of claim 1 , wherein receiving the branch instruction comprises receiving an unconditional jump instruction.

6. The method of claim 1 , wherein the prediction of the direction of the branch instruction as being not taken is statically determined by a compiler, and the compiler initializes each branch instruction as being not taken.

7. The method of claim 1 , wherein receiving the branch instruction comprises receiving a prediction bit that predicts the direction of the branch instruction.

8. An apparatus for storing a partial target address in an instruction cache, comprising:
a processor that is operable to:
receive a branch instruction from an instruction cache;
predict a direction of the branch instruction as being not taken;
calculate a destination address based on executing the branch instruction;
determine a partial target address using the destination address; and
in response to the predicted direction of the branch instruction changing from not taken to taken, replace an offset in the branch instruction in the instruction cache with the partial target address.

9. The apparatus of claim 8 , wherein the processor is further operable to, in response to the predicted direction of the branch instruction changing from taken to not taken, replace the partial target address in the branch instruction in the instruction cache with the offset.

10. The apparatus of claim 8 , wherein the processor is further operable to:
in response to replacing the offset in the branch instruction in the instruction cache with the partial target address, set a bit in the branch instruction; and
when the bit is set in the branch instruction and the predicted direction of the branch instruction changes from not taken to taken, use the partial target address in the instruction cache.

11. The apparatus of claim 8 , wherein the processor is operable to receive a conditional jump instruction.

12. The apparatus of claim 8 , wherein the processor is operable to receive an unconditional jump instruction.

13. The apparatus of claim 8 , wherein a compiler statically initializes the prediction of the direction of the branch instruction as being not taken.

14. The apparatus of claim 8 , wherein the processor is operable to receive a prediction bit that predicts the direction of the branch instruction.

15. A non-transitory computer-readable medium having stored thereon computer-executable instructions for performing operations, comprising:
receiving a branch instruction from an instruction cache;
predicting a direction of the branch instruction as being not taken;
calculating a destination address based on executing the branch instruction;
determining a partial target address using the destination address; and
in response to the predicted direction of the branch instruction changing from not taken to taken, replacing an offset in the branch instruction in the instruction cache with the partial target address.

16. The non-transitory computer-readable medium of claim 15 , the operations further comprising, in response to the predicted direction of the branch instruction changing from taken to not taken, replacing the partial target address in the branch instruction in the instruction cache with the offset.

17. The non-transitory computer-readable medium of claim 15 , the operations further comprising:
in response to replacing the offset in the branch instruction in the instruction cache with the partial target address, setting a bit in the branch instruction; and
when the bit is set in the branch instruction and the direction of the branch instruction changes from not taken to taken, using the partial target address in the instruction cache.

18. The non-transitory computer-readable medium of claim 15 , wherein receiving the branch instruction comprises receiving a conditional jump instruction.

19. The non-transitory computer-readable medium of claim 15 , wherein receiving the branch instruction comprises receiving an unconditional jump instruction.

20. An apparatus for storing a partial target address in an instruction cache, comprising:
means for receiving a branch instruction from an instruction cache;
means for predicting a direction of the branch instruction as being not taken;
means for calculating a destination address based on executing the branch instruction;
means for determining a partial target address using the destination address; and
means for, in response to the predicted direction of the branch instruction changing from not taken to taken, replacing an offset in the branch instruction in the instruction cache with the partial target address.

21. The apparatus of claim 20 , further comprising means for, in response to the predicted direction of the branch instruction changing from taken to not taken, replacing the partial target address in the branch instruction in the instruction cache with the offset.

22. The apparatus of claim 21 , further comprising:
means for, in response to replacing the offset in the branch instruction in the instruction cache with the partial target address, setting a bit in the branch instruction; and
means for, when the bit is set in the branch instruction and the predicted direction of the branch instruction changes from not taken to taken, using the partial target address in the instruction cache.

23. The method of claim 1 , further comprising:
predicting a direction of a next branch instruction as being taken; and
in response to the predicted direction of the next branch instruction being taken, retrieving a destination address for the next branch instruction based on a partial target address for the next branch instruction stored in the next branch instruction in the instruction cache.

24. The method of claim 23 , comprising in response to the predicted direction of the next branch instruction being taken, retrieving the destination address for the next branch instruction based on the partial target address stored in an opcode of the next branch instruction stored in the instruction cache.

25.

Assignees

• Qualcomm Inc

Inventors

• Tu Jiajin
• Venkumahanti Suresh K
• Mestan Brian R

Classifications

• G06F9/3812

  with instruction modification, e.g. store into instruction stream · CPC title

• G06F9/3804 Primary

  for branches, e.g. hedging, branch folding · CPC title

• G06F9/3806

  using address prediction, e.g. return stack, branch history buffer · CPC title

• G06F9/324 Primary

  using program counter relative addressing · CPC title

• G06F9/3846

  using static prediction, e.g. branch taken strategy · CPC title