Lesson 20.3 — Inlining: heuristics, cost models and learned policies

Techniques: classic inlining heuristics — Scheifler's formulation as a knapsack problem (1977), size thresholds, benefit/cost priorities (Davidson & Holler 1992; Ayers, Schooler & Gottlieb 1997; GCC's badness); LLVM's InlineCost with simplification during analysis, bonuses and the inline advisor; ML-guided inlining, MLGO (Trofin et al. 2021) · Pebble implements: pebble-inline with three heuristics — size threshold, bottom-up cost/benefit (the course cost model), profile-guided with Ch 12's pebble-bbcount counters (E2); the comparison lab labs/ch20-inline · Drill: inline-decision · Prerequisites: Lessons 20.1–20.2; constant folding (Ch 13); pebble-bbcount (Lesson 12.3) · Time: 7–9 hours

Inlining replaces a call by a copy of the callee's body. It is the single most profitable interprocedural transformation, not because calls are expensive — a call and a return cost a few cycles — but because the copy is specialized to its call site: constant arguments fold, dead branches disappear, the callee's loads and stores become visible to the caller's alias analysis. It is also the transformation most likely to make a program slower, through code growth. The running example is scale.c:

static int scale(int x, int mode) {
  if (mode == 0)
    return x + 1;
  int s = x;
  for (int k = 0; k < 8; k++) {
    s = s * 31 + k;
    s ^= s >> 7;
    s += (s & 0xff) * mode;
    s %= 1000003;
  }
  return s;
}
int fast(int x) { return scale(x, 0); }
int slow(int x, int m) { return scale(x, m); }

At the call in fast the constant mode = 0 makes nine of scale's ten blocks unreachable; at the call in slow nothing folds.

1. Problem and motivation

Classic inlining heuristics

Scheifler stated inlining as an optimization problem: choose a set of call sites to expand so as to minimize running time subject to a bound on program size, where expanding one site changes the size and the benefit of others; he showed the problem NP-complete and used a greedy approximation [Sch77]. Every production inliner since is a heuristic for it. The simplest rule, inline if the callee is smaller than \(N\) instructions, captures the most common win (tiny accessors) and nothing else. Davidson and Holler measured that inlining small and frequently called functions speeds programs up but that aggressive inlining can slow them down through register pressure and instruction-cache misses [DH92]. Ayers, Schooler and Gottlieb's HP compiler inlined aggressively with profile information and a global priority order [AGS97]; GCC's inline_small_functions keeps a priority queue of call edges keyed by badness — estimated time saved per unit of size growth — and inlines greedily until the unit-growth limit [GCC-Inline].

LLVM's InlineCost and inline advisor

LLVM's inliner visits the call graph bottom-up (Lesson 20.2) and asks, for each call site, an inline advisor. The default advisor calls getInlineCost, which simulates the callee under the call site's arguments: it walks the callee's instructions, constant-folds with the actual arguments, follows only branches that stay live, and adds a cost for each instruction that would remain, minus the savings of removing the call; the threshold (225 at -O2) is raised by bonuses — +50 % if the callee has a single reachable block, a vector bonus that is withdrawn if the callee has little vector code, 15 000 if this is the last call of an internal function (removing the function then shrinks the program) — and replaced by profile-based thresholds for hot and cold call sites [LLVM-InlineCost]. pebble-inline<cost> implements a small version of this model (Definitions 20.3.6–20.3.8); on scale it computes the same cost as LLVM (§3).

ML-guided inlining (MLGO)

A hand-tuned cost model has dozens of magic constants. MLGO replaces the decision (not the mechanics) with a small neural network that maps features of the call site, caller and callee — block counts, call-site height in the call graph, the InlineCost estimate, the number of constant arguments — to "inline or not", trained offline with reinforcement learning (policy gradient or evolution strategies) to minimize the final binary's size [TQY+21]. At compile time LLVM's MLInlineAdvisor evaluates the network, compiled ahead of time into the compiler, so no ML framework is needed at run time. The trained size policy is deployed for -Oz builds; speed policies use profile features [LLVM-MLGO].

2. Definitions and algorithms

Definition 20.3.1 (Inline substitution)

