Global optimization by suppression of partial redundancies

ABSTRACT

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.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Theory of Parsing, Translation and Compiling, Prentice Hall Professional Technical Reference, 1973
• 2: Frances E. Allen, Control flow analysis, Proceedings of a symposium on Compiler optimization, p.1-19, July 27-28, 1970, Urbana-Champaign, Illinois
• 3: Allen, F. E. and Cocke, J. A catalogue of optimizing techniques. In Design and Optimization of Compilers, R. Rustin, Ed., Prentice- Hall, Englewood Cliffs, N.J., 1971, pp. 1-30.
• 4: John Cocke, Global common subexpression elimination, Proceedings of a symposium on Compiler optimization, p.20-24, July 27-28, 1970, Urbana-Champaign, Illinois
• 5: Goldtmrg, P. A comparison of certain optimization techniques. In Design and Optimization of Compilers, R. Rustin, Ed., Prentice-HaU, Englewood Cliffs, N.J., 1971, pp. 31-50.
• 6: Hecht, M. S., and UUman, J. D. A simple algorithm for global data flow analysis problems. SIAM J. Comptng. 4 (1975), 519-532.
• 7: Ichbiah, J. D., Rissen, J. P., Heliard, J. C., and Cousot, P. The system implementation language LIS. Ref. Manual 4549 E/EN, CII-HB, Louveciennes, France, Dec. 1974.
• 8: Kennedy, K. A comparison of two algorithms for global data flow analysis. SIAM J. Comptng. 5 (1976), 158-180.
• 9: Gary A. Kildall, A unified approach to global program optimization, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.194-206, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512945]
• 10: Knuth, D. E. An empirical study of FORTRAN programs. Software-Practice and Experience (April 1971), pp. 105-134.
• 11: Edward S. Lowry , C. W. Medlock, Object code optimization, Communications of the ACM, v.12 n.1, p.13-22, Jan. 1969 [doi>10.1145/362835.362838]
• 12: Morel, E., and Renvoise, C. Etude et r6alisation d'un optimiseur global. Ph.D. Th., Universit6 de Paris VI, Juin 1974 (English version available).
• 13: Morel, E., and Renvoise, C. A global algorithm for the elimination of partial redundancies. 2nd Int. Symp. on Programming, Paris, April 13-15, 1976, pp. 147-159 (edited by Dunod, Paris).
• 14: Marvin Schaefer, A mathematical theory of global program optimization (Prentice-Hall series in automatic computation), Prentice-Hall, Inc., Upper Saddle River, NJ, 1973

INDEX TERMS

Keywords:
Boolean systems, compilation, compiler, data flow analysis, invariant computation elimination, optimization, optimizer, partial redundancy, redundancy elimination