Generalized common subexpressions in very high level languages

ABSTRACT

We propose a new optimization technique applicable to set-oriented languages, which we shall call general common subexpression elimination. It involves the computation of the IAVAIL(n) function for all nodes n in a flow graph, where IAVAIL(n) is the set of expressions such that along every path leading to n, there will be found a computation of the expression followed by only incidental assignments (i.e. A = A ∪ {x} or A = A - {x}) to its operands and that the number of such assignments is bounded, independent of the path taken. We shall try to justify our definitions and demonstrate the usefulness of this technique by several examples. We shall show that this optimization problem does not fit into the semilattice-theoretic model for global program optimization [Ki, KU, GW], and that the standard iterative algorithm for such problems does not work in this case. We then give several theorems which allow the problem to be solved for reducible flow graphs. The formulae given in the theorems are in such a form that an efficient algorithm can be found by adapting an algorithm given in [U]. The resulting algorithm takes 0(e log e) steps of an extended type, where bit vector operations are regarded as one step, and e is the number of edges of the flow graph. It takes 0(n log n) extended steps for a program flow graph of n nodes.

REFERENCES

• 1: {A1} F. E. Allen, "Program Optimization," in Annual Review in Automatic Programming, Vol. 5, Pergamon, 1969, pp. 239-307.
• 2: {A2} F. E. Allen and J. Cocke, "A Catalogue of Optimizing transformations," in Design and Optimization of Compilers (R. Rustin, ed.), Prentice Hall, 1972, pp. 1-30.
• 3: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 4: Alfred V. Aho , Jeffrey D. Ullman, Theory of Parsing, Translation and Compiling, Prentice Hall Professional Technical Reference, 1973
• 5: John Cocke, Global common subexpression elimination, ACM SIGPLAN Notices, v.5 n.7, p.20-24, July 1970
• 6: John Cocke, Programming languages and their compilers: Preliminary notes, Courant Institute of Mathematical Sciences, New York University, 1969
• 7: Jay Earley, High level operations in automatic programming, Proceedings of the ACM SIGPLAN symposium on Very high level languages, p.34-42, March 28-29, 1974, Santa Monica, California, United States
• 8: Amelia Fong , John Kam , Jeffrey Ullman, Application of lattice algebra to loop optimization, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.1-9, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512977]
• 9: Amelia C. Fong , Jeffrey D. Ullman, Induction variables in very high level languages, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.104-112, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811544]
• 10: Susan L. Graham , Mark Wegman, A fast and usually linear algorithm for global flow analysis, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.22-34, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512979]
• 11: {HU} J. E. Hopcroft and J. D. Ullman, "An n log n Algorithm for Reduction of Flow Graphs," 6th Annl. Princeton Conference on Information Sciences and Systems, 1972.
• 12: 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]
• 13: {KU} J. B. Kam and J. D. Ullman, "Global Optimization Problems and Iterative Algorithms," JACM, Jan., 1976.
• 14: {R} B. K. Rosen, Private Communication.
• 15: Robert Tarjan, Testing flow graph reducibility, Proceedings of the fifth annual ACM symposium on Theory of computing, p.96-107, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804040]
• 16: {U} J. D. Ullman, "Fast Algorithms for the Elimination of Common Subexpressions," Acta Informatica, 2:4, 1973, pp. 191-213.