Speculation and Recovery

A branch predictor is only useful if the processor acts on its guess. Speculative execution is exactly that leap of faith: rather than wait for a branch to resolve, the machine believes the prediction and charges ahead — fetching, renaming, and even executing instructions from the predicted path, cycles or tens of cycles before it knows whether the guess was right. On a modern deep pipeline the processor may have hundreds of in-flight instructions, most of them past one or more unresolved branches. It is running on faith, continuously.

Faith needs a safety net. The whole scheme works only because the machine can undo a bad guess perfectly. Every speculative instruction's effects are held provisionally in the reorder buffer, never committed to real architectural state until the branch it depends on is confirmed correct. If the prediction turns out wrong, the machine squashes everything down the wrong path as if it never happened. Speculation is aggressive optimism made safe by a flawless undo button.

The two outcomes: commit or squash

When a branch finally resolves, one of two things happens. If the prediction was right, the speculative instructions were real work all along — they simply commit in order like everything else, and the branch cost essentially nothing. If it was wrong, every instruction fetched after the branch is on the wrong path and must be squashed: the ROB entries younger than the branch are flushed, the rename map is rolled back, and the front end restarts fetching from the correct target. The two timelines below show the difference — the same start, wildly different endings.

The misprediction penalty

Squashing isn't free — it is the single largest cost a branch can inflict. Every wrongly-fetched instruction is thrown away, and the pipeline must refill from the correct path. The number of lost cycles is roughly the pipeline depth from fetch to branch-resolution: the deeper the pipeline, the taller the tower of speculative work that collapses. On a 15–20-stage core the misprediction penalty is commonly 15–20 cycles.

\Delta\text{CPI}_{\text{branch}} \;=\; f_{\text{branch}} \times m \times \text{penalty},

where f_{\text{branch}} is the fraction of instructions that are branches and m the misprediction rate. This is precisely why the previous lesson chased 99\% accuracy so hard, and why deeper pipelines (higher clock) fight a losing battle against branches unless prediction keeps up. Run the model:

// Branch misprediction's contribution to CPI, and the wasted work per second. function branchCpi(branchFrac: number, mispredictRate: number, penalty: number): number { return branchFrac * mispredictRate * penalty; } const branchFrac = 0.20; // 1 in 5 instructions is a branch const penalty = 18; // cycles lost per misprediction (deep pipeline) console.log("accuracy mispredict added-CPI"); for (const acc of [0.90, 0.95, 0.98, 0.99, 0.995]) { const m = 1 - acc; const dcpi = branchCpi(branchFrac, m, penalty); console.log(` ${(acc * 100).toFixed(1)}% ${(m * 100).toFixed(1)}% ${dcpi.toFixed(3)}`); } console.log("From 90% -> 99.5% accuracy, the branch CPI tax falls ~20x.");

speculative execution runs instructions past an unresolved branch, on the predictor's guess, before the branch is known;
speculative results are held in the ROB and never committed until the branch is confirmed;
on a misprediction the wrong-path instructions are squashed (ROB flushed, rename map rolled back) and the pipeline refills — the misprediction penalty;
the penalty grows with pipeline depth, so accurate prediction is what makes deep, fast pipelines worthwhile.

Speculating on memory, too

Branches aren't the only thing worth guessing. Loads and stores create a subtler problem called load–store disambiguation. Suppose a load's address isn't yet known, and there's an earlier store whose address is also unknown — does the load read from that store, or from memory? Waiting for every earlier store's address to be computed would serialise memory badly. So the machine speculates: it guesses the load does not alias any pending store and lets it go early (memory dependence speculation). A memory disambiguation unit watches, and if a store later turns out to write the same address the load already (wrongly) read, that's a memory-order violation — the load and its dependents are squashed and replayed, just like a branch misprediction.

Store data also gets forwarded speculatively to matching later loads (store-to-load forwarding) before the store commits. The pattern is universal: guess to avoid a stall, hold the result provisionally, verify, and squash-and-replay if wrong. Speculation is not one feature — it's a design philosophy woven through the whole out-of-order engine.

Here is the twist that shook the industry in 2018. Squashing perfectly undoes an instruction's effect on architectural state — registers and memory. But speculative instructions still ran on real hardware, and they left footprints in microarchitectural state that squashing does not clean up — most damningly, the cache. A speculatively-executed load can pull secret data and use it to index an array, evicting a specific cache line; even after the work is squashed, an attacker can time which line is now fast and read the secret back out. That is Spectre: the architectural undo is flawless, but the timing side-effects leak. Fixing it meant rethinking the boundary between "never happened" and "left no trace" — a story told in full in the security lessons.

A frequent worry: "if the CPU runs wrong-path instructions, can't they corrupt my program?" No — that is the entire point of holding results in the ROB until commit. A squashed instruction's writes never reach the architectural registers or memory, so the program's result is always exactly what non-speculative execution would produce. The only thing a misprediction costs is time (the flushed cycles) and energy (work done and thrown away). Correctness is never at stake — until you count microarchitectural side-channels, which are about timing, not results. Keep those two notions of "effect" separate and Spectre stops being paradoxical.

The bargain of running on faith

Speculation is what turns a good branch predictor into real speed: it lets a machine keep its wide, out-of-order engine full across dozens of branches, extracting parallelism that would otherwise be locked behind unresolved conditions. The costs are wasted energy on mispredicted paths and the flush penalty — both kept small by accurate prediction — plus, as we now know, a security surface nobody anticipated for thirty years. Every high-performance core is a machine that spends most of its life executing instructions it isn't yet certain it should, trusting a predictor and a flawless undo. It is one of the boldest ideas in engineering, and it runs in your pocket right now.