Let call site \(c\) in caller \(f\) call \(g\) with actual arguments \(a_1, \dots, a_k\), and let \(g\)'s definition be known. Inlining \(c\) replaces the call by: a split of \(c\)'s block into a head (up to \(c\)) and a continuation \(K\); a copy \(g'\) of \(g\)'s blocks in which every value is renamed fresh, every use of the formal parameter \(p_i\) is replaced by \(a_i\), every ret v becomes br K, and the call's result is replaced by a phi in \(K\) joining the returned values; the head branches to \(g'\)'s entry; static allocas of \(g\) are moved to \(f\)'s entry block (with lifetime markers). LLVM's InlineFunction performs exactly this, plus the updates of debug information, exception handling (invoke unwinds) and attributes.

Theorem 20.3.2 (Inlining preserves semantics, and the conditions)

Let \(g\)'s body be the one that executes at run time (it is an exact definition: not interposable, not replaceable at link time), let the call's type match \(g\)'s, and let \(g\) not use va_start, llvm.returnaddress or returns_twice calls, nor take the address of its own blocks (blockaddress), nor contain a musttail call. Then for every input, the program after Definition 20.3.1 has the same observable behavior (output, termination, final memory reachable from globals) as before, provided its stack does not overflow.

Proof sketch (full proof for a structured language: [Sch77, §2]; LLVM's conditions: isInlineViable, [LLVM-InlineCost])

By a simulation between the two small-step semantics. A state of the original program at a point inside \(g\)'s activation called from \(c\) is \(\langle \sigma_f, \sigma_g, pc_g, M \rangle\) (the frames of \(f\) and \(g\), the program point in \(g\), memory \(M\)); relate it to the state \(\langle \sigma_f \cup \rho(\sigma_g), pc_{g'}, M' \rangle\) of the inlined program, where \(\rho\) is the renaming of Definition 20.3.1 and \(pc_{g'}\) the copy of \(pc_g\), and \(M'\) equals \(M\) except that \(g\)'s stack slots live in \(f\)'s frame. (1) Entry: executing the call binds \(p_i := a_i\); the inlined program evaluates the same instructions with \(a_i\) substituted — related states. (2) Body: each instruction of \(g'\) is the renamed instruction of \(g\), reading related values; names are fresh, so no value of \(f\) is read or clobbered. (3) Allocas: a static alloca is allocated once per call before; after, once per activation of \(f\) — equivalent as long as no two activations of \(g\) inside one activation of \(f\) overlap (they cannot: the inlined copy is not recursive) and lifetime markers mark each dead between uses. (4) Return: ret v → br K and the phi in \(K\) receive exactly the value the call would have returned. The conditions exclude exactly the cases where (1)–(4) fail: an interposable \(g\) (another body runs), va_start (reads the caller's variadic area, which no longer exists), returnaddress and returns_twice (observe the call itself), blockaddress (identity of blocks changes), musttail (a tail-call guarantee the copy cannot keep). Stack use can grow (allocas from all inlined callees coexist in \(f\)'s frame), hence the proviso.

Definition 20.3.3 (The inlining problem)

Given a call graph with a size \(s(f)\) per function and, per call edge \(e\), a benefit \(b(e) \ge 0\) (time saved if \(e\) is inlined) and a growth \(\Delta(e)\), find a set \(I\) of edges to inline that maximizes \(\sum_{e \in I} b(e)\) subject to \(\sum_{f} s(f) + \sum_{e \in I} \Delta(e) \le B\) for a size budget \(B\). In reality \(b\) and \(\Delta\) depend on which other edges are inlined (inlining into a callee changes its size; constant arguments enable folding only after inlining higher up); the independent version is already hard.

Theorem 20.3.4 (The inlining problem is NP-hard)

Deciding whether some \(I\) achieves benefit \(\ge k\) within budget \(B\) is NP-complete, even for a call graph that is a star (one caller, \(n\) leaf callees called once each) with independent benefits and growths.

Proof

In NP: a set \(I\) is a certificate checkable in polynomial time. Hardness: reduce 0/1 knapsack (items with weight \(w_i\) and value \(v_i\), capacity \(W\), target \(k\)), which is NP-complete. Build main with \(n\) call sites \(e_i\) to leaves \(g_i\), each of size \(w_i + 1\) and called only there; set \(b(e_i) = v_i\) and \(\Delta(e_i) = w_i\) (the copy adds \(w_i + 1\) instructions and removes the call; the leaves stay, e.g. they are exported). With \(B = \sum_f s(f) + W\), a set \(I\) within budget with benefit \(\ge k\) is exactly a knapsack solution. The construction is polynomial.

