Load-store dependency predictor content management

• US 9,128,725 B2
• Filed: 05/04/2012
• Issued: 09/08/2015
• Est. Priority Date: 05/04/2012
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Meier, Stephan G., Mylius, John H., Williams, Gerard R. III, Vats, Suparn
• Primary Examiner(s): Caldwell, Andrew
• Assistant Examiner(s): Mehta, Jyoti
• Application Number:
  US13/464,647
• Publication Number:
  US 20130298127A1
• Time in Patent Office: 1,222 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/3838 Dependency mechanisms, e.g. register scoreboarding
• CPC Class Codes: G06F 9/3842 Speculative instruction execution
• CPC Class Codes: G06F 9/3844 using dynamic branch prediction, e.g. using branch history tables

Abstract

Methods and apparatuses for managing load-store dependencies in an out-of-order processor. A load store dependency predictor may include a table for storing entries for load-store pairs that have been found to be dependent and execute out of order. Each entry in the table includes a counter to indicate a strength of the dependency prediction. If the counter is above a threshold, a dependency is enforced for the load-store pair. If the counter is below the threshold, the dependency is not enforced for the load-store pair. When a store is dispatched, the table is searched, and any matching entries in the table are armed. If a load is dispatched, matches on an armed entry, and the counter is above the threshold, then the load will wait to issue until the corresponding store issues.

Claims

1. A processor comprising:

a reorder buffer;

one or more reservation stations;

a load-store dependency predictor coupled to the one or more reservation stations, the load-store dependency predictor comprising;

a table with entries, wherein each entry comprises;

a load identifier, a store identifier, a reorder buffer entry number, a strength of prediction indicator, and an armed bit used to indicate that a store operation having an identifier matching a store identifier of the respective entry has been dispatched;

and

circuitry configured to;

set an armed bit for an entry in the table, responsive to detecting dispatch of a store operation having an identifier that matches a store identifier stored in that entry of the table;

in response to detecting that a given load operation has an identifier that matches a load identifier of a given entry that has an armed bit that is set;

predict the given load operation is dependent on a given store operation having an identifier that matches a store identifier of the given entry;

increment a strength of prediction indicator of the given entry responsive to determining data for the given load operation is retrieved from a first location, the first location comprising a store queue; and

decrement the strength of prediction indicator of the given entry responsive to determining the data for the given load operation is retrieved from a second location that is different from the first location, wherein the second location is a cache.

2. The processor as recited in claim 1, wherein the strength of prediction indicator of each entry of the table comprises a strength of prediction counter.

3. The processor as recited in claim 2, wherein the circuitry of the load-store dependency predictor is further configured to:

set the armed bit of the given entry, responsive to detecting the given store operation has an identifier that matches the store identifier of the given entry and determining a strength of prediction counter of the given entry is above a threshold; and

store a reorder buffer entry number of the given store operation in the given entry.

4. The processor as recited in claim 3, wherein a reservation station of the one or more reservation stations stores the given load operation with an identification of the reorder buffer entry number of the given entry.

5. The processor as recited in claim 4, wherein responsive to issuance of the given store operation:

the reorder buffer number of the given store operation is broadcast;

the broadcast reorder buffer number is detected by the reservation station storing the given load operation; and

the given load operation is permitted to issue responsive to detecting the broadcast reorder buffer number of the given store operation matches the identification of the reorder buffer entry number stored with the given load operation.

6. The processor as recited in claim 2, wherein each entry of the table further comprises an age-out counter that is decremented responsive to expiration of a programmable period of time.

7. The processor as recited in claim 1, wherein responsive to detecting issuance of a given store operation from a reservation station, the circuitry is configured to clear an armed bit in the table that was previously set responsive to dispatch of the given store operation.

8. A method comprising:

maintaining a table with entries, wherein each entry comprises;

a load identifier, a store identifier, a reorder buffer entry number, a strength of prediction indicator and an armed bit used to indicate that a store operation having an identifier matching a store identifier of the respective entry has been dispatched;

setting an armed bit for an entry in the table, responsive to detecting dispatch of a store operation having an identifier that matches a store identifier stored in that entry of the table;

in response to detecting that a given load operation has an identifier that matches a load identifier of a given entry that has an armed bit that is set, predicting the given load operation is dependent on a given store operation having an identifier that matches a store identifier of the given entry;

incrementing a strength of prediction indicator of the given entry responsive to determining data for the given load operation is retrieved from a first location, the first location comprising a store queue; and

decrementing the strength of prediction indicator of the given entry responsive to determining the data for the given load operation is retrieved from a second location that is different from the first location, wherein the second location is a cache.

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

dispatching the given load operation that has a particular identifier;

searching the table for a load identifier that matches the particular identifier; and

responsive to finding a single entry that has a load identifier that matches the particular identifier and an armed bit that is set, establishing a dependency between the given load operation and a store operation corresponding to a reorder buffer entry number of the single entry.

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

storing the given load operation in a reservation station with an identification of the reorder buffer entry number of the single entry;

broadcasting the reorder buffer entry number of the single entry responsive to issuance of the store operation corresponding to the reorder buffer entry number of the single entry; and

permitting the given load operation to issue from the reservation station responsive to detecting the broadcast reorder buffer number entry.

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

dispatching the given load operation that has a particular identifier;

searching the table for a load identifier that matches the particular identifier; and

responsive to finding multiple matching entries, each matching entry having a load identifier that matches the particular identifier and an armed bit that is set, establishing a dependency between the given load operation and multiple store operations.

12. The method as recited in claim 11, further comprising

identifying an oldest store operation in each reservation station of a plurality of reservation stations responsive to establishing the dependency;

and

permitting the given load operation to issue from a reservation station of the plurality of reservation stations responsive to issuance of all identified oldest store operations from respective reservation stations of the plurality of reservation stations.

13. The method as recited in claim 11, further comprising permitting the given load operation to issue from a reservation station responsive to issuance of all store operations older than the given load operation.

14. The method as recited in claim 8, wherein each entry of the table comprises an age-out counter that is decremented responsive to expiration of a programmable period of time.