Fri, 27 Sep 1991 21:47:45 GMT

Related articles |
---|

Looking for conflict graph generators johnsson@cs.chalmers.se (Thomas Johnsson) (1991-09-26) |

Re: Looking for conflict graph generators preston@dawn.rice.edu (1991-09-27) |

Re: Looking for conflict graph generators hankd@ecn.purdue.edu (1991-10-05) |

Re: Looking for conflict graph generators preston@dawn.rice.edu (1991-10-06) |

Newsgroups: | comp.compilers |

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

Keywords: | optimize, theory |

Organization: | Rice University, Houston |

References: | 91-09-076 |

Date: | Fri, 27 Sep 1991 21:47:45 GMT |

Thomas Johnsson <johnsson@cs.chalmers.se> writes:

*>I'm looking for an algorithm, or better yet, a program, which generates*

*>conflict graphs `similar' to those obtained from a graph coloring register*

*>allocator.*

No help here. I don't even know about anyone working on the idea of

`similar' (that is, I don't know about people studying what sorts of

graphs arise from real code).

Some people have done experimental work with random graphs. This is

handy, since it's not too bad to generate random graphs of known chromatic

color. Further, David Turner has shown that a k-coloring for most

k-colorable graphs can be found with a simple, non-backtracking algorithm.

Unfortunately, "most" is out of the (after all, very large) universe of

k-colorable graphs. Further, as k becomes interesting (more than 4 or 5),

the graph needs to be quite large for the algorithm to have much chance.

For the purposes of register allocation, I don't much like measurements

made on random graphs. Real interference graphs aren't that densely

connected, but tend to require a relatively large number of colors. (Just

look at the code and count the maximum liveness. You'll need at least

that many colors.) Results on random graphs tend tend suggest things like

"3 registers are enough to avoid spilling". Don't believe it.

Preston Briggs

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.