|
 ABSTRACT
In a previous paper we reported the successful use of graph coloring techniques for doing global register allocation in an experimental PL/I optimizing compiler. When the compiler cannot color the register conflict graph with a number of colors equal to the number of available machine registers, it must add code to spill and reload registers to and from storage. Previously the compiler produced spill code whose quality sometimes left much to be desired, and the ad hoe techniques used took considerable amounts of compile time. We have now discovered how to extend the graph coloring approach so that it naturally solves the spilling problem. Spill decisions are now made on the basis of the register conflict graph and cost estimates of the value of keeping the result of a computation in a register rather than in storage. This new approach produces better object code and takes much less compile time.
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
|
|
| |
2
|
"The history of language processor technology in IBM," F.E. Allen, IBM Journal of Research and Development 25 (1981), pp. 535-548.
|
| |
3
|
"Measurement of code improvement algorithms," J. Cocke, P.W. Markstein, Information Processing 80, S.H. Lavington (ed.), North-Holland, Amsterdam, 1980, pp. 221-228.
|
| |
4
|
"Register allocation via coloring," G.J. Chaitin, M.A. Auslander, A.K. Chandra, J. Cocke, M.E. Hopkins, P.W. Markstein, Computer Languages 6 (1981), pp. 47-57.
|
| |
5
|
"Optimization of range checking," V. Markstein, J. Cocke, P. Markstein, this Proceedings.
|
| |
6
|
"Higher Level Programming: Introduction to the Use of the Set-Theoretic Programming Language SETL," R.B.K. Dewar, E. Schonberg, J.T. Schwartz, Courant Institute, New York University, 1981.
|
CITED BY 223
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Yumin Zhang , Xiaobo (Sharon) Hu , Danny Z. Chen, Global register allocation for minimizing energy consumption, Proceedings of the 1999 international symposium on Low power electronics and design, p.100-102, August 16-17, 1999, San Diego, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C. Eisenbeis , W. Jalby , A. Lichnewsky, Squeezing more CPU performance out of a Cray-2 by Vector block scheduling, Proceedings of the 1988 ACM/IEEE conference on Supercomputing, p.237-246, November 12-17, 1988, Orlando, Florida, United States
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Tokuzo Kiyohara , Scott Mahlke , William Chen , Roger Bringmann , Richard Hank , Sadun Anik , Wen-Mei Hwu, Register connection: a new approach to adding registers into instruction set architectures, ACM SIGARCH Computer Architecture News, v.21 n.2, p.247-256, May 1993
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Clifford Liem , Trevor May , Pierre Paulin, Register assignment through resource classification for ASIP microcode generation, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.397-402, November 06-10, 1994, San Jose, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Dirk Lanneer , Marco Cornero , Gert Goossens , Hugo De Man, Data routing: a paradigm for efficient data-path synthesis and code generation, Proceedings of the 7th international symposium on High-level synthesis, p.17-22, May 18-20, 1994, Niagra-on-the-Lake, Ontario, Canada
|
|
|
|
|
|
Akira Koseki , Hideaki Komatsu , Yoshiaki Fukazawa, A register allocation technique using guarded PDG, Proceedings of the 10th international conference on Supercomputing, p.270-277, May 25-28, 1996, Philadelphia, Pennsylvania, United States
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ana Azevedo , Alex Nicolau , Joe Hummel, Java annotation-aware just-in-time (AJIT) complilation system, Proceedings of the ACM 1999 conference on Java Grande, p.142-151, June 12-14, 1999, San Francisco, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Pohua P. Chang , Scott A. Mahlke , William Y. Chen , Nancy J. Warter , Wen-mei W. Hwu, IMPACT: an architectural framework for multiple-instruction-issue processors, 25 years of the international symposia on Computer architecture (selected papers), p.408-417, June 27-July 02, 1998, Barcelona, Spain
|
|
|
David M. Gillies , Dz-ching Roy Ju , Richard Johnson , Michael Schlansker, Global predicate analysis and its application to register allocation, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.114-125, December 02-04, 1996, Paris, France
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Benjamin Welch , Shobhit Kanaujia , Adarsh Seetharam , Deepaksrivats Thirumalai , Alexander G. Dean, Extending STI for demanding hard-real-time systems, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
R. R. Kessler , J. C. Peterson , H. Carr , G. P. Duggan , J. Knell, EPIC - a retargetable, highly optimizing Lisp compiler, ACM SIGPLAN Notices, v.21 n.7, p.118-130, July 1986
|
|
|
|
|
|
|
|
|
Richard E. Hank , Wen-Mei W. Hwu , B. Ramakrishna Rau, Region-based compilation: an introduction and motivation, Proceedings of the 28th annual international symposium on Microarchitecture, p.158-168, November 29-December 01, 1995, Ann Arbor, Michigan, United States
|
|
|
|
|
|
B. K. Rosen , M. N. Wegman , F. K. Zadeck, Global value numbers and redundant computations, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.12-27, January 10-13, 1988, San Diego, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Thomas S. Brasier , Philip H. Sweany , Steven J. Beaty , Steve Carr, CRAIG: a practical framework for combining instruction scheduling and register assignment, Proceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques, p.11-18, June 27-29, 1995, Limassol, Cyprus
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Siddhartha Shivshankar , Sunil Vangara , Alexander G. Dean, Balancing register pressure and context-switching delays in ASTI systems, Proceedings of the 2005 international conference on Compilers, architectures and synthesis for embedded systems, September 24-27, 2005, San Francisco, California, USA
|
|
|
|
|
|
|
|
|
Paul Morgan , Richard Taylor , Japheth Hossell , George Bruce , Barry O'Rourke, Automated data cache placement for embedded VLIW ASIPs, Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 19-21, 2005, Jersey City, NJ, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Gerolf Hoflehner , Knud Kirkegaard , Rod Skinner , Daniel Lavery , Yong-fong Lee , Wei Li, Compiler Optimizations for Transaction Processing Workloads on Itanium® Linux Systems, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.294-303, December 04-08, 2004, Portland, Oregon
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Rajiv A. Ravindran , Pracheeti D. Nagarkar , Ganesh S. Dasika , Eric D. Marsman , Robert M. Senger , Scott A. Mahlke , Richard B. Brown, Compiler Managed Dynamic Instruction Placement in a Low-Power Code Cache, Proceedings of the international symposium on Code generation and optimization, p.179-190, March 20-23, 2005
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
D.3