vault

Branch Prediction

19 min read

Branch Prediction

A pipelined processor fetches the next instruction before the current one finishes, so when a conditional branch enters the pipeline, the hardware does not yet know whether the branch will be taken (PC jumps to a new target) or not taken (PC falls through to the next instruction). Stalling the front end until the branch resolves wastes most of the pipeline; instead, the CPU guesses the direction with a branch predictor, speculatively fetches and decodes down the predicted path, and rolls back the speculative work on a misprediction (Smith 1981; Wikipedia: Branch predictor). Modern predictors achieve 95%+ accuracy on SPEC integer workloads, while the smallest embedded cores often ship with no predictor at all and pay the cycles back with cheaper silicon (Jimenez and Lin 2001; Seznec and Michaud 2006).

Mental Model

Imagine a freeway with two off-ramps. The fetch unit is a fleet of cars that all have to commit to one ramp before the sign explaining which ramp is correct comes into view. If the fleet picks the wrong ramp, every car already past the sign has to back up. A branch predictor is the navigator who, having driven this route many times, takes the bet on which ramp to enter. The bet is paid by every cycle of pipeline depth between the fetch stage (where the bet is placed) and the execute stage (where the bet resolves). On a five-stage in-order pipeline, that is two or three cycles of work to flush on a miss. On a modern out-of-order superscalar with a 15 to 20 stage front end, it is 15 to 20 cycles of front-end work plus all the dependent in-flight uops (Wikipedia: Branch predictor puts modern misprediction delay at 10 to 20 clock cycles).

flowchart LR
  PC["PC: next-instr address"] -->|"index by low PC bits"| BHT["Branch History Table<br/>(2-bit counters)"]
  PC --> BTB["Branch Target Buffer<br/>(target address cache)"]
  BHT -->|"taken / not-taken"| MUX{"select<br/>next PC"}
  BTB -->|"predicted target"| MUX
  FALL["PC + 4"] --> MUX
  MUX --> FETCH["Fetch from predicted PC"]
  FETCH --> DEC["Decode, issue, execute (speculative)"]
  DEC -->|"branch resolved"| RES{"actual ==<br/>prediction?"}
  RES -- "yes" --> COMMIT["Commit; predictor learns hit"]
  RES -- "no" --> FLUSH["Squash speculative uops;<br/>refetch from correct PC;<br/>predictor learns miss"]

The two questions a predictor answers, every cycle. What it shows: direction (taken vs not taken) comes from a Branch History Table indexed by PC bits, while the target address for a taken branch comes from a parallel Branch Target Buffer; the selected next PC drives fetch speculatively, and a downstream mismatch triggers a flush that discards everything fetched along the wrong path. The insight to take: prediction is two independent problems (direction and target), each with its own structure, and a miss on either one costs the same set of squashed pipeline stages.

Why Branches Are Control Hazards

The contract of a sequential program is that instruction i+1 runs after instruction i. The CPU bakes that assumption into the front end: every cycle, fetch loads mem[PC] and increments PC by four (or two for compressed instructions). A conditional branch breaks the assumption. The branch’s condition is computed in the execute stage, but by the time execute resolves the branch, the fetch unit has already pulled the next two or three instructions out of the instruction cache. Those instructions are speculative work: if the branch was actually taken and the next PC should be target, the work the pipeline has already done on PC+4, PC+8, PC+12 was on the wrong path and must be discarded (Wikipedia: Branch describes this as branches “causing stalls in which the pipeline has to be restarted”).

This is the control hazard: the next-PC is data-dependent on a computation that has not finished. The naive fix is to stall the fetch unit on every branch until execute resolves it. On the canonical five-stage RISC pipeline, that is a two-cycle bubble per branch. With roughly one branch every five to seven instructions in typical integer code (Smith 1981 used FORTRAN traces with around 15% to 20% branches), a two-cycle stall on every branch alone pushes CPI from 1.0 to roughly 1.3, a 30% hit. On a deeper pipeline the hit is proportionally worse. Smith’s 1981 paper, the foundational citation for the field, frames the problem precisely: “performance losses due to conditional branch instructions can be minimized by predicting a branch outcome and fetching, decoding, and/or issuing subsequent instructions before the actual outcome is known.”

