llvm dev - Jul 2009 - [LLVMdev] Removing the bigblock register allocator.

On Jul 29, 2009, at 3:14 PM, Roman Levenstein wrote:
> Hi Lang,
>
> There are at least two projects that were using BigBlock, directly or
> indirectly.
Hi Roman,

We have many plans to rip out linscan and replace it with something  
that handles large blocks better.  That's not the issue :).  The  
problem is that bigblock is unmaintained and bitrotted.  Since noone  
is working on it, it doesn't work, and it is a maintenance burden, I  
think it should be removed.

-Chris
>
> One approach is described in the paper "Register Spilling and
> Live-Range Splitting for SSA-Form Programs" by Matthias Braun and
> Sebastian Hack.
> It can be found here:
> http://pp.info.uni-karlsruhe.de/publication.php?id=braun09cc
> http://pp.info.uni-karlsruhe.de/uploads/publikationen/braun09cc.pdf
> This approach uses an approach similar to the BigBlock allocator (i.e.
> the MIN algorithm), but extends it from basic blocks to the whole CFG
> of a function and does it at the SSA level. The implementation is
> available as part of the libFirm project.
>
> Another research project can be found here:
> http://www.contrib.andrew.cmu.edu/~jbauman/15745/
> It seems to be based on LLVM's BigBlock and takes some inspiration
> from the paper mentioned above.
>
> In both cases, register allocators produce results that are quite
> comparable or even significantly better than LLVM's linear scan
> register allocator, in particular when it comes to the amount of
> loads/stores introduced due to spilling. Braun/Hack allocator also
> outperforms graph-coloring algorithms according to this metric.
>
> Taking this into account, it seems that BigBlock can be extended into
> something useful, if these researchers would contribute their code or
> someone would extend BigBlock using their papers as a basis.
>
> So, unless there is a really important reason to remove the BigBlock
> register allocator, I'd suggest keeping it in the source tree.
>
> Best regards,
>  Roman
>
> 2009/7/29 Lang Hames <lhames at gmail.com>:
>> Hi all,
>>
>> I'd like to kill off the bigblock register allocator. Is anyone  
>> still using it?
>>
>> Cheers,
>> Lang.
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Hi Chris,

2009/7/30 Chris Lattner <clattner at apple.com>:
>
> On Jul 29, 2009, at 3:14 PM, Roman Levenstein wrote:
>
>> Hi Lang,
>>
>> There are at least two projects that were using BigBlock, directly or
>> indirectly.
>
> Hi Roman,
>
> We have many plans to rip out linscan and replace it with something
> that handles large blocks better.  That's not the issue :).
As far as I know, we have these ambitious plans since a while (just X
years), but there is no good replacement for a LLVM linear scan yet :)
The alternatives are either slower at compile time or generate slower code.

BTW, the research papers that I mentioned are not about improving
register allocation for large blocks (which was the target in the case
of BigBlock). They are about register allocation for general purpose
CFGs. And they report improvements (greatly reduced number of
load/stores for spills) over linear scan. The compilation time is also
comparable with linear scan. So, independent of the BigBlock
discussion they are worse looking at.
> The problem is that bigblock is unmaintained and bitrotted.  Since noone
> is working on it, it doesn't work, and it is a maintenance burden, I
> think it should be removed.
I see the point and have no strong opinion here. Obviously, keeping
something unmaintained in the mainline just because it could be
potentially improved does not make too much sense. After all, if there
will be such an improvement of the BigBlock, it can be integrated back
into the mainline again.

-Roman
>>
>> One approach is described in the paper "Register Spilling and
>> Live-Range Splitting for SSA-Form Programs" by Matthias Braun and
>> Sebastian Hack.
>> It can be found here:
>> http://pp.info.uni-karlsruhe.de/publication.php?id=braun09cc
>> http://pp.info.uni-karlsruhe.de/uploads/publikationen/braun09cc.pdf
>> This approach uses an approach similar to the BigBlock allocator (i.e.
>> the MIN algorithm), but extends it from basic blocks to the whole CFG
>> of a function and does it at the SSA level. The implementation is
>> available as part of the libFirm project.
>>
>> Another research project can be found here:
>> http://www.contrib.andrew.cmu.edu/~jbauman/15745/
>> It seems to be based on LLVM's BigBlock and takes some inspiration
>> from the paper mentioned above.
>>
>> In both cases, register allocators produce results that are quite
>> comparable or even significantly better than LLVM's linear scan
>> register allocator, in particular when it comes to the amount of
>> loads/stores introduced due to spilling. Braun/Hack allocator also
>> outperforms graph-coloring algorithms according to this metric.
>>
>> Taking this into account, it seems that BigBlock can be extended into
>> something useful, if these researchers would contribute their code or
>> someone would extend BigBlock using their papers as a basis.
>>
>> So, unless there is a really important reason to remove the BigBlock
>> register allocator, I'd suggest keeping it in the source tree.
>>
>> Best regards,
>>  Roman
>>
>> 2009/7/29 Lang Hames <lhames at gmail.com>:
>>> Hi all,
>>>
>>> I'd like to kill off the bigblock register allocator. Is anyone
>>> still using it?
>>>
>>> Cheers,
>>> Lang.
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

Hi Roman,
> BTW, the research papers that I mentioned are not about improving
> register allocation for large blocks (which was the target in the case
> of BigBlock). They are about register allocation for general purpose
> CFGs. And they report improvements (greatly reduced number of
> load/stores for spills) over linear scan. The compilation time is also
> comparable with linear scan. So, independent of the BigBlock
> discussion they are worse looking at.
There are definitely some interesting alternatives to linear scan out
there. I'm currently working to improve our register allocation
framework, and one of our goals is to make it easier for people to
implement other allocators in LLVM. Hopefully this will encourage
contributions.
>> The problem is that bigblock is unmaintained and bitrotted.  Since
noone
>> is working on it, it doesn't work, and it is a maintenance burden,
I
>> think it should be removed.
>
> I see the point and have no strong opinion here. Obviously, keeping
> something unmaintained in the mainline just because it could be
> potentially improved does not make too much sense. After all, if there
> will be such an improvement of the BigBlock, it can be integrated back
> into the mainline again.
Agreed. If there haven't been any serious objections to the removal by
tomorrow I'll go ahead and kill it off.

Cheers,
Lang.

On Jul 29, 2009, at 10:31 PM, Roman Levenstein wrote:
> As far as I know, we have these ambitious plans since a while (just X
> years), but there is no good replacement for a LLVM linear scan yet :)
> The alternatives are either slower at compile time or generate  
> slower code.
Sure, we've been able to make the current algorithm significantly  
better over the years.  However, we're getting more serious about  
actually doing something about the core algorithms.
> BTW, the research papers that I mentioned are not about improving
> register allocation for large blocks (which was the target in the case
> of BigBlock). They are about register allocation for general purpose
> CFGs. And they report improvements (greatly reduced number of
> load/stores for spills) over linear scan.
Sure, we won't keep the linscan algorithm.  The current LLVM linscan  
implementation is not linear time in any case, and shares little with  
the commonly published algorithms.

-Chris