Algorithm 20.3.5 (Priority-driven greedy inlining, as in GCC's inline_small_functions)

• Input: a call graph with estimated \(b(e)\), \(\Delta(e)\); unit-growth budget \(B\).
• Output: the edges inlined, in order.
• Precondition: estimates available for every edge (function summaries, Lesson 20.2).
• Postcondition: no remaining edge fits the budget or passes the per-edge limits.
• Invariant: the heap holds every candidate edge with its current badness; sizes reflect every inline done.

function GreedyInline(CG, B):
    H ← heap of edges keyed by badness(e) = −b(e) / Δ(e)     # smallest = best benefit per growth
    size ← Σ s(f)
    while H ≠ ∅:
        e ← extract-min(H)                                      # e : f → g
        if size + Δ(e) > B or not allowed(e): continue          # recursion, limits, attributes
        InlineCall(e); size ← size + Δ(e)
        for each edge e' out of the copy of g in f: insert e' with badness(e')
        for each edge e'' into f: update badness(e'')            # f grew
    return the inlined edges

Definition 20.3.6 (The course cost model: counted instructions)

For a call site \(c : g(a_1, \dots, a_k)\), let \(\mathit{Known}(p_i) = a_i\) when \(a_i\) is a constant. Walk \(g\)'s blocks in reverse postorder, only those reached along live edges from the entry; an instruction is free if it is a phi, ret, unconditional br, unreachable, a static alloca in the entry, or a lifetime/assume intrinsic; otherwise it folds if all its operands are constants or folded values and it is not a memory access or call (then it becomes constant, and is free), or it counts. A conditional branch or switch whose condition folds is free and makes only one successor edge live; otherwise it counts and all successor edges are live. A phi folds when every live incoming edge brings the same constant (an edge from a block not yet visited — a back edge — counts as unknown). The body cost is \(5 \times \lvert\text{counted instructions}\rvert\).

Definition 20.3.7 (Call-site savings and bonuses)

The savings of \(c\) are \(5k + 5 + 25\) (one instruction per argument, the call, LLVM's call penalty). The cost is body cost − savings, minus \(15\,000\) when \(g\) is internal and \(c\) is its only use (the last-call bonus: \(g\) will be deleted), unless the site is cold.

Definition 20.3.8 (Threshold and decision)

Start from the base threshold \(T\) (225). If \(g\) has inlinehint, \(T \gets \max(T, 325)\). With a profile: a hot site (\(\mathrm{count} > 0\) and \(10 \cdot \mathrm{count} \ge\) the largest block count) sets \(T \gets 3000\); a cold site (\(\mathrm{count} = 0\)) sets \(T \gets \min(T, 45)\) and disables every bonus. If exactly one block of \(g\) is reachable and bonuses are enabled, \(T \gets T + \lfloor T/2 \rfloor\). Inline iff \(g\) is alwaysinline, or \(g\) is not noinline, the call is not recursive (caller and callee in different SCCs), and \(\mathrm{cost} < \max(1, T)\).

The model on the running example

At fast: mode = 0, so %cmp = icmp eq i32 %mode, 0 folds to true, the branch is free, and only if.then and return are reached; if.then has one counted add. Cost \(= 5 \cdot 1 - (5 \cdot 2 + 5 + 25) = -35\); one reachable block? No — entry, if.then and return are reachable (three blocks), so no single-block bonus in the course model: \(T = 225\), and \(-35 < 225\): inline. (LLVM keeps its single-block bonus as long as every conditional branch it meets folds: threshold 337, same cost −35, §7.)

Algorithm 20.3.9 (Bottom-up inliner with a pluggable heuristic: pebble-inline)

• Input: a module; a heuristic \(H \in \{\mathrm{size}_N, \mathrm{cost}_T, \mathrm{profile}_{T,P}\}\).
• Output: the module with the chosen calls inlined and dead internal functions deleted.
• Precondition: SCCs in bottom-up order (Algorithm 20.2.3, all functions).
• Postcondition: every inlined call satisfied \(H\) when it was decided; semantics preserved (Theorem 20.3.2); no call between two functions of one SCC was inlined.
• Invariant: when function \(f\) is processed, all its callees in earlier SCCs have been fully processed (their bodies are final).

function BottomUpInline(M, H):
    for SCC X in bottom-up order:
        for f in X, f defined:
            sites ← the calls in f to defined functions, in order    # snapshot: new calls are not candidates
            for c in sites (callee g):
                if SCC(g) = X or g is interposable/noinline/varargs or not viable: keep c; continue
                if g is alwaysinline or Decide(H, c):   InlineFunction(c)
    delete every internal function without uses (repeat until none)

function Decide(H, c):
    size mode:     return countedInstructions(g, no folding) ≤ N
    cost mode:     return cost(c) < max(1, threshold(c))           # Definitions 20.3.6–20.3.8
    profile mode:  as cost mode, with hot/cold thresholds from the counts P of c's original block

Definition 20.3.10 (Inline advisor and learned policy)

An inline advisor is a function \(A(c, \mathrm{state}) \in \{\text{inline}, \text{no}\}\) consulted for each candidate \(c\), where \(\mathrm{state}\) is what the advisor has seen so far (e.g. the current module size). The default advisor is \(A(c) = [\mathrm{cost}(c) < \mathrm{threshold}(c)]\). A learned policy is \(A_\theta(c) = [\pi_\theta(\phi(c)) > 1/2]\) for a feature vector \(\phi(c) \in \mathbb{R}^d\) and a network \(\pi_\theta\); MLGO trains \(\theta\) to minimize \(\mathbb{E}[\mathrm{size}(\text{binary})]\) over a corpus, where the size is only known at the end of compilation — a reinforcement-learning problem with one delayed reward per module.

Algorithm 20.3.11 (MLGO: training and deployment)

• Input: a corpus of IR modules; the feature extractor \(\phi\); the default advisor (for warm start).
• Output: policy parameters \(\theta\), compiled into the compiler.
• Precondition: compiling a module with any policy is deterministic given \(\theta\) and the sampled decisions.
• Postcondition: the deployed policy's expected size on the corpus is at most the warm-start policy's (checked on held-out modules; not guaranteed on new code).
• Invariant: the compiler's mechanics (legality, alwaysinline, recursion rules) are unchanged; only the decision among legal candidates is learned.

function TrainMLGO(corpus):
    θ ← behavior-clone the default advisor                    # imitation warm start
    repeat for many iterations:
        for a batch of modules m:
            compile m, sampling each decision from π_θ; log (φ(c), decision) per site; R ← −size(m)
            compute the advantage of R over the default policy's size on m
        θ ← θ + α · policy-gradient(logs, advantages)          # or evolution strategies
    export π_θ as an ahead-of-time compiled function
function Deploy(c):                                             # MLInlineAdvisor::getAdviceImpl
    if not legal(c): return no
    return π_θ(φ(c)) > 1/2

3. Worked example

Classic inlining heuristics

The size heuristic (\(N = 12\), pebble-inline<size>) on scale: its unsimplified body has 14 counted instructions — the compare and conditional branch of entry, the add of if.then, the loop's compare and conditional branch, eight arithmetic instructions in the body and the increment (phis, ret and unconditional branches are free) — so neither call is inlined (size=14 limit=12): the size rule cannot see that fast's copy would shrink to one add. Priority-driven greedy (Algorithm 20.3.5) on the three calls of inl.c in GCC 14 (§7) inlines big.part.0.constprop (badness −2.50) before considering fib (badness −0.00005): the recursive fib has almost no benefit per unit of growth.

LLVM's InlineCost and inline advisor

The course model at both call sites (the drill's inline-decision computes the same numbers for its abstract callees; tests/ch20/lit/inline-cost.ll checks them on IR):

call site	reachable blocks	counted	body cost	savings	last-call bonus	cost	threshold	decision
fast: scale(x, 0)	entry, if.then, return	1 (add)	5	40	no (2 uses)	−35	225	inline
slow: scale(x, m), if it were decided first	all 10	14	70	40	no (2 uses)	30	225	inline
slow, decided after fast's call was inlined (the actual order)	all 10	14	70	40	yes (last use)	−14 970	225	inline

LLVM (box in §7) reports the same costs: −35 at fast, 30 at slow when both calls exist, and cost=-14970 in the remark for slow, because by then fast's call is gone and the last-call bonus applies. pebble-inline<cost;remarks> prints cost=-35 and cost=-14970 for the two decisions. The only difference is the threshold at fast: the course model sees three reachable blocks and gives no single-block bonus (225); LLVM keeps the bonus as long as every conditional branch it meets folds (337). Lowering -inline-threshold to −50 (threshold −75 after the single-block bonus) keeps both calls.

Try it

./course drill inline-decision --seed 5 --difficulty medium --solution — cost, threshold and decision for a random callee with a foldable branch; --difficulty hard adds hot and cold call sites.

ML-guided inlining (MLGO)

The features MLGO reads for the call fast → scale include what print<func-properties> prints (§7): scale has 9 basic blocks, 24 instructions, one loop of depth 1, 2 uses; fast has 1 block and 2 instructions; plus the call-site height (the caller's level in the call graph counted from the leaves, computed once per module in the MLInlineAdvisor constructor: 1 here, because fast's only callee scale calls nothing and has level 0), the number of constant arguments (1) and the default InlineCost estimate (−35). The released size policy is a function of exactly such a vector; this build of LLVM 23 ships without an embedded model, so asking for it fails (§7) — one reason MLGO is enabled per distribution, not by default.

Comparison-lab measurement

The lab compares the three heuristics of pebble-inline on seven C benchmarks (labs/ch20-inline/corpus), with the same cleanup pipeline after each; static is the number of IR instructions, dyn the number executed (from pebble-bbcount), calls the calls executed:

heuristic	inlined sites	static	dyn-instrs	dyn-calls
none	0	541	98 349 450	5 397 680
size (\(N = 12\))	37	568	87 388 931	1 824 657
cost (the course model, \(T = 225\))	54	569	82 430 638	300 008
profile (hot 3000, cold 45)	53	666	81 930 638	8

The cost model removes every call the size rule keeps in mode (a large callee whose mode argument folds) and interp (handlers inlined into the dispatch loop); the profile additionally inlines the hot mix in hot (cost 285 > 225, hot threshold 3000), at +93 static instructions, and refuses the cold error reporters in interp and hot that the static model inlined.

4. Invariants and correctness

Theorem 20.3.2 (semantics) and Theorem 20.3.4 (hardness) are the two correctness facts of inlining; the invariants below concern the procedures.

Proposition 20.3.12 (Bottom-up inlining terminates and inlines no recursion)

Algorithm 20.3.9 terminates, performs at most \(\sum_f \lvert\mathrm{sites}(f)\rvert\) inlines (the call sites that exist in the input), and never inlines a call whose callee is in the caller's SCC.

Proof

Each function is processed once, and only the call sites of its snapshot are candidates; each is inlined at most once (after inlining it no longer exists). The SCCs are those of the input; a call inside an SCC is rejected by the first test. Inlining a call to \(g\) (an earlier SCC) copies calls to functions in \(g\)'s SCC or earlier (Proposition 20.2.11), which are not candidates in this pass: no unbounded expansion.

Proposition 20.3.13 (The course cost model is monotone in the arguments)

Replacing a non-constant argument by a constant never increases the body cost of Definition 20.3.6.

Proof

More known values can only make more instructions fold and more branches fold. A folded branch makes a subset of the successor edges live, so the set of reached blocks can only shrink (by induction over the RPO walk, a block is reached only if some live edge enters it, and live edges only shrink). A phi that was constant stays constant or its block becomes unreachable. So the counted instructions are a subset of those before.

Inlining order is not innocent

Bottom-up order decides small callees first, in isolation: g may be inlined into f when inlining f into its single caller h would have been better and would have made g's call site constant-foldable. Scheifler's problem has no optimal order-based solution (Theorem 20.3.4), and LLVM also offers a module inliner with a global priority queue (-enable-module-inliner, ModuleInlinerPass), GCC's order is global by construction (Algorithm 20.3.5), and MLGO learns decisions in the given order.

Recursion and inline history

Inlining a recursive callee once is legal (it is not in the caller's SCC if the recursion is elsewhere) but copies its recursive call into the caller; inlining that copy again would unroll the recursion without bound. LLVM records an inline history per call site (the chain of callees it came from) and refuses to inline a call whose callee is already in its history; pebble-inline avoids the issue by not considering new call sites at all.

5. Complexity

\(\lvert g \rvert\) = instructions of the callee, \(c\) = call sites, \(B\) = budget.

Technique	Time (worst)	Time (typical)	Space	Justification
Size threshold	\(O(\sum_c \lvert g_c \rvert)\)	linear; sizes cached	\(O(1)\) per function	one count per callee
Greedy priority (GCC)	\(O(c \log c)\) heap operations + re-estimation	fast; estimates come from summaries	heap of edges	each edge inserted once per change of its caller/callee
LLVM InlineCost	\(O(\lvert g \rvert)\) per call site, stops at the threshold	sub-linear: the walk stops once cost ≥ threshold	simplified-value map	one pass over live blocks (Definition 20.3.6)
MLGO	feature extraction \(O(\lvert f \rvert + \lvert g \rvert)\) incremental + \(O(1)\) model evaluation	a few percent of compile time	a small model in the compiler	features are maintained incrementally by FunctionPropertiesAnalysis

Pathological family (code growth). Let \(f_0\) have \(s\) instructions and \(f_i\) call \(f_{i-1}\) twice, for \(i = 1, \dots, n\). If every call is inlined bottom-up, \(f_n\) ends with \(2^n s\) instructions: exponential growth from a linear program. The cost model stops this because \(f_i\)'s cost doubles at each level and soon exceeds the threshold; GCC stops it with its unit-growth budget (--param inline-unit-growth, 40 % by default in GCC 15, gcc/params.opt [GCC-Inline]). A size threshold bounds the growth per level but not the number of copies: it inlines every level \(i\) with \(2^{i-1} s \le N\), i.e. the first \(\lfloor \log_2(N/s) \rfloor + 1\) levels, at every call site of those levels.

At scale. On the lab corpus the three heuristics inline 37, 54 and 53 call sites; the profile heuristic grows the code by 23 % (541 → 666 IR instructions) to execute 17 % fewer instructions than no inlining and all but 8 of the 5.4 million calls (§3).

6. Variants and refinements

• Partial inlining (Lesson 20.4): inline only the fast path, outline the rest — the benefit of inlining with a fraction of the growth.
• Context-sensitive profile inlining (Lesson 20.10): with AutoFDO or CSPGO, the profile says which inlined copies were hot in the training binary; the inliner replays them (SampleProfileLoader inlines before the regular inliner).
• Cost–benefit analysis with profiles (-inline-enable-cost-benefit-analysis): LLVM compares cycle savings (profile counts × instructions removed) with size, instead of a threshold — closer to Scheifler's objective, needs good profiles.
• Priority-based module inliner (LLVM ModuleInlinerPass, -inline-priority-mode=size|cost|cost-benefit|ml): a global order instead of bottom-up; trade-off: better choices, worse compile-time locality.
• Inlining for size (-Oz): threshold 5 (OptMinSizeThreshold), and MLGO's size policy — which reported a few percent smaller binaries than the heuristic on Google's production code [TQY+21].
• JIT inlining (HotSpot, V8): inline based on observed receiver types and invocation counts, deoptimize if the assumption breaks — speculation the static compilers of this chapter only do with profiles (Lesson 20.7).

7. In real compilers

Classic inlining heuristics

GCC: gcc/ipa-inline.cc — inline_small_functions is Algorithm 20.3.5 over a Fibonacci heap; edge_badness computes the key from estimate_edge_growth and estimate_edge_time (function summaries of ipa-fnsummary.cc); want_inline_small_function_p applies the per-edge limits (max-inline-insns-single, -auto) [GCC-Inline]. GCC also inlines tiny functions early (early_inliner) and partially inlines (ipa-split, Lesson 20.4).

GCC's badness-ordered inliner

Reproduce (gcc 14.2.0, Ubuntu 24.04 package gcc-14; inl.c below):

cat > inl.c <<'EOF'
int printf(const char *, ...);
static int sq(int x) { return x * x; }
static int big(int x, int mode) {
  if (mode == 0) return x + 1;
  int s = 0;
  for (int i = 0; i < x; i++) { s += i * mode; s ^= (s >> 3); s += sq(i); if (s > 1000) s -= 997; }
  return s;
}
static int once(int x) { return x * 3 + 1; }
int fib(int n) { return n < 2 ? n : fib(n - 1) + fib(n - 2); }
int main(void) {
  int t = 0;
  for (int i = 0; i < 10; i++) t += sq(i) + big(i, 0) + big(i, 2);
  printf("%d %d %d\n", t, once(4), fib(10));
  return 0;
}
EOF
gcc-14 -O2 -fdump-ipa-inline-details -c inl.c
grep -E 'enqueuing|Considering|Estimated badness|optimized:  Inlined' inl.c.*i.inline

Output:

  enqueuing call main/4 -> big.part.0.constprop/10, badness -2.500275
  enqueuing call fib/3 -> fib/3, badness -0.000051
Considering big.part.0.constprop/10 with 15 size
 Estimated badness is -2.500275, frequency 10.00.
optimized:  Inlined big.part.0.constprop/10 into main/4 which now has time 1050.566856 and size 30, net change of -7.
Considering fib/3 with 12 size
 Estimated badness is -0.000051, frequency 0.90.
inl.c:10:37: optimized:  Inlined fib/12 into fib/3 which now has time 85.003535 and size 60, net change of +48.

What to notice: the heap pops the edge with the smallest (most negative) badness first; big's call in the loop (frequency 10) saves much time per unit of growth, fib's self-call almost none — yet it still fits the budget, and GCC recursively inlines one copy of fib into itself (a clone fib/12, bounded by --param max-inline-recursive-depth); LLVM refuses this: isInlineViable rejects any callee that calls itself. The callee is already big.part.0.constprop: earlier IPA passes split big (partial inlining) and cloned it for the constant mode = 2 (ipa-cp) — Lesson 20.4.

LLVM's InlineCost and inline advisor

LLVM: llvm/lib/Analysis/InlineCost.cpp — CallAnalyzer::analyze walks the callee's live blocks, InlineCostCallAnalyzer::updateThreshold applies the hint, hot/cold and bonus rules, getCallsiteCost computes the savings of Definition 20.3.7, isInlineViable checks the conditions of Theorem 20.3.2 [LLVM-InlineCost]; llvm/lib/Analysis/InlineAdvisor.cpp — DefaultInlineAdvisor::getAdviceImpl wraps it [LLVM-InlineAdvisor]; llvm/lib/Transforms/IPO/Inliner.cpp — InlinerPass::run is the CGSCC driver with the inline history [LLVM-Inliner]; llvm/lib/Transforms/Utils/InlineFunction.cpp — InlineFunction does Definition 20.3.1.

InlineCost on the running example, and the threshold knob

Reproduce (clang 23.1.2, opt 23.1.2; scale.c as in the introduction):

clang-23 -O1 -Xclang -disable-llvm-passes -fno-discard-value-names -S -emit-llvm scale.c -o - | opt -passes=sroa -S -o scale.ll
opt -passes='print<inline-cost>' -disable-output scale.ll 2>&1 | grep -E 'Analyzing|NumInstructions|Cost:|Threshold:'
for t in 225 20 -50; do echo "== -inline-threshold=$t"; opt -passes=inline -inline-threshold=$t -pass-remarks=inline -pass-remarks-missed=inline -disable-output scale.ll 2>&1; done

Output:

      Analyzing call of scale... (caller:fast)
      NumInstructionsSimplified: 5
      NumInstructions: 6
      Cost: -35
      Threshold: 337
      Analyzing call of scale... (caller:slow)
      NumInstructionsSimplified: 10
      NumInstructions: 24
      Cost: 30
      Threshold: 225
== -inline-threshold=225
remark: <unknown>:0:0: 'scale' inlined into 'fast' with (cost=-35, threshold=337)
remark: <unknown>:0:0: 'scale' inlined into 'slow' with (cost=-14970, threshold=225)
== -inline-threshold=20
remark: <unknown>:0:0: 'scale' inlined into 'fast' with (cost=-35, threshold=30)
remark: <unknown>:0:0: 'scale' inlined into 'slow' with (cost=-14970, threshold=20)
== -inline-threshold=-50
remark: <unknown>:0:0: 'scale' not inlined into 'fast' because too costly to inline (cost=-35, threshold=-75)
remark: <unknown>:0:0: 'scale' not inlined into 'slow' because too costly to inline (cost=30, threshold=-50)

What to notice: at fast the analyzer visits only 6 of scale's 24 instructions (the folded branch makes the loop unreachable) and the cost is −35, the course model's value; the single-block bonus stays (+50 %: 337). At slow nothing folds and the bonus is withdrawn (225). After fast's copy is made, slow's call is the last use of the internal scale: \(30 - 15\,000 = -14\,970\). With -inline-threshold=-50 even the last-call bonus is not applied, because the first decision already fails and both calls remain.

ML-guided inlining (MLGO)

LLVM: llvm/lib/Analysis/MLInlineAdvisor.cpp — MLInlineAdvisor::getAdviceImpl fills the feature tensors (FeatureIndex::callsite_height, node_count, nr_ctant_params, and the others listed in InlineModelFeatureMaps.h) and asks the model runner [LLVM-MLAdvisor]; the model is compiled in only when LLVM is built with LLVM_HAVE_TF_AOT and a model path, or run interactively over pipes (-inliner-interactive-channel-base) for training [LLVM-MLGO].

MLGO's features, and what happens without a model

Reproduce (opt 23.1.2 from conda-forge; scale.ll from the previous box):

opt -passes='function(print<func-properties>)' -disable-output scale.ll 2>&1 | sed -n '/scale/,/^$/p'
opt -passes='scc-oz-module-inliner' -enable-ml-inliner=release -disable-output scale.ll

Output:

Printing analysis results of CFA for function 'scale':
BasicBlockCount: 9
BlocksReachedFromConditionalInstruction: 4
Uses: 2
DirectCallsToDefinedFunctions: 0
LoadInstCount: 0
StoreInstCount: 0
MaxLoopDepth: 1
TopLevelLoopCount: 1
TotalInstructionCount: 24

error: Could not setup Inlining Advisor for the requested mode and/or options

What to notice: FunctionPropertiesAnalysis is the incremental feature source of the ML advisor (block and instruction counts, loop depth, uses); the release-mode advisor needs a model compiled into the tool, and this LLVM build has none, so the pipeline refuses to start rather than silently falling back — the policy is a build-time choice of the toolchain vendor.

Find where LLVM does it. Open llvm/lib/Analysis/InlineCost.cpp and find the function that returns the default bonus for inlining the last call to a local function (hint: it is a TTI hook used in updateThreshold). Which value does the default TTI implementation return? (Quiz llvm-where-last-call-bonus.)

8. Comparison

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Classic heuristics (size threshold; GCC badness priority)	Size: blind to call-site facts; priority: global benefit/growth order	\(O(c)\) / \(O(c \log c)\) · cheap	Predictable; GCC's dumps explain every decision	Low / medium (needs summaries)	-O1-style inliners, GCC's IPA inliner, pebble-inline<size>
LLVM InlineCost + advisor	Per call site, simulates folding with the actual arguments; bonuses and profile thresholds	\(O(\lvert g \rvert)\) per site, early exit · the dominant IPO cost at -O2	Remarks with cost and threshold (-pass-remarks=inline)	High (every instruction kind, bonuses)	LLVM default<O2>, pebble-inline<cost> / <profile=…>
MLGO	Learned from whole-binary outcomes; not tied to one cost formula	Model evaluation \(O(1)\) · features incremental	Hard to explain an individual decision	High (training infrastructure), low to deploy	-Oz builds with a released model (Chrome, Android, Fuchsia toolchains)

Choose a size threshold when compile time matters most or as the -O1 baseline. Choose a cost model with simplification when callees have constant arguments or branches that fold at their call sites — most real code — and add profile thresholds when you have profiles. Choose MLGO when you own a large, stable corpus and a size (or speed) objective to optimize, and can ship a model with your compiler.

The lab (labs/ch20-inline, §3 table): cost model 54 inlines vs size 37, 16 % fewer executed instructions than no inlining vs 11 %; profile-guided −17 % at +23 % code size.

9. Assessment

• Quiz (./course quiz 20): inline-knapsack, inline-size-rule (tag inline-classic); inline-cost-lastcall, llvm-where-last-call-bonus (tag inline-llvm); mlgo-reward, mlgo-features (tag mlgo).
• Drill: ./course drill inline-decision (easy: cost and threshold; medium: folding, bonuses, attributes; hard: hot and cold call sites). MLGO has no drill: its policy is a trained network, not a procedure to trace; the quiz asks about its training signal and features.
• Flashcards: tags inline-classic, inline-llvm, mlgo.
• Exercises: E2 pebble-inline and lab part B (labs/ch20-inline/SPEC.md).

References

See the chapter references.