Progressive spill code placement

ABSTRACT

Register allocation has gained renewed attention in the recent past. Several authors propose a separation of the problem into decoupled sub-tasks including spilling, allocation, assignment, and coalescing. This approach is largely motivated by recent advances in SSA-based register allocation that suggest that a decomposition does not significantly degrade the overall allocation quality.

The algorithmic challenges of intra-procedural spilling have been neglected so far and very crude heuristics were employed. In this work, (1) we introduce the constrained min-cut (CMC) problem for solving the spilling problem, (2) we provide an integer linear program formulation for computing an optimal solution of CMC, and (3) we devise a progressive Lagrangian solver that is viable for production compilers. Our experiments with Spec2k and MiBench show that optimal solutions are feasible, even for very large programs, and that heuristics leave significant potential behind for small register files.

REFERENCES

• 1: Andrew W Appel and Lal George. Optimal spilling for cisc machines with few registers. In PLDI, pages 243 -- 253. ACM Press, 2001.
• 2: R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.
• 3: Preston Briggs, Keith D. Cooper, and Linda Torczon. Improvements to graph coloring register allocation. ACM Trans. Program. Lang. Syst., 16(3):428 -- 455, 1994.
• 4: Philip Brisk, Foad Dabiri, Jamie Macbeth, and Majid Sarrafzadeh. Polynomial-time graph coloring register allocation. In International Workshop on Logic and Synthesis. ACM Press, 2005.
• 5: Florent Bouchez, Alain Darte, and Fabrice Rastello. On the complexity of spill everywhere under SSA form. In Santosh Pande and Zhiyuan Li, editors, LCTES, pages 103--112. ACM, 2007.
• 6: Laszlo A. Belady. A study of replacement algorithms for virtual storage computers. IBM Syst. J., 5:78--101, 1966.
• 7: 1]CFRW91Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Efficiently computing ssa form and the control dependence graph. TOPLAS, 13(4):451--490, October 1991.
• 8: Fred C. Chow and John L. Hennessy. The priority-based coloring approach to register allocation. ACM Trans. Program. Lang. Syst., 12(4):501--536, 1990.
• 9: G J Chaitin. Register allocation and spilling via graph coloring. Symposium on Compiler Construction, 17(6):98 -- 105, 1982.
• 10: Farach-Colton and Liberatore. On local register allocation. ALGORITHMS: Journal of Algorithms, 37, 2000.
• 11: Lal George and Andrew W Appel. Iterated register coalescing. ACM Trans. Program. Lang. Syst., 18(3):300 -- 324, 1996.
• 12: Jia Guo, Maria Jesus Garzaran, and David A. Padua. The power of belady's algorithm in register allocation for long basic blocks. In LCPC, volume 2958 of LNCS, pages 374--390. Springer, 2004.
• 13: Daniel Grund and Sebastian Hack. A fast cutting-plane algorithm for optimal coalescing. In Compiler Construction, volume 4420 of LNCS, pages 111--125. Springer, 2007.
• 14: Goodwin and Wilken. Optimal and near-optimal global register allocation using 0-1 integer programming. Software-Practice and Experience, 26, 1996.
• 15: Sebastian Hack. Register Allocation for Programs in SSA Form. PhD thesis, Universitat Karlsruhe, October 2007.
• 16: W. Hsu, C. Fischer, and J. Goodman. On the minimization of loads/stores in local register allocation. IEEE Trans. on Softw. Eng., 15(10):1252, October 1989.
• 17: Sebastian Hack and Gerhard Goos. Optimal register allocation for ssa-form programs in polynomial time. Information Processing Letters, 98(4):150--155, May 2006.
• 18: Sebastian Hack, Daniel Grund, and Gerhard Goos. Register Allocation for Programs in SSA-Form. In Compiler Construction, volume 3923, pages 247--262. Springer, March 2006.
• 19: David Ryan Koes and Seth Copen Goldstein. A global progressive register allocator. ACM SIGPLAN Notices, 41(6):204--215, June 2006.
• 20: Chris Lattner and Vikram S. Adve. LLVM: A compilation framework for lifelong program analysis & transformation. In CGO, pages 75--88. IEEE Computer Society, 2004.
• 21: Jinpyo Park and Soo-Mook Moon. Optimistic register coalescing. In PACT, pages 196--204. IEEE Computer Society, October 1998.
• 22: Fernando Magno Quintao Pereira and Jens Palsberg. Register allocation via coloring of chordal graphs. In APLAS, volume 3780 of LNCS, pages 315--329. Springer, 2005.
• 23: Massimiliano Poletto and Vivek Sarkar. Linear scan register allocation. ACM Trans. Program. Lang. Syst., 21(5):895 -- 913, 1999.
• 24: H. S. Stone. Multiprocessor scheduling with the aid of network flow algorithms. IEEE TSE, SE-3(1):85--93, January 1977.
• 25: Mechthild Stoer and Frank Wagner. A simple min-cut algorithm. J. ACM, 44(4):585--591, 1997.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
SSA form, constrained min-cut, register allocation, spilling