Misprediction Recovery: Checkpoints, Squash, and the Cost of Being Wrong

Prediction is only half the mechanism. The other half is what happens when the prediction is wrong, and in an out-of-order machine that is not a matter of throwing away fetched bytes. By the time a branch resolves, dozens of younger instructions may have executed, written physical registers, filled store queue entries, and touched caches. None of it may be visible to the architectural state. Recovery is the process of removing exactly that work while keeping the correct work that preceded the branch, and its cost is a large part of why mispredictions are expensive at all.

What speculative state actually is

An out-of-order core separates the architectural registers from the physical registers that hold their values. Renaming maps each architectural register to a physical register, and a new write allocates a fresh physical register rather than overwriting the old value. That indirection is what makes recovery tractable: a wrong-path instruction’s write went to a physical register that the correct state does not reference, so discarding it requires only discarding the mapping, not restoring a value.

Three kinds of state must be dealt with.

Register mappings. The rename map is the authoritative record of which physical register holds each architectural register. A wrong-path write installed a mapping; recovery must restore the map to its value at the branch.

Physical register allocation. A free list hands out physical registers; wrong-path allocations must be returned, or the machine leaks registers and eventually stalls.

Memory ordering state. Stores sit in a store queue and become visible only at retirement, so wrong-path stores can simply be dropped from the queue. Loads, however, have already read memory, and their results sit in physical registers; they are handled by the register mechanism. The store queue is the easy part precisely because stores are deferred.

Everything else — the reorder buffer, the issue queues, the load/store queues, the branch predictor’s own history state — is either flushed wholesale or rolled back to a recorded point.

Walking the reorder buffer backwards

The simple recovery mechanism needs no extra state. Instructions in the reorder buffer carry a bit indicating whether they are speculative, set when a branch is predicted and cleared when the branch retires correctly. When a misprediction is detected, the core walks the reorder buffer from the tail toward the branch entry, marking every younger instruction as invalid, returning its physical registers to the free list, and clearing its store queue entry. The rename map is repaired by walking the same entries in reverse: for each wrong-path write, restore the previous mapping recorded in the entry.

The walk is serial and its length is the number of wrong-path instructions in flight, which on a large window can be a few hundred entries. At one entry per cycle, that is hundreds of cycles of recovery — far more than the pipeline refill cost. Designs therefore compress the walk: several entries per cycle, with the map repair done by a dedicated reverse-index structure, or by grouping the walk by physical register. The Alpha 21264’s published design carries an explicit example of the alternative: integer and floating-point register maps that can be restored without a serial walk.

Checkpoints: snapshot the map, not the instructions

A checkpoint is a saved copy of the rename map at a branch, plus a marker in the free list and in the reorder buffer. Recovery then consists of selecting the checkpoint, writing its map back into the live map in one operation, and freeing every physical register allocated after it.

The checkpoint costs one map’s worth of storage per checkpoint. A map for 32 architectural registers with, say, 8 bits of physical register index per entry is 32 bytes; four checkpoints is 128 bytes of checkpoint storage plus the control to write and restore them. That is cheap compared with a serial walk, which is why checkpoints are the standard mechanism.

The number of checkpoints bounds how many branches can be in flight speculatively. If the core allows four checkpoints and a fifth branch is predicted while four are outstanding, the fifth branch cannot get a checkpoint and must either stall until one frees or proceed without one, falling back to the serial walk if it mispredicts. Real designs tie the checkpoint count to the branch density they expect and to the reorder buffer’s capacity: a window of 200 instructions with a branch every 8 instructions implies up to 25 outstanding branches, so a handful of checkpoints means most branches run without one and recovery falls back to a walk. The mitigation is to allocate a checkpoint only for branches that the predictor marks as low-confidence, since a strongly-predicted branch rarely needs one.

Restoring a checkpoint also has to deal with the other speculative structures. The global history register must be rolled back to its value at the branch — which requires either a saved copy per checkpoint or a shift register that can be rewound by the number of branches retired since. Issue queues must be cleared of wrong-path entries; because they are age-ordered by the reorder buffer index, clearing is a range operation rather than a scan. The load/store queue needs the same treatment.

The redirect and the refill

Recovery and refill are separate costs that overlap. The redirect tells the fetch unit the correct address; the refill is the time from that redirect to the first correct instruction reaching execute. Refill includes the instruction cache access at the target, which may miss and go to the next level, and the pipeline’s own depth from fetch to execute.

The two overlap because the fetch unit can begin refilling while the back end is still draining. A well-designed core starts the redirect as soon as the branch’s direction and target are known, without waiting for the squash of younger instructions to complete, provided the younger instructions are prevented from retiring in the meantime. That ordering is what makes the penalty closer to the pipeline depth than to the sum of drain and refill.

The target for the refill comes from the execution pipeline, not from the predictor that was wrong. For a conditional branch the correct target is the computed one; for an indirect branch it is the value read from the register. This means the redirect address is available at the same time as the direction, and the front end can be restarted immediately.

A subtlety: the branch’s own entry in the predictor must be updated before the refetch, or the refetch will re-predict the same wrong direction. Update happens on the resolution path, which is why the predictor write port and the fetch read port contend in exactly the cycle that matters most. Designs accept a one-cycle bubble here or duplicate the relevant table entry.

What a misprediction costs in an out-of-order core

The fixed-penalty model from the control hazard article understates the cost in two ways that only appear with out-of-order execution.

The first is window occupancy. Wrong-path instructions occupy reorder buffer entries, issue queue entries, and physical registers until recovery completes. During recovery, the core cannot admit new correct-path instructions beyond the checkpoint’s limit. The lost issue opportunity is proportional to how much of the window the wrong path filled, so a misprediction detected after the wrong path has run deep is more expensive than one detected early — even at equal pipeline depth.

The second is cache pollution. Wrong-path loads and instruction fetches allocate cache lines. A wrong-path load that misses brings in a line that the correct path may then have to evict. The effect is data-dependent and can exceed the pipeline penalty by an order of magnitude when the working set is near the cache’s capacity.

A third cost is specific to the predictor itself: mispredictions are what the predictor learns from, but they also disturb global history. A mispredicted branch’s outcome is the opposite of what was predicted, and the speculative history register was built on the prediction. Repairing it requires the saved copies discussed above; failing to repair it leaves the predictor training on a history that never architecturally existed.

Recovery as a design constraint on speculation depth

The cost of recovery limits how aggressively a core can speculate. Every additional branch in flight needs a checkpoint or a fallback walk, and every additional instruction in the window increases the number of wrong-path entries to discard. There is a direct tension between window size, which buys instruction-level parallelism, and misprediction cost, which grows with the amount of speculative work discarded.

This is why some designs limit the number of unconfirmed branches, not just the number of instructions. A core that can hold 200 instructions but only four unresolved branches effectively caps speculation depth on branch-dense code, which is most code. The predictor’s accuracy and the checkpoint count therefore interact: a more accurate predictor needs fewer checkpoints for the same speculation depth, which is a real, if indirect, benefit of predictor research that never appears in misprediction-rate tables.

The mechanisms described here are what make wrong-path execution invisible to the architecture. They do not make it invisible to the machine’s physical state, and that gap is the subject of speculative execution and architectural side channels, where the same structures that discard speculative state leave traces that outlive the squash. That branch of the subject sits outside the recovery logic proper, but it is a direct consequence of it.