ToolSphere

Data-Flow Analysis

Computer science

Compute reaching definitions or live variables on a TAC flow graph, with GEN/KILL or USE/DEF sets and every fixed-point iteration through convergence.

Edit labelled instructions, then follow how block sets settle.

6 blocks; 3 rounds; B1 OUT {d1, d2}

6 blocks · fixed point confirmed at round 3

Copy analysis

GEN and KILL sets

GEN adds the block’s surviving definitions; KILL removes older definitions of overwritten scalars.

BlockGENKILL
B1{d1, d2}{d5, d7, d8}
B2{d3}{}
B3{d5}{d1, d8}
B4{d7}{d2}
B5{d8}{d1, d5}
B6{d10}{}

Control-flow graph

Scroll inside the graph to read all edge labels and blocks.

fallthroughtruefalsejumpfallthroughtruefalsefallthroughB1Instructions 1–2B2Instructions 3–4B3Instructions 5–6B4Instructions 7–7B5Instructions 8–9B6Instructions 10–10Exit

Fixed-point iterations

A fixed point means another pass changes no sets. IN is before a block; OUT is after it.

The final sweep is displayed initially. Earlier sweeps show the sets growing from empty; the last sweep makes no change.

BlockINOUT
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}

Definition legend

DefinitionVariable / instructionTAC
d1a · 1a = 1
d2b · 2b = 2
d3c · 3c = a + b
d5a · 5a = b
d7b · 7b = a
d8a · 8a = a + 1
d10out · 10out = a + b

Equations and assumptions

IN[B] = union of OUT[P] over reachable predecessors
OUT[B] = GEN[B] ∪ (IN[B] − KILL[B])
  • Forward may analysis; only explicit program definitions are numbered. External input definitions are not added.
  • Unreachable blocks are displayed but do not contribute to the reachable fixed point.
  • Array stores are conservative may-definitions of the region a[]: they do not kill all earlier region definitions or make the whole region dead.
  • Each sweep uses current information in source order for reaching definitions and reverse source order for liveness. The last sweep confirms no change.

On this browser only

Give feedback

Did this tool help?

Tell us what worked, what didn’t, or what you’d like next.

Opens Google Forms in a new tab with this tool’s name filled in. No sign-in or email required. Feedback is optional.

How to use Data-Flow Analysis

  1. 1Edit the loaded TAC loop or paste a small program using the documented labels and jump syntax.
  2. 2Choose reaching definitions for forward analysis, or live variables for backward analysis.
  3. 3For liveness, state the variables needed at program exit; an empty field means an empty exit boundary.
  4. 4Inspect the local sets and flow graph, then select earlier rounds to follow convergence from the initial empty sets.
  5. 5Read the stable IN/OUT sets and copy the analysis with its assumptions.

About Data-Flow Analysis

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.

Frequently asked questions

What is a reaching definition?

It is a definition that may reach a point along a path without another definition replacing the same scalar value. The analyzer numbers explicit program definitions and lists their instructions in a legend.

Why is union used at a join?

These are may analyses: a fact can matter if it occurs on any possible path. A must analysis such as dominance uses different join reasoning.

What do GEN and KILL contain?

GEN contains definitions produced locally that survive to the block exit. KILL contains the other numbered definitions of scalars written by that block.

What is the difference between USE and DEF?

USE records incoming values read before a local definition. DEF records scalar names assigned in the block; a read after a local assignment does not require the incoming value for USE.

Why does the live-at-exit field change the answer?

It supplies the boundary condition describing values needed after the program. Different valid boundary assumptions can produce different liveness results.

Why does the last iteration repeat the previous result?

The final sweep verifies that no IN or OUT set changes. It is the convergence check, not an extra source-program execution.

Are external inputs numbered as definitions?

No. Only explicit program definitions receive numbers here. Missing local reaching definitions do not automatically mean an external input is uninitialized.

How is unreachable code handled?

It remains visible but does not contribute to the reachable fixed point. The graph uses structural reachability and does not evaluate constant branch conditions.

Why does an array store not kill all array definitions?

Writing one cell does not replace every cell in a whole-region abstraction. The tool treats such stores conservatively as may-writes to a[] rather than exact element definitions.

Can I remove code just because its result is dead?

Not without checking effects and possible errors. Liveness is one input to an optimization proof; it does not make every unused division, load or store removable.

Have a suggestion for Data-Flow Analysis?Share your feedback ↗