[LLVMdev] BigBlock register allocator

[Duraid Madina]

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