Estimating branch probabilities | MaskRay
2026-08-09
LLVM's BranchProbabilityInfo assigns every<br>multi-successor terminator a probability distribution over its<br>successors. This post describes the estimation used when no profile is<br>available and reimplements it as a standalone program.
The cascade
BranchProbabilityInfo::calculate tries each source of<br>information in turn and takes the first that succeeds:
10<br>11<br>12<br>13<br>// If there is no at least two successors, no sense to set probability.<br>if (BB->getTerminator()->getNumSuccessors() 2)<br>continue;<br>if (calcMetadataWeights(BB))<br>continue;<br>if (calcEstimatedHeuristics(BB))<br>continue;<br>if (calcPointerHeuristics(BB))<br>continue;<br>if (calcZeroHeuristics(BB, TLI))<br>continue;<br>if (calcFloatingPointHeuristics(BB))<br>continue;
calcMetadataWeights translates !prof branch<br>weights, so with a PGO profile the distribution comes straight from<br>metadata. Every later step exists for functions that have none.
The last three heuristics each inspect one condition — a pointer<br>comparison, a test against a constant, ordered versus unordered floats —<br>and decide one branch in isolation. They and the loop branch heuristic<br>behind the LBH_ constants below come from Ball and Larus's<br>Branch Prediction for Free (PLDI 1993), though nothing in the<br>tree cites it. Wu and Larus combined such heuristics into probabilities<br>with Dempster–Shafer evidence; LLVM takes the first that succeeds.
calcEstimatedHeuristics is the odd one out, and the<br>subject of this post. No paper stands behind it: it arrived in 2020,<br>unifying what had been separate unreachable, cold-call, loop, and invoke<br>heuristics. It is a whole-function analysis because branch probability<br>is not a local property: given<br>br i1 %c, label %a, label %b, nothing at the terminator<br>distinguishes the two edges — what distinguishes them is what<br>%a and %b lead to. So it classifies blocks<br>first, then reads a branch's probabilities off the classifications of<br>its successors. The classification is a pure function of the CFG and its<br>loops: blocks known to be bad — unreachable, noreturn, cold<br>— pull probability away from the branches that lead to them, and loops<br>are treated as units so that staying in a loop is far likelier than<br>leaving it. This is the only step that needs the loop structure, and the<br>only one expressible over a bare CFG; the others need the instructions.<br>The program below implements it, omitting the other heuristics and<br>computeUnlikelySuccessors, a refinement that analyses<br>induction variables through PHI nodes.
That BlockFrequencyInfo consumes<br>BranchProbabilityInfo might suggest a circularity, but the<br>two run in opposite directions: BFI propagates forward from the entry<br>and needs probabilities to do it, while the estimated heuristic<br>propagates backward from syntactically bad blocks and needs only the<br>dominator trees and the loop forest. Nothing it reads comes from a<br>probability.
Estimating block weights
In outline:
Seed unreachable, noreturn, unwinding, and cold blocks<br>with fixed weights.
Propagate each seed up the dominator tree, to every dominator the<br>seeded block post-dominates.
Weight a loop by the maximum over its exit edges, floored at<br>LOWEST_NON_ZERO.
Run two worklists to a fixpoint: a block whose successor edges are<br>all known takes their maximum, which propagates like a seed.
At each branch, divide loop-exiting edges by an assumed trip count,<br>default unknown weights, and normalize.
Weights come from a small fixed scale. Despite the name, a<br>BlockExecWeight is not an execution estimate but one of<br>four ordered labels; the magnitudes exist only so a branch can compare<br>two successors and normalize.
10<br>11<br>12<br>13<br>14<br>15<br>16<br>17<br>18<br>enum class BlockExecWeight : std::uint32_t {<br>/// Special weight used for cases with exact zero probability.<br>ZERO = 0x0,<br>/// Minimal possible non zero weight.<br>LOWEST_NON_ZERO = 0x1,<br>/// Weight to an 'unreachable' block.<br>UNREACHABLE = ZERO,<br>/// Weight to a block containing non returning call.<br>NORETURN = LOWEST_NON_ZERO,<br>/// Weight to 'unwind' block of an invoke instruction.<br>UNWIND = LOWEST_NON_ZERO,<br>/// Weight to a 'cold' block. Cold blocks are the ones containing calls marked<br>/// with attribute 'cold'.<br>COLD = 0xffff,<br>/// Default weight is used in cases when there is no dedicated execution<br>/// weight set. It is not propagated through the domination line either.<br>DEFAULT = 0xfffff<br>};
Blocks not seeded start unweighted, and are treated as<br>DEFAULT only when a branch needs a number.<br>DEFAULT is a floor, not a seed: it never propagates.
How far a seed flows backwards is the interesting part. It is not<br>simply pushed to all predecessors:<br>propagateEstimatedBlockWeight walks up the dominator<br>tree from the seeded block and assigns the weight to each dominator<br>that the seeded block post-dominates . The<br>post-dominance condition is what makes this meaningful: a branch that<br>merely can reach a noreturn block may take the<br>other edge, whereas one that cannot avoid it is genuinely unlikely. The<br>weight therefore spreads through the...