Understanding and exploiting optimal function inlining

Function inlining — pasting a called function's body into the caller — is one of a compiler's most consequential decisions, but which of a program's thousands of call sites to inline is a two-to-the-N choice (SPEC's gcc has 2^11213 configurations) whose effects cascade unpredictably through the rest of the optimizer, so compilers just use hand-tuned heuristics and nobody knew how far those sat from optimal; this ETH Zurich work (an ASPLOS Best Paper) makes OPTIMAL inlining computable for the first time by proving that call-graph bridges split the problem into independent pieces — shrinking the search from 2^349 to 2^25 — then exhaustively finds the size-optimal inlining for 1,135 SPEC files, shows LLVM misses it in over half of them and is systematically too eager to inline, discovers that optimal inlining is mostly LOCAL, and turns that into a linear-cost greedy autotuner that beats LLVM's binary size by 7% on average and up to 28%.

The argument in one glance

Problem

Inlining is a core compiler decision, and nobody knew how good it could be

Function inlining replaces a call with the body of the function it calls. It is one of the most important transformations a compiler makes: it removes call overhead and, more importantly, exposes the callee's code to the caller's context so later optimizations (dead-code elimination, constant propagation) can fire. But it is a double-edged decision — inlining can also bloat the binary by duplicating code — and choosing which call sites to inline is genuinely hard, because the choices INTERACT: inlining one call can make inlining another beneficial or harmful through cascading effects in the rest of the optimization pipeline. Compilers handle this with decades-old hand-tuned heuristics, and here is the uncomfortable truth the paper confronts: because the optimum was uncomputable, nobody knew how far those heuristics were from the best possible.
What people did

Tune a heuristic, or try to search the space

Two approaches exist. Production compilers like LLVM use a HEURISTIC inliner: a cost model with tuned thresholds that estimates whether inlining a given call is worth it, applied greedily. Researchers who want to do better reach for SEARCH — autotuning that tries different inlining configurations and keeps the best. Either refine the cost model by hand, or throw compute at exploring configurations, and hope you land near a good answer.
Why it fell short

The search space is 2-to-the-N, so optimal was simply unknown

Search does not scale, because the space of inlining configurations is 2 raised to the number of inlinable call sites. The SPEC2017 gcc benchmark has 2^11213 configurations spread across its files — more than there are atoms in the universe, uncountably infeasible to explore. So no one could compute the OPTIMAL inlining for a real program, which means no one could answer the basic scientific questions: how far is LLVM's heuristic from optimal? Does it inline too much or too little? Is optimal inlining a global tangle or something with exploitable structure? Without the optimum as a yardstick, inlining research was tuning heuristics in the dark, unable to measure the gap it was trying to close.
This paper's idea

Split the problem at bridges, compute the optimum, then exploit its locality

This ETH Zurich work (Theodoridis, Grosser, and Su — an ASPLOS Best Paper) makes optimal inlining computable. The key is a decomposition: connected components of the call graph are independent for inlining, and NOT inlining a "bridge" edge (one whose removal disconnects the graph) is identical to deleting it, splitting the graph into more independent components. Recursively partitioning along bridges collapses the search from 2^349 to 2^25 on real files, enough to EXHAUSTIVELY find the size-optimal inlining for 1,135 SPEC2017 files in hours. The study then reveals the gap (LLVM misses optimal in 609 of 1,135 files and is too eager to inline) and, crucially, that optimal inlining is mostly LOCAL — inlined call chains are short. That locality justifies a linear-cost greedy autotuner that captures 81% of optimal and shrinks binaries 7% below LLVM on average, up to 28%.

Why this problem is worth solving

Inlining sits upstream of much of what a compiler does, so getting it right ripples through every later optimization — and getting it wrong wastes space or misses speedups. The reason it resists a clean solution is that

