Code Generation for a One-Register Machine

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Code Generation for a One-Register Machine

Full text

Pdf (554 KB)

Source

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

Pages: 502 - 510

Year of Publication: 1976

ISSN:0004-5411

Authors

John Bruno	Computer Science Department, The Pennsylvania State University, University Park, Pennsylvania
Ravi Sethi	Computer Science Department, The Pennsylvania State University, University Park, Pennsylvania

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 45, Citation Count: 33

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.321971 What is a DOI?

ABSTRACT

The majority of computers that have been built have performed all computations in devices called accumulators, or registers. In this paper, it is shown that the problem of generating minimal-length code for such machines is hard in a precise sense; specifically it is shown that the problem is NP-complete. The result is true even when the programs being translated are arithmetic expressions. Admittedly, the expressions in question can become complicated.

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, Proceedings of seventh annual ACM symposium on Theory of computing, p.207-217, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803770]
	3	Ano, A.V., AND ULLMAN, J.D. Optimization of straight line programs SIAM J. Comput. 1, 1 (March 1972), 1-19.
	4	James P. Anderson, A note on some compiling algorithms, Communications of the ACM, v.7 n.3, p.149-150, March 1964 [doi>10.1145/363958.363976]
	5	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]
	6	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]
	7	CHROUST, G. Scope conserving expression evaluation. Proe. IFIP Cong. 1971, North-Holland Pub. Co, Amsterdam, pp 178-182.
	8	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]
	9	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]
	10	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]
	11	SAHNI, S Computationally related problems SIAM J Comput S, 4 (Dec 1974), 262-279
	12	S~.THI, R. Complete register allocation problems. SIAM J Comput. ~i, 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	SHNV.H)ER, V. On the number of registers needed to evaluate arithmetic expressions BIT 11, 1 (1971), 84-93.
	15	Peter F. Stockhausen, Adapting optimal code generation for arithmetic expressions to the instruction sets available on present-day computers, Communications of the ACM, v.16 n.6, p.353-354, June 1973 [doi>10.1145/362248.362260]

CITED BY 33

	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
	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
	Dirk-Jan Jongeneel , Yosinori Watanbe , Robert K. Brayton , Ralph Otten, Area and search space control for technology mapping, Proceedings of the 37th conference on Design automation, p.86-91, June 05-09, 2000, Los Angeles, 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
	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 , 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
	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
	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
	Oscar H. Ibarra , Brian S. Leininger, The complexity of the equivalence problem for straight-line programs, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.273-280, April 28-30, 1980, Los Angeles, California, United States
	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
	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
	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
	Jack W. Davidson, A retargetable instruction reorganizer, ACM SIGPLAN Notices, v.21 n.7, p.234-241, July 1986
	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
	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
	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
	Robert A. Mueller , Joseph Varghese, Retargetable microcode synthesis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.2, p.257-276, April 1987
	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
	David Bernstein , Haran Boral , Ron Y. Pinter, Optimal chaining in expression trees, ACM SIGPLAN Notices, v.21 n.7, p.1-10, July 1986
	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
	Oscar H. Ibarra , Brian S. Leininger, On the Simplification and Equivalence Problems for Straight-Line Programs, Journal of the ACM (JACM), v.30 n.3, p.641-656, July 1983
	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
	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
	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
	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
	Randy Allen , Ken Kennedy, Vector Register Allocation, IEEE Transactions on Computers, v.41 n.10, p.1290-1317, October 1992
	R. Govindarajan , Hongbo Yang , José Nelson Amaral , Chihong Zhang , Guang R. Gao, Minimum Register Instruction Sequencing to Reduce Register Spills in Out-of-Order Issue Superscalar Architectures, IEEE Transactions on Computers, v.52 n.1, p.4-20, January 2003
	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
	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
	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
	Timothée Bossart , Alix Munier Kordon , Francis Sourd, Memory management optimization problems for integrated circuit simulators, Discrete Applied Mathematics, v.155 n.14, p.1795-1811, September, 2007
	R. Daniel Resler , Victor Winter, A higher-order strategy for eliminating common subexpressions, Computer Languages, Systems and Structures, v.35 n.4, p.341-364, December, 2009