More Web Proxy on the site http://driver.im/

article

Fast algorithms for the elimination of common subexpressions

Author:

J. D. UllmanAuthors Info & Claims

Acta Informatica, Volume 2, Issue 3

Pages 191 - 213

https://doi.org/10.1007/BF00289078

Published: 01 September 1973 Publication History

Abstract

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 ²) 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.

References

[1]

Aho, A. V., Ullman, J. D.: The theory of parsing, translation, and compiling, Vol. II -- Compiling. Englewood Cliffs (N.J.): Prentice Hall 1973

[2]

Allen, F. E.: Program optimization. Annl. Rev. Automatic Prog. 5, 239---307 (1969)

[3]

Allen, F. E.: Control flow analysis. SIGPLAN Notices 5, 1---19 (1970)

Digital Library

[4]

Allen, F. E.: A Basis for Program Optimization, Proc. IFIP Conf. 71, Amsterdam: North Holland 1972, pp. 385---390.

[5]

Cocke, J., Schwartz, J. T.: Programming languages and their compilers. New York (N.Y.): Courant Inst. of Mathematical Sciences 1970

[6]

Schaefer, M.: A mathematical theory of global flow analysis. System Development Corp., Santa Monica (Cal.) 1971. To be published by Prentice-Hall 1973

[7]

Kennedy, K.: A global flow analysis algorithm. Internatl. J. Computer Math. 3, 5---15 (1971)

[8]

Cook, S. A.: Linear time simulation of two-way pushdown automata. Proc. IFIP Conf. 71, Amsterdam: North-Holland 1971, pp. 75---80

[9]

Cocke, J.: Global common subexpression elimination. SIGPLAN Notices 5, 20---24 (1970)

Digital Library

[10]

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

[11]

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

[12]

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

[13]

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

[14]

Tarjan, R. E.: Testing flow graph reductability. Proc. 5th ACM Symposium on Theory of Computing, pp. 96---107, May 1973

[15]

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

[16]

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

Cited By

Zhou AHu YXu XZhang C(2024) ARCTURUS: Full Coverage Binary Similarity Analysis with Reachability-guided EmulationACM Transactions on Software Engineering and Methodology10.1145/364033733:4(1-31)Online publication date: 11-Jan-2024
https://dl.acm.org/doi/10.1145/3640337
Reps TTuretsky EPrabhu P(2017)Newtonian Program Analysis via Tensor ProductACM Transactions on Programming Languages and Systems10.1145/302408439:2(1-72)Online publication date: 21-Mar-2017
https://dl.acm.org/doi/10.1145/3024084
Reps TTuretsky EPrabhu P(2016)Newtonian program analysis via tensor productACM SIGPLAN Notices10.1145/2914770.283765951:1(663-677)Online publication date: 11-Jan-2016
https://dl.acm.org/doi/10.1145/2914770.2837659
Show More Cited By

Recommendations

Fast algorithms for identifying maximal common connected sets of interval graphs

Given a family of interval graphs F = {G₁ = (V, E₁) ..... G_k = (V, E_k)} on the same vertices V, a set S ⊂ V is a maximal common connected set of F if the subgraphs of G_i, 1 ≤ i ≤ k, induced by S are connected in all G_i and S is maximal for the inclusion ...
Fast Approximation Algorithms for Multicommodity Flow Problems

All previously known algorithms for solving the multicommodity flow problem with capacities are based on linear programming. The best of these algorithms uses a fast matrix multiplication algorithm and takes O(k3.5n3m0.5 log(nDU)) time for the ...
Generalized common subexpressions in very high level languages
POPL '77: Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Acta Informatica

Acta Informatica Volume 2, Issue 3

September 1973

92 pages

ISSN:0001-5903

Issue’s Table of Contents

Copyright © Copyright © 1973 Springer-Verlag.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 September 1973

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

41
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhou AHu YXu XZhang C(2024) ARCTURUS: Full Coverage Binary Similarity Analysis with Reachability-guided EmulationACM Transactions on Software Engineering and Methodology10.1145/364033733:4(1-31)Online publication date: 11-Jan-2024
Reps TTuretsky EPrabhu P(2017)Newtonian Program Analysis via Tensor ProductACM Transactions on Programming Languages and Systems10.1145/302408439:2(1-72)Online publication date: 21-Mar-2017
Reps TTuretsky EPrabhu P(2016)Newtonian program analysis via tensor productACM SIGPLAN Notices10.1145/2914770.283765951:1(663-677)Online publication date: 11-Jan-2016
Reps TTuretsky EPrabhu PBodik RMajumdar R(2016)Newtonian program analysis via tensor productProceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages10.1145/2837614.2837659(663-677)Online publication date: 11-Jan-2016
Bodik RMajumdar R(2016)Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming LanguagesundefinedOnline publication date: 11-Jan-2016
Hall MAmarasinghe SMurphy BLiao SLam M(2005)Interprocedural parallelization analysis in SUIFACM Transactions on Programming Languages and Systems10.1145/1075382.107538527:4(662-731)Online publication date: 1-Jul-2005
Cooper KTorczon L(2003)Engineering a CompilerundefinedOnline publication date: 11-Dec-2003
Ramalingam G(2002)On sparse evaluation representationsTheoretical Computer Science10.1016/S0304-3975(00)00315-7277:1-2(119-147)Online publication date: 28-Apr-2002
Sreedhar VGao GLee Y(1998)A new framework for elimination-based data flow analysis using DJ graphsACM Transactions on Programming Languages and Systems10.1145/276393.27852320:2(388-435)Online publication date: 1-Mar-1998
Knoop J(1998)Optimal interprocedural program optimizationundefinedOnline publication date: 1-Jan-1998
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents