Re: Effectiveness of coloring: Chaitin-style vs Chow-style

Thomas Johnsson <johnsson@cs.chalmers.se> writes:
[asking about Chow and Chaitin]


>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.


I disagree. If you waste colors on expensive (but trivially colorable)
nodes, you may have to spill in situations where no spilling was required.


Look at it like this. Both Chaitin and Chow divide the nodes in the graph
into two sets: trivial and non-trivial. Then they try and color the
non-trivial nodes first. Chow says all the nodes with degree < k (where k
is the number of registers) are trivially colorable. Chaitin finds his
sets of trivial nodes by removing from the graph all nodes of degree < k.
He continues removing nodes until no nodes of degree < k remain in the
graph. Chaitin's set always includes all the nodes in Chow's set. Thus,
Chow may spill nodes that Chaitin would consider trivial.


Within the remainder of the graph (the non-trivial part), Briggs et al.
(following Chaitin) first remove nodes with low spill cost and high
degree. Thus nodes with high spill cost tend to remain in the graph
longer and be colored earlier, just like Chow.


Preston Briggs
--

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