Register renaming: Worked examples — Hardware deep dive

This is the hands-on drill page for Register renaming. The parent note gave you the algorithm and one clean example. Here we deliberately hunt down every awkward case: the false hazards, the real hazards you must NOT break, the moment the free list runs dry, the branch that gets mispredicted, and the exception that forces a rollback. If you can trace all of these by hand, you understand renaming.

The figure above is the map we return to in every worked example below. Read it left to right and memorise its three arrows, because each example fires them in a specific order:

Arrow ①, cyan "read sources": the RAT is consulted to find where the current source values live.
Arrow ②, amber "allocate": a slot leaves the Free list to become the destination's fresh $P_{n e w}$ ; at the same moment the RAT's previous mapping is copied into the ROB (the "record old" tick on the arrow).
Arrow ③, amber "commit frees old": a committed (or squashed) instruction returns its $P_{o l d}$ to the Free list.

So the uniform pattern for a normal instruction is ① read → ② allocate + record → (later) ③ free. When an example below says "read / allocate+record / free", glance back at this figure and watch which of the three arrows is firing.

Before symbols, a vocabulary check so nothing is unearned:

Definition The three hazard names (RAW, WAR, WAW)

A hazard is when two instructions touch the same register name and their order suddenly matters. Reading them literally as "second-thing After first-thing" makes them memorable:

RAW — Read After Write. A later instruction reads a register an earlier one wrote. This is a true dependency: the reader genuinely needs the producer's value. Renaming must preserve it.
WAR — Write After Read. A later instruction writes a register an earlier one still needs to read. This is false: the writer does not need the reader's value, it just happens to reuse the name. Renaming removes it.
WAW — Write After Write. Two instructions write the same register name. Also false: architectural state only cares which write is last. Renaming removes it. The whole art of renaming is: keep RAW, dissolve WAR and WAW.

The scenario matrix

Every renaming problem is built from these cells. The worked examples afterwards are labelled with the cell they cover, and together they hit all of them. (RAW/WAR/WAW are defined just above.)

#	Case class	What is special	Danger if you get it wrong
A	RAW (true)	reader needs a real result	must NOT rename it away — keep the link
B	WAR (anti)	writer reuses a name still being read	rename destination → hazard vanishes
C	WAW (output)	two writes to same name	rename each → last one wins correctly
D	Read-before-any-write	source never renamed yet	must read the initial mapping
E	Chained RAW	dest of one is source of next	new physical tag must propagate
F	Free list empty	no physical register to allocate	decode must stall (register pressure)
G	Commit frees old	in-order commit returns a slot	free the old $P$ , not the new one
H	Branch mispredict	wrong-path instructions renamed	restore RAT from a checkpoint
I	Exception rollback	instruction faults mid-flight	unwind ROB, restore old mappings
J	Degenerate: dest = source	e.g. `ADD R1,R1,R2`	read old $P$ then allocate new $P$

