CPU Register Renaming Interview: True Dependencies, Free Lists, and Recovery

Register renaming removes false name dependencies by assigning new physical destinations, while preserving true producer-consumer dependencies through physical source tags. Also track the old destination, explains when it can be reclaimed and shows how a branch flush recovers both mappings and allocation history.

The original trace below follows those ownership changes explicitly. PracHub's CPU microarchitecture and simulator-design question provides broader discussion context. The goal is to make every physical register's lifetime explainable, rather than recite that renaming “removes hazards.”

BOOM's explicit-renaming design is the primary implementation reference. The register names, instruction sequence and recovery results here are original Python-model inputs. We did not run BOOM RTL or verify a complete speculative processor, and no candidate report establishes an employer-specific question pattern.

Separate architectural names from physical values

An architectural register name belongs to the instruction-set interface. A physical register holds one particular version of a value in an explicit-renaming design. Several physical versions associated with the same architectural name can exist while instructions are in flight.

A write-after-write relationship arises when two instructions use the same destination name. A write-after-read relationship arises when a younger instruction reuses a name an older instruction reads. Distinct physical destinations can separate those name conflicts. A true read-after-write dependence remains: the consumer still needs the producer's actual value.

BOOM's rename-stage documentation describes this distinction and its physical-register-file organization. Other processors can organize speculative values differently; do not assume that every reorder buffer stores all result data or that every renaming design has the same tables. BOOM rename stage

For this exercise, use ordinary writable registers r1, r2 and r3. Exclude the special constant-zero register, condition codes and partial-register writes. Our map starts with r1→p1, r2→p2 and r3→p3, while p4 through p7 are free.

Read sources before installing the new destination

Instruction I1 computes r1 = r1 + r2. Its sources must refer to the old r1 and current r2, so it reads p1 and p2. It then allocates p4 as its destination, remembers p1 as the stale destination and updates the speculative map to r1→p4.

If you update the map first and then read the r1 source, the instruction would appear to depend on its own newly allocated destination. The old value has not become unnecessary merely because the architectural spelling appears on both sides of the instruction.

Instruction I2 computes r3 = r1 + r3. It must see the preceding instruction's new r1 mapping p4, while reading the old r3 mapping p3. It allocates p5 and records p3 as stale. In a multi-instruction rename group, that requires the appropriate mapping update to reach later instructions in the same group.

The table preserves true dependencies. I2 needs the value I1 will write to p4; renaming does not make it ready early. A separate readiness mechanism determines when that value can be consumed through the register file or bypass network.

Explain why writeback is too early to free the stale value

After I1 writes p4, an older in-flight reader might still need p1. Reclaiming p1 at I1's writeback can let a younger instruction overwrite storage that an older instruction still owns. Completion order alone does not establish that all relevant readers have passed.

In this model, I1's retirement makes its stale destination p1 reclaimable. In-order retirement establishes that older instructions have completed the architectural work required before it. The newly committed p4 remains live; freeing the new destination at that moment would destroy the committed value.

BOOM documents retaining a stale destination specifier and returning it to the free list on commit. Its register-file/bypass description provides the associated operand-delivery context. These mechanisms must agree about value identity and lifetime. Register files and bypass

I3 later replaces r1's speculative mapping p4 with p6, but that does not immediately release p4 either. I2 already captured p4 as a source. A map table records the newest speculative name binding; it is not a complete inventory of every physical value still in use.

A useful interview check asks which register becomes free at each event. At I1 writeback, none becomes free solely for that reason. At I1 retirement, p1 becomes free under this model. At I3 retirement, p4 can be reclaimed if the surrounding retirement and ownership assumptions hold.

Snapshot the mapping at a branch boundary

Place a branch after I2 and before I3. Its checkpoint map is r1→p4, r2→p2 and r3→p5. At that point, the free set contains p6 and p7. I1 and I2 are older than the branch; I3 is younger.

If the branch later mispredicts, restoring this mapping returns the speculative name state to the branch boundary. It must not restore the initial map r1→p1, because I1 and I2 belong to the surviving older path. A branch checkpoint and a committed architectural checkpoint represent different boundaries.

BOOM's branch documentation supplies the broader speculation context. Our example has one branch and no nested masks, delayed checkpoint release or instruction-fetch recovery. Adding those features requires an explicit ownership and checkpoint protocol. Branch speculation context

Recovery must restore allocation ownership as well as the mapping snapshot. Younger instructions allocated physical registers that must return to the free list when squashed. Older surviving values and newly freed registers must remain correctly accounted for at the same time.

Reproduce the free-list snapshot leak

