Re: RFA: patch for register migration

[Daniel Berlin <dberlin at dberlin dot org>]

On Apr 21, 2004, at 1:16 PM, Vladimir Makarov wrote:

> Richard Kenner wrote:
>
> >    The reason for local register allocator is historical.  It makes 
> > all
> >    allocator faster (how fast computers were in 1980).  We can easyly 
> > rid
> >    off the local register allocator (just leave updating equivalent
> >    register optimization from local) and do all work in global.c.
> > I don't follow.  global.c is quadratic.  How would uit be practical to
> > use it to allocate all registers?
>  I don't plan to rid off it.  I think it will not improve code but 
> make compiler slower.  I wrote about this because Dan mentioned that 
> one weak point of the original register allocator is division on local 
> and global allocator.

This is correct, unless your global allocator will undo local decisions 
in the global allocator (and not at spill code time) when it is 
profitable, which ours will not.  And if you are doing that much work, 
you might as well just allocate them all with a global allocator, 
except for spill registers (since it's just as much code and gets rid 
of local-alloc entirely).

>  Actually I am not agree with this.  Bob Morgan (who has particular 
> interest in register allocation) proposed even more passes in his 
> book.

As Andrew suggested, one way to solve this that is to simply run one 
iteration of global coloring, and then do local spilling allocation for 
the spill registers that remain.
There are other approaches as well.
Splitting global and local register allocation as a principal (IE not 
just to allocate spill registers and whatnot) is something no other 
compiler does.
>   Combining compiler passes (combined register allocator, insn 
> scheduling and register allocator, insn scheduiling and code selection 
> and register allocator) is an interesting approach especially when 
> they are looking for optimal solutions.  But IMHO it is in field of 
> researches not in compiler engineering field.
Global graph coloring (be it stopping after a single pass or not) is a 
standard way of doing register allocation in compilers, not a research 
approach.

>   In any case on my opinion global.c without local-alloc.c still will 
> be faster for real programs than the new ra.
This may or may not be true. If you implemented register remat and 
live-range splitting in our spill code generation, it probably would.  
Right now, i seriously doubt it is.  This is because, as i mentioned, 
it's all about spill code. Coloring is easy.  The only problems we have 
with coloring is that local-alloc will make bad decisions that global 
alloc won't undo.
But the better way to fix that (rather than undoing allocations) is to 
just make a good decision in the first place.
But you are welcome to your opinions.


> Vlad