## Transfer Functions

**Introduction**: The family of transfer functions F: V -» V in a data-flow framework has the following properties:

1. F has an identity function i", such that I(x) = x for all x in V.

2. F is closed under composition; that is, for any two functions / and g in F, the function h defined by h(x) = g(f(x)) is in F.

**Example:** In reaching definitions, F has the identity, the function where gen and kill are both the empty set. Closure under composition was actually shown in Section 9.2.4; we repeat the argument succinctly here. Suppose we have two functions

fi(x) =GiU(x- K±) and f2(x) = G2U{x~ K2).

Then

h(hix)) = G2 U ((Gi U(x- Ki)) - K2).

The right side of the above is algebraically equivalent to

(G2 U (G1 - K2)) U(x- (# ! U K2)).

If we let K = K\ U K2 and G = G2 U (Gi - #2)5 then we have shown that the composition of /i and f2, which is f(x) = G U (x — K), is of the form that makes it a member of F. If we consider available expressions, the same arguments used for reaching definitions also show that F has an identity and is closed under composition.

**Monotone Frameworks: **To make an iterative algorithm for data-flow analysis work, we need for thedata-flow framework to satisfy one more condition. We say that a frameworkis monotone if when we apply any transfer function / in F to two members ofV, the first being no greater than the second, then the first result is no greaterthan the second result.

Formally, a data-flow framework (D,F, V, A) is monotone if

For all x and y in V and / in F, x < y implies f(x) < f(y). (9.22)

Equivalently, monotonicity can be defined as

For all x and y in V and / in F, f{x Ay) < f(x) A f(y). (9.23)

Equation (9.23) says that if we take the meet of two values and then apply /, the result is never greater than what is obtained by applying / to the values individually first and then "meeting" the results. Because the two definitions of monotonicity seem so different, they are both useful. We shall find one or the other more useful under different circumstances. Later, we sketch a proof to show that they are indeed equivalent.

We shall first assume (9.22) and show that (9.23) holds. Since x A y is the greatest lower bound of x and y, we know that

x Ay < x and x f\y <y.

Thus, by (9.22),

f(x A y) < f(x) and f{x Ay) < f{y).

Since f(x) A / ( y ) is the greatest lower bound of f(x) and f(y), we have (9.23).

Conversely, let us assume (9.23) and prove (9.22). We suppose x < y and use (9.23) to conclude f(x) < f(y), thus proving (9.22). Equation ( 9 . 2 3 ) tells us

f(xAy)<f(x)Af(y).

But since x < y is assumed, x A y — x, by definition. Thus (9.23) says

f(x) <f(x)Af(y).

Since f{x)Af(y) is the gib of f(x) and f(y), we know f(x) A f(y) < f(y). Thus

f(x)<f(x)Af(y)<f(y)

and (9.23) implies (9.22).

**Distributive Frameworks: **Often, a framework obeys a condition stronger than (9.23), which we call thedistributivity condition,

f(xAy) = f(x)Af(y)

for all x and y in V and / in F. Certainly, if a = b, then a A b = a by idempotence, so a < b. Thus, distributivity implies monotonicity, although the converse is not true.

**Example:** Let y and z be sets of definitions in the reaching-definitions framework. Let / be a function defined by f(x) = G U (x — K) for some sets of definitions G and K. We can verify that the reaching-definitions framework satisfies the distributivity condition, by checking that

G U ((y U z) - K) = (G U (y - K)) U (G U (z - K)).

While the equation above may appear formidable, consider first those definitions in G. These definitions are surely in the sets defined by both the left and right sides. Thus, we have only to consider definitions that are not in G. In that case, we can eliminate G everywhere, and verify the equality

(yUz)-K = (y-K)U(z-K).

The latter equality is easily checked using a Venn diagram.