Branch prediction on x86-64 cores

A core fetches and decodes far ahead of execution, so it must choose the path past every branch long before the branch’s condition or target is known. It runs the chosen path speculatively; when the guess proves wrong, the work done on the wrong path is thrown away and fetch restarts at the right address, which costs roughly the length of the pipeline. [Agner Fog, Chapter 3, page 14; AMD 58455, Section 2.8, page 26]

Each branch needs two predictions: whether it is taken, and if so where it goes. The target comes from the branch target buffer (BTB), which records a branch once it has been taken; the direction of a conditional branch comes from a predictor that learns from the history of earlier branches. AMD’s cores add a return address stack, a separate predictor for indirect branches and a queue that tracks the predicted fetch windows until they retire. [Agner Fog, Chapter 3, page 14; AMD 58455, Section 2.8.1, page 26]

The direction predictors of current cores work from global history, the outcomes of the branches that led to this one, and learn long repeating patterns. A branch that follows no pattern and correlates with nothing before it stays hard to predict: one taken at random half of the time is mispredicted about half of the time, and one taken at random 10% of the time about 11% of the time, slightly worse than its bias because the predictor keeps looking for a pattern. [Agner Fog, Section 3.1, Table 3.1, pages 16 and 17; AMD 58455, Section 2.8.1.5, page 29; Agner Fog, Sections 3.8 and 3.13, pages 31 and 36]

A loop’s exit is the one outcome in many that differs. Agner Fog found the exit of a loop predicted without a miss for counts up to about 32 on Skylake, up to 64 on Zen 3 and Zen 4 (Zen 3) and up to 128 on Zen 5; a longer loop usually costs one misprediction when it ends. [Agner Fog, Section 3.8, page 31; Agner Fog, Section 3.13, page 36]

A conditional branch the predictor knows nothing about is predicted not taken. On AMD’s Zen 3 to Zen 5 such a branch is not even in the BTB; once taken it is predicted always taken, and only after it has also fallen through does the history-based predictor take it on (Zen 5). Intel says the same of the predictor of its recent cores. [AMD 58455, Section 2.8.1.5, page 29; AMD 57647, Section 2.8.1.5, page 23; Agner Fog, Section 3.17, page 40; Intel 248966, Section 2.1.1.1, page 2-2]

Code should be laid out so that the common case falls through. A conditional branch that never jumps uses no BTB entry, and on AMD’s cores it stays out of the global history as well, leaving more of both for the branches that need them; not-taken branches also run at a higher rate than taken ones, and the fall-through path is what a branch the predictor has forgotten will follow. [Intel 248966, Sections 3.4.1.1 and 3.4.1.2, pages 3-4 and 3-6; AMD 58455, Section 2.8.1.5, page 29]

Prefixes 2Eh and 3Eh before a conditional jump once served as static hints, on the Pentium 4. Intel’s Redwood Cove gives the 3Eh prefix meaning again: a branch the predictor has no record of that carries it is redirected to its target at decode, which saves most of a misprediction when the branch is taken and adds a second redirection when it is not. Intel advises hints only on rarely run branches that are nearly always taken, placed by profile-guided optimization. Golden Cove ignores the prefix, and Agner Fog found hints without effect on AMD’s cores. [Agner Fog, Section 3.17, pages 39 and 40; Intel 248966, Sections 2.1.1.1 and 2.1.1.2, pages 2-2 and 2-3]

LLVM 23.1.2 emits the taken hint only for Granite Rapids (-mtune=graniterapids), only with the hidden option -enable-branch-hint, and only on jumps that its branch probabilities put above 50%. [LLVM 23.1.2, X86.td, line 1273; LLVM 23.1.2, X86MCInstLower.cpp, line 59; LLVM 23.1.2, X86MCInstLower.cpp, line 2655]

AMD’s Zen 3 to Zen 5 have a BTB of two levels: the first predicts most direct branches with no lost cycle, the second is larger and slower, and each generation has made the first level larger (Zen 3, Zen 4, Zen 5). Intel publishes no BTB sizes for its recent cores (Skylake, Golden Cove). [AMD 56665, Section 2.8.1.2, pages 28 and 29; AMD 57647, Section 2.8.1.2, page 21; AMD 58455, Section 2.8.1.2, page 27; Agner Fog, Section 3.8, page 31]

The BTB holds only so many branches, and a branch that falls out of the fast level pays the slower level’s delay or, out of both, a full misprediction for its target. Both vendors advise keeping the set of hot branches small; unrolling a loop that has branches in its body multiplies them. [AMD 58455, Section 2.8.1.2, page 27; Intel 248966, Sections 3.4.1.1 and 3.4.1.6, pages 3-4 and 3-10]

