Load-store dependency predictor PC hashing

• US 9,600,289 B2
• Filed: 05/30/2012
• Issued: 03/21/2017
• Est. Priority Date: 05/30/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/483,268
• Publication Number:
  US 20130326198A1
• Time in Patent Office: 1,756 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 12/1018 involving hashing techniques, e.g. inverted page tables
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/3838 Dependency mechanisms, e.g. register scoreboarding

Abstract

Methods and processors for managing load-store dependencies in an out-of-order instruction pipeline. A load store dependency predictor includes 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 hashed values to identify load and store operations. When a load or store operation is detected, the PC and an architectural register number are used to create a hashed value that can be used to uniquely identify the operation. Then, the load store dependency predictor table is searched for any matching entries with the same hashed value.

Claims

1. An apparatus comprising:

a plurality of entries, each of said entries being configured to store an identifier; and

circuitry comprising a first hashing stage and a second hashing stage, wherein the circuitry is configured to;

hash in the first hashing stage a portion of a program counter (PC) value of a given operation with at least a portion of a corresponding architectural register number or a micro-op number to produce an intermediate result, wherein the circuitry is configurable to switch between using the corresponding architectural register number or the micro-op number to produce the intermediate result; and

hash in the second hashing stage at least a portion of the intermediate result with a portion of the PC value of the given operation, the corresponding architectural register number, and the micro-op number to produce a first identifier;

store the first identifier in an entry of the plurality of entries; and

predict a first operation is dependent on a second operation based at least in part on the first operation having a second identifier that matches the first identifier stored in said entry of the plurality of entries.

2. The load-store dependency predictor as recited in claim 1, wherein the given operation is a load operation and the architectural register number is a destination architectural register number of the load operation.

3. The load-store dependency predictor as recited in claim 1, wherein the first operation is a load operation and the second operation is a store operation.

4. The load-store dependency predictor as recited in claim 1, wherein each of said entries is configured to store both a load identifier and a store identifier, wherein the first identifier in said entry is a load identifier and an identifier of the second operation is stored in said entry as a store identifier.

5. The load-store dependency predictor as recited in claim 1, wherein each of said entries is configured to store a valid indicator that indicates whether a corresponding entry is valid.

6. A processor comprising:

circuitry comprising a first hashing stage and a second hashing stage, wherein the circuitry is configured to;

hash in the first hashing stage a portion of a program counter (PC) value of a given operation with at least a portion of a corresponding architectural register number or a micro-op number to produce an intermediate result, wherein the circuitry is configurable to switch between using the corresponding architectural register number or the micro-op number to produce the intermediate result; and

hash in the second hashing stage at least a portion of the intermediate result with a portion of the PC value of the given operation, the corresponding architectural register number, and the micro-op number to produce a first identifier; and

store the first identifier in an entry of a plurality of entries;

a load-store dependency predictor comprising said plurality of entries, each of said entries being configured to store an identifier generated by the circuitry; and

circuitry configured to;

predict a first operation is dependent on a second operation based at least in part on the first operation having a second identifier that matches the first identifier stored in said entry of the plurality of entries.

7. The processor as recited in claim 6, wherein the given operation is a load operation and the architectural register number is a destination architectural register number of the load operation.

8. The processor as recited in claim 6, wherein the first operation is a load operation and the second operation is a store operation.

9. The processor as recited in claim 6, wherein each of said entries is configured to store both a load identifier and a store identifier, wherein the first identifier in said entry is a load identifier and an identifier of the second operation is stored in said entry as a store identifier.

10. The processor as recited in claim 6, wherein each of said entries is configured to store a valid indicator that indicates whether a corresponding entry is valid.

11. A method comprising:

generating a first identifier, wherein the first identifier is generated by circuitry comprising a plurality of hashing stages, wherein

a first hashing stage of the plurality of hashing stages is configured to hash a first portion of a program counter (PC) value of a given operation with at least a portion of a corresponding architectural register number or a micro-op number to produce an intermediate result, wherein the first hashing stage is configurable to switch between using the corresponding architectural register number or the micro-op number to produce the intermediate result, and wherein

a second hashing stage of the plurality of hashing stages is configured to hash at least a portion of the intermediate result with a portion of the PC value of the given operation, the corresponding architectural register number, and the micro-op number to produce the first identifier;

storing the first identifier by the circuitry in an entry of a plurality of entries of a load-store dependency predictor; and

predicting by circuitry a first operation is dependent on a second operation based at least in part on the first operation having a second identifier that matches the first identifier stored in said entry of the plurality of entries.

12. The method as recited in claim 11, wherein the given operation is a load operation and the architectural register number is a destination architectural register number of the load operation.

13. The method as recited in claim 11, wherein the first operation is a load operation and the second operation is a store operation.

14. The method as recited in claim 11, wherein each of said entries is configured to store both a load identifier and a store identifier, wherein the first identifier in said entry is a load identifier and an identifier of the second operation is stored in said entry as a store identifier.

15. The method as recited in claim 11, wherein each of said entries is configured to store a valid indicator that indicates whether a corresponding entry is valid.