Control Hazards: The CPU Does Not Know Where You Are Going
A pipelined CPU must fetch an instruction every cycle, but at a conditional branch it does not yet know which instruction comes next. Waiting for the answer is unaffordable on a deep pipeline, which is why every high-performance CPU guesses instead.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
The gap between fetch and resolve
Fetch happens at the front of the pipeline; the condition is evaluated in an execution unit well behind it. Between those two points, the fetch stage will have consumed several cycles, and it must have been fetching *something* during them.
If the machine stalled at every branch until resolution, the cost would be the number of stages between fetch and resolve — every time, for every conditional. Real code branches roughly every handful of instructions, so this would erase almost all the benefit pipelining provides.
This is also why the cost scales with pipeline depth. A shallow pipeline resolves quickly and could plausibly afford to wait; a deep, high-frequency one cannot. The industry's move toward deeper pipelines in pursuit of clock speed is precisely what made accurate branch prediction indispensable rather than merely useful.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|
| I1 BEQ r1, r2, target | I | I | E | M | W | |||
| I2 (waiting — address unknown) | I | I | E | M | W |
Three kinds of uncertainty
Not all control transfers are equally hard. An unconditional direct jump has a known target encoded in the instruction; the front end can follow it almost immediately, and it is barely a hazard at all. A conditional branch has a known target but an unknown direction — the machine must predict taken or not-taken. An indirect branch has an unknown target: a function pointer, a virtual call, or a switch compiled to a jump table.
Indirect branches are the hardest because the space of possible answers is large rather than binary. Predictors handle them with target buffers that remember recent destinations, and they work well when a call site is effectively monomorphic — always calling the same implementation — and poorly when it genuinely varies.
This is the hardware reason behind a familiar software observation: a virtual call in a hot loop where the concrete type changes unpredictably costs far more than the indirection itself suggests. The cost is not the extra pointer dereference; it is the mispredicted target and the pipeline refill behind it.
| Kind | What is unknown | Typical difficulty | Software shape |
|---|---|---|---|
| Unconditional direct jump | Nothing — target is encoded | Trivial | Loop back-edge, goto, static call |
| Conditional branch | Direction only | Easy when correlated with history | if, loop condition, bounds check |
| Indirect branch | Target address | Hard when the target varies | Virtual call, function pointer, jump table |
| Return | Target address | Easy — a dedicated return stack predicts it | Function return |
Why this shapes how code performs
Because the cost is the pipeline refill rather than the comparison, branch cost is invisible in an instruction count and roughly independent of how simple the condition is. if (x) and if (complicated_but_cheap_expression) cost the same when mispredicted, because what you pay for is the wrong guess, not the evaluation.
It also means the *data* determines the cost, not the code. The identical loop over sorted input and over shuffled input differs substantially in runtime on branch-heavy code, because sorted input makes the branch predictable. This is one of the clearest demonstrations that hardware behaviour is not a property of the program text alone — the same instructions on different data are effectively different programs to the front end.
The follow-on lessons split cleanly from here: Branch Prediction: Guessing Well Enough to Matter covers how the guess is made, Misprediction: What a Wrong Guess Costs covers what a wrong guess costs, and Branchless Code: A Trade, Not an Upgrade covers when it is worth removing the branch rather than trying to make it predictable.
1// Both loops execute identical instructions n times.2for (i = 0; i < n; i++)3 if (data[i] > threshold)4 sum += data[i];5 6// data[] sorted: the branch is taken for a long run,7// then not-taken for a long run.8// A predictor learns this almost perfectly.9//10// data[] shuffled: the branch outcome is effectively random.11// A predictor cannot do better than chance,12// and every wrong guess costs a pipeline refill.13//14// The gap is not in the arithmetic. It is in the front end.Key points
- The fetch stage needs a next address several cycles before a branch condition is evaluated.
- Stalling at every branch would cost pipeline depth per branch and erase most of pipelining's benefit.
- Direction uncertainty (conditional) and target uncertainty (indirect) are different problems with different difficulty.
- Branch cost is the pipeline refill, so it is independent of how cheap the condition itself is.
- The same code over different data can have completely different front-end behaviour.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Fetch → branch encountered: the front end reaches a conditional branch whose direction is not yet known.
- 2Branch → execution unit: the condition will be evaluated several stages later, after the operands are available.
- 3Front end → speculative address: rather than stall, the predictor supplies an address and fetch continues from it.
- 4Execution unit → resolution: the true direction and target become known and are compared against the prediction.
- 5Mismatch → squash: speculative instructions are discarded and fetch restarts at the correct address, costing pipeline depth.
- • "Branches are slow" — predictable branches are nearly free; only unpredictable ones cost.
- • "Simplifying the condition will make the branch cheaper" — the cost is the refill, not the comparison.
- • "The loop is slow so the body must be expensive" — a mispredicting branch can dominate an inexpensive body entirely.
Consequences, controls and cost
- • Branch-heavy code with unpredictable outcomes runs far below the machine's peak instruction rate.
- • Virtual calls in hot loops with varying concrete types cost far more than the extra indirection alone.
- • Sorting input before a branch-heavy pass can be a net win even counting the sort, on large enough inputs.
- • Make the branch predictable: sort or partition the data so outcomes come in runs rather than at random.
- • Hoist invariant conditions out of loops so the branch is evaluated once rather than every iteration.
- • Devirtualise hot call sites where possible, so the indirect branch becomes a direct one.
- • Consider removing the branch entirely if it is genuinely unpredictable ([[branchless-code]]) — but measure, because this is not a universal win.
- • Read the branch-misprediction counter and compute misses per instruction; a high rate points directly here.
- • Run the same code on sorted and shuffled versions of the same data — a large gap isolates the branch as the cause.
- • Check whether indirect-branch mispredictions are counted separately on your platform; virtual dispatch shows up there.
- • Sorting to gain predictability costs time and memory, and only pays off when the pass is repeated or the input is large.
- • Devirtualisation reduces flexibility and can require restructuring interfaces.
- • Optimising for a particular predictor is fragile: predictor behaviour is unpublished and changes between generations.
Scope
§224 — what these claims are specific to.
- SIMPLIFIEDThe five-stage model resolves branches at EX, giving a small penalty. Real cores resolve much later and predict much earlier, so real penalties are considerably larger.
- MICROARCH-SPECIFICPipeline depth and predictor quality determine the actual cost. A shallow in-order core pays a few cycles; a deep out-of-order core pays substantially more per misprediction.