Branch prediction

The pipelining chapter ended with a problem. A conditional branch is only decided in EX, but the fetch stage has to pick the next address every cycle. In the 5-stage pipeline, a wrong guess costs 2 cycles. In a modern core, where 15 to 20 stages separate fetch from branch resolution, it costs about 15 to 20 cycles. And in typical code, a branch shows up every five to seven instructions.

So CPUs don't wait. They predict each branch's outcome and keep fetching down the predicted path. When a guess is right, the branch costs nothing. When it's wrong, the instructions fetched after it are thrown away and fetching restarts at the right address.

Even an unconditional jmp needs prediction. The fetch stage has to choose the next address before the instruction has been decoded, so it doesn't yet know the bytes it just fetched are a jump at all.

Throwing away the wrong path

Instructions fetched after a predicted branch run speculatively: their results must not become permanent until the branch is confirmed. A CPU can either hold new register values in hidden scratch storage and copy them in once the branch is confirmed, or record the old values so it can roll back. Either way it takes a lot of bookkeeping, especially when a second branch is predicted before the first one has been checked. The next chapter, on out-of-order execution and speculation, covers how modern cores do it. This one is about the guessing.

Static prediction

The simplest predictors ignore history and apply a fixed rule:

• Always not taken: keep fetching sequentially. That's what the 5-stage pipeline did.
• Backward taken, forward not taken (BTFN): a branch that jumps backward is probably the bottom of a loop, so guess taken. A branch that jumps forward is often an if that skips rare code, such as error handling, so guess not taken.

Compilers can help by laying out code so that the likely path is the fall-through. In C, __builtin_expect (GCC, Clang) and C++20's [[likely]] / [[unlikely]] say which way a branch usually goes, and profile-guided optimization measures it on a real run. x86 once had branch-hint prefixes, but most cores have ignored them for years. Layout is what matters.

The demo below runs two nested loops: an inner loop of 5 iterations, run 10 times. It then replays all 60 conditional branches through the predictor you pick:

Always not taken misses nearly every branch, because both loops branch backward almost every time. Switch to backward taken: only the loop exits are wrong now, 11 in all — 10 inner exits and one outer.

Dynamic prediction: remember what happened

A dynamic predictor keeps a small table, indexed by the branch's address, recording how each branch behaved. It's organized like a cache: the low bits of the address select an entry, and two branches whose addresses share those bits can collide.

One bit: "same as last time"

The simplest table stores one bit per branch: taken or not, last time. Select 1-bit in the demo above: 20 mispredictions, more than the static rule.

Look at the inner jl in the per-branch table. Each time the inner loop runs, the predictor misses twice: once at the exit (it expected taken), and again at the first iteration of the next run, because the exit left its bit set to "not taken". A loop inside another loop pays that double price every time.

Two bits: a second chance

The fix is to change the prediction only after two wrong guesses in a row. The usual design is a 2-bit saturating counter per branch, with four states:

A taken branch counts up, a not-taken one counts down, stopping at 0 and 3. A single loop exit only moves the counter from strongly to weakly taken, so the next run of the loop is still predicted correctly. Select 2-bit: 11 mispredictions, just the exits.

Tanenbaum describes the same idea as a four-state machine that keeps "what the branch should do" and "what it did last time". The saturating counter is the version most designs use, and it behaves the same on loops.

When history matters: correlation

A per-branch counter only knows how often a branch is taken. Some branches follow a pattern instead. This loop tests whether i is even, so its jz alternates between taken and not taken:

With 2-bit, the jz is wrong all 32 times. The counter just bounces between weakly not taken and weakly taken, a step behind at every turn. 1-bit does no better.

Select global history. This predictor keeps a shift register of the last 8 outcomes of all branches, and uses it together with the branch address to choose a 2-bit counter. The same jz now gets its own counter for "after an odd iteration" and another for "after an even one". Once each counter has been trained, the jz stops missing: a few misses while it learns, then none. The price is training: every new history pattern starts from scratch, so on short runs a history predictor can do worse than a plain 2-bit counter. Try it on the nested loops above: 13 misses instead of 11.

History also captures correlation between branches. If one if tests x > 0 and a later one tests x > 5, the outcome of the first says a lot about the second. Two-level predictors like this one, and their many descendants, are the heart of every modern branch predictor.

Modern predictors

Current cores combine several ideas:

• TAGE-style predictors keep several tables that use histories of different lengths, from a few branches to hundreds, and trust the longest history that matches. Perceptron predictors learn a weight for each bit of history. AMD has said its Zen cores use both kinds. On typical code, accuracy is well above 95%.
• A branch target buffer (BTB) maps a branch's address to its target, so the fetch stage can redirect in the very cycle it fetches the branch, before decode even knows it's a branch.
• A return address stack predicts ret: every call pushes its return address onto a small hardware stack, and every ret pops one. It's almost always right, unless the software stack was tampered with.
• Indirect branch predictors guess the target of jmp rax or call [rax+8], which come from switch jump tables and virtual method calls, using the address plus history.

The predictor is shared hardware state, and that has security consequences. Spectre variant 2 (2018) showed that one program could train the predictor to make another program speculatively jump to code of the attacker's choosing. Mitigations include IBPB, a new control that flushes predictor state when switching between programs, added through microcode updates, and retpolines: compiler-generated sequences that replace indirect jumps with a call/ret trick the indirect predictor can't be steered through.

Data that can't be predicted

Some branches depend on data that is effectively random, and no predictor can beat a coin toss on them. This loop generates pseudo-random numbers (xorshift) and counts the odd ones:

Try every predictor: the jz stays wrong about half the time, whatever you pick. Global history even does worse, on the jz and on the loop's jl, because the random outcomes fill its history with noise. At 15 cycles per miss, that one branch costs hundreds of cycles.

The fix is to remove the branch. x86 has conditional moves (cmovcc) and conditional sets (setcc), which compute a value from the flags with no jump at all:

The only branch left is the loop's own, and it's predictable. Compilers do this rewrite on their own when a branch body is small and the condition looks unpredictable, so when you see cmov or setcc in a disassembly, there was probably an if or a ?: in the source. The same reasoning explains a famous benchmark: summing only the values above a threshold runs several times faster once the array is sorted. The data doesn't change, but the branch becomes predictable — false for the first half, true for the second.

Measuring it

On Linux, perf stat -e branches,branch-misses ./prog counts the branches a real run executed and how many were mispredicted. On most programs the miss rate is a few percent. A few percent of hundreds of millions of branches, at 15 to 20 cycles each, is still a lot of time.

Takeaways

• A pipeline has to choose the next fetch address before a branch is decided, so modern CPUs predict every branch and roll back when they're wrong. A miss costs roughly the pipeline depth: 15–20 cycles today.
• Static rules (backward taken, forward not taken) and compiler layout get the easy cases right.
• 1-bit predictors miss twice per loop; 2-bit saturating counters miss once.
• Global history predictors learn patterns and correlations between branches. TAGE and perceptron predictors are their modern form.
• The BTB, return address stack and indirect predictors predict where a branch goes, not just whether it's taken.
• Unpredictable data defeats every predictor. cmov/setcc remove the branch instead, and predictor sharing is what Spectre v2 exploits.