Solve a data-flow problem on the program's graph
This data-flow analyzer computes reaching definitions and live variables for small three-address programs. It first constructs the same basic blocks and control-flow edges used by the flow-graph tool, then builds local sets and iterates the appropriate equations until no set changes. The loaded loop produces a complete result immediately, with the stable round displayed first.
Reaching definitions are a forward may analysis
A definition gives a variable a value at a particular instruction. The analyzer numbers explicit program definitions by instruction ordinal, not by visual source line. A reaching definition may arrive at a point along a path with no intervening definition of the same scalar. At a join, it is enough for a definition to arrive on a possible incoming path, so predecessor information is combined with union.
For a scalar assigned more than once inside a block, GEN keeps its final local definition. KILL contains the other numbered definitions of the scalars written in that block. The equations are IN[B] = union of predecessor OUT sets, followed by OUT[B] = GEN[B] ∪ (IN[B] − KILL[B]). External input values are not given synthetic definition numbers. An empty set of local reaching definitions therefore does not, by itself, establish that an input variable is uninitialized.
Live variables are a backward may analysis
A variable is live when its current value may be used later before a replacement definition. USE contains names read before a local definition, while DEF contains the scalars defined in the block. Reading a variable after assigning it locally does not add its incoming value to USE, but a self-update at the start of a block reads the old value before defining the new one.
The backward equations are OUT[B] = union of successor IN sets and IN[B] = USE[B] ∪ (OUT[B] − DEF[B]). The live-at-exit field supplies the boundary values for reachable program exits. It defaults to out in the loaded example and can be left blank for an empty exit boundary. State that boundary when comparing answers: different assumptions about what is needed after the program can legitimately produce different liveness sets.
A worked loop with joins and redefinitions
The loaded program is:
a = 1
b = 2
L1: c = a + b
if c < 10 goto T
a = b
goto J
T: b = a
J: a = a + 1
if a < 5 goto L1
out = a + b
Its generated graph has 6 blocks and 7 explicit definitions. The definition legend is:
| Definition | Variable | Instruction |
|---|---|---|
| d1 | a | 1 |
| d2 | b | 2 |
| d3 | c | 3 |
| d5 | a | 5 |
| d7 | b | 7 |
| d8 | a | 8 |
| d10 | out | 10 |
Running forward reaching definitions gives these stable sets:
| Block | IN | OUT |
|---|---|---|
| B1 | {} | {d1, d2} |
| B2 | {d1, d2, d3, d7, d8} | {d1, d2, d3, d7, d8} |
| B3 | {d1, d2, d3, d7, d8} | {d2, d3, d5, d7} |
| B4 | {d1, d2, d3, d7, d8} | {d1, d3, d7, d8} |
| B5 | {d1, d2, d3, d5, d7, d8} | {d2, d3, d7, d8} |
| B6 | {d2, d3, d7, d8} | {d2, d3, d7, d8, d10} |
Using out as the live-at-exit boundary gives:
| Block | Live IN | Live OUT |
|---|---|---|
| B1 | {} | {a, b} |
| B2 | {a, b} | {a, b} |
| B3 | {b} | {a, b} |
| B4 | {a} | {a, b} |
| B5 | {a, b} | {a, b} |
| B6 | {a, b} | {out} |
Both tables are generated by the library used on this page. The forward result is confirmed unchanged at round 3; the backward result is confirmed unchanged at round 2. Those round numbers describe this processing order and example, not a universal convergence count for the algorithm.
Follow the iterations from empty sets
The initial round contains empty IN and OUT sets. Each forward sweep visits reachable blocks in source order, using the current predecessor information. Each backward sweep visits them in reverse source order, using current successor information. A round records the sets after its complete sweep, and the final recorded sweep confirms that nothing changed.
Choose an earlier round to see the information grow, then advance with the round controls. GEN/KILL or USE/DEF stays tied to the input program while IN/OUT evolves. Updates inside a sweep use the latest available values, so a different valid iteration order may converge in a different number of rounds while reaching the same fixed point. Do not compare intermediate round numbers without also comparing the update convention.
Treat unreachable blocks and arrays carefully
Unreachable blocks remain in the graph and local-set tables so the original input can be inspected. Their IN/OUT sets stay empty, and their edges do not contribute facts to reachable blocks. Reachability here is structural from the entry. A constant condition is not simplified, so branches that look impossible after arithmetic reasoning can still be present in this conservative graph.
Array accesses use a whole-region name such as a[]. A store to one cell is a may-definition of that region, not proof that every earlier cell definition has been overwritten. Reaching analysis therefore retains earlier possible region definitions, and liveness does not kill the whole region on a partial store. This is intentionally less precise than element-sensitive memory analysis. Distinct array symbols are treated as distinct regions; arbitrary pointer aliases and procedure side effects are not modeled by this TAC dialect.
Interpret what the result can justify
Both analyses use union at control-flow joins because they ask whether a fact may hold on some path. This differs from a must property such as dominance, where predecessor information is intersected. Reaching definitions can help explain where a use might obtain its value; liveness can help a code generator decide which values must remain available. Neither result alone gives permission to remove every instruction with a dead destination.
A division or load can have relevant behaviour even when its result is unused. The code optimizer separately applies conservative transformation rules under its own integer and observable-output contract. Keep the distinction between computing a data-flow fact and proving a particular optimization safe.
Copy the analysis and continue
The compiler lab links the related graph and optimization tools. Copy analysis saves the local sets, stable result and iteration history as text. The source-size and table limits keep the walkthrough readable; this is an educational finite-set solver rather than a production whole-program analysis framework.