Register Renaming: Killing WAR and WAW Hazards with a Rename Map

The problem: false dependencies that aren't really dependencies

Consider three instructions competing over one register name:

i1:  R1 = MEM[x]      ; long-latency load
i2:  R2 = R1 + 5      ; RAW on R1 (real: must wait for i1)
i3:  R1 = R9 * R8     ; WAW on R1 vs i1, WAR on R1 vs i2

Instruction i3 has nothing to do with i1 or i2 — it just happens to reuse the name R1. Yet an in-order machine must keep i3 after i1 (so the final value of R1 is i3's, a WAW hazard) and after i2's read (so i2 sees i1's value, not i3's, a WAR hazard). If the load i1 misses in cache, i3 stalls for hundreds of cycles for no good reason.

These are name dependencies, not data dependencies. The only genuine constraint is the RAW edge i1 to i2, where a real value flows. Register renaming removes the name dependencies by handing i3's write a brand-new register, letting it execute the instant its inputs R9 and R8 are ready.

How it works: the rename map, free list, and a fresh register per write

Renaming happens in the pipeline's rename stage, right after decode, and rests on three structures:

• Rename map (RAT): a table indexed by architectural register number, holding the physical register that currently represents it.
• Free list: a queue of physical registers not currently mapped to any architectural name.
• Physical register file (PRF): the wide pool of actual storage.

For each instruction, per operand:

for each source arch reg s:
    phys_src = RAT[s]              # look up current mapping
for the dest arch reg d:
    p_new = free_list.pop()       # grab a fresh physical reg
    old = RAT[d]                  # remember prior mapping (to free later)
    RAT[d] = p_new                # install new mapping

Sources read the current map; the destination gets a new physical register and overwrites the map. Because every write lands in its own physical register, no two writes collide (WAW gone) and a later write can never clobber a value an earlier reader still needs (WAR gone). The prior mapping old is stashed (in the ROB or a rename history) so it can be reclaimed at commit or restored on a misprediction.

Complexity and a full worked trace

Renaming each operand is a single table lookup or write, so it is O(1) time per operand and O(issue-width) per cycle. Space is the dominant cost: a PRF of P registers each W bits, plus a RAT of (arch-regs x log2 P) bits, plus read/write ports scaling with issue width. The map is checkpointed for fast recovery, which costs O(arch-regs) bits per checkpoint.

Trace the earlier snippet. Start: RAT[R1]=p10, RAT[R2]=p11, RAT[R8]=p18, RAT[R9]=p19. Free list: p30, p31, p32...

i1: R1=MEM[x]   src(x-addr)... ; dest R1 -> alloc p30, RAT[R1]=p30
i2: R2=R1+5     ; src R1 -> p30 (RAW edge to i1!), dest R2 -> p31, RAT[R2]=p31
i3: R1=R9*R8    ; src R9 -> p19, R8 -> p18, dest R1 -> p32, RAT[R1]=p32

Now i3 writes p32 while i1 writes p30 — different registers, so i3 may execute before i1 finishes. i2 still reads p30, i1's result, exactly as program order requires. The false WAR/WAW edges vanished; only the RAW edge i1 to i2 remains, and that is precisely the dependency that must exist.

Where it lives in real systems

Register renaming is standard in essentially every high-performance out-of-order processor shipped in the last three decades:

• MIPS R10000 (1996) and DEC Alpha 21264 popularized the explicit physical-register-file design with an integer and FP map table plus free list.
• Intel P6 (Pentium Pro, 1995) used ROB-based renaming; later Intel cores (Sandy Bridge onward) and AMD Zen moved to a unified PRF with ~180 to 224 integer physical registers.
• Apple Silicon (M-series) and high-end ARM Cortex-X/Neoverse cores rename hundreds of registers to feed very wide back-ends (8+ wide decode).

Renaming also carries free micro-optimizations: move elimination makes MOV rdst, rsrc a zero-cost map update (both names point to one physical register), and zero-idiom elimination turns XOR eax, eax into a map-to-a-hardwired-zero-register with no execution at all. The x86 partial-flag and partial-register renaming machinery is a direct extension of the same idea.

Compared to the alternatives

Before dynamic renaming, the only cures for WAR/WAW were software or stalling:

• Compiler register allocation / renaming: a good allocator spreads writes across distinct architectural names, but it is bounded by the ISA's tiny register count (16 on x86-64, 32 on ARM64). Hardware renaming is unbounded by the ISA and adapts at runtime to cache misses the compiler cannot predict.
• Scoreboarding (CDC 6600): tracks hazards and stalls on WAR/WAW rather than removing them, so false dependencies still cost cycles.
• Tomasulo's original scheme (1967): renames implicitly through reservation-station tags and forwards values on a common data bus — elegant, but values live in scattered RS slots and precise exceptions are awkward without a reorder buffer.

The tradeoff for modern explicit renaming is hardware cost: a large multiported PRF and RAT dominate the core's power and area, and the checkpoint/recovery logic is intricate. In exchange you get full extraction of instruction-level parallelism and precise interrupts.

Pitfalls, failure modes, and why it matters

Renaming is not free of hazards of its own:

• Free-list exhaustion: if every physical register is allocated, the rename stage stalls the whole front-end. PRF size directly bounds how many in-flight instructions (the ROB window) you can sustain.
• Misprediction recovery: on a wrong branch, the RAT must roll back to the state at the branch. Designs either walk the ROB backward (slow) or restore a checkpoint of the whole map (fast but expensive); getting this wrong corrupts architectural state.
• Premature freeing: a physical register may only return to the free list once the instruction that overwrote its architectural name has committed — freeing at the writer's own commit would destroy a value later readers or a rollback still need.
• False sharing of sub-registers: x86 partial-register writes (AL within RAX) create merge dependencies and the classic partial-register stalls.

Its significance is hard to overstate: register renaming is the enabling mechanism that lets out-of-order cores keep dozens to hundreds of instructions in flight, turning a small architected register set into an engine that mines instruction-level parallelism from ordinary code.

Two dominant ways to implement register renaming, plus the original Tomasulo scheme

Scheme	Where the value lives	How registers are freed	Real example
Reservation-station / implicit (Tomasulo 1967)	In reservation stations, tagged by RS number	RS deallocated after result broadcast on CDB	IBM 360/91, early designs
Reorder-buffer (ROB) renaming	Speculative value in the ROB entry; committed value in the ARF	Value copied to ARF at commit; ROB entry recycled	Intel P6 (Pentium Pro), AMD K7
Physical register file (PRF) / explicit	One unified PRF holds both speculative and committed values	Old physical reg freed when the overwriting instruction commits	MIPS R10000, DEC Alpha 21264, modern Intel/ARM
No renaming (in-order)	Architectural register file only	N/A — WAR/WAW stall the pipeline	Classic 5-stage RISC, in-order Atom/A53