Topic: register allocation by graph coloring

topics > computer science > programming > Group: code generation

register allocation
graph coloring
Subtopic: history up

Quote: graph coloring allocator developed for PL.8; simplified the compiler [»auslM6_1982]

Subtopic: algorithms up

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 up

Quote: use global register allocation to improve performance; priority-based coloring is practical [»chowFC10_1990]

Subtopic: register interference graph up

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 up

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 up

Quote: register allocation via greedy coloring of chordal graphs; better than iterated register coalescing over a few registers [»pereFM11_2005]

Subtopic: spill code up

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 up

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 up

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 up

Quote: graph-coloring usually makes invalid assumptions about register interchangeability and independence

Related Topics up

Topic: register allocation (28 items)
Topic: graph coloring
(7 items)

Updated barberCB 12/04
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.