Space efficient checkpoint facility and technique for processor with integrally indexed register mapping and free-list arrays
A processor may efficiently implement register renaming and checkpoint repair even in instruction set architectures with large numbers of wide (bit-width) registers by (i) renaming all destination operand register targets, (ii) implementing free list and architectural-to-physical mapping table as a combined array storage with unitary (or common) read, write and checkpoint pointer indexing and (iiii) storing checkpoints as snapshots of the mapping table, rather than of actual register contents. In this way, uniformity (and timing simplicity) of the decode pipeline may be accentuated and architectural-to-physical mappings (or allocable mappings) may be efficiently shuttled between free-list, reorder buffer and mapping table stores in correspondence with instruction dispatch and completion as well as checkpoint creation, retirement and restoration.
1. A processor comprising:
a renaming store coupled to provide instruction dispatch logic with physical register identifiers mapped from architectural register identifiers in correspondence with a current register renaming state;
storage for an array of entries each including a pair of corresponding free-list and register reorder buffer fields, the array storage coupled to the renaming store to, coincident with dispatch of each successive instruction that specifies a destination register, (i) supply a physical register identifier obtained from the free-list field of a next entry at a head-end thereof to the renaming store as a next physical register renaming target for the destination register and (ii) receive from the renaming store and store into the register reorder buffer field of the next entry a current physical register renaming target for the destination register; and
storage for a plurality of checkpoint images of the renaming store each capable of storing for a given checkpoint, both (i) a then current register renaming state and (ii) a corresponding head-end read pointer value for indexing into the array storage at an entry that, at the given checkpoint, was the then next entry at the then head-end of the array.
2. The processor of claim 1 , further comprising:
the instruction dispatch logic, wherein the instruction dispatch logic is configured to dispatch the successive instructions in program order, and
wherein, for an architectural register destination of each of the instructions successively dispatched in program order, the array storage is configured to supply a respective physical register renaming target from the free-list field of the corresponding next entry thereof.
3. The processor of claim 1 , further comprising:
a plurality execution units configured to execute respective ones of the successively dispatched instructions, the execution units coupled to, in correspondence with completion of a particular instruction executed thereby, mark as valid the reorder buffer field of the array storage entry that corresponds thereto.
4. The processor of claim 3 ,
wherein the instruction dispatch logic is configured to dispatch the successive instructions in program order, and
wherein the execution units are configured to complete the dispatched instructions generally out of program order and store results thereof to the corresponding physical register renaming targets.
5. The processor of claim 3 , further comprising:
a register file,
wherein results of the completed instructions are stored in physical registers of the register file generally out of program order and retired to architectural state in correspondence with checkpoint delimited sets of entries of the array storage.
6. The processor of claim 1 ,
wherein the plurality of checkpoint images allow for up to a corresponding plurality of in-flight checkpoints without imaging content of underlying physical registers of the register file.
7. The processor of claim 1 , further comprising:
a data path for saving in a checkpoint image storage, and in correspondence with checkpoint instruction or signal, a checkpoint image of both (i) an architectural-to-physical mapping table and (ii) a corresponding head-end read pointer value for indexing into the array storage at an entry that, at the given checkpoint, is the next entry at the head-end of the array storage.
8. The processor of claim 1 , further comprising:
a data path for restoring, in correspondence with a branch misprediction or exception, a checkpoint image of both (i) an architectural-to-physical mapping table and (ii) a corresponding head-end read pointer value for indexing into the array storage at an entry that, at the given checkpoint, was the then next entry at the then head-end of the array storage.
9. The processor of claim 1 ,
wherein the array storage is implemented as a circular buffer; and
wherein during operation of the processor, for each entry between the head-end and a tail-end of the circular buffer, the register reorder buffer field encodes a register identifier for a physical register renaming target to be restored in an architectural-to-physical mapping table upon retirement of the corresponding, unretired instruction.
10. The processor of claim 9 ,
wherein entries of the circular buffer, including the register reorder buffer fields, are as numerous as physical registers available to the processor as renaming targets.
11. The processor of claim 9 ,
wherein a single head-end read pointer is sufficient to index the free list and register reorder buffer fields in correspondence with dispatch of successive instructions.
12. The processor of claim 9 ,
wherein a single tail-end write pointer is sufficient to index the free list and register reorder buffer fields in correspondence with checkpoint retirements.
13. A method comprising:
decoding a first instruction to determine an architectural register that is a destination of the instruction;
in correspondence with the instruction decoding, indexing into a next entry at a head-end of storage for an array of entries that each include a pair of corresponding free-list and register reorder buffer fields;
based on a current state of an architectural-to-physical register mapping table,
(a) obtaining a first identifier for a first physical register to which the destination has been mapped and storing the obtained first identifier to the reorder buffer field of the indexed-into next entry at the head-end of the array storage;
(b) obtaining from the free-list field of the indexed-into next entry at the head-end of the array storage a second identifier for a second physical register as a next physical register renaming for the destination and storing the obtained second identifier to the architectural-to-physical register mapping table as a next physical register to which the destination is mapped;
dispatching the first instruction for execution with source register targets renamed in accordance with the current state of the architectural-to-physical register mapping table and with the next physical register renaming as destination target thereof;
decoding next successive instructions in program order to determine respective architectural registers that are destinations thereof and performing with respect to the successive instructions, and based on then current states of the architectural-to-physical register mapping table and array storage, the indexing, the (a) obtaining, the (b) obtaining and the dispatching; and
responsive to a checkpoint event, saving a checkpoint image of both (i) a current register renaming state and (ii) a corresponding read pointer value for indexing into the array storage at an entry that, at the checkpoint, is the next entry at the current head-end of the array storage.
14. The method of claim 13 ,
wherein the indexing to corresponding free-list and register reorder buffer fields is performed using a same read pointer; and
wherein further indexing into the array storage in connection with checkpoint creation or retirement operations on corresponding free-list and register reorder buffer fields is likewise performed using a same checkpoint or write pointer.
15. The method of claim 13 ,
wherein the dispatching of the first and successive instructions is in program order, and
wherein, for the architectural register destination of each of the instructions dispatched in program order, the array storage supplies a respective physical register renaming target from the free-list field of a corresponding next entry thereof.
16. The method of claim 13 , further comprising:
executing the dispatched first and successive instructions; and
in correspondence with completion of respective ones of the dispatched first and successive instructions, marking as valid the reorder buffer field of the corresponding array storage entry.
17. A method comprising:
maintaining as an array storage a coordinated free-list and reorder buffer data structure that represents, in the free-list, physical register renaming targets allocable to instruction destinations and, in the reorder buffer, presently allocated physical register renaming targets reclaimable upon retirement of or restoration to a corresponding checkpoint;
responsive to a checkpoint event, saving a checkpoint image of both (i) a current register renaming state of an architectural-to-physical mapping table and (ii) a corresponding read pointer value for indexing into the array storage at an entry that, at the checkpoint, is at a current head-end of the array storage; and
restoring, in correspondence with a branch misprediction or exception, both a checkpoint image of the architectural-to-physical mapping table and a corresponding head-end read pointer value for indexing into the array storage at an entry that, at the given checkpoint, was the then next entry at the then head-end of the array storage.
18. The method of claim 17 , further comprising, in correspondence with dispatch of each successive instruction that specifies a destination register:
retrieving from the architectural-to-physical mapping table a current physical register renaming target for the destination register and storing the retrieved current renaming target into the register reorder buffer at the current head-end thereof;
supplying a physical register identifier obtained from the free-list at the current head-end thereof to the architectural-to-physical mapping table store as a next physical register renaming target for the destination register; and
advancing a read pointer that identifies the current head-end of the coordinated free-list and reorder buffer data structure.