the benefit of inlining one call depends on which other calls are inlined, and on everything the rest of the compiler does afterward. Inlining a callee exposes its code to the caller, which may let constants propagate in, dead branches be deleted, or loops be fused — but whether those payoffs materialize can depend on whether some OTHER call was also inlined first. So the decisions are not independent knobs you can set one at a time; they form a tangled combinatorial problem where the value of each choice is contingent on the others and on downstream passes. This is why a simple per-call cost model is fragile: it judges each call in isolation, but the real value of inlining a call is a property of the whole configuration

, which is exactly what makes the problem both important and hard. A compiler that inlines well produces smaller, faster code across the board; one that inlines badly pays for it everywhere.

The deeper obstacle, and the one this paper removes, is that the optimum was literally uncomputable, so the field had no yardstick. The trouble is the

the fact that with n inlinable call sites, there are 2-to-the-n possible inlining configurations — every call site is either inlined or not, and the choices combine. For the SPEC2017 gcc benchmark that is 2^11213 configurations, a number so vast that exhaustively compiling and measuring each is not merely slow but physically impossible. Because of this, prior work could compare heuristics against each other, but never against the true best, so basic questions had no answer: is LLVM near-optimal or far from it? Does it systematically inline too much or too little? Is the optimal inlining for a program a global puzzle, or does it have local structure a cheap algorithm could exploit

. Answering those questions requires making the optimum computable, and the payoff of doing so is twofold: a scientific understanding of what good inlining actually looks like, and a practical yardstick against which any heuristic can finally be measured and beaten. The paper delivers both by focusing on binary SIZE — a deterministic metric that, unlike speed, does not depend on program inputs — which makes “optimal” a well-defined, reproducible target to compute.

What people did before, and where it broke

LLVM’s heuristic inliner (-Os / -Oz for size). A tuned cost model with thresholds, applied greedily per call. Fast and general, but the study shows it finds the size-optimal configuration in only 526 of 1,135 files, with a median 2.37% size overhead on the rest (up to 281%), and a systematic bias toward inlining too much.
Autotuning by searching configurations. Try many inlining configurations and keep the smallest. The right idea, but the 2-to-the-n space makes naive search hopeless on real programs, so prior autotuners could only sample a vanishing fraction and never knew how close to optimal they were.
Machine-learned inlining policies. Train a model to predict good inlining decisions. Promising, but without a computable optimum there was no ground truth to learn from or evaluate against — you could imitate an existing heuristic, not the best possible.
Per-call cost models in general. Judge each call site in isolation. Structurally unable to capture that inlining decisions interact — the value of a call depends on the whole configuration and on downstream passes — so they misjudge exactly the cases where inlining pays off jointly or not at all.
The gap. No one could compute optimal inlining for real programs, so no one could measure the heuristic gap, characterize what optimal looks like, or build an autotuner that provably approaches it. This paper makes the optimum computable, uses it as a yardstick, and exploits its structure — closing all three.

How the method works

Model on the call graph, split at bridges, compute the optimum, then autotune

Model inlining as choices on the call graph

Each inlinable call site is an edge in the call graph; an inlining configuration is a subset of edges to inline. The naive search space is 2 raised to the number of edges — 2^11213 for a single benchmark — which is why exhaustive evaluation looked impossible.
↓ →
Find the bridges new

A bridge is a call-graph edge whose removal disconnects the graph. The key observation: NOT inlining a bridge is identical to DELETING it as far as inlining is concerned, because with that call left as a call, the two sides can no longer share any cross-call optimization — so the graph splits into independent components that can be optimized separately.
↓ →
Recursively partition into an inlining tree new

Build a tree where each node decides inline-or-not for a bridge; each decision cleaves the graph into independent subproblems that are searched separately and their results combined. A heuristic picks bridges near central, high-degree vertices to split the problem as evenly as possible, minimizing evaluations.
↓ →
Exhaustively compute the OPTIMUM new

With the space collapsed (the largest single reduction is 2^349 to 2^10; across 1,186 files about 2^349 to 2^25), it becomes feasible to actually compile and measure every remaining configuration and find the size-optimal inlining for 1,135 SPEC2017 files — a few hours on a 64-core Threadripper. For the first time there is a ground-truth optimum to compare against.
↓ →
Measure the gap and the structure new

