In compiler theory, a reaching definition is a definition of a variable that may reach a particular point in a program without another definition of the same variable occurring along the intervening control-flow path. 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 analysis is a data-flow analysis that statically determines which definitions may reach a given point in the code. Because of its simplicity, it is often used as a canonical example of data-flow analysis in compiler textbooks. The data-flow confluence operator used is set union, and the analysis is a forward data-flow analysis. Reaching definitions can be used to compute use-def chains.

The data-flow equations used for a given basic block in reaching definitions are:

.

sets as follows:

• , a set containing the definition generated by the instruction

• killed by the instruction

is a unique label attached to the assigning instruction; thus, the domain of values in reaching definitions consists of these instruction labels.

Worklist algorithm

Reaching definitions are usually calculated using an iterative worklist algorithm.

Input: control-flow graph CFG = (Nodes, Edges, Entry, Exit)

See also

• Dead-code elimination

• Loop-invariant code motion

• Reachable uses

• Static single assignment form

References

Further reading