Inlining Decisions and the Cost Model Behind Them

Inlining replaces a call with a copy of the callee’s body. Mechanically it is the simplest interprocedural transformation: splice the body, bind the parameters to the arguments, map the return values onto the call’s result. Deciding when to do it is the hard part, because the transformation has no local cost model — its benefit appears in other passes, and its cost appears in the instruction cache.

The shape of the decision is a profitability estimate. A compiler computes some number for a call site, compares it against a threshold, and inlines if the number is below. Every production compiler does this, and the numbers differ so much between them that the decision is best understood as a policy rather than an algorithm.

What inlining actually buys

Four benefits, in rough order of how often they justify the transformation.

Constant argument propagation. If a call passes a literal, inlining makes the literal visible to the callee’s optimizer. A function scale(x, n) called with n = 4 can have its multiply replaced by a shift after inlining, which is impossible when the callee is compiled once for all callers. This is the largest of the four for a callee whose parameters are usually literals, and it is the same mechanism Constant Propagation over a Flat Lattice exploits once the values are visible in one procedure.

Removal of call overhead. Saving and restoring registers, adjusting the stack, and the call and return instructions themselves cost on the order of tens of cycles on common architectures. That is a real saving for a small callee called from a hot loop and negligible for a large callee called once.

Enabling further optimization across the boundary. After inlining, the callee’s body is inside the caller’s control flow, so the caller’s loop transformations, common subexpression elimination, and scheduling can work on it. A load inside the callee can be hoisted out of a caller’s loop only after the callee is inlined.

Exposing the callee’s effects. An inlined callee has no opaque memory effects from the caller’s point of view; the compiler sees exactly which stores it performs. This improves the alias information available to later passes, which is what allows stores to be reordered around it.

What it costs

Code size, primarily. Each inlined copy duplicates the callee’s instructions, and a callee inlined at ten sites is ten copies. The instruction cache on common x86-64 and AArch64 cores is 32 KiB per core, holding roughly a few thousand instructions, so a hot function that grows past that budget starts missing in the instruction cache on every call. That cost is invisible in instruction counts and shows up only in execution time.

Compile time. Inlining is the main driver of superlinear compile time in aggressive settings, because each inlining decision enlarges the input to every subsequent pass on that function. A recursive inlining chain can blow up the size of a single function by orders of magnitude if it is not bounded.

Loss of the callee as an optimization unit. A callee compiled once and called from twenty sites is optimized once. Inlined twenty times, it is optimized twenty times, possibly with different constant arguments and therefore different results — which is the point, but also means the compiler cannot share the work.

Debug information degradation. Inlined frames must be represented in the debug info as inlined subroutines with their own line tables; compilers that inline aggressively without emitting that information make stack traces and single-stepping worse. DWARF’s DW_TAG_inlined_subroutine exists for this, and a compiler that emits it correctly keeps the source-level view intact.

The cost model, concretely

A typical model assigns the callee a size in some normalized unit — instructions, IR nodes, or an estimate of the final machine code bytes — and compares it against a threshold scaled by the call site’s expected frequency.

The simplest form is: inline if callee_size < threshold, where the threshold is a policy constant that differs between compilers by a wide margin, with a separate, much larger threshold for call sites marked with an explicit always-inline attribute, or for callees with a single call site. Single-call-site inlining is nearly always profitable, because the callee has no other copy and its body would otherwise be emitted once anyway; the only cost is the loss of a separately compiled function, which matters for debug builds and for symbol interposition.

The next refinement multiplies by frequency. With profile data, a call site executed on most runs gets a larger budget than one executed once. Without profile data, compilers use static heuristics: calls inside loops are hot, calls in cold blocks after an error check are cold, and calls in functions that are themselves small are more likely to be hot. The heuristics are weak individually and useful in aggregate.

