Effectiveness of coloring: Chaitin-style vs Chow-style

Here is something that has puzzled me, regarding the effectiveness of
Chaitin style graph coloring vs Chow style priority based coloring.


In Chaitin's original coloring scheme, nodes which have degree < N (N
being the number of available registers) are deleted from the graph,
together with the incident arcs, because such nodes are trivially
colorable. If one comes to a point where all nodes have degree >= N, some
node is chosen for spilling, and the deletion continues (In a modification
of this, a node is simply chosen for deletion anyway -- I think this is
what Preston Briggs does). Nodes are colored in reverse order in which
they were deleted from the graph.


In Chow style priority based coloring, nodes are basically colorored in
order highest priority first, where the priority is set by the estimated
runtime gain by allocating the variable to a register.


In the (modified) Chaitin scheme, coloring order basically becomes: high
pressure regions first -- an order which is different from the priority
order.


All other things being equal (i.e., ignoring issues of subsumption, live
range splitting, etc) I would have thought that it would always be more
beneficial to color the high gain nodes first, irrespective of how many
other nodes that the node-to-be-colored conflicts with.


True or not?


-- Thomas Johnsson (johnsson@cs.chalmers.se)
--

Return to the comp.compilers page.
Search the comp.compilers archives again.