[LLVMdev] Removing the bigblock register allocator.

[Chris Lattner]

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