Re: Looking for conflict graph generators

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

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