Reaching definition¶

Track which variable assignments may flow to a program point along control-flow paths without an intervening assignment to the same variable.

Version: v1 · 2026-08-30 · History
Domain-specific #: 2629
Origin domain: compiler theory
Subdomain: forward may dataflow analysis
Aliases: Reaching definitions analysis, Reaching assignment

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.^[1]

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. Finite definition labels and monotone transfer functions guarantee termination. The result supports use–definition chains, constant propagation, dead-store reasoning, and other analyses, but path correlation is lost at union joins.^[2]

Reaching means may reach, not must reach. A definition can appear in the set even if another path carries a different assignment. It differs from variable liveness, which asks whether a current value may be used in the future, and from available expressions, which is normally a forward must-analysis using intersection. Aliasing, memory locations, exceptions, and interprocedural calls require a richer abstraction than simple variable names. A source statement and a compiler's intermediate definition units may not coincide.^[3]

Structural Signature¶

Definition labels. Assignments receive unique identities.
Control-flow graph. Basic blocks and directed edges represent possible execution paths.
GEN set. Definitions surviving at the end of a block are produced locally.
KILL set. Assignments remove competing definitions of the same abstract location.
Union join. Any predecessor path can contribute a reaching definition.
Forward transfer. Information moves in execution direction.
Fixed point. Iteration stops when every input and output set is stable.
Abstraction model. Variables, aliases, and calls determine what counts as one definition.

What It Is Not¶

Not liveness analysis. Liveness flows backward from possible future use.
Not available expressions. Availability usually requires truth on every predecessor path.
Not a must-reach fact. Union records existential path possibility.
Not dynamic tracing. Static analysis overapproximates possible executions.
Not source-text proximity. Control-flow paths and kills, not line distance, decide reachability.
Not value equality. Two definitions can compute equal values while remaining distinct labels.

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. A reader should be able to reconstruct the input, the operative rule, the output, and at least one defeater from the account without consulting an implementation or guessing an unstated convention.

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.. The compression is useful because it localizes disagreement. One can ask whether the input was properly formed, whether a constitutive relation held, whether an alternative explanation defeats the inference, or whether the output was overinterpreted. The same compression can mislead when its discarded detail is exactly what the decision requires. A reference-grade use therefore reports both the invariant retained and the information intentionally lost.

Abstract Reasoning¶

Partition the program into basic blocks and label definitions.
Construct sound control-flow predecessor and successor edges.
Compute block GEN and KILL sets under the location abstraction.
Initialize boundary and internal sets according to a forward may-analysis.
Apply transfer and union equations on a worklist.
Continue until no output set changes.
Validate uses against paths and inspect precision losses at joins.
Test the candidate interpretation against the nearest named confusable rather than accepting a shared surface feature.
State the conclusion at the same scope as the source conditions, and retain uncertainty or nonuniqueness where the construct does not remove it.

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.

Examples¶

Canonical¶

One branch assigns \(x:=1\) and another assigns \(x:=2\); both flow to a join that uses \(x\). The reaching set at the use contains both definition labels because each arrives along some path. If the join block first assigns \(x:=3\), that local definition kills both earlier ones before the later use.

Mapped back: input and conventions → constitutive role test → bounded output → explicit interpretation and defeater check.

Applied / In Practice¶

A compiler builds use–definition chains for an optimization. It retains two reaching assignments at a branch merge rather than guessing one. When pointers may alias the same memory, it expands the kill and generation model conservatively; reduced precision is reported as an abstraction consequence rather than a control-flow error.

Mapped back: field observation or problem → candidate recognition → confusable and limit checks → appropriately scoped conclusion.

Structural Tensions¶

T1: May precision versus soundness. Union retains infeasible path combinations. Diagnostic: Compare with path-sensitive analysis before using exclusivity.
T2: Variable names versus memory locations. Aliases can hide intervening writes. Diagnostic: Declare and test the location abstraction.
T3: Block summary versus instruction detail. GEN must exclude local definitions killed later in the block. Diagnostic: Recompute summaries from instruction order.
T4: Intraprocedural clarity versus calls. Unknown callees may define reachable state. Diagnostic: State call summaries and side-effect assumptions.
T5: Termination versus useful precision. Finite sets converge even when results are coarse. Diagnostic: Evaluate optimization opportunities and false possibilities.
T6: Autonomy versus generic flow. Flow transmits entities through a graph; reaching definitions add assignment labels, kill semantics, and a forward may fixed point. Diagnostic: Remove GEN/KILL and test whether only graph reachability remains.

Structural–Framed Character¶

Path existence, kill-free transfer, union joins, and fixed-point equations are structural; variable and alias abstraction are tool-framed. The five framing criteria point in a consistent direction. Evaluative weight is limited to whether the defining conditions are met, not whether the outcome is desirable. Human practice matters to the extent that experts choose conventions, instruments, or reporting thresholds, but those choices do not make every verdict arbitrary. Institutional history explains the name and standard use; it does not replace the recognition rule. The operative vocabulary travels within the home field and closely adjacent subfields, while transfer farther away requires translation to the parent prime. Thus recognition remains disciplined even where interpretation is defeasible.

Structural Core vs. Domain Accent¶

What is skeletal. Reaching Definition instantiates Flow because assignment facts propagate along control-flow edges subject to local generation and removal. This is the part that can be expressed without the candidate's specialist nouns.

What is domain-bound. The domain accent includes definitions, variables, basic blocks, control-flow graphs, GEN/KILL sets, worklists, monotone frameworks, and use–definition chains. Remove those elements and the result is no longer Reaching definition; it is only the parent relation or a loose analogy.

Why this does not clear the prime bar. The name does not recur with unchanged diagnostics across three independent domains. What transfers is already represented by prime:flow. The candidate remains autonomous because its in-domain recognition rule, failure modes, and consequences are stable, but its vocabulary and interventions do not float free of the home substrate.

Reaching Definition instantiates Flow because assignment facts propagate along control-flow edges subject to local generation and removal.

The prospective workspace queue contains one strict upward edge to prime:flow. No live DAG mutation is authorized.

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 (91^st percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

Live variable analysis. Flows backward from potential future use.
Available expressions. Uses intersection to require availability on all paths.
Dominance. A graph property requiring every entry path to pass through a node.
Definite assignment. A must property used to ensure initialization.
Dynamic data flow. Records one observed execution rather than possible paths.
SSA form. A representation discipline that gives definitions unique names and merge nodes.

References¶

[1] Kildall, G. A. (1973). ‘A Unified Approach to Global Program Optimization.’ Proceedings of the 1^st ACM Symposium on Principles of Programming Languages, 194–206. https://doi.org/10.1145/512927.512945 registry ↩

[2] Aho, A. V., Lam, M. S., Sethi, R., and Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools, 2^nd ed. Addison-Wesley. ISBN 978-0-321-48681-3. registry ↩

[3] Nielson, F., Nielson, H. R., and Hankin, C. (1999). Principles of Program Analysis. Springer. https://doi.org/10.1007/978-3-662-03811-6 registry ↩