Register Renaming and the Elimination of False Dependencies

Two instructions are dependent if one needs a value the other produces. Instruction sets give programmers a small register namespace, and compilers reuse that namespace aggressively: a value is written to %eax, consumed, and then %eax is overwritten by the next statement. The reuse is invisible to the programmer — nobody observes the old %eax afterwards — but the hardware sees two instructions writing the same register name and, naively, must order them.

Three kinds of dependency, one of which is fake

Take this sequence:

mul   %r1, %r2, %r3      # r3 = r1 * r2
add   %r4, %r5, %r3      # r3 = r4 + r5
sub   %r6, %r7, %r3      # r3 = r6 - r7
and   %r8, %r9, %r3      # r3 = r8 & r9

The first two instructions have a true data dependency: the add reads r3 as the multiply writes it. This is a read-after-write (RAW) hazard and is a real property of the program — no reordering can remove it, because the value must be produced before it is consumed.

The add and the sub have a different relationship. The add produces a value in r3; the sub overwrites r3. The sub’s output has nothing to do with the add’s output. Yet the sub must still be ordered after the add, or the add’s result would be lost before anyone read it. This is a write-after-write (WAW) hazard. Similarly, if some later instruction read r3 before the add wrote it, that would be a write-after-read (WAR) hazard — an anti-dependency.

WAW and WAR hazards are name dependencies. They exist because the assembler ran out of registers. Given an infinite namespace, the same computation would be written with distinct names:

mul   %t0, %r1, %r2
add   %t1, %r4, %r5
sub   %t2, %r6, %r7
and   %t3, %r8, %r9

Now all four are independent and can execute in any order, in parallel, or all at once. The computation is identical; only the naming changed. That observation is the entire basis of register renaming: mimic the infinite-register machine using a larger finite set of physical registers and a mapping table.

The distinction matters because name dependencies are an artifact of the encoding. They consume window space and issue slots without carrying any information. In scalar code with short-lived temporaries the ratio of name dependencies to true dependencies can be high — a compiler that reuses one scratch register for every intermediate creates a serial chain out of independent arithmetic.

How the mapping table works

Renaming replaces each architectural register with a physical register number for the duration of a value’s life. The structure that holds the current mapping is called a rename table, a register alias table, or a mapper: a small array indexed by architectural register number whose entries are physical register numbers.

The rename stage of the pipeline processes instructions in program order, one to several per cycle, and for each instruction:

Read the rename table for each source operand. If the source is architectural register r, the operand is now tagged with physical register T[r].
Allocate a free physical register p for the destination.
Write T[r_dest] = p. The instruction is tagged with p as its destination.
Emit the renamed instruction into the issue structures.

Because step 3 happens in program order, a later instruction reading the same architectural register sees the newer p, and a consumer of the overwritten value keeps the older physical register. WAW is resolved by the last writer claiming the name; WAR is resolved because readers already hold physical identifiers. Neither hazard survives renaming, and neither requires a pipeline interlock.

There is a subtlety in the ordering within a single cycle. If two instructions in the same rename group both write r3, the second must allocate a different physical register and the first must be able to read the register file entry the second overwrites, all in the same cycle. Implementations handle this with a small bypass network inside the rename stage: source lookups compare against the destinations of earlier instructions in the same group and take the newer physical number.

Physical register allocation and freeing

The mapping is only half the mechanism. The other half is knowing when a physical register may be reused.

A physical register holding an architectural value is live as long as it is either mapped in the rename table (it is the current value of some architectural register) or still needed by an instruction that has been renamed but not yet read its operand. Freeing it early corrupts a reader; freeing it never exhausts the pool.

The standard approach is to keep a free list of physical registers and an explicit record of when a register becomes dead. Consider T[r3] moving from physical register p18 to p41 when a new instruction writes r3. Register p18 is no longer the architectural value of anything, so the only remaining user is whichever already-renamed instruction still has p18 as a source. When the last such reader has read its operand — at issue, in a typical design — p18 returns to the free list. The bookkeeping is often a counter per physical register, or a bit vector in a “free at completion of instruction X” scheme, or an allocation discipline where the physical register file is a circular buffer and registers are reclaimed at retirement.

The circular-buffer variant deserves mention because it is the design used in several well-known processors and it changes the failure mode. Physical registers are allocated in program order from a monotonic pointer, and the register freed by retiring instruction i is the one whose only remaining role was as the old value of its destination. Retirement, not issue, moves the free pointer. The consequence is a hard coupling between window size and register file size: with a reorder buffer of W entries and four destination registers per instruction, the register file must have enough spare physical registers to cover W in-flight destinations plus the architectural set. Growing one without the other changes nothing.

The separate free-list design decouples the two, at the cost of an allocator with arbitration and a free list that must never empty. Either way, “out of physical registers” is a real stall condition: rename stops, decode backs up, and fetch follows.

How big is the namespace

Typical instruction sets define 16 or 32 general-purpose registers, plus a similar count of vector registers. Physical register files in out-of-order cores are considerably larger — the exact numbers differ per implementation and per generation, but the integer file typically holds several times the architectural count, and the vector file is usually wider per entry rather than larger in count.

The register file is not only a count but a port problem. Each issue port needs read ports, and each result bus needs a write port. Multiporting a large register array is expensive in both area and access latency, which is why register files are partitioned by execution cluster in wide designs and why reading operands at issue rather than collecting them at dispatch is the common choice: an instruction holds physical register numbers, not values, in the scheduler.

That choice has a consequence that connects to Issue Queue Wakeup and Select: because values are read at issue time, an instruction whose producer has completed but which has not yet been selected still needs the register file read port when it is selected. Scheduling distance from the producer does not remove the read.

Renaming beyond registers

The same name-versus-value distinction appears in three other places, and the same trick applies.

Flags. Architectures with a condition-code register have an implicit name dependency on nearly every arithmetic instruction, because every arithmetic instruction overwrites the flags. Renaming the flags register, or tracking the specific flag bits each instruction produces and consumes, is necessary before flag-setting can be scheduled freely.

Memory locations. Two stores to the same address are a WAW in memory; a load followed by a store to the same address is a WAR. The hardware cannot allocate a new physical location per store — the memory is a single namespace — so stores are kept in program order in a store buffer and loads are checked against pending stores. This is an approximation of renaming and fails when addresses are unknown, which is the subject of Load-Store Ordering and Memory Disambiguation.

Return addresses and stack pointers. A call pushes a return address; renaming the stack pointer is possible in principle but requires the depth to be statically predictable, so most designs maintain a return-address stack as a predictor rather than a renamed register.

What renaming does not fix

Renaming removes name dependencies only. It does not reduce the latency of a true dependency chain, it does not enlarge the reorder buffer, and it does not help when the program’s parallelism is genuinely absent. A loop that accumulates into one variable with a two-cycle-latency add remains a chain of adds no matter how many physical registers exist; the only fix there is transformation at a higher level, such as unrolling with multiple partial accumulators.

Renaming also imposes its own ordering requirement: the rename stage is in program order and is therefore a serialization point for the whole group of instructions per cycle. It needs to handle partial groups — if only three of four renamed instructions can find physical registers, the fourth must not consume a mapping, and the pipeline must be able to advance by three. Getting that right, along with precise state recovery on misprediction (the subject of Checkpointing and Recovery from Misprediction), is where much of the complexity of the front end lives.