Branch Prediction & Speculation

Hazard Detection followed instructions waiting for operands and resources. A branch creates another kind of wait: the processor may need to choose its next instruction address before the branch condition has been computed. Prediction lets fetch proceed, provided the processor can recover when that choice is wrong.

What is being predicted?

For a conditional branch, direction asks whether it is taken. If taken, fetch also needs the target address. Indirect jumps and returns add target-prediction problems of their own. The replay below isolates conditional direction so each state change is visible; BOOM's branch-prediction overview shows how direction and target machinery fit into a complete front end.

Replay outcomes, one branch at a time

Start with the repeated loop pattern: taken, taken, taken, not taken. Step through the first exit, then inspect the next loop's first outcome. Compare what the one-bit and two-bit predictors remembered.

These are authored outcome sequences, not instructions executed by a CPU simulator. Each branch address has independent predictor state with no table aliasing. The one-bit predictor starts not taken; the two-bit counter starts at 01, weakly not taken. Changing scenarios or resetting clears that learned state.

The replay counts correct predictions and misses over the resolved prefix. An assumed recovery cost multiplies misses by a chosen cycles-per-miss value. It is a separate arithmetic illustration, not measured latency, a pipeline trace or an IPC estimate. Selecting another predictor compares the same prefix.

From fixed guesses to remembered outcomes

Static prediction

A static policy uses a fixed rule rather than learned runtime outcomes. Always-not-taken is the replay's baseline. Backward-taken/forward-not-taken is another rule, motivated by common loop shapes, but code layout and control flow determine when it helps.

Compiler layout decisions and profile feedback can influence the instruction stream presented to hardware. They are not the same mechanism as the predictor remembering each resolved branch.

One bit: remember the last outcome

The one-bit policy predicts the last observed outcome at that branch address, then replaces its bit with the actual outcome. After a taken loop back-edge becomes a not-taken exit, it predicts not taken on the loop's next invocation too. An alternating branch is particularly difficult because the most recent outcome points the wrong way.

In the two-address replay, A is always taken and B always not taken. Keeping a bit per address separates those behaviors; a single bit shared indiscriminately across both addresses would represent a different predictor.

Two bits: retain confidence through one exception

The replay uses a conventional saturating counter:

The counter moves one step toward the observed outcome and stops at either end. From strongly taken, one not-taken exit reduces confidence without changing the next prediction. From a weak state, one contrary outcome can change it immediately.

For the default three repetitions of TTTN, the complete replay records 9 misses for fixed not-taken, 6 for one bit and 4 for two bits. Those are calculated outcomes for the displayed cold states and sequence. Try alternating outcomes: the two-bit counter does not automatically learn alternation, and these initial states make both adaptive policies miss every event.

A counter records bias and confidence. Learning a sequence requires remembering more about its history.

Local history, global history and choosing between them

Local history records recent outcomes of the same branch address. A short history can distinguish positions in a repeating pattern such as TTN. It indexes learned predictions for that context; a two-bit confidence counter alone does not encode the sequence.

Global history records recent outcomes across branches. It can capture correlations between an earlier condition and a later branch. Combining history with the branch address helps separate contexts, although finite tables can still suffer interference.

Tournament predictors combine candidate predictors, such as local and global, with a learned chooser. The chooser learns which candidate works better for a context, particularly when their predictions disagree. MIT's branch-prediction lecture develops these history-based designs and the Alpha 21264 tournament example.

These mechanisms are outside the replay's scope. Its per-address counters have neither a local sequence register nor a shared global history.

TAGE: several useful history lengths

TAGE combines predictor tables associated with geometrically increasing history lengths. Address and history information select entries and tags; a tag match determines whether an entry applies. This supports both short and longer correlations without assigning one history length to every branch. Partial tags reduce interference but do not make collisions impossible. BOOM's TAGE documentation describes its tables, prediction counters and usefulness tracking.

Neural prediction: learn a weighted history

A perceptron predictor forms a weighted sum of encoded history outcomes and a bias, uses its sign to predict direction, and updates weights through training. Jiménez and Lin's original paper explains how this makes longer histories practical, along with the limitations of a linear decision boundary. “Neural” here describes a small prediction mechanism, not a claim that a processor runs a large deep-learning model for every branch.

Prediction becomes speculation

Predicting a direction is useful because the processor can fetch and sometimes execute work on that path before the branch resolves:

1. Predict direction and obtain the next fetch address.
2. Process younger instructions under that unresolved branch.
3. Execute the branch and compare its actual outcome and target with the prediction.
4. Keep valid work, or squash younger wrong-path work and redirect fetch.

Instruction execution is not the same as architectural commit. The reorder-buffer discussion explains how an out-of-order design tracks completion and retires work in order.

Recovery must also repair speculative bookkeeping. BOOM, for example, retains rename snapshots and restores speculative global history after a misprediction; predictor training and speculative history updates occur at different points. These are implementation choices beyond our immediate-update replay. BOOM backing-predictor documentation

A deeper pipeline can increase the work between prediction and resolution, but a miss penalty is not universally equal to pipeline depth. Operand readiness, branch resolution, redirects and useful work already in flight affect the observed cost.

Write and measure branch-sensitive code

Start with the actual input pattern

Consider a threshold test:

for (int i = 0; i < n; ++i) {
    if (data[i] > threshold) {
        process(data[i]);
    }
}

The outcome sequence depends on the data order and threshold. Random-looking outcomes can be difficult for a predictor; long runs may be easier. Sorting merely to improve this pattern adds work and may change required processing order. A short loop also does not imply a fixed predictor failure rate: repeated invocations can reuse learned state.

Indirect calls introduce another question:

result += handlers[type[i]](data[i]);

Here the varying target matters, not just taken versus not taken. The direction-only replay cannot evaluate that behavior.

Let the compiler choose an instruction sequence

A clear selection expression gives the compiler room to use a branch, conditional move or another target-specific sequence:

int max_value(int a, int b) {
    return a > b ? a : b;
}

Source syntax does not guarantee branchless machine code or a speedup. Removing a branch can introduce data dependencies or extra work, so compare generated code and runtime for the intended workload. GCC's optimization documentation describes profile-guided branch probabilities and loop transformations; it also notes that unrolling increases code size and may or may not improve speed.

Measure the complete workload

Linux perf can count events for a command:

perf stat -r 5 -e cycles,instructions,branches,branch-misses ./program

Use representative inputs, record the CPU and compiler settings, and compare elapsed time alongside the counters. The kernel's perf-stat documentation covers repeated measurements and event selection.

For the same measured scope, IPC is instructions divided by cycles; branch-miss rate is branch misses divided by branches. Event availability and interpretation depend on the processor. A lower miss rate alone does not prove a faster program, and aggregate counters do not identify which source branch caused the misses.

The CPU execution branch has now followed capacity, dependencies and control flow. For the separate constraint on how much hardware can run at once, continue to Dennard Scaling and the power wall.

Related concepts