Data Flowtypical

Reaching Definitions

Which assignments may have produced the value I am reading here? A forward, may analysis with union at merges — and the analysis SSA was invented to make unnecessary, because in SSA the answer is the operand name.

The question

Which assignments could have produced the value at this program point, and why does SSA make the question trivial?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute
What the program is here

The CFG annotated with, at every program point, the set of definitions — assignment sites, identified by instruction rather than by value — that may still be the most recent write to their variable. It exists to answer the question a non-SSA three-address program cannot answer locally: *where did this value come from?* The answer is a set, not a single site, because different paths may have written it in different places.

What this phase may assume or do

The analysis is sound only if it is a *may* analysis: the set must contain every definition that reaches on any path, and may contain some that reach on none. Every transformation built on it depends on that direction. Constant propagation outside SSA is legal only when *every* definition in the reaching set is the same literal, so an over-large set costs an optimization and an under-sized set causes a miscompilation. The analysis is entitled to assume the CFG models every way control can arrive at a block; an unmodelled edge — an exception path, a computed jump — makes the set incomplete and therefore unsound.

Key points

  • Reaching definitions answers "which assignments may have produced this value" — a forward, may analysis with union at merges.
  • Facts are sets of definition sites; gen is what the block writes, and kill is every other definition of the same variables anywhere.
  • The set has more than one element exactly where control flow merged with different definitions on the paths.
  • It is what use-def chains are built from, and what non-SSA constant and copy propagation depend on.
  • In SSA the answer is the operand name and the analysis is unnecessary; a phi is exactly the multi-element case written down.
  • Over memory it is not trivial in SSA either, and its precision is bounded by the alias analysis beneath it.
  • It is a may analysis, so it may over-report; under-reporting would be a miscompilation, which is why the meet must be union.

The question, and why a set

Take a three-address program where x is assigned in the then-arm and again in the else-arm, and read afterwards. Which assignment does the read see? Both are possible, and which one actually happens is a run-time property. The honest answer is a set of two definitions, and every transformation that wants to know something about the value has to be true of both.

The classical formulation names definitions by their site — d1: x = 1, d2: x = 2 — and computes, at each program point, the set of definition sites that could still be in force. gen for a block is the definitions it makes; kill is every other definition of the same variables, because a new write to x invalidates all previous ones.

The meet is union, because "reaches" is a possibility: if a definition reaches along any incoming path it belongs in the set. That makes it a forward *may* analysis, which is the same shape as liveness with the direction flipped.

The instance, in the framework's vocabulary
1direction  forward
2meet       union            ("reaches on some path")
3facts      a set of definition sites
4 
5gen[B]     definitions in B that are not overwritten later in B
6kill[B]    all definitions elsewhere of the variables B assigns
7in[B]      union over predecessors P of out[P]
8out[B]     gen[B] union (in[B] minus kill[B])
9 
10boundary   in[entry] = the parameter definitions, nothing else

kill is the part that is easy to get wrong: assigning x in this block kills every *other* definition of x in the whole function, not just the ones in this block.

What it is used for

Reaching definitions is the analysis that builds use-def chains: for each use, the set of definitions that may supply its value. From those chains a non-SSA compiler gets constant propagation (every reaching definition is the same literal), copy propagation (the single reaching definition is a copy whose source has not been reassigned), and a serviceable definition of "uninitialised" (a use whose reaching set contains no definition at all, which is where many compiler warnings come from).

It is also the analysis behind a large fraction of static-analysis tooling. Taint tracking is reaching definitions with definitions labelled by trust; a "variable may be used before assignment" lint is reaching definitions with an extra bottom element. When you see a linter report something about a variable's possible values, this is usually the machinery underneath — see [[static-analysis]].

Two definitions reaching one use
  1. b0entryentry
    d0: x = 0
branch c ? b1 : b2
    gen = {d0}
  2. b1then
    d1: x = 1
    gen = {d1}, kill = {d0, d2}
  3. b2else
    d2: x = 2
    gen = {d2}, kill = {d0, d1}
  4. b3join
    use x
    in = {d1, d2} — d0 was killed on both paths
Edges
  • b0→b1
  • b0→b2
  • b1→b3
  • b2→b3
Immediate dominator
  • b0idomb0(entry)
  • b1idomb0
  • b2idomb0
  • b3idomb0

Read it asThe interesting entry is that d0 does not reach b3, even though it is on every path to it — because both arms overwrite x. That is what kill is for, and it is why the analysis needs the graph rather than just a list of assignments. Change b2 to assign a different variable and d0 reappears in the set.

SSA makes it trivial, and that is the point

In SSA the answer is the operand name. Every value has exactly one definition, so a use's reaching set is a singleton and it is written down in the instruction. The analysis has nothing left to compute.

This is not a coincidence — it is close to the reason the form was invented. The information reaching definitions computes is precisely what SSA construction bakes into the names, and the phi nodes are where the set would have had more than one element. %3 = phi x [1 from b1, 2 from b2] is the set {d1, d2} from the diagram above, written as an instruction instead of as an analysis result.

