Previous    Next

## TRANSFORMATIONS USING DATAFLOW ANALYSIS

Using the results of dataflow analysis, the optimizing compiler can improve the program in several ways.

### COMMON-SUBEXPRESSION ELIMINATION

Given a flow-graph statement s : t ← xy, where the expression xy is available at s, the computation within s can be eliminated. Algorithm. Compute reaching expressions, that is, find statements of the form n : v ← xy, such that the path from n to s does not compute xy or define x or y. Choose a new temporary w, and for such n, rewrite as n : wxy n′ : vw Finally, modify statement s to be s : tw

We will rely on copy propagation to remove some or all of the extra assignment quadruples.

### CONSTANT PROPAGATION

Suppose we have a statement d : t ← c, where c is a constant, and another statement n that uses t, such as n : y ← tx. We know that t is constant in n if d reaches n, and no other definitions of t reach n.

In this case, we can rewrite n as y ← cx.

### COPY PROPAGATION

This is like constant propagation, but instead of a constant c we have a variable z. Suppose we have a statement d : t ← z. and another statement n that uses t, suchas n : y ← tx. If d reaches n, and no other definition of t reaches n, and there is no definition of z on any path from d to n (including a path that goes through n one or more times), then we can rewrite n as n : y ← zx. A good graph-coloring register allocator will do coalescing (see ), which is a form of copy propagation. It detects any intervening definitions of z in constructing the interference graph - an assignment to z while d is live makes an interference edge (z, d), rendering d and z uncoalesceable. If we do copy propagation before register allocation, then we may increase the number of spills. Thus, if our only reason to do copy propagation were to delete redundant MOVE instructions, we should wait until register allocation. However, copy propagation at the quadruple stage may enable the recognition of other optimizations such as common-subexpression elimination. For example, in the program ay + z uy cu + z

the two +-expressions are not recognized as common subexpressions until after the copy propagation of u ← y is performed.