Decoupled graph-coloring register allocation with hierarchical aliasing

ABSTRACT

Recent results have shown how to do graph-coloring-based register allocation in a way that decouples spilling from register assignment. This decoupled approach has the main advantage of simplifying the implementation of register allocators. However, the decoupled model, as described in previous works, faces many problems when dealing with register aliasing, a phenomenon typical in architectures usually seen in embedded systems, such as ARM. In this paper we introduce the semi-elementary form, a program representation that brings decoupled register allocation to architectures with register aliasing. The semi-elementary form is much smaller than program representations used by previous decoupled solutions; thus, leading to register allocators that perform better in terms of time and space. Furthermore, this representation reduces the number of copies that traditional allocators insert into assembly programs. We have empirically validated our results by showing how our representation improves two well known graph coloring based allocators, namely the Iterated Register Coalescer (IRC), and Bouchez et al.'s brute force (BF) method, both augmented with Smith et al. extensions to handle aliasing. Running our techniques on SPEC CPU 2000, we have reduced the number of nodes in the interference graphs by a factor of 4 to 5; hence, speeding-up allocation time by a factor of 3 to 5. Additionally the semi-elementary form reduces by 8% the number of copies that IRC leaves uncoalesced.

References

1. Andrew W. Appel and Lal George. Optimal spilling for CISC machines with few registers. In PLDI, pages 243--253. ACM, 2001.
2. Andrew W. Appel and Jens Palsberg. Modern Compiler Implementation in Java. Cambridge University Press, 2nd edition, 2002.
3. Florent Bouchez. Allocation de registres et vidage en mémoire. Master's thesis, ENS Lyon, October 2005.
4. Florent Bouchez, Quentin Colombet, Alain Darte, Fabrice Rastello, and Christophe Guillon. Parallel copy motion. In SCOPES, pages 1--10. ACM, 2010.
5. Florent Bouchez, Alain Darte, and Fabrice Rastello. On the complexity of register coalescing. In CGO, pages 102--104. IEEE, 2007.
6. Florent Bouchez, Alain Darte, and Fabrice Rastello. Advanced conservative and optimistic register coalescing. In CASES, pages 147--156. ACM, 2008.
7. Preston Briggs, Keith D. Cooper, and Linda Torczon. Improvements to graph coloring register allocation. TOPLAS, 16(3):428--455, 1994.
8. Gregory J. Chaitin, Mark 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. Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Efficiently computing static single assignment form and the control dependence graph. TOPLAS, 13(4):451--490, 1991.
10. Janet Fabri. Automatic storage optimization. In CC, pages 83--91. ACM, 1979.
11. Lal George and Andrew W. Appel. Iterated register coalescing. TOPLAS, 18(3):300--324, 1996.
12. Sebastian Hack and Gerhard Goos. Copy coalescing by graph recoloring. In PLDI, pages 227--237. ACM, 2008.
13. Sebastian Hack, Daniel Grund, and Gerhard Goos. Register allocation for programs in SSA-form. In CC, pages 247--262. Springer-Verlag, 2006.
14. A. B. Kempe. On the geographical problem of the four colors. American Journal of Mathematics, 2(1):193--200, 1879.
15. Timothy Kong and Kent D Wilken. Precise register allocation for irregular architectures. In MICRO, pages 297--307. IEEE, 1998.
16. Chris Lattner and Vikram S. Adve. LLVM: A compilation framework for lifelong program analysis & transformation. In CGO, pages 75--88. IEEE, 2004.
17. Jonathan K. Lee, Jens Palsberg, and Fernando M. Q. Pereira. Aliased register allocation. In ICALP, 2007.
18. V. Krishna Nandivada, Fernando Pereira, and Jens Palsberg. A framework for end-to-end verification and evaluation of register allocators. In SAS, pages 153--169. Springer, Kongens Lyngby, Denmark, August 2007.
19. Fernando Magno Quintao Pereira and Jens Palsberg. Register allocation via coloring of chordal graphs. In APLAS, pages 315--329. Springer, 2005.
20. Fernando Magno Quintao Pereira and Jens Palsberg. Register allocation by puzzle solving. In PLDI, pages 216--226. ACM, 2008.
21. Fernando Magno Quintao Pereira and Jens Palsberg. SSA elimination after register allocation. In CC, pages 158--173, 2009.
22. Fernando Magno Quintão Pereira and Jens Palsberg. Punctual coalescing. In CC, pages 165--184, 2010.
23. Hongbo Rong. Tree register allocation. In MICRO, pages 67--77. ACM, 2009.
24. Vivek Sarkar and Rajkishore Barik. Extended linear scan: an alternate foundation for global register allocation. In LCTES/CC, pages 141--155. ACM, 2007.
25. Bernhard Scholz and Erik Eckstein. Register allocation for irregular architectures. In LCTES/SCOPES, pages 139--148. ACM, 2002.
26. Michael D. Smith, Norman Ramsey, and Glenn Holloway. A generalized algorithm for graph-coloring register allocation. In PLDI, pages 277--288. ACM, 2004.
27. Christian Wimmer and Michael Franz. Linear scan register allocation on SSA form. In CGO, pages 170--179. ACM, 2010.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Social and professional topics

  • Professional topics

    • Management of computing and information systems

      • Software management

        • Software selection and adaptation

• Software and its engineering

  • Software creation and management

    • Software verification and validation

      • Empirical software validation

  • Software organization and properties

    • Extra-functional properties

      • Software performance

    • Software functional properties

      • Formal methods