Comparing conservative coalescing criteria

ABSTRACT

Graph-coloring register allocators can eliminate copy instructions from a program by coalescing the interference graph nodes corresponding to the source and destination. Briggs showed that by limiting coalescing to those situations that he dubbed “conservative,” it could be prevented from causing spilling, that is, a situation where the allocator fails to assign a register to each live range. George and Appel adopted Briggs's conservativeness criterion in general, but provided an alternative criterion (the George test) to use in those cases where one of the nodes has been “precolored,” that is, preassigned a specific register. They motivated this alternative criterion by efficiency considerations, and provided no indication of the relative power of the two criteria. Thus it remained an open question whether the efficiency had been bought at the expense of reduced coalescing. Their implementation also used a limited version of the Briggs test, in place of the original, full version, without any comment on the impact of this substitution. In this article, we also present an analogously limited version of the George test.Thus we are now confronted with four different criteria for conservative coalescing: the full and limited Briggs tests and the full and limited George tests. We present a number of theorems characterizing the relative power of these different criteria, and a number of theorems characterizing the form of safety that each achieves. For example, we show that for coalescing with precolored nodes, the full George criterion is strictly more powerful than the full Briggs criterion, while offering an equally strong safety guarantee. Thus no coalesces are lost through George and Appel's introduction of the George test, and some can be gained without sacrificing safety.We also show that George and Appel's limited version of the Briggs test is probably undesirable. Although a slightly stronger safety result applies to it than to the full Briggs test, this comes at the expense of eliminating all coalesces that can reduce spilling.

REFERENCES

• 1: Andrew W. Appel, Modern compiler implementation in Java, Cambridge University Press, New York, NY, 1997
• 2: Preston Briggs, Register allocation via graph coloring, Rice University, Houston, TX, 1992
• 3: Briggs, P. 1993. ILOC register allocator contributed to the DIMACS graph challenge. Available online at ftp://dimacs.rutgers.edu/pub/challenge/graph/contributed/lewandowski/. Edited by Gary Lewandowski.
• 4: 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]
• 5: 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
• 6: Chaitin, G. J., Auslander, M. A., Chandra, A. K., Cocke, J., Hopkins, M. E., and Markstein, P. W. 1981. Register allocation via coloring. Comput. Lang. 6, 1, 47--57.
• 7: 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]
• 8: 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
• 9: Steven R. Vegdahl, Using node merging to enhance graph coloring, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.150-154, May 01-04, 1999, Atlanta, Georgia, United States

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

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

General Terms:
Algorithms, Languages

Keywords:
Copy propagation, graph coloring, register allocation, register coalescing