Register renaming: Visual walkthrough — Hardware deep dive

This is the picture-first deep dive for Register renaming. We build the whole idea from a blank slate: no jargon used before it is drawn. If a word looks scary, wait — there is a chalkboard picture for it right below.

Let us define our very first words, plainly.

We will follow one little program the entire way. Meet it now:

I1:  R1 = R2 + R3
I2:  R4 = R1 * R5
I3:  R1 = R6 + R7
I4:  R8 = R1 - R9

Keep your eye on the label R1. Three different instructions want to use it, but they mean different numbers. That collision is what we are about to cure.

Step 1 — Draw the collision on the label R1

WHAT. We lay the four instructions on a timeline and draw arrows between any two that touch the same register.

WHY. Before fixing a problem you must see it. Not every arrow is equally bad — we need to tell the real arrows from the fake ones, and a picture makes the difference obvious.

PICTURE.

Read the arrows:

Blue arrow (I1 → I2): I2 needs the number I1 just made in R1. If I1 hasn't finished, I2 has nothing to multiply. This is a Read After Write (RAW) dependency — a real one, called a true dependency.
Pink arrow (I2 → I3): I3 writes R1 while I2 is still reading R1. If I3 writes too early, I2 reads the wrong number. This is a Write After Read (WAR) dependency.
Yellow arrow (I1 → I3): both I1 and I3 write R1. This is a Write After Write (WAW) dependency.

Step 2 — See why the false arrows waste time

WHAT. We schedule the program obeying every arrow, then measure how many cycles it costs.

WHY. To prove the false arrows are expensive, we compare "obey everything" against "the ideal". The gap between them is exactly the speed we are leaving on the table.

PICTURE.

D = decode (understand the instruction), E = execute (do the maths).
Top block: obey the pink WAR arrow → I3 is forced to wait for I2 even though it is independent. Chain drags out.
Bottom block: if the pink and yellow arrows vanished, I3 could execute beside I2. The whole run finishes sooner.

The waiting boxes in the top block are pure loss caused by a name, not by data. That is our motive to keep going.

Step 3 — The core idea: names vs boxes are different things

WHAT. We split the single concept "register" into two separate concepts.

WHY. The trap is that R1 means both "the label a programmer typed" and "the physical box the number lives in". As long as those are the same thing, two instructions writing R1 must fight over one box. Separate them and the fight ends.

PICTURE.

The RAT is just a phone book: dial a label, get a box number. When two instructions want to "write R1", we simply point the label at a fresh box the second time. Now they scribble in different boxes — no fight.

Step 4 — The renaming recipe, one instruction at a time

WHAT. We turn the idea into a fixed 4-move procedure the hardware runs on every instruction as it is decoded.

WHY. A recipe must be mechanical — no cleverness, no guessing — because silicon has to do it millions of times per second. Each move answers one need.

Formula Rename one instruction

Rdest = Rsrc1 op Rsrc2

move 1: grab a fresh box P_{n e w} \leftarrow FreeList.pop()

move 2: look up where the inputs really live P_{sr c 1} = RAT [R_{sr c 1}], P_{sr c 2} = RAT [R_{sr c 2}]

move 3: repoint the label to the fresh box RAT [R_{d es t}] \to P_{n e w}

move 4: write down the box we replaced ROB [tail] = {R_{d es t}, P_{o l d}, P_{n e w}}

Term by term:

$P_{n e w}$ — the brand-new box this instruction will write its answer into.
$RAT [R_{sr c}]$ — "which box holds the current value of this source?" (Some earlier instruction may have moved it.)
$P_{o l d}$ — the box the label pointed at before this instruction. We keep its name so we can undo, and so we know what to recycle later.
$ROB$ — the Reorder Buffer, a queue that remembers in-flight instructions in program order.

PICTURE.

Follow the four moves for I1: R1 = R2 + R3: pop P0, look up R2→P11 and R3→P12, repoint R1→P0, and stash the note {R1, old=P10, new=P0} in the ROB.

Step 5 — Run the whole program through the machine

