On Wed, 2005-11-23 at 15:05 +0100, Michael Matz wrote:
> > Spill Cost Engine [page(s) 26-29]:
> > * The register allocator should not be estimating the execution
> > frequency of a basic block as 10^nesting level. That information
> > should be coming from the cfg which comes from profile data or
> > from a good static profile. The problem with 10^loop nesting
> > level is that we can overestimate the spill costs for some
> > pseudos. For example:
> > while (...) {
> > <use of "a">
> > if (...)
> > <use of "b">
> > else
> > <use of "b"
> > }
> > In the code above, "b"'s spill cost will be twice that of "a",
> > when they really should have the same spill cost.
>
> Nearly. "b" _is_ more costly to spill, code size wise. All else being
> equal it's better to spill "a" in this case. But the cost is of course
> not twice as large, as you say. I.e. I agree with you that the metric
> should be based exclusively on the BB frequencies attached to the CFG, not
> any nesting level. Also like in new-ra ;)
The spill cost for a pseudo in a classic Chaitin/Briggs allocator does
not take number of spill instructions inserted into account, so "b"'s
spill cost would be twice that of "a" if we were to use 10^nesting
level. That said, I think we're all in agreement that using basic
block frequencies from the cfg is the correct thing to do and that
taking static spill instruction counts into account is a good idea
which Andrew's proposal does by using it as a tie breaker.
I assume it goes without saying that when using -Os, spill cost will
be used as the tie breaker when two pseudos have the same static spill
instruction counts.
Peter
