Advanced conservative and optimistic register coalescing

ABSTRACT

In the context of embedded systems, it is crucial to minimize memory transfers to reduce latency and power consumption. Stack access due to variable spilling during register allocation can be significantly reduced using aggressive live-range splitting. However, without a good (conservative) coalescing technique, the benefit of a good spilling may be lost due to the many register-to-register moves introduced. The challenge is thus to find a good trade-off between a too aggressive strategy that could make the interference graph uncolorable without more spilling, and a too conservative strategy that preserves colorability but leaves unnecessary moves. Two main approaches are "iterated register coalescing" by George and Appel and "optimistic coalescing" by Park and Moon. The first coalesces moves one by one conservatively. The second coalesces moves regardless of the colorability, then undo coalescings to reduce spilling. Focusing on greedy-k-colorable graphs---which are usually obtained after all spill decisions and, possibly, some split decisions---we show how these two approaches can be improved, optimistic coalescing with a more involved de-coalescing phase, incremental coalescing with a less pessimistic conservative technique. Unlike previous experiments, our results show that optimistic strategies do not outperform conservative ones. Our incremental conservative coalescing performs even better than our improved de-coalescing scheme and leads to about 15% improvement compared to the state-of-the-art optimistic coalescing.

REFERENCES

• 1: Andrew W. Appel, Modern Compiler Implementation: In ML, Cambridge University Press, New York, NY, 1998
• 2: A. Appel and L. George. Coalescing challenge. http://www.cs.princeton.edu/~ appel/coalesce, 2000.
• 3: 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
• 4: F. Bouchez, A. Darte, C. Guillon, and F. Rastello. Register allocation and spill complexity under SSA. Technical Report RR2005-33, LIP, ENS-Lyon, France, Aug. 2005.
• 5: F. Bouchez, A. Darte, and F. Rastello. Improvements to conservative and optimistic register coalescing. Technical Report RR2007-41, LIP, ENS-Lyon, France, Oct. 2007.
• 6: 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]
• 7: Preston Briggs, Register allocation via graph coloring, Rice University, Houston, TX, 1992
• 8: 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]
• 9: P. Brisk, F. Dabiri, J. Macbeth, and M. Sarrafzadeh. Polynomial time graph coloring register allocation. In 14th International Workshop on Logic and Synthesis, June 2005.
• 10: G. Chaitin, M. Auslander, A. Chandra, J. Cocke, M. Hopkins, and P. Markstein. Register allocation via coloring. Computer Languages, 6:47--57, January 1981.
• 11: 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]
• 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: Martin Charles Golumbic, Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics, Vol 57), North-Holland Publishing Co., Amsterdam, The Netherlands, 2004
• 14: D. Grund and S. Hack. A fast cutting-plane algorithm for optimal coalescing. In S. Krishnamurthi and M. Odersky, editors, Compiler Construction 2007, volume 4420 of Lecture Notes In Computer Science, pages 111--125. Springer, March 2007. Braga, Portugal.
• 15: S. Hack, D. Grund, and G. Goos. Register allocation for programs in SSA-form. In Compiler Construction 2006, volume 3923 of LNCS. Springer Verlag, 2006.
• 16: A. Leung and L. George. A new MLRISC register allocator. Technical report, New York University, 1999.
• 17: 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]
• 18: F. M. Q. Pereira and J. Palsberg. Register allocation via coloring of chordal graphs. In Proceedings of APLAS'05, Asian Symposium on Programming Languages and Systems, pages 315--329, Tsukuba, Japan, Nov. 2005.
• 19: F. Rastello , F. de Ferrière , C. Guillon, Optimizing Translation Out of SSA Using Renaming Constraints, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.265, March 20-24, 2004, Palo Alto, California
• 20: 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
• 21: Steven R. Vegdahl, Using node merging to enhance graph coloring, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.150-154, May 01-04, 1999, Atlanta, Georgia, United States

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Compilers

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
chordal graph, coloring number, greedy-k-colorable graph, register allocation, register coalescing