Toolingtypical

Interprocedural Analysis

Facts that cross a function boundary. The dial is context sensitivity — whether two call sites of the same function get one answer or two — and every notch of precision is paid for in compile time. Summaries are the compromise everything real is built on.

The question

How does a tool know anything about a value that was computed in a different function?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute
What the program is here

The program as a call graph whose nodes each carry a *summary*: a compact description of what the function does to the facts the analysis cares about — which parameters it may write through, whether it can return null, whether it can throw, whether a parameter escapes, which globals it touches. The summary is the representation that makes this tractable: it replaces "re-analyse the callee at every call site" with "look up what the callee does", and the entire design space is how much of the calling context the summary is allowed to depend on.

What this phase may assume or do

An interprocedural analysis may assume the call graph it was given is a sound over-approximation of the calls that can occur — miss an edge and every summary applied downstream is applied to an incomplete picture. Applying a summary at a call site is valid only if the summary was computed under assumptions that hold at that site: a context-insensitive summary must be valid for *every* caller, so it must be the join over all of them; a context-sensitive summary is valid only at the context it was computed for. Applying a context-sensitive summary at the wrong context is not an imprecision, it is an unsoundness — and it is the classic implementation bug in this area.

Key points

  • Without interprocedural facts, an analysis must assume every call may write anything and return anything, and precision collapses after the first call.
  • The three options are inline-then-analyse, re-analyse per call site, and summarise once — and everything real is built on summaries.
  • Context-insensitive means one summary per function, valid for all callers, which merges facts across unrelated call sites.
  • Context-sensitive means one summary per calling context, which removes unrealizable paths and multiplies the work down the call chain.
  • Conditional summaries — "returns Positive if both arguments are Positive" — recover most context sensitivity without duplicating the analysis.
  • Summaries are computed bottom-up in reverse topological order over the call graph; mutual recursion is an SCC iterated to a fixed point.
  • Object sensitivity beats call-site sensitivity on object-oriented code at similar cost, so the right context abstraction is language-shaped.
  • Separate compilation is the structural obstacle: LTO, cross-module IR and runtime JIT compilation are three different ways of paying to remove it.

Where intraprocedural analysis stops

Every analysis in this module so far assumed the function it was looking at was the whole world. That assumption breaks at the first call. What does parse(input) return — can it be null? Does configure(&opts) write through that pointer? Does run(cb) invoke cb before or after acquiring the lock? Does this callee free the buffer I passed it? An intraprocedural analysis must assume the worst at every call: the callee may write every reachable location, may return anything, may throw, may not return. That assumption is sound and it is devastating for precision — after two calls, an analysis that started with useful facts knows nothing.

The options are exactly three. Inline first and analyse afterwards, which is precise and only works for small callees and non-recursive code, and is the reason [[inlining]] is described as the enabling transformation rather than an optimization in its own right. Re-analyse the callee at each call site, which is maximally precise and multiplies the work by the number of call sites, recursively. Or compute a summary once and apply it everywhere, which is what real systems do.

The interesting question is what the summary is allowed to know about who is calling.

Context sensitivity: one answer or many

typicalProduction compilers are overwhelmingly context-insensitive by default and recover precision through inlining rather than through context sensitivity, because inlining is cheaper and its cost (code size) is easier to budget than an exponential in analysis time. GCC's IPA passes and LLVM's interprocedural passes both work this way; GCC's -fipa-cp adds a limited form of context sensitivity by cloning a function for a constant argument, which is context sensitivity implemented as duplication. Dedicated whole-program analysers such as Doop or WALA offer real context sensitivity and take orders of magnitude longer. Neither approach is "the" right one; they sit at different points on the same curve.

A context-insensitive analysis computes one summary per function, valid for every caller. It is fast — one pass per function — and it merges. If id(x) is called once with a non-null value and once with a possibly-null value, its single summary says "may return null", and both call sites get the pessimistic answer even though one of them provably cannot see null. Classically this is described as analysing an *unrealizable path*: the analysis effectively considers "enter from call site A, return to call site B", which no execution ever does.

