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

[Quentin Colombet via llvm-dev]

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