Re: Looking for conflict graph generators

In article 91-10-020 hankd@ecn.purdue.edu (Hank Dietz) writes:


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


We only care about max live when register allocation is performed (after
optimization, ...). It should be calculated in terms of the number of
values subject to register allocation (since register allocation is the
point here). Generally, this means scalar variables, though temps arising
during optimization of address expressions are an important source of
allocation fodder. Recent high-payoff optimizations, such as scalar
replacement (allocating array elements in scalar variables), also
contribute remarkable amounts of pressure.


Further, max liveness is not the only consideration.


Imagine I have a little routine with a max liveness of 5 integer values.
With 8 integer registers, this should be no problem, right? But the
routine has a procedure call in the middle, and the calling conventions
say that registers 4..7 are killed. Max live hasn't changed, but we may
have to spill around the call.


Or suppose that the calling convention specifies that that the 1st
parameter be passed in R0 and the 2nd in R1. That's ok, except when an
incoming parameter (in R0) has to move (say to R1) or the same value is
passed in different parameter positions (first R0 and then R1).


Or suppose we have the luxury of a multiply instruction, but it requires
it's operands in registers R0 and R1.


Many other examples arise, even on relatively clean RISC machines. They
aren't really that difficult (that is, Chaitin gives solutions), but they
mean that minimum chromaticity can be much higher than max liveness.


Finally, it's easy to show examples where max live is large relative to
the number of registers available. Consider, at your leisure, the routine
twldrv.f, in the SPEC benchmark program fpppp.


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


But what is the connection between random "very large, dense graphs" and
the interference graphs we see when allocating registers?


Also recall that Chaitin's coloring scheme has been improved since your
tests. Comparisons with Chaitin's '82 work haven't been very interesting
since our '89 paper.


Preston Briggs
--

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