Branch Prediction Basics

A deep, wide, out-of-order pipeline has a terrible enemy: the branch. When the machine meets if (x < 10), it does not yet know whether execution goes down the "then" path or the "else" path — the condition may depend on a value still crawling back from memory. But the front end can't just wait: a modern pipeline is fifteen-plus stages deep and fetches several instructions per cycle, so stalling until the branch resolves would leave dozens of instruction slots empty. That is the control hazard, and it is expensive.

So the processor does something audacious: it guesses. It predicts which way the branch will go and charges ahead fetching and executing down the predicted path, speculatively. If the guess is right — and modern predictors are right well over 95\% of the time — the branch cost is essentially zero. If it's wrong, the machine must flush the wrongly-fetched instructions and restart, paying the misprediction penalty. Branch prediction is the art of guessing right, and it is one of the highest-leverage ideas in the whole machine.

Static prediction: guess without learning

The simplest predictors don't learn at all. Static prediction makes the same guess every time, decided at compile time or by a fixed rule:

Static scheme	Rule	Typical accuracy
Predict not-taken	always assume the branch falls through	~50–60%
Predict taken	always assume the branch jumps	~60–70%
BTFN (backward-taken, forward-not)	loops branch backward and usually repeat, so predict backward branches taken	~65–80%

BTFN is clever — the branch at the bottom of a loop jumps backward and is taken on every iteration but the last, so "backward = taken" is right most of the time. But static schemes can't adapt to a branch that changes its mind. For that we need to remember history.

The 1-bit predictor and its flaw

The simplest dynamic predictor keeps a single bit per branch: "last time, was it taken?" Predict the same as last time; when the branch resolves, update the bit. This is a branch history table (BHT) — a small array of counters indexed by the branch's address. A 1-bit predictor tracks a loop beautifully in the steady state… until you notice it mispredicts twice per loop. Consider a loop that runs 10 times:

iterations : T T T T T T T T T N (taken 9 times, then not-taken to exit) 1-bit pred : ? T T T T T T T T T <- wrong on the FINAL N (predicts T) next entry : the exit flips the bit to N... ...so on RE-ENTRY the first iteration is predicted N and is WRONG too.

One bit remembers only the single most recent outcome, so a lone exception (the loop-exit) flips it, and then the next entry pays for that flip. Two mispredicts every time the loop runs. We want a predictor with a little inertia — one that ignores a single anomaly.

The 2-bit saturating counter

The fix is a 2-bit saturating counter: a small state machine with four states — Strongly Not-taken (00), Weakly Not-taken (01), Weakly Taken (10), Strongly Taken (11). Each taken outcome nudges the counter up (saturating at 11); each not-taken nudges it down (saturating at 00). The prediction is just the top bit: states 10 and 11 predict taken, states 00 and 01 predict not-taken. The word saturating means it never wraps past the ends — 11 stays 11 on another taken.

The genius is the two "weak" middle states acting as a buffer. A branch sitting in Strongly Taken (11) that hits one surprise not-taken drops only to Weakly Taken (10) — still predicting taken. It takes two consecutive not-takens to actually flip the prediction. So a single anomaly (like a loop exit) is absorbed without changing the guess for the next iteration.

Why two bits tolerate the loop exit

Rerun the 10-iteration loop with a 2-bit counter starting in Strongly Taken (11):

// 2-bit saturating counter. State 0..3; predict TAKEN when state >= 2 (top bit set). function predict(state: number): boolean { return state >= 2; } function update(state: number, taken: boolean): number { return taken ? Math.min(3, state + 1) : Math.max(0, state - 1); } const names = ["00 StrongN", "01 WeakN", "10 WeakT", "11 StrongT"]; // A loop body: taken 9 times, then not-taken once to exit; run the loop 3 times. const oneRun: boolean[] = [true, true, true, true, true, true, true, true, true, false]; const pattern = [...oneRun, ...oneRun, ...oneRun]; let state = 3; // start Strongly Taken let hits = 0; for (const actual of pattern) { const guess = predict(state); if (guess === actual) hits++; state = update(state, actual); } const acc = (100 * hits / pattern.length).toFixed(1); console.log(`2-bit counter: ${hits}/${pattern.length} correct = ${acc}%`); console.log("Only the loop-EXIT is mispredicted each run -> ~1 miss per 10, not 2.");

The 2-bit counter mispredicts only the exit of each loop pass (one miss per ten), where the 1-bit version missed twice. On a loop that iterates many times, a 2-bit predictor approaches near-perfect accuracy. This tiny FSM, replicated thousands of times in a table, was the workhorse of 1990s branch prediction and is still the building block inside fancier predictors.

four states; taken increments (saturating at 11), not-taken decrements (saturating at 00);
the prediction is the high bit: states 10/11 predict taken, 00/01 predict not-taken;
it takes two opposite outcomes in a row to flip the prediction, so a single anomaly (e.g. a loop exit) is tolerated;
a table of these counters indexed by branch address is a branch history table (BHT).

The BHT is a fixed-size array, so the low bits of the branch's address pick the entry — and two different branches whose addresses share those low bits land on the same counter. This is aliasing (or interference): the two branches stomp on each other's history, and if they behave differently, both suffer. Bigger tables reduce it; hashing the address in more cleverly reduces it more. Aliasing is a recurring headache that the advanced predictors spend real effort fighting — some, like gshare, even mix in global history to spread colliding branches apart.

A branch predictor as described answers only "taken or not-taken?" — a single bit of direction. But to actually fetch down the taken path, the front end also needs the target address, and it needs it in the same cycle, before the branch has even been decoded. That's a separate structure — the branch target buffer (BTB), a cache from branch address to predicted target — covered in the next lesson. Don't conflate them: direction prediction (this lesson) and target prediction (the BTB) are two different jobs the front end must do at once.

Measuring what a predictor is worth

Accuracy isn't a vanity metric — it feeds straight into performance. If a branch is mispredicted with probability m and each misprediction costs c flushed cycles, and branches are a fraction b of all instructions, the added CPI is

\Delta\text{CPI} \;=\; b \times m \times c.

With b = 0.2 (a fifth of instructions are branches), c = 15 cycles, moving from m = 0.10 to m = 0.02 cuts \Delta\text{CPI} from 0.30 to 0.06 — a huge win on a machine whose ideal CPI is well below 1. This is exactly why chip designers pour so much silicon into the predictor, and why the next lesson chases the last few percent of accuracy so hard.