Global Optimization by Suppression of Partial Redundancies

The elimination of redundant computations and the moving of invariant
computations out of loops are often done separately, with invariants 
moved outward loop by loop.  We propose to do both at once and
to move each expression directly to the entrance of the outermost
loop in which it is invariant.  This is done by solving a more
general problem, i.e. the elimination of computations performed
twice on a given execution path.  Such computations are termed partially
redundant.  Moreover, the algorithm does not require any graphical
information or restrictions on the shape of the program graph.
Testing this algorithm has shown that its execution cost is nearly
linear with the size of the program, and that it leads
to a smaller optimizer that requires less execution time.

CACM February, 1979

Morel, E.
Renvoise, C.

Optimizer, optimization, compiler, compilation,
redundancy elimination, invariant
 computation elimination, partial redundancy,
data flow analysis, Boolean systems

4.12 5.21 5.24

CA790204 DH April 10, 1979  4:19 PM

3125	5	3125
3125	5	3125
3125	5	3125