[llvm-dev] Register spilling fix for experimental 6502 backend
N. E. C. via llvm-dev
llvm-dev at lists.llvm.org
Mon Feb 15 23:09:21 PST 2016
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.
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.
>> 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:
>> 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:
>> 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 
>> # transfer A to X
>> # load A from stack
>> LDA_stack 
>> # 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
More information about the llvm-dev