Against optimal, LLVM is exactly right in 526 files and suboptimal in 609, is systematically too eager (it inlines 69.4% of calls where optimal inlines only 49.3%), and — the pivotal finding — optimal inlining is mostly LOCAL: the most common inlined call-chain length is 1, and long chains are rare, so good size decisions can be made in a local scope.
↓ →
Exploit locality with a greedy autotuner new

Because optimal is local, a simple greedy autotuner works: from a clean slate (nothing inlined), try inlining each edge alone, keep it if the binary shrinks, revert otherwise — just n+2 compilations, LINEAR in call sites. A multi-round variant, re-seeding with the previous round's result, catches the cases where several edges must be inlined together to trigger dead-code elimination.

Evaluated on 1,135 SPEC2017 C/C++ files (optimal study) and on SPEC2017, the LLVM codebase (3.6M lines), and SQLite (x86 and WASM) for the autotuner, all against LLVM 11's size-optimizing modes. Optimal search took a few hours on a 64-core AMD Threadripper 3990X.

The idea

Make the optimum computable, and it becomes a yardstick that changes what you can know. The whole field had been tuning inlining heuristics without ever seeing the best possible answer, because the 2-to-the-n space forbade it. This paper’s first and deepest contribution is not an algorithm but a measurement made possible: by computing true optimal inlining, it can finally ask how far LLVM is from best (suboptimal in 609 of 1,135 files), in which direction it errs (too eager, inlining 69% where optimal inlines 49%), and whether optimal has structure. Establishing the oracle before optimizing against it is a discipline the site values — you cannot know how much you are leaving on the table until you can see the table — and here it converts inlining from heuristic folklore into something measurable.

Find the independence hiding in the dependency tangle. The optimum is computable only because the seemingly-global problem decomposes. A call that is NOT inlined is a wall: no optimization crosses it, so the program on either side of an un-inlined bridge becomes two independent inlining problems. Recursively splitting along bridges turns one intractable 2^349 search into many tiny independent ones totaling 2^25 — an astronomically smaller space. This is the exploit-independence-to-decompose move the site keeps meeting: the replicated-simulation page makes partitions independent by replicating their overlap, the spiking-network page cuts along a locality-preserving curve, and here the call graph’s own bridges hand you the cut for free. The art is recognizing that a problem which looks globally coupled is, along the right seams, a union of separable pieces.

Measure the shape of the optimum, then build the algorithm it implies. The exhaustive study is not just a scoreboard — it reveals that optimal inlining is LOCAL: inlined call chains are overwhelmingly short. That empirical fact is a design directive. If good decisions live in a local scope, you do not need global search; a greedy pass that considers each call once and keeps it only if the binary shrinks will capture most of the benefit, at linear cost. The autotuner (n+2 compilations, embarrassingly parallel) is exactly that algorithm, and it captures 81% of optimal where LLVM captures 46%. This is the science-then- engineering arc the site admires: study the structure of the ideal solution, and let what you find dictate a cheap method that matches it — the same match-the-method-to-the-landscape logic behind design-space autoschedulers, here grounded in a measured law about where good inlining lives.

From an impossible search to a linear autotuner

Why optimal inlining turned out to be reachable

Deciding inlining for a program's call graph. Numbers from the paper's study of 1,135 SPEC2017 files.

Step 1 of 5

Thousands of call sites, 2-to-the-N choices

Each inlinable call is a yes-or-no decision, and the decisions interact — inlining one call can change whether inlining another helps. So the configuration space is 2 raised to the number of call sites, which for the gcc benchmark is 2^11213. You cannot compile and measure them all, and judging each call in isolation misjudges the joint effects, which is why heuristics are fragile.

the value of inlining a call is a property of the whole configuration, not the call alone
prior work could compare heuristics to each other, but never to the true optimum

Why it works

