Register allocation by puzzle solving

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Register allocation by puzzle solving

Full text

Pdf (1.68 MB)

Source

Conference on Programming Language Design and Implementation archive
Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation table of contents

Tucson, AZ, USA

SESSION: Session VIII table of contents

Pages 216-226

Year of Publication: 2008

ISBN:978-1-59593-860-2

Also published in ...

Authors

Fernando Magno Quintão Pereira	University of California, Los Angeles, Los Angeles, CA, USA
Jens Palsberg	University of California, Los Angeles, Los Angeles, CA, USA

Sponsors

ACM: Association for Computing Machinery
SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 248, Citation Count: 0

Additional Information:

abstract references 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/1375581.1375609 What is a DOI?

ABSTRACT

We show that register allocation can be viewed as solving a collection of puzzles. We model the register file as a puzzle board and the program variables as puzzle pieces; pre-coloring and register aliasing fit in naturally. For architectures such as PowerPC, x86, and StrongARM, we can solve the puzzles in polynomial time, and we have augmented the puzzle solver with a simple heuristic for spilling. For SPEC CPU2000, the compilation time of our implementation is as fast as that of the extended version of linear scan used by LLVM, which is the JIT compiler in the openGL stack of Mac OS 10.5. Our implementation produces x86 code that is of similar quality to the code produced by the slower, state-of-the-art iterated register coalescing of George and Appel with the extensions proposed by Smith, Ramsey, and Holloway in 2004.

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	Scott Ananian. The static single information form. Master's thesis, MIT, September 1999.
	2	Andrew W. Appel , Lal George, Optimal spilling for CISC machines with few registers, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.243-253, June 2001, Snowbird, Utah, United States
	3	L. Belady. A study of the replacement of algorithms of a virtual storage computer. IBM System Journal, 5:78--101, 1966.
	4	M. Biró , M. Hujter , Zs. Tuza, Precoloring extension. I: Interval graphs, Discrete Mathematics, v.100 n.1-3, p.267-279, May 15, 1992 [doi>10.1016/0012-365X(92)90646-W]
	5	Rastislav Bodík , Rajiv Gupta , Vivek Sarkar, ABCD: eliminating array bounds checks on demand, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.321-333, June 18-21, 2000, Vancouver, British Columbia, Canada
	6	Florent Bouchez. Allocation de registres et vidage en mémoire. Master's thesis, ENS Lyon, 2005.
	7	Florent Bouchez, Alain Darte, Christophe Guillon, and Fabrice Rastello. Register allocation: What does the NP-completeness proof of chaitin et al. really prove? Or revisiting register allocation: Why and how. In LCPC, pages 283--298. Springer, 2006.
	8	Preston Briggs , Keith D. Cooper , Timothy J. Harvey , L. Taylor Simpson, Practical improvements to the construction and destruction of static single assignment form, Software—Practice & Experience, v.28 n.8, p.859-881, July 10, 1998 [doi>10.1002/(SICI)1097-024X(19980710)28:8<859::AID-SPE188>3.0.CO;2-8]
	9	Philip Brisk, Foad Dabiri, Jamie Macbeth, and Majid Sarrafzadeh. Polynomial-time graph coloring register allocation. In IWLS, pages 447--454. 2005.
	10	Philip Brisk , Majid Sarrafzadeh, Interference graphs for procedures in static single information form are interval graphs, Proceedingsof the 10th international workshop on Software & compilers for embedded systems, April 20-20, 2007, Nice, France [doi>10.1145/1269843.1269858]
	11	Zoran Budimlic , Keith D. Cooper , Timothy J. Harvey , Ken Kennedy , Timothy S. Oberg , Steven W. Reeves, Fast copy coalescing and live-range identification, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
	12	Gregory J. Chaitin, Mark A. Auslander, Ashok K. Chandra, John Cocke, Martin E. Hopkins, and Peter W. Markstein. Register allocation via coloring. Computer Languages, 6:47--57, 1981.
	13	Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
	14	Alkis Evlogimenos. Improvements to linear scan register allocation. Technical report, University of Illinois, Urbana-Champaign, 2004.
	15	Martin Farach , Vincenzo Liberatore, On local register allocation, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.564-573, January 25-27, 1998, San Francisco, California, United States
	16	Fanica Gavril. The intersection graphs of subtrees of a tree are exactly the chordal graphs. Journal of Combinatorial Theory, Series B, 16(1):47 -- 56, 1974.
	17	Lal George , Andrew W. Appel, Iterated register coalescing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.3, p.300-324, May 1996 [doi>10.1145/229542.229546]
	18	Martin Charles Golumbic. Trivially perfect graphs. Discrete Mathematics, 24:105 -- 107, 1978.
	19	Daniel Grund and Sebastian Hack. A fast cutting-plane algorithm for optimal coalescing. In CC, volume 4420, pages 111--115. Springer, 2007.
	20	Sebastian Hack, Daniel Grund, and Gerhard Goos. Register allocation for programs in SSA-form. In CC, pages 247--262. Springer, 2006.
	21	Lang Hames and Bernhard Scholz. Nearly optimal register allocation with PBQP. In JMLC, pages 346--361. Springer, 2006.
	22	Corporate SPARC International Inc. The SPARC Architecture Manual, Version 8. Prentice Hall, 1st edition, 1992.
	23	Richard Johnson , Keshav Pingali, Dependence-based program analysis, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.78-89, June 21-25, 1993, Albuquerque, New Mexico, United States
	24	Richard M Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85--103. Plenum, 1972.
	25	David Ryan Koes , Seth Copen Goldstein, A global progressive register allocator, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
	26	Chris Lattner , Vikram Adve, LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.75, March 20-24, 2004, Palo Alto, California
	27	Jonathan K. Lee, Jens Palsberg, and Fernando M. Q. Pereira. Aliased register allocation for straight-line programs is NP-complete. In ICALP, pages 680--691. Springer, 2007.
	28	Dániel Marx, Precoloring extension on unit interval graphs, Discrete Applied Mathematics, v.154 n.6, p.995-1002, 15 April 2006 [doi>10.1016/j.dam.2005.10.008]
	29	Clyde L Monma, Intersection graphs of paths in a tree, Journal of Combinatorial Theory Series B, v.41 n.2, p.141-181, Oct. 1986 [doi>10.1016/0095-8956(86)90042-0]
	30	Fernando Magno Quintao Pereira and Jens Palsberg. Register allocation via coloring of chordal graphs. In APLAS, pages 315--329. Springer, 2005.
	31	Fernando Magno Quintao Pereira and Jens Palsberg. Register allocation after classic SSA elimination is NP-complete. In FOSSACS, pages 79--93. Springer, 2006.
	32	Fernando Magno Quintao Pereira and Jens Palsberg. Register allocation by puzzle solving, 2008. http://compilers.cs.ucla.edu/ fernando/projects/puzzles/.
	33	Massimiliano Poletto , Vivek Sarkar, Linear scan register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.5, p.895-913, Sept. 1999 [doi>10.1145/330249.330250]
	34	Vivek Sarkar and Rajkishore Barik. Extended linear scan: an alternate foundation for global register allocation. In CC, pages 141--155. Springer, 2007.
	35	Bernhard Scholz , Erik Eckstein, Register allocation for irregular architectures, ACM SIGPLAN Notices, v.37 n.7, July 2002
	36	Michael D. Smith , Norman Ramsey , Glenn Holloway, A generalized algorithm for graph-coloring register allocation, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
	37	Vugranam C. Sreedhar , Roy Dz-Ching Ju , David M. Gillies , Vatsa Santhanam, Translating Out of Static Single Assignment Form, Proceedings of the 6th International Symposium on Static Analysis, p.194-210, September 22-24, 1999
	38	Omri Traub , Glenn Holloway , Michael D. Smith, Quality and speed in linear-scan register allocation, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.142-151, June 17-19, 1998, Montreal, Quebec, Canada
	39	CORPORATE SPARC International, Inc., The SPARC architecture manual (version 9), Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
	40	Christian Wimmer , Hanspeter Mössenböck, Optimized interval splitting in a linear scan register allocator, Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments, June 11-12, 2005, Chicago, IL, USA [doi>10.1145/1064979.1064998]
	41	Mihalis Yannakakis , Fanica Gavril, The maximum k-colorable subgraph problem for chordal graphs, Information Processing Letters, v.24 n.2, p.133-137, January 1987 [doi>10.1016/0020-0190(87)90107-4]