[LLVMdev] Greedy register allocation

[David A. Greene]

Jakob Stoklund Olesen <stoklund at 2pi.dk> writes:

>> Yikes!  Do we know why these codes got so much worse?  Even 5% is a big
>> deal on x86.
>
> On x86-64, n-body and puzzle have the exact same instructions as with
> linear scan. The only difference is the choice of registers. This
> causes some loops to be a few bytes longer or shorter which can easily
> change performance by that much if that small loop is all the
> benchmark does.

Ok, I can believe that.

> The greedy allocator is trying to pick registers so inner loops are as
> small as possible, but that is not always the right thing to do.

How does it balance that against spill cost?

> Unfortunately, we don't model the effects of code alignment, so there
> is a lot of luck involved.

As with any allocator.  :)

> I am working my way through the regressions, looking for things the
> allocator did wrong. Any help is appreciated, please file bugs if you
> find examples of stupid register allocation.

Certainly.  I would ask that we keep linearscan around, if possible, as
long as there are significant regressions like this.  Our customers tend
to really, really care about performance.

                             -Dave