9.2.2 Transfer Equation for Reaching Definitions

For all forward flow problems, the information which comes out of the block is a function of the information which goes into the block. We write this symbolically as:

Out (B) = f_B(In (B))

For reaching definitions, we define function f in terms of definitions which are generated and killed in the block B. We thus introduce two new variables:Kill(B) and Gen(B).

Definition def₁ kills definition def₁ and def₂ define the same variable:

Kill (B) = The set of definitions in the other blocks of the program that are killed by some definition in B.

Block B generates definition def if def is in B and is the last definition of def's variable within B.

Gen(B) = set of definitions generated by B

The transfer equation is:

Out (B) = (In(b) - Kill(B)) Gen (B)

Confluence Rule for Reaching Definitions

A definition def reaches the beginning of a block B if and only if it reaches the end of one of block B's predecessors.

In(B) = Out(P)
_{P Pred(B)}