- 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 adata-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. Thedata-flow confluence operator used is set union, and the analysis is forward flow. Reaching definitions are used to computeuse-def chain s anddef-use chain s.The data-flow equations used for a given basic block $S$ in reaching definitions are:

* $\{\; m\; REACH\}\_\{\; m\; in\}\; [S]\; =\; igcup\_\{p\; in\; pred\; [S]\; \}\; \{\; m\; REACH\}\_\{\; m\; out\}\; [p]$

* $\{\; 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

*Wikimedia Foundation.
2010.*