Toolingtypical

Control-Flow Analysis

Which statements can run in which order, and — the genuinely hard case — which functions a call site can actually reach when the callee is a value. In a higher-order language you cannot build the call graph without the analysis, and cannot run the analysis without the call graph.

The question

When the thing being called is a variable, how does any tool know what runs?

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

Two graphs at two scales. Inside a function, the control-flow graph: basic blocks and the edges between them, which is [[control-flow-graph]] and is fully determined by the syntax. Across functions, the call graph: nodes are functions, edges are "this call site may invoke that function" — and in any language with function values, virtual dispatch or dynamic loading, this graph is not given by the syntax. It is the *output* of an analysis, and every interprocedural question depends on having it.

What this phase may assume or do

Intraprocedural control-flow analysis may assume the frontend produced a well-formed CFG: every block ends in a terminator, every edge lands on a real block, and there is no path into the middle of a block. Call-graph construction may assume nothing comparable. It must treat every indirect call as reaching *some* set of functions, and it is sound only if that set over-approximates every callee possible at runtime — which means it must account for every function whose address is taken, every override of a dispatched method, and every entry point reachable through reflection, dlopen, eval or a foreign-function boundary. Miss one and every downstream conclusion, including whether a function is dead, is wrong.

Key points

  • Inside a function the CFG is determined by syntax; across functions the call graph is the output of an analysis, not a given.
  • The exception, finally and coroutine edges are the ones people forget, and they are where resource-leak bugs live.
  • Control-flow analysis in the higher-order sense means determining which function values reach which call sites — control depends on data depends on control.
  • k-CFA resolves the circularity by solving both as one fixed point, with k controlling how much calling context each abstract value keeps.
  • 0-CFA merges all call sites of a shared combinator; 1-CFA separates them and costs an analysis copy per site.
  • Cheap approximations — address-taken, CHA, RTA — are what production compilers usually run, because a static type already bounds the callee set.
  • JITs replace the analysis with observation: an inline cache plus a guard is more precise than any static CFA and needs a deoptimization path.
  • An unsound call graph does not produce a slow program, it produces a broken one — whole-program dead-code elimination deletes the reflectively-reached function.

The easy half: control flow inside a function

Within a single first-order function, control-flow analysis is a solved problem and largely a matter of bookkeeping. The frontend lowers statements into basic blocks, adds edges for branches, loops and fall-through, and the result is a graph you can run any of the classical algorithms over: reachability by depth-first search, [[dominators]] for what must execute before what, [[natural-loops]] for what iterates. Unreachable-code diagnostics, definite-assignment checks and "not all paths return a value" errors all fall directly out of it.

The details that catch people out are the edges nobody wrote. Exceptions add an edge from every potentially-throwing instruction to every enclosing handler and to the function exit, which is why [[exception-handling]] makes the CFG far denser than the source suggests and why resource-leak analysis is mostly about those edges. setjmp/longjmp, goto into a loop, computed gotos in an interpreter dispatch loop, and coroutine suspension points all add edges too. A CFG that models only the visible control flow is a CFG that will confidently tell you a finally block is unreachable.

All of this is genuinely local and genuinely cheap. Which is why the interesting content of this lesson is entirely in the other half.

The hard half: when the callee is a value

typicalReal compilers rarely run textbook k-CFA. Mainstream JIT compilers substitute *observation* for analysis: an inline cache records which function actually appeared at a call site and speculates on it with a guard, which is cheaper and more precise than any static CFA and is unsound in the sense that it needs a deoptimization path when the guard fails — see [[inline-caches]] and [[guards]]. Ahead-of-time compilers for statically typed languages get most of the benefit from cheaper approximations instead (class hierarchy analysis, rapid type analysis) because the type of the receiver already bounds the callee set. k-CFA in its general form appears mainly in whole-program analysers for functional and dynamic languages.

Write f(x) where f is a parameter, a field, an entry in a dispatch table, a closure returned from somewhere, or an object whose method is virtual, and the question "what runs here" stops being syntactic. This is what the literature calls control-flow analysis proper, or CFA, and the naming is initially confusing: it is not about branches, it is about determining the flow of *control values* — functions treated as data — to the sites where they are invoked.

