How Does Register Renaming Eliminate False Hazards?

Register renaming is a hardware technique used in modern out-of-order processors to remove artificial data dependencies between instructions. By dynamically mapping a small set of programmer-visible architectural registers to a much larger pool of internal physical registers, the processor ensures that instructions only wait for true data dependencies rather than name conflicts. This allows independent instructions to execute in parallel and significantly improves instruction-level parallelism.

Architectural Registers Versus Physical Registers

In classical instruction set architectures (ISAs) such as x86 or ARM, instructions reference a fixed, relatively small number of architectural registers—typically 16 or 32. Because compilers must reuse these limited names across many different variables, unrelated instructions frequently end up targeting the same architectural register name.

Inside the microarchitecture, however, the CPU maintains a much larger pool of physical registers, often numbering in the hundreds. If there are \(N\) architectural registers and \(M\) physical registers (where \(M > N\)), the extra \(M - N\) registers provide the storage needed to hold multiple simultaneous versions of the same architectural register without overwriting active values.

Understanding True and False Data Hazards

When instructions execute out of order, data hazards can prevent parallel execution. These hazards fall into two categories:

  • Read-After-Write (RAW): A true dependency where an instruction needs a value produced by an earlier instruction. This cannot be eliminated because the data genuinely does not exist yet.
  • Write-After-Read (WAR): A false (anti-)dependency where a later instruction writes to a register before an earlier instruction has finished reading its old value.
  • Write-After-Write (WAW): A false (output) dependency where two instructions write to the same register, and the later write must not overwrite the earlier one before consumers read it.

WAR and WAW hazards are called false hazards because they do not involve actual data flow between instructions; they exist solely because both instructions share the same architectural register name.

How the Register Alias Table Works

To break false dependencies, the processor's rename stage uses a hardware structure called the Register Alias Table (RAT), sometimes referred to as the map table, alongside a free list of unallocated physical registers.

When an instruction enters the rename stage, two things happen:

  1. Source operands are looked up: The RAT translates each architectural source register into the physical register that currently holds its most recent value.
  2. Destination operands are allocated: For each architectural destination register, the processor pops an unused physical register from the free list, updates the instruction to write to that new physical register, and updates the RAT to point that architectural register name to the newly allocated physical register.

Because every new write receives a distinct physical register, an earlier instruction reading the old physical register is completely unaffected by a later instruction writing to a new physical register. Both WAR and WAW hazards vanish.

A Step-by-Step Example

Consider the following sequence of instructions using architectural registers \(R_1\), \(R_2\), and \(R_3\):

  1. \(R_1 \leftarrow R_2 + R_3\)
  2. \(R_2 \leftarrow R_1 \times 4\)
  3. \(R_1 \leftarrow R_3 - 1\)

Instruction 3 has a WAW hazard with instruction 1 (both write to \(R_1\)) and a WAR hazard with instruction 2 (instruction 2 reads \(R_1\) before instruction 3 overwrites it).

Assuming the RAT initially maps \(R_1 \to P_1\), \(R_2 \to P_2\), and \(R_3 \to P_3\), and the free list contains \(P_4, P_5, P_6\):

  1. Instruction 1 becomes \(P_4 \leftarrow P_2 + P_3\). The RAT updates \(R_1 \to P_4\).
  2. Instruction 2 becomes \(P_5 \leftarrow P_4 \times 4\). The RAT updates \(R_2 \to P_5\).
  3. Instruction 3 becomes \(P_6 \leftarrow P_3 - 1\). The RAT updates \(R_1 \to P_6\).

Now, instruction 3 writes to \(P_6\) while instruction 2 reads from \(P_4\). Instruction 3 no longer depends on instructions 1 or 2 and can execute immediately if \(P_3\) is ready.

Reclaiming Physical Registers and Speculation Recovery

Because the physical register pool is finite, old physical registers must eventually be recycled. A physical register cannot be returned to the free list as soon as its instruction finishes executing; it must wait until the next instruction that overwrites the same architectural register commits (retires) in program order. At that point, no older instruction can ever read the old value again, so the previous physical register is safely freed.

Register renaming also simplifies branch misprediction and exception recovery. If a speculative branch is mispredicted, the processor simply discards the speculative RAT updates and restores the architectural RAT state from a checkpoint or a retirement map table, instantly returning the machine to a precise architectural state.