Load speculation recovery

• US 10,514,925 B1
• Filed: 01/28/2016
• Issued: 12/24/2019
• Est. Priority Date: 01/28/2016
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Reynolds, Sean M.
• Primary Examiner(s): Li, Aimee
• Assistant Examiner(s): Cromer, Andrew J
• Application Number:
  US15/009,614
• Time in Patent Office: 1,426 Days
• 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/38585 with result invalidation, e.g. nullification
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system

Abstract

Systems, apparatuses, and methods for managing dependencies between instruction operations when speculatively issuing load instruction operations. A processor may maintain dependency vectors for sources of instruction operations dispatched to the scheduler. The dependency vector may include a column for each cycle of the load recovery window and a row for each load execution pipeline. When a load speculatively issues, any instruction operation which is dependent on the load may have a bit set in the earliest bit position of its dependency vector to indicate the dependency. The bit may shift in the dependency vector toward the cancel bit position during each clock cycle as the load executes. If the load does not produce its data at the expected latency, an instruction operation may be canceled if there is a bit in the cancel bit position of the dependency vector row corresponding to the execution pipeline of the load.

Claims

1. A processor comprising:

one or more execution units; and

a scheduler configured to schedule instruction operations for execution on the one or more execution units;

wherein the processor is configured to;

maintain a first dependency vector for a first instruction operation, wherein the first dependency vector comprises one or more bits stored in one or more propagate bit positions and one or more cancel bit positions;

mark an earliest bit of the first dependency vector to indicate a dependency of the first instruction operation on a second instruction operation; and

for each clock cycle the second instruction operation executes, shift bits of the first dependency vector from the one or more propagate bit positions toward the one or more cancel bit positions; and

cancel the first instruction operation responsive to receiving a cancel signal and determining a bit of the dependency vector has been shifted into a cancel bit position of the one or more cancel bit positions.

2. The processor as recited in claim 1, wherein the second instruction operation is a load instruction operation.

3. The processor as recited in claim 2, wherein the processor is configured to maintain a plurality of dependency vectors for the first instruction, wherein each of the plurality of dependency vectors corresponds to a different load execution pipeline of the processor.

4. The processor as recited in claim 3, wherein the processor is further configured to update a source dependency vector of a source of a third instruction operation with a disjunction of the instruction dependency vector and an existing source dependency vector of the third instruction operation responsive to determining the third instruction operation is dependent on the second instruction operation.

5. The processor as recited in claim 1, wherein the processor is further configured to create an instruction dependency vector for the second instruction operation from a disjunction of a plurality of source dependency vectors corresponding to sources of the second instruction operations responsive to issuing the second instruction operation to an execution unit.

6. The processor as recited in claim 1, wherein the first dependency vector comprises a row for each load execution unit of the one or more execution units, and wherein the processor is further configured to cancel the first instruction operation responsive to receiving a cancel signal associated with a first load execution unit and responsive to determining that there is a dependency indicator in the cancel bit position of a first row of the first dependency vector, wherein the first row corresponds to the first load execution unit.

7. The processor as recited in claim 1, wherein each of the one or more cancel bit positions of the dependency vector corresponds to a single stage of an execution pipeline.

8. The processor as recited in claim 1, wherein a position of a given bit of the dependency vector in a propagate bit position indicates a number of cycles until the given bit becomes a kill bit.

9. A method comprising:

maintaining a first dependency vector for a first instruction operation, wherein the first dependency vector comprises one or more bits stored in one or more propagate bit positions and one or more cancel bit positions;

marking an earliest bit of the first dependency vector to indicate a dependency of the first instruction operation on a second instruction operation; and

for each clock cycle the second instruction operation executes, shifting bits of the first dependency vector from the one or more propagate bit positions toward the one or more cancel bit position;

cancelling the first instruction operation responsive to receiving a cancel signal and determining a bit of the dependency vector has been shifted into a cancel bit position of the one or more cancel bit positions.

10. The method as recited in claim 9, wherein the second instruction operation is a load instruction operation.

11. The method as recited in claim 10, further comprising maintaining a plurality of dependency vectors for the first instruction, wherein each of the plurality of dependency vectors corresponds to a different load execution pipeline of the processor.

12. The method as recited in claim 11, further comprising updating a source dependency vector of a source of a third instruction operation with a disjunction of the instruction dependency vector and an existing source dependency vector of the third instruction operation responsive to determining the third instruction operation is dependent on the second instruction operation.

13. The method as recited in claim 9, further comprising creating an instruction dependency vector for the second instruction operation from a disjunction of a plurality of source dependency vectors corresponding to sources of the second instruction operations responsive to issuing the second instruction operation to an execution unit.

14. The method as recited in claim 9, further comprising canceling the first instruction operation responsive to receiving a cancel signal and determining that there is a dependency indicator in the cancel bit position of the first dependency vector.

15. The method as recited in claim 9, wherein the first dependency vector comprises a row for each load execution unit of the one or more execution units, wherein the method further comprising canceling the first instruction operation responsive to receiving a cancel signal associated with a first load execution unit and responsive to determining that there is a dependency indicator in the cancel bit position of a first row of the first dependency vector, wherein the first row corresponds to the first load execution unit.

16. A computing system comprising:

a memory; and

a processor comprising;

one or more execution units; and

a scheduler configured to schedule instruction operations for execution on the one or more execution units;

wherein the processor is configured to;

maintain a first dependency vector for a first instruction operation, wherein the first dependency vector comprises one or more bits stored in one or more propagate bit positions and one or more cancel bit positions;

mark an earliest bit of the first dependency vector to indicate a dependency of the first instruction operation on a second instruction operation; and

for each clock cycle the second instruction operation executes, shift bits of the first dependency vector from the one or more propagate bit positions toward the one or more cancel bit position;

cancel the first instruction operation responsive to receiving a cancel signal and determining a bit of the dependency vector has been shifted into a cancel bit position of the one or more cancel bit positions.

17. The computing system as recited in claim 16, wherein the processor is further configured to create an instruction dependency vector for the second instruction operation from a disjunction of a plurality of source dependency vectors corresponding to sources of the second instruction operations responsive to issuing the second instruction operation to an execution unit.

18. The computing system as recited in claim 16, wherein the second instruction operation is a load instruction operation.

19. The computing system as recited in claim 18, wherein the processor is further configured to maintain a plurality of dependency vectors for the first instruction, wherein each of the plurality of dependency vectors corresponds to a different load execution pipeline of the processor.

20. The computing system as recited in claim 19, wherein the processor is further configured to update a source dependency vector of a source of a third instruction operation with a disjunction of the instruction dependency vector and an existing source dependency vector of the third instruction operation responsive to determining the third instruction operation is dependent on the second instruction operation.

21. The computing system as recited in claim 20, wherein the processor is further configured to cancel the first instruction operation responsive to receiving a cancel signal and determining that there is a dependency indicator in the cancel bit position of the first dependency vector.