The misprediction penalty as a function of pipeline depth is the dominant cost equation:

penalty_cycles ≈ depth(fetch → execute)
mispredict_cost_per_instr ≈ branch_frequency × miss_rate × penalty_cycles

For a five-stage pipeline (fetch, decode, execute, memory, writeback), a misprediction costs roughly two or three cycles. For a 20-stage out-of-order pipeline, it costs 15 to 20 cycles of front-end work plus the cost of squashing every uop that the wrong-path instructions issued. The lengthening of pipelines through the late 1990s and 2000s, which sought higher clock frequencies, was the driver behind sophisticated prediction; without 95%+ accuracy, deep pipelines lose every cycle they gain from frequency.

The Two Sub-Problems: Direction and Target

A taken branch needs two predictions. Direction prediction asks, “will this branch be taken or not?” Target prediction asks, “if taken, what is the target address?” For PC-relative direct branches such as RISC-V beq and bne, the target is a constant offset encoded in the instruction, so the decoder can compute it the cycle after fetch; the harder problem is target prediction for indirect branches (jalr, virtual-function dispatch) where the target lives in a register that may not yet be computed, and for returns where the target is the dynamically pushed return address.

The predictor structures split along the same line:

  • Branch History Table (BHT) / Pattern History Table (PHT) answers direction. Indexed by some hash of the PC and (in modern designs) global history, each entry is typically a small counter.
  • Branch Target Buffer (BTB) answers target. A small associative cache of (branch_PC → target_PC) pairs; on a hit during fetch, the BTB provides the predicted target immediately, before decode has even confirmed the instruction is a branch (Wikipedia: Branch target predictor describes the BTB as “fetch[ing] predicted target addresses faster than traditional instruction cache lookups”).
  • Return Address Stack (RAS) specializes target prediction for returns. On a jal ra, function call, the predicted return PC (PC+4) is pushed onto a small hardware stack, typically 4 to 16 entries deep (Wikipedia: Branch predictor cites “4 to 16 entries”); on a ret (in RISC-V, jalr x0, 0(ra)), the top of the RAS supplies the predicted target. The RAS is almost perfect for well-nested call/return code; it fails only on tail calls, longjmp, and deep recursion that overflows the stack.

Static Predictors

The first class of schemes makes the same prediction every time. They cost essentially zero hardware and serve as the floor that any dynamic scheme must beat.

Always-taken and always-not-taken are the simplest. Smith’s “Strategy 1” was always-taken; on his FORTRAN trace mix, accuracy ranged from 60% to over 90% depending on the program (Smith 1981 reported program-sensitive results, with the always-taken success rate “typically over 50%”). Always-not-taken was the implicit policy on early SPARC and MIPS, which did not have prediction hardware at all and just kept fetching sequentially.

Opcode-based (Smith’s Strategy 1a). Different branch instructions are biased differently. Smith found, on the CYBER 170 instruction set, that “branch if negative,” “branch if equal,” and “branch if greater than or equal” were usually taken, while other branches were usually not taken; predicting on that basis raised one benchmark from 65.4% to 98.5% accuracy. This is the foundation of compiler-provided hint bits, which surface in ISAs such as HP PA-RISC and (optionally) PowerPC.

Backwards-Taken Forwards-Not-Taken (BTFNT). The branch’s direction in the binary (does it jump to a lower or higher address?) is a remarkably good proxy for likelihood. Backward branches close loops; loops iterate many times before exiting; therefore backward branches are almost always taken. Forward branches usually skip an if-clause that the common path falls through. Smith’s Strategy 3 codifies this: “Predict that all backward branches (toward lower addresses) will be taken; predict that all forward branches will not be taken.” The scheme reached around 80% accuracy on his traces (per Dan Luu’s reproduction, 1.76 CPI on a model where always-taken gives 2.14 CPI). PowerPC 601 and 603 used BTFNT, and the RISC-V manual recommends that compilers lay out code assuming BTFNT will be the hardware’s default static prediction.

Profile-guided. The compiler runs the program once on a training input, records which way each branch went, and emits hint bits that the predictor consults when no dynamic information is available. This is the bridge between static and dynamic.

Dynamic Predictors: The Smith Counter Lineage

