Register renaming scheme with checkpoint repair in a processing device
View Patent ↗A data processing device maintains register map information that maps accesses to architectural registers, as identified by instructions being executed, to physical registers of the data processing device. In response to determining that an instruction, such as a speculatively-executing conditional branch, indicates a checkpoint, the data processing device stores the register map information for subsequent retrieval depending on the resolution of the instruction. In addition, in response to the checkpoint indication the data processing device generates new register map information such that accesses to the architectural registers are mapped to different physical registers. The data processing device maintains a list, referred to as a free register list, of physical registers available to be mapped to an architectural registers.
1. A processing device comprising:
a plurality of physical registers;
a register map comprising a first map entry that is associated with a first architectural register, the first map entry being adapted to store a first identifier of a first physical register of the plurality of physical registers such that a program instruction that accesses the first architectural register results in an access of the first physical register;
a first free register list comprising a first free register entry adapted to store a second identifier for a second physical register of the plurality of physical registers, wherein the second physical register is not mapped to the first architectural register, and wherein the first free register entry includes a valid entry indicator;
a first checkpoint map comprising a first checkpoint entry that is associated with the first map entry, wherein the first checkpoint entry is adapted to store the first identifier in response to a first program instruction;
a scoreboard comprising a first scoreboard entry that is associated with the first physical register, wherein the first scoreboard entry includes a read counter that indicates a number of outstanding reads to the first physical register, a checkpoint indicator that indicates when the first identifier is stored in the first checkpoint entry, and a free tag indicator to store a location identifier for locating an identifier of a physical register in the first free register list;
checkpoint logic adapted to:
determine that the first program instruction results in a first change in execution path of program instructions within the processing device; and
in response to determining that the first program instruction specifies the first change in execution path, to:
store the first identifier in the first checkpoint entry;
set the checkpoint indicator;
store the first identifier at a first location in the first register list in response to storing the first identifier in the checkpoint map;
clear the valid entry indicator at the first location in response to storing the first identifier in the first free register list;
store a first location identifier associated with the first location in the free tag indicator; and
when the read counter indicates that the number of outstanding reads to the first physical register is equal to zero:
determine if the checkpoint indicator is set;
access the free tag indicator to determine the first location; and
set the valid entry indicator at the first location; and
a renaming logic adapted to:
determine that a second program instruction that specifies a read operation to the first architectural register is programmed to be executed before a third program instruction that specifies a write operation to the first architectural register, and that the second program instruction is pending execution by an out-of-order execution engine of the processing device after the third program instruction is executed by the execution engine; and
in response to determining that the second program instruction will be executed after the third program instruction store the second identifier in the first map entry such that a program instruction that accesses the first architectural register is mapped to the second physical register.
2. The processing device of claim 1 , further comprising:
a second checkpoint map comprising a second checkpoint entry that is associated with the first map entry, wherein the second checkpoint entry stores the first identifier in response to a second program instruction;
wherein the checkpoint logic is further adapted to:
determine that the second program instruction specifies a second change in execution path of instructions within the processing device; and
store the first identifier in the second checkpoint entry in response to determining that a second program instruction specifies the second change in execution path.
3. The processing device of claim 1 , wherein:
the first free register list is a stack, and the second identifier is initially stored on a top of the stack;
the second and third program instructions are programmed to be executed after the first program instruction;
the checkpoint logic is further adapted to:
store the first identifier in the first free register list below a first bottom of stack pointer for the first free register list;
move a bottom-of-first-checkpoint for the first free register list to below the location of the first identifier; and
enter a location identifier for the location of the first identifier in the first free register into the free tag indicator.
4. The processing device of claim 3 , wherein the checkpoint logic is further adapted to:
determine that a plurality of instructions that are associated with the first change in execution path have been executed; and
move the first bottom of stack pointer to below the location of the first identifier in response to determining that the plurality of instructions have been executed.
5. The processing device of claim 1 , further comprising:
a second free register list adapted to store a third identifier for a third physical register of the plurality of physical registers, wherein the third physical register is not mapped to the first architectural register;
wherein the processing device is adapted to process a first thread and a second thread;
the first free register list and the second free register list are stacks; and
the checkpoint logic is further adapted to:
store a fourth identifier associated with the first thread in the first free register list below a first bottom of stack pointer; and
store a fifth identifier associated with the second thread in the second free register list below a second bottom of stack for the second free register list.
6. The processing device of claim 1 , further comprising:
a second architectural register associated with the instruction set architecture;
wherein:
the register map further comprises a second map entry that is associated with the second architectural register, the second map entry being adapted to store a third identifier of a third physical register of the plurality of physical registers such that a program instruction call to the second architectural register is mapped to the third physical register;
the first checkpoint map further comprises a second checkpoint entry that is associated with the second map entry, the second checkpoint entry being adapted to store the third identifier;
the scoreboard further comprises a second scoreboard entry that is associated with the third physical register.
7. A processing device comprising:
a first physical register identified by a first physical register identifier;
a register map including a first register storage location that is associated with a first architectural register, the first register storage location being adapted to store the first physical register identifier such that a program instruction that accesses the first architectural register results in an access of the first physical register;
a first checkpoint map comprising a first checkpoint storage location that is associated with the first register storage location, the first checkpoint storage location being adapted to store the first physical register identifier in response to a first program instruction;
a first free register list including a first free register storage location having a first free register identifier field and a first valid entry field;
a scoreboard including a first scoreboard storage location associated with the first physical register, the first scoreboard storage location having a first read counter field that indicates a number of outstanding reads to the first physical register, a first checkpoint field that indicates when the first physical register identifier is stored in the first checkpoint storage location, and a free tag field that indicates a location in the first free register list; and
checkpoint logic adapted to:
store the first physical register identifier in the first checkpoint storage location in response to determining that the first program instruction specifies a change in an execution path of instructions; and
in response to storing the first physical register identifier in the first free register identifier field:
set the checkpoint field;
store the first physical register identifier in the first free register identifier field;
clear the first valid entry field;
store a first free register storage location indicator associated with the first free register storage location in the free tag field; and
when the first read counter indicates that the number of outstanding reads to the first physical register is equal to zero, to:
determine if the checkpoint field is set;
access the free tag field to determine the first free register storage location indicator; and
set the first valid entry field.
8. The processing device of claim 7 , wherein the checkpoint logic is further adapted to:
increment the first read counter field in response to receiving, by the processing device, a second program instruction, wherein the second program instruction includes a read addressed to the first physical register.
9. The processing device of claim 8 , wherein the checkpoint logic is further adapted to:
decrement the first read counter field in response to executing, by the processing device, the second program instruction.
10. The processing device of claim 7 , wherein the first free register storage location indicator comprises a depth within the first free list that the first physical register identifier is located.
11. A processing device comprising:
a physical register to store information to be accessed by the processing device, wherein the physical register is identified by a physical register identifier;
a scoreboard comprising a scoreboard entry associated with the physical register, the scoreboard entry having a read counter field adapted to store a read count that indicates a number of outstanding read accesses to the physical register, a checkpoint indicator that indicates when the physical register identifier is stored in a checkpoint, and a free tag indicator;
a free register list comprising a free register entry having a free register location field and a valid entry indicator, wherein the free tag indicator stores a location identifier for locating a physical register identifier in the free register list; and
a checkpoint map comprising a checkpoint entry;
checkpoint logic adapted:
to store the physical register identifier in the checkpoint entry in response to determining that an instruction received by the processing device specifies a change in an execution path of instructions; and
in response to storing the physical register identifier in the checkpoint entry:
to set the checkpoint indicator;
to clear the valid entry indicator;
to store the physical register identifier in the free register location field;
to enter a location identifier for the free register entry into the free tag indicator; and
when the read count indicates that the number of outstanding accesses to the physical register is equal to zero:
to determine if the checkpoint indicator is set;
to access the free tag indicator to determine location identifier; and
set the valid entry indicator at the free register entry.