Slice construction for pre-executing data dependent loads

Abstract

Systems and methods for constructing an instruction slice for prefetching data of a data-dependent load instruction include a slicer for identifying a load instruction in an instruction sequence as a first occurrence of a qualified load instruction which will miss in a last-level cache. A commit buffer stores information pertaining to the first occurrence of the qualified load instruction and shadow instructions which follow. For a second occurrence of the qualified load instruction, an instruction slice is constructed from the information in the commit buffer to form a slice payload. A pre-execution engine pre-executes the instruction slice based on the slice payload to determine an address from which data is to be fetched for execution of a third and any subsequent occurrences of the qualified load instruction. The data is prefetched from the determined address for the third and any subsequent occurrence of the qualified load instruction.

What is claimed is: 
     
       1. A method of instruction processing, the method comprising:
 identifying a load instruction in an instruction sequence executable by a processor as a first occurrence of a qualified load instruction which will encounter a miss in a last-level cache of a cache hierarchy associated with the processor, wherein identifying the load instruction as a first occurrence of the qualified load instruction comprises determining that a number of cycles that the load instruction is waiting for load data in a load queue of the processor is greater than a number of cycles which will be incurred in servicing the load instruction from the last-level cache if there is a hit in the last-level cache for the load data; 
 storing information pertaining to the first occurrence of the qualified load instruction and shadow instructions which follow the qualified load instruction in a commit buffer; 
 upon detecting a second occurrence of the qualified load instruction in one of the shadow instructions, constructing an instruction slice from the information in the commit buffer to form a slice payload; 
 pre-executing the instruction slice based on the slice payload to determine an address from which data is to be fetched for executing a third occurrence of the qualified load instruction; and 
 prefetching the data from the address for the third occurrence of the qualified load instruction. 
 
     
     
       2. The method of  claim 1 , further comprising storing a program counter (PC) of the first occurrence of the qualified load instruction in a concurrent slice list if the concurrent slice list does not contain the PC. 
     
     
       3. The method of  claim 2 , wherein the slice payload comprises one or more of the program counters (PCs), instruction encoding, input registers, or output registers of the first and second occurrences of the qualified load instruction and one or more other shadow instructions. 
     
     
       4. The method of  claim 3  comprising detecting the second occurrence of the qualified load instruction based on detecting that the concurrent slice list comprises the PC of the second occurrence of the qualified load instruction. 
     
     
       5. The method of  claim 4 , further comprising creating one or more live-ins vectors for the instruction slice, walking backwards from the second occurrence of the qualified load instruction to the first occurrence of the qualified load instruction in an instruction buffer, wherein the one or more live-ins vectors comprise a set of live-ins, wherein the live-ins are input registers which are not produced as output registers by any of the instructions in the instruction slice. 
     
     
       6. The method of  claim 5  wherein creating the one or more live-ins vectors comprises:
 creating a load slice live-ins vector comprising live-ins for instructions which do not include branch or compare instructions in the instruction slice; 
 creating a branch slice live-ins vector comprising live-ins for instructions which include branch or compare instructions in the instruction slice; and 
 merging the load slice live-ins vector and the branch slice live-ins vector to generate a merged slice live-ins vector. 
 
     
     
       7. The method of  claim 5 , further comprising:
 creating a load slice program counter (PC) vector comprising PCs for instructions which do not include branch or compare instructions in the instruction slice; 
 creating a branch slice PC vector comprising PCs for instructions which include branch or compare instructions in the instruction slice; and 
 merging the load slice PC vector and the branch slice PC vector to generate a merged slice PC vector. 
 
     
     
       8. The method of  claim 7 , wherein pre-executing the instruction slice comprises providing the merged slice live-ins vector and the merged slice PC vector as part of the slice payload to be stored in a slice cache, and for the third occurrence of the load instruction, upon detection that the slice cache comprises the slice payload, providing the slice payload to a pre-execution engine and executing instructions based on the slice payload in the pre-execution engine to determine the address. 
     
     
       9. The method of  claim 8 , comprising prefetching the data into a buffer coupled to the last-level cache, wherein the buffer is provided in a memory controller coupled to the last-level cache and configured to control access to an external memory system. 
     
     
       10. The method of  claim 2 , further comprising disabling the commit buffer if the concurrent slice list is empty. 
     
     
       11. The method of  claim 2 , wherein the concurrent slice list and the commit buffer are first-in-first-out (FIFO) buffers. 
     
     
       12. An apparatus comprising:
 a processor configured to execute an instruction sequence; 
 a slicer of the processor configured to identify a load instruction in the instruction sequence as a first occurrence of a qualified load instruction which will encounter a miss in a last-level cache of a cache hierarchy associated with the processor, wherein the slicer is configured to identify the load instruction as a first occurrence of the qualified load instruction based on a determination that a number of cycles that load instruction is waiting in a load queue of the processor is greater than a number of cycles which will be incurred for the load instruction to be serviced from the last-level cache if there is a hit in the last-level cache for the load data; 
 a commit buffer configured to store information pertaining to the first occurrence of the qualified load instruction and shadow instructions which follow the qualified load instruction; 
 wherein the slicer is configured to, upon detection of a second occurrence of the qualified load instruction in one of the shadow instructions, construct an instruction slice from the information in the commit buffer to form a slice payload; and 
 a pre-execution engine configured to pre-execute the instruction slice based on the slice payload to determine an address from which data is to be fetched for execution of a third occurrence of the qualified load instruction; and 
 a memory controller configured to prefetch the data from the address for the third occurrence of the qualified load instruction. 
 
     
     
       13. The apparatus of  claim 12 , further comprising a concurrent slice list configured to store a program counter (PC) of the first occurrence of the qualified load instruction if the concurrent slice list does not contain the PC. 
     
     
       14. The apparatus of  claim 13 , wherein the slice payload comprises one or more of the program counters (PCs), instruction encoding, input registers, or output registers of the first and second occurrences of the qualified load instruction and one or more other shadow instructions. 
     
     
       15. The apparatus of  claim 14 , wherein the slicer is configured to detect the second occurrence of the qualified load instruction if the concurrent slice list comprises the PC of the second occurrence of the qualified load instruction. 
     
     
       16. The apparatus of  claim 15 , further comprising one or more live-ins vectors for the instruction slice, wherein the one or more live-ins vectors comprise a set of live-ins, wherein the live-ins are input registers which are not produced as output registers by any of the instructions in the instruction slice. 
     
     
       17. The apparatus of  claim 16  wherein the one or more live-ins vectors comprises:
 a load slice live-ins vector comprising live-ins for instructions which do not include branch or compare instructions in the instruction slice; 
 a branch slice live-ins vector comprising live-ins for instructions which include branch or compare instructions in the instruction slice; and 
 a merged slice live-ins vector comprising the load slice live-ins vector merged with the branch slice live-ins vector. 
 
     
     
       18. The apparatus of  claim 17 , further comprising:
 a load slice program counter (PC) vector comprising PCs for instructions which do not include branch or compare instructions in the instruction slice; 
 a branch slice PC vector comprising PCs for instructions which include branch or compare instructions in the instruction slice; and 
 a merged slice PC vector comprising the load slice PC vector merged with the branch slice PC vector. 
 
     
     
       19. The apparatus of  claim 18 , wherein the pre-execution engine is configured to pre-execute the instruction slice based on the merged slice live-ins vector and the merged slice PC vector to determine the address. 
     
     
       20. The apparatus of  claim 19 , wherein the memory controller comprises a buffer configured to store the prefetched data. 
     
     
       21. The apparatus of  claim 13 , wherein the commit buffer is configured to be disabled if the concurrent slice list is empty. 
     
     
       22. The apparatus of  claim 13 , wherein the concurrent slice list and the commit buffer comprise first-in-first-out (FIFO) buffers. 
     
     
       23. A non-transitory computer-readable medium comprising code, which, when executed by a computer, causes the computer to perform operations for instruction processing, the non-transitory computer-readable medium comprising:
 code for identifying a load instruction in an instruction sequence executable by a processor as a first occurrence of a qualified load instruction, wherein the code for identifying the load instruction as a first occurrence of the qualified load instruction comprises code for determining that a number of cycles that the load instruction is waiting for load data in a load queue of the processor is greater than a number of cycles which will be incurred in servicing the load instruction from the last-level cache if there is a hit in the last-level cache for the load data; 
 code for storing information pertaining to the first occurrence of the qualified load instruction and shadow instructions which follow the qualified load instruction in a commit buffer; 
 code for, upon detecting a second occurrence of the qualified load instruction in one of the shadow instructions, constructing an instruction slice from the information in the commit buffer to form a slice payload; 
 code for pre-executing the instruction slice based on the slice payload to determine an address from which data is to be fetched for executing a third occurrence of the qualified load instruction; and 
 code for prefetching the data from the address for the third occurrence of the qualified load instruction. 
 
     
     
       24. The non-transitory computer-readable medium of  claim 23 , further comprising code for storing a program counter (PC) of the first occurrence of the qualified load instruction in a concurrent slice list if the concurrent slice list does not contain the PC. 
     
     
       25. The non-transitory computer-readable medium of  claim 24 , wherein the slice payload comprises one or more of the program counters (PCs), instruction encoding, input registers, or output registers of the first and second occurrences of the qualified load instruction and one or more other shadow instructions. 
     
     
       26. The non-transitory computer-readable medium of  claim 25  comprising code for detecting the second occurrence of the qualified load instruction based on code for detecting that the concurrent slice list comprises the PC of the second occurrence of the qualified load instruction. 
     
     
       27. An apparatus comprising:
 means for identifying a load instruction in an instruction sequence executable by a processor as a first occurrence of a qualified load instruction, wherein the means for identifying the load instruction as a first occurrence of the qualified load instruction comprises means for determining that a number of cycles that the load instruction is waiting for load data in a load queue of the processor is greater than a number of cycles which will be incurred in servicing the load instruction from the last-level cache if there is a hit in the last-level cache for the load data; 
 means for storing information pertaining to the first occurrence of the qualified load instruction and shadow instructions which follow the qualified load instruction; 
 means for, upon detecting a second occurrence of the qualified load instruction in one of the shadow instructions, constructing an instruction slice from the information in the means for storing to form a slice payload; 
 means for pre-executing the instruction slice based on the slice payload to determine an address from which data is to be fetched for executing a third occurrence of the qualified load instruction; and 
 means for prefetching the data from the address for the third occurrence of the qualified load instruction.