[LLVMdev] Regalloc Refactoring

[David Greene]

Chris Lattner wrote:

> 1. Coallesce vregs together as aggressively as possible.  Build huge live 
> ranges, delete as many copies as possible.
> 2. Start priority based register allocation.
> 3. For each live range without a register available, consider:
>     1. live range splitting
>     2. remat
>     3. spilling
> 
> In particular, by doing live range splitting, the *register allocator* can 
> control where the copies go, rather than relying on luck that previous 
> passes introduce copies in convenient places.

Yes, I think that's a good approach.  I was thinking along the same
general lines.

> In practice, right now we have no splitting capability.  In addition, we 
> coallesce physregs with vregs, which can end up pinning a physreg across 
> an entire function even if it has few uses.  This is all very bad, Evan is 
> working on making the coallescer more careful about coallescing vregs with 
> pregs now.

This gets into a discussion I had with Preston Briggs once.  He suggests
doing "pre-coloring" (putting virtuals into physicals for needed
operations like shift on X86) and 2-address transformations within the
register allocator itself.  I'll have to dig up my notes but he
convinced me it was the right way to go.  A previous compiler I worked
on did the 2-address transformation just like LLVM and he pointed out
some weaknesses in that to me.

That's another avenue I'd like to explore in my copious spare time.  :-/

> In the next 6 months or so, I'd like to start investigating a bigger 
> refactoring of linear scan, which will hopefully allow us to build in some 
> of the smarter techniques like aggressive remat, splitting, etc.  The 
> first step to getting that is to make sure the datastructures (e.g. live 
> intervals) are sane.

Great!  Hopefully I'll gain a bunch of experience with regalloc by
then and can contribute some insights.

                                     -Dave