[LLVMdev] Removing the bigblock register allocator.

Roman Levenstein romix.llvm at googlemail.com
Thu Jul 30 00:30:55 PDT 2009

2009/7/30 Chris Lattner <clattner at apple.com>:
>> 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.

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

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 ;-)


More information about the llvm-dev mailing list