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

Hi all,

I'd like to kill off the bigblock register allocator. Is anyone still using
it?

Cheers,
Lang.

Hi Lang,

There are at least two projects that were using BigBlock, directly or
indirectly.

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
>

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