Lal George
Andrew W. Appel
Abstract
An important function of any register allocator is to target registers so as to eliminate copy instructions. Graph-coloring register allocation is an elegant approach to this problem. If the source and destination of a move instruction do not interfere, then their nodes can be coalesced in the interference graph. Chaitin's coalescing heuristic could make a graph uncolorable (i.e., introduce spills); Briggs et al. demonstrated a conservative coalescing heuristic that preserves colorability. But Briggs's algorithm is too conservative and leaves too many move instructions in our programs. We show how to interleave coloring reductions with Briggs's coalescing heuristic, leading to an algorithm that is safe but much more aggressive.
- APPEL, A. W. 1992. Compiling with Continuations. Cambridge University Press. ISBN 0-521- 41695-7. Google Scholar
- APPEL, A. W. AND iV{ACQUEEN, D. B. 1991. Standard ML of New Jersey. In Third Int'l Syrup. on Prog. Lang. Implementation and Logic Programming, M. Wirsing, Ed. Springer-Verlag, New York, 1-13.Google Scholar
- APPEL, t. W. AND SHAO, Z. 1992. Callee-save registers in continuation-passing style. Lisp Symb. Comput. 5, 3, 191-221. Google Scholar
- BRIGGS, P., COOPER, K. D., AND TORCZON, L. 1994. Improvements to graph coloring register allocation. ACM Trans. Program. Lang. Syst. 16, 3 (May), 428-455. Google Scholar
- BRIGGS, P. AND TORCZON, L. 1993. An efficient representation for sparse sets. ACM Lett. Program. Lang. Syst. 2, 1-4 (March-December), 59-69. Google Scholar
- CHAITIN, G. J. 1982. Register allocation and spilling via graph coloring. SIGPLAN Notices 17(6), 98-105. Proceeding of the ACM SIGPLAN '82 Symposium on Compiler Construction. Google Scholar
- CHAITIN, G. J., AUSLANDER, ~/{. t., CHANDRA, t. K., COCKE, J., HOPKINS, 54. E., AND 54ARK- STEIN, P. W. 1981. Register allocation via coloring. Comput. Lang. 6, 47-57.Google Scholar
- CHOW, F. C. 1988. Minimizing register usage penalty at procedure calls. In Proc. SIGPLAN '88 Conf. on Prog. Lang. Design and Implementation. AC54 Press, New York, 85-94. Google Scholar
- CYTRON, R., FERRANTE, J., ROSEN, B. K., WEGMAN, M. N., AND ZADECK, F. K. 1991. Efficiently computing static single assignment form and the control dependence graph. A CM Trans. Program. Lang. Syst. 13, 4 (Oct.), 451-490. Google Scholar
- GAREY, M. R. AND JOHNSON, D. S. 1979. Computers and Intractability, A Guide to the Theory of NP-completeness. Freeman. ISBN 0-7167-1044-7. Google Scholar
- KEMPE, A. B. 1879. On the geographical problem of the four colors. Am. J. Math. 2, 193-200.Google Scholar
- KRANZ, D., KELSEY, R., REES, J., HUDAK, P., PHILBIN, J., AND ADAMS, N. 1986. ORBIT: An optimizing compiler for Scheme. SIGPLAN Notices (Proc. Sigplan '86 Syrup. on Compiler Construction) 21, 7 (July), 219-33. Google Scholar
- LEROY, X. 1992. Unboxed objects and polymorphic typing. In Nineteenth Annual ACM Syrup. on Principles of Prog. Languages. ACM Press, New York, 177-188. Google Scholar
- SHAO, Z. AND APPEL, A. W. 1994. Space-efficient closure representations. In Proc. 1994 ACM Conf. on Lisp and Functional Programming. ACM Press, 150-161. Google Scholar
- SHAO, Z. AND APPEL, A. W. 1995. A type-based compiler for Standard ML. In Proc 1995 ACM Conf. on Programming Language Design and Implementation. ACM Press, 116-129. Google Scholar
Index Terms
- Iterated register coalescing
Recommendations
Optimistic register coalescing
Graph-coloring register allocators eliminate copies by coalescing the source and target nodes of a copy if they do not interfere in the interference graph. Coalescing, however, can be harmful to the colorability of the graph because it tends to yield a ...
Register coalescing techniques for heterogeneous register architecture with copy sifting
Optimistic coalescing has been proven as an elegant and effective technique that provides better chances of safely coloring more registers in register allocation than other coalescing techniques. Its algorithm originally assumes homogeneous registers, ...
Coloring-based coalescing for graph coloring register allocation
CGO '10: Proceedings of the 8th annual IEEE/ACM international symposium on Code generation and optimizationGraph coloring register allocation tries to minimize the total cost of spilled live ranges of variables. Live-range splitting and coalescing are often performed before the coloring to further reduce the total cost. Coalescing of split live ranges, ...
Comments