Reaching definition

In compiler theory, a reaching definition for a given instruction is another instruction, the target variable of which may reach the given instruction without an intervening assignment. For example, in the following code:

d1 : y := 3 d2 : x := y

d1 is a reaching definition at d2. In the following, example, however:

d1 : y := 3 d2 : y := 4 d3 : x := y

d1 is no longer a reaching definition at d3, because d2 kills its reach.

As analysis

The similarly-named reaching definitions is a data-flow analysis 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 used is set union, and the analysis is forward flow. Reaching definitions are used to compute use-def chains and def-use chains.

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

*
* $\{\; m\; REACH\}\_\{\; m\; out\}\; [S]\; =\; \{\; m\; GEN\}\; [S]\; cup\; (\{\; m\; REACH\}\_\{\; m\; in\}\; [S]\; -\; \{\; m\; KILL\}\; [S]\; )$

In other words, the set of reaching definitions going into $S$ are all of the reaching definitions from $S$'s predecessors, $pred\; [S]$. $pred\; [S]$ consists of all of the basic blocks that come before $S$ in the control flow graph. The reaching definitions coming out of $S$ are all reaching definitions of its predecessors minus those reaching definitions whose variable is killed by $S$ plus any new definitions generated within $S$.

For a generic instruction, we define the $\{\; m\; GEN\}$ and $\{\; m\; KILL\}$ sets as follows:

* $\{\; m\; GEN\}\; [d\; :\; y\; leftarrow\; f(x\_1,cdots,x\_n)]\; =\; \{d\}$
* $\{\; m\; KILL\}\; [d\; :\; y\; leftarrow\; f(x\_1,cdots,x\_n)]\; =\; \{\; m\; DEFS\}\; [y]\; -\; \{d\}$

where $\{\; m\; DEFS\}\; [y]$ is the set of all definitions that assign to the variable $y$. Here $d$ is a unique label attached to the assigning instruction; thus, the domain of values in reaching definitions are these instruction labels.

Further reading

*cite book
author=Aho, Alfred V.; Sethi, Ravi; & Ullman, Jeffrey D.
title=
publisher=Addison Wesley
year=1986
id=ISBN 0-201-10088-6
*cite book
author=Appel, Andrew W.
title=Modern Compiler Implementation in ML
publisher=Cambridge University Press
year=1999
id=ISBN 0-521-58274-1
*cite book
author=Cooper, Keith D.; & Torczon, Linda.
title=Engineering a Compiler
publisher=Morgan Kaufmann
year=2005
id=ISBN 1-55860-698-X
*cite book
author=Muchnick, Steven S.
title=Advanced Compiler Design and Implementation
publisher=Morgan Kaufmann
year=1997
id=ISBN 1-55860-320-4