Topic:
register allocation
Topic:
graph coloring
| |
Subtopic: history 
| Quote: graph coloring allocator developed for PL.8; simplified the compiler [»auslM6_1982]
|
Subtopic: algorithms
| Quote: improved graph coloring algorithm for register allocation; attempts to color spilled code; 22% cost reduction, especially large routines [»brigP6_1989]
| | Quote: graph-coloring register allocation with register aliases and groups of interchangeable registers; constant time test for trivial colorability
| | Quote: SETL program for register allocation by graph coloring [»chaiGJ6_1982]
|
Subtopic: global register allocation
| Quote: use global register allocation to improve performance; priority-based coloring is practical [»chowFC10_1990]
|
Subtopic: register interference graph
| Quote: represent a register interference graph by a bit matrix and adjacency vectors [»chaiGJ6_1982]
| | Quote: build register interference graph in two passes: bit matrix then adjacency vectors [»chaiGJ2_1986]
|
Subtopic: coalesce nodes
| Quote: coalesce nodes of register interference graph to prevent unnecessary copying [»chaiGJ_1981]
| | Quote: coalesce registers for condition code computations, self modifying operations, and register specific operations [»chaiGJ_1981]
| | Quote: rebuild register interference graph after coalescing symbolic registers
| | Quote: rebuild interference graph after coalescing nodes; two or three iterations, much smaller graphs [»chaiGJ6_1982]
|
Subtopic: chordal graphs
| Quote: register allocation via greedy coloring of chordal graphs; better than iterated register coalescing over a few registers [»pereFM11_2005]
|
Subtopic: spill code
| Quote: except for spilling, graph coloring register allocation did well; avoided spilling by doubling hardware registers to 32 [»auslM6_1982]
| | Quote: 32 registers eliminated most spill code from PL.8; with sixteen registers about half of the routines used spill code
| | Quote: rebuild interference graph after spilling registers; relatively inexpensive [»chaiGJ2_1986]
| | Quote: add spill code if can not n_color the register interference graph
| | Quote: if can not 32-color a graph then add spill code to remove a register node [»chaiGJ6_1982]
|
Subtopic: instruction scheduling
| Quote: register allocation and instruction scheduling can conflict; schedule dependency information can reduce interference in register coloring [»ambrW3_1994]
|
Subtopic: linear scan vs. graph coloring
| Quote: use linear scan for global register allocation; up to several times faster than graph coloring, within 12% as efficient [»poleM9_1999]
| | Quote: if 512 simultaneously live variables, linear scan is 600x faster than graph coloring; due to coloring's O(n^2) time for the interference graph [»poleM9_1999]
|
Subtopic: problems with graph coloring
Quote: graph-coloring usually makes invalid assumptions about register interchangeability and independence
[»smitMD6_2004]
|
Related Topics
Topic: register allocation (28 items)
Topic: graph coloring
(7 items)
|