A context-sensitive analysis keeps a separate summary per calling context, so each site gets its own answer and unrealizable paths disappear. The cost is that the number of contexts multiplies down the call chain: a function called from ten places, each of which is called from ten places, has a hundred contexts at depth two. This is the same exponential as [[control-flow-analysis]], for the same reason, and the standard defences are the same: bound the depth (k-limiting), or pick a smarter notion of context than "the call site" — the receiver object's allocation site, or the types of the arguments.

The example below is the smallest thing that shows the difference, and the shape it has — a small generic helper used from many places with different assumptions — is exactly the shape modern code is written in.

One helper, two callers, and the fact that context-insensitivity destroys
1int scale(int v, int k) { return v * k; }
2 
3int a(void) { return scale(2, 3);   }   /* both operands positive */
4int b(void) { return scale(x, -1);  }   /* sign of x unknown       */
5 
6/* context-insensitive summary of scale:
7 *   returns Top   (join over all callers)
8 *   -> a() is Top too, even though 2*3 is obviously positive
9 *
10 * context-sensitive (k=1):
11 *   scale@a  returns Positive
12 *   scale@b  returns Top
13 *   -> a() is Positive, and constant folding can finish the job
14 */

Note what the imprecision costs downstream: with the insensitive summary, a range analysis in a cannot prove the result is positive, so a bounds check that depended on it survives, so a loop does not vectorize. One merged summary three levels down is how a missing optimization gets its cause. This is also why aggressive inlining recovers so much: inlining scale into a makes the whole question intraprocedural again.

Summaries: the compromise everything is built on

A summary is a function from what the analysis knows at the call site to what it knows afterwards, small enough to store and cheap enough to apply. The classic bottom-up scheme computes them in reverse topological order over the call graph: analyse the leaves, summarise, move up. Mutual recursion forms a strongly-connected component, which is handled by iterating the whole component to a fixed point — starting from an optimistic assumption and weakening until stable.

What goes in a summary is a design decision with the same character as choosing an abstract domain. Common contents: which parameters are dereferenced unconditionally (so a null argument is definitely a bug), which parameters may be written through, whether the function may throw and what, whether an argument escapes into the heap or into another thread, purity, the return value's abstract element, and a set of conditions under which each of these holds.

That last one — conditional summaries — is what makes summary-based analysis competitive with context sensitivity without paying for it. Instead of "returns Top", the summary says "returns Positive if both arguments are Positive". The summary is computed once, and each call site instantiates it with its own facts. Infer's separation-logic summaries and GCC's value-range propagation across calls both work this way, and it is the single highest-leverage idea in the area: parameterise the summary rather than duplicating it.

The precision/compile-time dial, and where real toolchains sit on ittypical
StrategyCost modelPrecisionUsed by
Assume the worst at every callFreeAlmost none across boundariesAny single-file linter or fast IDE check
Inline, then analyseCode size grows; compile time grows with itExact, for what was inlinedEvery mainstream optimizing compiler
Context-insensitive summariesOne pass per functionMerged across callers; unrealizable pathsGCC IPA, LLVM interprocedural passes
Conditional summariesOne pass per function, larger summariesNear context-sensitive where the condition is expressibleInfer, GCC value-range across calls
k-limited context sensitivityMultiplicative in k, exponential in the limitSeparates callers up to depth kDoop, WALA, research analysers
Object/type sensitivityComparable to k=1 call-site, better results on OO codeSeparates by receiver allocation siteDoop for Java; the current best practice for OO
Whole-program re-analysisMultiplicative in call sites, recursivelyMaximalNothing at production scale

The separate-compilation problem

There is a structural obstacle that no amount of algorithmic cleverness removes: interprocedural analysis needs to see the callee, and [[separate-compilation]] exists precisely so that it does not have to. When each translation unit is compiled alone, a call into another unit is opaque, and the analysis is back to assuming the worst.

The industry answers are all variations of "defer the analysis until more is visible". [[link-time-optimization]] serialises the IR into object files and runs the interprocedural passes at link time, when the whole program is present. Header-only libraries and C++ templates side-step it by putting the body in the caller's translation unit. Rust and Swift emit cross-crate/cross-module IR for the same reason, and #[inline] in Rust is a request to make a body available across a crate boundary rather than a hint about inlining per se. Java sidesteps the whole issue by doing the analysis at runtime, where the entire loaded program is visible.

Each of these buys precision and pays it back in build structure: LTO makes the link step the bottleneck and defeats fine-grained incremental rebuilds, header-only libraries multiply compile time across every consumer, and cross-module IR grows the artifact. This is the real reason interprocedural analysis is rarer in practice than its value suggests — the algorithmic cost is only half the bill, and the other half lands on the build system.

  • Within a translation unit, interprocedural analysis is nearly free and mainstream compilers do it by default.
  • Across translation units it requires LTO, which moves the cost to link time and hurts incremental builds — [[incremental-compilation]] and this are in direct tension.
  • Across library boundaries it requires the library to ship IR or source, which is a distribution decision, not a compiler one.
  • A JIT gets it for free at the cost of doing it repeatedly at runtime and needing deoptimization when an assumption stops holding.
  • A closed-world analyser (native image, whole-program bundler) gets it by refusing to be open — which is the same trade under a different name.

How it works

The steps, in the order the compiler takes them.

  • Build a call graph and condense it into strongly-connected components, giving a DAG of components.
  • Process components in reverse topological order so that every callee is summarised before its callers are analysed.
  • For a single-function component, analyse the body with the summaries of its callees applied at each call site, then abstract the result into a summary.
  • For a multi-function component (mutual recursion), initialise each member optimistically, iterate the whole component, and stop when no summary changes.
  • Decide the context abstraction: none, the call site, the last k call sites, the receiver's allocation site, or the abstract types of the arguments.
  • Where the summary can be made conditional on facts about the arguments, do so rather than instantiating separate contexts — the same precision at a fraction of the cost.
  • At each call site, instantiate the callee summary with the caller's facts: bind parameters, translate the effect on the heap into the caller's naming, and apply the return fact.
  • For calls whose target is unknown or external, apply a conservative default summary — writes everything reachable, returns Top, may throw — and record that as an imprecision source rather than silently proceeding.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

  • A function that provably cannot receive null still carries a null check in the generated code, because one unrelated caller in a different file passes an optional and the summary was merged over both.
  • Turning on LTO turns a two-minute incremental build into a twelve-minute one, and the team turns it off, losing every cross-module optimization with it.
  • A whole-program analyser reports the same finding at forty call sites of one shared helper, because a context-insensitive summary propagated one caller's taint to all of them.
  • A recursive component fails to converge because the summary lattice has no finite height and nobody added widening, so the analysis either loops or is cut off by a timeout that produces no diagnostic.
  • A summary computed for one context is cached and reused at another by an off-by-one in the context key, and the analysis reports "cannot be null" about a value that can — unsound, silent, and only visible as a crash much later.
  • An analysis that looks precise in a single-file test becomes useless on the real project, because the real project calls into libraries with no summaries and every call resets the state to Top.

When it helps

  • Null and resource analysis, where the fact that matters — "this function dereferences its first parameter unconditionally" — is exactly a summary and is cheap to compute and store.
  • Escape analysis and allocation elimination, which are interprocedural by nature: whether an object escapes depends on what every callee does with it. See [[escape-analysis]].
  • Constant propagation into library and helper functions, where GCC's -fipa-cp cloning turns a generic function into a specialised one for the arguments it actually receives.
  • Taint tracking for security, which is fundamentally an interprocedural question — the source and the sink are almost never in the same function.
  • Devirtualization and inlining decisions, which need to know what the callee costs and does before deciding whether crossing the boundary is worth it.

When it hurts

  • On a fast edit-compile loop. Interprocedural passes are the first thing to disable when compile time matters, and a language server will not run them at all.
  • In codebases dominated by dynamic dispatch and framework callbacks, where the call graph is dense, summaries merge everything, and the analysis produces Top at scale.
  • When incremental correctness matters: a summary depends on the callee, so changing one leaf function invalidates every summary above it, and naive caching produces stale results.
  • Where the code crosses a language boundary — FFI, JNI, a native module — and there is simply no body to summarise, so the conservative default dominates the result.

What it costs

