Optimal Code Generation for Expression Trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal Code Generation for Expression Trees

Full text

Pdf (896 KB)

Source

Journal of the ACM (JACM) archive
Volume 23 , Issue 3 (July 1976) table of contents

Pages: 488 - 501

Year of Publication: 1976

ISSN:0004-5411

Authors

A. V. Aho	Bell Laboratories, Murray Hill, New Jersey
S. C. Johnson	Bell Laboratories, Murray Hill, New Jersey

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 92, Citation Count: 62

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321958.321970 What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	AHO, A. V. , AND ULLMAN, J. D. Optimization of stratght line code SIAM J. Comput. 1, 1 (1972), 1-19.
	3	James C. Beatty, An axiomatic approach to code optimization for expressions, Journal of the ACM (JACM), v.19 n.4, p.613-640, Oct. 1972 [doi>10.1145/321724.321728]
	4	J. L. Bruno , T. Lassagne, The Generation of Optimal Code for Stack Machines, Journal of the ACM (JACM), v.22 n.3, p.382-396, July 1975 [doi>10.1145/321892.321901]
	5	John Bruno , Ravi Sethi, Code Generation for a One-Register Machine, Journal of the ACM (JACM), v.23 n.3, p.502-510, July 1976 [doi>10.1145/321958.321971]
	6	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	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	Brian W. Kernighan , Lorinda L. Cherry, A system for typesetting mathematics, Communications of the ACM, v.18 n.3, p.151-157, March 1975 [doi>10.1145/360680.360684]
	9	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	10	Ikuo Nakata, On compiling algorithms for arithmetic expressions, Communications of the ACM, v.10 n.8, p.492-494, Aug. 1967 [doi>10.1145/363534.363549]
	11	R. R. Redziejowski, On arithmetic expressions and trees, Communications of the ACM, v.12 n.2, p.81-84, Feb. 1969 [doi>10.1145/362848.362859]
	12	SETHI, R Complete register allocation problems SlAM J Computing 4, 3 (Sept 1975), 226-248
	13	Ravi Sethi , J. D. Ullman, The Generation of Optimal Code for Arithmetic Expressions, Journal of the ACM (JACM), v.17 n.4, p.715-728, Oct. 1970 [doi>10.1145/321607.321620]
	14	Stephen Gibbs Wasilew, A compiler writing system with optimization capabilities for complex object order structures, 1972
	15	S. A. Walker , H. R. Strong, Characterizations of flowchartable recursions short version, Proceedings of the fourth annual ACM symposium on Theory of computing, p.18-34, May 01-03, 1972, Denver, Colorado, United States [doi>10.1145/800152.804893]

