Reaching definition
Encyclopedia
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
Data-flow analysis
Data-flow analysis is a technique for gathering information about the possible set of values calculated at various points in a computer program. A program's control flow graph is used to determine those parts of a program to which a particular value assigned to a variable might propagate. The...

 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 in reaching definitions are:


In other words, the set of reaching definitions going into are all of the reaching definitions from 's predecessors, . consists of all of the basic blocks that come before in the control flow graph
Control flow graph
A control flow graph in computer science is a representation, using graph notation, of all paths that might be traversed through a program during its execution.- Overview :...

. The reaching definitions coming out of are all reaching definitions of its predecessors minus those reaching definitions whose variable is killed by plus any new definitions generated within .

For a generic instruction, we define the and sets as follows:


where is the set of all definitions that assign to the variable . Here is a unique label attached to the assigning instruction; thus, the domain of values in reaching definitions are these instruction labels.
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK