Improvements to graph coloring register allocation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Improvements to graph coloring register allocation

Full text

Pdf (2.00 MB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 16 , Issue 3 (May 1994) table of contents

Pages: 428 - 455

Year of Publication: 1994

ISSN:0164-0925

Authors

Preston Briggs	Rice Univ., Houston, TX
Keith D. Cooper	Rice Univ., Houston, TX
Linda Torczon	Rice Univ., Houston, TX

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 25, Downloads (12 Months): 131, Citation Count: 79

Additional Information:

abstract references cited by index terms review 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/177492.177575 What is a DOI?

ABSTRACT

We describe two improvements to Chaitin-style graph coloring register allocators. The first, optimistic coloring, uses a stronger heuristic to find a k-coloring for the interference graph. The second extends Chaitin's treatment of rematerialization to handle a larger class of values. These techniques are complementary. Optimistic coloring decreases the number of procedures that require spill code and reduces the amount of spill code when spilling is unavoidable. Rematerialization lowers the cost of spilling some values. This paper describes both of the techniques and our experience building and using register allocators that incorporate them. It provides a detailed description of optimistic coloring and rematerialization. It presents experimental data to show the performance of several versions of the register allocator on a suite of FORTRAN programs. It discusses several insights that we discovered only after repeated implementation of these allocators.

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	Patricia Anklam , Cutler , Heinen , MacLaren, Engineering a Compiler: VAX-11 Code Generation and Optimization, Butterworth-Heinemann, Newton, MA, 1982
	2	D. Bernstein , M. Golumbic , y. Mansour , R. Pinter , D. Goldin , H. Krawczyk , I. Nahshon, Spill code minimization techniques for optimizing compliers, ACM SIGPLAN Notices, v.24 n.7, p.258-263, July 1989
	3	Preston Briggs, Register allocation via graph coloring, Rice University, Houston, TX, 1992
	4	Preston Briggs , Keith D. Cooper , Linda Torczon, Coloring register pairs, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.1, p.3-13, March 1992 [doi>10.1145/130616.130617]
	5	David Callahan , Brian Koblenz, Register allocation via hierarchical graph coloring, ACM SIGPLAN Notices, v.26 n.6, p.192-203, June 1991
	6	G. J. Chaitin, Register allocation & spilling via graph coloring, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.98-105, June 23-25, 1982, Boston, Massachusetts, United States
	7	~ CHAITIN, G.J. 1986. Register allocal~lon and spilling via graph coloring. United States Patent ~ 4,571,678, Feb.
	8	~ CHAITIN, a. J., AUSLANDER, M. A., CRANDRA, A K, COOKE, J., HOPKINS, M. E., AND MARKSTEIN, ~ P.W. 1981. Register allocation via coloring. Comput. Lang. 6, 1 (Jan.), 47-57.
	9	Jong-Deok Choi , Ron Cytron , Jeanne Ferrante, Automatic construction of sparse data flow evaluation graphs, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.55-66, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99594]
	10	Frederick Chow , John Hennessy, Register allocation by priority-based coloring, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.222-232, June 17-22, 1984, Montreal, Canada
	11	Fred C. Chow , John L. Hennessy, The priority-based coloring approach to register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.4, p.501-536, Oct. 1990 [doi>10.1145/88616.88621]
	12	COOPER, K. D., HALL, M. W., HOOD, R. T., KENNEDY, K., MCKINLEY, K., MELLOR-CRUMMEY, J., ~TORCZON, L., AND WARREN, S.K. 1993. The ParaScope parallel programming environment. ~Proc. IEEE 81, 2 (Feb.), 244-263.
	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	ERSHOV, A.P. 1962. Reduction of the problem of memory allocation in programming to the ~problem of coloring the vertices of graphs. Doklady Akademii Nauk S.S.S.R. 142, 4, 785-787. ~(English translation in Soviet Math. 3, 1 (Jan. 1962), 163-165.)
	15	A. P. Yershov, ALPHA—An Automatic Programming System of High Efficiency, Journal of the ACM (JACM), v.13 n.1, p.17-24, Jan. 1966 [doi>10.1145/321312.321314]
	16	Janet Fabri, Automatic storage optimization, Proceedings of the 1979 SIGPLAN symposium on Compiler construction, p.83-91, August 06-10, 1979, Denver, Colorado, United States
	17	Todd A. Proebsting , Charles N. Fischer, Probabilistic register allocation, ACM SIGPLAN Notices, v.27 n.7, p.300-310, July 1992
	18	George E. Forsythe , Michael A. Malcolm , Cleve B. Moler, Computer Methods for Mathematical Computations, Prentice Hall Professional Technical Reference, 1977
	19	Christopher W. Fraser, A retargetable compiler for ANSI C, ACM SIGPLAN Notices, v.26 n.10, p.29-43, Oct. 1991 [doi>10.1145/122616.122621]
	20	Christopher W. Fraser , David R. Hanson, Simple register spilling in a retargetable compiler, Software—Practice & Experience, v.22 n.1, p.85-99, Jan. 1992 [doi>10.1002/spe.4380220105]
	21	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
	22	~GOLUB, G. H., AND REINSCH, C. 1971. Singular value decomposition and least squares solu- ~tions. In Handbook for Automatic Computation, J. H. Wilkinson and C. Reinsch, Eds. ~Springer-Verlag, New York.
	23	R. Gupta , M. L. Soffa , T. Steele, Register allocation via clique separators, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.264-274, June 19-23, 1989, Portland, Oregon, United States
	24	Mark S. Johnson , Terrence C. Miller, Effectiveness of a machine-level, global optimizer, ACM SIGPLAN Notices, v.21 n.7, p.99-108, July 1986
	25	Kenneth Wade Kennedy, Jr., Global flow analysis and register allocation for simple code structures, 1971
	26	James R. Larus , Paul N. Hilfinger, Register allocation in the SPUR Lisp compiler, ACM SIGPLAN Notices, v.21 n.7, p.255-263, July 1986
	27	~LAVROV, S.S. 1961. Store economy in closed operator schemes. J. Comput. Math. Math. Phys. ~1, 4, 687-701. (English translation in U.S.S.R. Comput. Math. Math. Phys. 1, 3 (1962), ~810-828.
	28	David W. Matula , Leland L. Beck, Smallest-last ordering and clustering and graph coloring algorithms, Journal of the ACM (JACM), v.30 n.3, p.417-427, July 1983 [doi>10.1145/2402.322385]
	29	Brian R. Nickerson, Graph coloring register allocation for processors with multi-register operands, ACM SIGPLAN Notices, v.25 n.6, p.40-52, Jun. 1990
	30	~SCHWARTZ, J.T. 1973. On programming: An interim report on the SETL project, Installment ~II: The SETL language and examples of its use. Tech. Rep., Courant Inst., New York Univ., ~New York, Oct.
	31	~SPEC. 1990. Release 1.2, Standards Performance Evaluation Corp., Freemont, Calif., Sept.
	32	Mark N. Wegman , F. Kenneth Zadeck, Constant propagation with conditional branches, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.181-210, April 1991 [doi>10.1145/103135.103136]

CITED BY 79

	Sreeranga P. Rajan , Masahiro Fujita , Ashok Sudarsanam , Sharad Malik, Development of an optimizing compiler for a Fujitsu fixed-point digital signal processor, Proceedings of the seventh international workshop on Hardware/software codesign, p.2-6, March 1999, Rome, Italy
	Suhyun Kim , Soo-Mook Moon , Jinpyo Park , Kemal Ebcioglu, Unroll-Based Copy Elimination for Enhanced Pipeline Scheduling, IEEE Transactions on Computers, v.51 n.9, p.977-994, September 2002
	Keith D. Cooper , Philip J. Schielke , Devika Subramanian, Optimizing for reduced code space using genetic algorithms, ACM SIGPLAN Notices, v.34 n.7, p.1-9, July 1999
	Omri Traub , Glenn Holloway , Michael D. Smith, Quality and speed in linear-scan register allocation, ACM SIGPLAN Notices, v.33 n.5, p.142-151, May 1998
	Bernhard Scholz , Erik Eckstein, Register allocation for irregular architectures, ACM SIGPLAN Notices, v.37 n.7, July 2002
	Lal George , Andrew W. Appel, Iterated register coalescing, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.208-218, January 21-24, 1996, St. Petersburg Beach, Florida, United States
	Daniel Luna , Mikael Pettersson , Konstantinos Sagonas, Efficiently compiling a functional language on AMD64: the HiPE experience, Proceedings of the 7th ACM SIGPLAN international conference on Principles and practice of declarative programming, p.176-186, July 11-13, 2005, Lisbon, Portugal
	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
	Keith I. Farkas , Paul Chow , Norman P. Jouppi , Zvonko Vranesic, The multicluster architecture: reducing cycle time through partitioning, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.149-159, December 01-03, 1997, Research Triangle Park, North Carolina, United States
	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
	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
	Sriraman Tallam , Rajiv Gupta, Bitwidth aware global register allocation, ACM SIGPLAN Notices, v.38 n.1, p.85-96, January 2003
	James D. Shuler , Henry R. Bauer, III, Look-ahead allocation in the presence of branches, Proceedings of the 1997 ACM symposium on Applied computing, p.504-508, April 1997, San Jose, California, United States
	Jinpyo Park , Je-Hyung Lee , Soo-Mook Moon, Register Allocation for Banked Register File, ACM SIGPLAN Notices, v.36 n.8, p.39-47, Aug. 2001
	Ashok Sudarsanam , Stan Liao , Srinivas Devadas, Analysis and evaluation of address arithmetic capabilities in custom DSP architectures, Proceedings of the 34th annual conference on Design automation, p.287-292, June 09-13, 1997, Anaheim, California, United States
	Keith I. Farkas , Paul Chow , Norman P. Jouppi , Zvonko Vranesic, The Multicluster Architecture: Reducing Processor Cycle Time Through Partitioning, International Journal of Parallel Programming, v.27 n.5, p.327-356, Oct. 1999
	Kameswari V. Garigipati , Cindy Norris, Evaluating the use of profiling by a region-based register allocator, Proceedings of the 2002 ACM symposium on Applied computing, March 11-14, 2002, Madrid, Spain
	Keith D. Cooper , L. Taylor Simpson , Christopher A. Vick, Operator strength reduction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.5, p.603-625, September 2001
	Josep Llosa , Mateo Valero , Eduard Ayguadé, Heuristics for register-constrained software pipelining, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.250-261, December 02-04, 1996, Paris, France
	Erik Johansson , Mikael Pettersson , Konstantinos Sagonas, A high performance Erlang system, Proceedings of the 2nd ACM SIGPLAN international conference on Principles and practice of declarative programming, p.32-43, September 20-23, 2000, Montreal, Quebec, Canada
	John Lu , Keith D. Cooper, Register promotion in C programs, ACM SIGPLAN Notices, v.32 n.5, p.308-319, May 1997
	Xavier Leroy, Bytecode verification on Java smart cards, Software—Practice & Experience, v.32 n.4, p.319-340, 10 April 2002
	Wen-Tsong Shiue, Retargetable compilation for low power, Proceedings of the ninth international symposium on Hardware/software codesign, p.254-259, April 2001, Copenhagen, Denmark
	Javier Zalamea , Josep Llosa , Eduard Ayguadé , Mateo Valero, Improved spill code generation for software pipelined loops, ACM SIGPLAN Notices, v.35 n.5, p.134-144, May 2000
	Andrew W. Appel , Lal George, Optimal spilling for CISC machines with few registers, ACM SIGPLAN Notices, v.36 n.5, p.243-253, May 2001
	Ashok Sudarsanam , Sharad Malik , Masahiro Fujita, A retargetable compilation methodology for embedded digital signal processors using a machine-dependent code optimizaton library, Readings in hardware/software co-design, Kluwer Academic Publishers, Norwell, MA, 2001
	William C. Kreahling , Cindy Norris, Profile assisted register allocation, Proceedings of the 2000 ACM symposium on Applied computing, p.774-781, March 2000, Como, Italy
	Liu Yang , Sun Chan , G. R. Gao , Roy Ju , Guei-Yuan Lueh , Zhaoqing Zhang, Inter-procedural stacked register allocation for itanium® like architecture, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA
	Changqing Fu , Kent Wilken, A faster optimal register allocator, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
	Thomas Zeitlhofer , Bernhard Wess, List-coloring of interval graphs with application to register assignment for heterogeneous register-set architectures, Signal Processing, v.83 n.7, p.1411-1425, July 2003
	Suhyun Kim , Soo-Mook Moon , Jinpyo Park , Kemal Ebcioğlu, Unroll-based register coalescing, Proceedings of the 14th international conference on Supercomputing, p.296-305, May 08-11, 2000, Santa Fe, New Mexico, United States
	Jinpyo Park , Soo-Mook Moon, Optimistic register coalescing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.26 n.4, p.735-765, July 2004
	Kun Zhang , Tao Zhang , Santosh Pande, Binary translation to improve energy efficiency through post-pass register re-allocation, Proceedings of the 4th ACM international conference on Embedded software, September 27-29, 2004, Pisa, Italy
	Christian W. Probst , Andreas Gal , Michael Franz, Average case vs. worst case: margins of safety in system design, Proceedings of the 2005 workshop on New security paradigms, September 20-23, 2005, Lake Arrowhead, California
	Daniel Luna , Mikael Pettersson , Konstantinos Sagonas, HiPE on AMD64, Proceedings of the 2004 ACM SIGPLAN workshop on Erlang, p.38-47, September 22-22, 2004, Snowbird, Utah, USA
	Michael D. Smith , Norman Ramsey , Glenn Holloway, A generalized algorithm for graph-coloring register allocation, ACM SIGPLAN Notices, v.39 n.6, May 2004
	Sathyanarayanan Thammanur , Santosh Pande, A fast, memory-efficient register allocation framework for embedded systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.26 n.6, p.938-974, November 2004
	Akira Koseki , Hideaki Komatsu , Toshio Nakatani, Preference-directed graph coloring, ACM SIGPLAN Notices, v.37 n.5, May 2002
	Atsushi Ohori, Register allocation by proof transformation, Science of Computer Programming, v.50 n.1-3, p.161-187, March 2004
	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
	Jay Bharadwaj , William Y. Chen , Weihaw Chuang , Gerolf Hoflehner , Kishore Menezes , Kalyan Muthukumar , Jim Pierce, The Intel IA-64 Compiler Code Generator, IEEE Micro, v.20 n.5, p.44-53, September 2000
	T. Suganuma , T. Ogasawara , K. Kawachiya , M. Takeuchi , K. Ishizaki , A. Koseki , T. Inagaki , T. Yasue , M. Kawahito , T. Onodera , H. Komatsu , T. Nakatani, Evolution of a java just-in-time compiler for IA-32 platforms, IBM Journal of Research and Development, v.48 n.5/6, p.767-795, September/November 2004
	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
	Max Hailperin, Comparing conservative coalescing criteria, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.3, p.571-582, May 2005
	Javier Zalamea , Josep Llosa , Eduard Ayguadé , Mateo Valero, Register Constrained Modulo Scheduling, IEEE Transactions on Parallel and Distributed Systems, v.15 n.5, p.417-430, May 2004
	Yoonseo Choi , Hwansoo Han, Optimal register reassignment for register stack overflow minimization, ACM Transactions on Architecture and Code Optimization (TACO), v.3 n.1, p.90-114, March 2006
	Jian Wang , Andreas Krall , M. Anton Ertl , Christine Eisenbeis, Software pipelining with register allocation and spilling, Proceedings of the 27th annual international symposium on Microarchitecture, p.95-99, November 30-December 02, 1994, San Jose, California, United States
	Xiaotong Zhuang , Santosh Pande, Parallelizing load/stores on dual-bank memory embedded processors, ACM Transactions on Embedded Computing Systems (TECS), v.5 n.3, p.613-657, August 2006
	Michael Paleczny , Christopher Vick , Cliff Click, The java hotspot^TM server compiler, Proceedings of the Java^TM Virtual Machine Research and Technology Symposium on Java^TM Virtual Machine Research and Technology Symposium, p.1-1, April 23-24, 2001, Monterey, California
	David Ryan Koes , Seth Copen Goldstein, A global progressive register allocator, ACM SIGPLAN Notices, v.41 n.6, June 2006
	Matthias Jacob , Keith H. Randall, Cross-Architectural Performance Portability of a Java Virtual Machine Implementation, Proceedings of the 2nd Java™ Virtual Machine Research and Technology Symposium, p.79-89, August 01-02, 2002
	Philip Brisk , Ajay Kumar Verma , Paolo Ienne, An optimistic and conservative register assignment heuristic for chordal graphs, Proceedings of the 2007 international conference on Compilers, architecture, and synthesis for embedded systems, September 30-October 03, 2007, Salzburg, Austria
	Philip Brisk , Ajay K. Verma , Paolo Ienne, Optimal polynomial-time interprocedural register allocation for high-level synthesis and ASIP design, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
	Ivan D. Baev , Richard E. Hank , David H. Gross, Prematerialization: reducing register pressure for free, Proceedings of the 15th international conference on Parallel architectures and compilation techniques, September 16-20, 2006, Seattle, Washington, USA
	Weijia Li , Youtao Zhang , Jun Yang , Jiang Zheng, UCC: update-conscious compilation for energy efficiency in wireless sensor networks, ACM SIGPLAN Notices, v.42 n.6, June 2007
	Bjorn De Sutter , Paul Coene , Tom Vander Aa , Bingfeng Mei, Placement-and-routing-based register allocation for coarse-grained reconfigurable arrays, ACM SIGPLAN Notices, v.43 n.7, July 2008
	Wolfram Amme , Jeffery von Ronne , Michael Franz, SSA-based mobile code: Implementation and empirical evaluation, ACM Transactions on Architecture and Code Optimization (TACO), v.4 n.2, p.13-es, June 2007
	Yunhe Shi , Kevin Casey , M. Anton Ertl , David Gregg, Virtual machine showdown: Stack versus registers, ACM Transactions on Architecture and Code Optimization (TACO), v.4 n.4, p.1-36, January 2008
	Christopher Lupo , Kent D. Wilken, Post Register Allocation Spill Code Optimization, Proceedings of the International Symposium on Code Generation and Optimization, p.245-255, March 26-29, 2006
	Keith D. Cooper , Anshuman Dasgupta, Tailoring Graph-coloring Register Allocation For Runtime Compilation, Proceedings of the International Symposium on Code Generation and Optimization, p.39-49, March 26-29, 2006
	Tao Zhang , Xiaotong Zhuang , Santosh Pande, Compiler Optimizations to Reduce Security Overhead, Proceedings of the International Symposium on Code Generation and Optimization, p.346-357, March 26-29, 2006
	Jongeun Lee , Aviral Shrivastava, Compiler-managed register file protection for energy-efficient soft error reduction, Proceedings of the 2009 Conference on Asia and South Pacific Design Automation, January 19-22, 2009, Yokohama, Japan
	Tao Zhang , Xiaotong Zhuang , Santosh Pande, Building Intrusion-Tolerant Secure Software, Proceedings of the international symposium on Code generation and optimization, p.255-266, March 20-23, 2005
	David Koes , Seth Copen Goldstein, A Progressive Register Allocator for Irregular Architectures, Proceedings of the international symposium on Code generation and optimization, p.269-280, March 20-23, 2005
	Florent Bouchez , Alain Darte , Fabrice Rastello, On the Complexity of Register Coalescing, Proceedings of the International Symposium on Code Generation and Optimization, p.102-114, March 11-14, 2007
	Olivier Morandi , Fulvio Risso , Silvio Valenti , Paolo Veglia, Design and implementation of a framework for creating portable and efficient packet-processing applications, Proceedings of the 7th ACM international conference on Embedded software, October 19-24, 2008, Atlanta, GA, USA
	Sebastian Hack , Gerhard Goos, Copy coalescing by graph recoloring, ACM SIGPLAN Notices, v.43 n.6, June 2008
	Thomas Kotzmann , Christian Wimmer , Hanspeter Mössenböck , Thomas Rodriguez , Kenneth Russell , David Cox, Design of the Java HotSpot™ client compiler for Java 6, ACM Transactions on Architecture and Code Optimization (TACO), v.5 n.1, p.1-32, May 2008
	Fang Lu , Lei Wang , Xiaobing Feng , Zhiyuan Li , Zhaoqing Zhang, Exploiting idle register classes for fast spill destination, Proceedings of the 22nd annual international conference on Supercomputing, June 07-12, 2008, Island of Kos, Greece
	Li Wang , Xuejun Yang , Jingling Xue , Yu Deng , Xiaobo Yan , Tao Tang , Quan Hoang Nguyen, Optimizing scientific application loops on stream processors, ACM SIGPLAN Notices, v.43 n.7, July 2008
	Florent Bouchez , Alain Darte , Fabrice Rastello, Advanced conservative and optimistic register coalescing, Proceedings of the 2008 international conference on Compilers, architectures and synthesis for embedded systems, October 19-24, 2008, Atlanta, GA, USA
	Xuejun Yang , Li Wang , Jingling Xue , Yu Deng , Ying Zhang, Comparability graph coloring for optimizing utilization of stream register files in stream processors, Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, February 14-18, 2009, Raleigh, NC, USA
	Preston Briggs, Register allocation, Encyclopedia of Computer Science, 4th edition, John Wiley and Sons Ltd., Chichester, 2003
	M. Sh. Levin, Combinatorial optimization in system configuration design, Automation and Remote Control, v.70 n.3, p.519-561, March 2009
	Ioana Cutcutache , Weng-Fai Wong, Fast, frequency-based, integrated register allocation and instruction scheduling, Software—Practice & Experience, v.38 n.11, p.1105-1126, September 2008
	Benoit Boissinot , Alain Darte , Fabrice Rastello , Benoit Dupont de Dinechin , Christophe Guillon, Revisiting Out-of-SSA Translation for Correctness, Code Quality and Efficiency, Proceedings of the 2009 International Symposium on Code Generation and Optimization, p.114-125, March 22-25, 2009
	Ivan D. Baev, Techniques for Region-Based Register Allocation, Proceedings of the 2009 International Symposium on Code Generation and Optimization, p.147-156, March 22-25, 2009
	David Ryan Koes , Seth Copen Goldstein, Register allocation deconstructed, Proceedings of th 12th International Workshop on Software and Compilers for Embedded Systems, April 23-24, 2009, Nice, France
	Xue-Jun Yang , Yu Deng , Li Wang , Xiao-Bo Yan , Jing Du , Ying Zhang , Gui-Bin Wang , Tao Tang, SRF coloring: stream register file allocation via graph coloring, Journal of Computer Science and Technology, v.24 n.1, p.152-164, January 2009

INDEX TERMS

Primary Classification:
D. Software
D.3 PROGRAMMING LANGUAGES
D.3.4 Processors
Subjects: Optimization

General Terms:
Algorithms, Languages

Keywords:
code generation, graph coloring, register allocation

REVIEW

"Rajiv Gupta : Reviewer"

The authors identify problems with the Chaitin-style graph coloring register allocator and propose solutions to these problems.The first problem is unnecessary spilling of values. Chaitin's allocator continues to spill valu more...

Collaborative Colleagues:

Preston Briggs: colleagues

Keith D. Cooper: colleagues

Linda Torczon: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player