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

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

Hi Chris,

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 :slight_smile:
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

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.

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 :slight_smile:
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

I'd go even further with your statement as I just cannot resist doing so :slight_smile:

You are right that it shares very little with the commonly published
linear scan algorithms.
Current LLVM linear scan is in fact ... (almost) a tweaked Graph
Coloring register allocation algorithm (!!!) with iterative spilling
and coloring phases and non-iterative coalescing phase. In any case,
it has more common with graph coloring algorithms than with linear
scan algorithms. I could try to explain in in depth, but it would
require a dedicated lengthy post about it.

The fun part of it is that most people in the research community
consider LLVM linear scan to be one of the best Linear Scan
implementations (e.g. based on Wimmer's suggestion, doing very
intelligent live-range splitting, using furthest use information and
so on - all this is wrong!). They use these assumptions, perform
comparisons and claim improvements over linear scan algorithms in
general (based on LLVM's representative example), even though in fact
they unwillingly compare against a tweaked graph coloring allocator in
this case. This is rather unfortunate and only increases overall
misunderstanding related to selection of proper register allocation
algorithms and supports flame wars between GC and linear scan register
allocation algorithms.

Probably, the name of the LLVM LinearScan allocator is really, really
misleading for many people and leads to wrong associations with real
linear scan algorithms. Clearly stating in the LLVM documentation,
what LLVM LinearScan actually is, could be very helpful. Renaming it
could be useful as well.

Just my 2 cents :wink:

-Roman

Agreed. If there haven't been any serious objections to the removal by
tomorrow I'll go ahead and kill it off.

As there were no calls for mercy, the big block allocator has been removed.

Cheers,
Lang.