graph

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.

LLVM's BranchProbabilityInfo assigns every multi-successor terminator a probability distribution over its successors. This post describes the estimation used when no profile is available and reimplements it as a standalone program.

The dominator tree lets us identify natural loops: a back edge T->H whose head H dominates its tail T defines a loop with the single entry H. This works only for reducible control flow graphs. Optimized machine code and decompiler output routinely contain irreducible loops, which have more than one entry and thus no dominating header, so the dominator-based method cannot see them.

This post builds a loop-nesting forest for an arbitrary CFG with the single-pass depth-first search of 韦韬、毛剑、邹维、陈宇(Tao Wei, Jian Mao, Wei Zou & Yu Chen) A New Algorithm for Identifying Loops in Decompilation, SAS 2007 (The 14th International Static Analysis Symposium).