Storing incidental branch predictions to reduce latency of misprediction recovery

Patent metadata

Field	Value
Publication number	US-12204908-B2
Application number	US-201815997344-A
Country	US
Kind code	B2
Filing date	Jun 4, 2018
Priority date	Jun 4, 2018
Publication date	Jan 21, 2025
Grant date	Jan 21, 2025

Abstract

A branch predictor predicts a first outcome of a first branch in a first block of instructions. Fetch logic fetches instructions for speculative execution along a first path indicated by the first outcome. Information representing a remainder of the first block is stored in response to the first predicted outcome being taken. In response to the first branch instruction being not taken, the branch predictor is restarted based on the remainder block. In some cases, entries corresponding to second blocks along speculative paths from the first block are accessed using an address of the first block as an index into a branch prediction structure. Outcomes of branch instructions in the second blocks are concurrently predicted using a corresponding set of instances of branch conditional logic and the predicted outcomes are used in combination with the remainder block to restart the branch predictor in response to mispredictions.

First claim

What is claimed is:

1. An apparatus comprising:
a branch predictor configured to predict a first outcome of a first branch instruction in a first block of instructions and to predict a second outcome for a remainder block of the first block of instructions;
an alternate prediction storage array in the branch predictor to selectively store the second outcome by:
storing the second outcome in response to the first outcome being taken, and
not storing the second outcome in response to the first outcome being not taken; and

fetch logic to, in response to the first outcome being a predicted to be taken and an actual outcome of the first branch instruction being not taken, restart the branch predictor based on the second outcome.

2. The apparatus of claim 1 , wherein the branch predictor is configured to concurrently predict the first outcome of the first branch instruction and the second outcome, wherein the second outcome is for a second branch instruction in the remainder block of the first block of instructions.

3. The apparatus of claim 2 , wherein the branch predictor is restarted to begin branch prediction at a second block identified by one of:
a target address of a second branch instruction in response to the second outcome indicating that the second branch instruction is taken; and
an address of an instruction subsequent to the second branch instruction in response to the second outcome indicating that the second branch instruction is not taken and the first block including at least one third branch instruction.

4. The apparatus of claim 2 , wherein the first block does not include a second branch instruction until a subsequent memory boundary, and wherein the remainder block of the first block includes information indicating that the first block does not include the second branch instruction until the subsequent memory boundary.

5. The apparatus of claim 4 , wherein the branch predictor is configured to restart at the subsequent memory boundary indicated in the remainder block of the first block.

6. The apparatus of claim 1 , further comprising:
a branch prediction structure configured to store a set of entries corresponding to a set of second blocks along speculative paths from the first block, wherein the branch predictor is configured to access the branch prediction structure using an address of the first block as an index.

7. The apparatus of claim 1 , wherein, in response to the first outcome not being mispredicted, processing the first block of instructions.

8. A method comprising:
predicting, at a branch predictor, a first outcome of a first branch instruction in a first block of instructions and a second outcome for a remainder block of the first block of instructions;
selectively storing, in an alternate prediction storage array in the branch predictor, the second outcome, wherein selectively storing the second outcome comprises storing the second outcome in the alternate prediction storage array in response to the first outcome being taken, and
not storing the second outcome in the alternate prediction storage array in response to the first outcome being not taken; and
in response to the first branch instruction being predicted to be taken and an actual outcome of the first branch instruction being not taken, restarting the branch predictor based on the second outcome.

9. The method of claim 8 , wherein selectively storing the second outcome comprises storing information indicating that the first block does not include any branch instructions until a subsequent memory boundary.

10. The method of claim 8 , wherein multiple copies of branch predictor conditional logic are instantiated to concurrently predict outcomes of branch instructions in the first block of instructions.

11. The method of claim 8 , further comprising:
responsive to the first outcome not being mispredicted, processing the first block of instructions.

12. The method of claim 8 , further comprising:
concurrently predicting the first outcome of the first branch instruction and the second outcome, wherein the second outcome is for a second branch instruction in the first block of instructions.

13. The method of claim 12 ,
wherein restarting the branch predictor comprises restarting the branch predictor to begin branch prediction at a second block identified by one of:
a target address of a second branch instruction in the remainder block of the first block of instructions in response to the second outcome indicating that the second branch instruction is taken; and
an address of an instruction subsequent to the second branch instruction in response to the second outcome indicating that the second branch instruction is not taken and the first block including at least one third branch instruction.

14. The method of claim 8 , wherein the first block does not include a second branch instruction prior to a subsequent memory boundary, and wherein the remainder block includes information indicating that the first block does not include the second branch instruction prior to the subsequent memory boundary.

15. The method of claim 14 ,
wherein restarting the branch predictor comprises restarting the branch predictor at the subsequent memory boundary indicated in the remainder block.

16. The method of claim 8 , further comprising:
accessing information in a branch prediction structure using an address of the first block as an index, wherein the information comprises a set of entries corresponding to a set of second blocks along speculative paths from the first block.

17. The method of claim 8 , wherein selectively storing the second outcome comprises storing information associated with the remainder block including information indicating the second outcome and a location of an end of the remainder block.

Assignees

• Advanced Micro Devices Inc

Inventors

• Evers Marius
• Williams Douglas
• Venkatachar Ashok T
• Kalaiselvan Sudherssen

Classifications

• G06F9/30058

  Conditional branch instructions · CPC title

• G06F9/3844

  using dynamic branch prediction, e.g. using branch history tables · CPC title

• G06F9/264

  Microinstruction selection based on results of processing · CPC title

• G06F9/3842

  Speculative instruction execution · CPC title

• G06F9/3861

  Recovery, e.g. branch miss-prediction, exception handling (error detection or correction G06F11/00) · CPC title