Continue the original sequence. I3 allocates p6 after the branch. Then the older I1 retires and frees its stale p1. A younger instruction I4 now allocates p1 to write r3. The current free set is only p7.

At recovery, the branch's old free-list snapshot contains p6 and p7. The current free list contains p7. Taking their union recovers p6 and p7, but misses p1: it was allocated at the checkpoint, freed by older retirement and then allocated again to younger work.

A post-branch allocation list records p6 and p1. Returning those allocations to the current free list produces p1, p6 and p7. The restored map still owns p4, p2 and p5, so none of those live mappings overlaps the recovered free set.

Checkpoint free:          {p6, p7}
Current free:             {p7}
Post-branch allocations:  {p6, p1}
Snapshot union result:    {p6, p7}       misses p1
Allocation-list result:   {p1, p6, p7}

The local checker reproduced the missing-p1 case and verified the corrected free set. It also checked that I2's sources are p4 and p3, I3's stale destination is p4, and p4 is not reclaimed by the branch flush. Those are concrete invariants, not a full proof of the allocator.

Recover ownership rather than every historical free event

The allocation-list approach answers which physical destinations younger work acquired after the checkpoint. It does not mean blindly freeing every register mentioned by a squashed instruction. A stale destination can belong to surviving older work and must remain allocated.

In our trace, I4's stale destination is p5, which I2 produced before the branch. Squashing I4 must return its new p1 but retain p5. Confusing new and stale destinations at flush would free a value the restored mapping still uses.

Also consider a late result from squashed I3. Its destination p6 may already have been returned and reassigned. A completion message needs enough valid identity to avoid corrupting the new owner. The free-list model does not implement result-bus cancellation, so this remains a required integration check.

For nested branches, ask which allocation lists receive a new destination and which lists are discarded or merged after resolution. A correct one-branch example does not establish nested recovery correctness. Write down the branch-age relationships before generalizing the union operation.

Check resource exhaustion before accepting another rename

A free-list trace should also say what happens when no destination is available. A writing instruction cannot be accepted into rename with a made-up physical tag or a tag that another live instruction owns. Upstream backpressure must preserve the instruction until allocation can complete.

For a multi-instruction group, clarify whether acceptance is all-or-nothing or permits a valid prefix. If only one register is free and two instructions write destinations, that interface choice determines which mappings may change. A later retry must not allocate a second destination for an instruction that was already accepted.

These are proposed allocator-interface checks beyond the four-instruction model. They connect physical ownership to accepted work, much like the retirement trace connects completion status to architectural history. Count accepted allocations, committed stale returns and squashed new destinations separately.

A scalar free-count check is useful but incomplete. Returning the wrong physical identifier can preserve the total count while creating one duplicate owner and one leaked register. Our explicit map/set trace exposes identity, so the count is a consistency check rather than the only oracle.

Distinguish rename correctness from execution readiness

Stale busy state can break scheduling even when the physical map is correct. A newly allocated destination should not appear ready simply because its previous owner left a ready bit behind. Allocation and readiness initialization must describe the same version of the value.

Likewise, a bypass path can deliver the right numeric bits with the wrong tag. A consumer waiting for p4 must not accept an unrelated result merely because it uses the same architectural name r1. Renaming works by preserving physical producer identity through the whole operand path.

The original Python trace models mappings and free sets only. It does not simulate execution latency, multiple writeback ports or branch/result races. Its purpose is to make the ownership arithmetic visible and expose two tempting shortcuts: update-before-read and snapshot-only free-list recovery.

For a proposed verification environment, keep a reference architectural execution and separate physical ownership checks. Ensure free registers are disjoint from live mappings, no destination is allocated twice and every accepted allocation is eventually retained or reclaimed according to retirement or squash. Avoid an oracle that merely copies the implementation's bit-vector updates.

Practice the trace with a challenged lifetime

These PracHub records cover microarchitecture, out-of-order behavior, verification, VLIW scheduling and an interpreter. The last two are related reasoning exercises with different execution models. The shared CPU records support distinct physical-lifetime follow-ups here; they are not an employer-specific rename question bank.

Use the CPU microarchitecture question, then draw the map and free set after every event in the leak witness. Ask a partner to select a physical register and challenge why it is free or live. Your explanation should identify its owner and the event that can legally end that ownership.

Sources and Further Reading

• BOOM: rename maps, stale destinations and allocation-list recovery
• BOOM: physical register files and bypass networks
• BOOM: branch speculation and recovery context

Sources checked November 3, 2026. Original map/set checks do not establish full-core recovery, timing or formal correctness.