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

ABSTRACT

Register allocation is always a trade-off between live-range splitting and coalescing. Live-range splitting generally leads to less spilling at the cost of inserting shuffle code. Coalescing removes shuffle code while potentially raising the register demand and causing spilling.

Recent research showed that the live-range splitting of the SSA form's Æ-functions leads to chordal interference graphs. This improves upon two long-standing inconveniences of graph coloring register allocation: First, chordal graphs are optimally colorable in quadratic time. Second, the number of colors needed to color the graph is equal to the maximal register pressure in the program. However, the inserted shuffle code incurred by the Æ-functions can slow down the program severely. Hence, to make such an approach work in practice, a coalescing technique is needed that removes most of the shuffle code without causing further spilling.

In this paper, we present a coalescing technique designed for, but not limited to, SSA-form register allocation. We exploit that a valid coloring can be easily obtained by an SSA-based register allocator. This initial coloring is then improved by recoloring the interference graph and assigning shuffle-code related nodes the same color. Thereby, we always keep the coloring of the graph valid. Hence, the coalescing is safe, i. e. no spill code will be caused by coalescing.

Comparing to iterated register coalescing, the state of the art in safe coalescing, our method is able to remove 22.5% of the costs and 44.3% of the copies iterated coalescing left over. The best solution possible, found by a colaescer using integer linear programming (ILP), was 35.9% of the costs and 51.9% of the copies iterated coalescing left over. The runtime of programs compiled with our heuristic matches that of the programs compiled with the ILP technique.

REFERENCES

• 1: 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
• 2: 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 19th International Workshop on Languages and Compilers for Parallel Computing (LCPC'06), New Orleans, USA, Nov 2006.
• 3: 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 [doi>10.1109/CGO.2007.26]
• 4: 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]
• 5: 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]
• 6: Philip Brisk, Foad Dabiri, Roozbeh Jafari, and Majid Sarrafzadeh. Optimal Register Sharing for High-Level Synthesis of SSA Form Programs. IEEE Trans. on CAD of Integrated Circuits and Systems, 25(5):772--779, 2006.
• 7: G. J. Chaitin, M. A. Auslander, A. K. Chandra, J. Cocke, M. E. Hopkins, and P. W. Markstein. Register allocation via graph coloring. Journal of Computer Languages, 6:45--57, 1981.
• 8: Standard Performance Evaluation Corporation. SPEC CPU2000 V1.3. http://www.spec.org/cpu2000/.
• 9: 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]
• 10: 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
• 11: 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]
• 12: Daniel Grund and Sebastian Hack. A Fast Cutting-Plane Algorithm for Optimal Coalescing. In Shriram Krishnamurthi and Martin Odersky, editors, Compiler Construction, volume 4420 of Lecture Notes In Computer Science, pages 111--115, March 2007.
• 13: Sebastian Hack. Register Allocation for Programs in SSA Form. PhD thesis, Universität Karlsruhe, October 2007.
• 14: Sebastian Hack, Daniel Grund, and Gerhard Goos. Register Allocation for Programs in SSA Form. In Andreas Zeller and Alan Mycroft, editors, Compiler Construction, volume 3923, pages 247--262. Springer, March 2006.
• 15: The libFirm Compiler. http://www.libfirm.org.
• 16: Guei-Yuan Lueh , Thomas Gross , Ali-Reza Adl-Tabatabai, Fusion-based register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.3, p.431-470, May 2000 [doi>10.1145/353926.353929]
• 17: Dániel Marx. Graph Coloring with Local and Global Constraints. PhD thesis, Budapest University of Technology and Economics, 2004.
• 18: Robert Morgan, Building an optimizing compiler, Digital Press, Newton, MA, 1998
• 19: Takuya Nakaike , Tatsushi Inagaki , Hideaki Komatsu , Toshio Nakatani, Profile-based global live-range splitting, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 20: Michael Paleczny , Christopher Vick , Cliff Click, The java hotspot^TM server compiler, Proceedings of the 2001 Symposium on Java^TM Virtual Machine Research and Technology Symposium, p.1-1, April 23-24, 2001, Monterey, California
• 21: 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 [doi>10.1145/1011508.1011512]
• 22: Fernando Magno Quintão Pereira and Jens Palsberg. Register allocation via coloring of chordal graphs. In Proceedings of APLAS'05, volume 3780 of Lecture Notes In Computer Science, pages 315--329. Springer, November 2005.
• 23: Tim A. Wagner , Vance Maverick , Susan L. Graham , Michael A. Harrison, Accurate static estimators for program optimization, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.85-96, June 20-24, 1994, Orlando, Florida, United States

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation

General Terms:
Algorithms, Languages, Performance

Keywords:
graph coloring, register allocation, ssa form