Checkpointing and Recovery from Misprediction

A branch predicted taken sends the front end down a path that may not exist. Hundreds of instructions may be renamed, executed, and even retired behind that prediction before the branch resolves. If the prediction was wrong, every one of those instructions must vanish, and the machine must resume as though only the instructions up to the branch had happened. The hard part is not discarding the instructions. It is reconstructing the small, dense piece of state that says which physical register currently holds each architectural value.

Why unwinding the map is not trivial

The rename table maps 32 or so architectural registers to physical numbers. Instructions change that map as they are renamed: each writing instruction installs a new entry. To undo the renames performed since a branch, the machine would need to know, for each one, the previous mapping it displaced.

One approach stores that in the reorder buffer: each entry records, for its destination, the physical register that the mapping replaced. Recovery then walks the buffer backward from the youngest renamed instruction to the branch, restoring each displaced mapping as it goes. This is called walk-back repair, and its cost is proportional to the number of instructions speculative at the time — potentially hundreds of cycles during which the front end is idle, precisely when the machine has just discovered it needs to refill at a new address.

A second approach avoids the walk by keeping complete copies of the map. These are checkpoints: a snapshot of the rename table, the free register pointers, sometimes the branch history register and the return-address stack, taken at a point from which the machine may need to restart.

What a checkpoint contains

The minimum content is the rename table. A snapshot of 32 architectural entries at, say, 8 bits of physical register number is a few hundred bits — small enough to duplicate several times. The complication is that the machine’s speculative state consists of more than the map:

the free pointer of the circular physical register file, or the head of the free list;
the tail of the reorder buffer and its allocation pointer;
the store queue allocation pointer, if stores allocate at rename;
the branch history register, when the fetch engine’s prediction depends on it;
the return-address stack, in designs that predict returns from a replicated stack.

If any of these is not restored, the machine either leaks resources (never freeing physical registers that were allocated on the wrong path) or commits a partially repaired state that later faults. Designs therefore either checkpoint the whole set or carefully classify which parts are monotonic and need only a pointer reset.

Allocation policies

Three schemes are in use, and they differ mainly in how many speculative branches can be in flight.

Single checkpoint at every branch, none for non-branches. Every predicted branch allocates a checkpoint when it is renamed and frees one when it retires. Since branches are roughly one in six instructions in typical integer code, a 100-instruction window holds on the order of a dozen branches, so the checkpoint pool must have comparable depth. When the pool is empty, the front end stalls — a condition that shows up as fetch starvation unrelated to any cache effect.

Checkpoint at each unresolved branch only. The checkpoint is created when the branch is resolved predicted-taken and freed on resolution, which bounds the number live by the number of in-flight branches but requires the branch to be identified at rename rather than earlier.

Rollback-only with limited deep speculation. A single architectural checkpoint plus walk-back for mispredictions inside the most recent few branches. Cheaper, at the cost of slow recovery for deep mispredictions.

The pool size is a direct trade: more checkpoints allow deeper speculation past multiple branches, and the squash of an older branch still finds a valid snapshot, but each checkpoint costs storage and each allocation costs a write port on the rename table.

Recovery sequence

On a misprediction, the sequence is roughly:

Mark the branch as mispredicted; stop renaming younger instructions.
Select the checkpoint belonging to the youngest correct point — normally the branch’s own checkpoint.
Squash all reorder buffer entries younger than the branch, releasing issue queue entries and invalidating load and store queue entries allocated after it.
Restore the rename table, free pointers, and any other checkpointed state.
Redirect fetch to the correct target and update the branch predictor’s history.
Resume renaming; the correct-path instructions re-enter at the bottom of the window.

Steps 3 and 4 are the expensive ones in a wide machine. The squash can be made cheap by not physically clearing entries: entries carry a “valid up to” marker, and the allocator’s pointers are reset, so the younger entries are simply overwritten later. That reduces the squash to pointer arithmetic and a broadcast of the recovery point. The restore of the rename table is unavoidable and costs a write of each entry.

Recovery latency, meaning the number of cycles from resolution to the first correct-path instruction retiring, is what matters for performance, not the squash cost alone. A deep machine may need the whole front-end pipeline refill before the first useful instruction issues. This is why mispredict recovery is measured in tens of cycles even on machines whose squash is nearly instantaneous, and why the predictor’s accuracy (a separate subject, covered by the branch-prediction material) usually dominates the recovery strategy in importance.

Interaction with the reorder buffer and the register file

Recovery must leave the physical register file in a consistent state. In a circular-register-file design the free pointer is part of the checkpoint, so restoring it also discards the wrong-path allocations. In a free-list design, the registers allocated to wrong-path destinations must be returned to the list; the simplest way is to have the checkpoint record the free-list state, which is a stack snapshot and is cheap to store but awkward to restore if the list is a bit-vector of arbitrary order. Designs that keep the list as a stack avoid the problem entirely.

The checkpoint also interacts with the mechanism described in The Reorder Buffer and In-Order Retirement: because retirement is in order and the branch has not retired when it resolves, the architectural state is provably unaffected, so no memory or architectural register needs undoing. Only the speculative bookkeeping is restored. The converse — recovering after retirement — never needs to happen for a misprediction, because retirement only occurs for resolved branches.

