MULTI-STAGE REGISTER RENAMING USING DEPENDENCY REMOVAL
Multi-stage register renaming using dependency removal is described. In an embodiment, the registers are renamed in two stages. The first stage involves removing all the dependencies within a set of instructions which are being renamed together. The final stage then renames all registers in parallel using a renaming map. In various embodiments, the dependencies are removed in the first stage using a fixed mapping to rename destination registers in each instruction and in some embodiments the fixed mapping is based on the position of a destination register within the set of instructions. Dependent registers, which are those registers which are read in an instruction but have been written in a previous instruction in the set, are also renamed in the first stage. In addition to performing the renaming in the final stage, the renaming map is updated.
1 . A method of register renaming in an out-of-order processor, comprising:
in a first stage, removing dependencies within a set of instructions using a fixed mapping defined in hardware logic; and
in a final stage, renaming all registers in the set of instructions in parallel using a renaming map.
2 . A method according to claim 1 , wherein removing dependencies within a set of instructions using a fixed mapping defined in hardware logic comprises:
renaming all destination registers and any dependent registers within the set of instructions with one of a set of additional registers using the fixed mapping; and
passing details of which additional register was used to rename each destination register to the final stage.
3 . A method according to claim 2 , wherein the fixed mapping between destination registers and additional registers is based on a physical position of each destination register in the set of instructions.
4 . A method according to claim 1 , wherein the final stage further comprises:
updating the renaming map.
5 . A method according to claim 4 , wherein the renaming map comprises entries associated with each additional register.
6 . A method according to claim 5 , wherein updating the renaming map comprises:
updating entries in the renaming map associated with each destination register based on details passed from the first stage; and
updating entries in the renaming map associated with each additional register to map each additional register to an unassigned physical register.
7 . A method according to claim 6 , further comprising:
accessing a list of unassigned physical registers.
8 . A method according to claim 1 , wherein the fixed mapping is independent of any previous state.
9 . A method according to claim 1 , further comprising:
performing an optimization operation between the first stage and the final stage.
10 . A method according to claim 2 , wherein the set of instructions comprises N instructions and the set of additional registers comprises N additional registers, where N is an integer.
11 . A method according to claim 1 , wherein each instruction within the set of instructions comprises no more than Y destination registers and wherein each instruction has a set of Y associated valid bits, each valid bit indicating whether one of the Y destination registers is used in the instruction.
12 . A method according to claim 11 , wherein the set of instructions comprises N instructions and the set of additional registers comprises N×Y additional registers, where N and Y are integers.
13 . A method according to claim 1 , wherein each instruction within the set of instructions comprises no more than X source registers and wherein each instruction has a set of X associated valid bits, each valid bit indicating whether one of the X source registers is used in the instruction.
14 . An out-of-order processor comprising:
a renaming map;
hardware logic defining a fixed mapping between registers;
dependency removal logic arranged to remove dependencies within a set of instructions using the fixed mapping;
rename logic arranged to rename all registers in the set of instructions in parallel using the renaming map; and
a plurality of physical registers.
15 . An out-of-order processor according to claim 14 , wherein the dependency removal logic comprises a plurality of dependency removal logic instances, and wherein each dependency removal logic instance is arranged to remove dependencies within a separate, non-overlapping subset of the set of instructions.
16 . An out-of-order processor according to claim 14 , wherein the dependency removal logic is arranged to remove dependencies within a set of instructions by renaming all destination registers and any dependent registers within the set of instructions with one of a set of additional registers using the fixed mapping; and passing details of which additional register was used to rename each destination register to the rename logic.
17 . An out-of-order processor according to claim 14 , wherein the renaming map comprises entries associated with each additional register.
18 . An out-of-order processor according to claim 14 , wherein the plurality of physical registers comprises a plurality of unassigned physical registers.
19 . An out-of-order processor according to claim 14 , wherein the rename logic is further arranged to update the renaming map.
20 . An out-of-order processor according to claim 14 , further comprising a loop buffer between the dependency removal logic and the rename logic, wherein the loop buffer is arranged to store instructions located within a loop after dependency removal by the dependency removal logic; and once all instructions in the loop are stored, to release the instructions to the rename logic.