Near-optimal instruction selection on dags

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Near-optimal instruction selection on dags

Full text

Pdf (614 KB)

Source

Code Generation and Optimization archive
Proceedings of the sixth annual IEEE/ACM international symposium on Code generation and optimization table of contents

Boston, MA, USA

SESSION: Static program analysis table of contents

Pages 45-54

Year of Publication: 2008

ISBN:978-1-59593-978-4

Authors

David Ryan Koes	Carnegie Mellon University, Pittsburgh, PA, USA
Seth Copen Goldstein	Carnegie Mellon University, Pittsburgh, PA, USA

Sponsors

ACM: Association for Computing Machinery
SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing
SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 72, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	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/1356058.1356065 What is a DOI?

ABSTRACT

Instruction selection is a key component of code generation. High quality instruction selection is of particular importance in the embedded space where complex instruction sets are common and code size is a prime concern. Although instruction selection on tree expressions is a well understood and easily solved problem, instruction selection on directed acyclic graphs is NP-complete. In this paper we present NOLTIS, a near-optimal, linear time instruction selection algorithm for DAG expressions. NOLTIS is easy to implement, fast, and effective with a demonstrated average code size improvement of 5.1% compared to the traditional tree decomposition and tiling approach.

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	Aho, A., and Ullman, J. Optimization of stright line programs. SIAM Journal on Computing 1, 1 (1972), 1--19.
	2	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 [doi>10.1145/69558.75700]
	3	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]
	4	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 [doi>10.1145/321992.322001]
	5	Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	6	Andrew W. Appel, Modern compiler implementation in Java: basic techniques, Cambridge University Press, New York, NY, 1997
	7	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
	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	R. G. Cattell, Automatic Derivation of Code Generators from Machine Descriptions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.2, p.173-190, April 1980 [doi>10.1145/357094.357097]
	10	Cooper, K. D., and Torczon, L. Engineering a Compiler. Morgan Kaufmann Publishers, 2004.
	11	CPLEX.http://ilog.com/products/cplex.
	12	Jack W. Davidson , Christopher W. Fraser, Code selection through object code optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.4, p.505-526, Oct. 1984 [doi>10.1145/1780.1783]
	13	Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
	14	H. Emmelmann , F.-W. Schröer , L. Landwehr, BEG: a generation for efficient back ends, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.227-237, June 19-23, 1989, Portland, Oregon, United States
	15	M. Anton Ertl, Optimal code selection in DAGs, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.242-249, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292562]
	16	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 [doi>10.1145/151640.151642]
	17	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 [doi>10.1145/131080.131089]
	18	Christopher W. Fraser , Alan L. Wendt, Integrating code generation and optimization, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.242-248, June 25-27, 1986, Palo Alto, California, United States
	19	C. W. Fraser , A. L. Wendt, Automatic generation of fast optimizing code generators, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.79-84, June 20-24, 1988, Atlanta, Georgia, United States
	20	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	21	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 [doi>10.1145/512760.512785]
	22	Soha Hassoun , Tsutomu Sasao, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 2001
	23	Christoph Keßler , Andrzej Bednarski, A Dynamic Programming Approach to Optimal Integrated Code Generation, Proceedings of the ACM SIGPLAN workshop on Languages, compilers and tools for embedded systems, p.165-174, August 2001, Snow Bird, Utah, United States
	24	Robert R. Kessler, Peep: an architectural description driven peephole optimizer, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.106-110, June 17-22, 1984, Montreal, Canada
	25	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 [doi>10.1145/37888.37940]
	26	Rainer LEUPERS Leupers , Steven Bashford, 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 [doi>10.1145/362652.362661]
	27	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
	28	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 [doi>10.1145/270580.270583]
	29	The LLVM compiler infrastructure project. http://llvm.org.
	30	W. M. McKeeman, Peephole optimization, Communications of the ACM, v.8 n.7, p.443-444, July 1965 [doi>10.1145/364995.365000]
	31	Mayur Naik , Jens Palsberg, Compiling with code-size constraints, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.1, p.163-181, February 2004 [doi>10.1145/972627.972635]
	32	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 [doi>10.1145/73560.73586]
	33	Proebsting, T. Least-cost instruction selection in dags is NP-complete. http://research.microsoft.com/ toddpro/papers/proof.htm.
	34	Todd A. Proebsting, Simple and efficient BURS table generation, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.331-340, June 15-19, 1992, San Francisco, California, United States
	35	Todd A. Proebsting, BURS automata generation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.3, p.461-486, May 1995 [doi>10.1145/203095.203098]
	36	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]
	37	MediaBench I http://euler.slu.edu/ fritts/mediabench/
	38	MiBench http://www.eecs.umich.edu/mibench/
	39	SPEC CPU2006 http://www.spec.org/cpu2006/.
	40	VersaBench: A Benchmark Suite for Versatile Architectures http://cag.csail.mit.edu/versabench/