Re: Register Allocation

[Michael Matz <matz at suse dot de>]

Hi,

On Tue, 22 Nov 2005, Peter Bergner wrote:

> Spill Location Optimizer [page(s) 11]:
>     * The IBM iSeries backend has this optimization.  During spilling,
>       it inserts copies to/from spill pseudos (essentially like another
>       register class) which represent the stores/loads from the stack.
>       These spill pseudos can then be dead code eliminated, coalesced
>       and colored (using an interference graph) just like any other
>       normal pseudo.  Normal Chaitin coloring (using k = infinity) does
>       a good job of minimizing the amount of stack space used for
>       spilled pseudos.

This is btw. also done by the new-ra branch.  Instead of spilling to stack 
directly it spills to special new pseudo regs.  The obvious problem with 
that is a phase ordering problem, namely that if you only have pseudo 
stack locations (the pseudo regs in this case) you don't know the final 
insn sequence (e.g. if the final stack offset happens to be 
unrepresentable so that insns are necessary to actually construct the 
stack address for the load/store).  That's why new-ra leaves the stack 
slots as pseudos only for one round, and then assign real stack positions 
to them (and recolors the possibly new insns and affected pseudos).

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


Ciao,
Michael.