Two consequences follow. First, in an SSA middle-end, reaching definitions is largely of historical and pedagogical interest — you will meet it in a textbook and in a linter, and not in the pass list. Second, the cost profile changes completely: instead of a fixed-point analysis that must be re-run after every transformation, the information is maintained incrementally by the rewriting itself, which is the argument in [[why-ssa-helps]].

Where it does not become trivial is memory. Loads and stores are not in SSA form unless a memory-SSA layer puts them there, and reaching definitions over memory needs alias information to compute kill at all — a store through an unknown pointer kills everything. That version of the analysis is alive and well in every optimizing compiler.

The same information, two ways
Before
b1: x = 1
b2: x = 2
b3: use x        ; reaching definitions of x here = {b1's, b2's}
After
b1: x1 = 1
b2: x2 = 2
b3: x3 = phi(x1 from b1, x2 from b2)
    use x3       ; the set is the phi
Legal only when

The rewrite is legal wherever SSA construction is legal: the variable's address does not escape, and the phi is placed at the iterated dominance frontier of the definitions so that no path reaches the use without passing through it. Under those conditions the phi records exactly the reaching set, and any transformation that consulted the analysis can consult the phi instead.

Illegal when

The variable is aliased — its address was taken, or it is memory that another thread or another function can write. Then the definitions that reach are not limited to the ones visible in this function, and neither the analysis nor the phi accounts for them. Substituting a value on that basis is a miscompilation; this is why the same reasoning does not transfer to loads and stores without alias analysis.

The precision limits, stated honestly

The set is a *may* set, so it is an over-approximation, and the over-approximation has predictable sources. Path insensitivity: two definitions on mutually exclusive paths both appear in the set even if no single execution could take both. Calls: a call to an unknown function may write anything reachable, so a conservative analysis kills everything it cannot prove untouched. Pointers: without alias analysis, one store kills the whole memory partition.

The consequence in practice is that reaching definitions over registers is precise and useful, and reaching definitions over memory is only as good as the alias analysis under it. That asymmetry — value questions are answerable, memory questions are not without more work — recurs throughout the middle-end, and is why [[alias-analysis]] is disproportionately valuable.

How it works

The steps, in the order the compiler takes them.

  • Number every definition site in the function, and for each variable record the set of its definition sites.
  • For each block compute gen — definitions made here and not overwritten here — and kill — every definition elsewhere of a variable this block assigns.
  • Initialise the entry block with the definitions that hold on entry (parameters), and every other block with the empty set.
  • Iterate forward: the incoming set is the union over predecessors' outgoing sets; the outgoing set is gen plus the incoming set minus kill.
  • Stop when nothing changes, then read the incoming set at each use to get its use-def chain.
  • For memory, partition locations using alias analysis first; a store to an unknown location kills every partition it may touch.

How it breaks

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

  • kill is computed only over definitions in the same block. Stale definitions survive across blocks, constant propagation substitutes a value that was overwritten on the path taken, and the program computes with an old number.
  • The meet is intersection instead of union. Definitions that reach on only one path disappear from the set, a use appears to have a single reaching definition when it has two, and the substitution is wrong on one branch.
  • A call is treated as writing nothing. Definitions the callee invalidated remain in the set, and an optimization built on them produces a value that is correct until the callee actually writes.
  • The analysis result is cached across a transformation that changed the CFG. The chains describe a graph that no longer exists, and the next pass acts on them.
  • An engineer reads a "variable may be used uninitialised" warning and dismisses it because they can see the initialisation. The analysis is path-insensitive: it is reporting that some path in its model lacks the definition, and the path may well be infeasible — which is a precision limit, not a false alarm to be ignored on principle.

When it helps

  • Any non-SSA optimizer, where it is the foundation for constant propagation, copy propagation and dead store elimination.
  • Linters and static analysers, where "which assignment could this have come from" is directly the user-facing question — uninitialised reads, taint tracking, unused assignments.
  • Reasoning about memory even in an SSA compiler, where the register half is free and the memory half still needs the classical analysis.

When it hurts

  • In an SSA middle-end for register values, where it recomputes information the representation already carries.
  • On code dominated by calls and pointers, where the conservative kill makes the sets so large that nothing can be concluded.
  • On large functions, where the set at every program point is a bit-vector over every definition in the function, and the memory is genuinely significant.

What it costs

Every one of these is paid by something.

  • Definition-site sets buy the ability to answer the question for any variable at any point; they pay memory proportional to program points times definitions, which is the largest of the classical bit-vector analyses on real code.
  • Union at merges buys soundness; it pays precision, because two definitions on mutually exclusive paths both appear and every consumer must be true of both.
  • Replacing the analysis with SSA buys permanently maintained use-def information; it pays construction and destruction, and it only covers values that could be promoted out of memory.
  • Conservative treatment of calls buys correctness without interprocedural analysis; it pays nearly all the precision in call-heavy code, which is a large part of why [[inlining]] helps unrelated optimizations so much.

