Reaching definition¶
Track which variable assignments may flow to a program point along control-flow paths without an intervening assignment to the same variable.
Core Idea¶
A definition of variable \(v\) reaches a program point when at least one control-flow path leads from that assignment to the point without another assignment to \(v\) intervening. Reaching-definitions analysis computes, for each basic block, a set of such definition labels. It is a forward may-analysis: predecessor information combines by union, a block kills older definitions of assigned variables, and generated definitions enter the outgoing set.
For block \(B\), the standard equations are \(\mathrm{IN}[B]=\bigcup_{P\in pred(B)}\mathrm{OUT}[P]\) and \(\mathrm{OUT}[B]=\mathrm{GEN}[B]\cup(\mathrm{IN}[B]\setminus\mathrm{KILL}[B])\). A worklist propagates set changes along control-flow edges until a fixed point is reached.
Scope of Application¶
The abstraction is literal wherever practitioners can identify the same constitutive roles, apply the same boundary tests, and obtain the same kind of output. The following habitats are uses of Reaching definition itself, not metaphors based only on resemblance.
- Use–definition chains. Linking each use to assignments that may supply its value.
- Compiler education. Illustrating monotone data-flow equations and worklists.
- Constant propagation support. Identifying candidate assignments feeding a use.
- Dead-store analysis. Contributing evidence about overwritten definitions.
- SSA construction comparison. Relating merge points to alternative reaching values.
- Static-analysis engineering. Testing precision under alias and interprocedural abstractions.
Clarity¶
A clear account of Reaching definition must preserve the recognition invariant stated in the Core Idea rather than rely on the title alone. Define the control-flow graph, entry boundary, and definition granularity. State explicitly that the result is a may fact with union at joins. Specify GEN and KILL treatment for multiple assignments in one block. Declare alias, memory, exception, and call assumptions. These declarations are not editorial extras: each changes what observations count, which transformations are licensed, and what conclusion can be drawn.
Manages Complexity¶
Reaching definition manages complexity by replacing a diffuse field of observations or possible operations with a bounded role structure: definition labels supplies assignments receive unique identities.; control-flow graph supplies basic blocks and directed edges represent possible execution paths.; gen set supplies definitions surviving at the end of a block are produced locally.; kill set supplies assignments remove competing definitions of the same abstract location.; union join supplies any predecessor path can contribute a reaching definition..
Abstract Reasoning¶
- Partition the program into basic blocks and label definitions. 2. Construct sound control-flow predecessor and successor edges. 3. Compute block GEN and KILL sets under the location abstraction. 4. Initialize boundary and internal sets according to a forward may-analysis. 5. Apply transfer and union equations on a worklist. 6. Continue until no output set changes. 7. Validate uses against paths and inspect precision losses at joins.
Knowledge Transfer¶
The strict upward abstraction is Flow. Reaching Definition instantiates Flow because assignment facts propagate along control-flow edges subject to local generation and removal. Within forward may dataflow analysis, the full mechanism transfers literally when the same roles and boundary tests recur. Beyond that domain, only the parent-level skeleton should travel. Reusing the label Reaching definition after removing its constitutive vocabulary would hide a change of mechanism behind an analogy. The honest transfer rule is therefore two-stage: recognize the domain-specific pattern first, then lift only the parent relation that remains invariant under a substrate change.
Relationships to Other Abstractions¶
Current abstraction Reaching definition Domain-specific
Parents (1) — more general patterns this builds on
-
Reaching definition is a kind of Flow Prime
Reaching Definition instantiates Flow because assignment facts propagate along control-flow edges subject to local generation and removal.
Hierarchy path (1) — routes to 1 parentless root
- Reaching definition → Flow
Neighborhood in Abstraction Space¶
Reaching definition sits in a sparse region of the domain-specific corpus (91st percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (1565 abstractions)
Nearest neighbors
- Symbolic Execution — 0.79
- Activity Diagram — 0.79
- Zémor's Decoding Algorithm — 0.78
- Blum–Shub–Smale Machine — 0.78
- Combinatory Logic — 0.78
Computed from structural-signature embeddings · 2026-09-08