Code Generation for Expressions with Common Subexpressions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Code Generation for Expressions with Common Subexpressions

Full text

Pdf (847 KB)

Source

Journal of the ACM (JACM) archive
Volume 24 , Issue 1 (January 1977) table of contents

Pages: 146 - 160

Year of Publication: 1977

ISSN:0004-5411

Authors

A. V. Aho	Bell Laboratories, Murray Hill, NJ
S. C. Johnson	Bell Laboratories, Murray Hill, NJ
J. D. Ullman	Dept. of EECS, Princeton University, Princeton, NJ

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 81, Citation Count: 42

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/321992.322001 What is a DOI?

ABSTRACT

This paper shows the problem of generating optimal code for expressions containing common subexpressions is computationally difficult, even for simple expressions and simple machines. Some heuristics for code generation are given and their worst-case behavior is analyzed. For one register machines, an optimal code generation algorithm is given whose time complexity is linear in the size of an expression and exponential only in the amount of sharing.

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	A. V. Aho , S. C. Johnson, Optimal Code Generation for Expression Trees, Journal of the ACM (JACM), v.23 n.3, p.488-501, July 1976 [doi>10.1145/321958.321970]
	3	Alfred V. Aho , Jeffrey D. Ullman, Theory of Parsing, Translation and Compiling, Prentice Hall Professional Technical Reference, 1973
	4	BEA'r'rY, j C A register assignment algorithm for generation of highly optimized object code. IBM J Res Develop. 18, 1 (Jan 1974), 20-39
	5	BELADY, L A A study of replacement algorithms for virtual storage computers. IBM Syst. J 5, 2 (1966), 78-101
	6	Melvin A. Breuer, Generation of optimal code for expressions via factorization, Communications of the ACM, v.12 n.6, p.333-340, June 1969 [doi>10.1145/363011.363153]
	7	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]
	8	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]
	9	CHEN, S On the Setht-Ullman algorithm int Z Comp. Math, A, 5 (1975), 37-55
	10	John Cocke, Programming languages and their compilers: Preliminary notes, Courant Institute of Mathematical Sciences, New York University, 1969
	11	DEMERS, A Private commumcatlon
	12	Richard J. Fateman, Optimal code for serial and parallel computation, Communications of the ACM, v.12 n.12, p.694-695, Dec. 1969 [doi>10.1145/363626.363661]
	13	R. A. Freiburghouse, Register allocation via usage counts, Communications of the ACM, v.17 n.11, p.638-642, Nov. 1974 [doi>10.1145/361179.361201]
	14	L. P. Horwitz , R. M. Karp , R. E. Miller , S. Winograd, Index Register Allocation, Journal of the ACM (JACM), v.13 n.1, p.43-61, Jan. 1966 [doi>10.1145/321312.321317]
	15	SETm, R Complete register allocation problems SIAM J Computmg 4, 3 (Sept 1975), 226-248
	16	SETHI, R Private commumcatlon
	17	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]
	18	William M. Waite, Optimization, Compiler Construction, An Advanced Course, 2nd ed., p.549-602, January 1976
	19	Stephen Gibbs Wasilew, A compiler writing system with optimization capabilities for complex object order structures, 1972
	20	William Allan Wulf , Richard K. Johnsson , Charles B. Weinstock , Steven O. Hobbs , Charles M. Geschke, The Design of an Optimizing Compiler, Elsevier Science Inc., New York, NY, 1975

CITED BY 43

	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
	T. J. Kowalski , D. E. Thomas, The VLSI design automation assistant: prototype system, Papers on Twenty-five years of electronic design automation, p.561-565, June 1988
	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
	Jack W. Davidson, A retargetable instruction reorganizer, ACM SIGPLAN Notices, v.21 n.7, p.234-241, July 1986
	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
	J. R. Goodman , W.-C. Hsu, Code scheduling and register allocation in large basic blocks, Proceedings of the 2nd international conference on Supercomputing, p.442-452, June 1988, St. Malo, France
	S. C. Prasad , K. Roy, Transistor reordering for power minimization under delay constraint, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.2, p.280-300, April 1996
	E. Pelegrí-Llopart , S. L. Graham, Optimal code generation for expression trees: an application BURS theory, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.294-308, January 10-13, 1988, San Diego, California, United States
	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
	John L. Hennessy , Thomas Gross, Postpass Code Optimization of Pipeline Constraints, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.422-448, July 1983
	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
	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
	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
	J. A. van Hulzen, Breuer's grow factor algorithm in computer algebra, Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.100-104, August 05-07, 1981, Snowbird, Utah, United States
	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
	Timothy J. Callahan , Philip Chong , André DeHon , John Wawrzynek, Fast module mapping and placement for datapaths in FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.123-132, February 22-25, 1998, Monterey, California, United States
	Alok Jain , Randal E. Bryant, Mapping switch-level simulation onto gate-level hardware accelerators, Proceedings of the 28th conference on ACM/IEEE design automation, p.219-222, June 17-22, 1991, San Francisco, California, United States
	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
	Steven J. Deitz , Bradford L. Chamberlain , Lawrence Snyder, Eliminating redundancies in sum-of-product array computations, Proceedings of the 15th international conference on Supercomputing, p.65-77, June 2001, Sorrento, Italy
	David Bernstein , Haran Boral , Ron Y. Pinter, Optimal chaining in expression trees, ACM SIGPLAN Notices, v.21 n.7, p.1-10, July 1986
	S. Liao , K. Keutzer , S. Tjiang , S. Devadas, A new viewpoint on code generation for directed acyclic graphs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.3 n.1, p.51-75, Jan. 1998
	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
	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
	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
	David F. Bacon , Susan L. Graham , Oliver J. Sharp, Compiler transformations for high-performance computing, ACM Computing Surveys (CSUR), v.26 n.4, p.345-420, Dec. 1994
	Richard Gisselquist, An experimental C compiler for the Cray 2 computer, ACM SIGPLAN Notices, v.21 n.9, September 1986
	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
	John L. Hennessy , Thomas R. Gross, Code generation and reorganization in the presence of pipeline constraints, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.120-127, January 25-27, 1982, Albuquerque, Mexico
	Tatsushi Inagaki , Hideaki Komatsu , Toshio Nakatani, Integrated prepass scheduling for a Java Just-In-Time compiler on the IA-64 architecture, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
	Sheldon Finkelstein, Common expression analysis in database applications, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida
	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
	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
	Jens Knoop , Oliver Rüthing , Bernhard Steffen, Partial dead code elimination, ACM SIGPLAN Notices, v.29 n.6, p.147-158, June 1994
	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
	Andrew Riffel , Aaron E. Lefohn , Kiril Vidimce , Mark Leone , John D. Owens, Mio: fast multipass partitioning via priority-based instruction scheduling, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, August 29-30, 2004, Grenoble, France
	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
	A. Hosangadi , F. Fallah , R. Kastner, Factoring and eliminating common subexpressions in polynomial expressions, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.169-174, November 07-11, 2004
	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
	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
	Lars Gesellensetter , Sabine Glesner, Only the Best Can Make It: Optimal Component Selection, Electronic Notes in Theoretical Computer Science (ENTCS), v.176 n.2, p.105-124, May, 2007