## Necessary Assumptions About Transfer Functions

**Introduction**: In order for region-based analysis to work, we need to make certain assumptions about properties of the set of transfer functions in the framework. Specifically, we need three primitive operations on transfer functions: composition, meet and closure; only the first is required for data-flow frameworks that use the iterative algorithm.

**Composition: **The transfer function of a sequence of nodes can be derived by composing thefunctions representing the individual nodes. Let /i and f2 be transfer functionsof nodes n\ and n2. The effect of executing n\ followed by n2 is representedby f2 o /]_. Function composition has been discussed in Section 9.2.2, and anexample using reaching definitions was shown in Section 9.2.4. To review, letgerii and kilk be the gen and kill sets for Then:

Thus, the gen and kill sets for f2°fi aregen2 U (gen\—kill2) and kill\ U kill2, respectively. The same idea works for any transfer function of the gen-kill form. Other transfer functions may also be closed, but we have to consider each case separately.

**Meet:** Here, the transfer functions themselves are values of a semilattice with a meet operator A/. The meet of two transfer functions /i and f2, /i A/ f2, is defined by (/i A/ fi){x) = fi(x) A f2(x), where A is the meet operator for data-flow values. The meet operator on transfer functions is used to combine the effect of alternative paths of execution with the same end points. Where it is not ambiguous, from now on, we shall refer to the meet operator of transfer functions also as A. For the reaching-definitions framework, we have

That is, the gen and kill sets for /i A f2 are gen\ U gen2 and killi n kill2, respectively. Again, the same argument applies to any set of gen-kill transferfunctions.

**Closure**: If / represents the transfer function of a cycle, then fn represents the effect of going around the cycle n times. In the case where the number of iterations is not known, we have to assume that the loop may be executed 0 or more times. We represent the transfer function of such a loop by /*, the closure of /, which is defined by

Note that /° must be the identity transfer function, since it represents the effect of going zero times around the loop, i.e., starting at the entry and not moving. If we let / represent the identity transfer function, then we can write

Suppose the transfer function / in a reaching definitions framework has a gen set and a kill set. Then,

and so on: any fn(x) is gen U (x — kill). That is, going around a loop doesn't affect the transfer function, if it is of the gen-kill form. Thus,

That is, the gen and kill sets for /* are gen and 0, respectively. Intuitively, since we might not go around a ioop at all, anything in x will reach the entry to the loop. In all subsequent iterations, the reaching definitions include those in the gen set.