CITED BY 62

	Alfred V. Aho , Mahadevan Ganapathi , Steven W. K. Tjiang, Code generation using tree matching and dynamic programming, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.491-516, Oct. 1989
	John Crawford, Engineering a production code generator, ACM SIGPLAN Notices, v.17 n.6, p.205-215, June 1982
	A. V. Aho , S. C. Johnson , J. D. Ullman, Code Generation for Expressions with Common Subexpressions, Journal of the ACM (JACM), v.24 n.1, p.146-160, Jan. 1977
	Bhaskaram Prabhala , Ravi Sethi, Efficient Computation of Expressions with Common Subexpressions, Journal of the ACM (JACM), v.27 n.1, p.146-163, Jan. 1980
	Guido Araujo , Sharad Malik, Code generation for fixed-point DSPs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.3 n.2, p.136-161, April 1998
	K. Keutzer , W. Wolf, Anatomy of a hardware compiler, ACM SIGPLAN Notices, v.23 n.7, p.95-104, July 1988
	Pradip Bose, Optimal code generation for expressions on super scalar machines, Proceedings of 1986 ACM Fall joint computer conference, p.372-379, November 1986, Dallas, Texas, United States
	Jack W. Davidson, A retargetable instruction reorganizer, ACM SIGPLAN Notices, v.21 n.7, p.234-241, July 1986
	S. C. Johnson, A portable compiler: theory and practice, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.97-104, January 23-25, 1978, Tucson, Arizona
	Bhaskaram Prabhala , Ravi Sethi, Efficient computation of expressions with common subexpressions, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.222-230, January 23-25, 1978, Tucson, Arizona
	A. V. Aho , S. C. Johnson , J. D. Ullman, Code-generation for machines with multiregister operations, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.21-28, January 17-19, 1977, Los Angeles, California
	Christopher W. Fraser , David R. Hanson , Todd A. Proebsting, Engineering a simple, efficient code-generator generator, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.3, p.213-226, Sept. 1992
	Mahadevan Ganapathi , Charles N. Fischer , John L. Hennessy, Retargetable Compiler Code Generation, ACM Computing Surveys (CSUR), v.14 n.4, p.573-592, Dec. 1982
	E. G. Coffman, Jr. , Ravi Sethi, Instruction Sets for Evaluating Arithmetic Expressions, Journal of the ACM (JACM), v.30 n.3, p.457-478, July 1983
	Guido Araujo , Sharad Malik, Optimal code generation for embedded memory non-homogeneous register architectures, Proceedings of the 8th international symposium on System synthesis, p.36-41, September 13-15, 1995, Cannes, France
	Stephan Murer , Philipp Färber, Code Generation for Multi-Threaded Architectures from Dataflow Graphs, Proceedings of the IFIP WG10.3. Working Conference on Architectures and Compilation Techniques for Fine and Medium Grain Parallelism, p.77-90, January 20-22, 1993
	Sungjoon Jung , Yunheung Paek, The very portable optimizer for digital signal processors, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA
	Bhaskaram Prabhala , Ravi Sethi, A comparison of instruction sets for stack machines, Proceedings of the ninth annual ACM symposium on Theory of computing, p.132-142, May 04-04, 1977, Boulder, Colorado, United States
	A. Rudmik , E. S. Lee, Compiler design for efficient code generation and program optimization, ACM SIGPLAN Notices, v.14 n.8, p.127-138, August 1979
	Leon Stok , Vivek Tiwari, Technology mapping, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 2001
	Robert J. Sheraga , John L. Gieser, Automatic microcode generation for horizontally microprogrammed processors, ACM SIGMICRO Newsletter, v.12 n.4, p.154-168, Dec. 1981
	David Bernstein , Haran Boral , Ron Y. Pinter, Optimal chaining in expression trees, ACM SIGPLAN Notices, v.21 n.7, p.1-10, July 1986
	Christoph Kessler , Andrzej Bednarski, Optimal integrated code generation for clustered VLIW architectures, ACM SIGPLAN Notices, v.37 n.7, July 2002
	Massoud Pedram , Narasimha Bhat, Layout driven technology mapping, Proceedings of the 28th conference on ACM/IEEE design automation, p.99-105, June 17-22, 1991, San Francisco, California, United States
	Philip Brisk , Adam Kaplan , Ryan Kastner , Majid Sarrafzadeh, Instruction generation and regularity extraction for reconfigurable processors, Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems, October 08-11, 2002, Grenoble, France
	K. Keutzer, DAGON: Technology binding and local optimization by DAG matching, Papers on Twenty-five years of electronic design automation, p.617-624, June 1988
	K. Keutzer, DAGON: technology binding and local optimization by DAG matching, Proceedings of the 24th ACM/IEEE conference on Design automation, p.341-347, June 28-July 01, 1987, Miami Beach, Florida, United States
	M. Corazao , M. Khalaf , L. Guerra , M. Potkonjak , J. Rabaey, Instruction set mapping for performance optimization, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.518-521, November 07-11, 1993, Santa Clara, California, United States
	David Bernstein , Izidor Gertner, Scheduling expressions on a pipelined processor with a maximal delay of one cycle, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.1, p.57-66, Jan. 1989
	Guido Araujo , Guilherme Ottoni , Marcelo Cintra, Global array reference allocation, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.2, p.336-357, April 2002
	Christoph Keßler , Andrzej Bednarski, A Dynamic Programming Approach to Optimal Integrated Code Generation, ACM SIGPLAN Notices, v.36 n.8, p.165-174, Aug. 2001
	Philippe Aigrain , Susan L. Graham , Robert R. Henry , Marshall Kirk McKusick , Eduardo Pelegri-Llopart, Experience with a Graham-Glanville style code generator, ACM SIGPLAN Notices, v.19 n.6, p.13-24, June 1984
	David R. Ditzel , David A. Patterson, Retrospective on high-level language computer architecture, 25 years of the international symposia on Computer architecture (selected papers), p.166-173, June 27-July 02, 1998, Barcelona, Spain
	Waleed M. Meleis , Edward S. Davidson, Dual-issue scheduling with spills for binary trees, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.678-686, January 17-19, 1999, Baltimore, Maryland, United States
	Graph-based code selection techniques for embedded processors, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.4, p.794-814, Oct. 2000
	Roger Hoover , Kenneth Zadeck, Generating machine specific optimizing compilers, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.219-229, January 21-24, 1996, St. Petersburg Beach, Florida, United States
	Stan Liao , Srinivas Devadas , Kurt Keutzer , Steve Tjiang, Instruction selection using binate covering for code size optimization, Readings in hardware/software co-design, Kluwer Academic Publishers, Norwell, MA, 2001
	D. Bernstein , J. M. Jaffe , M. Rodeh, Scheduling arithmetic and load operations in parallel with no spilling, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.263-273, January 21-23, 1987, Munich, West Germany
	Qin Zhao , Bart Mesman , Twan Basten, Static resource models for code-size efficient embedded processors, ACM Transactions on Embedded Computing Systems (TECS), v.2 n.2, p.219-250, May 2003
	R. Venugopal , Y. N. Srikant, Scheduling expression trees for delayed-load architectures, Journal of Systems Architecture: the EUROMICRO Journal, v.48 n.4-5, p.151-173, December 2002
	Gert Goossens , Johan Van Praet , Dirk Lanneer , Werner Geurts , Augusli Kifli , Clifford Liem , Pierre G. Paulin, Embedded software in real-time signal processing systems: design technologies, Readings in hardware/software co-design, Kluwer Academic Publishers, Norwell, MA, 2001
	Jason Cong , Yiping Fan , Guoling Han , Zhiru Zhang, Application-specific instruction generation for configurable processor architectures, Proceedings of the 2004 ACM/SIGDA 12th international symposium on Field programmable gate arrays, February 22-24, 2004, Monterey, California, USA
	David W. Krumme , David H. Ackley, A practical method for code generation based on exhaustive search, ACM SIGPLAN Notices, v.17 n.6, p.185-196, June 1982
	Stan Liao , Srinivas Devadas , Kurt Keutzer , Steve Tjiang, Instruction selection using binate covering for code size optimization, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.393-399, November 05-09, 1995, San Jose, California, United States
	Thomas W. Christopher , Philip J. Hatcher , Ronald C. Kukuk, Using dynamic programming to generate optimized code in a Graham-Glanville style code generator, ACM SIGPLAN Notices, v.19 n.6, p.25-36, June 1984
	Karel Čulík, Almost control-free (indeterministic) parallel computation on permit schemes, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.176-184, January 23-25, 1978, Tucson, Arizona
	Manfred Weber , Susan L. Bernstein, Global register allocation for non-equivalent register sets, ACM SIGPLAN Notices, v.15 n.2, p.74-81, February 1980
	Christine Eisenbeis , Franco Gasperoni , Uwe Schwiegelshohn, Allocating registers in multiple instruction-issuing processors, Proceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques, p.290-293, June 27-29, 1995, Limassol, Cyprus
	D. Bernstein , H. Boral , R. Y. Pinter, Optimal Chaining in Expression Trees, IEEE Transactions on Computers, v.37 n.11, p.1366-1374, November 1988
	R. Steven Glanville , Susan L. Graham, A new method for compiler code generation, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.231-254, January 23-25, 1978, Tucson, Arizona
	Stefan Farfeleder , Andreas Krall , Edwin Steiner , Florian Brandner, Effective compiler generation by architecture description, ACM SIGPLAN Notices, v.41 n.7, July 2006
	K. S. Venugopal , Geetha Manjunath , Venkatesh Krishnan, sEc: A Portable Interpreter Optimizing Technique for Embedded Java Virtual Machine, Proceedings of the 2nd Java™ Virtual Machine Research and Technology Symposium, p.127-138, August 01-02, 2002
	David Ryan Koes , Seth Copen Goldstein, Near-optimal instruction selection on dags, Proceedings of the sixth annual IEEE/ACM international symposium on Code generation and optimization, April 05-09, 2008, Boston, MA, USA
	Florian Brandner , Dietmar Ebner , Andreas Krall, Compiler generation from structural architecture descriptions, Proceedings of the 2007 international conference on Compilers, architecture, and synthesis for embedded systems, September 30-October 03, 2007, Salzburg, Austria
	Dietmar Ebner , Florian Brandner , Bernhard Scholz , Andreas Krall , Peter Wiedermann , Albrecht Kadlec, Generalized instruction selection using SSA-graphs, ACM SIGPLAN Notices, v.43 n.7, July 2008
	Stefan Schäfer , Bernhard Scholz, Optimal chain rule placement for instruction selection based on SSA graphs, Proceedingsof the 10th international workshop on Software & compilers for embedded systems, April 20-20, 2007, Nice, France
	Paul Týma, Transient variable caching in Java’s stack-based intermediate representation, Scientific Programming, v.7 n.2, p.157-166, April 1999
	David Bernstein , Ron Y. Pinter , Michael Rodeh, Optimal scheduling of arithmetic operations in parallel with memory access (preliminary version), Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.325-333, January 14-16, 1985, New Orleans, Louisiana, United States
	Alfred V. Aho , Mahadevan Ganapathi, Efficient tree pattern matching (extended abstract): an aid to code generation, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.334-340, January 14-16, 1985, New Orleans, Louisiana, United States
	Johan van Praet , Dirk Lanneer , Gert Goossens , Werner Geurts , Hugo de Man, A Graph Based Processor Model for Retargetable Code Generation, Proceedings of the 1996 European conference on Design and Test, p.102, March 11-14, 1996
	Christopher W. Fraser , Robert R. Henry , Todd A. Proebsting, BURG: fast optimal instruction selection and tree parsing, ACM SIGPLAN Notices, v.27 n.4, p.68-76, April 1992
	Henry G. Baker, Linear logic and permutation stacks—the Forth shall be first, ACM SIGARCH Computer Architecture News, v.22 n.1, p.34-43, March 1994