Classical dataflow analysis lives inside the fence of a single function: it reasons about one control-flow graph, treating every call as an opaque black box that might do anything. That is safe, but ruinously pessimistic. A call to strlen cannot possibly write to your local x, yet an intraprocedural analysis, seeing only "a call", must assume it clobbers the world. To recover the precision hiding across the fence, we do interprocedural analysis — analysis that follows information through calls and returns, over the whole program at once.

The prize is large: constants that flow into a callee's parameters, exceptions that can never be thrown, pointers that a function never writes, side-effect-free calls that can be hoisted out of loops. The difficulty is equally large, and it has a precise shape. A program is no longer one graph but a graph of graphs, stitched together at call sites — and the naive way of stitching them leaks information along paths that no real execution could ever take.

The call graph: the skeleton of the whole program

The first object every interprocedural analysis needs is the call graph: one node per function, and a directed edge f \to g whenever the body of f contains a call site that may invoke g. For a language with direct calls this is trivial to read off the source. For anything with function pointers, virtual dispatch or closures it is itself the output of an analysis — you need to know what a call target might be before you can draw the edge, which is exactly the chicken-and-egg problem that devirtualization and points-to analysis exist to break.

A path in the call graph is a chain of calls: main → parse → lex → advance. Two facts about the shape matter enormously. First, a cycle in the call graph is exactly a set of mutually recursive functions — and just as loops force iteration to a fixed point inside a CFG, recursion forces iteration to a fixed point over the call graph. Second, if the graph is acyclic we can process functions bottom-up in reverse topological order: analyse a callee fully before any of its callers, so that by the time we reach a call site we already know what the callee does.

Context-insensitive vs context-sensitive

Here is the central design axis. Suppose id(x) { return x; } is called twice — id(3) in one place and id(7) in another. A context-insensitive analysis has a single summary of id shared by all callers: it merges the two calls, learns that the argument is "3 or 7", and concludes the result is "3 or 7" everywhere. Cheap, but it has just smeared two unrelated facts together.

A context-sensitive analysis keeps the calls apart. It distinguishes the abstract state by the context in which the callee runs, so that the id(3) instance returns exactly 3 and the id(7) instance returns exactly 7. Two classic ways to encode context:

Both are instances of the same idea: split the callee's single summary into several context-qualified summaries. More splitting means more precision and more cost — potentially exponentially more.

The valid-paths problem: why naive propagation lies

Imagine gluing every caller's CFG to every callee's CFG with plain edges: a call becomes a jump into the callee's entry, a return becomes a jump out of the callee's exit. Now run an ordinary reachability or dataflow analysis on this giant supergraph. It over-approximates badly, and the reason is beautiful. Consider two call sites c_1 and c_2 that both call g:

The supergraph happily lets a fact enter through call site c_1 and leave through the return edge belonging to c_2 — a path that enters via one caller and returns to a different one. No real execution does that; a function always returns to whoever called it. Such a path is unrealizable. The precise interprocedural answer counts only valid paths (also called realizable or interprocedurally valid paths): those in which every return edge is matched to the most recent unmatched call edge, exactly like balanced parentheses.

This "matched-parenthesis" structure is why interprocedural dataflow is often phrased as a context-free-language (CFL) reachability problem — the valid paths are precisely those whose call/return labels form a string in a balanced-bracket grammar. The celebrated IFDS/IDE framework of Reps, Horwitz and Sagiv solves exactly this class of problems (distributive, finite-domain) in polynomial time by threading summary edges through the graph.

Summary functions: solve the callee once

The workhorse technique for scalable, reasonably precise interprocedural analysis is the summary function (or procedure summary). Instead of re-analysing a callee at every call site, you compute once a compact description of its input/output behaviour — "given the abstract state at entry, here is the abstract state at exit" — and then simply apply that summary at each call. Because summaries are built for callees before callers, they compose bottom-up over an acyclic call graph.

A summary can capture whatever the analysis tracks: a MOD/REF set (which globals and parameters a call may modify or read), a constant-propagation transfer function, a "may-throw" bit, a points-to effect. A well-known instance is the MOD/REF summary used to answer "can this call touch x?" — if x is not in the call's MOD set, a load of x across the call is safe to reuse.

Recursion breaks the tidy bottom-up order: to summarise f you would need f's own summary. The fix is the same one dataflow uses for loops — start from an optimistic (bottom) summary and iterate the strongly-connected component of the call graph to a fixed point, re-deriving each member's summary until nothing changes.

Inlining: the simplest interprocedural transform of all

Before any of that machinery, there is the bluntest interprocedural weapon: inlining — physically replacing a call with a copy of the callee's body. Inlining is interprocedural analysis' poor, powerful cousin. It manufactures context sensitivity for free (the copy is specialised to exactly this call site), exposes the callee's internals to the caller's intraprocedural optimiser, and kills call/return overhead. It is often the single most profitable optimisation a compiler performs, precisely because it turns a hard interprocedural problem into an easy intraprocedural one.

Its cost is code growth: inline too eagerly and the binary explodes, instruction caches thrash, and compile time balloons. Recursive functions cannot be inlined without bound. So real compilers inline by heuristic — small callees, hot call sites, single-caller functions — and fall back on genuine summary-based analysis for everything else.

Build a call graph and summarise, in code

The snippet builds a call graph from a tiny program, then computes two bottom-up summaries by fixed-point iteration over the call graph: reachability (which functions can be transitively invoked) and a MOD summary (which globals a function may write, directly or via callees). Notice the fixed-point loop — it is what lets the analysis survive the recursive cycle.

The fixed point closes each summary under its callees: main ends up with {ast, out, pos} — everything reachable — while lex stays at {out, pos}, which is exactly the fact that licenses reusing a value of ast across a call to lex.