Retargeting a C Compiler to 6502#
I’ve written before about cc65 and some of its optimization challenges. It’s a stable compiler with a robust toolchain, but its code generator doesn’t full advantage of the 6502 when performing 8-bit operations. It places function parameters and many local variables on a separate stack, which requires many calls to helper functions.
I’ve done a survey of 6502 high-level languages, and while many are intriguing, none have the stability and C compatiblity of cc65.
So what’s so hard about the 6502? What’s keeping us from just retargeting a modern C compiler, bringing its powerful optimization routines to 6502? Well, it’s complicated. Like, really complicated.
LLVM#
LLVM is the dominant compiler backend library, and there’s documentation on how to write a LLVM backend.
However, many of the instructions read like “draw two circles, then draw the rest of the damn owl”. LLVM is a freakin’ huge library, and backends tend to be complex. It wasn’t designed for 8-bit systems like the 6502 where stack access is cumbersome and registers are scarce.
SDCC#
But what if there were something already in the 8bitworkshop pipeline, right under our nose? Yes, it’s SDCC, the Small Device C Compiler, the same one we use for Z80! What if we could retarget it to the 6502?
The benefit of SDCC is that it already supports a handful of microcontrollers more constrained than the Z80. The Motorola/Freescale HC08 is similar to the 6502 in some ways. It has an 8-bit accumulator and two 8-bit index registers. It also differentiates between direct (0-255, or zero page) and extended (0-65535, or absolute) addressing modes.
Might this be a good start for our own 6502 backend? Let’s find out.
The Test Program#
We’ll use this simple C program to compare compilers:
#include <stdint.h>
#include <stdbool.h>
bool get_pixel(uint_fast8_t x, uint_fast8_t y);
void set_pixel(uint_fast8_t x, uint_fast8_t y);
void fill_line_left(uint_fast8_t x, const uint_fast8_t y) {
for(;; x--) {
if(get_pixel(x, y))
return;
set_pixel(x, y);
}
}
Caveat: This test program is from a research paper about register allocation written by SDCC’s maintainer, so we might be cherry-picking a bit.
The CC65 Version#
Let’s see how CC65 compiles this:
.proc _fill_line_left: near
jsr pusha
ldy #$01
L000E: lda (sp),y
jsr pusha
ldy #$01
lda (sp),y
jsr _get_pixel
tax
bne L0003
ldy #$01
lda (sp),y
jsr pusha
ldy #$01
lda (sp),y
jsr _set_pixel
ldy #$01
lda (sp),y
sec
sbc #$01
sta (sp),y
jmp L000E
L0003: jmp incsp2
CC65 stores its parameters on the stack, requiring an expensive indirect (sp),y instruction.
Note the jsr pusha subroutine calls, which take about 40 cycles each,
used to push parameters on the stack for get_pixel and set_pixel function calls.
The HC08 Target#
HC08 is the backend on which we’ll base the 6502 backend, so let’s see how it does:
_fill_line_left:
stx _fill_line_left_y_1_3
00104$:
psha ;fill.c:9: if(get_pixel(x, y))
ldx _fill_line_left_y_1_3
jsr _get_pixel
tax
pula
tstx
beq 00102$
rts ;fill.c:10: return;
00102$:
psha ;fill.c:11: set_pixel(x, y);
ldx _fill_line_left_y_1_3
jsr _set_pixel
pula ;fill.c:8: for(;; x--) {
deca
bra 00104$
rts
It’s a lot smaller than the CC65 version, and has no indirect loads or parameter pushes. This backend passes two 8-bit parameters in the A and X registers – additional parameters are generally passed in static locations.
It also looks pretty similar to 6502 code, doesn’t it? One might be tempted to convert this directly to 6502 without mucking about in the backend.
The Peephole Assembly Code Translator#
SDCC has a peephole optimizer that we can configure to translate to 6502 code. For example, HC08’s TST instruction can be converted to 6502’s BIT instruction:
tst %0
=
BIT %0
Some HC08 instructions aren’t directly mappable. For example, indirect load of X requires a zero-page pointer:
lda ,x
=
STX ptr
STY ptr+1
LDY #0
LDA (ptr),Y
PHP
LDY ptr+1
PLP
Going down the rabbit hole, we’ll discover that this approach isn’t workable. HC08 isn’t exactly like 6502:
Not little-endian
16-bit index register (HX) vs two 8-bit index registers (X and Y)
Different flag behavior
Additional instructions and addressing modes
So now we’ll go mucking around in the compiler source. Hacking the HC08 backend to produce 6502 code is easy, right?
Figure out what it is doing
Make it do the other thing
Really Doing a Compiler Backend#
Turns out there is a lot involved in “making it do the other thing”, e.g. emitting working 6502 code:
Change big-endian to little-endian.
Modify the register allocator to allocate both X and Y properly.
Make sure to pop/push/transfer registers without clobbering other registers.
Various optimizations:
Use the absolute X/Y indexing modes when possible.
Prefer 16-bit values and pointers to be in zero-page addresses.
Implement bit-shifting logic when multiplying/dividing by powers of two.
Create assembler and linker tools.
Port the standard SDCC library to 6502.
Create a 6502 simulator and test suite.
Fix the broken tests.
After all that and more, we finally get output from the experimental SDCC 6502 backend:
_fill_line_left:
stx _fill_line_left_y_65536_3
pha
ldx _fill_line_left_y_65536_3
jsr _get_pixel
tax
pla
cpx #0x00
beq 00102$
rts
00102$:
pha
ldx _fill_line_left_y_65536_3
jsr _set_pixel
pla
sec
sbc #0x01
jmp 00104$
rts
Yikes#
What kind of obstacles did we run into?
The code base is 20 years old, and the HC08 backend was hacked up by someone other than the author. The maintainer later came back and shoehorned a new, fancy register allocator in C++. The whole thing is hard for mere mortals to understand.
There are lots of special cases to fix – multibyte operations especially.
There’s a test suite, we had to fix many of the examples, as well as bring up a 6502 command-line simulator.
Registers can be free, in use, or dead (free after the current operation).
Pointers required rearranging much of the code, since the HC08 uses a register for indirect access, and the 6502 uses zero-page.
Had to transfer the S -> X register for stack access.
Had to make special case for absolute indexing (
aaaa,xoraaaa,y)Some instructions have addressing limitations, like
BITand shift instructions.PLAmodifies the flags in 6502 land, but not the HC08.Register allocation is a big complex thing that I’m afraid to touch, and when I do ASSERTs are thrown. It actually does a “dry run” compiling multiple times to figure out the optimal register allocation.
Some registers had to be “pushed” onto a temporary zero-page stack, since vanilla 6502 can’t push/pop X or Y.
Needed to keep a pointer to the stack frame in zero page when there’s stuff on the stack.
Memory allocation (calloc of asmops, random freeing of objs)
Regression tests only expose one bug on average, so it goes very slow. There’s one test case per 14,000 lines of code. Had to use my own 6502 simulator to find some bugs.
Longlong routines yuk (found bug in longlong shift functions)
AST operations take lots of arguments (e.g. a == b << c) so tends to be a lot of logic to test.
Endless bugs from transferring registers in the wrong order
Most of the regression tests pass, but even after heroic efforts fixing things, many of them still fail. (“Debugging something into existence” is a phrase that keeps popping into my head.)
If I started from scratch, I’d think about writing a 6502 code generation layer before touching the SDCC backend, that would:
Track register liveness
Track bitmasks/ranges of values
Track equivalences (register == constant, etc)
Choose stack vs. memory for temporaries
Handle multiple register transfers (e.g. X -> A -> Y)
Convert pointers to absolute indexing
Handle 6502 vs 65C02 instructions
Convert long branches to JMP
Try it Out#
You can download the experimental fork of SDCC with 6502 support here:
https://github.com/sehugg/sdcc-m6502
Look at the manual (PDF) for build instructions.