Re: Looking for conflict graph generators

preston@dawn.rice.edu (Preston Briggs)
Fri, 27 Sep 1991 21:47:45 GMT

          From comp.compilers

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)
| List of all articles for this month |

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.