Graph-coloring register allocators eliminate copies by coalescing the
source and target node of a copy if they do not interfere in the
interference graph. Coalescing is, however, known to be harmful to the
colorability of the graph because it tends to yield a graph with nodes
of higher degrees. Unlike aggressive coalescing which coalesces any
pair of non-interfering copy-related nodes, conservative coalescing or
iterated coalescing perform safe coalescing that preserves the
colorability. Unfortunately, these heuristics give up coalescing too
early, losing many opportunities of coalescing that would turn out to
be safe. Moreover, they ignore the fact that coalescing may even
improve the colorability of the graph by reducing the degree of
neighbor nodes that are interfering with both the source and target
nodes being coalesced.  This paper proposes a new heuristic called
optimistic coalescing which optimistically performs aggressive
coalescing, thus fully exploiting the positive impact of coalescing,
yet when a coalesced node is to be spilled, it is split back into
separate nodes; there is a better chance of coloring one of them which
reduces the overall spill cost.
<p>

KEYWORDS: Register allocation, copy coalescing, instruction scheduling,
renaming

<p><hr>

The author's web site:
<a href="http://altair.snu.ac.kr">http://altair.snu.ac.kr</a>