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 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