Static Branch Prediction and the Branch Delay Slot

A pipelined fetch unit commits to a next address before a conditional branch resolves, and the recovery logic that fixes a wrong commit is expensive. One family of answers needs no tables, no training, and no recovery at all: make the decision deterministic from the instruction itself, or remove the decision from the pipeline entirely. Both approaches were deployed in shipping instruction sets, and the reasons one survived while the other did not say something about how architectural cost migrates as pipelines deepen.

Direction from the sign of the displacement

The cheapest static predictor is a rule over the branch encoding. Two variants matter.

Always not taken needs no rule at all. The fetch unit increments the program counter and ignores target computation for conditional branches until the condition is known. Forward branches — the shape compilers emit for if statements, error checks, and short-circuit conditions — are usually not taken, so the rule is right more often than a coin flip. Backward branches close loops and are taken on every iteration but the last, so the rule is badly wrong exactly where the time is spent.

Backward taken, forward not taken (BTFN) fixes that by comparing the branch target with the branch’s own address. If the target is lower, predict taken; otherwise predict not taken. The comparison is one subtractor on the already-computed target, and it requires no memory. BTFN captures the dominant pattern in compiled code: loop-closing branches go backward and are taken, and most other conditional branches go forward and are not. The rule is wrong on loop exit, which is one misprediction per loop invocation, and it is wrong on forward branches that are usually taken, which includes the common if (error) goto cleanup; idiom in C.

A variant refines the loop case. Because a loop’s exit branch is mispredicted exactly once per invocation while its body may execute many times, the cost of getting the exit wrong is amortised over the trip count, and short loops amortise poorly. Some designs therefore apply BTFN and accept the loss, while compilers restructure short loops to reduce the trip count’s effect — unrolling, or converting the exit test into a guard branch hoisted out of the loop.

When the compiler knows more than the rule

The rule above is a guess about typical code. The compiler has the actual control-flow graph, so it can do better: it can mark which successor is likely and lay out code so the likely successor is the fall-through path. If the fetch unit predicts not-taken by default, then arranging the hot successor immediately after the branch makes the default correct without any hardware change.

Two sources of likelihood are available to a compiler without running the program. Heuristics derived from the shape of the CFG — a loop header’s back edge is likely taken, a block that ends in a call is likely to be followed by the return, a block whose successor is the function’s exit is unlikely — are cheap, and published evaluations found them competitive with the hardware predictors of their era on standard benchmark suites. Profile data is better: compile once with instrumentation, collect edge counts, then recompile with the layout driven by measured frequencies. The cost is a two-stage build and a representative input set; the benefit is layout matching the workload rather than the average.

The source-level signal is a hint that the compiler propagates into layout and, on some architectures, into a bit in the branch encoding:

/* __builtin_expect tells the compiler which side is hot; it does not
   change semantics, only block ordering and hint bits. */
if (__builtin_expect(err != 0, 0)) {
    handle_error(err);   /* cold: placed out of line */
    return -1;
}
return process(buf);     /* hot: falls through */

The hint is advisory. Nothing in the language requires the compiler to honour it, and nothing in the hardware requires the hardware to believe it. That is the fundamental weakness of static prediction: it is a compile-time judgement about a run-time distribution. A branch that is 90 percent taken under one input is 10 percent taken under another, and the encoding cannot change between the two.

One x86 generation accepted explicit hint prefixes on branch instructions, letting hand-written assembly state the expected direction. Its successors ignored the prefixes entirely, treating them as no-ops, because a dynamic predictor trained on actual behaviour beats a hint written months earlier. Once that happened, the prefixes became a source of code-size bloat with no effect.

Removing the decision instead of predicting it

The delay slot attacks the problem from the other end. If the pipeline cannot know the next address in time, change the contract so that the next address is not in question: the instruction following a branch always executes. This was the architectural choice of MIPS, SPARC, PA-RISC, and SuperH, and it turns a control hazard into a scheduling constraint.

The contract has three consequences. The instruction in the slot executes unconditionally, so it must be valid on both paths. It cannot be another branch in most encodings, because that would reintroduce the hazard one instruction later. And it must not depend on state the branch modifies — in particular it must not read a register written by the branch’s comparison, since that write may or may not be committed. Compilers therefore choose slot contents from three sources, in decreasing order of safety:

1. An instruction from before the branch that is independent of it. This is always safe and often available in the basic block that precedes the branch.
2. An instruction from the taken target that is safe to execute when the branch is not taken. Safe means it does not fault, does not trap, and does not corrupt state that the fall-through path will later read. A load from a valid address whose result is discarded qualifies; a divide that might trap does not.
3. A no-op. Correct, and a wasted issue slot on every branch.

MIPS added a second form, the branch-likely instruction, whose delay slot is annulled — converted to a no-op — when the branch is not taken. This lets the compiler fill the slot from the taken path without worrying about the fall-through path, at the cost of extra encoding and of a slot that is sometimes wasted. SPARC’s manual states the general rule plainly: the instruction after a branch is executed before the branch takes effect, and the delay instruction may not itself be a control transfer.

The benefit is real and measurable in the abstract: the pipeline never stalls for a conditional branch and never needs recovery logic. On a classic five-stage machine with a single delay slot, a well-filled slot means zero branch penalty.

Why the delay slot lost

The scheme is a fixed-size solution to a growing problem. A five-stage pipeline exposes one instruction of branch latency; a delay slot of one instruction covers it. A deeper pipeline exposes three or five instructions, and there is no encoding in which the compiler fills five slots after every branch with useful independent work. Extending the delay to multiple slots makes the architecture’s branch cost scale with pipeline depth, which is the opposite of what a designer wants when increasing depth for frequency.

Compilers also found the slots hard to fill. The independent instruction from before the branch exists only if the scheduler can find one that is not on the branch’s critical path, and register pressure often prevents hoisting it. Measurements published with the MIPS and SPARC designs put the fill rate for useful instructions well below the theoretical maximum, with no-ops common in branch-dense code. Every unfilled slot is an issue slot burned unconditionally.

There is a subtler cost: the delay slot constrains later optimisations. Instruction scheduling, software pipelining, and any transformation that wants to move code across a branch must preserve the slot’s semantics. Removing the branch then requires removing its slot, which is why binary translators and JIT compilers targeting these architectures carry explicit slot-handling code. The architectural commitment outlives the pipeline that motivated it: MIPS binaries with delay slots still run on cores with dynamic predictors that must emulate the slot’s effect.

The successor design keeps the compiler’s knowledge but removes the architectural commitment. A branch hint bit, or a layout convention that the hardware learns to expect, is advisory; a delay slot is mandatory. Modern instruction sets chose advisory, and moved the prediction into hardware that can retrain when the input distribution changes.

What static prediction still does

Static prediction did not disappear; it became the initial condition. A dynamic predictor’s tables start empty at reset, and the first encounter with a branch has no history to consult. The usual choice is to initialise counters to weakly taken or weakly not-taken, which makes the first prediction for a cold branch equivalent to a static rule, and to apply BTFN when a branch is not found in the table at all. For code that executes once — initialisation paths, error handling, cold library entry points — a static rule is the whole of the prediction, and the dynamic machinery never gets enough observations to improve on it.

The two-level designs in two-bit saturating counters are best understood as a way to learn a per-branch static prediction rather than a per-program one. The counter’s steady state is the branch’s typical direction, discovered at run time, which is strictly more information than the compiler had. That table is the subject of two-bit saturating counters, which is where the counters live and where they break.