Iterating to a Fixed Point
Apply the equations until nothing changes. It terminates because the transfer functions are monotone over a lattice of finite height, so a fact can only move one way and only so far. Worklist order changes how many rounds it takes and never what it converges to.
Why does "keep applying the equations until they stop changing" terminate, and why does the order I visit blocks in not change the answer?
The CFG with a fact attached to each block, mid-solve — a partial answer that is not yet correct. The whole method is defined by that intermediate state: it starts at the identity for the meet, moves monotonically towards the true answer, and stops when a full round produces no change. The representation exists to answer "have we finished?", which is a question about the previous iteration rather than about the program.
The iteration converges to the least fixed point, and is therefore sound, only if two conditions hold: the transfer functions are monotone — a stronger input never produces a weaker output — and the lattice has finite height, so no chain of strictly increasing facts can be infinite. Break monotonicity and the iteration can oscillate; break finite height and it need not terminate at all, which is why analyses over intervals or other infinite domains require a widening operator. The solver is entitled to assume every block's equation depends only on its neighbours' current facts, with no hidden state between rounds.
Key points
- Iteration terminates because transfer functions are monotone and the lattice has finite height — facts move one way and only so far.
- For bit-vector analyses that means sets only grow (union) or only shrink (intersection), over a finite universe.
- The fixed point is a property of the equations; any schedule that runs until nothing changes finds the same one.
- Visit order changes the number of rounds and nothing else: reverse post-order for forward analyses, its reverse for backward ones.
- A worklist processes only the blocks whose inputs changed, which is strictly less work than a full sweep.
- Non-boundary blocks must start at the meet's identity — empty for union, full for intersection — or the analysis converges to something useless but sound.
- A loop always needs at least two rounds, because the back edge carries information the first pass cannot have seen.
Why it stops
The termination argument is short and worth being able to state, because it is the same argument for every instance. Facts move in one direction only. A set-valued "may" analysis starts empty and only ever adds elements; a "must" analysis starts full and only ever removes them. Since the universe of possible elements is finite — finitely many definitions, finitely many registers, finitely many expressions in the function — a set cannot change more than a bounded number of times.
That is exactly what the comment on our own liveness() says: *the iteration terminates because the sets only grow and the register space is finite — the standard monotone-framework argument.* The word carrying the weight is monotone: applying a transfer function to a larger input must not produce a smaller output. If that held only sometimes, a fact could grow and then shrink, and there would be nothing to bound the number of rounds.
The general statement is Kleene's: a monotone function on a lattice of finite height, started at the bottom element, reaches its least fixed point in at most as many steps as the lattice is tall. For bit-vector analyses the height is the size of the universe, which is why they converge fast in practice, and usually in far fewer rounds than the bound.
A real fixed point, one round at a time
liveness() in src/compilers/sim/regalloc.ts, which sweeps fn.blocks from last to first and repeats while anything changed. The final answer matches the function's output exactly; the intermediate rounds are specific to that visit order, and a different order reaches the same final answer in a different number of rounds.Here is liveness() from src/compilers/sim/regalloc.ts converging on a real loop. The function is fn f(k: int): int { let n = 0; while (n < k) { n = n + 1; } return n; }, and the interesting value is %0 — the parameter k. It is read in the loop header and nowhere else, and it must therefore stay live across the whole loop body, including the back edge.
The solver walks blocks in reverse order — b3, b2, b1, b0 — and the first round cannot possibly get %0 right. When it processes b2 (the loop body) it needs the live-in set of b1 (the header), and b1 has not been visited yet, so its live-in is still empty. The first round therefore concludes that %0 is dead inside the loop body, which is wrong.
The second round fixes it. By then b1's live-in is {%0}, so b2's live-out becomes {%0, %5} and its live-in becomes {%0, %7}. A third round changes nothing, and the solver stops. Two rounds of real work, one round to notice it is finished.
toSSA output▸b0: ; entry▸ %0 = param 0 ; k: int▸ jump b1▸b1: ; while.cond preds=b0,b2▸ %7 = phi n [0 from b0, %5 from b2]▸ %3 = bool %7 < %0▸ branch %3 ? b2 : b3▸b2: ; while.body preds=b1▸ %5 = int %7 + 1▸ jump b1▸b3: ; while.exit preds=b1▸ ret %7
Read it as%0 appears exactly once, in b1. Everything the analysis has to discover about it — that it survives the whole loop — is a consequence of the back edge b2 -> b1, and no single pass over the blocks in any order can see that consequence before it has seen the header.
| Block | Initial | After round 1 | After round 2 | After round 3 |
|---|---|---|---|---|
| b3 (exit) | {} | {} | {} | {} — stable |
| b2 (body/latch) | {} | {%5} | {%0, %5} | {%0, %5} — stable |
| b1 (header) | {} | {%7} | {%0, %7} | {%0, %7} — stable |
| b0 (entry) | {} | {%0} | {%0} | {%0} — stable |
Order changes speed, not the answer
This is the property that makes the whole method practical, and it is worth stating precisely. The fixed point is a property of the *equations*, not of the procedure used to solve them. Any schedule that keeps applying equations until none of them changes anything arrives at the same least fixed point, because the least fixed point is unique for a monotone function on a lattice.
What the order changes is how many times you apply an equation before it is stable. Visiting a block before its inputs are known wastes a round; visiting it after saves one. For a forward analysis the good order is reverse post-order, which visits a block after as many of its predecessors as the graph shape allows. For a backward analysis it is the reverse of that — which is exactly the choice our engine makes, and its comment says why: *reverse order converges faster for a backward analysis; correctness does not depend on it, only speed. That is true of every data-flow analysis.*
The refinement of this idea is the worklist. Instead of sweeping every block every round, keep a queue of blocks whose inputs have changed and process only those, pushing a block's neighbours when its own fact changes. That does strictly less work than a full sweep, and using a priority queue ordered by reverse post-order rather than a plain FIFO usually reduces the round count further.
1ROUND-ROBIN (what AtlasLang does)2 repeat3 changed = false4 for each block B in a fixed order:5 recompute in[B], out[B]6 if either changed: changed = true7 until not changed8 9WORKLIST10 worklist = all blocks11 while worklist not empty:12 B = worklist.pop() // pop order = the heuristic13 recompute in[B], out[B]14 if in[B] changed:15 push every predecessor of B // backward analysis16 17Both reach the same fixed point. The worklist touches fewer blocks;18the pop order decides how many fewer.The round-robin version is easier to read and to prove things about, which is why our engine uses it. On a function with thousands of blocks the difference stops being cosmetic.
Where the initial value comes from
One detail decides whether the iteration converges to the right thing at all: the starting fact for blocks other than the boundary. It must be the identity for the meet operator — the empty set for a union analysis, the *full* set for an intersection analysis.
The reason is that an unvisited neighbour must not constrain the answer. Under union, meeting with the empty set leaves the fact unchanged; under intersection, meeting with the full set leaves it unchanged. Start a "must" analysis with empty sets instead and every meet immediately produces empty, the iteration terminates in one round, and the analysis reports that nothing is ever available. It is sound — the answer is an under-approximation of a must-property, which is the safe direction — so nothing crashes and nothing is wrong. The optimization it feeds just never fires, and that is a difficult bug to notice, because "the compiler did not optimize this" has a hundred other explanations.
The boundary block is the exception and takes the real boundary condition: for a forward analysis the entry block starts with whatever holds on entry to the function; for a backward analysis every exit block starts with what is live on return.
The sparse alternative
Everything above is *dense*: a fact is computed at every program point, and the cost scales with points times facts. Over SSA there is a cheaper shape. Facts about values can be attached to the values themselves and propagated along def-use edges, so a value is revisited only when one of its inputs actually changes. The fixed point is the same idea; the graph it iterates over is smaller.
The best-known instance is sparse conditional constant propagation, which iterates two worklists at once — one for values whose lattice element changed, one for CFG edges newly discovered to be reachable — and is both faster and strictly more precise than running constant propagation and unreachable-block elimination separately. [[constant-propagation]] covers what it does; the point here is that the termination argument is identical, and only the graph changed.
How it works
The steps, in the order the compiler takes them.
- Initialise the boundary block with the boundary fact, and every other block with the identity element for the meet.
- Choose a visit order: reverse post-order for forward analyses, reverse of reverse post-order for backward ones.
- For each block, apply the meet over its neighbours in the analysis direction to get the incoming fact.
- Apply the block's transfer function — for the classic instances, remove
killand addgen— to get the outgoing fact. - Record whether either set changed for this block.
- Repeat until a full pass changes nothing, or in the worklist form, until the worklist is empty.
- In practice, cap the iteration count as a defensive measure: a solver that cannot converge is a bug, and an infinite loop in a compiler is worse than an assertion.
How it breaks
What the engineer observes when it goes wrong — not what goes wrong internally.
- A non-monotone transfer function — usually an accidental one, where the block also mutates some shared state — makes the sets oscillate. The solver either loops forever or hits its iteration guard, and the compiler hangs or gives up on a specific input.
- A "must" analysis initialised with empty sets converges instantly to empty. Nothing is wrong, nothing crashes, and an entire optimization silently never fires. This is the most common and hardest to spot bug in the list.
- An analysis over an infinite-height lattice with no widening runs until the iteration guard trips. Compile time explodes on one function, usually one with a loop that increments something.
- A transformation changes the CFG and the cached analysis result is not invalidated. The next pass reads facts about a graph that no longer exists and makes a decision that is wrong for the current program.
- The visit order is chosen badly — forward analysis in post-order, say — and the analysis still gives the right answer but takes many times more rounds. The symptom is compile time, not correctness, and it is easy to mistake for the analysis being inherently expensive.
When it helps
- Every classical analysis in a compiler, and most analyses in a linter or static analyser. One solver serves all of them.
- Any recursive definition where the answer depends on itself around a cycle — dominance is computed the same way, by the same kind of iteration, in
computeDominance. - Reasoning about loops at all. The back edge is exactly the cycle that makes a single pass insufficient, and iteration is the cheapest correct response.
When it hurts
- Very large functions with dense lattices, where the cost is points times facts times rounds and all three are big. This is the argument for sparse formulations over SSA.
- Analyses whose lattice is tall or infinite, where convergence needs widening and the result is much less precise than the domain suggested it would be.
- Fast compilation tiers, where the fixed point costs more than the optimization it enables is worth.
What it costs
Every one of these is paid by something.
- Round-robin iteration buys a solver that is a dozen lines and easy to prove correct; it pays repeated recomputation of blocks that could not have changed, which is wasted time on large functions.
- A worklist buys fewer block visits; it pays a queue, a membership test to avoid duplicates, and a priority order that has to be maintained as the CFG changes.
- A taller lattice buys precision; it pays directly in rounds, because the bound on iterations is the lattice height, and in memory for the larger facts at every point.
- Widening buys termination on infinite domains; it pays precision, sometimes dramatically — a widened bound is often just "unbounded", and the narrowing pass that recovers some of it is extra machinery and extra time.
What else you could do
What a different compiler or language does instead, and when that is better.
- Elimination methods — interval analysis in the older sense, or Tarjan's path-compression approach — solve the equations by structurally reducing the graph rather than by iterating. They are asymptotically better on reducible graphs and considerably more complex, which is why iterative solvers dominate in practice.
- Sparse propagation over SSA def-use edges, which iterates over a smaller graph for value questions. Strictly cheaper where it applies, and it does not apply to questions about program points.
- For dominance specifically, Lengauer-Tarjan computes the answer in near-linear time without iterating. Our engine deliberately uses the iterative Cooper-Harvey-Kennedy method instead, because it is twenty legible lines and fast enough for any program a learner will type.
- Solve the constraints with a general constraint solver or a datalog engine. This is what several modern program-analysis frameworks do, and it buys declarative analyses at the cost of a large dependency and much less control over performance.
See it for yourself
The flag, dump or tool that shows you this directly.
gcc -fdump-tree-all-detailsincludes iteration counts and intermediate sets for several analyses, which is the easiest way to see a real fixed point converge.llc -debug-only=regallocprints the liveness LLVM computed on the way into allocation, so you can compare the final sets against your own hand computation.- Instrument any solver you are reading with a counter on the outer loop. The round count on real functions is almost always small, and seeing that number is worth more than any amount of asymptotic reasoning.
- Our data-flow stepper at
/compilers/dataflowadvances one round at a time over an AtlasLang CFG and highlights which sets changed, which is the same table as in this lesson, generated live.
Plausible wrong readings
Stated the way a confident engineer states them.
- "It terminates because the program is finite." The program being finite is necessary and not sufficient — the *lattice* must have finite height. An interval analysis on a finite program does not terminate without widening.
- "Choosing a better visit order gives a better answer." It gives the same answer sooner. If a different order changes your result, the transfer functions are not monotone and you have a bug.
- "The worklist algorithm is a different analysis." It is a different schedule for the same equations.
- "One pass over the blocks is enough if I order them well." Not with a back edge. A loop carries information from the bottom of the body to the top, and no order of blocks can visit a block before itself.
Misconceptions
The claim, and what is actually true.
Go deeper
The same idea at increasing depth. Stop wherever it stops being useful.
overview
Solving a data-flow problem means applying its equations over and over until the answers stop changing. It always stops, because each fact can only move in one direction and the number of things a fact can contain is finite. It always stops at the same answer, whatever order you visit blocks in; the order only decides how many rounds it takes.
practical
Two things to check when a solver misbehaves. If it never terminates, look for a transfer function that is not monotone, or a lattice you did not realise was infinite. If it terminates instantly with useless answers, check the initial value for non-boundary blocks — a "must" analysis must start full, not empty, and starting empty gives you a sound, worthless result that nothing will flag. And when you are reading someone else's solver, find the visit order first: it tells you which direction the analysis runs even when nothing else in the code says so.
internals
The formal content is Kleene's fixed-point theorem specialised to a finite-height lattice: starting from bottom, iterating a monotone function reaches the least fixed point in at most height steps. Kildall gave the compiler formulation in 1973; Kam and Ullman generalised it beyond distributive frameworks and, importantly, showed where the generalisation costs you. For a *distributive* framework — the bit-vector analyses are distributive — the iterative solution coincides with the meet-over-all-paths answer, which is the answer you would get by enumerating every path and merging. For a merely monotone framework, the iterative answer is a safe over-approximation of the meet-over-all-paths answer and can be strictly worse. Constant propagation is the standard example of the gap: merging two branches loses the correlation between two variables that a path-by-path enumeration would keep. That gap is not a defect in the solver — it is the price of not enumerating paths, and enumerating paths is exponential.
How much this depends on
Nothing in this domain is true of every compiler. These say how much.
liveness() in src/compilers/sim/regalloc.ts, which uses a reverse round-robin sweep with an iteration guard of 1000. LLVM and GCC use worklist solvers with priority orders, so their intermediate states differ; the final answer does not.If you were asked this in an interview
- Why does data-flow iteration terminate? State the argument precisely.
- Does the order in which you visit basic blocks affect the result? What does it affect?
- A "must" analysis reports that nothing is ever available. Where would you look first?
- How many rounds does a loop need at minimum, and why?
Connections
- Testing & Reliability Engineering — Testing an iterative solver against a brute-force referenceOn small graphs the meet-over-all-paths answer can be computed by enumeration, which gives an exact oracle for a distributive analysis. Building that kind of differential oracle is a general testing technique and is owned there.