Dynamic prediction looks at runtime history. Smith’s contribution was to formalize that a small saturating counter, indexed by hashed branch PC, captures enough history to beat any static scheme on most code.

One-bit predictor. Keep one bit per branch: 0 means “last time it was not taken, predict not taken”; 1 means the opposite. Smith called this “Strategy 6” with a one-bit count. Accuracy is around 85% on integer workloads (Luu cites 1.57 CPI). The fatal pathology is the loop exit: a for (i=0; i<N; i++) loop has a backward branch that is taken N times and then not taken once. The one-bit predictor mispredicts the not-taken exit; then on the next entry of the loop it mispredicts the first iteration as not-taken, because the last execution flipped the bit. Every loop entry pays two mispredictions.

Two-bit saturating counter. Smith’s “Strategy 7” extends the counter to two (or more) bits, with prediction taken from the sign bit (Smith 1981 writes: “Use strategy 6 with twos complement counts instead of a single bit. Predict that the branch will be taken if the sign bit of the accessed count is 0… Increment the count when a branch is taken; decrement it when a branch is not taken”). The crucial property is that the counter has hysteresis: one wrong prediction does not flip the predicted direction, it only nudges the counter toward the boundary. The four-state finite state machine (Strongly Not Taken, Weakly Not Taken, Weakly Taken, Strongly Taken) is detailed in Two-Bit Saturating Counter. Accuracy lands near 90% (Luu: 1.38 CPI). The Pentium, PowerPC 604, DEC Alpha EV5, and essentially every entry-level dynamic predictor since 1990 use this design.

Smith’s 1981 paper concludes: “Of the feasible strategies, strategy 7 was the most accurate. It also had the advantage of using random access memory rather than associative memory. … At least for the applications studied here, strategy 7 is probably the best choice based on accuracy, cost, and flexibility.” Almost every dynamic predictor since builds on top of it.

Two-Level Adaptive Predictors

By the early 1990s the limits of per-branch counters were clear: a counter records only the bias of one branch in isolation. But branches correlate. A branch testing if (x > 0) is often correlated with a subsequent branch testing if (x > 5). Encoding that correlation needs more state per branch and indexing by some notion of recent history.

Yeh and Patt (Michigan, 1991-92) proposed the two-level adaptive predictor: a Branch History Register (BHR) records the taken/not-taken outcomes of the last n branches as a shift register; the BHR is concatenated with PC bits to index a Pattern History Table (PHT) of 2-bit counters. The same branch PC, executed under different histories, hits different PHT entries, so the predictor can learn that “the third branch in this loop is taken when the previous two branches were taken and not taken otherwise.” Per Luu’s CPI numbers, local two-level reaches 1.23 CPI (94% accuracy); a global-history variant on the Pentium MMX reached 93% with a 4-bit history.

Gshare (McFarling, DEC 1993) is a minor but enormous tweak: instead of concatenating the BHR and PC, XOR them together. The hash distributes branches more uniformly across the PHT and uses the bits more efficiently; gshare on the same hardware budget beats local two-level and became the de facto baseline. The MIPS R12000 and UltraSPARC-III used gshare (Wikipedia: Branch predictor).

Hybrid / tournament predictors run two predictors in parallel (e.g., a global-history gshare alongside a per-branch saturating counter), with a third meta-predictor that learns which of the two has been more accurate for each branch and picks its prediction. The DEC Alpha 21264 famously used a tournament predictor (Kessler 1999), as do IBM POWER4 through POWER7; accuracy on SPEC integer climbs to around 96%.

TAGE and Geometric History

The dominant modern conditional branch predictor family is TAGE (TAgged GEometric history length), introduced by André Seznec and Pierre Michaud at IRISA/INRIA (Seznec and Michaud 2006). The insight is that different branches need different history lengths: a tight loop branch is best predicted from very short global history, while a branch that depends on a function-call pattern far up the call chain needs hundreds of bits of history.

