Name
Abstract | ||
|---|---|---|
This 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 simplification. Our coloring algorithm uses a graph representation of preferences called a Register Preference Graph, which helps find a good register selection. We then try to relax the register selection order created by the graph simplification. The relaxed order is defined as a partial order, represented using a graph called a Coloring Precedence Graph. Our algorithm utilizes such a partial order for the register selection instead of using the traditional simplification-driven order so that the chances of honoring the preferences are effectively increased. Experimental results show that our coloring algorithm is powerful to simultaneously handle spill decisions, register coalescing, and preference resolutions.
|
Year | DOI | Venue |
|---|---|---|
2002 | 10.1145/543552.512535 | Special Interest Group on Programming Languages |
Keywords | Field | DocType |
graph coloring,irregular-register architectures,register allocation,register coalescing | Complete coloring,Comparability graph,Fractional coloring,Computer science,List coloring,Algorithm,Directed graph,Theoretical computer science,Null graph,Greedy coloring,Graph coloring | Conference |
Volume | Issue | ISSN |
37 | 5 | 0362-1340 |
ISBN | Citations | PageRank |
1-58113-463-0 | 4 | 0.47 |
References | Authors | |
17 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Akira Koseki | 1 | 46 | 4.73 |
| Hideaki Komatsu | 2 | 410 | 34.00 |
| Toshio Nakatani | 3 | 741 | 56.80 |