Findings

Advantages

With LLVM being as broad as it is, we gain a considerable number of advantages by being a first-class citizen of LLVM, beyond its code generator and optimizer.

Efficiently compiling C to the 6502 is a notoriously difficult problem. LLVM is an amazing platform for building compilers, and we've found that it presents some exciting new solutions, as well as new challenges.

There are two main obstacles when turning C into efficient machine code: stacks and registers.

Stacks

Past a certain point, processors were designed with C and other stack-bearing high-level languages in mind, while the 6502 decidedly predates this. C's runtime model explicitly states that the automatic variables of a function invocation must be kept separately on a per-invocation basis. The only efficient way to do this is with a stack. But the fastest available implementation of a sufficiently-large stack on the 6502 is quite slow, and much slower than the usual zeitgeist of assembly-language programming.

While it's true that the standard C runtime model is quite hostile to 6502 performance, the C standard provides broad latitude for alternative models that behave in all points "as if" it were the C model. In the broad space of possible alternatives, we've found a collection of techniques that broadly preserve C standard compatibility while emitting very high quality code. To put it another way, we go to great lengths to emit code that operates as if there were stacks, without using stacks at all. LLVM's sophistication facilitates this. The analyses required are quite intricate, given that the compiler needs to correctly deal with recursive code as well as interrupt-driven reentrant code, but most of them are slight modifications to data structures already available in LLVM.

Registers

The 6502 has only three relatively general-purpose registers. One is an accumulator, while the other two are index registers. Most instructions bake in which register they operate on, which is quite different than most modern CPUs, which take register numbers in an operand field in the instruction encoding. Since registers are few, it's difficult to keep values in them for any length of time. Additionally, different instructions are constrained to use different registers. Few registers and tight register constraints are both poison to a traditional Chaitin-style register allocator, which causes a proliferation of code to spill values to and from the stack. This in turn requires additional registers, producing a horrible soup of spill-reload-spill-reload.

The original 6502 designers were well aware of the 6502's register limitations, so they provided zero-page addressing modes to compensate. The zero page locations are often treated much like processor registers; we take this view at face value (although we're not the first 6502 compiler to do so). We present ranges of zero page memory to LLVM in the form of imaginary registers.

Instead of keeping instructions like LDA, LDX, and LDY separate, we merge them together into a logical instruction set. This would have one instruction: LD, which takes either A, X, or Y as argument. The distinction is subtle, but this makes the instruction set much more regular, which makes the register allocation problem easier to solve.

Together, these approaches take our backend from "alien nightmare" to "ugly duckling", not unlike x86 or AVR. Normal register allocation techniques apply, since the logical instruction set often treats different zero page locations and processor registers identically. While the instruction set remains a bit unusual, it's not *that* much worse than x86, and LLVM's register allocator is fully capable of handling it, even if the relationship is a bit strained.

ELF

Instead of creating a custom object file format for llvm-mos, we've created an ELF target. While it's not likely that ELF is a good candidate for runtime loading and relocation on the 6502, support for it in POSIX operating systems is excellent. Existing tools like nm and ar can operate on llvm-mos binaries on an abstract level, and the LLVM versions of these tools bundled with the compiler can perform detailed reasoning about the contents. Using ELF gives us access to a whole scope of linker features; weak symbols, garbage collection, and most notably, link-time optimization.

GAS Assembler

The llvm-mos project comes with a powerful GNU-compatible assembler for the 6502, in the form of llvm-mc. All GNU assembler features can now be brought to bear on the 6502: weak symbols, section manipulation primitives, macros, etc. Some of this support extends into the inline assembly fragments understood by Clang, since it uses the underlying assembler to interpret these fragments.

Non-C languages

LLVM IR is used as the primary backend for a number of languages, not just C. Accordingly, the compiler already has a degree of support for C++ and Rust. Accordingly, an opportunity exists to provide 6502 support for languages operating at a considerably higher level of abstraction than C, while still compiling down to relatively efficient machine code.

Challenges

LLVM's complexity is both a blessing and a curse. While the sheer scope of the platform has given us the basis to solve the above problems, working with it is a daunting and complicated task. Much of the really important stuff is barely documented, and much of the compiler's passes are on the level of someone's PhD thesis.

Luckily, all that complexity gives us the support necessary to shoehorn the 6502 into it. It already supports AVR, weird DSP chips, GPUs, and WebAssembly (which doesn't even HAVE registers; it's a stack machine!). It even supports IBM SystemZ! All of the hooks necessary to emit good code for those platforms also help us get good code out of the 6502. We stand on the shoulders of weird, misshapen giants.