How a Branch Target Buffer Delivers the Target in the Fetch Cycle

A direction predictor answers whether the branch is taken. That answer is useless on its own, because fetch needs an address, and on the cycle the branch is fetched no decoder has yet extracted the displacement from the instruction word. The branch target buffer solves this by caching, per branch, the address the branch went to last time. It is a small associative structure read in the fetch stage, and it makes prediction possible one full pipeline stage earlier than the instruction cache alone allows.

The timing problem the BTB solves

Suppose the fetch unit is delivering one block of instructions per cycle. It needs to know, by the end of the cycle, where the next block starts. Three sources of next address exist: the sequential increment of the current block, a target supplied by a predictor, and a redirect from the execution pipeline.

The sequential increment is free. A redirect from execution arrives late and is the misprediction path. The target from the predictor must arrive in the same cycle as the block it applies to, which means the predictor lookup and the instruction cache lookup happen in parallel, and both must complete within one cycle.

That is a hard constraint on the BTB’s size and associativity: it must be as fast as the instruction cache’s tag access, and it must be addressed by something available at the start of the cycle, which is the current fetch address and nothing else. It cannot be indexed by the branch’s own address, because that address is not known until the fetch block is decoded. So the BTB is indexed by the fetch address and contains entries for branch addresses within that block.

Indexed by fetch address, tagged by branch address

The standard organisation has two parts. The index comes from the fetch address — typically a slice of its low bits — and selects a set. Within the set, each entry holds a tag, the branch’s own address, the predicted target, and some prediction state.

The lookup proceeds as follows. On a fetch at address A, the BTB is read at index A[i:j]. Each candidate entry is compared against A’s tag bits. A match means a branch is predicted to be taken at exactly A — not “somewhere in the block”, but at the block’s first instruction, because that is the only address the lookup knows. A hit yields the target, and the fetch unit redirects to it at the end of the cycle.

This restricts what the BTB can represent: it predicts a taken branch only when the branch is the first instruction of a fetch block. In practice a fetch block on a wide machine spans several instructions, so a taken branch in the middle of the block wastes the rest of the block — the fetch unit redirects at the end of the cycle regardless, and the instructions after the branch in the block are discarded. The fix used by wide designs is to fetch short blocks (fewer instructions per fetch) so that a block rarely contains a branch beyond its first instruction, or to include the branch’s offset within the block in the entry so the fetch unit can truncate the block at the branch.

Some implementations store several targets per entry, one per possible branch position, or use a separate small “branch predictor array” indexed by instruction address that returns the branch’s offset within a block. Both amount to the same thing: enough information for the fetch unit to stop delivering instructions at the branch and start at the target.

Direction and target are stored together

An entry that holds a target for a taken prediction is naturally paired with the direction state for the same branch. Storing them together avoids a second lookup and, more importantly, avoids the inconsistency of a direction predictor saying taken while the BTB has no target — a state that forces the fetch unit to stall or to guess.

A typical entry therefore holds:

Field	Width	Purpose
tag	enough to distinguish branches in the set	identity check
target	address width, or a compressed offset	where to go
direction counter	2 bits	taken/not-taken state
branch type	2 bits	conditional, call, return, indirect
history	varies	for history-based prediction

The type field matters because the BTB serves more than conditional branches. Direct jumps and calls are always taken and need only a target, so they can be predicted with no direction state at all. A return needs the return address stack, not the stored target, because the stored target is from the last execution of that return instruction and is wrong whenever the function is called from a different site. This is why the type field exists and why the return stack (return address stacks and indirect branch prediction) is consulted before the BTB’s stored target.

Allocation, replacement, and the cost of a miss

A BTB miss on a taken branch means the fetch unit cannot redirect. The options are to stall until decode produces the target, or to fall through and accept a misprediction. Falling through is what most designs do for conditional branches, because the displacement is in the instruction word and decode can compute the target one or two cycles later, which is cheaper than a stall.

Allocation happens when a branch resolves. On the first execution of a branch, the BTB is empty at that address; the branch is fetched, decoded, executed, and its taken target computed. The entry is then written with the address, the target, and an initial direction state. If the branch is not taken, some designs allocate an entry anyway (with the target field filled and direction set to not-taken) so that later taken outcomes are cheap; others allocate only on taken, which saves capacity for branches that matter.

The BTB is a cache with all the usual pathologies. Its index is a hash of the fetch address, so two branches at different addresses that map to the same set and share tag bits collide. Because the tag is narrower than a full address — often 8 to 12 bits — a collision produces a false hit: the fetch unit believes a branch exists at address A and redirects to a target belonging to a different branch. The penalty is a full misprediction plus whatever wrong-path work was done. False hits are worse than misses because a miss merely costs latency while a false hit costs correctness of the fetch stream.

Associativity mitigates but does not remove this. A two-way or four-way BTB with LRU replacement keeps the hot branches resident but still produces false hits when a new branch’s tag happens to match a resident entry in the selected set. Wider tags reduce false hits at the cost of storage; the trade is direct and is why tag width in published BTB designs is chosen to make false hits rare rather than impossible.

Keeping the BTB consistent with the instruction stream

The BTB holds addresses derived from instruction words, and instruction words change. Self-modifying code, JIT compilation, and dynamic loading all write new instructions into memory that may already have BTB entries from a previous occupant of that address. An entry pointing at a target that belonged to the old code will send fetch to a stale address.

Instruction cache invalidation is the standard remedy, and it must be extended to the BTB: on a coherence or icache invalidate for a page, the corresponding BTB entries are invalidated too. The architectural requirement appears in the instruction-set manual as a requirement that modification of instruction memory be followed by a synchronisation sequence before the new instructions execute. Architectures specify an instruction that flushes the pipeline and the fetch-side structures, and implementations must make that instruction sufficient, which means flushing the BTB along with the instruction cache.

Incoherence between the BTB and the instruction cache also shows up benignly: a BTB entry can point to a target whose instruction cache line has been evicted. That is not a correctness problem, just a fetch miss, and it is handled by the normal miss path.

Why the BTB is where the pipeline gets complicated

The BTB is the first structure in the front end that must be both fast and correct, and its design pressures propagate in both directions. Making it faster forces smaller tags and fewer ways, which raises false-hit rates. Making it more accurate forces more ways and history fields, which grows it and slows it. Making it cover more branches — including those not at a block boundary — requires extra structures or narrower fetch blocks, which costs fetch bandwidth.

The resolution is usually a hierarchy: a small, fast, level-one BTB consulted every cycle, backed by a larger level-two BTB that catches the misses and is accessed only when the fast one misses. The level-two lookup takes extra cycles and is only tolerable because a BTB miss is already going to cost latency. Hierarchy in the branch predictor proper follows the same pattern, which is why TAGE-style predictors are built from several tables of different lengths rather than one large table.

The recovery path, once a false hit or a misprediction is detected, is the subject of checkpoints and misprediction recovery; the BTB’s role in it is to supply the correct target on the refetch, which it does only if the entry written at resolution is accurate.