Steven R. Vegdahl
Abstract
A Chaitin-style register allocator often blocks during its simplification phase because no node in the interference graph has a degree that is sufficiently small. Typically, this is handled by node-splitting, or by optimistically continuing---and hoping that a legal N-coloring will still be found. We observe that the merging of two nodes in a graph causes a reduction in the degree of any node that had been adjacent to both. We have enhanced Chaitin's coloring algorithm so that it attempts node-merging during graph simplification; this often allows simplification to continue, while still guaranteeing a coloring for the graph. We have tested this algorithm using Appel's database of register-coloring graphs, and have compared it with Chaitin's algorithm. The merge-enhanced algorithm yields a better coloring about 8% of the time, and a worse coloring less than 0.1% of the time.
- 1 Appel, A. Sample Graph Coloring Problems. URL: http:// www. cs.princeton.edu/fac/appel/~aphdata (1996).Google Scholar
- 2 Appel, A. Modem Compiler Implementation in Java. Cambridge University Press (1998). Google ScholarDigital Library
- 3 Bergner, P., Dahl, P, Engebretsen, D. and O'Keefe, M. Spill Code Minimization via Interference Region Spilling. SIG- PLAN Notices 32, 5 (May 1997), 287-295. Proc. A CM SIG. PLAN '97 Conference on Programming Language Design and Implementation. Google ScholarDigital Library
- 4 Blum, M., Floyd, R., Pratt, V., Rivest, R. and Tarjan, R. Time Bounds for Selection. Journal of Computer and System Sciences, 7,4 (1972), 448--461.Google Scholar
- 5 Briggs, P., Cooper, D. and Torczon, L. Improvements to Graph Coloring Register Allocation. A CM Trans Programming Languages and Systems, 12,4 (Oct. 1990), 501-536. Google ScholarDigital Library
- 6 Chaitin, G., Auslander, M., Chandra, A.,eocke, J. Hopkins, M. and Markstein, P. Register Allocation via Coloring. Computer Languages 6(1981), 47-57.Google ScholarDigital Library
- 7 Chaitin, G. Register Allocation and Spilling via Graph Coloring. SIGPLAN Notices 17, 6 (June 1992), 257-265. Proc. A CM SIGPLAN '82 Symposium on Compiler Construction. Google ScholarDigital Library
- 8 Chow, E and Hennessy, J. The Priority-Based Coloring Approach to Register Allocation. ACM Trans Programming Languages and Systems, 12,4 (Oct. 1990), 501-536. Google ScholarDigital Library
- 9 George, L. and Appel, A. Iterated register coalescing. ACM Trans. on Programming Languages and Systems, 18, 3 (May 1996), 300-324. Google ScholarDigital Library
- 10 Kurlander, S. and Fischer, C. Zero-Cost Range Splitting. SIG- PLAN Notices 29, 6 (June 1994), 257-265. Proc. ACM SIG- PLAN '94 Conference on Programming Language Design and Implementation. Google ScholarDigital Library
- 11 Lueh, G. and Gross, T. Call-Cost Directed Register Allocation. SIGPLAN Notices 32, 5 (May 1997), 296-307. Proc. A CM SIGPLAN '97 Conference on Programming Language Design and Implementation. Google ScholarDigital Library
- 12 Park, J. and Moon, S. Optimistic Register Coalescing. Proc. 1998 International Conference on Parallel Architectures and Compilation Techniques (1998), 196-204. Google ScholarDigital Library
Index Terms
- Using node merging to enhance graph coloring
Recommendations
Using node merging to enhance graph coloring
PLDI '99: Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementationA Chaitin-style register allocator often blocks during its simplification phase because no node in the interference graph has a degree that is sufficiently small. Typically, this is handled by node-splitting, or by optimistically continuing---and hoping ...
List-coloring the square of a subcubic graph
The square G2 of a graph G is the graph with the same vertex set G and with two vertices adjacent if their distance in G is at most 2. Thomassen showed that every planar graph G with maximum degree Δ(G) = 3 satisfies χ(G2) ≤ 7. Kostochka and Woodall ...
Preference-directed graph coloring
PLDI '02: Proceedings of the ACM SIGPLAN 2002 conference on Programming language design and implementationThis paper describes a new framework of register allocation based on Chaitin-style coloring. Our focus is on maximizing the chances for live ranges to be allocated to the most preferred registers while not destroying the colorability obtained by graph ...
Comments