Arthur Sorkin
Abstract
There is a problem with the definition of constrained live range and unconstrained live range in Chow and Hennessy's paper on priority-based register allocation that unnecessarily pessimizes the performance of the register allocator. Some corrections to the algorithm are suggested. Some problems with Chow and Hennessy's analysis of caller-save vs. callee-save are also discussed.
- [1] Chow, F., and Hennessy, J. The Priority-Based Coloring Approach to Register Allocation, TOPLAS 12, 4 (1990) pp. 501-536. Google Scholar
Digital Library
- [2] Chaitin, G. J. Register allocation and spilling via graph coloring. In Proceedings of the ACM SIGPLAN 1982 Symposium on Compiler Construction (Boston, June 1982). ACM, New York, 1982, pp. 22-31. Google ScholarDigital Library
- [3] Chaitin, G. J., Auslan der, M. A., Chandra, A. K., Cocke, J., Hopkins, M. E., and Markstein, P. Register allocation via coloring. Comput. Lang. 6 (1981), pp. 47-57.Google ScholarDigital Library
- [4] Chow, F., and Hennessy, J. Register allocation by priority-based coloring. In Proceedings of the ACM SIGPLAN 84 Symposium on Compiler Construction (Montreal, June 1984). ACM, New York, 1984, pp. 222-232. Google ScholarDigital Library
- [5] Chow, F. A portable machine-independent global optimizer -- Design and measurements. Ph.D. thesis and Tech. Rep. 83-254, Computer System Lab, Stanford Univ., Stanford, Calif., Dec. 1983. Google ScholarDigital Library
Index Terms
- Some comments on “the priority-based coloring approach to register allocation”
Recommendations
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, ...
Fusion-based register allocation
The register allocation phase of a compiler maps live ranges of a program to registers. If there are more candidates than there are physical registers, the register allocator must spill a live range (the home location is in memory) or split a live range ...
Differential register allocation
PLDI '05: Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementationMicro-architecture designers are very cautious about expanding the number of architected registers (also the register field), because increasing the register field adds to the code size, raises I-cache and memory pressure, complicates processor ...
Comments