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