Effectiveness of coloring: Chaitin-style vs Chow-style

Thomas Johnsson <johnsson@cs.chalmers.se>
Tue, 13 Apr 1993 08:39:09 GMT

          From comp.compilers

Related articles
Effectiveness of coloring: Chaitin-style vs Chow-style johnsson@cs.chalmers.se (Thomas Johnsson) (1993-04-13)
Re: Effectiveness of coloring: Chaitin-style vs Chow-style preston@dawn.cs.rice.edu (1993-04-13)
| List of all articles for this month |

Newsgroups: comp.compilers
From: Thomas Johnsson <johnsson@cs.chalmers.se>
Keywords: optimize, registers, question
Organization: Compilers Central
Date: Tue, 13 Apr 1993 08:39:09 GMT

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

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)

Post a followup to this message

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