A third refinement accounts for what inlining enables. If the callee’s parameters are all bound to constants at this site, the model adds a bonus large enough to inline almost anything, because the resulting constant propagation usually deletes most of the body. If the callee contains a loop whose trip count becomes constant after inlining, the bonus is larger still. This is the mechanism behind “aggressive inlining” as described by Ayers and colleagues: the decision is made by estimating the post-inlining size, not the pre-inlining size, on the theory that inlining plus constant folding usually shrinks the code.

/* A representative shape. The constants are policy, not physics. */
bool worth_inlining(call_site *cs) {
    int cost = callee_size(cs->callee);
    if (cs->callee->always_inline) return true;
    if (cs->callee->call_count == 1)  return true;      /* no duplicate copy */
    if (cs->is_indirect)              return false;      /* target unknown */
    cost -= constant_arg_bonus(cs);                      /* folding will shrink it */
    cost -= loop_trip_count_bonus(cs);
    return cost <= inline_threshold * frequency_factor(cs);
}

The ordering problem

Inlining decisions are not independent, and the order in which a compiler considers call sites changes the result. Bottom-up inlining processes callees before callers, so a small function is inlined into its caller and the caller’s size — now including the inlined body — is what the caller’s own callers see. Top-down inlining processes callers first, which lets a hot caller’s budget be spent on its callees before their bodies are themselves expanded.

Both orders have failure modes. Bottom-up can inline a small helper into a medium function, making the medium function too large to inline into its hot caller — the transformation that mattered was blocked by one that did not. Top-down can spend a caller’s budget on a callee that is itself a wrapper around something expensive, so the expansion is large and the constant propagation never happens.

Production compilers typically run several rounds, alternating direction, with a global size budget on the whole module or on each function. The budget is the safety valve: it bounds the total growth regardless of what the per-site decisions do, and it is what prevents pathological cases like mutually recursive functions that each inline the other.

Recursion, indirect calls, and other refusals

Recursion needs a depth limit rather than a size limit, because the size test never terminates. The usual rule is to allow inlining a recursive call only if the callee is already being inlined at that site, up to a small depth such as one or two levels, or to refuse entirely unless the call site has a constant argument that lets the compiler prove the recursion terminates — a proof compilers generally do not attempt.

Indirect calls are refused by default because the callee is unknown. Devirtualization first, then inlining of the now-direct target, is the standard order; without it, a call through a function pointer in a hot loop stays opaque. This is where profile data earns its keep, since a call site that is monomorphic in practice can be speculated, and speculation is the subject of Profile-Guided Optimization and Hot-Cold Code Splitting.

Calls to functions with variadic arguments, calls that must preserve a specific calling convention, and calls to functions whose address is taken and compared are refused or handled specially. The last case matters because inlining changes the function’s address identity, so a program that compares function pointers would observe a difference; compilers either refuse or emit both an out-of-line copy and the inlined body.

Interaction with the analyses

Inlining invalidates every analysis whose result depended on the call boundary. Alias information must be recomputed because the inlined body’s memory effects are now visible; constant propagation must be re-run because the point of inlining is to expose constants; liveness and the interference graph must be rebuilt because the caller now has more live values. A pass order that inlines late, after allocation, gets little benefit; one that inlines early pays for re-analysis.

The analyses that feed the decision are themselves interprocedural. Knowing that a callee is called only from one site requires a call graph; knowing that a parameter is always a constant requires per-parameter value summaries. Whole-program compilation makes these available; separate compilation requires either link-time optimization, which defers code generation until the whole program is visible, or speculative summaries that are checked at link time. The two-stage structure — summarize at compile time, decide at link time — is why link-time optimization changes inlining behavior more than any flag inside a single translation unit.

One consequence worth stating plainly: inlining is the transformation with the largest effect on the rest of the optimizer and the weakest local justification. A compiler that inlines nothing loses most of the benefit of its other passes on small functions. A compiler that inlines everything produces code that is slower for being larger. The cost model is the entire engineering content, and it is tuned per target because the instruction cache, the call overhead, and the value of constant folding all vary with the architecture.