Data Flowtypical

The Data-Flow Framework

Four slots — a lattice of facts, a transfer function per instruction, a meet operator at joins, and iteration to a fixed point. Fill them in four different ways and you get reaching definitions, liveness, available expressions and constant propagation. There is only one algorithm here.

The question

Is there one thing called "data-flow analysis", or is every analysis its own algorithm?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

The control-flow graph, annotated with a *fact* at the entry and exit of every basic block. A fact is an element of a lattice — a set of definitions, a set of live registers, a set of available expressions, a map from value to constant — and the annotated graph exists to answer a question the instruction list cannot phrase: what is true *here*, given every path that could have reached here.

What this phase may assume or do

An analysis is sound if its result is an over-approximation in the direction that keeps transformations safe: it may claim a value is live when it is not, or that a definition reaches when it does not, but never the reverse. That asymmetry is the whole safety argument, and it comes from the meet operator — merging paths must never produce a fact stronger than what holds on every path. A framework instance is entitled to assume the CFG is complete and that anything it cannot see (a call to an unknown function, a store through an unanalysed pointer) is modelled conservatively rather than ignored.

Key points

Four slots determine an analysis: the lattice of facts, the transfer function, the meet operator, and the direction.
The direction follows from the question, not from taste — see [[forward-vs-backward-analysis]].
Union is "may", intersection is "must", and choosing wrongly is unsound in exactly one of the two directions.
Soundness means over-approximating in the safe direction: claiming more liveness or fewer guarantees than actually hold.
Reaching definitions, liveness, available expressions and constant propagation are the same algorithm with different slots filled in.
The framework is path-insensitive and intraprocedural by default; both limits are real and both have expensive remedies.
SSA makes several of these instances unnecessary for value questions, but not the ones about program points.

The four slots

A data-flow analysis is completely determined by four choices. What is a fact — the lattice, which fixes what can be said and how precise it can be. How does one instruction change a fact — the transfer function. What happens where paths meet — the meet operator, union or intersection depending on whether the question is "on some path" or "on every path". And which direction the information travels, which follows from the question rather than from preference.

Once those four are fixed, the algorithm is the same one every time: initialise every block's fact, repeatedly apply the transfer functions and the meet until nothing changes, and stop. That is [[fixed-point-iteration]], and it is shared code in any compiler that has more than one analysis.

It is worth being suspicious of the word "framework" here, because it usually means an abstraction that costs more than it saves. This one does not: the four classic analyses below have been implemented as instances of the same solver in production compilers for forty years, and the reason is that the *only* thing they disagree about is what goes in the four slots.

The four classic analyses, as instances of one framework

Analysis	Direction	Facts	Meet	Used for
Reaching definitions	Forward	A set of definitions that may have written each variable	Union — a definition reaches if it reaches on any path	Constant propagation and copy propagation outside SSA; building use-def chains
Live variables	Backward	A set of values that some future use will read	Union — live if needed on any successor path	Register allocation, dead store elimination, and deciding what must survive a call
Available expressions	Forward	A set of expressions already computed and not since invalidated	Intersection — available only if available on every path	Common subexpression elimination and global value numbering
Constant propagation	Forward	A map from each value to "unknown", one specific constant, or "not constant"	Meet on the constant lattice — two different constants meet to "not constant"	Folding, branch simplification, and specialising code to a known value

Why the meet operator is where correctness lives

simplifiedPresenting the meet as union-or-intersection is the bit-vector special case, which covers the four classic analyses. The general framework requires only a semilattice with a finite-height ordering and monotone transfer functions; constant propagation already needs that generality, because its lattice is not a set of bits but a map to a three-level value lattice, and its meet is defined pointwise.

The direction and the transfer functions are usually obvious once the question is stated. The meet is where analyses are got wrong, because the choice between union and intersection is the choice between "may" and "must", and picking the wrong one is unsound in one direction and merely imprecise in the other.

A may question — *could* this definition reach here, *might* this value be needed later — merges by union, because a possibility on any one path is a possibility. A must question — is this expression available on *every* path, is this value definitely a constant — merges by intersection, because a guarantee has to hold everywhere.

Get it backwards and the failure is not subtle in its consequences and completely silent in its symptoms. Use intersection for liveness and the analysis will tell you a value is dead when one path still needs it; the allocator reuses its register and a value is corrupted on that path only. Use union for available expressions and CSE will reuse a value that was only computed on one arm of a branch, reading a register that holds something else entirely.

May and must, and what each meet costs when it is wrong

Question shape	Meet	Safe error	Unsafe error
May — true on some path	Union	Claiming something reaches or is live when it is not: lost optimization	Missing a path: a real definition or use is not accounted for, and a transformation destroys it
Must — true on every path	Intersection	Claiming something is unavailable when it is: lost optimization	Claiming availability from one path only: a use reads a value that was never computed on the path taken

The equations, written once

For a forward analysis, the fact on entry to a block is the meet of the facts on exit from its predecessors, and the fact on exit is the transfer function applied to the fact on entry. For a backward analysis both sentences are the same with predecessors and successors swapped. Everything else — which sets, which operator — is the instance.

The gen/kill phrasing below is how the bit-vector instances are usually written and is worth recognising because every textbook uses it: gen is what this block makes true, kill is what it invalidates, and the transfer function is "keep what arrived, drop what was killed, add what was generated".

The framework, and the classic instances written in it

1FORWARD:   in[B]  = meet over predecessors P of out[P]
2           out[B] = gen[B] union (in[B] minus kill[B])
3 
4BACKWARD:  out[B] = meet over successors S of in[S]
5           in[B]  = gen[B] union (out[B] minus kill[B])
6 
7reaching definitions   forward,  meet = union
8  gen  = definitions in B not later overwritten in B
9  kill = all other definitions of the same variables
10 
11live variables         backward, meet = union
12  gen  = values read in B before being written in B   ("use")
13  kill = values written in B                           ("def")
14 
15available expressions   forward,  meet = intersection
16  gen  = expressions computed in B and not invalidated later in B
17  kill = expressions whose operands B assigns to

Three analyses, one shape. The only differences are the direction, the meet, and what goes into gen and kill — which is exactly the claim the matrix above makes, written as code.

What the framework cannot do

It is path-insensitive by construction. The meet throws away which path a fact came from, so an analysis in this framework can say "x is 1 or 2 here" but not "x is 1 on the path where the branch was taken". Recovering that means either a path-sensitive analysis, which is exponential in general, or splitting the paths in the CFG so that the framework sees them separately — which is what tail duplication and if-conversion do.

It is also intraprocedural unless something extends it. A call is a black box: a sound analysis must assume the callee may read and write anything reachable, which is why the results degrade sharply in code full of calls and why [[inlining]] improves so many unrelated optimizations. Doing better is [[interprocedural-analysis]].

And it says nothing about memory without help. All four classic analyses in their usual form talk about variables or registers. Extending them to loads and stores requires knowing which memory locations can alias, which is [[alias-analysis]] — and the conservative answer, "any store may write any location", makes available expressions over memory nearly useless.

The final limitation is the one that matters most in a modern compiler: for questions about *values*, SSA has already answered several of these. Reaching definitions is trivial in SSA, and constant propagation needs no analysis at all — see [[why-ssa-helps]]. The framework survives because plenty of questions are about program points rather than values, and liveness is the one every backend still runs.

How it works

The steps, in the order the compiler takes them.

Choose the lattice: what a fact is, what "top" and "bottom" mean, and the partial order between facts.
Choose the direction from the question — does the answer depend on what came before or on what comes after?
Define the transfer function per instruction, and compose it over a block to get the block transfer function.
Choose the meet: union for "on some path", intersection for "on every path".
Initialise: the boundary block gets the boundary fact, every other block gets the identity for the meet (empty set for union, the full set for intersection).
Iterate: recompute each block's facts from its neighbours until nothing changes.
Read the answer at the program points the transformation cares about, then run the transformation.

How it breaks

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

The meet is intersection where it should be union. The analysis reports a value dead while one path still needs it, the allocator reuses the register, and the value is corrupted on that path only — so the bug depends on the branch outcome.
The initial value for non-boundary blocks is wrong — empty for a "must" analysis instead of full — and the fixed point converges to the empty set. Every optimization that depended on the analysis silently stops firing, and the only symptom is code that is slower than expected.
The transfer function forgets that a call may write memory. Available expressions survive across a call that invalidated them, and CSE reuses a stale value; the wrong answer appears only when the callee actually writes.
The analysis is not re-run after a transformation changed the CFG. Stale facts describe a graph that no longer exists, and the next transformation acts on them — this is the classic pass-ordering bug and it produces wrong code rather than slow code.

When it helps

Anywhere a transformation needs to know something about all paths reaching a point: allocation, elimination of redundant computation, and every legality check that mentions "on every path".
Backends specifically. Liveness is not optional — [[register-allocation]] cannot be done without it, whatever the middle-end representation was.
Static analysis tooling outside compilers: linters, taint tracking and null-dereference checkers are all this framework with a different lattice — see [[static-analysis]] and [[abstract-interpretation]].

When it hurts

When the question is really about values rather than points. In SSA those questions are answered by the representation, and running a dense analysis to rediscover them is wasted compile time.
On code dominated by calls and pointer traffic, where the conservative assumptions swamp the analysis and the results are technically sound and practically empty.
On very large functions, where a dense analysis computing a fact at every program point is a real fraction of compile time — which is the argument for sparse, SSA-based formulations.

What it costs

Every one of these is paid by something.

A shared framework buys one solver, one termination argument and one set of tests for many analyses; it pays an abstraction that makes each instance slightly less efficient than a hand-written version, and a lattice interface that some questions fit awkwardly.
Sound over-approximation buys the guarantee that no transformation built on the result is wrong; it pays missed optimizations, and there is no way to reduce the missed optimizations without either more analysis time or a stronger lattice.
A denser lattice buys precision; it pays convergence time, because the number of iterations is bounded by the lattice height, and memory, because the fact at every program point gets bigger.
Path insensitivity buys tractability; it pays exactly the facts that depend on which branch was taken, and recovering them means duplicating code and paying in size and instruction-cache pressure.

What else you could do

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

Abstract interpretation is the general theory this framework is a special case of: pick an abstract domain, prove the transfer functions are sound with respect to the concrete semantics, and the fixed point is sound by construction. It buys intervals, relational domains and a proper account of widening, at a substantial cost in implementation and in analysis time.
Sparse analysis over SSA def-use edges: propagate facts between values rather than at every program point. Wegman and Zadeck's SCCP is the canonical instance, and it is both faster and more precise than the dense version for the questions it can express.
Symbolic execution or a solver-based approach, which is path-sensitive and can answer questions the framework cannot, at a cost that makes it a tool for verification and bug-finding rather than for a compiler on a build machine.
Do not analyse at all: a baseline JIT tier or an -O0 build skips almost everything here, on the reasonable grounds that compile time is what the user is waiting for.

See it for yourself

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

gcc -fdump-tree-all writes a dump per pass, several of which print the data-flow results the pass consumed; the .dse and .dce dumps are the readable ones.
llc -print-after=livedebugvalues and llc -debug-only=regalloc expose the liveness LLVM computed on the way into allocation.
opt -passes='print<scalar-evolution>' -disable-output shows a different, loop-oriented analysis in the same spirit, which is a useful contrast with the bit-vector ones.
Our data-flow stepper at /compilers/dataflow runs the framework over an AtlasLang CFG one iteration at a time, so you can watch the sets grow and see where the fixed point is reached.

Plausible wrong readings

Stated the way a confident engineer states them.

"Data-flow analysis tells you what the program does." It tells you what is true on *all* paths, over-approximated. It is deliberately less precise than the program, and the imprecision is what makes it terminate.
"Each analysis is its own algorithm." Each analysis is four choices handed to the same solver. Recognising this is most of what makes a new analysis quick to write.
"If the analysis says a value might be live, it is live." It says it cannot prove otherwise. Over-approximation in the safe direction is the design, not a weakness.
"SSA replaced data-flow analysis." SSA replaced several instances of it for value questions. Liveness is still a backward data-flow analysis in every backend, including SSA ones.

Misconceptions

The claim, and what is actually true.

Data-flow analysis computes what will happen at run time.

It computes what is true on every path, conservatively. A fact that holds only on the path actually taken is invisible to it, by design.

Union versus intersection is a performance choice.

It is a correctness choice. Union answers "on some path" and intersection answers "on every path", and each is unsound if used for the other question.

A more precise analysis is always better.

Precision costs lattice height, which costs iterations, which costs compile time. Every production compiler deliberately uses analyses less precise than it could afford, and the choice is a budget.

Go deeper

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

overview

Data-flow analysis answers questions of the form "what is true at this point in the program, given every way control could have got here". You choose what a fact is, how each instruction changes it, what happens when paths merge, and which direction to travel; then a shared solver iterates until the answers stop changing. Four famous analyses are just four different sets of those choices.

practical

When you meet an analysis you have not seen before, name its four slots and you will understand it. Direction tells you what question it answers. The meet tells you whether it is a "may" or a "must" analysis, which tells you which way its errors go. And the lattice tells you how precise it can possibly be — no amount of iteration makes an analysis say something its lattice cannot express, which is why "the compiler should have known x was positive" usually has the answer "its lattice had no way to say so".

advanced

The framework is the special case of abstract interpretation where the abstract domain is a finite-height lattice and the transfer functions are monotone, which is exactly the condition that makes naive iteration terminate at the least fixed point. Step outside it — intervals, for instance, whose lattice has infinite height — and iteration need not terminate; you need a widening operator that jumps to a coarser fact after a few rounds, and then a narrowing pass to recover some precision. That is the whole difference between the classical compiler analyses and the analyses in a static-analysis tool: the compiler chose finite lattices so that the solver could be simple and fast, and paid for it in expressiveness. Kildall's original 1973 formulation and Kam and Ullman's later generalisation are the two papers that fixed these conditions, and the reason the same code solves four analyses is that they proved it could.

How much this depends on

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

typicalEvery mainstream optimizing compiler contains a shared data-flow solver of roughly this shape — GCC's df infrastructure and LLVM's per-analysis implementations both fit it. What differs is how much is shared: GCC has an explicit framework, LLVM tends towards purpose-built analyses that share the fixed-point idea but not the code.

simplifiedThe union/intersection presentation is the bit-vector special case. The general requirement is a semilattice of finite height with monotone transfer functions; constant propagation already exceeds the bit-vector case, and interval or relational domains exceed it far more and need widening to terminate at all.

implementationAtlasLang implements one instance of this framework for real — liveness() in src/compilers/sim/regalloc.ts — and the data-flow stepper animates the others over the same CFG. Our solver iterates over blocks in reverse order rather than using a priority worklist, which affects how many passes it takes and nothing else.

If you were asked this in an interview

Describe the data-flow framework in four parts, then instantiate it for liveness.
When do you use union at a merge and when do you use intersection? What happens if you swap them?
What does it mean for a data-flow analysis to be sound, and in which direction may it be wrong?

Connections

DSAdirected-graph dfs bfs topological-sort

Domains that do not exist yet

Testing & Reliability Engineering — Testing an analysis rather than a transformation
A data-flow analysis changes no code, so its output can be compared directly against a hand-computed answer or a brute-force path enumeration on small graphs. That makes these the easiest passes to test well, and the general property-testing technique is owned there.