Summary
We give two algorithms for computing the set of available expressions at entrance to the nodes of a flow graph. The first takes O(mn) isteps on a program flow graph (one in which no node has more than two successors), where n is the number of nodes and m the number of expressions which are ever computed. A modified version of this algorithm requires O(n 2) steps of an extended type, where bit vector operations are regarded as one step. We present another algorithm which works only for reducible flow graphs. It requires O(n log n) extended steps.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aho, A. V., Ullman, J. D.: The theory of parsing, translation, and compiling, Vol. II — Compiling. Englewood Cliffs (N.J.): Prentice Hall 1973
Allen, F. E.: Program optimization. Annl. Rev. Automatic Prog. 5, 239–307 (1969)
Allen, F. E.: Control flow analysis. SIGPLAN Notices 5, 1–19 (1970)
Allen, F. E.: A Basis for Program Optimization, Proc. IFIP Conf. 71, Amsterdam: North Holland 1972, pp. 385–390.
Cocke, J., Schwartz, J. T.: Programming languages and their compilers. New York (N.Y.): Courant Inst. of Mathematical Sciences 1970
Schaefer, M.: A mathematical theory of global flow analysis. System Development Corp., Santa Monica (Cal.) 1971. To be published by Prentice-Hall 1973
Kennedy, K.: A global flow analysis algorithm. Internatl. J. Computer Math. 3, 5–15 (1971)
Cook, S. A.: Linear time simulation of two-way pushdown automata. Proc. IFIP Conf. 71, Amsterdam: North-Holland 1971, pp. 75–80
Cocke, J.: Global common subexpression elimination. SIGPLAN Notices 5, 20–24 (1970)
Allen, F. E., Cocke, J.: Graph theoretic constructs for program control flow analysis. IBM Research Lab., Yorktown Hts. (N.Y.), Report RC-3923, July 1972
Hecht, M. S., Ullman, J. D.: Analysis of a simple algorithm for global data flow problems, to appear in Proc. of ACM Symposium on Principles of Programming Languages, Oct., 1973
Cocke, J., Miller, R. E.: Some analysis techniques for optimizing computer programs. Proc. 2nd Intl. Conf. on System Sciences, U. of Hawaii, Honolulu, Hawaii, 1969
Hecht, M. S., Ullman, J. D.: Flow graph reducibility. SIAM J. Computing 1, 188–202 (1972)
Hopcroft, J. E., Ullman, J. D.: An n log n algorithm for reduction of flow graphs. 6th Annl. Princeton Conf. on Inf. Sc. and Systems, March 1972, pp. 119–122
Tarjan, R. E.: Testing flow graph reductability. Proc. 5th ACM Symposium on Theory of Computing, pp. 96–107, May 1973
Engeler, E.: Structure and meaning of elementary programs. In: E. Engeler (ed.): Symposium on Semantics of Algorithmic Languages, Springer Lecture Notes 188. Berlin: Springer 1971, pp. 89–101
Kildall, G. A.: Global expression optimization during compilations. Univ. of Washington, Computer Science Dept., TR 12/06-02, June 1972. To appear in ACM Symposium on Principles of Programming languages, Oct. 1973
Author information
Authors and Affiliations
Additional information
Work supported by NSF grant GJ-1052. Portions of this paper appeared in the Proceedings of the IEEE 13th Annual Symposium on Switching and Automata Theory.
Rights and permissions
About this article
Cite this article
Ullman, J.D. Fast algorithms for the elimination of common subexpressions. Acta Informatica 2, 191–213 (1973). https://doi.org/10.1007/BF00289078
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF00289078