Branch target buffer with early return prediction

Patent metadata

Field	Value
Publication number	US-11055098-B2
Application number	US-201816043293-A
Country	US
Kind code	B2
Filing date	Jul 24, 2018
Priority date	Jul 24, 2018
Publication date	Jul 6, 2021
Grant date	Jul 6, 2021

Abstract

A processor includes a branch target buffer (BTB) having a plurality of entries whereby each entry corresponds to an associated instruction pointer value that is predicted to be a branch instruction. Each BTB entry stores a predicted branch target address for the branch instruction, and further stores information indicating whether the next branch in the block of instructions associated with the predicted branch target address is predicted to be a return instruction. In response to the BTB indicating that the next branch is predicted to be a return instruction, the processor initiates an access to a return stack that stores the return address for the predicted return instruction. By initiating access to the return stack responsive to the return prediction stored at the BTB, the processor reduces the delay in identifying the return address, thereby improving processing efficiency.

First claim

What is claimed is:

1. A method comprising:
identifying, in response to a first branch instruction and based on a first entry of a branch target buffer (BTB) of a processor, a prediction of a first branch return instruction, the first branch return instruction different from the first branch instruction; and
in response to identifying the prediction of the first branch return instruction, initiating access to a stack of branch return addresses of the processor to retrieve an address for provision to an instruction fetch stage of the processor.

2. The method of claim 1 , wherein the first entry comprises:
a first return field indicating the prediction of the first branch return instruction; and
a first branch field indicating a first predicted branch address.

3. The method of claim 2 , wherein the prediction of the first branch return instruction comprises a prediction that the first predicted branch address corresponds to a return instruction.

4. The method of claim 3 , further comprising setting the first entry to indicate no return prediction in response to identifying that the first branch return instruction was mispredicted.

5. The method of claim 1 , further comprising:
in response to determining that the first entry indicates a prediction of a return instruction, suppressing a subsequent access to the BTB.

6. The method of claim 1 , further comprising:
identifying, based on a second entry of the BTB, a prediction of a second branch return instruction; and
in response to identifying the prediction of the second branch return instruction, initiating access to the stack of branch return addresses.

7. A method, comprising:
accessing a first entry of a branch target buffer (BTB) based on a first program counter value corresponding to a first branch instruction;
branching to a first instruction address based on a first branch address field of the first entry of the BTB; and
in response to a first return field of the first entry of the BTB indicating that the first instruction address corresponds to a return instruction different from the first branch instruction, initiating access to a stack of branch return addresses to retrieve an address for provision to an instruction fetch stage of a processor.

8. The method of claim 7 , further comprising:
in response to determining that the first instruction address corresponds to the return instruction, storing an indication of a return at the first return field.

9. The method of claim 7 , wherein initiating access to the stack of branch return addresses comprises returning an instruction address from the stack of branch return addresses concurrent with branching to the first instruction address.

10. The method of claim 7 , further comprising:
in response to the first return field indicating that the first instruction address corresponds to the return instruction, suppressing a subsequent access to the BTB.

11. The method of claim 10 , wherein suppressing the subsequent access comprises suppressing an access to the BTB that is expected to result in a BTB hit on a predicted return instruction.

12. The method of claim 7 , further comprising:
accessing a second entry of the BTB based on a second program counter value;
branching to a second instruction address based on a second branch address field of the first entry of the BTB; and
in response to a second return field of the second entry of the BTB indicating that the second instruction address corresponds to a return instruction, initiating access to the stack of branch return addresses.

13. The method of claim 7 , further comprising:
setting the first entry to indicate no return prediction in response to identifying that the return instruction was mispredicted.

14. A processor, comprising:
a branch target buffer (BTB) comprising a first entry identifying a prediction of a first branch return instruction, the first entry associated with a first branch instruction different than the first branch return instruction;
a stack of branch return addresses; and
a processor core configured to, in response to the first entry of the BTB indicating the prediction of the first branch return instruction, initiating access to the stack of branch return addresses to retrieve an address for provision to an instruction fetch stage of the processor.

15. The processor of claim 14 , wherein the first entry of the BTB comprises:
a first return field indicating the prediction of the first branch return instruction; and
a first branch field indicating a first predicted branch address.

16. The processor of claim 15 , wherein the prediction of the first branch return instruction comprises a prediction that the first predicted branch address corresponds to a return instruction.

17. The processor of claim 15 , wherein the processor core is configured to:
set the first entry to indicate no return prediction in response to identifying that the first branch return instruction was mispredicted.

18. The processor of claim 14 , wherein the processor core is configured to:
in response to determining that the first entry indicates a return instruction, suppress a subsequent access to the BTB.

19. The processor of claim 14 , wherein the processor core is configured to:
in response to determining that the first entry indicates a return instruction, suppress a subsequent access to the BTB that is expected to access the first branch return instruction.

20. The processor of claim 14 , wherein:
the BTB comprises a second entry indicating a prediction of a second branch return instruction; and
the processor core is configured to, in response to identifying the prediction of the second branch return instruction, initiate access to the stack of branch return addresses.

Assignees

• Advanced Micro Devices Inc

Inventors

• Thyagarajan Aparna
• Evers Marius
• Annamalai Arunachalam

Classifications

• G06F9/323

  for indirect branch instructions · CPC title

• G06F9/30054

  Unconditional branch instructions · CPC title

• G06F9/30058

  Conditional branch instructions · CPC title

• G06F9/3844

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

• G06F9/3806 Primary

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