The Control Hazard and Why Fetch Must Guess the Next Instruction

A five-stage pipeline issues one instruction per cycle because each stage hands its work to the next stage on every tick. That schedule only holds if the instruction behind the current one is already in the fetch stage when the current one moves on. For straight-line code the answer is mechanical: the next instruction begins at the current program counter plus the instruction length. A conditional branch destroys that assumption, and the pipeline has to decide what to fetch before it knows what the branch will do. Everything in this cluster exists to make that guess cheap and to clean up when it is wrong.

The assumption the front end cannot verify

Consider a pipeline that fetches, decodes, executes, accesses memory, and writes back. While instruction i is in execute, the fetch unit is working on i+2. If i is a conditional branch, the condition is computed in execute — two stages after the fetch that already committed to a path. The fetched instructions i+1 and i+2 are only useful if the branch falls through. If it is taken, they are garbage and must be discarded.

The window between fetching a branch and knowing its outcome is the branch resolution latency, and it is a property of the pipeline rather than of the program. In the classic five-stage design the branch is resolved at the end of execute, so two instructions have been fetched on the wrong side of the decision. Add decode-stage resolution — comparators on the register file read ports plus an adder for the target — and the window narrows to one. Deepen the pipeline for frequency and the window widens again: a design with fifteen stages between fetch and execute carries roughly a dozen fetched instructions of exposure per branch.

Two distinct pieces of information are needed to redirect fetch. The direction is whether the branch is taken. The target is the address to fetch next. Direct conditional branches encode the target as an immediate in the instruction word, so the target is available as soon as the instruction is decoded, even though the direction is not. That asymmetry is why real designs treat the two separately: a branch that is predicted taken needs its target in the fetch stage, before any decode has happened, which is the job of the branch target buffer described in the branch target buffer article. Indirect branches — returns, virtual dispatch, jump tables — have no target in the instruction at all; it lives in a register and cannot be known until that register is read.

The arithmetic of getting it wrong

The cost of a misprediction is the resolution latency plus the refill latency: the cycles spent discarding wrong-path work and the cycles spent getting the first correct instruction back into execute. Refill includes an instruction cache access at the new address, which may itself miss.

A useful first-order model treats the pipeline penalty as a fixed number $P$ cycles per misprediction. If a fraction $f_b$ of executed instructions are branches and a fraction $m$ of those are mispredicted, the cycles per instruction contributed by control hazards is

$$ \text{CPI}_{\text{branch}} = f_b \cdot m \cdot P $$

The sensitivity to $P$ is the reason branch prediction became a first-class design problem rather than an optimisation. Take $f_b = 0.2$ — one instruction in five is a branch, which is the right order for compiled integer code — and $m = 0.05$. At $P = 2$, the penalty is 0.02 cycles per instruction, under two percent of a four-cycle baseline. At $P = 15$, the same prediction accuracy costs 0.15 cycles per instruction, which against a four-cycle baseline is a several-percent throughput loss. Improve accuracy from 95 to 99 percent and the penalty drops by a factor of five. This is why predictor research kept going long after predictors were already “good”: at depth, the remaining mispredictions are a large share of the remaining lost cycles.

The same arithmetic makes the alternative look bad. Stalling until the branch resolves costs $f_b \cdot P$ cycles per instruction — the same expression with $m = 1$. At $f_b = 0.2$ and $P = 15$ that is three cycles per instruction, which would erase most of the benefit of building a wide machine in the first place. Waiting is only tolerable when $P$ is small and branches are rare, which is the situation the earliest RISC pipelines were in.

Three ways to avoid waiting, and what each costs

Before dynamic prediction there were three families of answer, and all three survive in modern designs in modified form.

Always fall through. Predict not-taken unconditionally. This costs nothing to implement — the fetch unit simply keeps incrementing the program counter — and it is correct for forward branches used for error checks and wrong for backward branches used for loops. Loops are where the time goes, so this is a poor default on its own, but it is an excellent default when combined with a small table that overrides it, which is exactly what a bimodal predictor is.

Always taken when backward. A purely static rule that needs no state: if the target is below the branch, predict taken. Loops close with a backward branch, and a loop body executes many times per exit. This is the basis of the static schemes discussed in static prediction and branch delay slots.

Expose the delay. Instead of hiding the gap, make it architectural: the instruction after the branch always executes, whether or not the branch is taken. The compiler fills that slot with useful work or a no-op. The pipeline never stalls and never guesses. The cost is instruction encoding space and a permanent constraint on the compiler, and the scheme stops scaling once the pipeline has more than one slot to fill.

Predicate instead of branch. Convert a short forward branch into conditional execution of the following instructions. If the condition is false, the instructions execute but do not commit their results. There is no control transfer at all, so there is no hazard to predict. The cost is that both sides of the condition consume issue slots, which is fine for a two-instruction body and wasteful for a twenty-instruction one.

Every one of these is a trade of one resource against another: fetch bandwidth, encoding space, issue slots, or prediction accuracy. The modern machine uses all of them at once, choosing per branch based on what the compiler and the predictor know.

Why a correctly predicted taken branch still costs a cycle

There is a second, smaller penalty that survives perfect prediction. A fetch unit delivers a block of instructions per cycle — four, five, or six on current wide designs — and that block must be contiguous in memory. When a taken branch sits in the middle of the block, the instructions after it in the block belong to the not-taken path and are useless. The fetch unit must restart at the target on the next cycle, losing the remainder of the current block.

On a machine that fetches, say, 32 bytes per cycle, a taken branch every ten instructions wastes a fraction of a fetch slot each time. The loss is proportional to how far into the block the branch sits. This is the origin of “branch density” as a metric: code with many small taken branches cannot sustain full fetch bandwidth even with a perfect predictor. Compilers mitigate it by aligning loop headers and by arranging hot paths so that branches fall at block boundaries, which is a code-layout problem rather than an architectural one.

Predicted-not-taken branches are free in this respect: the sequential fetch continues through the branch and the block is fully used.

Where the model stops being accurate

The fixed-penalty model above is a planning tool, not a measurement. It assumes the penalty is independent of what else is in flight, and that is false in three ways.

First, a misprediction does not merely cost $P$ cycles; it also occupies the machine with wrong-path work that must be drained. In an out-of-order core with a window of a few hundred micro-operations, wrong-path instructions fill issue slots and consume execution units until they are squashed, so the effective cost depends on how much of the window they occupied. A misprediction detected early is cheaper than one detected late, even at the same pipeline depth.

Second, wrong-path execution touches caches. It fills instruction and data cache lines with data the program does not need, and it can evict lines the correct path does need. The penalty then includes cache misses caused by the mistake, which can be an order of magnitude larger than the pipeline refill. The same mechanism, taken seriously as an attack surface, is the subject of speculative execution and architectural side channels.

Third, the resolution latency is not a constant. It depends on whether the branch’s operands are ready when it reaches the execution unit. A branch whose condition depends on a load that missed in cache resolves late, and the fetch unit has been running on a guess for far longer than the pipeline depth suggests. This is why some designs give branches priority in the scheduler and why “branch resolution latency” in a real machine is a distribution with a long tail rather than a number.

The bet the machine is making

Every cycle the front end issues a fetch request, it is asserting that the program counter it holds is the right one. A branch predictor is a table of past behaviour used to keep that assertion true most of the time, and the rest of the machinery — checkpoints, history registers, squash logic — exists because the assertion is occasionally false. The next question is what the machine can know without any table at all, and what the instruction set can do to make the gap smaller.