Next fetch prediction return table

• US 10,445,102 B1
• Filed: 09/18/2017
• Issued: 10/15/2019
• Est. Priority Date: 09/18/2017
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Pistol, Constantin, Kountanis, Ian D.
• Primary Examiner(s): Faherty, Corey S
• Application Number:
  US15/707,834
• Time in Patent Office: 757 Days
• Field of Search: None
• CPC Class Codes: G06F 9/30047 Prefetch instructions; cache control instructions
• CPC Class Codes: G06F 9/3816 Instruction alignment, e.g. cache line crossing
• CPC Class Codes: G06F 9/3832 Value prediction for operands; operand history buffers
• CPC Class Codes: G06F 9/3844 using dynamic branch prediction, e.g. using branch history tables
• CPC Class Codes: G06F 9/3848 using hybrid branch prediction, e.g. selection between prediction techniques

Abstract

Systems, apparatuses, and methods for efficient program flow prediction. After receiving a current fetch address, a first predictor performs a lookup of a first table. When the lookup results in a miss and the first table has no available entries, the first predictor overwrites a given entry of the first table with the received fetch address, in response to detecting a strength value for the given entry is below a threshold. Otherwise, in response to detecting no entries of the first table have a strength value below the threshold, the first predictor allocates an entry in the second table for the received fetch address. When an indication of a target address for the received fetch address is a return address for a function call, a third predictor allocates an entry of a third table with the received fetch address.

Claims

1. An apparatus comprising:

a cache comprising a first table, wherein the first table comprises a plurality of entries;

an array comprising a second table, wherein the second table comprises a plurality of entries; and

control logic, wherein in response to determining a received fetch address misses in the first table and the first table has no entries available for allocation, the control logic is configured to;

overwrite a given entry of the first table with the received fetch address, in response to detecting a strength value for the given entry is below a threshold; and

allocate an entry in the second table for the received fetch address, in response to detecting no entries of the first table have a strength value below the threshold.

2. The apparatus as recited in claim 1, wherein the control logic is configured to allocate the entry in the second table for the received fetch address in further response to determining the received fetch address is not currently stored in the second table.

3. The apparatus as recited in claim 1, wherein the control logic is further configured to overwrite a first entry of the first table with at least a fetch address stored in a second entry of the second table, in response to determining:

a strength value for the first entry is below the threshold; and

an identifier stored in the first entry identifies the second entry.

4. The apparatus as recited in claim 3, wherein the first entry is configured to store an indication of hysteresis based at least in part on a branch history.

5. The apparatus as recited in claim 3, wherein in response to receiving a next fetch address corresponding to a given fetch address, the control logic is further configured to:

determine the given fetch address hits in the first table, wherein a matching entry stores at least a portion of the given fetch address; and

reduce a strength value of the matching entry, in response to determining the next fetch address does not match a given target address stored in the matching entry.

6. The apparatus as recited in claim 5, wherein the control logic is further configured to increase the strength value of the matching entry, in response to determining the next fetch address matches the given target address.

7. The apparatus as recited in claim 1, further comprising a third table comprising a plurality of entries, wherein in response to an indication that a target address for a given fetch address is a return address for a function call, the control logic is further configured to allocate an entry in the third table for the given fetch address.

8. The apparatus as recited in claim 7, wherein

the entry in the third table is configured to store a tag portion of the given fetch address;

and

the entry of the third table does not store an indication of a target address.

9. The apparatus as recited in claim 3, wherein storage of data in the first table follows a set associative arrangement.

10. The apparatus as recited in claim 3, wherein storage of data in the second table follows a first-in-first-out arrangement.

11. A method comprising:

storing indications of target addresses in a plurality of entries of a first table;

storing indications of target addresses in a plurality of entries of a second table;

wherein in response to determining a received fetch address misses in the first table and the first table has no entries available for allocation;

overwriting a given entry of the first table with the received fetch address, in response to detecting a strength value for the given entry is below a threshold; and

allocating an entry in the second table for the received fetch address, in response to detecting no entries of the first table have a strength value below the threshold.

12. The method as recited in claim 11, further comprising allocating the entry in the second table for the received fetch in further response to determining the received fetch address is not currently stored in the second table.

13. The method as recited in claim 11, further comprising overwriting a first entry of the first table with at least a fetch address stored in a second entry of the second table, in response to determining:

a strength value for the first entry is below the threshold; and

an identifier stored in the first entry identifies the second entry.

14. The method as recited in claim 13, wherein in response to receiving a next fetch address corresponding to a given fetch address, the method further comprises:

determining the given fetch address hits in the first table, wherein a matching entry stores at least a portion of the given fetch address; and

reducing a strength value of the matching entry, in response to determining the next fetch address does not match a given target address stored in the matching entry.

15. The method as recited in claim 11, wherein in response to an indication that a target address for a given fetch address is a return address for a function call, the method further comprises allocating an entry in a third table for the given fetch address.

16. A processor comprising:

a first predictor comprising a first table;

a second predictor comprising a second table;

wherein in response to determining a received fetch address misses in the first table and the first table has no entries available for allocation, the first predictor is configured to;

overwrite a given entry of the first table with the received fetch address, in response to detecting a strength value for the given entry is below a threshold; and

allocate an entry in the second table for the received fetch address, in response to detecting no entries of the first table have a strength value below the threshold.

17. The processor as recited in claim 16, wherein the second predictor is configured to allocate the entry in the second table for the received fetch address in further response to determining the received fetch address is not currently stored in the second table.

18. The processor as recited in claim 16, wherein the first predictor is further configured to overwrite a first entry of the first table with at least a fetch address stored in a second entry of the second table, in response to determining

a strength value for the first entry is below the threshold;

and

an identifier stored in the first entry identifies the second entry.

19. The processor as recited in claim 18, further comprising a branch predictor, wherein in response to receiving a next fetch address that corresponds to a given fetch address from the branch predictor, the first predictor is configured to:

determine the given fetch address hits in the first table, wherein a matching entry stores at least a portion of the given fetch address; and

reduce a strength value of the matching entry, in response to determining the next fetch address does not match a given target address stored in the matching entry.

20. The processor as recited in claim 16, further comprising a third predictor comprising a third table, wherein in response to an indication that a target address for a given fetch address is a return address for a function call, the third predictor is configured to allocate an entry in the third table for the given fetch address.