[llvm-dev] Experimental 6502 backend; memory operand folding problem

[Steve Montgomery via llvm-dev]

I have a similar problem with my CPU12 family backend. There are very few instructions that operate on two register operands so I have to force the right-hand operand to be an immediate or load from memory.

I’ve been through several attempts at dealing with this issue but my current favourite is to define pseudo instructions for register-register instructions, e.g. ADD8rr, ADD16rr, SUB8rr, SUB16rr, AND8rr and so on. I then use a pre-RA pass to convert the pseudos into rImm or rMem versions. Some instructions are essentially free to convert because the RHS operand can be rematerialised but in some cases it’s necessary to store to a new stack object and then fold the load into the pseudo instruction to give the rMem version. It’s made more complicated by the fact that some instructions are commutative and some actually do have rr variants but it’s not always most efficient to use them, but that’s not really important to the principle of the approach I’ve taken.

I did try custom lowering and I also tried using preprocessISelDAG() but both those approaches are limited in scope to basic blocks. If you do it after post-ISel then you get to examine the whole function and might be able to make better decisions as to what can be rematerialised and what needs to be spilled to the stack.

It’s been a long time since I used a 6502 so I’m a bit rusty on the instruction set but IIRC it’s not just ADD that gives you this problem. Won’t SUB, CMP, AND, EOR and XOR all have the same issue?

I’ve not seen that assertion failure before so can’t really help, sorry.

Steve

> On 12 Feb 2016, at 09:39, N. E. C. via llvm-dev <llvm-dev at lists.llvm.org> wrote:
> 
> Greetings, LLVM devs,
> 
> For the past few weeks, I have been putting together a 6502 backend for LLVM.
> The 6502 and its derivatives, of course, have powered countless microcomputers,
> game consoles and arcade machines over the past 40 years.
> 
> The backend is just an experimental hobby project right now. The code is
> available here: <https://github.com/beholdnec/llvm-m6502>. This branch
> introduces
> a target called "m6502", which can be used in llc to compile some very simple
> functions. Only a few instructions are implemented, it's not useful for anything
> yet.
> 
> There was another attempt in August of last year by c64scene-ar on GitHub to
> design a 6502 backend, however, the project appears to be stalled with no
> substantial progress. As far as I know, my backend is the only one able to
> generate 6502 instructions.
> 
> Here is a test file: <https://gist.github.com/beholdnec/910eba79391bb24ba2fa>.
> 
> I would like to ask for help as I'm stuck on one particularly sticky problem.
> I'll describe the problem shortly.
> 
> Occasionally, the topic of a 6502 backend comes up on this mailing list. Here
> is an old thread talking about some of the challenges involved:
> <https://groups.google.com/forum/#!topic/llvm-dev/w37MfNU_Ag8>.
> 
> The 6502 has only three 8-bit registers: A, X and Y, and 256 bytes of hardware-
> supported stack. Generating code for such a constrained system pushes LLVM to
> its limits.
> 
> For one thing, LLVM couldn't figure out how to lower an ADD instruction that
> added a reg to a reg. The 6502's ADD instruction can only add register A to an
> immediate or a value loaded from memory. There is no instruction that adds A to
> another register.
> 
> I had thought LLVM would allocate a stack object for the second operand, but
> it didn't, and LLVM threw an ISel matching error. I currently solve this with
> a custom ADD lowering function, see LowerADD in M6502ISelLowering.cpp.
> Question: Is custom lowering ideal for this situation? Or, is there another way
> to coax LLVM into recognizing ADD?
> 
> The problem I'm stuck on is folding memory operands. In the test file above,
> in @testSum, switch %a, %b to %b, %a. llc will assert in Register Spilling:
> "Remaining use wasn't a snippet copy". Debug output shows STRabs being
> generated,
> followed by an attempted fold of a stack-load into ADDabs.
> 
> I must be on the wrong track in M6502InstrInfo::foldMemoryOperandImpl. If
> someone could please explain this error, it would really help. Thanks!
> 
> - Nolan
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev