Data Flowimplementation

Forward and Backward Analysis

Liveness runs backward because "is this value needed?" is a question about the future. Reaching definitions runs forward because "where did this value come from?" is a question about the past. The direction is dictated by the question, and choosing it is not a design decision.

The question

How do I know whether an analysis should run forwards or backwards through the control-flow graph?

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

What the program is here

The CFG traversed in one of its two orientations. A forward analysis reads predecessors and computes what has already happened; a backward analysis reads successors and computes what is still going to be needed. Same graph, same solver, edges followed in opposite directions — and the annotated result answers a question that is either about the program's past or about its future, never both.

What this phase may assume or do

A forward analysis is entitled to assume that facts at a block's entry summarise every path from the function entry to that point, and it must therefore begin at the entry block with the function's entry condition. A backward analysis is entitled to assume the mirror image, and must begin at every exit block with what holds on return. Getting the boundary wrong is unsound in a specific way: a backward analysis that forgets a return value is live at an exit will report it dead, and the register holding the return value can then be reused before the return.

Key points

The direction follows from whether the question is about the program's past or its future.
Forward: meet over predecessors, boundary at the entry block. Backward: meet over successors, boundary at every exit.
A CFG has one entry and possibly many exits, so backward analyses have several boundary blocks and forgetting one is a real bug.
Direction also fixes the fast visit order: reverse post-order forward, post-order backward.
Swapping the direction of an analysis does not make it imprecise; it makes it answer a different question incorrectly.
When an optimization needs both directions, run two unidirectional analyses rather than one bidirectional framework.

The direction is in the question

Ask what the analysis is *for*, phrase it as a sentence, and read which way it points. "Which assignments may have produced the value I am reading?" is entirely about what has already executed — forward. "Will anything read this value before it is overwritten?" is entirely about what is going to execute — backward. There is no third option and no room for preference.

The reason it feels like a choice is that both analyses run on the same graph with the same solver, so the code looks nearly identical. It is not. Swapping the direction of an analysis does not make it less precise; it makes it answer a different question, and the answer will be confidently wrong.

A useful check: which end of the program is the *boundary condition* at? If you know something about the state on entry to the function, the analysis is forward and that is where it starts. If you know something about the state at the return — the return value is live, callee-saved registers are live — it is backward and it starts there.

Reading the direction off the question

Question	About	Direction	Boundary condition
Which definitions may reach this use?	The past	Forward	At the entry: parameters are defined, locals are not
Is this value needed later?	The future	Backward	At each return: the returned value is live
Has this expression already been computed on every path?	The past	Forward	At the entry: nothing is available
Is this value known to be a constant here?	The past	Forward	At the entry: parameters are unknown
Is this store overwritten before anything reads it?	The future	Backward	At each return: memory visible to the caller is live
Can this expression be moved later without changing anything?	The future	Backward	At each return: nothing is anticipated

The same graph, two orientations

Mechanically the difference is two lines. A forward analysis meets over *predecessors* and pushes facts along edges as they are drawn; a backward analysis meets over *successors* and pushes facts against them. Everything else — the lattice, the fixed point, the termination argument — is unchanged, which is why a well-built solver takes the direction as a parameter.

The one asymmetry worth knowing is about entry and exit blocks. A CFG has exactly one entry, so a forward analysis has one boundary. It may have many exits — several return statements, or a return plus a trap — so a backward analysis has several, and every one of them needs the boundary fact. A backward analysis that initialises only the last block in the listing is a real bug with an intermittent symptom.

One CFG, read both ways

b0entryentry
```
%0 = param 0
branch %0 ? b1 : b2
```
Forward analyses start here.
b1then
```
%1 = int %0 + 1
```
b2else
```
%2 = int %0 * 2
```
b3join
```
%3 = phi [%1 from b1, %2 from b2]
ret %3
```
Backward analyses start here — and at every other exit.

Edges

b0→b1
b0→b2
b1→b3
b2→b3

Immediate dominator

b0idomb0(entry)
b1idomb0
b2idomb0
b3idomb0

Read it asA forward analysis at b3 meets the facts arriving from b1 and b2. A backward analysis at b0 meets the facts required by b1 and b2. Both are looking at the same two edges; the difference is whether the edge is a source of information or a consumer of it.

What the direction does to convergence

The direction also decides the good visit order, which is why the two matter together. A forward analysis converges fastest in reverse post-order, because that visits a block after as many of its predecessors as the graph allows. A backward analysis wants the reverse of that — post-order — for the same reason with successors.

Our engine takes the shortcut of sweeping the block list from last to first, which for the block numbering AtlasLang produces is close enough to the ideal backward order, and its comment is explicit that this is a speed decision only: *correctness does not depend on it, only speed. That is true of every data-flow analysis.*

Where the direction genuinely changes the difficulty is at loops. For a backward analysis a loop's back edge means information from the header must travel to the body, which the first sweep cannot know — this is why [[liveness-analysis]] needs at least two rounds on any loop. For a forward analysis the same thing happens in the other direction. Neither is harder than the other; both are the reason iteration exists.

Both directions at once, and when that is a different thing

typicalMainstream compilers implement PRE and its relatives as several unidirectional passes rather than as one bidirectional analysis, following the lazy-code-motion formulation. Bidirectional frameworks appear in the literature and in a few specialised analyses; the reason they are rare is not that they are unsound but that their termination and precision arguments are much harder to get right.

Some optimizations need facts from both directions, and the right response is two analyses rather than one bidirectional one. Partial redundancy elimination is the classic case: it needs *availability* (a forward, must analysis — has this been computed already?) and *anticipability* (a backward, must analysis — will this be computed on every path from here?), and it places the computation where the two meet. Lazy code motion is that pair plus two more passes to pick the latest safe placement.

Genuinely bidirectional frameworks — where a single set of equations has facts flowing both ways simultaneously — exist, and are notoriously harder to reason about, because the monotonicity and termination arguments are no longer the simple ones from [[fixed-point-iteration]]. The practical advice is the one Knoop, Rüthing and Steffen made famous by reformulating PRE as four unidirectional analyses instead of one bidirectional one: if you think you need a bidirectional analysis, you probably need two.

How it works

The steps, in the order the compiler takes them.

State the question the transformation needs answered, as a sentence about a program point.
If the sentence refers to what has already executed, the analysis is forward; if to what will execute, backward.
Set the boundary: entry block for forward, every exit block for backward, with the fact that genuinely holds there.
Meet over predecessors (forward) or successors (backward), then apply the block transfer function in the matching direction.
Iterate in reverse post-order (forward) or post-order (backward) until nothing changes.
Read the result at the program points the transformation asks about — for a backward analysis that usually means the point *after* an instruction, which is a common off-by-one.

How it breaks

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

A backward analysis initialises only one exit block. Values live at the other returns are reported dead, their registers are reused, and the function returns garbage on the paths that use the neglected exit.
A forward analysis is written with the meet over successors by copy-paste from a backward one. It converges, produces plausible sets, and every optimization built on it is wrong in a way no verifier will catch.
The result is read at the wrong side of an instruction — live-in where live-out was meant. Interference is computed against the wrong set and two values that overlap get the same register, corrupting one of them.
An analysis is run forward because the code for a forward solver was already there. The answer looks reasonable on straight-line code and is wrong the moment there is a branch, which is exactly the code the tests are thinnest on.

When it helps

Choosing correctly is not optional, so the value here is diagnostic: when an analysis gives an answer that feels backwards, checking the direction against the question is the fastest first test.
Reading an unfamiliar compiler. Finding the meet — over predecessors or successors — tells you what the pass is for before you read anything else.
Designing a new analysis, where writing the question as a sentence first prevents the most expensive possible mistake.

When it hurts

When an optimization genuinely wants correlated information from both directions and neither analysis alone suffices, so you pay for two passes and combine their results by hand.
On graphs with many exits — exception edges, multiple returns, noreturn calls — where the backward boundary is more work to get right than the analysis itself.
When the natural question is about paths rather than points, in which case neither direction helps and the framework is the wrong tool.

What it costs

Every one of these is paid by something.

A direction-parameterised solver buys one implementation for both kinds of analysis; it pays an indirection on the hottest loop in the compiler, and code that is harder to read than two specialised solvers.
Running two unidirectional analyses instead of one bidirectional one buys tractable termination and precision arguments; it pays two full passes over the function and the memory for both results at once.
Choosing the fast visit order buys fewer rounds; it pays a reverse-post-order computation up front, which on a small function can cost more than the rounds it saves.

What else you could do

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

Formulate the question over SSA def-use edges instead of the CFG. Direction then means "along uses" or "along definitions", and for value questions the traversal is much smaller.
Use a bidirectional framework where the problem genuinely is bidirectional. Sound, and much harder to establish termination and precision for, which is why the lazy-code-motion reformulation into four unidirectional passes became the standard treatment.
For "is this value needed" specifically, an SSA compiler can often skip liveness entirely at the IR level by using the use lists — though the backend still needs real liveness over the CFG, because a register allocator asks about program points rather than values.
Demand-driven analysis: rather than computing facts everywhere, answer a specific query by walking backwards from the point of interest. Cheaper for a handful of queries, more expensive if you end up asking about most of the function.

See it for yourself

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

Read any compiler's solver and find the meet: for pred in block.preds or for succ in block.succs is the whole answer to which direction it runs.
llc -debug-only=regalloc prints live-in and live-out sets, which are the output of a backward analysis and can be checked by hand on a small function.
gcc -fdump-tree-dse shows dead store elimination, which is the backward analysis in this lesson applied to memory rather than registers.
Our data-flow stepper lets you run the same CFG in both directions and see how differently the sets fill in.

Plausible wrong readings

Stated the way a confident engineer states them.

"Backward analyses are harder." They are the same solver with succs instead of preds. What is harder is remembering that there may be several exit blocks.
"Forward means following the instruction order." It means following control-flow edges from predecessors. In a loop that is not the listing order, and assuming it is produces a solver that works on straight-line code only.
"An analysis can be run either way and you pick the more precise one." Running it the other way answers a different question. Precision does not enter into it.
"Liveness could be forward if I tracked definitions instead." Tracking definitions forwards is reaching definitions, which is a different analysis with a different answer. It cannot tell you whether anything will read the value.

Misconceptions

The claim, and what is actually true.

The direction of an analysis is an implementation choice.

It is determined by the question. An analysis run in the wrong direction computes a well-defined answer to a question nobody asked.

Backward analysis means processing instructions in reverse order within a block.

It means that too, but the defining property is meeting over successors rather than predecessors. Within-block order is a consequence.

A bidirectional analysis is the natural answer when you need both kinds of fact.

Two unidirectional analyses are almost always the better engineering, which is exactly the lesson of the lazy-code-motion reformulation of PRE.

Go deeper

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

overview

Some questions are about what already happened — which assignment produced this value, has this expression been computed yet — and those analyses run forwards from the function entry. Others are about what is still to come — will anything read this value, is this store ever observed — and those run backwards from the returns. The question decides; there is nothing to choose.

practical

When reading an analysis, find the meet loop: predecessors means forward, successors means backward. When writing one, write the question as a sentence first and check which tense it is in. And when a backward analysis behaves oddly, check that every exit block got its boundary fact — a function with two returns and one initialised exit is a bug that only shows on one path.

advanced

The pairing of directions is where the interesting optimizations live. Availability is forward-must; anticipability is backward-must; an expression can be computed at a point exactly where it is anticipated and not yet available, and the *latest* such point is the one that minimises register pressure. Knoop, Rüthing and Steffen's lazy code motion is four unidirectional analyses composed to find exactly that point, and it subsumes loop-invariant code motion and partial redundancy elimination in one framework. The historical lesson is worth keeping: the original PRE formulation was bidirectional and correspondingly hard to reason about, and reformulating it as a composition of unidirectional passes made it both easier to prove and easier to implement. When a problem seems to need facts flowing both ways at once, the productive move is almost always to factor it.

How much this depends on

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

implementationAtlasLang's liveness() sweeps blocks from last to first rather than computing a true post-order, which is close enough for the block numbering our lowering produces. A production solver computes the order explicitly, because a compiler cannot rely on block ids correlating with graph structure after passes have reordered them.

typicalMainstream compilers implement partial redundancy elimination as several unidirectional analyses rather than one bidirectional framework, following lazy code motion. Bidirectional frameworks are sound and are used occasionally; they are rare because their termination and precision arguments are substantially harder.

simplifiedOur CFGs have a single exit block because AtlasLang functions have one return path after lowering. Real functions have several exits — multiple returns, exception edges, noreturn calls — and every one of them is a boundary a backward analysis must initialise.

If you were asked this in an interview

Is liveness forward or backward? Justify it from the question rather than from memory.
Where does a backward analysis get its boundary condition, and what goes wrong if a function has two returns?
An optimization needs to know both that an expression is already available and that it will definitely be used. How would you structure that?

Connections

DSAdirected-graph dfs topological-sort

Domains that do not exist yet

Programming Languages & Runtime Internals — What is live at a safepoint, from the collector's point of view
A garbage collector needs to know which references are live at each safepoint, which is the same backward question the compiler already answered for register allocation. The compiler emits the stack map; what the collector does with it is owned there.