Inlining decisions interact, so a per-call cost model misjudges joint effects → but a NOT-inlined call blocks all cross-call optimization → the program splits at un-inlined bridges into genuinely independent subproblems.
Bridges are edges whose removal disconnects the call graph → recursively partitioning along them turns one 2^349 search into many tiny independent ones (about 2^25 total) → the optimum becomes exhaustively computable for the first time.
A computable optimum is a yardstick → measuring LLVM against it reveals a 609-of-1,135 suboptimality, a consistent over-inlining bias, and the locality of good decisions → the field can finally see and characterize the gap.
Optimal inlined call chains are overwhelmingly short (length 1 dominates) → good size decisions live in a local scope → a greedy pass that keeps each inline only if the binary shrinks captures most of the benefit at linear cost.
The autotuner asks the compiler directly (does the binary get smaller?) instead of trusting a cost model → so it is immune to the model errors that make LLVM over-inline → it captures 81% of optimal where LLVM captures 46%.

What it costs

Size, not speed. The whole approach rests on optimizing a DETERMINISTIC metric (binary size). Performance optimality depends on program inputs and on second-order hardware effects (instruction-cache pollution) the call-graph model does not capture, so the method does not directly transfer to tuning for speed.
Greedy misses joint inlinings. A single greedy round cannot find configurations where several non-adjacent edges must be inlined together to unlock an optimization; the multi-round variant helps but multiplies the number of compilations.
Autotuning is slow on huge files. It is linear, but the constant is a full compile per edge: a single round on the LLVM source takes 44 to 53 hours, and files with tens of thousands of calls (one has 55,156) can take over 4 hours each.
Per-file, not whole-program. Calls across source files are resolved at link time and cannot be inlined here, so the study works on per-file call graphs and does not capture cross-module inlining opportunities.
The decomposition leans on a heuristic. Choosing which bridges to split on affects how much the search shrinks; the chosen heuristic is empirically effective, but a poor choice could in principle force exploration of the full 2-to-the-n space.

The evaluation

An exhaustive optimal-inlining study on 1,135 SPEC2017 C/C++ files (the first computable ground truth), plus the greedy autotuner evaluated on SPEC2017, the 3.6-million-line LLVM codebase, and SQLite (x86 and WebAssembly), all measured against LLVM 11’s size-optimizing modes.

Three ways to decide function inlining

Property	LLVM heuristic (-Os)	Naive exhaustive search	This work (bridge-decomposed + greedy autotuner)
How it decides
Feasible on real programs?
Fraction of optimal found
Inlining tendency		Whatever is optimal
Binary size vs LLVM -Os		Optimal (unreachable)

Optimizing for size costs only a 2% median (3.6% average) runtime overhead, and the overhead is measurable rather than assumed. The autotuner needs no cost model — it compiles and measures, letting the real toolchain judge each decision — which is why it sidesteps the systematic biases of a hand-tuned heuristic.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The results are about binary SIZE, chosen precisely because it is deterministic and input-independent; extending the approach to PERFORMANCE is explicitly out of reach, because speed-optimality depends on program inputs and on hardware second-order effects (instruction-cache pollution) that a call-graph model cannot represent. The greedy autotuner’s power comes from the measured locality of optimal inlining, so it inherits that assumption’s limits: a single round cannot discover configurations where several non-adjacent calls must be inlined together, and while multi-round rounds help, they cost more compilations. The tuner is linear in call sites but each step is a full compile, so it can take dozens of hours on very large files, and it operates per file (cross-module calls are resolved at link time and left alone). The bridge-decomposition that makes the optimum computable also relies on a bridge-selection heuristic that is effective in practice but not guaranteed to shrink every graph. None of this diminishes the core achievement — making optimal inlining computable turned a heuristic tuned in the dark into a measurable problem, revealed that production inliners are systematically too eager and that good inlining is local, and turned that understanding into a simple autotuner that beats a mature compiler on real, large codebases.

Background

Compute the optimum to see the gap, then let the optimum's shape design your algorithm