The structure: a base bimodal predictor (PC-indexed 2-bit counters) backed by M tagged tables T1..TM. Each table Ti is indexed using a different history length L(i) drawn from a geometric series, for example {0, 2, 4, 8, 16, 32, 64, 128} (Seznec and Michaud 2006: “as an example on a 8-component predictor, using α = 2 and L(1) = 2 leads to the series {0, 2, 4, 8, 16, 32, 64, 128}”). Each tagged entry holds a (partial) tag for collision detection, a signed 3-bit prediction counter, and a 2-bit useful counter for replacement. On a lookup, all tables are consulted in parallel; the prediction comes from the table with the longest history length that has a tag hit; if no tagged table hits, the base bimodal supplies the prediction.

Allocation policy on a misprediction: try to allocate an entry on a table with longer history than the table that mispredicted, so the predictor progressively learns to use longer history when shorter history was insufficient. Seznec’s L-TAGE submission to the 2007 Championship Branch Prediction was a 256-Kbit 13-component TAGE plus a small loop predictor; it achieved 3.314 mispredictions per kilo-instruction (misp/KI) on the CBP-2 traces (Seznec L-TAGE), at the time the most accurate published predictor at any storage budget. TAGE-derived predictors are reportedly used in production at Intel (Haswell onwards) and elsewhere (Wikipedia: Branch predictor).

Uncertain

Verify: that current Intel cores still use a TAGE-derived predictor in 2026. Reason: vendor microarchitecture documents do not name the predictor algorithm; this is a long-running claim from leaked die photos and microarchitecture analyses, but Intel does not confirm it directly. To resolve: Intel optimization manual, recent uarch papers from Agner Fog or Intel engineering blog.

Perceptron Predictors

The other strand of modern prediction grows from machine learning. Jimenez and Lin (HPCA 2001) showed that a single-layer perceptron, the simplest neural network, can replace the table of saturating counters in a two-level predictor and beat it (Jimenez and Lin 2001).

The mechanics: each static branch is allocated a small vector of signed integer weights w0, w1, ..., wn. The inputs x1..xn are bipolar (+1 for taken, -1 for not taken) drawn from the global branch history register. The prediction is the sign of y = w0 + Σ xi * wi; if y >= 0 predict taken, else predict not taken. Training, on the actual outcome t ∈ {-1, +1}, runs the perceptron rule: if the predictor was wrong, or if |y| <= θ (a threshold), update each weight wi := wi + t*xi. Weights that consistently agree with the outcome grow; weights that disagree shrink. The bias weight w0 learns the unconditional bias of the branch.

The decisive advantage: storage scales linearly with history length, where every PHT-based scheme (gshare, two-level) scales exponentially. A perceptron predictor at a 4 KB budget achieves a 4.6% miss rate on SPEC 2000 integer, a 26% relative improvement over gshare at the same budget (Jimenez and Lin 2001, Section 5.3). The decisive disadvantage: perceptron prediction requires a multi-input adder, which is slow; the original paper devoted Section 6 to “tricks” (carry-save adders, ahead-pipelined prediction) to fit prediction in a single cycle. The limitation is that a perceptron can only learn linearly separable Boolean functions; for non-linearly-separable branches (the XOR-shaped ones) it loses to a PHT, which is why production designs hybridize. The first commercial perceptron predictor shipped in AMD’s Piledriver / Bulldozer microarchitecture; later refinements ship in Zen (Wikipedia: Branch predictor).

The Branch Target Buffer

Direction is half the problem. The other half is supplying the target address fast enough to redirect fetch in the same cycle. The Branch Target Buffer (BTB) is a small, set-associative cache. Each entry holds a tag (a hash of the branch’s PC), the predicted target address, and (often) a hint about the branch type (conditional, unconditional, call, return, indirect). Fetch indexes the BTB with the current PC; on a hit, the BTB supplies the predicted next PC immediately, before the instruction has even been decoded. If the predictor also says “taken,” fetch redirects to the BTB target on the very next cycle, hiding the branch latency entirely.

The BTB is necessary for any non-trivial predictor: even with a perfect direction predictor, if you cannot supply the target in the fetch cycle, you pay a one-cycle bubble for every taken branch. BTB capacity in modern cores is in the thousands of entries; entry size is dominated by the target address (32 to 64 bits). Indirect branches (jalr in RISC-V, virtual-function dispatch in C++, jump tables in switch statements) are uniquely difficult because the target varies between executions of the same branch; specialized indirect-branch predictors (an analogue of TAGE called ITTAGE in Seznec 2006) handle these by indexing the BTB with history bits as well as PC.

