Replacement scheme for map checkpoints
Techniques are disclosed pertaining to a replacement scheme for map checkpoints. A processor of a computer system receives an instruction to be executed. The processor updates the state of a map structure to map a set of logical registers specified by the instruction to a set of physical registers. The processor then stores a first map checkpoint that corresponds to the updated state of the map structure and is usable by the processor to restore the map structure to the updated state. The storing of the first map checkpoint can include the processor selecting a second map checkpoint from a set of stored map checkpoints based on a non-first in, first out replacement scheme. The second map checkpoint may thus be selected out of order relative to an order in which the set of stored map checkpoints were stored. The second map checkpoint is overridden with the first map checkpoint.
1 . An apparatus, comprising:
a computer processor that includes:
a plurality of physical registers, a given one of which is configured to store a value;
fetch circuitry configured to fetch instructions; and
map circuitry coupled to the fetch circuitry and configured to:
maintain a map structure that maps a set of logical registers specified by an instruction to a set of the plurality of physical registers of the computer processor;
store a set of map checkpoints, wherein a given one of the set of map checkpoints corresponds to a state of the map structure at a particular point in a dynamically changing out-of-order execution window and is usable by the computer processor to roll back the map structure to the state at the particular point;
assign a tier value to a given map checkpoint of the set of map checkpoints based on a sequence of a repeating series of tier values; and
based at least in part on a detection that the set of map checkpoints includes a threshold number of map checkpoints, select and replace a first one of the set of map checkpoints with a second map checkpoint in accordance with a non-first in, first out (non-FIFO) replacement scheme that alters relative spacing of the set of map checkpoints within the dynamically changing out-of-order execution window, wherein the first map checkpoint is selected based on a tier value assigned to the first map checkpoint.
2 . The apparatus of claim 1 , wherein the map circuitry is further configured to:
select the first map checkpoint over a third one of the set of map checkpoints based on the first map checkpoint being assigned a lower prioritized tier value than the third map checkpoint.
3 . The apparatus of claim 2 , wherein the map circuitry is further configured to:
select the first map checkpoint over a fourth map checkpoint that is assigned a same tier value as the first map checkpoint based on the first map checkpoint being stored more recently than the fourth map checkpoint.
4 . The apparatus of claim 2 , wherein the map circuitry is further configured to:
select the first map checkpoint over a fourth map checkpoint that is assigned a lower prioritized tier value based on the first map checkpoint having been invalidated.
5 . The apparatus of claim 2 , wherein the map circuitry is further configured to:
select the first map checkpoint over a fourth map checkpoint that is assigned a same tier value as the first map checkpoint based on the first map checkpoint being stored less recently than the fourth map checkpoint.
6 . The apparatus of claim 1 , wherein the map circuitry is configured to:
receive an indication of a branch misprediction;
based on the branch misprediction, select one of the set of map checkpoints to which to roll back the state of the map structure; and
invalidate any one of the set of map checkpoints that was stored more recently than the selected map checkpoint.
7 . The apparatus of claim 6 , wherein the map circuitry is configured to:
store a history of changes made to the map structure; and
determine to roll back the state of the map structure to a prior state based on the branch misprediction; and
based on a detection that the prior state is different than a state identified by the selected map checkpoint, perform a roll back operation to roll back the state of the map structure to the prior state, wherein the roll back operation includes:
restoring the state of the map structure to the state identified by the selected map checkpoint; and
rolling back, based on the history of changes, the state of the map structure to the prior state from the state identified by the selected map checkpoint.
8 . The apparatus of claim 1 , wherein the map circuitry is configured to:
detect that a threshold number of map operations have been executed and a threshold number of conditional branch instructions have been issued in the computer processor since a last map checkpoint was generated; and
generate the second map checkpoint in response to the detect.
9 . The apparatus of claim 1 , wherein the map circuitry is configured to:
obtain an indication that a retire pointer has advanced past the particular point in the dynamically changing out-of-order execution window; and
invalidate the second map checkpoint in response to the indication and a detection that the second map checkpoint is stored in a valid state.
10 . A method, comprising:
receiving, by a processor of a computer system, an instruction to execute;
updating, by the processor, a state of a map structure of the processor to map a set of logical registers specified by the instruction to a set of physical registers of the processor;
storing, by the processor, a first map checkpoint that corresponds to the updated state of the map structure, wherein the first map checkpoint is usable by the processor to restore the map structure to the updated state, and wherein the storing includes:
selecting a second map checkpoint from a set of stored map checkpoints based on a replacement scheme, wherein the second map checkpoint is selected out of order relative to an order in which the set of previously stored map checkpoints were stored; and
replacing the second map checkpoint with the first map checkpoint.
11 . The method of claim 10 , further comprising:
assigning, by the processor and to the first map checkpoint, a first tier value from a tier sequence of a repeating series of tier values, wherein the second map checkpoint is selected based on the second map checkpoint being assigned a second tier value that has a lower priority than tier values assigned to other ones of the set of stored map checkpoints.
12 . The method of claim 11 , wherein at least one other map checkpoint of the set of stored map checkpoints is assigned the second tier value, and wherein the second map checkpoint is selected based on the second map checkpoint being the youngest map checkpoint assigned the second tier value.
13 . The method of claim 11 , wherein the second tier value of the second map checkpoint has a higher priority than the first tier value assigned to the first map checkpoint.
14 . The method of claim 11 , wherein the repeating series of tier values is ordered so that an instruction distance between the set of stored map checkpoints increases over time as a number of instructions within a dynamically changing instruction window increases over that time.
15 . The method of claim 11 , wherein a number of different tier values used in the repeating series of tier values is selected so that the set of stored map checkpoints is uniformly distributed in an instruction window when the instruction window includes a defined maximum number of instructions.
16 . A non-transitory computer readable medium having stored thereon design information that specifies a circuit design in a format recognized by a fabrication system that is configured to use the design information to fabricate a hardware integrated circuit that comprises:
a plurality of physical registers, a given one of which is configured to store a value;
fetch circuitry configured to fetch instructions; and
map circuitry coupled to the fetch circuitry and configured to:
maintain a map structure that maps a set of logical registers specified by an instruction to a set of the plurality of physical registers of the hardware integrated circuit;
generate a first map checkpoint corresponding to a state of the map structure at a particular point in an execution path, wherein the first map checkpoint enables the hardware integrated circuit to roll back the map structure to the state at the particular point; and
replace a previously stored second map checkpoint with the first map checkpoint in accordance with a replacement scheme that replaces map checkpoints at least partially out of order relative to an order in which the map checkpoints are stored.
17 . The non-transitory computer readable medium of claim 16 , wherein the map circuitry is configured to:
assign, to the first map checkpoint, a first tier value from a repeating series of tier values, wherein to implement the replacement scheme, the map circuitry is configured to select a map checkpoint for replacement based on validity state, tier value, and age.
18 . The non-transitory computer readable medium of claim 16 , wherein the map circuitry is configured to:
obtain an indication that a threshold number of map operations have been executed since a last map checkpoint was generated; and
generate the first map checkpoint in response to the indication.
19 . The non-transitory computer readable medium of claim 16 , wherein the map circuitry is configured to:
invalidate a stored map checkpoint in response to receiving an indication that the stored map checkpoint has passed outside of a dynamically changing out-of-order execution window.
20 . The non-transitory computer readable medium of claim 16 , wherein the map circuitry is configured to:
select one of a set of map checkpoints to which to restore the map structure; and
invalidate any one of the set of map checkpoints that was stored more recently than the selected map checkpoint.