The Program Counter: Deciding What Happens Next
One register holds the address of the next instruction. Incrementing it is trivial; redirecting it is the single most disruptive thing that can happen to a modern CPU, because everything the front end fetched behind the redirect turns out to have been the wrong guess.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
Sequential flow is the easy case
The program counter holds the address of the next instruction to fetch. For straight-line code its behaviour is trivial: fetch the instruction at the current address, advance by the length of that instruction, repeat. On a fixed-length instruction set that advance is a constant; on a variable-length one it depends on what was just decoded, which is one of several reasons variable-length decode is harder.
What makes this the easy case is that the next address is known immediately, so the fetch unit can run ahead without waiting for anything. And it does run ahead — substantially. By the time an instruction executes, the front end has typically already fetched and begun decoding a considerable number of instructions behind it. That lead is what keeps the execution units supplied.
The pipeline view below shows the steady state: each instruction enters fetch one cycle after the last, and the machine sustains one completion per cycle even though each individual instruction takes several cycles end to end. This is the throughput-versus-latency distinction that Pipelining: Throughput Without Making Anything Faster develops and Throughput Improved, Latency Did Not generalises.
| 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|
| add r1, r2, r3 | F | D | E | W | ||
| sub r4, r1, r5 | F | D | E | W | ||
| and r6, r4, r7 | F | D | E | W |
A redirect throws away work that was already done
Now the hard case. A conditional branch's target is not known until its condition has been evaluated — which happens in execute, several cycles after the branch was fetched. But the fetch unit cannot pause for several cycles without emptying the pipeline. So it continues, fetching from *somewhere*, and if that somewhere turns out to be wrong, every instruction fetched since must be discarded.
The trace below shows the shape without prediction: the branch resolves, the two instructions fetched behind it are annulled, and the front end restarts from the correct target. The bubbles are not the machine being slow — they are the machine having done work that turned out not to count. That is the cost that Branch Prediction: Guessing Well Enough to Matter exists to avoid and Misprediction: What a Wrong Guess Costs quantifies.
Deeper pipelines make this worse in a direct and unavoidable way: the more cycles between fetch and resolution, the more speculative work is in flight, and the more there is to throw away. This is one of the real constraints on pipeline depth, and part of why the industry stopped pursuing ever-deeper pipelines in exchange for clock rate (The Clock: Why GHz Is Not Performance).
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|
| cmp / branch | F | D | E | W | |||
| fall-through #1 | F | D | |||||
| fall-through #2 | F | ||||||
| branch target | F | D | E | W |
Why this makes prediction inevitable
Put the two traces together and the conclusion is forced. The fetch unit must keep fetching or the pipeline drains. It cannot know the direction of a conditional branch at fetch time. Therefore it must guess. Prediction is not an optimisation bolted onto an otherwise sensible design — it is the only way a pipelined machine can function at all.
What follows from that is a recurring practical point. The cost of a branch is not the branch instruction, which is cheap. It is the *predictability* of the branch. A branch that always goes the same way costs almost nothing, because the guess is right and no work is discarded. A branch that alternates on unpredictable data costs the full redirect penalty every time it surprises the predictor.
This is why sorted input can make a data-dependent loop dramatically faster than unsorted input while executing exactly the same instructions on exactly the same values — one of the most striking demonstrations in the whole domain, and one that makes no sense at all from a source-level reading. Misprediction: What a Wrong Guess Costs works through that example directly.
- The PC feeds fetch continuously — pausing it drains the pipeline and idles the execution units.
- Conditional targets resolve late, in execute, long after the fetch that needed the answer.
- So the machine guesses, and speculatively fetches down the predicted path.
- A wrong guess discards everything fetched since — the deeper the pipeline, the more is thrown away.
- Branch cost is predictability, not instruction count. The instruction is cheap; the surprise is not.
| Branch behaviour | Predictor outcome | Effective cost |
|---|---|---|
| Always taken (loop back-edge) | Predicted correctly almost every time | Close to free |
| Never taken (error check) | Predicted correctly almost every time | Close to free |
| Regular repeating pattern | Learned by history-based predictors | Low |
| Depends on unpredictable data | Frequently wrong | Roughly the pipeline depth in discarded work, every surprise |
| Same branch, sorted vs unsorted input | Correct vs frequently wrong | Identical instructions, very different runtime |
Key points
- The program counter holds the next instruction address; advancing it is trivial, redirecting it is disruptive.
- The fetch unit runs far ahead of execution, which is what keeps the execution units supplied.
- A conditional branch resolves in execute, several cycles after the fetch that needed its answer.
- A wrong guess discards all speculative work fetched since — deeper pipelines discard more.
- The cost of a branch is its predictability, not its instruction count.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Program counter → fetch unit: the address of the next instruction is supplied every cycle.
- 2Fetch unit → instruction cache: bytes are requested and handed to decode while earlier instructions are still executing.
- 3Branch instruction → execute: the condition is evaluated and the true target becomes known, several cycles after fetch.
- 4Execute → front end: if the prediction was wrong, a redirect signal annuls every instruction fetched since the branch.
- 5Front end → correct target: fetching restarts from the resolved address with an empty pipeline behind it.
- • "Branches are slow." Well-predicted branches are close to free. Mispredicted ones are expensive. The distinction is everything.
- • "Fewer branches means faster code." Only if the removed branches were mispredicting; removing predictable branches often achieves nothing.
- • "The CPU stops at a branch to work out where to go." It does not stop; it guesses and continues, which is why being wrong costs so much.
Consequences, controls and cost
- • Identical instruction sequences run at very different speeds depending on whether their branches are predictable.
- • Deeper pipelines pay a larger penalty per misprediction, which bounds how deep a pipeline is worth making.
- • A tight loop with a well-predicted exit condition costs essentially nothing for the loop control itself.
- • Make branch outcomes predictable where you control the data — sorting or partitioning input can eliminate mispredictions entirely.
- • For genuinely unpredictable conditions on simple bodies, consider branchless formulations ([[branchless-code]]) — measured, not assumed.
- • Hoist loop-invariant conditions out of loops so the branch is evaluated once rather than every iteration.
- • Otherwise leave it to the predictor, which is extremely good on anything with structure.
- • Read branch instruction and branch miss counters; the miss *rate* matters far more than the branch count.
- • Compare the same workload on sorted versus unsorted input — a large gap with identical instruction counts is a prediction effect.
- • Check whether the mispredicting branch is in the hot path before doing anything about it ([[cpu-profiling]]).
- • Sorting input to improve predictability costs time and memory that may exceed the misprediction savings.
- • Branchless rewrites remove the misprediction risk and add unconditional work, which loses when the branch was predictable.
Scope
§224 — what these claims are specific to.
- SIMPLIFIEDA four-stage pipeline used as a teaching device. Real pipelines are considerably deeper, which increases the misprediction penalty proportionally.
- MICROARCH-SPECIFICPipeline depth, redirect latency and predictor quality differ substantially between designs; the penalty magnitude is not portable.