An entry of AMD’s BTB holds up to two branches, so one lookup can predict two: on Zen 3 a conditional branch and the branch after it in the same 64-byte line, and from Zen 4 on also a direct jump and the next branch at its target. The two share bits for their targets, so a branch whose target is far away may need an entry to itself (Zen 5). [AMD 56665, Section 2.8.1.2, pages 28 and 29; AMD 57647, Section 2.8.1.2, page 21; AMD 58455, Section 2.8.1.2, page 27]

A direct branch whose target lies across a 1 MB aligned boundary cannot share its entry on Zen 3 and Zen 4, a limit Zen 5 raises to 16 MB, and Zen 3 and Zen 4 can track only a few targets across a 128 GB boundary. Keeping hot code and the code it calls close together keeps the BTB’s capacity for branches. [AMD 56665, Section 2.8.2, page 31; AMD 57647, Section 2.8.2, page 23; AMD 58455, Section 2.8.2, page 30]

AMD’s cores track each predicted 64-byte fetch window from fetch to retirement, in 64 entries on Zen 3, 96 on Zen 4 and 128 on Zen 5, halved for each thread when two share the core. A line whose branches need more than one BTB entry takes more than one window, and when the queue is full fetch stops until something retires, so many branches in a line cost capacity here too. [AMD 56665, Section 2.8.1.6, pages 30 and 31; AMD 57647, Section 2.8.1.6, page 23; AMD 58455, Section 2.8.1.6, page 30]

Taken branches cost more than not-taken ones on every core. Agner Fog measured one taken branch or jump a cycle on Skylake at best and on Zen 3 and Zen 4, two on Zen 5; not-taken branches run at two a cycle on Skylake, Zen 3 and Zen 4 and three on Zen 5, fused compare-and-branch pairs included (Skylake, Zen 3). [Agner Fog, Section 3.8, page 31; Agner Fog, Sections 23.15, 24.15 and 25.15, pages 245, 252 and 258; Agner Fog, Section 3.13, page 37]

On AMD’s cores the number of branches that code meets in a line after entering it matters more than the number the line holds: one BTB entry covers the first two, and a third needs another entry and more cycles, unless an earlier branch is unconditional or nearly always taken (Zen 5, Zen 4, Zen 3). [AMD 58455, Section 2.8.3, page 30; AMD 57647, Section 2.8.3, pages 23 and 24; AMD 56665, Section 2.8.3, page 31]

Intel’s general rules allow at most four branches in a 16-byte block and at most two loop-ending branches. Before Ice Lake, two conditional branches whose last bytes fall in the same aligned 8 bytes should not have targets that agree in their low 6 bits. [Intel 248966, Section 3.4.1, page 3-4; Intel 248966, Section 3.4.1.3, Rules 9 and 10, page 3-8]

Returns are predicted by a return stack, which every call pushes and every return pops. It holds 16 entries on Skylake, 22 on both Ice Lake and Tiger Lake, 32 per thread on Zen 3 and Zen 4 and 52 on Zen 5 (Zen 5); calls nested deeper than that, as in deep recursion, mispredict their returns once the stack has wrapped. Intel suggests inlining to reduce the depth of a hot chain of more than 16 calls. [Agner Fog, Section 3.8, page 31; Agner Fog, Section 3.13, page 37; AMD 58455, Section 2.8.1.3, page 28; Intel 248966, Section 3.4.1.3, Rule 6, pages 3-7 and 3-8]

The stack works only when calls and returns pair up. Pushing an address and jumping in place of a call, or returning to an address the code computed, leaves it out of step and costs mispredictions on the returns that follow. A call to the next instruction, the old way to read the instruction pointer, is the exception both vendors handle; in 64-bit code lea with a RIP-relative address does the same without a call. [Intel 248966, Section 3.4.1.3, Rule 4, page 3-7; Agner Fog, Section 3.16, page 39; Intel 248966, Section 3.6.8.2, page 3-54; AMD 58455, Section 2.8.1.3.1, page 28]

A call that is the last thing a function does can become a jump to the callee, whose return then goes straight to the original caller. This saves the return and a return stack entry, and in 64-bit code it works as long as the stack is left as the caller gave it. [Intel 248966, Section 3.4.1.3, Rule 8, page 3-8; Agner Fog, Section 3.16, page 39]

Even predicted calls and returns are not free. On Zen 3 and Zen 4 each leaves the predictor idle for a cycle, and on Zen 5 a return for two while a direct call costs nothing; Agner Fog measured one call or return every two cycles on Zen 3 to Zen 5. A one-byte ret is as fast as any other on these cores. [AMD 56665, Section 2.8.1.3.3, page 30; AMD 57647, Sections 2.8.1.2 and 2.8.1.3.3, pages 21 and 22; AMD 58455, Sections 2.8.1.2 and 2.8.1.3.2, pages 27 and 28; Agner Fog, Sections 23.15, 24.15 and 25.15, pages 245, 252 and 258]

An indirect jmp or call that always goes to the same place is predicted from its BTB entry like a direct one. One with several targets needs a predictor that chooses among them by the path that led to it: AMD’s has 1,536 entries on Zen 3 and 3,072 on Zen 4 and Zen 5 (Zen 3, Zen 5), and Agner Fog found Intel’s cores from Haswell on predict such branches well. Fewer targets per branch still predict better. [AMD 56665, Section 2.8.1.4, page 30; AMD 57647, Section 2.8.1.4, page 22; AMD 58455, Section 2.8.1.4, pages 28 and 29; Agner Fog, Section 3.8, page 31]

An indirect branch the predictor has no target for is assumed to fall through, so the bytes after it are fetched and may be decoded and run. They should be code: either the most likely target or an instruction that stops the wrong path, such as UD2. Data placed there, a jump table above all, can be decoded as instructions and slow the recovery. [Intel 248966, Section 3.4.1.5, Rule 13, page 3-8; Intel 248966, Section 3.6.8, Rule 49, page 3-53; Agner Fog, Section 3.15, page 38]

When one target of an indirect branch is common and the branches before it tell when it will be taken, testing for that target with a conditional branch first, and taking the indirect branch only for the rest, gives the predictor history it can use. Intel advises measuring both ways, since the extra branch must itself predict well to pay off. [Intel 248966, Section 3.4.1.5, pages 3-9 and 3-10]

A switch compiles to a jump through a table, one indirect branch that depends on the indirect predictor, or to a tree of conditional branches, which takes more BTB entries and is dense with branches. Which predicts better depends on the core and on the pattern of the values. [Agner Fog, Section 3.15, page 38]

Distant targets cost the indirect predictors too. On Zen 3 and Zen 4 only a few targets beyond a 64 MB aligned boundary from the branch can be tracked, and on Intel’s cores an indirect branch to a target more than 2 GB away mispredicts more often (Golden Cove). [AMD 56665, Section 2.8.1.4, page 30; AMD 57647, Section 2.8.1.4, page 22; Intel 248966, Section 3.11.7, pages 3-82 and 3-83]

Spectre mitigations take indirect prediction away. LLVM’s retpoline options replace indirect calls and jumps with a sequence that does not speculate on their target, and with them it builds no jump tables, lowering each switch to conditional branches instead. [LLVM 23.1.2, X86.td, line 421; LLVM 23.1.2, X86ISelLowering.cpp, line 36548]

A misprediction costs about as many cycles as the pipeline is long: 11 to 18 cycles on Zen 3 and Zen 4 and 12 to 18 on Zen 5 by AMD’s figures, which vary with the kind of branch and with whether the op cache supplies the right path, and about 15 to 20 on Skylake and sometimes over 20 on Golden Cove by Agner Fog’s (Zen 3, Zen 4, Zen 5, Skylake, Golden Cove). [AMD 56665, Section 2.8, page 28; AMD 57647, Section 2.8, page 20; AMD 58455, Section 2.8, page 26; Agner Fog, Sections 3.8 and 11.4, pages 31 and 153; Agner Fog, Section 13.1, page 175]

What a branch costs on average is its misprediction rate times the penalty. At 15 cycles, a branch that goes either way at random costs about 7 or 8 cycles each time it runs, more than most of the work it chooses between, while one mispredicted 1% of the time costs a fraction of a cycle. [Agner Fog, Section 3.1, Table 3.1, pages 16 and 17; AMD 58455, Section 2.8, page 26]

Intel’s top-down method counts the cost as Bad Speculation: the slots spent on micro-ops that never retire and the slots lost while the pipeline recovers; the wait for the right path’s code appears as front-end stalls. Intel treats a high share of Bad Speculation as the first thing to look at, since it distorts the other measurements. [Intel 248966, Section 22.1.6, pages 22-5 and 22-6]

A tight spin-wait loop ends in a flush of its own: its loads run ahead of the store that releases it, and the processor must discard them to keep memory order. A PAUSE in the loop slows the loads enough to avoid it and frees the core for the other thread; how long it waits differs widely between cores (Skylake, Zen 5). [Intel 248966, Section 11.4.2, pages 11-12 and 11-13; Intel 248966, Section 3.4.1, page 3-4]

CMOVcc and SETcc replace a branch with a data dependence: nothing can be mispredicted, but the result waits for the condition and for both inputs, and the core can no longer run ahead on a guessed path. Both vendors advise them for branches that are hard to predict, and Intel warns against them for predictable ones. [Intel 248966, Section 3.4.1.1, Rule 2, page 3-5; AMD 58455, Section 2.8.1.2, page 27]

Branchless code wins when the work it adds costs fewer cycles than the branch it removes costs on average. That favours conditions that follow no pattern and often go either way; a branch that goes one way 99% of the time is mispredicted about 1% of the time and is cheaper kept, and Intel notes that branches its cores mispredict consistently are rare. [Intel 248966, Section 3.4.1.1, Rule 2, page 3-5; Agner Fog, Section 3.1, Table 3.1, pages 16 and 17]

Without CMOV a choice between two constants can be made from the flags with arithmetic: setcc gives 0 or 1, subtracting 1 turns it into a mask of all ones or zeros, and an and with the difference of the constants and an add of one of them gives the result. [Intel 248966, Section 3.4.1.1, Example 3-2, page 3-5]

A CMOV with a memory source always reads it, and may fault on it, even when the condition is false, so it cannot replace a branch that guards a load from a pointer that may be invalid. [AMD 24594, CMOVcc, page 152]

LLVM 23.1.2 turns CMOVs back into branches where a branch is likely faster. It does so for every CMOV that loads from memory, since the CMOV must wait for the load where a predicted branch would not; and in innermost loops for CMOVs whose condition is late, when the change shortens the loop’s critical path by at least 4 cycles and an eighth, and each CMOV’s gain covers at least a quarter of the misprediction penalty, but not when the result is the address of the next load, as in a tree search. [LLVM 23.1.2, X86CmovConversion.cpp, line 14; LLVM 23.1.2, X86CmovConversion.cpp, line 96; LLVM 23.1.2, X86CmovConversion.cpp, line 195; LLVM 23.1.2, X86CmovConversion.cpp, line 522; LLVM 23.1.2, X86CmovConversion.cpp, line 555]

In vector code the same idea applies a lane at a time: a comparison makes a mask, and an AVX-512 masked operation applies it, so a condition that differs between elements needs no branch at all. [Intel 248966, Section 3.4.1.1, page 3-6]

Inlining removes a call and a return and lets the callee’s branches be predicted in the context of each caller, which often makes them more predictable. Intel advises it for small functions called often and for those whose branches predict poorly; AMD for functions in hot loops that are small or have few callers. [Intel 248966, Section 3.4.1.3, Rules 5 and 7, pages 3-7 and 3-8; AMD 58455, Section 2.8.1.3.3, page 28]

The likely path should run straight through memory, and code that seldom runs, such as error handling, moved out of it, to a separate page when it is almost never needed. [Intel 248966, Section 3.4.1.1, Rule 1, page 3-5; Intel 248966, Section 3.4.1.4, Rule 12, page 3-8]

Unrolling a small loop spends fewer branches and less loop overhead on the same work; Intel suggests unrolling until they take less than about a tenth of the time, and AMD notes that a small loop that runs only twice predicts better unrolled. Past that point unrolling costs room in the BTB and the decoded cache (front end). [Intel 248966, Section 3.4.1.6, Rule 14, page 3-10; AMD 57647, Section 2.8.1.5, page 23; AMD 56665, Section 2.8.1.5, page 30]

Where a taken branch and its target sit in a line matters to the front end. On AMD’s cores a jump to near the end of a 64-byte line leaves only a short fetch block, and on Intel’s a taken branch should end near the end of its line and its target start near the beginning of one (front end). [AMD 58455, Section 2.8.1.1, page 26; Intel 248966, Section 3.4.1.4, Rule 11, page 3-8]

Some layout rules belong to one core. On the Skylake family with the microcode update for its JCC erratum, a jump that crosses or ends on a 32-byte boundary is no longer cached in decoded form, which code built for those cores avoids by padding (Skylake, front end). Other cores have no such rule, and Intel lists none of its later cores as affected. [Intel 341810, Sections 2.1 and 3.0, pages 6 and 11; Intel 341810, Section 4.0, pages 13 to 15]