Wed Mar 15, 2006, 10:30-12pm, 4549 Boelter Hall.

Complexity results for register coalescing.

Fabrice Rastello
ENS Lyon, France

The complexity of register allocation comes from two main
optimizations, spilling and coalescing. The spilling problem is to
decide which variables should be stored in memory so as make register
assignment possible (i.e., the interference graph should be
k-colorable for k registers), while minimizing the cost of stores and
loads.  The coalescing problem is to reduce the cost of moves between
registers as much as possible. For coalescing, we distinguish several
problems that occur in most 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) iterative conservative coalescing tries
to remove one particular move while keeping the colorability of the
graph; d) optimistic coalescing coalesces all moves (when possible),
aggressively, and gives up about as few moves as possible
(de-coalescing) so that the graph becomes colorable. 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).

Host: Jens Palsberg