Load/store dependency predictor optimization for replayed loads

• US 10,437,595 B1
• Filed: 03/15/2016
• Issued: 10/08/2019
• Est. Priority Date: 03/15/2016
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Kanapathipillai, Pradeep, Meier, Stephan G., Williams, III, Gerard R., Agarwal, Mridul, Kothari, Kulin N.
• Primary Examiner(s): Petranek, Jacob
• Application Number:
  US15/070,435
• Time in Patent Office: 1,302 Days
• CPC Class Codes: G06F 9/30021 Compare instructions, e.g. Greater-Than, Equal-To, MINMAX
• CPC Class Codes: G06F 9/30145 Instruction analysis, e.g. decoding, instruction word fields
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/3838 Dependency mechanisms, e.g. register scoreboarding

Abstract

Systems, apparatuses, and methods for optimizing a load-store dependency predictor (LSDP). When a younger load instruction is issued before an older store instruction and the younger load is dependent on the older store, the LSDP is trained on this ordering violation. A replay/flush indicator is stored in a corresponding entry in the LSDP to indicate whether the ordering violation resulted in a flush or replay. On subsequent executions, a dependency may be enforced for the load-store pair if a confidence counter is above a threshold, with the threshold varying based on the status of the replay/flush indicator. If a given load matches on multiple entries in the LSDP, and if at least one of the entries has a flush indicator, then the given load may be marked as a multimatch case and forced to wait to issue until all older stores have issued.

Claims

1. A processor comprising:

a load-store dependency predictor comprising a table having a plurality of entries; and

circuitry configured to;

detect a first load instruction;

determine that the first load instruction matches a first entry in the table, wherein the first entry includes an indication as to whether a previous ordering violation resulted in a flush event or a replay event; and

responsive to determining the first load instruction caused a flush event during a previous execution of the first load instruction, establish a dependency of the first load instruction on a store instruction responsive to determining a confidence value stored in the first entry is greater than a first threshold;

and

responsive to determining the first load instruction caused a replay event during the previous execution of the first load instruction, establish a dependency of the first load instruction on the store instruction responsive to determining the confidence value stored in the first entry is greater than a second threshold different from the first threshold.

2. The processor as recited in claim 1, wherein the processor is configured to:

store an indication of a flush event in the first entry of the table responsive to detecting a flush event during execution of the first load instruction; and

store an indication of a replay event in the first entry responsive to detecting a replay event during execution of the first load instruction.

3. The processor as recited in claim 1, wherein the second threshold is greater than the first threshold.

4. The processor as recited in claim 1, further comprising a reservation station, wherein responsive to determining the first load instruction matches multiple entries of the table and responsive to determining all matching entries have replay indicators, the processor is configured to mark the first load instruction as not being a multimatch case in a corresponding reservation station entry.

5. The processor as recited in claim 4, wherein if the first load instruction is marked as not being a multimatch case, the reservation station is configured to issue the first load instruction prior to one or more older store instructions.

6. The processor as recited in claim 1, wherein the processor is configured to split the store instruction into a store address operation and a store data operation, wherein the first load instruction is dependent on the store instruction, wherein a replay event rather than a flush event occurs when the first load instruction issues after the store address operation but before the store data operation, and wherein a flush event rather than a replay event occurs when the first load instruction issues before both the store address operation and the store data operation.

7. The processor as recited in claim 1, further comprising a store queue, wherein the processor is configured to:

increment the confidence value responsive to determining the first load instruction received data from the store queue; and

decrement the confidence counter value responsive to determining the first load instruction did not receive data from the store queue.

8. A method comprising:

detecting a first load instruction;

determining that the first load instruction matches a first entry in a table of a load-store dependency predictor, wherein the first entry includes an indication as to whether a previous ordering violation resulted in a flush event or a replay event; and

responsive to determining the first load instruction caused a flush event during a previous execution of the first load instruction, establishing a dependency of the first load instruction on a store instruction responsive to determining a confidence value stored in the first entry is greater than a first threshold;

and

responsive to determining the first load instruction caused a replay event during the previous execution of the first load instruction, establishing a dependency of the first load instruction on the store instruction responsive to determining the confidence value stored in the first entry is greater than a second threshold different from the first threshold.

9. The method as recited in claim 8, further comprising:

storing an indication of a flush event in the first entry of the table responsive to detecting a flush event during execution of the first load instruction; and

storing an indication of a replay event in the first entry responsive to detecting a replay event during execution of the first load instruction.

10. The method as recited in claim 8, wherein the second threshold is greater than the first threshold.

11. The method as recited in claim 8, further comprising marking the first load instruction as not being a multimatch case in a corresponding reservation station entry responsive to determining the first load instruction matches on multiple entries of the table and responsive to determining all matching entries have replay indicators.

12. The method as recited in claim 11, further comprising issuing the first load instruction prior to one or more older store instructions responsive to determining the first load instruction is marked as not being a multimatch case.

13. The method as recited in claim 8, further comprising splitting the store instruction into a store address operation and a store data operation, wherein a first load instruction is dependent on the store instruction, wherein a replay rather than a flush occurs when the first load instruction issues after the store address operation but before the store data operation, and wherein a flush rather than a replay occurs when the first load instruction issues before both the store address operation and the store data operation.

14. The method as recited in claim 8, further comprising:

incrementing the confidence value responsive to determining the given load instruction received data from a store queue; and

decrementing the confidence value responsive to determining the given load instruction did not receive data from the store queue.

15. A computing system comprising:

a memory; and

a processor comprising a load-store dependency predictor, wherein the processor is configured to;

detect a first load instruction;

determine that the first load instruction matches a first entry in a table in the load-store dependency predictor, wherein the first entry includes an indication as to whether a previous ordering violation resulted in a flush event or a replay event; and

responsive to determining the first load instruction caused a flush event during a previous execution of the first load instruction, establish a dependency of the first load instruction on a store instruction responsive to determining a confidence value stored in the first entry is greater than a first threshold;

and

responsive to determining the first load instruction caused a replay event during the previous execution of the first load instruction, establish a dependency of the first load instruction on the store instruction responsive to determining the confidence value stored in the first entry is greater than a second threshold different from the first threshold.

16. The computing system as recited in claim 15, wherein the processor is configured to:

store an indication of a flush event in the first entry of the table responsive to detecting a flush event during execution of the first load instruction; and

store an indication of a replay event in the first entry responsive to detecting a replay event during execution of the first load instruction.

17. The computing system as recited in claim 15, wherein the second threshold is greater than the first threshold.

18. The computing system as recited in claim 15, wherein the processor further comprises a reservation station, wherein responsive to determining the first load instruction matches on multiple entries of the table and responsive to determining all matching entries have replay indicators, the processor is configured to mark the first load instruction as not being a multimatch case in a corresponding reservation station entry.

19. The computing system as recited in claim 18, wherein if the first load instruction is marked as not being a multimatch case, the reservation station is configured to issue the first load instruction prior to one or more older store instructions.

20. The computing system as recited in claim 15, wherein the processor is configured to split the store instruction into a store address operation and a store data operation, wherein a first load instruction is dependent on the store instruction, wherein a replay event rather than a flush event occurs when the first load instruction issues after the store address operation but before the store data operation, and wherein a flush event rather than a replay event occurs when the first load instruction issues before both the store address operation and the store data operation.