The circularity is what makes it hard. To know which functions a call site reaches, you need to know which function values flow into that position. To know which values flow anywhere, you need to know which functions run, because a function's body is what propagates values to its callees. Data flow depends on control flow depends on data flow. The resolution is the same as everywhere else in this module: solve both at once, as a single fixed point over a graph you are building while you traverse it.

The standard family of answers is k-CFA, where k is how much calling context each abstract value carries.

Why 0-CFA merges these and 1-CFA does not
1function apply(f, v) {
2  return f(v);          // which function does this call?
3}
4 
5apply(x => x + 1, 10);  // site A: f is the increment closure
6apply(x => x * 2, 10);  // site B: f is the doubling closure
7 
8// 0-CFA:  at `f(v)`, f may be {increment, double}. Both call sites merged.
9// 1-CFA:  at `f(v)` from A, f = {increment}; from B, f = {double}.

With 0-CFA every use of apply shares one abstract binding for f, so a devirtualizer sees two possible callees and inlines neither. With 1-CFA the analysis keeps one abstract copy of apply per call site and each sees exactly one callee — at the cost of analysing apply twice. Now imagine apply is called from two hundred places and calls three other higher-order helpers, and you have the k-CFA cost curve.

The cheap approximations, and when each is enough

Because full CFA is expensive, real toolchains use a ladder of approximations and stop at the cheapest one that answers the question. It is worth knowing the ladder by name, because "the compiler could not devirtualize this" almost always means "the approximation in use could not narrow the callee set to one".

Each rung buys precision with either analysis time or a soundness caveat, and the last two buy it with a runtime check rather than a proof.

Approximations to "what can this call site reach", cheapest firsttypical
TechniqueCallee set for a virtual callPrecise enough whenCost
Address-taken (for function pointers)Every function whose address is taken anywhere with a compatible signatureFew function pointers existTrivial
Class Hierarchy Analysis (CHA)Every override of the method in the static type's subtreeShallow hierarchies; single implementationOne pass over the hierarchy
Rapid Type Analysis (RTA)CHA restricted to classes actually instantiated in the programA framework declares many types and the app uses fewOne extra fixed point
0-CFAFunctions flowing to that variable, merged across all calling contextsHigher-order code without shared combinatorsRoughly cubic in program size
k-CFA (k ≥ 1)Per calling context, so shared helpers separateShared combinators such as map, apply, middleware chainsExponential in k; rarely used past k=1 or 2
Profile-guidedWhatever was observed, plus a fallbackThe hot receiver dominates in productionA profiling run — see [[profile-guided-optimization]]
Inline cache (JIT)Whatever appeared last, behind a guardCall sites are monomorphic in practice, which most areA guard per call plus deoptimization support

What the call graph is actually for

A call graph is not an end in itself; it is the substrate for every question that crosses a function boundary. [[inlining]] needs to know there is exactly one callee before it can inline. [[devirtualization]] is literally the act of narrowing a callee set to one and replacing the dispatch with a direct call. Dead-code elimination at the whole-program level — tree shaking, --gc-sections, dead-method removal — needs reachability from the roots. [[interprocedural-analysis]] needs the graph to know which summaries to apply where. Even build systems use a coarse version of it.

The consequence of an *unsound* call graph is therefore not a missed optimization but a broken program. If reflection, a dynamically registered handler, a JNI callback or a dlsym lookup can reach a function the graph does not connect, whole-program dead-code elimination will delete it and the program will fail at runtime with a missing symbol or a null method reference. This is the single most common way an aggressive tree-shaking or native-image build breaks: not a bug in the analysis, but an entry point the analysis had no way to see. That is why every such toolchain ships an escape hatch — reflection configuration files, @Keep annotations, KEEP sections in linker scripts, sideEffects declarations in bundlers.

The reverse consequence — an over-approximate graph — is merely expensive: everything is reachable, nothing is dead, no call devirtualizes, and the build is large and slow. Which is the correct direction to fail in, and the reason every production call-graph builder is conservative by default and precise only where it can prove it.

  • Reachability from roots: what code can run at all. Feeds tree shaking, --gc-sections, and native-image closed-world builds.
  • Callee-set size at a site: 1 means direct call and inlining candidate; small means guarded polymorphic inline cache; large means real dispatch.
  • Recursion and SCCs: a strongly-connected component in the graph is mutual recursion, which bounds what a summary-based analysis can do in one pass.
  • Call-graph order: analysing callees before callers (reverse topological order over the SCC-condensed graph) is what makes bottom-up summaries possible.
  • Escape hatches exist because the graph cannot see reflection, eval, dlopen, FFI callbacks, or a function registered by a string name in a config file.

How it works

The steps, in the order the compiler takes them.

  • Build the intraprocedural CFG: partition instructions into basic blocks at labels and after terminators, add edges for branches, fall-through, loop back edges, and every exceptional edge to an enclosing handler.
  • Seed the call graph with the direct calls, which are syntactically evident, and with the program roots — main, exported symbols, registered entry points.
  • For each indirect call site, compute the set of function values that may flow to the callee position, using whichever approximation the toolchain has chosen.
  • Add an edge from the call site to every function in that set, which may make new code reachable and therefore new values flow.
  • Iterate to a fixed point: the call graph and the value flow are computed together, because adding an edge can add a value and adding a value can add an edge.
  • Condense the resulting graph into strongly-connected components to get a DAG, and process it in reverse topological order so callees are analysed before callers.
  • Supply the analysis with an explicit list of the entry points it cannot see — reflection configuration, keep rules, exported symbol lists — because a sound graph is impossible without them.

How it breaks

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

  • A native-image or tree-shaken build passes every test and fails in production with a missing-class or missing-method error, because a handler was only ever reached by reflection from a config string.
  • A bundler drops a module whose only job was a side effect on import, and a polyfill or a registration silently stops happening.
  • A profiler shows a hot call site that never gets inlined, and the reason is that the callee set has two members because one obscure subclass exists in a test fixture that the analysis cannot distinguish from production code.
  • A whole-program analysis runs for hours and reports nothing, because one eval or one function-pointer table forced the callee set at a central dispatch site to "every function", and the graph became complete.
  • Coverage tooling reports a function as never executed while the same function appears in production stack traces, because the instrumentation used a call graph that missed the dynamic path.
  • A finally block's cleanup is reported as dead code by a tool whose CFG has no exceptional edges, and someone deletes it.

When it helps

  • Any whole-program optimization: inlining across modules, devirtualization, link-time dead-code elimination, tree shaking a JavaScript bundle, or a closed-world native image.
  • Security review: knowing which paths can reach a sink is a reachability question over the call graph, and it is the difference between "this vulnerable function exists in a dependency" and "this vulnerable function is callable from our code".
  • Change-impact analysis and test selection: which tests can reach the code I changed is a reverse reachability query, and it is how large monorepos avoid running everything.
  • Understanding an unfamiliar codebase — a call graph rendered from the real binary shows the paths that exist rather than the ones the documentation describes.

When it hurts

  • In dynamic languages with pervasive metaprogramming, where the sound answer at most indirect call sites is "anything" and the analysis costs a great deal to produce no information.
  • In plugin architectures and anywhere modules load at runtime, where the closed-world assumption the analysis needs is simply false and must be replaced by explicit declarations.
  • When the precision needed is per-call-context and the code is built out of shared combinators. This is the worst case for 0-CFA and the exact place where the cost of higher k becomes unaffordable.
  • As a merge-gate check: whole-program CFA is a link-time or nightly cost, not something to run per keystroke — a language server uses a far coarser and deliberately unsound approximation for "find implementations".

What it costs

Every one of these is paid by something.

  • Higher context sensitivity (k) buys separation of shared helpers and pays analysis time and memory that grows exponentially in k, which is why almost nothing ships past k = 1.
  • A sound over-approximate call graph buys the right to delete unreachable code and pays in a graph so dense that little is provably unreachable, so the optimization it enabled does not fire.
  • An unsound but precise graph — assume no reflection, assume a closed world — buys aggressive optimization and pays with runtime failures that only appear on the code path nobody tested.
  • Inline caching buys per-site precision at runtime for free from the analysis's point of view, and pays a guard on every call, memory per call site, and the substantial engineering of a deoptimization mechanism.
  • Whole-program analysis buys cross-module precision and pays the ability to compile modules independently — see [[separate-compilation]] — which shows up as a build that cannot be incremental at the link step.

What else you could do

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

  • Let the type system bound the callee set: sealed hierarchies, final methods and non-virtual-by-default make CHA precise for free, which is a language-design answer rather than an analysis one.
  • Observe instead of prove: a JIT's inline cache, or a profile-guided build, records the callees that actually occur and speculates, with a guard and a fallback. More precise than static analysis and requires a deoptimization path.
  • Declare the graph: reflection configuration, @Keep/@Reflective annotations, explicit entry-point lists and bundler sideEffects fields let the human supply what the analysis cannot see. Tedious, and the only sound option in an open world.
  • Trace-based approaches that record real execution and build the graph from it — precise for what ran, silent about the rest, and the standard technique for generating native-image reflection configuration.
  • Skip the graph entirely and analyse each function in isolation with worst-case assumptions at every call. Fast, always sound, and imprecise enough that most interprocedural questions become unanswerable.

See it for yourself

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

  • LLVM: opt -passes=print-callgraph -disable-output file.ll prints the call graph; pass names move between releases, so check opt --print-passes | grep -i callgraph on your build first.
  • GCC: gcc -O2 -fdump-ipa-cgraph -c file.c writes a .cgraph dump listing nodes, callers and callees; -fdump-ipa-all gives the whole interprocedural set.
  • Java: jdeps --print-module-deps for the coarse version; for a real call graph, Soot, WALA or SootUp, all of which let you choose CHA, RTA or k-CFA and see the difference in edge count.
  • GraalVM native image: -H:+PrintAnalysisCallTree writes the reachability tree the closed-world analysis computed, which is the fastest way to find out why a class was kept — or why it was not.
  • JavaScript bundlers: webpack --profile --json or rollup --plugin visualizer show what survived tree shaking; esbuild --analyze prints the reachability decision per module.
  • Go: go build -gcflags=-m reports inlining and escape decisions, which is the observable consequence of its (deliberately simple) call analysis; golang.org/x/tools/cmd/callgraph builds real graphs with a choice of algorithm.
  • Binaries, after the fact: objdump -d plus a cross-reference tool, or Ghidra/radare2, which reconstruct a call graph from machine code and hit exactly the same indirect-call problem with less information.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "Control-flow analysis means analysing if-statements and loops." That is the intraprocedural half and it is the easy half. The term of art means resolving which functions a call site can reach.
  • "The compiler knows what my function calls." For direct calls, yes. For a call through a variable, an interface or a function pointer, it knows a *set*, and the size of that set is what determines whether anything downstream can be optimized.
  • "Tree shaking removes code that is not used." It removes code that is not *reachable in the graph it built*. Anything reached by a name looked up at runtime is invisible to that graph and needs to be declared.
  • "A JIT does control-flow analysis better than a static compiler." It does something different: it observes rather than proves, so it is more precise about what happened and guarantees nothing about what could happen. That is why it needs guards.
  • "If two subclasses exist, the call cannot be devirtualized." It can, if the analysis can prove only one is ever instantiated on the reachable paths — which is exactly what rapid type analysis is for.

Misconceptions

The claim, and what is actually true.

A call graph is derived from the source, like a CFG.
Only the direct calls are. Every indirect call site is an inference, and its accuracy is the whole subject.
More precise analysis always helps the optimizer.
Past a point the analysis time exceeds the compile-time budget and the toolchain falls back to a coarse approximation anyway. Precision you cannot afford to compute is precision you do not have.
Dynamic dispatch is slow because of the indirect branch.
The indirect branch is usually well predicted. The real cost is that the callee is unknown, so nothing inlines across it and every optimization that would have crossed the boundary is blocked.

