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

article

Free access

Optimal Code Generation for Expression Trees

Authors:

S. C. JohnsonAuthors Info & Claims

Journal of the ACM (JACM), Volume 23, Issue 3

Pages 488 - 501

https://doi.org/10.1145/321958.321970

Published: 01 July 1976 Publication History

Abstract

This paper discusses algorithms which transform expression trees into code for register machines. A necessary and sufficient condition for optimality of such an algorithm is derived, which applies to a broad class of machines. A dynamic programming algorithm is then presented which produces optimal code for any machine in this class; this algorithm runs in time linearly proportional to the size of the input.

References

[1]

AHO, A V, HOPCROFT, J E, AND ULLMAN, J D The Destgn and Analysts of Computer Algorithms Addison-Wesley, Reading, Mass, 1974

[2]

AHO, A. V., AND ULLMAN, J. D. Optimization of stratght line code SIAM J. Comput. 1, 1 (1972), 1-19.

[3]

BEATTY, J C An axlomattc approach to code optimization for expressions J ACM 19, 4 (Oct 1972), 613-640

[4]

BRUNO, J L, AND LASSAGNE, T The generaL,on of opttmal code for stack machmes J ACM 22, 3 (July 1975), 382-396

[5]

BRUNO, J L, AND SETm, R Code generation for a one-register machine J ACM 23, 3 (July 1976)

[6]

COOK, S A The complextty of theorem prowng procedures Proc 3rd Annual ACM Symposium on Theory of Computing, May 1971, pp 151-158

[7]

KARP, R M Reducibility among combinatorial problems In Complextty of Computer Computattons, R E Miller and J W Thatcher, Eds, Plenum Press, New York, 1972, pp 85-103

[8]

KERNIGHAN, B W AND CHERRY', L,L A system for typesetting mathematics Comm ACM 18, 3 (Mar 1975), 151-156

[9]

KNUTH, D E The Art oJ Computer Programming, Vol 1, Fundamental Algorahms, 2nd ed Addison- Wesley, Reading, Mass, 1973

[10]

NAKATA, I On complhng algorithms for arithmetic expressions Comm ACM 10, 8 (Aug 1967), 492-494

[11]

REDZIEJOWSKI, R R On arithmetic expressions and trees Comm ACM 12, 2 (Feb 1969), 81-84

[12]

SETHI, R Complete register allocation problems SlAM J Computing 4, 3 (Sept 1975), 226-248

[13]

SETHI, R, AND ULLMAN, J D The generation of optimal code for anthmeUc expressions J ACM 17, 4 (Oct 1970), 715-728

[14]

WASILEW, S G A compder wrmng system w~th opt~mtzat~on capablhttes for complex order structures, Ph D th, Northwestern U, Evanston, I11, 1971

[15]

WALKER, S A, AND STRONG, H R Characterizations of flowchartable recurmons Proc 4th Annual ACM Symposium on Theory of Computing, May 1972, pp 18-34

Cited By

Espindola VZago LYviquel HAraujo G(2023)Source Matching and Rewriting for MLIR Using String-Based AutomataACM Transactions on Architecture and Code Optimization10.1145/357128320:2(1-26)Online publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1145/3571283
(2023)BibliographyEngineering a Compiler10.1016/B978-0-12-815412-0.00023-1(793-813)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00023-1
Cooper KTorczon L(2023)Instruction SelectionEngineering a Compiler10.1016/B978-0-12-815412-0.00017-6(575-616)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00017-6
Show More Cited By

Index Terms

Optimal Code Generation for Expression Trees
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Trees
2. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Source code generation

Recommendations

Optimal code generation for expression trees
STOC '75: Proceedings of the seventh annual ACM symposium on Theory of computing

We discuss the problem of generating code for a wide class of machines, restricting ourselves to the computation of expression trees. After defining a broad class of machines and discussing the properties of optimal programs on these machines, we derive ...
Efficient generation of plane trees

A rooted plane tree is a rooted tree with a left-to-right ordering specified for the children of each vertex. In this paper we give a simple algorithm to generate all rooted plane trees with at most n vertices. The algorithm uses O(n) space and ...
On the Optimality of Binary AIFV Codes with Two Code Trees
2021 IEEE International Symposium on Information Theory (ISIT)
Huffman code is the optimal code in the class of uniquely decodable codes in the sense of the average length of codeword when a single code tree can represent the code. This paper defines hierarchical subclasses of noiseless source codes by allowing <tex>$...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 23, Issue 3

July 1976

175 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321958

Issue’s Table of Contents

Copyright © 1976 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1976

Published in JACM Volume 23, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

234
Total Citations
View Citations
2,692
Total Downloads

Downloads (Last 12 months)320
Downloads (Last 6 weeks)31

Reflects downloads up to 27 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Espindola VZago LYviquel HAraujo G(2023)Source Matching and Rewriting for MLIR Using String-Based AutomataACM Transactions on Architecture and Code Optimization10.1145/357128320:2(1-26)Online publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1145/3571283
(2023)BibliographyEngineering a Compiler10.1016/B978-0-12-815412-0.00023-1(793-813)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00023-1
Cooper KTorczon L(2023)Instruction SelectionEngineering a Compiler10.1016/B978-0-12-815412-0.00017-6(575-616)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00017-6
Cooper KTorczon L(2023)Code ShapeEngineering a Compiler10.1016/B978-0-12-815412-0.00013-9(327-378)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00013-9
Berezun DBoulytchev D(2022)Reimplementing the Wheel: Teaching Compilers with a Small Self-Contained OneElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.363.2363(22-43)Online publication date: 26-Jul-2022
https://doi.org/10.4204/EPTCS.363.2
Barthels HPsarras CBientinesi P(2021)LinneaACM Transactions on Mathematical Software10.1145/344663247:3(1-26)Online publication date: 26-Jun-2021
https://dl.acm.org/doi/10.1145/3446632
Barthels HPsarras CBientinesi P(2020)Automatic Generation of Efficient Linear Algebra ProgramsProceedings of the Platform for Advanced Scientific Computing Conference10.1145/3394277.3401836(1-11)Online publication date: 29-Jun-2020
https://dl.acm.org/doi/10.1145/3394277.3401836
Khatri SShenoy NGiomi JKhouja A(2016)Logic SynthesisElectronic Design Automation for IC Implementation, Circuit Design, and Process Technology10.1201/b19714-4(27-55)Online publication date: 14-Apr-2016
https://doi.org/10.1201/b19714-4
Keutzer KRavindran K(2016)Technology MappingEncyclopedia of Algorithms10.1007/978-1-4939-2864-4_420(2200-2204)Online publication date: 22-Apr-2016
https://doi.org/10.1007/978-1-4939-2864-4_420
Wasik SFratczak FKrzyskow JWulnikowski J(2015)Inferring Mathematical Equations Using CrowdsourcingPLOS ONE10.1371/journal.pone.014555710:12(e0145557)Online publication date: 29-Dec-2015
https://doi.org/10.1371/journal.pone.0145557
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents