[llvm-dev] Register spilling fix for experimental 6502 backend

[N. E. C. via llvm-dev]

Thank you for pointing me to getLargestLegalSuperClass, implementing
this is adequate to fix the reg allocation problem without patching
LLVM's register allocator.

It is understandable that I should avoid touching the Reg Allocator,
as doing so might potentially break other backends.

Nolan Check

On Mon, Feb 15, 2016 at 10:36 AM, Quentin Colombet <qcolombet at apple.com> wrote:
> Hi Nolan,
>
> One thing you could try is to define a register class that is the union of X and Acc.
> That register class would be used for spill and reload instructions.
> In other words, both store and load would use the “same" register class.
>
> By doing so, you shouldn’t need to patch any of the RA pipeline.
>
> Cheers,
> -Quentin
>> On Feb 13, 2016, at 2:54 PM, N. E. C. via llvm-dev <llvm-dev at lists.llvm.org> wrote:
>>
>> So I've been designing an experimental 6502 backend for LLVM. Link:
>> <https://github.com/beholdnec/llvm-m6502>
>>
>> The 6502 only has a few registers, one accumulator and two indexes, none of
>> which are large enough to hold an absolute pointer. Because of this, the
>> backend really tests the power of LLVM's register allocator (RA).
>>
>> I've made a change to the RA that might be of interest to devs of other
>> backends, read on.
>>
>> Other devs suggested reserving the zero page of memory (addresses $00-$FF) and
>> treating it as a giant set of registers. And I don't know, because doesn't that
>> sort of defeat the purpose of register allocation? It might be inevitable that
>> we have to lie to LLVM about the 6502's registers, but, for now, I want to see
>> how far I can get using the allocator as intended.
>>
>> The registers are A, X, and Y. They belong to a hierarchy of Register Classes:
>>  Acc class: A
>>  Index class: X, Y
>>  General class: Acc, Index
>>
>> There's a fictional instruction "SUBidx Acc, Index". It subtracts an Index from
>> an Acc. Bear with me.
>>
>> What if we want to subtract A from X?
>> We can't say "SUBidx X, A". The operands must be Acc, Index.
>>
>> The DAG looks something like this:
>>
>>  %vreg2 = COPY %X ; %vreg2 is Index
>>  %vreg0 = COPY %A ; %vreg0 is Acc
>>  SUBidx %vreg2, %vreg0
>>
>> To make this work, we first have to swap A and X.
>> For technical reasons, we can't use Y as temporary storage. Instead, we must
>> spill to the stack.
>>
>> When spilling a reg to the stack, the RA needs two virtual regs, one to store
>> and one to load. Currently, the loaded reg always has the same class as the
>> stored reg. Because of this limitation, I ran into a problem: the RA would try
>> to assign two Accs to physical regs, but only one is available, and the RA
>> would fail.
>>
>> Line 1290 of InlineSpiller.cpp, inside the function spillAroundUses, says:
>> "// FIXME: Infer regclass from instruction alone"
>> (As opposed to the current behavior of always using the same class as the reg
>> being spilled.)
>> The line refers to this very limitation. It was written in 2010, so we've known
>> about the limitation since the beginning.
>>
>> My RA patch can be found in this commit:
>> <https://github.com/beholdnec/llvm-m6502/commit/a4b492f63>
>>
>> This patch allows spills to use a more general reg class, so a spilled Acc can
>> be reloaded as a General.
>>
>> Previously, the RA would fail because it would spill X, but it couldn't reload
>> X into an Acc.
>>
>> Now, with the patch, the DAG compiles into this:
>>
>>  # store X to stack
>>  STX_stack [0]
>>  # transfer A to X
>>  TAX
>>  # load A from stack
>>  LDA_stack [0]
>>  # now that A and X are swapped, we can subtract!
>>  SUBidx A, X
>>
>> It works, but I'm not sure if I used the best approach. If you're familiar with
>> the RA, feel free to look at the patch and leave feedback.
>>
>> - Nolan
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>