|Looking for conflict graph generators firstname.lastname@example.org (Thomas Johnsson) (1991-09-26)|
|Re: Looking for conflict graph generators email@example.com (1991-09-27)|
|Re: Looking for conflict graph generators firstname.lastname@example.org (1991-10-05)|
|Re: Looking for conflict graph generators email@example.com (1991-10-06)|
|From:||firstname.lastname@example.org (Preston Briggs)|
|Organization:||Rice University, Houston|
|Date:||Fri, 27 Sep 1991 21:47:45 GMT|
Thomas Johnsson <email@example.com> 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
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.
Return to the
Search the comp.compilers archives again.