In computer architecture, register renaming is a technique that abstracts logical registers from physical registers. Every logical register has a set of physical registers associated with it. When a machine language instruction refers to a particular logical register, the processor transposes this name to one specific physical register on the fly. The physical registers are opaque and cannot be referenced directly but only via the canonical names.
This technique is used to eliminate false data dependencies arising from the reuse of registers by successive instructions that do not have any real data dependencies between them. The elimination of these false data dependencies reveals more instruction-level parallelism in an instruction stream, which can be exploited by various and complementary techniques such as superscalar and out-of-order execution for better performance.
Problem approach Programs are composed of instructions which operate on values. The instructions must name these values in order to distinguish them from one another. A typical instruction might say: add and and put the result in . In this instruction, , and are the names of storage locations.
It is common for the values being manipulated to be used several times in succession. Register machines take advantage of this by introducing a number of processor registers, which are high-speed memory locations that hold these values. Since register access is typically much faster than accessing memory, high-performance code and processors try to operate on registers when possible. The collection of registers in a particular design is known as its register file.
Individual registers in the file are referred to by number in the machine code. Encoding a number in the machine code requires several bits. For instance, in the Zilog Z80 there were eight general-purpose registers in the file. To select one of eight values requires three bits, as 23 = 8. More architectural (logical) registers of the same width and type can result in better performance, as more temporary values can be held in registers and thus avoid the expensive operations of saving or loading from memory. Similarly, wider registers that can hold more data can also improve performance, if the workload can make use of that. Generally, more modern processors and those with larger instruction words will use more registers when possible. For example, the IA-32 instruction set architecture has 8 general purpose registers, x86-64 has 16, many RISCs have 32, and IA-64 has 128.
The advantages of a larger register file are offset by the need to use more bits to encode the register number. For instance, in a system using 32-bit instructions, you might wish to have three registers, such that you can perform operations of the type = . If the register file contains 32 entries, each one of the references will require 5 bits, and the set of three registers thus takes up 15 bits, leaving 17 to encode the operation and other information. Expanding the register file to 64 entries would require 6 bits, a total of 18 bits. While this may result in faster performance, it also means there are fewer bits left over for encoding the instruction. This leads to an effort to balance the size of the file with the number of possible instructions.
Out-of-order Processors in early computers often worked lock-step with their main memory, which reduced the advantages of large register files. A common design note from the minicomputer market of the 1960s was to have the registers be physically implemented in main memory, in which case the performance advantage was simply that the instruction could directly refer to the location rather than having to use a second byte or two to specify a complete memory address. This made the instructions smaller, and thus faster to read. This sort of design, which maximized performance by carefully tuning the instruction set for minimal size, was common until the 1980s. An example of this approach is the MOS 6502, which had only a single register, in which case it is referred to as the accumulator, and a special "zero page" addressing mode for the first 256 bytes of memory. Placing code and data in the zero page meant the instruction was only two bytes long instead of three, greatly improving performance through avoided reads, providing similar benefits to having more registers.
The widespread introduction of dynamic RAM in the 1970s changed this approach. Over time, the performance of the central processing units (CPUs) increased relative to the memory they were attached to, it was no longer reasonable to use main memory as registers. This led to increasingly large register files, internal to the CPU, to avoid referring to memory wherever possible. However, it is not possible to avoid accessing memory entirely in practice, and as the speed difference grew, every such access became more and more expensive in terms of the number of instructions that might be performed had the value been in a register.
Different instructions may take different amounts of time; for example, a processor may be able to execute hundreds of register-to-register instructions while a single load from the main memory is in progress. A key advance in improving performance is to allow those fast instructions to be performed while the others are waiting for data. This means the instructions are no longer completed in the order they are specified in the machine code, they are instead performed out-of-order.
Consider this piece of code running on an out-of-order CPU: r1 ≔ m ;read the value in memory location 1024 r1 ≔ r1 + 2 ;add two to the value m ≔ r1 ;save the result to location 1032 r1 ≔ m ;read value in 2048 r1 ≔ r1 + 4 ;add 4 m ≔ r1 ;save it to 2056 The instructions in the final three lines are independent of the first three instructions, but the processor cannot finish r1 ≔ m until the preceding m ≔ r1 is complete, as doing so would add four to the value of 1024, not 2048.
If another register is available, this restriction can be eliminated by choosing different registers for the first three and the second three instructions: r1 ≔ m r1 ≔ r1 + 2 m ≔ r1 r2 ≔ m r2 ≔ r2 + 4 m ≔ r2
Now the last three instructions can be executed in parallel with the first three. The program will run faster than before by eliminating the data dependency caused by unnecessarily using the same register in both sequences. A compiler can detect independent instruction sequences and, if there are registers that are available for use, choose different registers during register allocation in the code generation process.
However, to speed up code generated by compilers that do not perform that optimization, or code for which there were not sufficient registers to perform that optimization, many high-performance CPUs provide a register file with more registers than are specified in the instruction set, and, in hardware, rename references in instruction-set-defined registers to refer to registers in the register file, so that the original instruction sequence, using only r1, behaves as if it were:
rA ≔ m rA ≔ rA + 2 m ≔ rA rB ≔ m rB ≔ rB + 4 m ≔ rB
with register r1 "renamed" to the internal register rA for the first three instructions and to the internal register rB for the second three instructions. This removes the false data dependency, allowing the first three instructions to be executed in parallel with the second three instructions.
Data hazards
When more than one instruction references a particular location as an operand, either by reading it (as an input) or by writing to it (as an output), executing those instructions in an order different from the original program order can lead to three kinds of data hazards: Read-after-write (RAW) a read from a register or memory location must return the value placed there by the last write in program order, not some other write. This is referred to as a true dependency or flow dependency, and requires the instructions to execute in program order. Write-after-write (WAW) successive writes to a particular register or memory location must leave that location containing the result of the second write. This can be resolved by squashing (also known as cancelling, annulling, or mooting) the first write if necessary. WAW dependencies are also known as output dependencies. Write-after-read (WAR) a read from a register or memory location must return the last prior value written to that location, and not one written programmatically after the read. This is a sort of false dependency that can be resolved by renaming. WAR dependencies are also known as anti-dependencies.
Instead of delaying the write until all reads are completed, two copies of the location can be maintained, the old value and the new value. Reads that precede, in program order, the write of the new value can be provided with the old value, even while other reads that follow the write are provided with the new value. The false dependency is broken and additional opportunities for out-of-order execution are created. When all reads that need the old value have been satisfied, it can be discarded. This is the essential concept behind register renaming.
Anything that is read and written can be renamed. While the general-purpose and floating-point registers are discussed the most, flag and status registers or even individual status bits are commonly renamed as well.
Memory locations can also be renamed, although it is not commonly done to the extent practiced in register renaming. The Transmeta Crusoe processor's gated store buffer is a form of memory renaming.
If programs refrained from reusing registers immediately, there would be no need for register renaming. Some instruction sets (e.g., IA-64) specify very large numbers of registers for specifically this reason. However, there are limitations to this approach: It is very difficult for the compiler to avoid reusing registers without large code size increases. In loops, for instance, successive iterations would have to use different registers, which requires replicating the code in a process called loop unrolling, or utilising self-modifying code to change the operand targets in each iteration. Large numbers of registers require more bits for specifying a register as an operand in an instruction, resulting in increased code size. Many instruction sets historically specified smaller numbers of registers and cannot be changed while still retaining backwards compatibility.
Code size increases are important because when the program code is larger, the instruction cache misses more often and the processor stalls waiting for new instructions.
Architectural versus physical registers Machine language programs specify reads and writes to a limited set of registers specified by the instruction set architecture (ISA). For instance, the Alpha ISA specifies 32 integer registers, each 64 bits wide, and 32 floating-point registers, each 64 bits wide. These are the architectural registers. Programs written for processors running the Alpha instruction set will specify operations reading and writing those 64 registers. If a programmer stops the program in a debugger, they can observe the contents of these 64 registers (and a few status registers) to determine the progress of the machine.
One particular processor which implements this ISA, the Alpha 21264, has 80 integer and 72 floating-point physical registers. There are, on an Alpha 21264 chip, 80 physically separate locations which can store the results of integer operations, and 72 locations which can store the results of floating point operations (In fact, there are even more locations than that, but those extra locations are not germane to the register renaming operation.)
The following text describes two styles of register renaming, which are distinguished by the circuit which holds the data ready for an execution unit.