Name
Abstract | ||
|---|---|---|
Memory transfers are becoming more important to optimize, for both performance and power consumption. With this goal in mind, new register allocation schemes are developed, which revisit not only the spilling problem but also the coalescing problem. Indeed, a more aggressive strategy to avoid load/store instructions may increase the constraints to suppress (coalesce) move instructions. This paper is devoted to the complexity of the coalescing phase, in particular in the light of recent developments on the SSA form. We distinguish several optimizations that occur in coalescing heuristics: a) aggressive coalescing removes as many moves as possible, regardless of the colorability of the resulting interference graph; b) conservative coalescing removes as many moves as possible while keeping the colorability of the graph; c) incremental conservative coalescing removes one particular move while keeping the colorability of the graph; d) optimistic coalescing coalesces moves aggressively, then gives up about as few moves as possible so that the graph becomes colorable again. We almost completely classify the NP-completeness of these problems, discussing also on the structure of the interference graph: arbitrary, chordal, or k-colorable in a greedy fashion. We believe that such a study is a necessary step for designing new coalescing strategies. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1109/CGO.2007.26 | CGO |
Keywords | Field | DocType |
coalescing heuristics,interference graph,coalescing phase,conservative coalescing,optimistic coalescing coalesces,incremental conservative coalescing,coalescing problem,resulting interference graph,register coalescing,new coalescing strategy,aggressive coalescing,chordal,registers,resource allocation,greedy algorithms,col,interference,merging,register allocation,computational complexity,frequency,graph coloring | Register allocation,Computer science,Chordal graph,Parallel computing,Greedy algorithm,Heuristics,Resource allocation,Static single assignment form,Graph coloring,Computational complexity theory | Conference |
ISSN | ISBN | Citations |
2164-2397 | 0-7695-2764-7 | 26 |
PageRank | References | Authors |
0.92 | 19 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Florent Bouchez | 1 | 90 | 4.37 |
| Alain Darte | 2 | 888 | 56.40 |
| Fabrice Rastello | 3 | 482 | 38.30 |