Live-range unsplitting for faster optimal coalescing

ABSTRACT

Register allocation is often a two-phase approach: spilling of registers to memory, followed by coalescing of registers. Extreme live-range splitting (i.e. live-range splitting after each statement) enables optimal solutions based on ILP, for both spilling and coalescing. However, while the solutions are easily found for spilling, for coalescing they are more elusive. This difficulty stems from the huge size of interference graphs resulting from live-range splitting.

This paper focuses on coalescing in the context of extreme live-range splitting. It presents some theoretical properties that give rise to an algorithm for reducing interference graphs. This reduction consists mainly in finding and removing useless splitting points. It is followed by a graph decomposition based on clique separators. The reduction and decomposition are general enough, so that any coalescing algorithm can be applied afterwards.

Our strategy for reducing and decomposing interference graphs preserves the optimality of coalescing. When used together with an optimal coalescing algorithm (e.g. ILP), optimal solutions are much more easily found. The strategy has been tested on a standard benchmark, the optimal coalescing challenge. For this benchmark, the cutting-plane algorithm for optimal coalescing (the only optimal algorithm for coalescing) runs 300 times faster when combined with our strategy. Moreover, we provide all the optimal solutions of the optimal coalescing challenge, including the three instances that were previously unsolved.

REFERENCES

• 1: Andrew W. Appel, Modern Compiler Implementation: In ML, Cambridge University Press, New York, NY, 1998
• 2: Andrew W. Appel and Lal George. Optimal coalescing challenge, 2000. http://www.cs.princeton.edu/ appel/coalesce
• 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: Peter Bergner , Peter Dahl , David Engebretsen , Matthew O'Keefe, Spill code minimization via interference region spilling, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.287-295, June 16-18, 1997, Las Vegas, Nevada, United States
• 5: Florent Bouchez. A Study of Spilling and Coalescing in Register Allocation as Two Separate Phases. PhD thesis, ENS Lyon, France, dec 2008.
• 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: Philip Brisk, F.Dabiri, J.Macbeth, et al. Polynomial time graph coloring register allocation. In Workshop on Logic and Synthesis, 2005.
• 9: G. J. Chaitin, Register allocation & spilling via graph coloring, ACM SIGPLAN Notices, v.17 n.6, p.98-101, June 1982
• 10: 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]
• 11: Keith D. Cooper , L. Taylor Simpson, Live Range Splitting in a Graph Coloring Register Allocator, Proceedings of the 7th International Conference on Compiler Construction, p.174-187, March 28-April 04, 1998
• 12: 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
• 13: 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]
• 14: David W. Goodwin , Kent D. Wilken, Optimal and near-optimal global register allocations using 0–1 integer programming, Software—Practice & Experience, v.26 n.8, p.929-965, Aug. 1996 [doi>10.1002/(SICI)1097-024X(199608)26:8<929::AID-SPE40>3.3.CO;2-K]
• 15: David W. Goodwin. Optimal and near-optimal global register allocation. PhD thesis, University of California, 1996.
• 16: Daniel Grund and Sebastian Hack. A fast cutting-plane algorithm for optimal coalescing. In CC'07, LNCS, pages 111--125, 2007.
• 17: Rajiv Gupta , Mary Lou Soffa , Denise Ombres, Efficient register allocation via coloring using clique separators, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.370-386, May 1994 [doi>10.1145/177492.177499]
• 18: Priyadarshan Kolte , Mary Jean Harrold, Load/store range analysis for global register allocation, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.268-277, June 21-25, 1993, Albuquerque, New Mexico, United States
• 19: 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]
• 20: J. Park , S.-M. Moon, Optimistic Register Coalescing, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.196, October 12-18, 1998
• 21: Vivek Sarkar and Rajkishore Barik. Extended linear scan: An alternate foundation for global register allocation. In CC'07, LNCS, pages 141--155, 2007.
• 22: Robert Endre Tarjan. Decomposition by clique separators. In Discrete Mathematics, 55(2):221--232, 1985.
• 23: Douglas B. West. Introduction to Graph Theory (2nd Edition). Prentice Hall, August 2000.
• 24: Mihalis Yannakakis , Fanica Gavril, The maximum k-colorable subgraph problem for chordal graphs, Information Processing Letters, v.24 n.2, p.133-137, January 1987 [doi>10.1016/0020-0190(87)90107-4]

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: Optimization

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Languages

Keywords:
coalescing, graph reduction, register allocation