NEXT FETCH PREDICTOR RETURN ADDRESS STACK

• US 20140344558A1
• Filed: 05/14/2013
• Published: 11/20/2014
• Est. Priority Date: 05/14/2013
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Gunna, Ramesh B., Blasco-Allue, Conrado, Holman, Douglas C.
• Granted Patent: US 9,405,544 B2
• Time in Patent Office: Days
• US Class Current: 712/239
• CPC Class Codes: G06F 9/30054 Unconditional branch instructions
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer
• CPC Class Codes: G06F 9/382 Pipelined decoding, e.g. using predecoding
• CPC Class Codes: G06F 9/3848 using hybrid branch prediction, e.g. selection between prediction techniques

Abstract

A system and method for efficient branch prediction. A processor includes a next fetch predictor to generate a fast branch prediction for branch instructions at an early pipeline stage. The processor also includes a main return address stack (RAS) at a later pipeline stage for predicting the target of return instructions. When a return instruction is encountered, the prediction from the next fetch predictor is replaced by the top of the main RAS. If there are any recent call or return instructions in flight toward the main RAS, then a separate prediction is generated by a mini-RAS.

Claims

1. A processor comprising:

a return address stack (RAS) configured to store return addresses associated with call branch instructions;

a next fetch prediction unit configured to predict a next fetch address based on a current fetch address;

responsive to determining a current fetch address corresponds to a return branch instruction, the next fetch prediction unit is configured to generate the next fetch address using an address from the RAS.

2. The processor as recited in claim 1, wherein the next fetch prediction unit is configured to store entries for encountered branch instructions.

3. The processor as recited in claim 2, wherein each entry of the next fetch prediction unit includes an indicator to indicate if the entry corresponds to a return branch instruction.

4. The processor as recited in claim 3, wherein each entry of the next fetch prediction unit further includes a next fetch address associated with the encountered branch instruction.

5. The processor as recited in claim 4, wherein the RAS is updated in a later pipeline stage than the next fetch prediction unit predicts a next fetch address.

6. The processor as recited in claim 4, wherein each entry of the next fetch prediction unit further includes an indicator to indicate if the entry corresponds to a call branch instruction.

7. The processor as recited in claim 1, wherein the next fetch prediction unit predicts the next fetch address based on the current fetch address in a single clock cycle.

8. A method comprising:

performing a lookup of a next fetch prediction unit with a current fetch address; and

selecting a top of a main return address stack as a next fetch address responsive to determining that the current fetch address is associated with a return instruction and that there are no in-flight call or return instructions toward the main return address stack (RAS).

9. The method as recited in claim 8, further comprising a mini-RAS generating the next fetch address responsive to determining that the current fetch address is associated with a return instruction and that there is at least one in-flight call or return instruction toward the main RAS.

10. The method as recited in claim 9, wherein the main RAS is located at a later pipeline stage than the mini-RAS.

11. The method as recited in claim 8, further comprising tracking any in-flight call and return branch instructions that have not yet updated the main RAS.

12. The method as recited in claim 11, further comprising generating the next fetch address by adding an offset to a fetch address corresponding to a previous call branch instruction responsive to detecting that the current fetch address is associated with a return instruction and that the previous call branch instruction is currently in-flight and has not yet updated the main RAS.

13. The method as recited in claim 12, wherein the lookup of the next fetch prediction unit is performed responsive to determining a fetch group corresponding to the current fetch address includes a branch instruction.

14. An apparatus comprising:

a next fetch predictor configured to generate a next fetch address based on a current fetch address;

a main return address stack (RAS); and

a mini-RAS configured to track in-flight call and return instructions toward the main RAS.

15. The apparatus as recited in claim 14, wherein the next fetch predictor includes a cache for storing entries associated with branch instructions.

16. The apparatus as recited in claim 15, wherein the next fetch predictor is configured to perform a lookup of the cache with the current fetch address.

17. The apparatus as recited in claim 16, wherein the next fetch predictor is configured to use an address stored in a hit entry as the next fetch address responsive to determining that the lookup of the cache with the current fetch address is a hit and that the hit entry does not correspond to a return or call branch instruction.

18. The apparatus as recited in claim 14, wherein the next fetch predictor is configured to generate a next fetch address from a top of the main RAS responsive to determining that a current fetch address corresponds to a return branch instruction and that are no in-flight call or return instructions.

19. The apparatus as recited in claim 18, wherein the next fetch prediction unit is configured to determine that there are no in-flight call or return instructions by receiving an indication from the mini-RAS.

20. The apparatus as recited in claim 14, wherein the main RAS is updated at a later time than the mini-RAS.