Tue, 13 Apr 1993 19:37:54 GMT

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

Newsgroups: | comp.compilers |

From: | preston@dawn.cs.rice.edu (Preston Briggs) |

Keywords: | optimize, registers |

Organization: | Rice University, Houston |

References: | 93-04-046 |

Date: | Tue, 13 Apr 1993 19:37:54 GMT |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.