In
compiler theory
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that ...
, a reaching definition for a given instruction is an earlier instruction whose target variable can reach (be assigned to) the given one without an intervening assignment. For example, in the following code:
d1 : y := 3
d2 : x := y
d1
is a reaching definition for
d2
. In the following, example, however:
d1 : y := 3
d2 : y := 4
d3 : x := y
d1
is no longer a reaching definition for
d3
, because
d2
kills its reach: the value defined in
d1
is no longer available and cannot reach
d3
.
As analysis
The similarly named reaching definitions is a
data-flow analysis
In computing, dataflow is a broad concept, which has various meanings depending on the application and context. In the context of software architecture, data flow relates to stream processing or reactive programming.
Software architecture
Dataf ...
which statically determines which definitions may reach a given point in the code. Because of its simplicity, it is often used as the canonical example of a data-flow analysis in textbooks. The
data-flow confluence operator
In computing, dataflow is a broad concept, which has various meanings depending on the application and context. In the context of software architecture, data flow relates to stream processing or reactive programming.
Software architecture
Dataf ...
used is set union, and the analysis is forward flow. Reaching definitions are used to compute
use-def chain
Within computer science, a Use-Definition Chain (''UD Chain'') is a data structure that consists of a use, U, of a variable, and all the definitions, D, of that variable that can reach that use without any other intervening definitions. A UD Chain ...
s.
The data-flow equations used for a given basic block
in reaching definitions are:
*