What else you could do

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

  • Convert to SSA and read the answer off the operands. This is what every optimizing compiler built since the 1990s does for register values, and the trade is construction cost against per-pass analysis cost.
  • Use-def chains computed and maintained explicitly over non-SSA IR. Same information, and the maintenance across rewrites is the part that goes wrong — which is exactly what SSA makes structural.
  • Memory SSA, which extends the SSA idea to loads and stores by giving memory a version at each store and phis where memory states merge. It gives the memory half of the problem the same treatment, and its precision is still bounded by alias analysis.
  • Demand-driven backward slicing from a single use, when only a few queries are needed. Much cheaper for one question, much 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.

  • gcc -fdump-tree-ssa shows the SSA versions that replace this analysis — reading a version number back to its definition is the same information as a use-def chain.
  • opt -passes='print<memoryssa>' -disable-output t.ll prints LLVM's MemorySSA, which is reaching definitions for memory in SSA clothing.
  • Any linter's "used before assignment" or "value assigned but never used" diagnostic is this analysis surfacing — pylint, clang -Wuninitialized and go vet all report from it.
  • Our data-flow stepper runs reaching definitions over an AtlasLang CFG round by round, next to the SSA form of the same function so the phi and the set can be compared directly.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "Reaching definitions tells you which assignment actually ran." It tells you which ones *could* have. Deciding which one did is a run-time question.
  • "If the set has one element, the value is that definition's value." Only if the definition's own value has not since changed — which is guaranteed in SSA and needs proving otherwise.
  • "SSA makes reaching definitions unnecessary." For register values, yes. For memory it is as necessary as ever, and that is where the hard optimizations are.
  • "An empty reaching set means dead code." It means the variable has no definition reaching that use — an uninitialised read, which is a very different diagnosis.

Misconceptions

The claim, and what is actually true.

Reaching definitions and liveness are the same analysis in different directions.
They are the same *shape* — forward and backward may-analyses with union — but they track different objects and answer opposite questions. One is about origins, the other about futures.
SSA eliminated the need for this analysis.
It eliminated it for values that could be promoted to registers. Memory still needs it, and memory is where the difficult optimizations live.
A large reaching set means the code is badly written.
It usually means the analysis is being conservative about calls or pointers. The set is a property of what the compiler can prove, not of the program's quality.

Go deeper

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

overview

Reaching definitions computes, at each point in a program, which assignments could have produced the current value of each variable. It runs forwards, and at a merge it takes the union, because a definition that arrives on any path is a possibility. It is the foundation for constant propagation and copy propagation in a compiler that does not use SSA.

practical

You will most often meet this analysis through its diagnostics rather than its optimizations: "used before assignment", "value never read", and every taint-tracking report. When one of those seems wrong, remember it is path-insensitive — it is telling you that a path *in its model* reaches the use without the definition, and that path may be infeasible for reasons the analysis cannot see. The fix is usually to make the initialisation unconditional rather than to argue with the tool.

advanced

The relationship with SSA is worth stating precisely, because it is the clearest example in the domain of a representation replacing an analysis. SSA construction computes exactly the same information — a phi is placed at precisely those points where a use would have had a multi-element reaching set — and then stores it in the operand names rather than in a side table. The result is not merely faster to query; it is *self-maintaining*, because a transformation that rewrites an operand rewrites the fact. Every classical analysis in this module has been examined for the same treatment, with mixed results: constant propagation transfers beautifully (SCCP), liveness does not transfer at all because it is about program points rather than values, and memory needed a whole parallel construction — MemorySSA — to get the same benefit. The pattern to take away is that a representation can absorb an analysis when the facts attach to values, and cannot when they attach to places.

How much this depends on

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

typicalMainstream compilers do not run this analysis over register values, because SSA already carries the answer. They do run its memory equivalent, and the precision of that version is set almost entirely by the alias analysis underneath it rather than by the data-flow solver.
simplifiedThe gen/kill presentation assumes each definition writes exactly one variable and that variables do not alias. Real IRs have instructions writing several places, calls writing unknown memory, and pointers that may target anything, and each of those complicates kill far more than it complicates gen.
implementationAtlasLang never runs reaching definitions in its optimizer: toSSA runs first and the information is in the operands, so our pass list has no such pass. The data-flow stepper computes it over the pre-SSA IR specifically so the two forms can be compared.

If you were asked this in an interview

  • Define reaching definitions and give its four framework slots.
  • Why does a definition get killed by a later assignment in a different block?
  • How does SSA change this analysis, and where does it fail to help?
  • A linter says a variable may be used uninitialised, but you can see it is always assigned. What is going on?

Connections

DSAdirected-graphdfshash-table
Domains that do not exist yet
  • Testing & Reliability Engineering — Why a static warning with a false positive rate is still worth acting on
    This analysis is the engine behind "may be used uninitialised" style diagnostics, and its path insensitivity is the structural reason those warnings sometimes fire on correct code. How to triage and budget for such warnings is a process question owned there.