Control Hazards: What a Branch Costs Before It Resolves

The branch is the instruction whose effect is not known until the machine has already fetched past it. In a five-stage pipeline the condition is computed in EX, which means two younger instructions have already entered the pipeline by the time the outcome is available. If the branch is taken, those two instructions are wrong and must be discarded. The penalty is not a property of the branch itself but of how many instructions the front end managed to fetch ahead, which is why the same branch costs two cycles in a classic five-stage machine and a dozen or more in a deeply pipelined one.

The penalty is the number of speculative fetches

Trace a taken branch through the five stages:

         cycle 1  2  3  4  5  6  7
beq      IF      ID EX MEM WB
(target)         IF ID EX  MEM WB
(next+1)            IF ID  -- discarded --
(next+2)               IF  -- discarded --

The branch resolves at the end of EX in cycle 3. At that point the two instructions behind it have been fetched and one of them has been decoded. Both are invalid because the PC should have gone to the target. The target’s fetch begins in cycle 4, so the pipeline has two bubbles, and the taken branch costs three cycles of front-end occupancy instead of one.

The count is structural. If the branch condition is computed in stage k of an n-stage pipeline, the number of wrong-path instructions already in flight is k - 1, and the penalty is that many cycles, assuming the front end can restart the fetch in the cycle after resolution. A pipeline that computes the condition later, because the comparison needs the ALU or because the flags are produced by an earlier instruction, pays correspondingly more.

Two design levers exist, and they act on different terms. Resolving the branch earlier reduces k - 1: dedicated branch comparators in ID, or even in a pre-decode stage, cut the wrong-path instructions to one or zero. Predicting the direction changes the probability that the penalty is paid at all. Neither eliminates the cost of a mispredicted branch, which is why both are used together and why the two mechanisms are often described as if they were one.

Why predicting direction is not the same as predicting the target

A branch has two things to get right: whether it is taken, and where it goes. The first is a direction prediction, learned from history. The second is a target address, which for a PC-relative branch is computable from the instruction word once the immediate is extracted and the PC is known.

Direction is the harder half. A conditional branch that alternates with a loop counter has a pattern that a two-bit counter predicts badly and a history-based predictor predicts well; a branch whose outcome depends on data has no pattern at all and caps the achievable accuracy. The theoretical limit for a predictor that sees only the branch’s own past outcomes is set by the conditional entropy of the outcome sequence, and real predictors with global history do better than that limit by exploiting correlation between branches.

Target prediction is a table lookup. A branch target buffer indexed by the branch’s address returns the last target; if the entry is present and the prediction is taken, the front end redirects to that address without waiting for the target computation. This is what makes a predicted-taken branch cost zero in the steady state. It also introduces the failure mode where the direction is right and the target is wrong, which costs the full penalty plus the redirect.

The interaction with the pipeline is the important part for this cluster. Once the front end is redirecting on a prediction rather than on a computed result, the pipeline is executing instructions whose architectural effect is provisional. Nothing may become permanent until the branch resolves, which forces the machine to keep the speculative state separable. That is the subject of precise exceptions and pipeline restart, and the recovery machinery is the same machinery, applied to a different trigger.

The three ways to pay for a branch

There are exactly three ways to handle a conditional branch, and they differ in who pays.

Stall until resolution. Fetch stops at the branch, the pipeline drains to the point where the condition is known, then refills from the correct address. The penalty is k cycles for every branch, taken or not. This is simple and needs no recovery state, and it is what a machine without prediction does. It also means branch density directly divides throughput: one branch per ten instructions with a three-cycle penalty gives a CPI of 1.3 before any other hazard.

Predict and recover. Fetch continues down the predicted path; on a mismatch the wrong-path instructions are squashed and the front end restarts. The penalty is paid only on mispredictions, so the average cost is the misprediction rate times the penalty. A predictor at 90 percent accuracy on a three-cycle penalty yields 0.3 cycles per branch, which is an order of magnitude better than stalling and is why prediction is universal.

Delay the effect. Give the branch a slot that executes regardless of outcome, so the instruction behind it is useful either way. This is the delay-slot approach, and it moves the problem into the instruction set: see delay slots and static scheduling. The hardware cost is zero and the software cost is that every branch in every program must fill the slot correctly.

The three are not exclusive. A machine may predict and also expose one delay slot, filling it speculatively from the predicted path and squashing on a mismatch.

Misprediction cost in a deeper machine

The penalty scales with the number of stages between fetch and resolution, and that number grows for reasons unrelated to branches. Deeper pipelines need more stages to resolve a condition because the ALU result comes later relative to the fetch, and wider machines fetch more instructions per cycle, so each wrong-path cycle discards more work. A machine that fetches four instructions per cycle and resolves branches six cycles after fetch throws away up to 24 instruction slots on a misprediction.

That product, not the branch count, is what makes prediction accuracy a first-order design constraint in wide machines. It is also why the predictor’s own latency matters: if the prediction takes three cycles to produce, the front end has already fetched three cycles of the wrong path before the prediction arrives, and the effective penalty includes the predictor’s latency. Predictors are therefore built to be read in the same cycle as the fetch, with the branch address available from the fetch stage itself.

/* A two-bit saturating counter, the smallest predictor that has hysteresis.
   States: 0 strongly not-taken, 1 weakly not-taken,
           2 weakly taken,        3 strongly taken. */
struct bht_entry { unsigned counter : 2; };

int predict(const struct bht_entry *e) { return e->counter >= 2; }

void update(struct bht_entry *e, int taken)
{
    if (taken && e->counter < 3) e->counter++;
    if (!taken && e->counter > 0) e->counter--;
}

The hysteresis is the point: a single anomalous outcome does not flip the prediction, so a loop that iterates many times and exits once is predicted taken on every iteration including the last few, and the exit costs one misprediction rather than one per iteration. The counter width trades responsiveness against stability, and a two-bit counter is the usual compromise.

The residual cost that prediction cannot remove

Even a perfect direction predictor does not make branches free. The fetch redirect itself takes a cycle in most front ends, the target must be available, and the branch’s own resolution still consumes an execution slot. A machine that resolves one branch per cycle caps its branch throughput at one per cycle regardless of accuracy, which matters for code with a branch every few instructions.

There is also the case where the prediction is correct and the penalty is still paid: a branch whose target is not in the target buffer, or whose direction is predicted correctly but whose target address was never recorded. The first occurrence of every branch pays. In a program with many distinct branches executed once each, the predictor’s tables are cold and the effective accuracy is far below the steady-state figure.

Finally, the recovery path itself has a cost that is easy to overlook. Squashing wrong-path instructions means clearing valid bits across pipeline registers, restoring the PC, and, in a machine with speculation state, rolling back any renamed registers or store buffer entries allocated on the wrong path. The cycles spent doing that are not overlapped with useful work, and in a wide machine they can exceed the fetch penalty that triggered them.