The checkpoint’s content is also a function of the rename mechanism it snapshots. A design that maps architectural names through a table, as described in Register Renaming and the Elimination of False Dependencies, can snapshot a small dense array; a design that encodes the mapping implicitly, in the reorder buffer’s displacement chain, must reconstruct it by walking. That difference is what decides whether a checkpoint is a few hundred bits or a pointer into a structure that has already been overwritten.

There is one exception worth naming: an operation whose ordering is only known at retirement, such as a load that must be checked against an older store whose address is not yet known. This is not a control-flow misprediction and is handled by a different mechanism — replay of the dependent slice, as described in Load-Store Ordering and Memory Disambiguation. Conflating the two in a simulator produces models that either over- or under-count recovery costs.

Recovery cost also depends on what else has to be discarded, and the most expensive thing to discard is not a register value but an in-flight memory operation. A squash that follows a wrong-path load whose address has already been compared against the store queue must unwind that comparison as well as the map, which is why the memory side keeps its own identifiers for speculative operations.

A minimal model of checkpoint pools

The following C model demonstrates the resource behaviour: checkpoints as a fixed pool, squashes discarding all younger speculative work, and a measurable stall when the pool is exhausted.

#include <stdio.h>

#define CHECKPOINTS 4
#define ROB 32

struct ckpt { unsigned long long branch; int in_use; };

struct core {
    struct ckpt pool[CHECKPOINTS];
    unsigned long long alloc;   /* next ROB slot identifier, monotonic */
    int free_slots;             /* ROB entries available */
    int pool_stalls;            /* cycles fetch was blocked on a checkpoint */
};

/* Rename a batch of instructions; returns how many were accepted this cycle. */
static int rename_batch(struct core *c, int width, int n_branches)
{
    int accepted = 0;
    for (int i = 0; i < width; i++) {
        if (n_branches > 0) {
            int slot = -1;
            for (int k = 0; k < CHECKPOINTS; k++) {
                if (!c->pool[k].in_use) { slot = k; break; }
            }
            if (slot < 0) { c->pool_stalls++; break; }   /* pool exhausted */
            c->pool[slot] = (struct ckpt){ .branch = c->alloc, .in_use = 1 };
            n_branches--;
        }
        if (c->free_slots == 0) break;
        c->free_slots--;
        c->alloc++;
        accepted++;
    }
    return accepted;
}

/* Squash everything younger than `branch`, restoring the pool entries after it. */
static void mispredict(struct core *c, unsigned long long branch)
{
    for (int k = 0; k < CHECKPOINTS; k++) {
        if (c->pool[k].in_use && c->pool[k].branch >= branch)
            c->pool[k].in_use = 0;
    }
    unsigned long long killed = c->alloc - branch - 1;
    c->alloc = branch + 1;
    c->free_slots += (int)killed;
    if (c->free_slots > ROB) c->free_slots = ROB;
}

int main(void)
{
    struct core c = { .alloc = 0, .free_slots = ROB, .pool_stalls = 0 };
    /* a run of narrow branches: one branch per four instructions */
    for (int cycle = 0; cycle < 100; cycle++) {
        int n = rename_batch(&c, 4, 1);
        if (cycle % 7 == 0 && c.alloc > 2) mispredict(&c, c.alloc - 3);
        if (n == 0) break;
    }
    printf("pool stalls: %d, allocations: %llu\n", c.pool_stalls, c.alloc);
    return 0;
}

The behaviour to watch is the pool_stalls count as the number of in-flight branches approaches the pool size. With a smaller pool, the stall counter rises before the reorder buffer is full, and the machine’s throughput becomes limited by checkpoint availability rather than by any execution resource. That ordering — the bottleneck moving from data to bookkeeping — is the general failure mode of speculation depth.

Failure modes specific to recovery

Branch inside a microcoded sequence. An expanded instruction containing an internal branch occupies several reorder buffer entries, and its internal checkpoint semantics are not the same as a normal branch. Recovery must either treat the whole expansion atomically or have a defined restart point inside it. Getting this wrong produces states where half of an expansion is committed.

Checkpoint invalidation by an older squash. If a younger branch has a checkpoint and an older branch mispredicts, the younger checkpoint describes wrong-path state and must be destroyed. Designs that keep the checkpoints linearly ordered and discard all after the recovery point handle this; designs that reuse pool slots arbitrarily need a generation tag.

Recovery while a long-latency operation is outstanding. A cache-missing load issued before the branch may still be in flight when the branch squashes. Its result arrives and must be discarded silently. Tagging each result with the reorder buffer identifier of its producer makes this trivial, but the tag must survive the squash and must not collide with a newer entry at the same slot.

State not covered by the checkpoint. The subtle bugs are always here: a predictor’s history register, a prefetcher’s state, a per-instruction operand collector that was not reset. These do not produce wrong arithmetic immediately; they produce a slightly worse prediction rate or an occasional hang, which is the hardest class of defect to attribute.