[LLVMdev] Regalloc Refactoring
greened at obbligato.org
Tue Apr 17 13:48:50 PDT 2007
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
> 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.
More information about the llvm-dev