[LLVMdev] BigBlock register allocator

[Evan Cheng]

Thanks Duraid. Nice job.

I'd like to point out a couple of things.

1. The local register allocator is currently broken. :-( Actually it  
has been broken for a while (due to physical sub-regs changes in  
earlier passes. I am currently working on  it. You probably will need  
to merge the fixes back once I am done.
2. Please benchmark against some more "normally sized" programs.  
Perhaps SPEC? I don't expect a local register allocator to win  
against linearscan.

Thanks,

Evan

On Jun 22, 2007, at 2:46 AM, Duraid Madina wrote:

> Hi everyone,
>
> Quick summary:
>
> 	LLVM now has a new register allocator particularly suitable for
> compiling (very) large, machine-generated functions.
>
> Longer story:
>
> 	I've recently been using LLVM in an application that involves JITing
> fairly large functions that have no control flow - they're just flat
> sequences of instructions, anywhere from 100 to 10000+ in size. (The
> control flow is all in the host program, which works out which monster
> function to call and when.)
>
> 	The default (linearscan) register allocator wasn't doing a good  
> job, as
> it doesn't (yet) have live range splitting. It would quickly use all
> available registers and then get stuck, using only a single register
> (and the stack, a lot!) for hundreds or thousands of instructions at a
> time, greatly slowing (+bloating) the code. Luckily, I didn't have the
> presence of mind to actually try using the local register allocator
> before I ripped its guts out, turning it into RegAllocBigBlock.cpp
> that's now in CVS. (Had I done that, I would have been quite happy to
> find that the local allocator produced much better code, much faster
> than linearscan.)
>
> 	The good news is the new "BigBlock" allocator turns out to produce  
> even
> better code than the local allocator when blocks are very large. We're
> talking a +10~20% speed boost on average. (If your basic blocks are
> small, or there's not much register pressure, you'll actually get the
> same code out of both local and BigBlock.)
>
> 	While BigBlock isn't (and never will be) as fast as the local
> allocator, it's not much slower, doesn't use much memory, and is
> certainly faster than linearscan. So if you're compiling very large,
> (probably) machine-generated blocks of straight-line code, give the
> Local and BigBlock allocators a try, especially if you're JITing  
> things
> and compile time is important.
>
> 	If anyone has any problems with or comments on the BigBlock  
> allocator,
> please drop me an email!
>
> 	Enjoy,
>
> 	Duraid
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev