Estimating
branch probabilities says how one branch splits.
BlockFrequencyInfo turns those local numbers into per-block
frequencies, which nearly every profitability decision in LLVM ends up
reading.
The core is a linear-time propagation over loop-packaged regions. Where no such structure exists — irreducible control flow — the accuracy goes with it.
Mass, packaging, scale
BFI propagates mass — a fixed-point fraction of the 64-bit range — one loop level at a time. The scheme is Wu and Larus, Static Branch Frequency and Program Profile Analysis (MICRO-27, 1994), though nothing in the tree cites it.
Blocks are numbered in reverse post-order, and a
BlockNode's index is its RPO index — which
is why later code can test edge direction with a plain
<. Bottom-up, each loop gets full mass at its header and
one RPO sweep over its members. It is then packaged:
collapsed to a pseudo-node reusing the header's RPO number, whose
successors are the loop's recorded exits. Its scale is
1 / (Full − BackedgeMass) — return 90% of the mass to the
header and the scale is 10. Finally unwrapLoops walks
outermost-first, multiplying each block's local mass by the composed
scale of its enclosing packages.
Packaging is not a detail, it is the algorithm: it bounds mass to
[0,1] so the arithmetic stays exact under dithering, makes
every level acyclic so each block is swept once, and gives the whole
thing O(V+E). GCC's propagate_freq instead
re-walks each block once per loop depth, O(V·D).
The irreducible fiction
An SCC with several entries has no header to sweep from. BFI invents one, as the file's comment says:
Block frequency calculations act as if a block is inserted that intercepts all the edges to the headers. All backedges and entries point to this block. Its successors are the headers, which split the frequency evenly.
analyzeIrreducible runs Tarjan over an
IrreducibleGraph — the CFG restricted to the enclosing
loop, quotiented by packaged sub-loops, cut at the enclosing header —
and classifies members:
1 | // entry: an edge from another SCC reaches it |
Entries are reached from outside; two or more is
what makes the region irreducible. Extra headers are
internal cycles that would otherwise wrap back past an already-swept
block — !(U.Node < V->Node) compares RPO indices. The
!IsEntry[U] guard matters: a retreating edge from
an entry does not create one, since entries have no meaningful relative
order. Everything else is an ordinary member.
Entries and extras are sorted together into a header prefix
of LoopData::Nodes, so isHeader is a binary
search and getHeaderIndex a lower_bound. The
primary entry is just Nodes[0], the
lowest-RPO header — and because of that joint sort it may well be an
extra header rather than a real entry. Its two jobs:
getResolvedNode() maps every member to it, and it donates
its RPO number to the package.
Mass then reaches the headers in four steps. Full mass is
seeded across them by
!irr_loop_header_weight, or by MinHeaderWeight
for headers lacking it (the minimum, the comment notes, beats the
average), or evenly when no metadata exists at all. Every node is
swept, headers included. Any edge to any header
accumulates into a per-header BackedgeMass
vector, indexed by getHeaderIndex. Finally
adjustLoopHeaderMass corrects, but only if
no header had metadata: it discards the seeded split and redistributes
full mass in proportion to the backedge mass each header actually
received.
That correction is the entire approximation — one step of power iteration, seeded from uniform, never repeated, and skipped outright when a profile is present.
Measuring it
For a region with an exit, frequencies are the unique solution of
f = e + fP; for a closed region only ratios are defined,
and the answer is the stationary distribution of P. Both
are small exact rational solves: scrape
print<branch-prob> for the probabilities, eliminate
over fractions.Fraction, compare against
print<block-freq>.
Two traps. Filter blocks below ~1e-6 of the hottest —
BPI's weight-1 floor manufactures 1e-19 blocks that
otherwise dominate every relative error. And do not renormalize
P's rows to stochastic in order to compare ratios when the
region has a real exit; that changes the object being solved, and will
report an improvement as a regression.
Upstream today, against that oracle:
1 | exact BFI |
4.000 against 2.667 is exactly what one correction step from an even split gives.
What the CycleInfo port cost
#213488
moved BFI to CycleInfo, removing a redundant
LoopInfo. The forest BFI wants is now a strict subset of
the cycle forest, and the selection has a subtle second clause: a
reducible cycle whose header is an entry of an enclosing
irreducible cycle is deliberately not represented, so that equal entries
stay equal.
That fixes @crossloops. It also discards the loop scale
such a cycle used to contribute. nonentry is the clean case
— {a,c} is a natural loop headed by a, and
a is an entry of the irreducible {a,b,c}:
1 | entry -> a | b a -> c | b c -> a b -> a | exit |
-debug-only=block-freq now prints no
- loop = line at all: it goes straight to
found-scc and gives the flat SCC one
scale = 64.0. The ~32× trip count of {a,c}
never enters the computation, and every block lands 16–31× too cold
where it had been exact to 1.6%. Three of the four closed-form cases
added to pin this down regressed with the port; only
equalrows held.
Solving the SCC
If the entry split is the approximation, compute it — #215170,
still open. Package the SCC with one representative (lowest RPO) and
drop the header set; build the internal transition matrix from
getSuccWeights, partitioning intra-SCC edges from escapes;
power-iterate F ← F·P to a relative
Δ < 2⁻³² or 16 iterations, the running sum dividing out
the geometric decay of mass leaking through the exits; pin any members
carrying !irr_loop_header_weight and let the rest settle
around them.
NumHeaders, the sorted prefix,
getHeaderIndex, distributeIrrLoopHeaderMass,
adjustLoopHeaderMass and MinHeaderWeight all
disappear; isHeader collapses to
Node == Nodes[0] and the per-header
BackedgeMass vector to a scalar — a strictly more accurate
patch at net −80 lines of code. The entry/extra classification itself
survives, now only to mark isIrrLoopHeader(), where PGO
instrumentation places its counters.
1 | exact before after |
On a tail-duplicated computed-goto dispatch — the shape irreducible CFGs actually take in the wild — worst-block error goes 1.536× → 1.003×. That is the number that matters: these regions are rare and almost entirely CodeGen-manufactured, 22 of 221703 functions at MIR against 3 of 64391 at IR.
Cost, per SCC of n members and e internal
edges: setup stays O(e) — members are located by binary
search over the sorted node list rather than a table sized by the whole
function — and the solve goes O(e) → O(k·e)
with k ≤ 16.
k is the part to watch, and the cap started far higher.
At a bound of 200, over the in-tree corpus plus 300 fuzzed CFGs, 434
SCCs:
1 | pure power iteration: n=120 median k=138 hit the 200 cap: 43% |
A third exhausted the cap, so the result was often truncated rather
than converged — but that turns out not to matter. Sweeping the bound
over an irreducible corpus leaves the error distribution unchanged from
10 iterations to 1000, and not monotonically: 20 scores better than 30.
The iterate wanders rather than steadily improving, so the tail is
noise, and the bound is a backstop rather than a convergence criterion —
which is why the patch settles on 16. Nor is it a cost problem: the
computed-goto dispatch that motivates all this has a six-block SCC, and
llc on it runs in 14ms end to end.
One thing is still worth fixing. A periodic SCC oscillates forever —
10 of 38 in one corpus were still moving at 100000 iterations. Damping
(F ← (F + F·P)/2) fixes that and converges in a median of
32 steps, but it converges towards the quasi-stationary vector,
which is the wrong target while the entry injection is missing: it turns
three exact cases into 1.24–1.41× to buy one improvement. Not worth
doing before the injection is available.
The other solver
LLVM already contains a second solver for the same system, behind
-use-iterative-bfi-inference and gated on profile data plus
an irreducible loop. It is tempting to describe the two as complementary
— fixing different failures — but the measurements do not support that.
They approximate the same f = e + fP; one does it during
distribution on a single SCC, the other afterwards over the whole
function.
On yyparse_1, the function whose comment says inference
exists to fix it:
1 | exact BFI (SCC solved) BFI + inference |
Inference is exact; the packaged propagation is 335–782x off on the same function. Solving the SCC properly barely moves it.
The split between them is by CFG shape, not by kind of failure.
initTransitionProbabilities routes sinks back to the entry,
so the chain it solves is closed; where a function has no exit
blocks — the computed-goto dispatch, exactly the shape irreducible CFGs
take in the wild — inference is a no-op. That holds even after forcing
its hasProfileData gate open, so it is the missing exits,
not the gate. There, BFI's own numbers are all there is. Conversely,
where a function has exits and a profile, inference is right and BFI is
orders of magnitude out.
On 38 generated functions with no parallel or zero-probability edges
and no useful block profile, the SCC solve is exact on 34 and adding
inference is never better and worse on three — it only drifts. Feeding
it the unfiltered generator output makes it look far worse still (median
4.6x → 16.2x), but that is the generator:
initTransitionProbabilities drops parallel edges rather
than summing their probabilities, and discards zero-probability jumps,
and gen.py stresses both deliberately. Dropping a parallel
edge changes the chain, so it converges to something the CFG does not
describe. That looks like a real defect, separate from any of this.
The honest reading is that inference is not a companion to the
structural fix but a better solver bolted on afterwards, reachable only
when a profile exists and the function has an exit. It also says
something about priorities: getting yyparse_1 exact needs
the flow equations solved, not a better eigenvector for one SCC, which
is an argument for the entry-injection work over anything else described
here.
Detecting irreducibility up front
BFI used to learn which regions need this by failing.
Distribution ran until addToDist hit a retreating local
edge to a non-header, then aborted, packaged, and reran — and the
abandoned attempt had to be undone, which is why
IrreducibleGraph::addNode resets each node's mass as a side
effect of building the graph.
CycleInfo already knows, and initializeLoops already
walks the cycle forest carrying the innermost represented ancestor:
1 | } else if (!CI->isReducible(Cycle)) { |
#214941
packages the marked regions before distributing, and the retry protocol
collapses: addToDist, addLoopSuccessorsToDist
and computeMassInLoop return void,
tryToComputeMassInFunction folds into
computeMassInFunction, and both undo sites become asserts.
Net −57 lines, and addToDist sheds 168 bytes per successor
edge because under NDEBUG the retreating-edge check
compiles out entirely. The caveat: turning "unconditionally undo" into
"assert nothing to undo" is NFC only if the invariant holds, and a
release build has no assert to catch it.
Two traps
A BFI change silently reinterprets existing PGO
profiles. CFGMST weights edges by
BFI->getBlockFreq() to pick which edges go
uninstrumented. Change BFI and the counter indices permute —
while the function hash, computed from CFG structure, does not. The
profile is not rejected, it is misattributed. This surfaces as a test
failure that looks like a correctness bug and is not: permuting the
counter values in Inputs/irreducible.proftext to match the
new numbering made the test pass with its original expected
counts.
FileCheck cannot see numerical drift.
print<block-freq> prints five significant digits, so
a change moving only low-order scaled integers passes every lit test
while being wrong. A standalone model of BFI drifted from the branch it
tracked and kept passing all 14 tests while 65% of fuzzed CFGs
mismatched byte-for-byte — every mismatch a function with irreducible
control flow, which is also the fastest way to localize such a drift.
Only differential fuzzing over whole output catches this class.
What not to do
Sourcing the SCC decomposition from CycleInfo rather than running
Tarjan over IrreducibleGraph looks obvious and is not worth
it.
The graph is not the CFG — it is quotiented by packaged sub-loops and
cut at the enclosing header, without which the entire loop is one SCC
and nothing decomposes. More decisively, the order is load-bearing:
packages are created in reverse-topological order and siblings interact,
since an edge into a sibling resolves to its raw block if it is not yet
packaged but to its header if it is. 7.8% of irreducible regions contain
two or more SCCs, so this is common, not a corner case, and restoring
the order needs a topological sort of the SCC DAG — the thing just
deleted. Extra headers also still need the intra-SCC RPO
scan, which CycleInfo cannot answer.
What CycleInfo can answer is "does this region contain an irreducible cycle" — which is exactly the detection above.