Linear scan register allocation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Linear scan register allocation

Full text

Pdf (231 KB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 21 , Issue 5 (September 1999) table of contents

Pages: 895 - 913

Year of Publication: 1999

ISSN:0164-0925

Authors

Massimiliano Poletto	Massachusetts Institute of Technology, Cambridge
Vivek Sarkar	IBM Thomas J. kWatson Research Center

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 24, Downloads (12 Months): 168, Citation Count: 59

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

Warning: The download time has expired please click on the item to try again.

ABSTRACT

We describe a new algorithm for fast global register allocation called linear scan. This algorithm is not based on graph coloring, but allocates registers to variables in a single linear-time scan of the variables' live ranges. The linear scan algorithm is considerably faster than algorithms based on graph coloring, is simple to implement, and results in code that is almost as efficient as that obtained using more complex and time-consuming register allocators based on graph coloring. The algorithm is of interest in applications where compile time is a concern, such as dynamic compilation systems, “just-in-time” compilers, and interactive development environments.

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 , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	2	Saman P. Amarasinghe , Jennifer-Ann M. Anderson , Monica S. Lam , Amy W. Lim, An Overview of a Compiler for Scalable Parallel Machines, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.253-272, August 12-14, 1993
	3	Marc Auslander , Martin Hopkins, An overview of the PL.8 compiler, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.22-31, June 23-25, 1982, Boston, Massachusetts, United States
	4	Belady, L. A. 1966. A study of replacement algorithms for a virtual storage computer. IBM Systems Journal 5, 2, 78-101.
	5	Blickstein, D., Craig, P., Davidson, C., Faiman, R., Glossop, K., Grove, R., Hobbs, S., and Noyce, W. 1992. The GEM optimizing compiler system. Digital Equipment Corporation Technical Journal 4, 4, 121-135.
	6	Preston Briggs , Keith D. Cooper , Linda Torczon, Improvements to graph coloring register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.428-455, May 1994 [doi>10.1145/177492.177575]
	7	Chaitin, G. J., Auslander, M. A., Chandra, A. K., Cocke, J., Hopkins, M. E., and Mark-stein, P. W. 1981. Register allocation via coloring. Computer Languages 6, 47-57.
	8	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	9	R. Cytron , J. Ferrante , B. K. Rosen , M. N. Wegman , F. K. Zadeck, An efficient method of computing static single assignment form, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.25-35, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75280]
	10	Christopher W. Fraser , David R. Hanson, A Retargetable C Compiler: Design and Implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
	11	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]
	12	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]
	13	Wei-Chung Hsu , Charles N. Fisher , James R. Goodman, On the Minimization of Loads/Stores in Local Register Allocation, IEEE Transactions on Software Engineering, v.15 n.10, p.1252-1260, October 1989 [doi>10.1109/TSE.1989.559775]
	14	Rajeev Motwani , Krishna V. Palem , Vivek Sarkar , Salem Reyen, Combining Register Allocation and Instruction Scheduling, Stanford University, Stanford, CA, 1995
	15	Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
	16	Massimiliano Poletto , Dawson R. Engler , M. Frans Kaashoek, tcc: a system for fast, flexible, and high-level dynamic code generation, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.109-121, June 16-18, 1997, Las Vegas, Nevada, United States
	17	Massimiliano Poletto , Wilson C. Hsieh , Dawson R. Engler , M. Frans Kaashoek, C and tcc: a language and compiler for dynamic code generation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.2, p.324-369, March 1999 [doi>10.1145/316686.316697]
	18	Smith, M. 1996. Extending SUIF for machine-dependent optimizations. In Proceedings of the First SUIF Compiler Workshop. Stanford, CA, 14-25. http://www.eecs.harvard.edu/machsuif.
	19	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

