Two-Bit Saturating Counters and the Bimodal Predictor

The simplest table that learns is one bit per branch: remember whether the branch was taken last time and predict the same again. It works until a loop’s exit, where the pattern is one not-taken after many taken. A one-bit predictor mispredicts the exit and then mispredicts again on re-entry, because the single bit was flipped by the exit. Two bits fix that by adding hysteresis, and the resulting table — the bimodal or “per-address” predictor — has been in essentially every processor since the mid-1990s. It is also the fallback path of every more elaborate scheme built on top of it.

Why one bit is not enough

A loop with trip count $n$ executes its back edge $n-1$ times taken and once not taken. A one-bit predictor settles on taken. On the exit it mispredicts once, flipping the bit to not-taken. On the next invocation of the loop, the first back-edge execution is predicted not-taken and mispredicts again, flipping back. So the cost is two mispredictions per invocation, not one.

Two bits, arranged as a saturating up/down counter, require two consecutive contrary outcomes to change the prediction. Encoding taken as the upper two states:

State	Meaning	Prediction
00	strongly not taken	not taken
01	weakly not taken	not taken
10	weakly taken	taken
11	strongly taken	taken

A loop’s back edge drives the counter to 11 and holds it there. The exit takes it to 10 — prediction still taken, so the exit is still mispredicted, but only once. Re-entry drives it back to 11 on the first taken outcome, so no second misprediction occurs. The loop now costs one misprediction per invocation, which is the theoretical minimum for a predictor that must guess before the condition is known.

The same hysteresis helps branches that alternate slowly or that are taken with probability near one half but in runs. A counter near the middle behaves like a majority filter over the recent past, while a saturated counter resists a single outlier.

The table and its index

The table is an array of two-bit counters, addressed by some function of the branch’s program counter. The standard construction drops the low bits of the PC, because instructions are aligned: on a machine with 4-byte instructions, bits 1:0 are always zero and carry no information. So the index is typically PC[k:k+11] for a 2K-entry table, where k is the alignment shift. The high bits of the index come from the PC, which means the table is indexed by address, not by branch identity: two different branches whose addresses agree in the selected bits share a counter.

A direct-mapped table of $2^n$ entries costs $2^{n+1}$ bits, plus the read and write ports. A 4K-entry table with two-bit counters is 8 Kbit — a small fraction of a modern core’s area — and fits in a single-cycle access alongside the fetch stage. That cheapness is why the design persisted: it can be consulted at the same time the instruction cache is read, so a prediction is available with no added latency.

The update happens at resolution. The counter is incremented on a taken outcome and decremented on a not-taken outcome, saturating at 11 and 00. Some designs use a different update rule — for example, incrementing only on taken and decrementing only on not-taken by two — but the saturating increment/decrement is the standard.

A predictor that can be simulated in a dozen lines

The mechanism is small enough to state exactly. The following is a complete bimodal predictor over a trace of (address, taken) pairs, including the alignment shift:

class Bimodal:
    def __init__(self, bits=12, shift=2):
        self.size = 1 << bits
        self.mask = self.size - 1
        self.shift = shift
        # 2 = weakly taken, 3 = strongly taken; start weakly taken
        self.table = [2] * self.size

    def index(self, pc):
        return (pc >> self.shift) & self.mask

    def predict(self, pc):
        return self.table[self.index(pc)] >= 2

    def update(self, pc, taken):
        i = self.index(pc)
        c = self.table[i]
        if taken:
            self.table[i] = min(c + 1, 3)
        else:
            self.table[i] = max(c - 1, 0)

The initial value matters. Starting at 2 (weakly taken) makes cold branches predict taken, which matches loop back edges and is a better default than not-taken for the branches that dominate execution time. Starting at 1 would make cold branches predict not-taken, the static always-not-taken rule in disguise.

Where the bimodal table breaks

Three failure modes account for most of the gap between a bimodal predictor and a good one.

Aliasing. Because the index is a hash of the PC, distinct branches collide. A hot loop’s counter can be overwritten by a cold branch that happens to map to the same entry, and the interference is invisible to software. With $2^{12}$ entries and a large binary, collisions are rare per branch but not rare in aggregate; the effect is worse in code with many branches in a small address range, such as a switch statement compiled to a jump table followed by many small cases. Aliasing is the reason predictors grew history-based indexing: mixing branch history into the index separates a branch’s different history patterns into different entries, so an accidental collision between unrelated branches depends on the full combined key rather than the address alone.

Correlated branches. A branch’s outcome often depends on an earlier branch. The canonical case is two tests of the same condition — if (x) ... if (x) ... where the compiler could not merge them, or a loop whose trip count determines whether an inner branch is taken. The bimodal table sees only the branch’s own history, so it cannot use the earlier outcome. Global-history predictors, described in global history and gshare indexing, fix precisely this.

Short loops and long loops. A two-bit counter predicts a loop exit perfectly for a trip count of one and poorly for a trip count that varies. For a loop that iterates exactly $n$ times with a constant $n$, the outcome pattern is $n-1$ taken then one not taken — periodic, and a plain counter cannot represent a period longer than its hysteresis. Loop-specific predictors count iterations explicitly for this reason. The general statement: the bimodal counter is a two-state automaton, and any pattern needing more states is invisible to it.

There is also a fourth, less discussed failure: a branch whose behaviour depends on data that changes between phases of the program. A counter trained during one phase is wrong at the start of the next, and the two-bit hysteresis means it takes two contrary outcomes to flip. The cost is small — two mispredictions per phase change — but it is the reason predictors that adapt quickly (and forget quickly) matter for workloads with distinct phases.

Reading before knowing, writing after

A predictor is consulted for a branch that has been fetched, but updated when a branch resolves, and those are different points in time. In between, the same branch may be fetched again — a loop body re-enters the branch every iteration — so a design must decide whether to update the counter speculatively at fetch or only at retirement.

Updating at resolution is correct by construction: the outcome is known, so the counter cannot be polluted by a wrong-path execution. It also means that within a single loop, every iteration after the first is predicted from a counter that has not yet seen the previous iteration’s outcome. For a short loop the counter lags the pattern by one or more iterations, which is exactly the case where the hysteresis is least able to help. Some designs speculatively update at fetch — predicting taken and immediately moving the counter toward taken — and undo the update if the branch resolves the other way. The undo requires a saved copy of the counter, so speculative update is only used where the saved state is cheap, typically in the small loop counters rather than in the main table.

The same timing asymmetry explains why a branch that is mispredicted twice in a row is worse than two independent mispredictions: the first wrong update moves the counter, and the second outcome moves it back, so the predictor spends the interval in the wrong half of the state space. Designs that update on resolution and predict from a stale counter are trading a small systematic lag for immunity to wrong-path pollution.

Table size, warm-up, and the cost of being wrong about capacity

Doubling the table halves the collision rate for a fixed set of branches. The curve flattens: going from 1K to 4K entries helps substantially, 4K to 16K helps modestly, and beyond a point the remaining mispredictions are dominated by correlation and not by aliasing. This is why the literature’s progression went from bigger bimodal tables to history-based indexing rather than to ever-larger direct-mapped arrays.

Warm-up is the other cost. A cold table has no information, and every branch costs a misprediction on first encounter (and, with two-bit counters, potentially a second if the initial state disagrees). For a short-running process — a command-line tool, a script interpreter start-up — the table may never reach steady state, so the predictor’s benefit is limited by how many times each branch executes. This is a structural property: prediction improves with repetition, and repetition is exactly what a long-running workload provides and a short one does not.

The base of a hierarchy

Almost every subsequent design keeps a bimodal table and consults it when its own structure has no useful entry. The reason is that the bimodal table is the cheapest predictor with no failure mode worse than “mediocre”: it never produces a systematically wrong prediction for a branch it has seen enough times, and its storage is proportional to the code’s branch count rather than to any history length. Tournament predictors use it as one of two competing components and pick whichever is right more often, as described in aliasing, tournaments, and predictor selection. A higher layer replaces the PC-only index with one that includes recent branch outcomes.