Go deeper

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

overview

Inside one function, working out what runs in what order is easy — it is right there in the syntax. Across functions it is not, as soon as the thing being called is a value rather than a name: a callback, a virtual method, an entry in a table. Working out which functions a call site can reach is what "control-flow analysis" means in this stricter sense, and it matters because inlining, devirtualization and dead-code removal all need the answer. When a bundler deletes code you needed, or a native image cannot find a class, that analysis missed an entry point.

practical

Two habits pay for themselves. First, when something will not inline or devirtualize, find out how many callees the toolchain thinks the site has — -fdump-ipa-cgraph, -Rpass-missed=inline, PrintAnalysisCallTree — before theorising. It is usually two, and usually one of them is a test double or an unused subclass. Second, when a closed-world build (native image, tree shaking, --gc-sections) breaks at runtime, do not treat it as a build bug: it is a call-graph gap, and the fix is to declare the entry point the analysis could not see. Generating that declaration from a trace of a real run is the standard workflow and it is much faster than guessing.

advanced

The structural insight is that CFA and data-flow analysis are the same fixed point viewed from two sides, and the k-CFA hierarchy is the knob controlling how much of the call history each abstract binding remembers. It is also worth knowing that k-CFA past k = 1 is provably expensive — deciding it is EXPTIME-complete for the standard formulation — which is why the field largely moved to other axes: object sensitivity (context is the receiver's allocation site rather than the call site), type sensitivity, and demand-driven queries that compute a callee set only where somebody asked. The practical lesson from that literature is that the *right* context abstraction is language-shaped: object sensitivity outperforms call-site sensitivity substantially on object-oriented code and not on functional code, so the choice is a modelling decision about your programs, not a dial to turn up.

How much this depends on

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

typicalThe claim that mainstream compilers use CHA and RTA rather than k-CFA describes ahead-of-time compilers for statically typed languages — HotSpot's C2, GraalVM native image, LLVM's whole-program devirtualization. Whole-program analysers for Scheme, JavaScript and Python do run k-CFA-style analyses, and there the cost profile is completely different. Neither is "how compilers do it"; each matches a language shape.
implementationWhether a given call devirtualizes depends on the compiler, its version, whether LTO is on, and whether the class is loaded. HotSpot devirtualizes on the currently-loaded class hierarchy and *undoes* it when a new subclass is loaded, which is a dynamic technique with no static equivalent; a C++ compiler needs final or LTO plus -fwhole-program-vtables to reach a comparable conclusion. Do not carry a devirtualization result between toolchains.
specReachability in the presence of dynamic language features is not merely hard, it is undecidable — determining whether an arbitrary eval string names a given function is equivalent to deciding what the program computes. This is why every closed-world toolchain defines its own sound-by-declaration escape hatch rather than trying to analyse harder: the specification of the analysis explicitly excludes what it cannot see, and requires the user to supply it.

If you were asked this in an interview

  • What does the term "control-flow analysis" mean when the callee is a variable, and why is it circular?
  • Explain the difference between 0-CFA and 1-CFA on a shared map helper.
  • A native-image build works in tests and throws a missing-method error in production. Where do you look and why?

Connections

DSAdirected-graphdfstopological-sorthash-table
Performanceflame-graphscpu-profiling
Securityattack-surface-mappingdependency-security
Domains that do not exist yet
  • Programming Languages & Runtime Internals — Virtual dispatch, vtables and method caches as they exist at runtime
    The runtime mechanism for an unresolved call — the vtable lookup, the itable, the megamorphic cache — is what remains when the analysis fails to narrow the callee set to one. The mechanism belongs there; why the analysis could not narrow it, and what that costs the optimizer, is ours.
  • Testing & Reliability Engineering — Trace-driven configuration generation and change-impact test selection
    Both are reachability queries over a call graph run for a non-compiler purpose: recording a real execution to produce reflection configuration, and computing which tests can reach a change. The testing strategy is owned there; the graph and its unsoundness are ours.