Re: Looking for conflict graph generators

In article 91-09-086 preston@dawn.rice.edu (Preston Briggs) writes:
>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.
...
>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.


Back in 1987-1988, Chi and I did a fair amount of work in graph-based
register allocation. We wrote a simple program to generate random graphs
where the number of nodes, number of arcs, and the minimum number of
colors (i.e., max live) were independently-specified. Results:


[1] For our random graphs with known max live, optimal colorings
were nearly always found. Hence, the number of colors is
generally max live, perhaps plus 1 or 2.


[2] Max live depends not only on the program being examined, but
also on how you measure liveness. Do globals and array
elements count? Is liveness based on live values, or on live
variable names (using names is wrong, but common, and it
increases the apparent value of max live)? Further, max live
is not invariant wrt to code motions and code scheduling...
do we attempt to minimize max live?


Despite all these differences, typical max live values have
been quoted in many places, and are usually between 5 and 7.
Global compiler analysis & RISC code motions tend to increase
these numbers somewhat....


[3] Although Preston is correct that real graphs are very sparse,
for our studies using random graphs WITHOUT max live specified,
we used very large, dense, graphs.


Our result was that 10-12 registers were enough for the vast
majority of these random graphs (although Chaitin's coloring
scheme needed many more colors). I don't know where Preston
got the number 3, but it wasn't from us....


Our register allocation techniques, both our graph coloring algorithm (a
random walk) and a different scheme which directly minimizes execution
time, were discussed in:


C-H. Chi and H. G. Dietz, "Register Allocation for GaAs Computer
Systems," 1988 Hawaii International Conference on Systems Sciences,
Architecture Track, vol. 1, pp. 266-274, January 1988.


-hankd
--

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