WHAT. We apply the 4-move recipe to all four instructions and watch the RAT change.

WHY. One instruction proves the mechanics; four prove the cure — we want to literally see the pink and yellow arrows vanish.

Start state: R1→P10, R2→P11, R3→P12, R4→P13, R5→P14, R6→P15, R7→P16, R8→P17, R9→P18, free list [P0,P1,P2,P3,…].

Instr	reads (boxes)	new box	RAT after	ROB note
I1 `R1=R2+R3`	P11, P12	P0	R1→P0	{R1, P10→P0}
I2 `R4=R1*R5`	P0, P14	P1	R4→P1	{R4, P13→P1}
I3 `R1=R6+R7`	P15, P16	P2	R1→P2	{R1, P0→P2}
I4 `R8=R1-R9`	P2, P18	P3	R8→P3	{R8, P17→P3}

PICTURE.

The magic is in the boxes for R1:

I2 reads R1 and gets P0 (I1's answer).
I3 writes R1 into P2 — a different box — so it cannot clobber P0.
I4 reads R1 and gets P2 (I3's answer).

The pink WAR arrow (I2 read vs I3 write) is gone: they touch P0 vs P2. The yellow WAW arrow (I1 write vs I3 write) is gone: P0 vs P2. Only the blue true arrows survive.

Step 6 — The commit rule and the "don't free too soon" case

WHAT. We describe when a used-up box goes back to the free list, and the mistake of doing it early.

WHY. If we never recycled boxes we would run out. But recycle too soon and an instruction that still needs the old value reads garbage. The commit rule threads this needle.

PICTURE.

The picture shows the danger case: if we freed P0 the instant I3 renamed R1, then I2 — which still needs P0 — could find P0 already handed to someone else and overwritten. Waiting for I2's commit before recycling P0 is exactly why $P_{o l d}$ is stored and freed late.

Step 7 — The degenerate case: running out of boxes

WHAT. We count how many physical boxes we need, and what happens when the pile empties.

WHY. Renaming only works while the free list has boxes. If move 1 (FreeList.pop()) finds an empty pile, the whole trick stalls. So we must size the pile correctly.

PICTURE.

The picture shows the free list draining to empty; the next pop() finds nothing, so decode stalls until a commit pushes a box back. This backlog is register pressure. Example: 16 labels + a 224-entry ROB ⇒ need ≥ 240 boxes; real chips round up to 256 (a tidy power of two for indexing).

The one-picture summary

One label R1, three writers, three distinct boxes P0, P2, P3 — the false arrows dissolve while the true arrows remain, and independent work runs side by side. This same engine feeds Out-of-Order Execution, Tomasulo's Algorithm, and Superscalar Execution; a wrong branch guess is undone by restoring old RAT mappings from the ROB.

Recall Feynman retelling — say it back in plain words

We had only a few register labels, so different jobs kept colliding on the same label even when their work was unrelated. We split "label" from "storage box": labels stay few (so old programs still run), boxes are many and hidden. A little phone book, the RAT, remembers which box each label points to right now. Every instruction grabs a fresh box for its answer, looks up its inputs' current boxes, then repoints its output label to the fresh box — and jots down the box it replaced. Because each writer of R1 gets its own box, the only surviving connections are the ones that carry a real number. We recycle a box only when the instruction that replaced it becomes official, so nobody ever reads a box that got handed away too early. And we keep enough boxes — at least labels plus in-flight instructions — or the machine has to pause. That is the whole trick: same tiny instruction set on the outside, a big secret pile of boxes on the inside.

Recall Quick self-test

Which arrows are false and why? ::: WAR and WAW — they are only name clashes, not data needs; renaming to distinct boxes removes them. Why read source operands from the RAT instead of using the label directly? ::: Because an earlier instruction may have moved that label to a new box; the RAT gives the box holding the current value. Why free $P_{o l d}$ at commit, not at rename? ::: An earlier-in-program-order instruction still in flight may need the old box; only commit guarantees it is truly dead. Minimum physical registers for 16 labels and a 224-entry ROB? ::: $16 + 224 = 240$ (chips round to 256).