Callgraph signature prefetch

• US 10,642,618 B1
• Filed: 06/02/2016
• Issued: 05/05/2020
• Est. Priority Date: 06/02/2016
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Hakewill, James R., Gupta, Nikhil
• Primary Examiner(s): Partridge, William B
• Application Number:
  US15/171,316
• Time in Patent Office: 1,433 Days
• Field of Search: 712207
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 12/126 with special data handling, e.g. priority of data or instructions, handling errors or pinning
• CPC Class Codes: G06F 2212/452 Instruction code
• CPC Class Codes: G06F 2212/6022 Using a prefetch buffer or dedicated prefetch cache
• CPC Class Codes: G06F 9/30054 Unconditional branch instructions
• CPC Class Codes: G06F 9/3802 Instruction prefetching
• CPC Class Codes: G06F 9/3804 for branches, e.g. hedging, branch folding
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer

Abstract

A method and system for prefetching instructions is disclosed. A signature may be updated in response to determining that a received instruction initiates a transition in function. A plurality of entries stored in a memory may be searched in response to determining the signature has been updated and a prefetch operation may be initiated in response to determining that the signature matches a given entry of the plurality of entries.

Claims

1. An apparatus, comprising:

a memory configured to store a table, wherein the table includes a plurality of entries; and

circuitry configured to;

receive a first instruction and a second instruction; and

in response to a determination that the first instruction initiates a transition between a first function or subroutine and a second function or subroutine, update a signature by performing a processing operation on previous call or return target addresses;

in response to a cache miss determination, generate a training signature using a previous signature that was valid at a time period before the cache miss;

store the training signature in a particular entry of the plurality of entries;

search the plurality of entries in response to a determination that the signature has been updated;

determine a candidate prefetch operation in response to a determination that the signature matches a given entry of the plurality of entries; and

initiate the candidate prefetch operation based on a predicted usefulness of the candidate prefetch operation.

2. The apparatus of claim 1, wherein to generate the training signature the circuitry is configured to determine the training signature using contents of a return-address stack delayed by a number of call/return transitions.

3. The apparatus of claim 2, wherein to update the plurality of entries, the circuitry is further configured to select a particular entry of the plurality of entries for replacement based on a usefulness associated with the particular entry.

4. The apparatus of claim 2, wherein to update the plurality of entries, the circuitry is further configured to update the plurality of entries based on a usefulness of a previous prefetch operation.

5. The apparatus of claim 1, wherein to generate the training signature, the circuitry is configured to delay a change in the signature by a particular number of call/return transitions.

6. The apparatus of claim 1, wherein the circuitry is further configured to update the signature in response to the determination that the first instruction initiates the transition between the first function or subroutine and the second function or subroutine based on a history of branch instructions, wherein the history of branch instructions is sampled in response to a detection of a call or return function.

7. The apparatus of claim 1, wherein to search the plurality of entries, the circuitry is further configured to check a filter, wherein the filter includes at least one filter entry corresponding to a signature used in a previous search of the plurality of entries.

8. A method, comprising:

receiving a first instruction and a second instruction;

in response to determining that the first instruction initiates a transition between a first function or subroutine and a second function or subroutine, updating a signature by performing processing operation on previous call or return target addresses;

in response to detecting a cache miss, generating a training signature using a previous signature that was valid at a time period before the cache miss;

storing the training signature in a particular entry of a plurality of entries that are stored in a memory;

searching the plurality of entries, in response to a determination that the signature has been updated;

determining a candidate prefetch operation in response to determining that the signature matches a given entry of the plurality of entries; and

initiating the candidate prefetch operation based on a predicted usefulness of the candidate prefetch operation.

9. The method of claim 8, further comprising updating the plurality of entries in response to detecting the cache miss, wherein the cache miss results in a delay in fetching a new instruction.

10. The method of claim 9, wherein updating the plurality of entries comprises selecting a particular entry of the plurality of entries for replacement based on a usefulness associated with the particular entry.

11. The method of claim 8, further comprising updating the plurality of entries based on a usefulness of a previous prefetch operation.

12. The method of claim 8, wherein generating the training signature includes delaying a change in the signature by a particular number of call/return transitions.

13. The method of claim 8, further comprising updating the signature in response to determining that the first instruction initiates the transition between the first function or subroutine and the second function or subroutine based on a history of branch instructions, wherein the history of branch instructions is sampled in response to a detection of a call or return function.

14. A system, comprising:

a memory; and

a processor including an instruction cache, wherein the processor is configured to;

fetch a first instruction and a second instruction from the instruction cache;

in response to a determination that the first instruction initiates a transition between a first function or subroutine and second function or subroutine, update a signature by performing a processing operation on previous call or return target addresses;

in response to a cache miss, generate a training signature using a previous signature valid at a time period before the cache miss;

store the training signature in a particular entry of a plurality of entries that is stored in a table included in the memory;

search the plurality of entries, in response to a determination that the signature has been updated;

determine a candidate prefetch operation in response to a determination that the signature matches a given entry of the plurality of entries; and

initiate the candidate prefetch operation based on a predicted usefulness of the candidate prefetch operation.

15. The system of claim 14, wherein the processor is further configured to update the plurality of entries in response to a detection of the cache miss, wherein the cache miss results in a delay in fetching a new instruction.

16. The system of claim 15, wherein to update the plurality of entries, the processor is further configured to select a particular entry of the plurality of entries for replacement based on a usefulness associated with the particular entry.

17. The system of claim 15, wherein the processor is further configured to update the plurality of entries based on a usefulness of a previous prefetch operation.

18. The system of claim 14, wherein the processor is further configured to update the signature in response to the determination that the first instruction initiates the transition in function based on a history of received call or return instructions.

19. The system of claim 14, wherein to generate the training signature, the processor is configured to delay a change in the signature by a particular number of call/return transitions.

20. The system of claim 14, wherein to search the plurality of entries, the processor is further configured to check a filter, wherein the filter includes at least one filter entry corresponding to a signature used in a previous search of the plurality of entries.