This paper sits in the site’s compiler-and-optimization cluster and rhymes with several ideas covered elsewhere on this site. Its first move is one the site does not see often and prizes when it does: establish the true optimum as a yardstick before trying to beat it. Because the 2-to-the-n space made optimal inlining uncomputable, the whole field had been tuning heuristics without ever seeing best-possible; making the optimum computable is what lets the paper measure the gap (LLVM suboptimal in 609 of 1,135 files) and catch a systematic bias (over-inlining) — the same know-the-ground-truth-before-you-optimize discipline that separates measuring the true cost from trusting a proxy. Its second move is the exploit-independence-to-decompose approach the site meets repeatedly: an un-inlined bridge splits the program into separable subproblems, exactly the way the replicated-RTL-simulation page replicates a partition’s overlap to make threads independent, the spiking-network-mapping page cuts along a locality-preserving curve, and the heterogeneous-serving page carves a cluster with a graph cut — a globally-coupled problem revealed as a union of pieces along the right seams. Its third move is the science-then- engineering arc: measuring that optimal inlining is LOCAL, then building a linear greedy autotuner that matches that structure, which is the match-the-method-to-the-landscape logic the design- space autoscheduling pages share, here grounded in a measured law rather than a guess. And in optimizing binary size directly by asking the compiler rather than a cost model, it is the same skip-the-proxy-and-measure-the-real-thing instinct that runs through the whole site.

If you remember only three things

1. Function inlining is one of a compiler's most consequential decisions, but choosing which of a program's call sites to inline is a 2-to-the-number-of-call-sites problem (over 2^11000 for a single SPEC benchmark) whose effects cascade unpredictably through the rest of the optimizer, so compilers use hand-tuned heuristics and — because the optimum was uncomputable — no one knew how far those heuristics sat from the best possible.
2. This ETH Zurich work makes optimal inlining computable by exploiting a decomposition: an un-inlined call blocks all cross-call optimization, so not inlining a call-graph BRIDGE (an edge whose removal disconnects the graph) splits the program into independent subproblems, and recursively partitioning along bridges collapses the search from 2^349 to 2^25 — enough to exhaustively find the size-optimal inlining for 1,135 SPEC2017 files in hours, revealing that LLVM misses optimal in 609 of them, is systematically too eager (inlining 69.4% of calls where optimal inlines 49.3%), and that optimal inlining is mostly LOCAL (inlined chains are short).
3. That locality justifies a greedy autotuner — from a clean slate, try each edge alone and keep it only if the binary shrinks, just n+2 compilations, linear and embarrassingly parallel — which captures 81% of optimal (versus LLVM's 46%) and beats LLVM -Os by 7% on average and up to 27.6% on SPEC, 15.21% on LLVM's own source, and about 10% on SQLite, at a measured 2% median runtime cost. The durable lessons: compute the optimum to see the gap you are trying to close, find the independence hiding in a coupled problem, and let the measured shape of the ideal solution design your algorithm.

Check yourself

Check your understanding

1. The paper's central enabling move is making OPTIMAL inlining computable, even though the configuration space is 2-to-the-N. Predict why computing the optimum matters so much, beyond being a technical feat.
2. The optimum becomes computable because NOT inlining a "bridge" edge splits the call graph into independent components. Predict why an un-inlined call creates independence, and why that collapses the search space so dramatically.
3. The exhaustive study finds that optimal inlined call chains are mostly SHORT (length 1 dominates), and the authors then build a simple greedy autotuner. Predict the connection between the finding and the algorithm.
4. The greedy autotuner keeps an inlining only if it actually shrinks the compiled binary, rather than consulting a cost model like LLVM does. Predict why measuring directly is what lets it beat a mature, heavily-tuned heuristic.

Sources

ACM DL: Understanding and Exploiting Optimal Function Inlining — ASPLOS 2022 (Best Paper; full text read via the author-hosted ETH PDF; no arXiv preprint).
Artifact (Zenodo, DOI 10.5281/zenodo.5848986) — open-source tooling and data for the study.