On the complexity of spill everywhere under SSA form

ABSTRACT

Compilation for embedded processors can be either aggressive (time consuming cross-compilation) or just in time (embedded and usually dynamic). The heuristics used in dynamic compilation are highly constrained by limited resources, time and memory in particular. Recent results on the SSA form open promising directions for the design of new register allocation heuristics for embedded systems and especially for embedded compilation. In particular, heuristics based on tree scan with two separated phases -- one for spilling, then one for coloring/coalescing -- seem good candidates for designing memory-friendly, fast, and competitive register allocators. Still, also because of the side effect on power consumption, the minimization of loads and stores overhead (spilling problem) is an important issue. This paper provides an exhaustive study of the complexity of the "spill everywhere" problem in the context of the SSA form. Unfortunately, conversely to our initial hopes, many of the questions we raised lead to NP-completeness results. We identify some polynomial cases but that are impractical in JIT context. Nevertheless, they can give hints to simplify formulations for the design of aggressive allocators.

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: L. A. Belady. A study of replacement algorithms for a virtual storage computer. IBM Systems Journal, 5(2):78--101, 1966.
• 3: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 4: Florent Bouchez, Alain Darte, Christophe Guillon, and Fabrice Rastello. Register allocation and spill complexity under SSA. Technical Report RR2005-33, LIP, ENS-Lyon, France, August 2005.
• 5: Florent Bouchez, Alain Darte, Christophe Guillon, and Fabrice Rastello. Register allocation: What does the NP-completeness proof of Chaitin et al. really prove? In International Workshop on Languages and Compilers for Parallel Computing (LCPC'06), LNCS, New Orleans, Louisiana, 2006. Springer Verlag.
• 6: Philip Brisk, Foad Dabiri, Jamie Macbeth, and Majid Sarrafzadeh. Polynomial time graph coloring register allocation. In 14th International Workshop on Logic and Synthesis, June 2005.
• 7: Zoran Budimlic , Keith D. Cooper , Timothy J. Harvey , Ken Kennedy , Timothy S. Oberg , Steven W. Reeves, Fast copy coalescing and live-range identification, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 8: Gregory J. Chaitin, Marc A. Auslander, Ashok K. Chandra, John Cocke, Martin E. Hopkins, and Peter W. Markstein. Register allocation via coloring. Computer Languages, 6:47--57, 1981.
• 9: Keith D. Cooper , Anshuman Dasgupta, Tailoring Graph-coloring Register Allocation For Runtime Compilation, Proceedings of the International Symposium on Code Generation and Optimization, p.39-49, March 26-29, 2006 [doi>10.1109/CGO.2006.35]
• 10: Keith D. Cooper and Linda Torczon. Engineering a Compiler. Morgan Kaufmann, 2004.
• 11: Martin Farach-Colton , Vincenzo Liberatore, On local register allocation, Journal of Algorithms, v.37 n.1, p.37-65, Oct. 2000 [doi>10.1006/jagm.2000.1095]
• 12: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 13: Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980.
• 14: Christian Grothoff, Rajkishore Barik, Rahul Gupta, and Vinayaka Pandit. Optimal bitwise register allocation using integer linear programming. In International Workshop on Languages and Compilers for Parallel Computing (LCPC'06), LNCS, New Orleans, Louisiana, 2006. Springer Verlag.
• 15: Sebastian Hack , Gerhard Goos, Optimal register allocation for SSA-form programs in polynomial time, Information Processing Letters, v.98 n.4, p.150-155, 31 May 2006 [doi>10.1016/j.ipl.2006.01.008]
• 16: Sebastian Hack, Daniel Grund, and Gerhard Goos. Towards register allocation for programs in SSA-form. Technical Report RR2005-27, Universität Karlsruhe, September 2005.
• 17: Sebastian Hack, Daniel Grund, and Gerhard Goos. Register allocation for programs in SSA-form. In International Conference on Compiler Construction (CC'06), volume 3923 of LNCS. Springer Verlag, 2006.
• 18: 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]
• 19: Massimiliano Poletto , Vivek Sarkar, Linear scan register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.5, p.895-913, Sept. 1999 [doi>10.1145/330249.330250]
• 20: Omri Traub , Glenn Holloway , Michael D. Smith, Quality and speed in linear-scan register allocation, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.142-151, June 17-19, 1998, Montreal, Quebec, Canada
• 21: Christian Wimmer , Hanspeter Mössenböck, Optimized interval splitting in a linear scan register allocator, Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments, June 11-12, 2005, Chicago, IL, USA [doi>10.1145/1064979.1064998]
• 22: Mihalis Yannakakis, Node-and edge-deletion NP-complete problems, Proceedings of the tenth annual ACM symposium on Theory of computing, p.253-264, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804355]
• 23: 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: Code generation

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

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

General Terms:
Algorithms, Performance, Theory

Keywords:
SSA form, complexity, register allocation, spill