Every one of these is paid by something.

  • Context sensitivity buys per-caller precision and pays a multiplicative and eventually exponential increase in analysis time and memory, which is why almost everything ships k ≤ 1.
  • Summaries buy a linear-ish cost model and pay in expressiveness: whatever the summary language cannot say is lost at every call site, permanently.
  • Inlining before analysis buys exact interprocedural facts and pays in code size, instruction-cache pressure and compile time, and it cannot be applied to recursion or to large callees.
  • LTO buys cross-module analysis and pays with link-time serialisation, memory at link, and the loss of a genuinely incremental build.
  • Conditional summaries buy near-context-sensitive precision and pay in summary size and in the implementation complexity of instantiating a condition correctly at every site — the place where unsound reuse bugs live.
  • A conservative default for unknown callees buys soundness and pays by making one unanalysable call poison every fact in its caller, which is why model coverage of libraries matters more than the algorithm.

What else you could do

What a different compiler or language does instead, and when that is better.

  • Rely on inlining and give up on the rest. This is what most production compilers effectively do, and it is a defensible engineering choice: cheap, predictable, and it covers the small hot callees that matter most.
  • Move the fact into the type or annotation system so it does not need to be inferred: @NotNull, noexcept, pure, const, ownership, effects. The programmer supplies the summary — see [[effect-systems]] and [[ownership-types]]. Cheaper, checkable, and it costs annotation burden.
  • Analyse at runtime, where the whole loaded program is visible and the actual types are known, and pay in warmup and in the need to deoptimize — see [[jit-compilation]].
  • Demand-driven analysis: instead of summarising everything, answer only the specific query the user asked, following the call graph backwards from the point of interest. This is what makes an IDE feature such as "find implementations" feasible at all.
  • Modular analysis with declared interfaces, where each module publishes its summary as part of its interface and callers use it without seeing the body. This is what [[interface-files]] do for types, applied to effects, and it preserves separate compilation at the cost of a bigger interface language.

See it for yourself

The flag, dump or tool that shows you this directly.

  • GCC: -fdump-ipa-all writes every interprocedural pass's state; -fipa-cp -fipa-cp-clone performs constant propagation with cloning and -fdump-ipa-cp-details shows which clones it made and why; -fipa-pta enables interprocedural points-to analysis (off by default because of its cost).
  • LLVM: opt -passes='default<O2>' -print-after-all shows the interprocedural passes running; -passes=function-attrs is the pass that infers readnone/readonly/nocapture — the attributes are summaries, and you can read them straight off the IR after it runs.
  • Read the summaries directly in LLVM IR: parameter attributes such as nocapture, readonly, noalias and function attributes such as memory(none) are exactly what an interprocedural analysis inferred, written down.
  • LTO: clang -flto=thin (or -flto) plus -Rpass=inline to see which cross-module inlines happened; llvm-lto2 --print-summary inspects the ThinLTO summary index, which is a summary-based interprocedural design you can look at.
  • Java/Android: infer run -- ./gradlew assembleDebug runs a summary-based (bi-abduction) interprocedural analysis and caches summaries in infer-out/specs, which you can read to see what it inferred per method.
  • Rust: cargo build --release with -Ccodegen-units=1 and -Clto=fat maximises cross-crate analysis; cargo llvm-lines shows what monomorphization and inlining actually produced.
  • Go: go build -gcflags='-m -m' prints escape-analysis reasoning per allocation, including why a value escaped through a call — a readable example of an interprocedural fact affecting codegen.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "Interprocedural means the compiler looks at the whole program." It means it looks past one function. Whole-program is a stronger and much rarer condition, and needs LTO or a closed world to be true at all.
  • "Context-sensitive analysis is more accurate, so tools should use it." It is more accurate and exponentially more expensive, and the accuracy only materialises where callers genuinely differ. Most production toolchains buy the same precision more cheaply with inlining.
  • "Summaries lose precision because they are approximations." A conditional summary can be as precise as re-analysis for the facts it can express. The loss is in expressiveness of the summary language, not in the idea of summarising.
  • "If it works within a file it will work across files." Across a translation unit boundary the body is not there. Without LTO or shipped IR the analysis has nothing to summarise and falls back to the worst case.
  • "The analysis is slow because the algorithm is bad." Usually it is slow because the call graph is dense or the context abstraction is too fine. Both are modelling choices, and both are fixable without touching the algorithm.

