Return Address Stacks and the Prediction of Indirect Branches

A conditional branch has one of two targets, and one of them is encoded in the instruction. An indirect branch has arbitrarily many targets, and none of them are in the instruction: the destination is in a register or a memory location. That single difference makes indirect branches the hardest part of the fetch-side prediction problem. A predictor that gets the direction right and the target wrong has achieved nothing, because fetch needs an address. Returns are the most common indirect branches and the most predictable, which is why they get their own dedicated structure rather than sharing the general machinery.

Why the target is not in the instruction

Consider the encodings. A direct conditional branch carries a signed displacement relative to the program counter, so the target is computable in decode with one adder. A direct jump carries a larger displacement or an absolute address in the instruction word. An indirect jump carries neither: the instruction names a register, and the register’s value is determined by whatever executed before it.

The idioms that produce indirect control flow are worth enumerating, because each has a different predictability profile.

Returns. The target is the address after the call. Every invocation of a function has a different return address if the call sites differ, so a per-address target cache stores the wrong answer for any function called from more than one place.

Virtual dispatch and function pointers. The target depends on the object’s dynamic type. In code where the type is stable at a call site, the target is highly predictable; in code that iterates over a heterogeneous collection, it alternates among a small set of targets in a pattern that may be periodic or may not.

Jump tables. A switch compiles to an indexed load from a table of code addresses. The target is a function of the switch value, so the pattern depends on the data distribution. A state machine driven by input bytes produces a target sequence that is a walk over the state graph, which a history-based predictor can learn if the graph is small.

PLT and vDSO stubs. An indirect jump through a table slot that is resolved once and then stable. The target is constant after resolution but may change when a lazy binding completes.

In all of these, the predictor’s problem is not binary. It must produce one address from a set whose size is not bounded by the instruction encoding.

The return address stack

Returns are common — in typical compiled code they are a significant fraction of all branches — and they have a structure the hardware can exploit directly: calls and returns nest. If the fetch unit maintains a stack that mirrors the program’s call stack, a call pushes the return address and a return pops it.

The structure is a small circular buffer with a stack pointer. It is not a memory stack; it holds only addresses, typically 8 to 32 entries on the order of a few bytes each, and it lives in the fetch unit so that a return’s predicted target is available in the same cycle as the fetch. On a call, the fetch unit computes the return address — the address after the call instruction — and pushes it. On a return, it pops and predicts the popped value.

The mechanism is exact as long as the stack’s contents match the program’s actual call nesting. It breaks in four ways.

Depth overflow. A recursion deeper than the stack’s capacity overflows the top. The standard handling is to stop pushing and keep a counter of overflowed entries; on popping, the counter is decremented and the prediction is unavailable, so the return is mispredicted until the nesting unwinds back into the buffer. Because the overflowed entries are the deepest calls, which are usually the hottest in a recursive algorithm, overflow can be costly. Some designs instead predict the oldest entry, which is right for a self-recursive function whose return addresses are identical.

Non-call pushes. A return-address stack assumes every call pushes and every return pops. That assumption fails with setjmp/longjmp, with exceptions that unwind through frames, with tail calls that replace a frame rather than adding one, and with hand-written assembly that manipulates the stack without a matching call. Each of these desynchronises the pointer, and every subsequent return in that thread of control is mispredicted until the pointer happens to realign.

Speculation and the shadow stack. The fetch unit pushes speculatively, before the call is known to be on the correct path. A mispredicted branch between a call and its return means the pushed address was never architecturally pushed. Recovery must restore the stack pointer and the contents to the checkpoint, which is why the return stack is included in the per-checkpoint state described in misprediction recovery. The stack is small enough that saving it per checkpoint is practical — at most a few hundred bytes.

Calls with mismatched returns. A function that returns through a different mechanism than it was called — a thunk that pops its caller’s frame, or a compiler-generated ret after a tail call that reused the frame — breaks the one-to-one correspondence. Compilers that generate tail calls are aware of this and either emit a jump rather than a call-plus-return or ensure the stack discipline is preserved.

The stack also has to handle the case where the return address is not computable at fetch. On a variable-length instruction set, the return address is the address after the call, whose length depends on the encoding; the fetch unit knows the call’s address but not necessarily its length until decode. Designs solve this by computing the push value in decode rather than fetch, accepting that the first return after a call may be predicted late, or by using the length information that the fetch unit already has from the instruction cache’s predecode bits.

Predicting the indirect target from history

For indirect branches that are not returns, the standard structure is a table of (address, target) pairs indexed by the branch address and, in better designs, by the branch history. The simplest version is a target cache: a small direct-mapped array keyed by the branch’s PC that stores the last target. It works for call sites whose target is stable and fails for those that alternate.

The refinement is to store several targets per branch and select among them with history. A two-level scheme keeps a per-branch history of the recent targets and uses it to index a table of targets, so a branch that cycles through three targets in a fixed order can be predicted by remembering which target followed the last occurrence of each history pattern. This is the same idea as gshare (global history and gshare) applied to a multi-valued outcome rather than a binary one, and it faces the same interference problem with a worse multiplier: the outcome alphabet is the number of distinct targets, not two.

A different approach predicts the target by recognising the branch’s shape. For a jump table, the target is base + index * scale, so a predictor that learns the base and scale and observes the index can compute the target rather than memorise it. This is the basis of predictors that store a target and an offset, or that keep a small table of recent targets and a stride between them. It handles jump tables driven by a loop counter well and does nothing for virtual dispatch.

The published designs that matter here use a hybrid: the return stack for returns, a target cache for stable indirects, and a history-indexed multi-target table for the rest, with a confidence mechanism that decides whether to use the prediction or to stall. Stalling until the target is computed is sometimes the right choice: a two-cycle stall is cheaper than a misprediction that costs the pipeline depth plus the wrong-path cache damage, and the confidence mechanism is what makes that choice available.

Call and return prediction as a bandwidth problem

On a wide machine, the fetch unit may need to predict several branches per cycle. A call followed immediately by a return in the same fetch block requires a push and a pop in the same cycle, which a single-ported stack cannot do. Designs handle this with a small amount of replication or by predicting only the first control transfer in a block, as with the branch target buffer (how a branch target buffer delivers the target in the fetch cycle).

The interaction with the branch target buffer is specific: the BTB entry for a return instruction carries a type field, and the fetch unit consults the return stack instead of the stored target when that field says return. Getting this wrong is a classic source of mispredictions in new designs, because the stored target is often right for the first few executions of a function and then wrong once the call site changes. A return stack that is correctly maintained is more accurate than any per-address target cache for returns, which is why the structure has survived from the earliest out-of-order designs to current cores.

The cost is area and complexity for a structure that handles only one instruction type. The benefit is that returns are frequent enough that their misprediction rate dominates the indirect-branch budget in typical integer code, and the stack’s accuracy is close to perfect when its discipline holds. The remaining indirect branches — dispatch, tables, pointers — are rarer but harder, and the research on them continues in the direction of longer target histories and of combining the target prediction with the direction prediction so that a single lookup yields both.