Method and apparatus for performing register file checkpointing to support speculative execution within a processor

1. A method for performing register file checkpointing to support speculative execution within a processor, comprising:

commencing speculative execution of a program from a point of speculation, at which the outcome of a long latency instruction is speculatively predicted;

wherein updating a register with a new value during the speculative execution involves,

checkpointing an old value of the register when the register has not already been checkpointed, wherein checkpointing the old value of the register involves:

determining if the register has already been checkpointed by examining a checkpoint table, wherein the checkpoint table contains an entry for each architectural register, wherein each entry comprises a single bit specifying if the corresponding register has been checkpointed during the speculative execution, and

if the register has not already been checkpointed,

checkpointing the old value for the register, and

updating the checkpoint table to indicate that the register has been checkpointed, and

updating the architectural state of the register with the new value;

whereby only registers that are updated during the speculative execution are checkpointed, instead of checkpointing all of the architectural registers prior to commencing speculative execution.

2. The method of claim 1 , wherein if the speculation turns out to be incorrect, the method further comprises:

using the checkpointed values to restore the architectural state of registers that have been updated during the speculative execution; and

resuming execution of the program from the point of speculation.

3. The method of claim 1 , wherein if the speculation turns out to be correct, the method further comprises:

flushing the checkpointed values; and

continuing execution of the program from the point where the speculative execution left off.

4. The method of claim 1 , wherein checkpointing the old value of the register involves storing the old value in a checkpoint queue, which contains checkpoints for registers that have been updated during the speculative execution.

5. The method of claim 4 ,

wherein the processor supports nested speculative execution; and

wherein the checkpoint table has a separate column associated with each nested level of speculative execution.

6. The method of claim 4 ,

wherein the processor supports nested speculative execution; and

wherein there exists a separate checkpoint queue for each nested level of speculative execution.

7. The method of claim 4 ,

wherein the processor supports nested speculative execution; and

wherein there exists a combined checkpoint queue that contains register checkpoints for all nested levels of speculative execution.

8. The method of claim 4 ,

wherein the processor supports register renaming; and

wherein checkpointing the old value of the register involves storing a physical register number and a corresponding architectural register number for the register in the checkpoint queue.

9. The method of claim 8 , wherein if the speculation turns out to be incorrect, the method further comprises:

using the physical register numbers and the corresponding architectural register numbers from the checkpoint queue to restore a rename map to reflect the architectural state of the processor at the point of speculation; and

resuming execution of the program at the point of speculation.

10. The method of claim 1 , wherein the long latency instruction can include a load instruction that generates a cache miss.

11. An apparatus that performs register file checkpointing to support speculative execution, comprising:

a processor that supports speculative execution of a program from a point of speculation, at which the outcome of a long latency instruction is speculatively predicted;

a register file within the processor;

a register updating mechanism, wherein during speculative execution the register updating mechanism is configured to,

checkpointing an old value of the register when the register has not already been checkpointed, wherein checkpointing the old value of the register involves:

determining if the register has already been checkpointed by examining a checkpoint table, wherein the checkpoint table contains an entry for each architectural register, wherein each entry comprises a single bit specifying if the corresponding register has been checkpointed during the speculative execution, and

if the register has not already been checkpointed,

checkpointing the old value for the register, and

updating the checkpoint table to indicate that the register has been checkpointed, and

updating the architectural state of the register with a new value;

whereby only registers that are updated during the speculative execution are checkpointed, instead of checkpointing all of the architectural registers prior to commencing speculative execution.

12. The apparatus of claim 11 , wherein if the speculation turns out to be incorrect, the processor is configured to:

use the checkpointed values to restore the architectural state of registers that have been updated during the speculative execution; and to

resume execution of the program from the point of speculation.

13. The apparatus of claim 11 , wherein if the speculation turns out to be correct, the processor is configured to:

flush the checkpointed values; and to

continue execution of the program from the point where the speculative execution left off.

14. The apparatus of claim 11 , further comprising:

a checkpoint queue which contains checkpoints for registers that have been updated during the speculative execution;

wherein while checkpointing the old value of the register, the register updating mechanism is configured to store the old value in the checkpoint queue.

15. The apparatus of claim 14 ,

wherein the processor supports nested speculative execution; and

wherein the checkpoint table has a separate column associated with each nested level of speculative execution.

16. The apparatus of claim 14 ,

wherein the processor supports nested speculative execution; and

wherein there exists a separate checkpoint queue for each nested level of speculative execution.

17. The apparatus of claim 14 ,

wherein the processor supports nested speculative execution; and

wherein there exists a combined checkpoint queue that contains register checkpoints for all nested levels of speculative execution.

18. The apparatus of claim 14 ,

wherein the processor supports register renaming; and

wherein the register updating mechanism is configured to store a physical register number and a corresponding architectural register number for the register in the checkpoint queue.

19. The apparatus of claim 18 , wherein if the speculation turns out to be incorrect, the processor is configured to:

use the physical register numbers and the corresponding architectural register numbers from the checkpoint queue to restore a rename map to reflect the architectural state of the processor at the point of speculation; and to

resume execution of the program at the point of speculation.

20. The apparatus of claim 11 , wherein the long latency instruction can include a load instruction that generates a cache miss.

21. An computer system that performs register file checkpointing to support speculative execution, comprising:

a processor that supports speculative execution of a program from a point of speculation, at which the outcome of a long latency instruction is speculatively predicted;

a memory;

a register file within the processor;

a register updating mechanism, wherein during speculative execution the register updating mechanism is configured to,

checkpointing an old value of the register when the register has not already been checkpointed, wherein checkpointing the old value of the register involves:

determining if the register has already been checkpointed by examining a checkpoint table, wherein the checkpoint table contains an entry for each architectural register, wherein each entry comprises a single bit, and

if the register has not already been checkpointed, checkpointing the old value for the register, and

updating the checkpoint table to indicate that the register has been checkpointed, and

updating the architectural state of the register with a new value;

whereby only registers that are updated during the speculative execution are checkpointed, instead of checkpointing all of the architectural registers prior to commencing speculative execution.