Name
Abstract | ||
|---|---|---|
We describe two improvements to Chaitin-style graph coloring register allocators. The first, optimistic coloring, uses a stronger heuristic to find a k-coloring for the interference graph. The second extends Chaitin's treatment of rematerialization to handle a larger class of values. These techniques are complementary. Optimistic coloring decreases the number of procedures that require spill code and reduces the amount of spill code when spilling is unavoidable. Rematerialization lowers the cost of spilling some values. This paper describes both of the techniques and our experience building and using register allocators that incorporate them. It provides a detailed description of optimistic coloring and rematerialization. It presents experimental data to show the performance of several versions of the register allocator on a suite of FORTRAN programs. It discusses several insights that we discovered only after repeated implementation of these allocators. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1145/177492.177575 | ACM Trans. Program. Lang. Syst. |
Keywords | Field | DocType |
experience building,register allocation,interference graph,optimistic coloring,fortran program,spill code,chaitin-style graph,detailed description,experimental data,register allocator,code generation,graph coloring,register allocators,programming language,compiler optimization | Heuristic,Programming language,Register allocation,Suite,Computer science,Parallel computing,Fortran,Theoretical computer science,Code generation,Allocator,Rematerialization,Graph coloring | Journal |
Volume | Issue | ISSN |
16 | 3 | 0164-0925 |
Citations | PageRank | References |
211 | 17.48 | 16 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Preston Briggs | 1 | 379 | 32.43 |
| Keith D. Cooper | 2 | 1726 | 229.37 |
| Linda Torczon | 3 | 1096 | 146.31 |