[llvm-dev] Register allocators and constrained classes at -O0

[Andrew Trick via llvm-dev]

> On Jul 21, 2021, at 10:36 PM, Nagurne, James via llvm-dev <llvm-dev at lists.llvm.org> wrote:
> 
> I did find it interesting that you used 'greedy' in the description for the fast allocator, given that there is a 'Greedy' allocator. I also feel that fast seems far greedier.
> 
> Can you or anyone else see an issue with always running the Greedy (tuned Basic) allocator at all optimization levels, or have history as to why Fast was chosen as the default at -O0? I can imagine it might involve the debugability of values as their live ranges are split.

The fast LLVM register allocator is truly on-the fly allocation with minimal analysis and book-keeping.

LLVM register allocator that supports the current "basic" and "greedy" variants should probably be called the "incremental" allocator. The goal was to allow live range splitting in between individual allocation decisions without rerunning any analyses. It's really part of a larger register allocation pipeline that requires significant setup just to get going: SlotIndexes, LiveVariables, LiveIntervals, etc. Then to perform allocation it maintains a LiveIntervalUnion data structure. The live range splitting and register reuse that it performs might also slightly degrade debug information or at least make assembly-level debugging more confusing.

Once you get through the setup, LLVM's incremental allocation itself is pretty fast for an optimizing register allocator (at least for targets that don’t have thousands of physical registers). The basic variant is probably a good choice for first or second level JITs. It was intended to be about as fast as linear scan when spilling/splitting is not required, but avoid linear scan's quadratic behavior when spilling/splitting is required.

The greedy variant adds eviction. This is a form of backtracking, actually making it algorithmically non-greedy--it reverses incremental allocation decisions. (I started using the name because eviction seemed like a "greedy" thing to do in the context of a single allocation decision, and the name regrettably stuck). Eviction can be interleaved with live range splitting and other incremental allocation decisions, making it hard to control the number of steps. I suspect live range splitting can get somewhat out of control for certain CFG structures. I'm sure that would fixable by someone who understands the splitter well enough though.

-Andy
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20210804/a82bd5d8/attachment.html>