We use 9 architectural registers R1–R9 and physical registers P0–P31 throughout, with this starting state (an extension of the parent's — the parent used R1–R8; we include R9 so the SUB examples have a legal second source):

Worked examples

Example 1 — The pure RAW chain (cells A, D, E)

Worked example Statement

Rename, from the shared initial state:

I1: ADD R1, R2, R3   # R1 = R2 + R3
I2: MUL R4, R1, R5   # R4 = R1 * R5

Give the RAT after each instruction, the ROB entry each records, and the physical-register operation executed.

Forecast: which physical register does I2 read for R1 — the old P10 or a new one? Guess before reading.

Step 1 — Read I1's sources from the RAT (arrow ①). $RAT [R 2] = P 11$ , $RAT [R 3] = P 12$ . Why this step? (cell D) R2 and R3 were never written yet, so their values still sit in the initial slots. Never guess — always look up the current table.

Step 2 — Allocate a fresh destination for R1, and record the old mapping (arrow ②). Pop $P 0$ from the free list. Capture the current $RAT [R 1] = P 10$ as $P_{o l d}$ , then write ROB[0]={R1, old P10, new P0}. Execute $P 0 \leftarrow P 11 + P 12$ . Why this step? R1 needs its own slot (reusing P10 could clobber a value someone still reads), and we must stamp the ROB with the old mapping P10 now — that is the only record that lets us free P10 at commit or restore it on a fault.

Step 3 — Update RAT: $R 1 \to P 0$ . Why this step? Future reads of R1 must now find the new result.

Step 4 — Read I2's sources (arrow ①). $RAT [R 1] = P 0$ (not P10!), $RAT [R 5] = P 14$ . Why this step? (cells A, E) This is the true RAW dependency. Step 3 already redirected R1 to P0, so I2 automatically reads I1's result. The dependency is preserved, not removed — that is the whole point of RAW.

Step 5 — Allocate for R4, record, execute (arrow ②). Pop $P 1$ ; capture $RAT [R 4] = P 13$ and write ROB[1]={R4, old P13, new P1}; execute $P 1 \leftarrow P 0 \times P 14$ ; set $R 4 \to P 1$ . Why this step? R4 is written, so it needs its own fresh slot P1, its old mapping P13 must be recorded, and future reads of R4 must be redirected there.

Verify: After renaming, R1 lives in P0, R4 in P1. I2's first source is P0, exactly I1's destination — the data path from I1 to I2 exists, RAW link intact. ROB holds {R1,P10,P0} and {R4,P13,P1}, the two old mappings we will need later. ✓

Example 2 — WAR and WAW dissolved (cells B, C, G)

Worked example Statement

Continue Example 1 with:

I3: ADD R1, R6, R7   # R1 = R6 + R7   (WAW with I1, WAR with I2)
I4: SUB R8, R1, R9   # R8 = R1 - R9   (RAW with I3)

Show that I3 can run before I2 finishes, record its ROB entry, then show what commit frees.

Forecast: after I3, does I2 still read the correct old R1? Yes/No — decide now.

Step 1 — Read I3's sources (arrow ①). $RAT [R 6] = P 15$ , $RAT [R 7] = P 16$ . Nobody touched R6/R7, so initial slots. Why this step? We must locate where the current R6 and R7 values live before computing; they were never renamed, so the initial mapping still holds.

Step 2 — Allocate P2, record old, execute (arrow ②). Pop P2; capture $RAT [R 1] = P 0$ and write ROB[2]={R1, old P0, new P2}; execute $P 2 \leftarrow P 15 + P 16$ . Why this step? (cells B, C) I3 writes R1, and so did I1 (WAW), while I2 is still reading R1 (WAR). By writing into a brand-new slot P2, I3 collides with neither: I2 keeps reading P0, I3 writes P2. Recording old-P0 in the ROB is what will later let commit free P0 safely.

Step 3 — Update RAT: $R 1 \to P 2$ . Why this step? From now on, any instruction reading R1 should see I3's result, so the name R1 must point at P2. I2 already captured P0 in Example 1 step 4, so redirecting the name does not disturb it.

Step 4 — I4: read, allocate, record, execute (arrows ① then ②). Read $RAT [R 1] = P 2$ , $RAT [R 9] = P 18$ ; pop P3; write ROB[3]={R8, old P17, new P3}; execute $P 3 \leftarrow P 2 - P 18$ ; set $R 8 \to P 3$ . Why this step? (cell A) I4's RAW on I3 is real; reading P2 preserves it, R8's write needs a fresh slot P3, and P17 is recorded as its old mapping.

Step 5 — Commit I1 in program order (arrow ③). I1's entry is ROB[0]={R1, old P10, new P0}. Push P10 back to the free list. Why this step? (cell G) You free the register the destination used to map to, because now nothing in program order will ever read P10 again. You do not free P0 — I2 still needs it, and I3's ROB entry still names P0 as its old mapping.

Verify: Physical slots used: I1→P0, I2→P1, I3→P2, I4→P3, all distinct. I2 reads P0, I3 writes P2 → WAR gone. I1 and I3 write P0 and P2 → WAW gone. ROB now holds four entries; committing I1 frees exactly P10 (its $P_{o l d}$ ), not P0. ✓

Example 3 — Degenerate: destination equals source (cell J)

Worked example Statement

From the shared initial state, rename:

I1: ADD R1, R1, R2   # R1 = R1 + R2

This is the trap. Do the order of steps matter?

Forecast: if you allocate the new physical register first, what goes wrong?

Step 1 — Read the source R1 FIRST (arrow ①). $RAT [R 1] = P 10$ . Also $RAT [R 2] = P 11$ . Why this step? (cell J) R1 is both a source and the destination. The read must capture the old mapping P10 before we overwrite it. Reversing the order would make the instruction read its own not-yet-computed result.

Step 2 — Allocate the destination and record old (arrow ②). Pop $P 0$ ; write ROB[0]={R1, old P10, new P0}; execute $P 0 \leftarrow P 10 + P 11$ . Why this step? Only after the source read is safely captured may we hand out a fresh slot; note the recorded $P_{o l d} = P 10$ is the very value we just read as a source — the ROB entry and the source read agree by construction.

Step 3 — Update RAT: $R 1 \to P 0$ . Why this step? The name R1 must now point at the newly computed result in P0, so every later reader of R1 sees the updated value rather than the stale P10.

Verify: Source read = P10 (pre-instruction R1), destination = P0, ROB records old P10. The instruction adds the old R1 to R2 into a fresh slot — identical to R1_new = R1_old + R2. If we had allocated first and read after, R1 would have read P0 (uninitialised) — a bug. Read-then-allocate is mandatory. ✓

Example 4 — Free list empty: register pressure stall (cell F)

Worked example Statement

Suppose only two physical registers are free: free list = $[P 0, P 1]$ , and the ROB is otherwise full of un-committed instructions. Rename this stream (full read / allocate+record bookkeeping):

I1: ADD R1, R2, R3
I2: MUL R4, R5, R6
I3: SUB R7, R1, R4

What happens at I3?

Forecast: how many instructions get renamed before something blocks?

Step 1 — I1: read, allocate, record (arrows ① then ②). Read $RAT [R 2] = P 11$ , $RAT [R 3] = P 12$ ; pop P0 (free list → $[P 1]$ ); write ROB[k]={R1, old P10, new P0}; set $R 1 \to P 0$ . Why this step? Even under pressure the bookkeeping is unchanged: sources are read first, then the destination consumes the top free slot and stamps its old mapping into the ROB.

Step 2 — I2: read, allocate, record (arrows ① then ②). Read $RAT [R 5] = P 14$ , $RAT [R 6] = P 15$ ; pop P1 (free list → $[]$ , empty); write ROB[k+1]={R4, old P13, new P1}; set $R 4 \to P 1$ . Why this step? I2 writes R4, consuming the last free slot P1 and recording old-P13; the free list is now empty, which is the condition we want to stress-test.

Step 3 — I3: read succeeds, allocate FAILS. Read $RAT [R 1] = P 0$ , $RAT [R 4] = P 1$ (arrow ① completes fine). Then attempt arrow ②: the free list is empty → decode stalls. Why this step? (cell F) Reading sources needs no free slot, so arrow ① always works. But every write needs a fresh physical slot for arrow ②. With none available, the renamer cannot record a valid ROB entry and cannot make forward progress; I3 waits in decode. This is exactly register pressure.

Step 4 — An older instruction commits (arrow ③), then I3 resumes. A committed instruction pushes its $P_{o l d}$ (say P10) back: free list → $[P 10]$ . Now I3 completes arrow ②: pop P10, write ROB[k+2]={R7, old P16, new P10}, set $R 7 \to P 10$ . Why this step? Commit returns exactly one $P_{o l d}$ ; that single slot lets the stalled I3 allocate, record its old mapping (P16), and proceed.

Verify: Two allocations exhaust a two-entry free list ( $2 - 2 = 0$ ), so the third's arrow ② stalls even though its arrow ① read (P0, P1) succeeded. One commit restores exactly one slot, enabling exactly one more allocation, whose ROB entry is {R7, old P16, new P10}. The stall is the pipeline throttling itself to the physical-register budget. ✓

Example 5 — Branch misprediction rollback (cell H)

Before the example, one mechanism must be defined so the recovery is not hand-waved:

Worked example Statement

I1: ADD R1, R2, R3       # allocates P0 for R1
I2: BEQ R1, R2, target   # branch: taken if R1 == R2; predicted NOT taken
I3: MUL R4, R1, R5       # wrong-path if branch WAS taken
I4: ADD R1, R6, R7       # wrong-path

The branch was mispredicted (actually taken). I3, I4 were renamed on the wrong path. Restore the machine.

Forecast: what value must R1 map to after recovery — the one before I3/I4, or after?

Start from the shared initial state and rename I1 and I2 first:

I1 pops P0 for R1, records {R1, old P10, new P0}; free list becomes $[P 1, P 2, P 3, \dots]$ .
I2 is a branch: BEQ reads R1 and R2 but writes nothing, so it allocates no physical register. The free list stays $[P 1, P 2, P 3, \dots]$ . At this branch we take the checkpoint: $R 1 \to P 0$ , $R 4 \to P 13$ , everything else initial.

Step 1 — Rename I3 speculatively (arrows ① then ②). Read $RAT [R 1] = P 0$ , $RAT [R 5] = P 14$ ; pop P1 (free list → $[P 2, P 3, \dots]$ ); record {R4, old P13, new P1}; set $R 4 \to P 1$ . Why this step? Even though the branch outcome is unknown, the pipeline keeps renaming down the predicted path so it never idles; I3 reads the current R1 (P0) and takes the next free slot P1 for R4.

Step 2 — Rename I4 speculatively (arrows ① then ②). Read $RAT [R 6] = P 15$ , $RAT [R 7] = P 16$ ; pop P2 (free list → $[P 3, \dots]$ ); record {R1, old P0, new P2}; set $R 1 \to P 2$ . Why this step? Continuing speculatively, I4 writes R1 into fresh slot P2; this is the RAT change that will have to be undone if the guess was wrong.

Step 3 — Branch resolves: mispredict. I3 and I4 must be squashed. Why this step? (cell H) They were never supposed to execute. Any RAT changes and allocations they made are wrong-path pollution.

Step 4 — Restore RAT from the checkpoint; free the wrong-path slots (arrow ③). Copy the checkpoint back: $R 1 \to P 0$ , $R 4 \to P 13$ . Return P1 and P2 to the free list. Why this step? The checkpoint captured the exact map before speculation began, so copying it back erases every wrong-path change in one step; the two speculatively-allocated slots go back to the pool.

Verify: After I1, only P0 is gone, so the free list at the branch is $[P 1, P 2, \dots]$ — the wrong-path instructions therefore take P1 and P2 (not P2/P3). After recovery $R 1 \to P 0$ (I1's result) and $R 4 \to P 13$ (committed value); freed slots are exactly ${P 1, P 2}$ . Physical-register count is conserved. ✓

Example 6 — Exception rollback via the ROB (cell I)

Step 1 — Commit everything older than I2 (arrow ③). I1 commits normally: its entry {R1, old P10, new P0} frees old P10. Why this step? (cell I) A precise exception preserves all instructions before the faulting one. I1 finished cleanly, so it retires and returns its $P_{o l d}$ .

Step 2 — At I2, take the fault; unwind the ROB from the tail back to I2 (arrow ③, in reverse). Walk entries I4, I3, I2 in reverse program order, restoring each $P_{o l d}$ and freeing each $P_{n e w}$ :

undo I4 {R8,P17,P3}: set $R 8 \to P 17$ , free P3
undo I3 {R1,P0,P2}: set $R 1 \to P 0$ , free P2
undo I2's own entry {R4,P13,P1}: set $R 4 \to P 13$ , free P1

Why this step? Unwinding from the tail restores mappings in reverse order, so each register returns to whatever it pointed at just before its writer ran. The $P_{n e w}$ slots the squashed instructions allocated are freed because nothing valid will ever read them. This is the payoff of the "record old" arrow ② we stamped in every example above — without those recorded $P_{o l d}$ fields this reversal would be impossible.

Step 3 — Resulting architectural state. $R 1 \to P 0$ (from committed I1), $R 4 \to P 13$ , $R 8 \to P 17$ ; free list regains P1, P2, P3 (plus P10 from step 1). Why this step? This is the exact machine state as if only I1 had run — the definition of precise.

Verify: I1's write survives ( $R 1 \to P 0$ ), while I2/I3/I4 vanish ( $R 4 \to P 13$ , $R 8 \to P 17$ ). Freed by unwinding: P1, P2, P3 — precisely the three the squashed instructions allocated; plus P10 from committing I1. The ROB's old-mapping field is exactly what makes the reversal possible. ✓

Example 7 — Cycle-count word problem (real-world twist)

Before the numbers, the timing vocabulary this example uses:

Step 1 — Write the ratio. $Speedup = \frac{T _{without}}{T _{with}} = \frac{9}{6} .$ Why this step? Speedup is old time over new time — a dimensionless number telling you how many times faster.

Step 2 — Evaluate. $9/6 = 1.5$ . Why this step? Reducing the fraction gives the plain multiplier; $9$ and $6$ share a factor of $3$ , so $9/6 = 3/2 = 1.5$ .

Step 3 — Interpret. Renaming removed the false WAR/WAW stalls on R1, letting I3 start alongside I2 instead of after it. Why this step? The whole point of the number is to attribute it to a mechanism — here the eliminated false dependencies are exactly what shrank the "wait" cycles from the without-renaming timeline.

Verify: $1.5 \times$ means the renamed block finishes in $6/9 = 0.667$ of the original time. Cycles are the unit on both top and bottom, so speedup is unitless. ✓

Example 8 — Physical-register sizing (exam-style)

Step 1 — (a) Apply the sizing bound. $N_{p h y s} \geq N_{a r c h} + N_{R O B} = 16 + 224 = 240.$ Why this step? You need one slot per committed architectural value (16) plus one per in-flight, uncommitted instruction that may have allocated a slot (up to 224). Below 240, a full ROB could demand a slot the file cannot supply.

Step 2 — (b) Round to a design-friendly number. The next power of two $\geq 240$ is $256 = 2^{8}$ . Why this step? Physical registers are addressed by a binary tag; choosing a power of two makes that tag a clean fixed width (here 8 bits) with no wasted decode logic, so designers pick the smallest power of two that still meets the minimum.

Step 3 — (b, continued) Report and justify. Minimum 240, typical 256, using an 8-bit physical register tag. The extra $256 - 240 = 16$ slots are useful slack: they let bursts of back-to-back writes allocate without immediately hitting the register-pressure stall of Example 4. Why this step? The exam answer must name both the hard minimum and the practical choice, and explain that the choice is the tightest power-of-two that both indexes cleanly and leaves headroom.

Verify: $2^{8} = 256 \geq 240$ , and $2^{7} = 128 < 240$ would be too small — so 256 is indeed the smallest adequate power of two. The 16-register slack (256 − 240) also cushions bursts of writes. ✓

Recall Self-test — cover the answers

RAW is a true dependency; renaming must ___ it. ::: preserve it (keep source pointing at producer's physical register) WAR and WAW are false; renaming removes them by ___. ::: giving each write its own fresh physical register The three arrows fired at every instruction, in order, are ___. ::: ① read sources, ② allocate + record old in ROB, ③ free old at commit For ADD R1,R1,R2 you must ___ before you ___. ::: read the old source mapping ; allocate the new destination When the free list is empty, ___ still succeeds but ___ stalls. ::: reading sources (arrow ①) ; allocation (arrow ②) → register pressure On misprediction you restore the RAT from a ___; on exception you unwind the ___. ::: branch checkpoint ; ROB using recorded old mappings At commit you free the ___ physical register, not the new one. ::: old

Where this connects

The renaming tables feed directly into Out-of-Order Execution and Tomasulo's Algorithm, where physical tags are what reservation stations wait on.
The Reorder Buffer (ROB) supplies the old-mapping field every rollback above depended on.
Removing false hazards is exactly how renaming boosts Instruction-Level Parallelism (ILP) in Superscalar Execution.
Branch Prediction supplies the checkpoints used in Example 5; contrast the simpler Scoreboarding which stalls on false hazards instead of renaming them away.
🇮🇳 Yeh sab Hinglish mein →