Method and apparatus for recovering from branch misprediction

1. A method for executing a branch instruction, comprising:

using a computer to execute the branch instruction, wherein executing the branch instruction involves obtaining a stored prediction of a resolution of the branch instruction and fetching subsequent instructions for execution based on the predicted resolution of the branch instruction;

if an actual resolution of the branch instruction is different from the predicted resolution,

updating the stored prediction of the resolution of the branch instruction to the actual resolution of the branch instruction; and

re-executing the branch instruction, wherein re-executing the branch instruction involves obtaining the updated stored prediction of the resolution of the branch instruction and fetching subsequent instructions for execution based on the updated stored prediction of the branch instruction.

2. The method of claim 1 , wherein executing the branch instruction involves saving a program counter (PC) for the branch instruction and wherein re-executing the branch instruction involves restoring the saved PC for the branch instruction and fetching instructions for execution from the restored PC, wherein the branch instruction is a first instruction fetched for execution, whereby the branch instruction is re-executed.

3. The method of claim 1 , wherein the method further comprises computing a target program counter (target PC) for the branch instruction in a branch target unit, wherein the target PC is used to fetch subsequent instructions for execution when the predicted resolution for the branch instruction is “taken”.

4. The method of claim 3 , wherein the method further comprises incrementing a PC to a next instruction in program order, wherein the incremented PC is used to fetch subsequent instructions for execution when the predicted resolution for the branch instruction is “not taken”.

5. The method of claim 1 , wherein obtaining the stored prediction involves reading the predicted resolution for the branch instruction from an entry for the branch instruction in a branch prediction table.

6. The method of claim 5 , wherein updating the stored prediction involves recording the actual resolution of the branch instruction in the entry for the branch instruction in the branch prediction table.

7. The method of claim 1 , wherein re-executing the branch instruction involves at least one of, terminating execution of, or deleting a result of, one or more instructions fetched for execution based on a misprediction of the resolution of the branch instruction.

8. An apparatus for executing a branch instruction, comprising:

a processor;

a branch prediction unit on the processor;

a fetch unit on the processor;

wherein during execution of the branch instruction by the processor, the fetch unit fetches subsequent instructions for execution based on a stored prediction of a resolution of the branch instruction provided to the fetch unit by the branch prediction unit;

if an actual resolution of the branch instruction is different from the predicted resolution, the processor

updates the stored prediction of the resolution of the branch instruction to the actual resolution of the branch instruction; and

re-executes the branch instruction, wherein when re-executing the branch instruction, the fetch unit fetches subsequent instructions for execution based on the updated stored prediction for the resolution of the branch instruction provided to the fetch unit by the branch prediction unit.

9. The apparatus of claim 8 , wherein when executing the branch instruction, the processor saves a program counter (PC) for the branch instruction and when re-executing the branch instruction, the processor restores the saved PC for the branch instruction and the fetch unit fetches instructions for execution from the restored PC, wherein the branch instruction is a first instruction fetched for execution, whereby the branch instruction is re-executed.

10. The apparatus of claim 8 , further comprising a branch target unit on the processor, wherein the branch target unit computes a target PC for the branch instruction and signals the target PC to the fetch unit, wherein the fetch unit uses the target PC to fetch subsequent instructions for execution when the predicted resolution for the branch instruction is “taken”.

11. The apparatus of claim 10 , wherein the fetch unit increments a PC to a next instruction in program order, wherein the fetch unit uses the incremented PC to fetch subsequent instructions for execution when the predicted resolution for the branch instruction is “not taken”.

12. The apparatus of claim 8 , wherein when providing the stored prediction, the branch prediction unit reads the predicted resolution for the branch instruction from an entry for the branch instruction stored in a branch prediction table.

13. The apparatus of claim 12 , wherein when updating the stored prediction, the processor records the actual resolution of the branch instruction in the entry for the branch instruction in the branch prediction table.

14. The apparatus of claim 8 , wherein when re-executing the branch instruction, the processor terminates execution of, or deletes a result of, one or more instructions fetched for execution based on a misprediction of the resolution of the branch instruction.

15. A computer system for executing a branch instruction, comprising:

a processor;

a memory coupled to the processor, wherein the memory stores data for the processor;

a branch prediction unit on the processor;

a fetch unit on the processor;

wherein during execution of the branch instruction by the processor, the fetch unit fetches subsequent instructions for execution from the memory based on a stored prediction of a resolution of the branch instruction provided to the fetch unit by the branch prediction unit;

if an actual resolution of the branch instruction is different from the predicted resolution, the processor

updates the stored prediction of the resolution of the branch instruction to the actual resolution of the branch instruction; and

re-executes the branch instruction, wherein when re-executing the branch instruction, the fetch unit fetches subsequent instructions for execution from the memory based on the updated stored prediction for the resolution of the branch instruction provided to the fetch unit by the branch prediction unit.

16. The computer system of claim 15 , wherein when executing the branch instruction, the processor saves a program counter (PC) for the branch instruction and when re-executing the branch instruction, the processor restores the saved PC for the branch instruction and the fetch unit fetches instructions for execution from the restored PC, wherein the branch instruction is a first instruction fetched for execution, whereby the branch instruction is re-executed.

17. The computer system of claim 15 , further comprising a branch target unit on the processor, wherein the branch target unit computes a target PC for the branch instruction and signals the target PC to the fetch unit, wherein the fetch unit uses the target PC to fetch subsequent instructions for execution from the memory when the predicted resolution for the branch instruction is “taken”.

18. The computer system of claim 17 , wherein the fetch unit increments a PC to a next instruction in program order, wherein the fetch unit uses the incremented PC to fetch subsequent instructions for execution from the memory when the predicted resolution for the branch instruction is “not taken”.

19. The computer system of claim 15 , wherein when providing the stored prediction, the branch prediction unit reads the predicted resolution for the branch instruction from an entry for the branch instruction stored in a branch prediction table.

20. The computer system of claim 19 , wherein when updating the stored prediction, the processor records the actual resolution of the branch instruction in the entry for the branch instruction in the branch prediction table.

21. The computer system of claim 15 , wherein when re-executing the branch instruction, the processor terminates execution of, or deletes a result of, one or more instructions fetched for execution based on a misprediction of the resolution of the branch instruction.