Advanced Branch Prediction

The 2-bit saturating counter looks at one branch in isolation: "how has this branch behaved lately?" That's enough for a loop, but it is blind to a huge source of predictability — branches correlate with each other. How one branch resolves often tells you how the next will. Consider:

if (x < 5) a = ... // branch B1 if (y < 5) b = ... // branch B2 if (x == y) ... // branch B3 -- its outcome is CORRELATED with B1 and B2!

A per-branch 2-bit counter for B3 can't see B1 and B2 at all. The leap in the 1990s — and the reason today's predictors exceed 99\% accuracy — was to predict a branch using the history of recent branches, not just its own. These are correlating or two-level predictors, and they are some of the most elegant machine-learning-in-hardware ever built.

Two levels: history, then a counter

A two-level predictor has, unsurprisingly, two levels. The first level is a history register — a shift register recording the taken/not-taken outcomes of the last k branches (a 1 for taken, 0 for not-taken, shifted in each time). The second level is a table of 2-bit counters, the pattern history table (PHT), indexed by that history pattern. In effect the predictor learns "when the recent history looks like 1011, this branch is usually taken."

The history can be global (one shared register of the last k branches anywhere — captures correlation between branches) or local (a separate history per branch address — captures a single branch's own repeating pattern, like an alternating T,N,T,N). Global history nails the B1/B2/B3 correlation above; local history nails a branch with its own rhythm. Neither wins everywhere — which sets up the tournament idea.

gshare: mixing history and address

A pure global-history index wastes the table — many branches share the same recent history and pile onto the same counters (aliasing again). Scott McFarling's gshare (1993) fixes this with one cheap trick: XOR the global history register with the branch's address and use the result to index the PHT. Now two branches with identical history but different addresses hash to different counters, dramatically reducing interference — for almost no extra hardware. It became the standard baseline for a decade.

// gshare index = (branch PC bits) XOR (global history), masked to the table size. function gshareIndex(pc: number, history: number, indexBits: number): number { const mask = (1 << indexBits) - 1; // e.g. 10 bits -> 1024 entries return (pc ^ history) & mask; } const indexBits = 10; // 1024-entry PHT // Two different branches that happen to share the same recent global history: const historyAB = 0b0110110101; console.log(`branch A @0x40 -> PHT index ${gshareIndex(0x40, historyAB, indexBits)}`); console.log(`branch B @0x7C -> PHT index ${gshareIndex(0x7C, historyAB, indexBits)}`); console.log("Same history, different PC -> different counters -> no aliasing.");

Tournaments: let predictors compete

Since global-history and local-history predictors each win on different branches, why choose? A tournament predictor (pioneered in the Alpha 21264, 1998) runs two predictors in parallel and adds a third small table — the chooser — that learns, per branch, which predictor to trust. The chooser is itself a table of 2-bit counters, updated toward whichever component was right. You get the best of both, dynamically, per branch. This "predict which predictor" idea is the direct ancestor of everything modern.

PredictorIdeaTypical accuracy
Static (BTFN)fixed rule, no learning~65–80%
2-bit bimodalone counter per branch address~85–93%
gshareglobal history XOR PC → PHT~93–96%
Tournamentchooser picks global vs local per branch~96–98%
TAGE (state of the art)many tables, many history lengths, tagged>99%

TAGE: the modern champion

Today's best predictors are variants of TAGE (TAgged GEometric history length, ~2006). The insight: different branches need different amounts of history — some correlate with the last 2 branches, some with the last 80. TAGE keeps several tables indexed with geometrically increasing history lengths (say 4, 8, 16, 32, 64…), each entry tagged so it only answers for the branch it actually learned. For each prediction it uses the match from the table with the longest history that has a confident, tagged hit. TAGE-family predictors reach well past 99\% and dominate every branch-prediction championship — they are what's inside current Intel, AMD, and Apple cores in spirit.

The other half: predicting the target (BTB)

Everything so far predicts direction (taken/not-taken). But the front end also needs the target address to know where to fetch next — and it needs it in the fetch cycle, before the branch is even decoded. The branch target buffer (BTB) is a small cache from branch address → last-seen target address, queried every fetch. For a plain conditional branch the target is fixed, so the BTB nails it. Indirect branches (virtual calls, jump tables, switch) are harder — their target varies — so cores add a specialised indirect predictor and a return address stack (RAS) that pushes on call and pops on return to predict function returns almost perfectly.

Real program branches are wildly non-random. Loop branches are taken hundreds of times then exit once. Error checks (if (ptr == null)) are almost never taken. A branch guarding a rarely-hit case is predictable precisely because it's rare. And correlation means even "data-dependent" branches leak their outcome through the branches before them. A modern TAGE predictor exploiting dozens of history lengths finds structure a human would never spot — which is why "just a coin flip" branches (genuinely random data) are the one case that still defeats prediction, and the reason branchless code and predication exist for those.

A common muddle: thinking a correlating predictor is just "a longer memory of this branch." Local-history prediction is that — a branch's own repeating pattern. But the powerful idea is global correlation: using the outcomes of different, recent branches to predict this one, because control flow ties them together (if (x<5) and if (x==y) share the variable x). If you only ever think about one branch's own history, you miss the entire reason two-level predictors beat the bimodal counter. Global history is the star of the show.

Why the last few percent are worth a fortune

On a wide, deep, speculative core the misprediction penalty is 15–20+ cycles, and a fifth of instructions are branches. Going from 95\% to 99\% accuracy cuts the misprediction rate fivefold (from 1-in-20 to 1-in-100), and the wasted-cycle bill falls with it. That is why a state-of-the-art predictor — TAGE plus a BTB, an indirect predictor, and a return stack — is one of the most valuable square millimetres on a modern chip. It is also what makes deep speculation pay off, and, uncomfortably, what later made speculative side-channel attacks like Spectre possible.