Misconceptions

The claim, and what is actually true.

Interprocedural analysis is just running the intraprocedural analysis on more code.
The new problems are all about the boundary: what a summary can express, which context it is valid in, and how recursion converges. None of them exist inside one function.
LTO is a switch that makes programs faster.
It makes more analysis possible, at a link-time and incrementality cost that is often the reason it is disabled again. Whether the extra analysis helps a given program is a measurement, not a given.
A summary is a cached result.
A cached result answers one question for one input. A summary is a function from call-site facts to result facts, and the useful ones are conditional rather than fixed.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

Most analyses stop at the edge of a function: past a call, they have to assume the worst. Interprocedural analysis is what gets facts across that edge, and the practical mechanism is a summary — a small description of what a function does to what you care about, computed once from the bottom of the call graph upward. The one dial that matters is whether a function gets one summary for all its callers (fast, but merges unrelated facts) or a separate one per caller (precise, and the count multiplies down the call chain).

practical

When you are chasing a missing optimization, the question to ask is which fact failed to cross which boundary. -Rpass-missed=inline, -fdump-ipa-cp-details and go build -gcflags="-m -m" all answer it directly. The two most common answers are that the callee was in another translation unit (fix: LTO, or make it inline-visible) and that one unrelated caller pessimised the shared summary (fix: split the function, or let cloning specialise it). And when the fix is LTO, measure the link time before committing to it — the build cost is real and it is what makes teams revert.

advanced

The literature's framing is the IFDS/IDE family: encode the interprocedural problem as a graph-reachability question over an exploded supergraph, where valid paths are constrained to those with matched calls and returns. That constraint is what eliminates unrealizable paths and it buys full context sensitivity in polynomial time — for the specific class of problems whose flow functions distribute over the merge operator. The practical significance is that context sensitivity is *not* inherently exponential; it is exponential for general lattices and polynomial for distributive ones, which is why null and taint analyses can afford it and value-range analysis cannot. Knowing which class your problem is in tells you whether precision is affordable before you build anything.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

typicalThe description of production compilers as context-insensitive-plus-inlining describes GCC and LLVM at -O2/-O3 today. It is not a rule: HotSpot performs a form of context sensitivity by inlining aggressively at runtime with profile data, and dedicated analysers such as Doop are context-sensitive by design and take minutes to hours on programs a compiler handles in seconds. The right comparison is always cost-per-question, not "which is better".
implementationWhich interprocedural passes run, and how far, is a flag-and-version question. GCC gates -fipa-pta off by default on cost; -fipa-cp-clone is enabled at -O3 but not -O2; LLVM's ThinLTO summarises rather than merging IR, so it makes different precision/scalability trades than full LTO. A result observed under one configuration does not transfer to another configuration of the same compiler, let alone to a different one.
specThe soundness condition for applying a summary is precise: the summary must have been derived under assumptions implied by the facts at the call site. A context-insensitive summary must therefore be the join over all callers, and using a summary derived from one context at another is unsound rather than merely imprecise. Languages that let the programmer *declare* a summary — noexcept, pure, @NotNull — shift this obligation onto a check at the definition, which is why those annotations must be verified rather than trusted.

If you were asked this in an interview

  • What is the difference between a context-sensitive and a context-insensitive interprocedural analysis, and what does each cost?
  • What would you put in a summary for a null-safety analysis, and what would you deliberately leave out?
  • Why does turning on LTO often hurt more than it helps, and how would you decide?

Connections

DSAdirected-graphtopological-sortdfshash-table
Performanceperformance-regression-detectioncpu-profiling
Securityinput-validationsql-injection
Domains that do not exist yet
  • DevOps / Production Engineering — The build-time cost of link-time optimization and how it interacts with caching and incremental builds
    The reason interprocedural analysis is often disabled is not that it fails to help but that it destroys incremental rebuild and slows the link step past what a delivery pipeline tolerates. Budgeting that, and deciding whether to run it only on release builds, is a delivery-engineering decision owned there; what precision is being given up is ours.