The Return Address Stack is the BTB’s specialized cousin for returns. Function calls and returns follow stack discipline (every call has a matching ret), so a hardware stack of pushed return PCs predicts returns essentially perfectly within its depth. The RAS is typically 4 to 16 entries; deeper than that and the program is in pathological recursion.

Pipeline Depth and the Misprediction Penalty

The cost of a single misprediction is roughly the distance, in pipeline stages, from fetch to the point where the branch is resolved. On a five-stage in-order pipeline, the branch executes in stage 3 (EX), so a miss costs the two stages of fetched-but-wrong instructions in IF and ID. Two cycles wasted per miss is a modest tax: a 10% miss rate on a 15% branch frequency costs only 0.15 * 0.10 * 2 = 0.03 cycles per instruction, lifting CPI from 1.0 to 1.03.

On a 20-stage out-of-order pipeline the math inverts. A miss costs 15 to 20 cycles of squashed front-end work plus the cost of resetting the rename map and squashing every dependent uop in the reorder buffer. At the same 10% miss rate and 15% branch frequency, the tax is 0.15 * 0.10 * 18 = 0.27 cycles per instruction, lifting CPI from 1.0 to 1.27, a 27% slowdown. Pushing the miss rate from 10% down to 5% (the gap between gshare and TAGE on many benchmarks) recovers half of that lost performance. That is why every major architecture effort since the Pentium Pro has put substantial silicon into branch prediction.

The asymmetry has a clean diagnostic. If a workload’s CPI is high and the perf counters show high branch-misses, the front end is the bottleneck and a better predictor would help. If branch-misses is low but CPI is still high, the bottleneck is elsewhere (cache misses, dependency chains) and prediction is already doing its job.

What Small Embedded RV32IMC Cores Actually Ship

For the definitely-not-esp32 target (an in-order RV32IMC core on a Tang Nano 20K, roughly 20K LUT4 / 15K flip-flops, ~50 MHz), the realistic predictor budget is “very little.” A 2- to 3-stage pipeline has a misprediction penalty of only one or two cycles, so the payoff from a sophisticated predictor is small in absolute cycles. The silicon cost of a TAGE-class predictor (kilobytes of tagged tables, multi-cycle prediction logic) would dwarf the entire ALU. Most production small RISC-V cores in this class ship with:

  • No predictor. Just assume branches are not taken, let the pipeline pay the bubble on taken branches. SiFive’s E20 / E21 (Bumblebee class, two-stage pipeline) take this approach.
  • Static BTFNT. The decoder inspects the branch offset sign; backward branches predict taken, forward branches predict not taken. Free in hardware; one comparator on the sign bit.
  • Small dynamic 2-bit table. Often 128 to 512 entries of 2-bit counters, indexed by PC bits. Picorv32 and many Cortex-M class cores use this. Even at 512 entries, that is only 1 Kbit of state.
  • A tiny BTB. 4 to 16 entries, single-cycle lookup, only for unconditional jumps to absolute addresses. Returns are often not predicted at all and pay the bubble; the cost is small because most embedded code is shallow.

The ESP32-C3 (ESP32-C3 is the project’s reference target) ships an Espressif-designed RV32IMC core; Espressif does not document the predictor in detail. For comparison, the SiFive E31 (Freedom E310 series) documents a “small dynamic branch predictor” without specifying details, and the open-source VexRiscv configures from “no predictor” through “small BTB + 2-bit BHT” depending on whether the user wants area or IPC.

Uncertain

Verify: the exact predictor used in the ESP32-C3 RV32IMC core. Reason: Espressif’s public TRM does not describe the branch predictor microarchitecture, and the C3 core is a proprietary Espressif design rather than a licensed third-party core. To resolve: ESP32-C3 Technical Reference Manual section on the CPU microarchitecture, or Espressif engineering posts.

For v1.0 of the project, the right call is the same call most cores in this class make: ship a static BTFNT or a 128-entry 2-bit predictor (see Two-Bit Saturating Counter), measure the miss rate in Verilator, and only escalate if the data demands it. Premature predictor sophistication is the classic mistake.

See Also

Graph View

Backlinks