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 ← x ⊕ y, where the expression x ⊕ y is available at s, the computation within s can be eliminated. Algorithm. Compute reaching expressions, that is, find statements of the form n : v ← x ⊕ y, such that the path from n to s does not compute x ⊕ y or define x or y. Choose a new temporary w, and for such n, rewrite as n : w ← x ⊕ y n′ : v ← w Finally, modify statement s to be s : t ← w

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 ← t ⊕ x. 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 ← c ⊕ x.

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 ← t ⊕ x. 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 ← z ⊕ x. 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 a ← y + z u ← y c ← u + z

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

DEAD-CODE ELIMINATION

If there is a quadruple s : a ← b ⊕ c or s : a ← M[x], such that a is not live-out of s, then the quadruple can be deleted. Some instructions have implicit side effects. For example, if the computer is configured to raise an exception on an arithmetic overflow or divide by zero, then deletion of an exception-causing instruction will change the result of the computation.

The optimizer should never make a change that changes program behavior, even if the change seems benign (such as the removal of a run-time "error"). The problem with such optimizations is that the programmer cannot predict the behavior of the program - and a program debugged with the optimizer enabled may fail with the optimizer disabled.