A global progressive register allocator

ABSTRACT

This paper describes a global progressive register allocator, a register allocator that uses an expressive model of the register allocation problem to quickly find a good allocation and then progressively find better allocations until a provably optimal solution is found or a preset time limit is reached. The key contributions of this paper are an expressive model of global register allocation based on multicommodity network flows that explicitly represents spill code optimization, register preferences, copy insertion, and constant rematerialization; two fast, but effective, heuristic allocators based on this model; and a more elaborate progressive allocator that uses Lagrangian relaxation to compute the optimality of its allocations. Our progressive allocator demonstrates code size improvements as large as 16.75% compared to a traditional graph allocator. On average, we observe an initial improvement of 3.47%, which increases progressively to 6.84% as more time is permitted for compilation.

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: 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
• 3: B. M. Baker and J. Sheasby. Accelerating the convergence of subgradient optimisation. European Journal of Operational Research, 117(1):136--144, August 1999.
• 4: L. A. Belady. A study of replacement algorithms for virtual-storage computer. IBM Systems Journal, 5(2):78--101, 1966.
• 5: 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
• 6: D. Bernstein , M. Golumbic , y. Mansour , R. Pinter , D. Goldin , H. Krawczyk , I. Nahshon, Spill code minimization techniques for optimizing compliers, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.258-263, June 19-23, 1989, Portland, Oregon, United States
• 7: Hans Bodlaender , Jens Gustedt , Jan Arne Telle, Linear-time register allocation for a fixed number of registers, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.574-583, January 25-27, 1998, San Francisco, California, United States
• 8: Preston Briggs, Register allocation via graph coloring, Rice University, Houston, TX, 1992
• 9: Preston Briggs , Keith D. Cooper , Linda Torczon, Coloring register pairs, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.1, p.3-13, March 1992 [doi>10.1145/130616.130617]
• 10: 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]
• 11: David Callahan , Brian Koblenz, Register allocation via hierarchical graph coloring, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.192-203, June 24-28, 1991, Toronto, Ontario, Canada
• 12: G. J. Chaitin, Register allocation & spilling via graph coloring, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.98-105, June 23-25, 1982, Boston, Massachusetts, United States
• 13: Frederick Chow , John Hennessy, Register allocation by priority-based coloring, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.222-232, June 17-22, 1984, Montreal, Canada
• 14: K. Cooper, A. Dasgupta, and J. Eckhardt. Revisiting graph coloring register allocation: A study of the Chaitin-Briggs and Callahan-Koblenz algorithms. In Proc. of the Workshop on Languages and Compilers for Parallel Computing (LCPC'05), October 2005.
• 15: 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
• 16: Martin Farach , Vincenzo Liberatore, On local register allocation, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.564-573, January 25-27, 1998, San Francisco, California, United States
• 17: C. Fu, K.Wilken, and D. Goodwin. A faster optimal register allocator. The Journal of Instruction-Level Parallelism, 7:1--31, January 2005.
• 18: Catherine H. Gebotys, Low energy memory and register allocation using network flow, Proceedings of the 34th annual conference on Design automation, p.435-440, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266192]
• 19: 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]
• 20: U. Hirnschrott, A. Krall, and B. Scholz. Graph coloring vs. optimal register allocation for optimizing compilers. In JMLC, pp. 202--213, 2003.
• 21: Wei-Chung Hsu , Charles N. Fisher , James R. Goodman, On the Minimization of Loads/Stores in Local Register Allocation, IEEE Transactions on Software Engineering, v.15 n.10, p.1252-1260, October 1989 [doi>10.1109/TSE.1989.559775]
• 22: ILOG CPLEX. http://www.ilog.com/products/cplex.
• 23: K. Kennedy. Design and optimization of compilers, Index register allocation in straight line code and simple loops, pp. 51--63. Prentice- Hall, 1972.
• 24: David Koes , Seth Copen Goldstein, A Progressive Register Allocator for Irregular Architectures, Proceedings of the international symposium on Code generation and optimization, p.269-280, March 20-23, 2005 [doi>10.1109/CGO.2005.4]
• 25: D. Koes and S. C. Goldstein. An analysis of graph coloring register allocation. Technical Report CMU-CS-06-111, Carnegie Mellon University, March 2006.
• 26: David J. Kolson , Alexandru Nicolau , Nikil Dutt , Ken Kennedy, Optimal register assignment to loops for embedded code generation, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.2, p.251-279, April 1996 [doi>10.1145/233539.233542]
• 27: Timothy Kong , Kent D. Wilken, Precise register allocation for irregular architectures, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.297-307, November 1998, Dallas, Texas, United States
• 28: Akira Koseki , Hideaki Komatsu , Toshio Nakatani, Preference-directed graph coloring, ACM SIGPLAN Notices, v.37 n.5, May 2002
• 29: Claude Lemarechal, Lagrangian Relaxation, Computational Combinatorial Optimization, Optimal or Provably Near-Optimal Solutions [based on a Spring School], p.112-156, May 15-19, 2000
• 30: Vincenzo Liberatore , Martin Farach-Colton , Ulrich Kremer, Evaluation of Algorithms for Local Register Allocation, Proceedings of the 8th International Conference on Compiler Construction, Held as Part of the European Joint Conferences on the Theory and Practice of Software, ETAPS'99, p.137-152, March 22-28, 1999
• 31: F. Luccio, A comment on index register allocation, Communications of the ACM, v.10 n.9, p.572-574, Sept. 1967 [doi>10.1145/363566.363694]
• 32: 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]
• 33: A. R. Madabushi. Lagrangian relaxation / dual approaches for solving large-scale linear programming problems. Master's thesis, Virginia Polytechnic Institute and State University, February 1997.
• 34: Waleed M. Meleis , Edward S. Davidson, Optimal local register allocation for a multiple-issue machine, Proceedings of the 8th international conference on Supercomputing, p.107-116, July 11-15, 1994, Manchester, England [doi>10.1145/181181.181318]
• 35: Rajeev Motwani , Krishna V. Palem , Vivek Sarkar , Salem Reyen, Combining Register Allocation and Instruction Scheduling, Stanford University, Stanford, CA, 1995
• 36: Mayur Naik , Jens Palsberg, Compiling with code-size constraints, Proceedings of the joint conference on Languages, compilers and tools for embedded systems: software and compilers for embedded systems, June 19-21, 2002, Berlin, Germany
• 37: Mizuhito Ogawa , Zhenjiang Hu , Isao Sasano, Iterative-free program analysis, Proceedings of the eighth ACM SIGPLAN international conference on Functional programming, p.111-123, August 25-29, 2003, Uppsala, Sweden
• 38: 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]
• 39: John Ruttenberg , G. R. Gao , A. Stoutchinin , W. Lichtenstein, Software pipelining showdown: optimal vs. heuristic methods in a production compiler, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.1-11, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 40: Michael D. Smith , Norman Ramsey , Glenn Holloway, A generalized algorithm for graph-coloring register allocation, ACM SIGPLAN Notices, v.39 n.6, May 2004
• 41: Mikkel Thorup, All structured programs have small tree width and good register allocation, Information and Computation, v.142 n.2, p.159-181, May 2, 1998 [doi>10.1006/inco.1997.2697]
• 42: 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
• 43: 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]

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

General Terms:
Algorithms, Design, Languages, Performance

Keywords:
progressive solver, register alocation