Speculative load issue
View Patent ↗A method and load and store buffer for issuing a load instruction to a data cache. The method includes determining whether there are any unresolved store instructions in the store buffer that are older than the load instruction. If there is at least one unresolved store instruction in the store buffer older than the load instruction, it is determined whether the oldest unresolved store instruction in the store buffer is within a speculation window for the load instruction. If the oldest unresolved store instruction is within the speculation window for the load instruction, the load instruction is speculatively issued to the data cache. Otherwise, the load instruction is stalled until any unresolved store instructions outside the speculation window are resolved. The speculation window is a short window that defines a number of instructions or store instructions that immediately precede the load instruction.
1. A method of issuing to a data cache a load instruction in a program, the method comprising:
determining at a load and store logic unit whether there are any unresolved store instructions in a store buffer that are older than the load instruction;
in response to determining that there is at least one unresolved store instruction in the store buffer older than the load instruction, determining at the load and store logic unit whether the oldest unresolved store instruction in the store buffer is within a speculation window for the load instruction, wherein the speculation window for any load instruction in the program covers a predetermined number of instructions immediately preceding that load instruction or a predetermined number of store instructions immediately preceding that load instruction; and
in response to determining that the oldest unresolved store instruction is within the speculation window for the load instruction, speculatively issuing the load instruction to the data cache.
2. An apparatus with a load and store buffer arranged to issue to a data cache a load instruction in a program, the load and store buffer comprising:
a store buffer for storing one or more store instructions; and
a load and store logic unit in communication with the store buffer, the load and store logic unit configured to:
determine whether there are any unresolved store instructions in the store buffer that are older than the load instruction,
in response to determining that there is at least one unresolved store instruction in the store buffer older than the load instruction, determining whether the oldest unresolved store instruction in the store buffer is within a speculation window for the load instruction, wherein the speculation window for any load instruction in the program covers a predetermined number of instructions immediately preceding that load instruction or a predetermined number of store instructions immediately preceding that load instruction, and
in response to determining that the oldest unresolved store instruction is within the speculation window for the load instruction, speculatively issuing the load instruction to the data cache.
3. The apparatus of claim 2 , wherein each store instruction writes to a memory address and an unresolved store instruction is a store instruction where the memory address is unresolved.
4. The apparatus of claim 3 , wherein the store buffer comprises memory address valid data for each store instruction in the store buffer, and the load and store logic unit determines whether there are any unresolved store instructions in the store buffer that are older than the load instruction by at least analyzing the memory address valid data in the store buffer.
5. The apparatus of claim 2 , wherein the store buffer comprises an ID for each store instruction in the store buffer.
6. The apparatus of claim 5 , wherein the load and store logic unit determines whether there are any unresolved store instructions in the store buffer that are older than the load instruction by at least comparing an ID associated with the load instruction with the IDs of the store instructions in the store buffer.
7. The apparatus of claim 5 , wherein the load and store logic unit determines whether the oldest unresolved store instruction in the store buffer is within the speculation window for the load instruction by at least:
identifying a start of the speculation window as an ID associated with the instruction in the program immediately preceding the load instruction;
identifying an end of the speculation window as an ID associated with the Xth instruction in the program immediately preceding the load instruction, wherein X is the size of the speculation window; and
comparing the IDs of the unresolved store instructions in the store buffer to the start and end of the speculation window to determine if the unresolved store instructions lie within the speculation window.
8. The apparatus of claim 5 wherein the IDs are re-order buffer IDs.
9. The apparatus of claim 2 , wherein the load and store logic unit determines whether the oldest unresolved store instruction in the store buffer is within the speculation window for the load instruction by at least:
identifying X store instructions in the store buffer immediately preceding the load instruction, wherein X is a size of the speculation window; and
determining whether there are any unresolved store instructions in the store buffer that are older than the identified instructions.
10. The apparatus of claim 9 , wherein the load and store logic unit identifies X store instructions in the store buffer immediately preceding the load instruction by at least comparing a re-order buffer ID associated with the load instruction to re-order buffer IDs associated with the store instructions in the store buffer.
11. The apparatus of claim 2 , wherein the load and store logic unit is further configured to:
determine whether the program comprises a function return instruction within a function window of the load instruction; and
in response to determining that the program comprises a function return instruction within the function window of the load instruction, stalling the load instruction.
12. The apparatus of claim 2 , wherein the size of the speculation window is fixed.
13. The apparatus of claim 2 , wherein the load and store logic unit is further configured to dynamically adjust the size of the speculation window.
14. The apparatus of claim 13 , wherein the load and store logic unit dynamically adjusts the size of the speculation window by at least:
obtaining metric data at the load and store logic unit;
updating a resizing metric based on the obtained metric data;
periodically comparing the resizing metric to at least one of a lower threshold and an upper threshold;
in response to determining that the resizing metric is less than the lower threshold, adjusting the size of the speculation window; and
in response to determining that the resizing metric is greater than the upper threshold, adjusting the size of the speculation window.
15. The apparatus of claim 14 , wherein the metric data is one of:
a number of rewinds of speculatively executed load instructions that have occurred in a clock cycle and the resizing metric is a total count of the number of rewinds of speculatively executed load instructions; and
a number of unnecessary stalls of load instructions that have occurred in a clock cycle and the resizing metric is a total count of the number of unnecessary stalls.
16. The apparatus of claim 14 , wherein the resizing metric is compared to at least one of the lower threshold and the upper threshold after a predetermined number of cycles have elapsed since the last comparison.
17. The apparatus of claim 2 , wherein the load and store logic unit is further configured to stall the load instruction if the oldest unresolved store instruction is outside the speculation window.
18. The apparatus of claim 2 , wherein the load and store logic unit is further configured to non-speculatively issue the load instruction to the data cache if there are no unresolved store instructions in the store buffer older than the load instruction.
19. A non-transitory computer readable storage medium having encoded thereon computer readable program code for generating a processor comprising the apparatus of claim 2 .
20. A non-transitory computer readable storage medium having encoded thereon computer readable program code for generating a processor configured to perform a method comprising:
determining at a load and store logic unit whether there are any unresolved store instructions in a store buffer that are older than a load instruction to be issued to a data cache;
in response to determining that there is at least one unresolved store instruction in the store buffer older than the load instruction, determining at the load and store logic unit whether the oldest unresolved store instruction in the store buffer is within a speculation window for the load instruction, the speculation window for any load instruction in the program covering a predetermined number of instructions immediately preceding that load instruction or a predetermined number of store instructions immediately preceding that load instruction; and
in response to determining that the oldest unresolved store instruction is within the speculation window for the load instruction, speculatively issuing the load instruction to the data cache.