CITED BY 59

	George Almási , David Padua, MaJIC: compiling MATLAB for speed and responsiveness, ACM SIGPLAN Notices, v.37 n.5, May 2002
	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
	Michael G. Burke , Jong-Deok Choi , Stephen Fink , David Grove , Michael Hind , Vivek Sarkar , Mauricio J. Serrano , V. C. Sreedhar , Harini Srinivasan , John Whaley, The Jalapeño dynamic optimizing compiler for Java, Proceedings of the ACM 1999 conference on Java Grande, p.129-141, June 12-14, 1999, San Francisco, California, United States
	Matthew Arnold , Stephen Fink , David Grove , Michael Hind , Peter F. Sweeney, Adaptive optimization in the Jalapeño JVM, ACM SIGPLAN Notices, v.35 n.10, p.47-65, Oct. 2000
	Matthew Arnold , Stephen Fink , David Grove , Michael Hind , Peter F. Sweeney, Adaptive optimization in the Jalapeño JVM (poster session), Addendum to the 2000 proceedings of the conference on Object-oriented programming, systems, languages, and applications (Addendum), p.125-126, January 2000, Minneapolis, Minnesota, United States
	Kazuaki Ishizaki , Mikio Takeuchi , Kiyokuni Kawachiya , Toshio Suganuma , Osamu Gohda , Tatsushi Inagaki , Akira Koseki , Kazunori Ogata , Motohiro Kawahito , Toshiaki Yasue , Takeshi Ogasawara , Tamiya Onodera , Hideaki Komatsu , Toshio Nakatani, Effectiveness of cross-platform optimizations for a java just-in-time compiler, ACM SIGPLAN Notices, v.38 n.11, November 2003
	Bowen Alpern , Anthony Cocchi , Stephen Fink , David Grove, Efficient implementation of Java interfaces: Invokeinterface considered harmless, ACM SIGPLAN Notices, v.36 n.11, p.108-124, 11/01/2001
	Massimiliano Poletto , Wilson C. Hsieh , Dawson R. Engler , M. Frans Kaashoek, C and tcc: a language and compiler for dynamic code generation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.2, p.324-369, March 1999
	Pramod G. Joisha , Prithviraj Banerjee, Static array storage optimization in MATLAB, ACM SIGPLAN Notices, v.38 n.5, May 2003
	Dietmar Ebner , Bernhard Scholz , Andreas Krall, Progressive spill code placement, Proceedings of the 2009 international conference on Compilers, architecture, and synthesis for embedded systems, October 11-16, 2009, Grenoble, France
	Jeffery von Ronne , Andreas Hartmann , Wolfram Amme , Michael Franz, Efficient online optimization by utilizing offline analysis and the safeTSA representation, Proceedings of the inaugural conference on the Principles and Practice of programming, 2002 and Proceedings of the second workshop on Intermediate representation engineering for virtual machines, 2002, June 13-14, 2002, Dublin, Ireland
	Wolfram Amme , Niall Dalton , Jeffery von Ronne , Michael Franz, SafeTSA: a type safe and referentially secure mobile-code representation based on static single assignment form, ACM SIGPLAN Notices, v.36 n.5, p.137-147, May 2001
	Lukasz Strozek , David Brooks, Efficient architectures through application clustering and architectural heterogeneity, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea
	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
	B. Alpern , C. R. Attanasio , J. J. Barton , M. G. Burke , P. Cheng , J.-D. Choi , A. Cocchi , S. J. Fink , D. Grove , M. Hind , S. F. Hummel , D. Lieber , V. Litvinov , M. F. Mergen , T. Ngo , J. R. Russell , V. Sarkar , M. J. Serrano , J. C. Shepherd , S. E. Smith , V. C. Sreedhar , H. Srinivasan , J. Whaley, The Jalapeño virtual machine, IBM Systems Journal, v.39 n.1, p.211-238, January 2000
	T. Suganuma , T. Ogasawara , M. Takeuchi , T. Yasue , M. Kawahito , K. Ishizaki , H. Komatsu , T. Nakatani, Overview of the IBM Java just-in-time compiler, IBM Systems Journal, v.39 n.1, p.175-193, January 2000
	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
	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
	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
	David Zaretsky , Gaurav Mittal , Xiaoyong Tang , Prith Banerjee, Evaluation of scheduling and allocation algorithms while mapping assembly code onto FPGAs, Proceedings of the 14th ACM Great Lakes symposium on VLSI, April 26-28, 2004, Boston, MA, USA
	Eijiro Sumii, MinCaml: a simple and efficient compiler for a minimal functional language, Proceedings of the 2005 workshop on Functional and declarative programming in education, September 25-25, 2005, Tallinn, Estonia
	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
	Chi-Keung Luk , Robert Cohn , Robert Muth , Harish Patil , Artur Klauser , Geoff Lowney , Steven Wallace , Vijay Janapa Reddi , Kim Hazelwood, Pin: building customized program analysis tools with dynamic instrumentation, ACM SIGPLAN Notices, v.40 n.6, June 2005
	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
	Rajiv A. Ravindran , Robert M. Senger , Eric D. Marsman , Ganesh S. Dasika , Matthew R. Guthaus , Scott A. Mahlke , Richard B. Brown, Partitioning Variables across Register Windows to Reduce Spill Code in a Low-Power Processor, IEEE Transactions on Computers, v.54 n.8, p.998-1012, August 2005
	Sid-Ahmed-Ali Touati, Register saturation in instruction level parallelism, International Journal of Parallel Programming, v.33 n.4, p.393-449, August 2005
	B. Alpern , S. Augart , S. M. Blackburn , M. Butrico , A. Cocchi , P. Cheng , J. Dolby , S. Fink , D. Grove , M. Hind , K. S. McKinley , M. Mergen , J. E. B. Moss , T. Ngo , V. Sarkar, The Jikes research virtual machine project: building an open-source research community, IBM Systems Journal, v.44 n.2, p.399-417, January 2005
	Han Lee , Daniel von Dincklage , Amer Diwan , J. Eliot B. Moss, Understanding the behavior of compiler optimizations, Software—Practice & Experience, v.36 n.8, p.835-844, July 2006
	David Ryan Koes , Seth Copen Goldstein, A global progressive register allocator, ACM SIGPLAN Notices, v.41 n.6, June 2006
	Jason Cong , Guoling Han , Zhiru Zhang, Architecture and compiler optimizations for data bandwidth improvement in configurable processors, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.14 n.9, p.986-997, September 2006
	Hai Lin , Yunsi Fei, Utilizing custom registers in application-specific instruction set processors for register spills elimination, Proceedings of the 17th great lakes symposium on Great lakes symposium on VLSI, March 11-13, 2007, Stresa-Lago Maggiore, Italy
	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
	Bowen Alpern , Maria Butrico , Anthony Cocchi , Julian Dolby , Stephen J. Fink , David Grove , Ton Ngo, Experiences Porting the Jikes RVM to Linux/IA32, Proceedings of the 2nd Java™ Virtual Machine Research and Technology Symposium, p.51-64, August 01-02, 2002
	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
	Min Zhao , Bruce R. Childers , Mary Lou Soffa, An approach toward profit-driven optimization, ACM Transactions on Architecture and Code Optimization (TACO), v.3 n.3, p.231-262, September 2006
	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
	Florent Bouchez , Alain Darte , Fabrice Rastello, On the complexity of spill everywhere under SSA form, ACM SIGPLAN Notices, v.42 n.7, July 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
	J. Cong , Guoling Han , Zhiru Zhang, Architecture and compilation for data bandwidth improvement in configurable embedded processors, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.263-270, November 06-10, 2005, San Jose, CA
	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
	Min Zhao , Bruce R. Childers , Mary Lou Soffa, A Model-Based Framework: An Approach for Profit-Driven Optimization, Proceedings of the international symposium on Code generation and optimization, p.317-327, March 20-23, 2005
	A. E. Doroshenko , D. V. Ragozin, Using Graph Models in Retargetable Optimizing Compilers for Microprocessors with VLIW Architectures, Cybernetics and Systems Analysis, v.39 n.2, p.192-211, March-April 2003
	Suranjan Pramanik , Shambhu J. Upadhyaya, RABIT: A New Framework for Runtime Emulation and Binary Translation, Proceedings of the 37th annual symposium on Simulation, p.213, April 18-22, 2004
	Fernando Magno Quintão Pereira , Jens Palsberg, Register allocation by puzzle solving, 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
	Byung-Sun Yang , Junpyo Lee , SeungIl Lee , Seongbae Park , Yoo C. Chung , Suhyun Kim , Kemal Ebcioglu , Erik Altman , Soo-Mook Moon, Efficient Register Mapping and Allocation in LaTTe, an Open-Source Java Just-in-Time Compiler, IEEE Transactions on Parallel and Distributed Systems, v.18 n.1, p.57-69, January 2007
	Masataka Sassa , Yo Ito , Masaki Kohama, Comparison and evaluation of back-translation algorithms for static single assignment forms, Computer Languages, Systems and Structures, v.35 n.2, p.173-195, July, 2009
	Hitoshi Oi, Local variable access behavior of a hardware-translation based Java virtual machine, Journal of Systems and Software, v.81 n.11, p.2059-2068, November, 2008
	Lukasz Strozek , David Brooks, Energy- and area-efficient architectures through application clustering and architectural heterogeneity, ACM Transactions on Architecture and Code Optimization (TACO), v.6 n.1, p.1-31, 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
	Michele Tartara , Simone Campanoni , Giovanni Agosta , Stefano Crespi Reghizzi, Just-In-Time compilation on ARM processors, Proceedings of the 4th workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems, p.70-73, July 06-06, 2009, Genova, Italy
	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
	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
	Heiko Falk, WCET-aware register allocation based on graph coloring, Proceedings of the 46th Annual Design Automation Conference, July 26-31, 2009, San Francisco, California
	Scott S. Sirowy , Bailey Miller , Frank Vahid, Portable SystemC-on-a-chip, Proceedings of the 7th IEEE/ACM international conference on Hardware/software codesign and system synthesis, October 11-16, 2009, Grenoble, France
	Weijia Li , Youtao Zhang , Jun Yang , Jiang Zheng, Towards update-conscious compilation for energy-efficient code dissemination in WSNs, ACM Transactions on Architecture and Code Optimization (TACO), v.6 n.4, p.1-33, October 2009