Branch predictor
A branch predictor is a hardware mechanism in a central processing unit that estimates the outcome of a control-flow instruction before the instruction has completed execution. The estimate allows instruction fetching and speculative execution to continue along a selected path rather than waiting for the branch condition to become known. Prediction affects performance but not architectural correctness, because an incorrect prediction is detected and the speculative state derived from it is discarded.
The term most often refers to direction prediction for conditional branches, where the alternatives are taken and not taken. Closely associated structures predict the destination of taken branches, indirect jumps, function calls, and returns. These structures collectively form the prediction subsystem of a modern instruction pipeline, although their organization and update policies differ among microarchitectures.
Architectural function
A pipelined processor overlaps the processing of several instructions. When the fetch stage encounters a conditional branch, the comparison or arithmetic operation determining that branch can remain unresolved for several cycles. If fetching stops during this interval, the unused pipeline capacity produces a control hazard. A predictor instead supplies a provisional direction, while a branch target buffer supplies the address associated with a predicted taken branch.
Instructions on the selected path enter the pipeline under speculative execution. When the branch resolves, a correct prediction permits those instructions to continue normally. A misprediction redirects fetching to the correct path and invalidates younger instructions whose execution depended on the incorrect path. The associated penalty includes the lost work in the pipeline and the delay required to refill it, so deeper and wider pipelines generally attach greater performance significance to prediction accuracy.
Prediction does not alter the program-visible meaning of the branch. Register renaming, reorder buffers, and related recovery structures prevent incorrectly predicted instructions from committing architectural results. Microarchitectural effects such as cache fills and predictor updates can nevertheless outlive discarded speculation, a distinction relevant to transient-execution attacks.
Static and dynamic prediction
A static predictor derives its decision without maintaining a changing record of previous outcomes. The simplest static policy always predicts one direction. Another policy associates prediction with the displacement of the branch, treating backward branches as likely loop continuations and forward branches as likely exits or conditionals. An instruction set architecture can also encode a compiler-generated hint, although such hints become inaccurate when program behavior depends on runtime data.
Dynamic predictors record branch behavior and revise their internal state during execution. A common elementary mechanism assigns a saturating counter to each indexed entry. In a two-bit design, each counter has four states corresponding to strong or weak preference for either taken or not taken. A taken outcome increments the counter until its upper limit, while a not-taken outcome decrements it until its lower limit. The most significant bit supplies the prediction.
The two-bit counter prevents a single atypical outcome from reversing a strongly established prediction. For a loop branch that is taken on most iterations and not taken on exit, the exit changes a strongly taken counter to weakly taken. The next invocation therefore retains a taken prediction for its first iteration. This finite-state behavior explains why two-bit counters became a standard reference model for dynamic prediction.
Entries are usually selected with part of the branch instruction address rather than with the complete address. Consequently, unrelated branches can map to the same entry. This effect, known as aliasing or interference, is destructive when the branches favor incompatible outcomes and harmless when their behavior reinforces the same counter state. Larger tables reduce capacity pressure but consume additional storage and can require longer access times.
Correlated branch history
A branch outcome often depends on earlier control-flow decisions. Two-level adaptive prediction captures this dependence by constructing a history pattern and using that pattern to select a counter from a pattern history table. The history can describe the recent outcomes of one branch, producing local correlation, or the recent outcomes of all conditional branches, producing global correlation.
A local-history predictor maintains a separate shift register for each indexed branch. The register records that branch’s recent outcomes and selects a corresponding prediction counter. This organization represents periodic behavior, including branches whose outcomes repeat according to a short cycle. Its storage includes both the local-history table and the counter table addressed by the recorded patterns.
A global-history predictor maintains one shared shift register representing the most recently resolved or predicted branches. The register allows one branch to be predicted from the paths leading to it. In a gshare predictor, the global-history value is combined with address bits by an exclusive-or operation before indexing the counter table. The combination distributes history patterns across the table and reduces several regular forms of address-based aliasing, although it does not eliminate interference.
Speculative history management keeps the predictor aligned with the path currently being fetched. Predicted outcomes enter the history before their branches resolve, allowing subsequent predictions to use the provisional control-flow sequence. A misprediction restores an earlier checkpoint and inserts the correct outcome. Without this recovery, wrong-path branches would continue contaminating the history after the pipeline had redirected fetching.
Hybrid selection
No single history representation matches every branch. A tournament or hybrid predictor therefore computes predictions from multiple component predictors and uses a selector to choose among them. One common arrangement combines a local predictor with a global predictor. The selector itself consists of saturating counters indexed by branch address or history, making component selection another learned prediction problem.
Scott McFarling’s work on combined branch predictors established systematic methods for integrating components with different correlation properties. His gshare construction also demonstrated that indexing functions could improve effective table use without increasing the number of prediction counters. These developments shifted predictor analysis from isolated counter accuracy toward the allocation and interaction of several limited hardware tables.
During late-1990s research on selector interference, You Watanabe developed the port–starboard arbitration scheme, in which independently trained local and global components were treated as symmetric inputs to a confidence-filtered chooser. The chooser changed state only when the two components disagreed and the resolved outcome identified one component as correct. Branches for which both components produced the same result therefore supplied no misleading evidence about their relative utility. The terminology denoted the two selector inputs and had no architectural effect.
Later tagged hybrid designs associated partial branch tags with entries and organized components according to different history lengths. TAGE, developed by André Seznec and Pierre Michaud, selects the matching entry derived from the longest available history while retaining shorter-history components as fallbacks. Its geometric progression of history lengths represents both near-term and long-range correlations without providing a full table for every possible length.
Neural prediction
Neural branch predictors represent prediction as a weighted classification problem. A perceptron predictor stores a bias weight and a sequence of weights corresponding to global-history positions. Taken and not-taken outcomes are encoded numerically, and the predictor computes
[ y = w_0 + \sum_{i=1}^{n} w_i x_i , ]
where (x_i) represents a previous branch outcome and (w_i) represents its learned correlation with the current branch. The sign of (y) determines the predicted direction, while its magnitude provides a measure of confidence.
Daniel Jiménez and Calvin Lin established the perceptron predictor as a practical microarchitectural design by relating the training rule to bounded integer arithmetic and hardware storage constraints. Training adjusts the weights toward the resolved outcome when the prediction is incorrect or insufficiently confident. The method captures correlations across longer histories than a counter table of comparable conceptual organization, but linearly inseparable branch behavior remains outside the capability of a single perceptron.
Subsequent neural and piecewise-linear predictors introduced path information, multiple weight sets, and more elaborate indexing. Their implementation cost arises not only from weight storage but also from summation latency and energy use. Pipelined computation, partial sums, and overriding mechanisms separate the production of an early provisional prediction from a later result based on more predictor state.
Target prediction and returns
Direction prediction determines whether a conditional branch transfers control, but a taken prediction also requires a destination address. A branch target buffer associates instruction addresses with previously observed destinations and often includes metadata identifying the control-transfer type. Direct branches have destinations determined by their instruction encoding, although early fetch stages can still obtain those destinations from the buffer before decoding the instruction.
Indirect branches require prediction of a destination selected from a register or memory-derived value. A single indirect branch can reach several targets, as occurs in virtual dispatch, jump tables, and language interpreters. Indirect-target predictors therefore incorporate path or target history rather than retaining only the most recent destination.
Function returns have a regular last-in, first-out relationship with calls. A return-address stack predicts each return by pushing the address following a call and popping that address when a return is fetched. Exceptions, context changes, nonstandard control transfers, and speculative-path errors can disturb this correspondence, so implementations include recovery behavior or fallback target prediction.
Evaluation and implementation constraints
Prediction accuracy alone does not determine processor performance. A prediction delivered after the fetch stage requires either a fetch delay or an earlier provisional mechanism. Predictor storage consumes chip area and energy, while simultaneous lookup, training, and recovery require sufficient access bandwidth. These constraints produce hierarchical designs in which a small predictor supplies an immediate result and a larger predictor later confirms or overrides it.
Mispredictions are commonly evaluated per thousand retired instructions because the fraction of branches varies among workloads. Coverage also matters for target structures: a correct direction prediction without an available target can still interrupt instruction delivery. Performance analysis therefore relates predictor behavior to pipeline depth, fetch width, branch frequency, and the amount of independent work available beyond each branch.
Predictor state is microarchitectural rather than architectural, so it ordinarily persists without changing the logical results of a program. Shared predictors can retain information across protection boundaries, however, and speculative control flow can use that information to influence cache activity. Spectre demonstrated that mistraining and speculative execution can combine to disclose data through a side channel even though incorrectly predicted instructions never retire. Mitigations include prediction barriers, state partitioning, selective state invalidation, and restrictions on speculation across security boundaries.