Every clock cycle, the front end of a pipelined processor must decide where next to fetch instructions, and it must decide before it knows what it has fetched. By the time the decoder recognizes a branch, the fetch unit has moved on, several cycles and dozens of bytes down the sequential path, and if the branch is taken, all of that work must be discarded. The branch target buffer addresses this problem by remembering, for each fetch address where a taken branch was previously found, what type of branch it is and its previous destination. When a fetch address hits in the BTB, the front end redirects to fetch from the target on the next cycle, without waiting for the branch to be decoded, or even fetched. Intel shipped one in the original Pentium in 1993, where it held up to 256 jump instructions, organized as a four-way set-associative array with 64 entries in each way.1

Modern front ends take the idea further: in a decoupled front end, the branch predictor runs ahead of instruction fetch, walking the BTB to produce a queue of predicted fetch addresses, and the instruction cache is prefetched from that queue2. The BTB thus doubles as a map of the program’s control flow, and the branch predictor doubles as the instruction prefetcher. BTBs have grown accordingly, from a few hundred entries to multilevel structures holding thousands, because large server applications are dominated by front-end stalls, and the BTB’s capacity determines how far ahead the front end can see.

The BTB differs from the TLB and the µop cache (subject of a later article) in that it is allowed to be wrong. Every prediction it supplies is checked when the branch executes, and if the branch was mispredicted, the pipeline is flushed and fetching is restarted at the correct address. An incorrect BTB entry incurs a performance penalty of a couple dozen cycles; it cannot cause incorrect code execution. So the BTB does not need any invalidation machinery, like the TLB. Nothing invalidates the BTB when a process unmaps its code, and for most of its history, nothing flushed the BTB on a context switch. Its tags can be partial (a hash of some of the address bits, rather than all of them), because two branches that alias to the same entry will merely mispredict each other now and then. Each of those efficiencies saves area and power, and each is defensible on performance grounds alone, since aliasing is rare and doesn’t cause incorrect behavior.

Those optimizations also mean that one program’s branches can influence another program’s predictions, a property exploited in January 2018 by Spectre. An attacker executes indirect branches at addresses chosen to alias, in the BTB, with an indirect branch in the victim (a kernel, a hypervisor, or another process), and trains them to jump to an address of the attacker’s choosing. When the victim reaches its own branch, the BTB supplies the attacker’s target; the victim’s code, executing speculatively at that target, loads secret data and leaves a trace of it in the data cache before the misprediction is discovered and the architectural results are discarded. The data cache leaked what the victim did, but the BTB determined what the victim did. That distinction separates the two families of covert caches: a structure that must be correct can be observed by an attacker (timing side channels through the TLB also have been demonstrated3), but a structure that is allowed to be wrong can be steered.

The mitigations have been performed amidst a years-long negotiation over the tradeoffs between security and performance. The processor vendors added controls to flush the predictors (IBPB) or restrict them (IBRS) on privilege transitions, and later enhanced IBRS, which effectively tags each prediction with the privilege level of the code being tracked. Google’s retpolines took a different route, replacing each indirect branch with a RET instruction so that its prediction would come from the return stack buffer rather than the BTB, a route that Retbleed closed again in 2022 by showing that returns could themselves be predicted from the BTB. Branch History Injection showed that even with predictions tagged by privilege level, the branch history that selects among them was still shared, and could be poisoned from user mode.

How to Detect It

Names are Intel’s for Skylake and Ice Lake, and AMD’s for Zen 4.

• Retired mispredictions, all and indirect.

  • Intel: BR_MISP_RETIRED.ALL_BRANCHES, .INDIRECT, .RET

  • AMD: ex_ret_brn_misp, ex_ret_brn_ind_misp, ex_ret_near_ret_mispred

• Taken branches the front end did not know about.

  • Intel: BACLEARS.ANY

  • AMD: bp_de_redirect

Skylake has no retired event for indirect or return mispredictions; both arrive with Ice Lake.

Working Around It

Branch less, or branch predictably. A data-dependent branch whose outcome is close to random, such as a comparison against the pivot in a sort, or a filter that keeps about half of its input, will mispredict about half the time no matter how good the predictor, and each misprediction discards dozens of cycles of work. Such a branch is better expressed as a data dependency: a conditional move, a select computed with arithmetic, or (for a loop over an array) a SIMD comparison followed by a masked or compressing store, which removes the branch from the loop entirely. Compilers choose between a branch and a conditional move heuristically, and not always well; clang’s __builtin_unpredictable lets the programmer convey this information to the compiler. For predictable branches, which cost almost nothing when predicted correctly, conditional moves may degrade performance by consuming valuable execution resources that would be skipped by correctly-predicted branches. Sorting the input, where the algorithm permits, converts a random branch into a predictable one, which is the answer to one of the most upvoted questions in Stack Overflow’s history and that was reproduced in our earlier article on computing the third-largest element of an array.

Replicate the code. The BTB is indexed by the address of the branch instruction, so if a single branch makes different decisions at different times, those decisions are conflated into one entry4. Making copies of the code gives each path its own branch, at its own address, and therefore its own entry: a function specialized for each call site, which GCC’s -fipa-cp-clone does for constant arguments and inlining does wholesale. Interpreters apply the same remedy to their dispatch branch. An interpreter that ends every opcode handler with its own copy of the indirect jump to the next handler (as threaded code and computed-goto dispatch do) gives the indirect branch predictor one branch per opcode, each with a history that reflects which opcodes tend to follow that one, instead of a single shared branch whose target looks nearly random5. The copies are not free: each competes for the same instruction cache, µop cache, instruction TLB, and BTB, so the remedy trades capacity for accuracy, and pays off only when the counters show more time lost to mispredictions than to misses in those structures.

Budget for the mitigations. The Spectre mitigations are paid for mostly at transitions between privilege levels (system calls, interrupts, and exits from virtual machines), where predictors must be flushed, refilled, or fenced. A program that makes many small system calls pays that cost on every one, and batching its requests (larger reads and writes, or io_uring in place of a system call per operation) reduces the number of transitions. The kernel’s mitigations=off boot parameter shows how much the mitigations cost a given workload, and only should be done in test environments.

Further Reading

• Spectre Attacks: Exploiting Speculative Execution — The disclosure that turned branch prediction into a security topic.

• Branch History Injection — What remained exploitable after predictions were tagged by privilege level.

• Casey, Ertl, and Gregg, Optimizing Indirect Branch Prediction Accuracy in Virtual Machine Interpreters — The extended version of the paper that names code replication, with the measurements behind it.