7 ms·

Explaining my fast 6502 code generator

217 points by pubby 4y ago

deterministic 4y ago
Excellent read. I am a pro compiler developer and I learned quite a few things from the article.
commandlinefan 4y ago
> my compiler generates faster code than GCC, LLVM, and every other compiler I compared it to GCC and LLVM can target the 6502?!?
- binarycrusader 4y ago
  For LLVM, I don’t think it’s in the official repo, but yes: https://github.com/llvm-mos/llvm-mos https://github.com/llvm-mos/llvm-mos
  - pubby 4y ago
    I think it's possible LLVM-MOS gets into mainline LLVM eventually. The devs have done a good job getting all the kinks ironed out. BTW, mysterymath, one of the most prominent LLVM-MOS contributors, left this comment on their current code gen. (I'm posting it here for visibility): "In LLVM-MOS, we mainly struggle with its register allocator; the rest of the backend is really quite reasonable. The "Greedy register allocator" in LLVM is a just finely tuned priority allocator with nice live-range splitting. It works great for zero page cache locations, but it's just not tuned very well for tight register classes like those involving the processor's three architectural registers. I've half a mind to implement Hack's SSA-based register allocator in LLVM to use on A, X, and Y; this would clean up the oodles of spurious copies LLVM-MOS spits out in the worst cases."
- acuozzo 4y ago
  GCC: Via an old, unofficial port: https://github.com/itszor/gcc-6502 https://github.com/itszor/gcc-6502
thechao 4y ago
This is a Massalin superoptimizer.
- pubby 4y ago
  From a quick skim of Massalin's paper, they seem similar in how they generate combinations of instructions and prune, but different in other areas. Superoptimizer spews out every combination of instruction (even invalid ones) in a search for true optimality, and uses boolean logic + emulation to determine equivalent code sequences to prune. 6502 algorithm only generates combinations it knows will work, and uses a symbolic approach to determine equivalence. Its results are not always optimal, and portions like the PBQP stuff is obviously different.
  - peterfirefly 4y ago
    I think you'll be (very!) interested in e-graphs: https://en.wikipedia.org/wiki/E-graph https://en.wikipedia.org/wiki/E-graph Google fodder: "Equality Saturation: A New Approach to Optimization" "Denali: A Goal-directed Superoptimizer" "Z3: An Efficient SMT Solver" "Efficient E-matching for SMT Solvers" "egg: Fast and Extensible Equality Saturation" "Rewrite Rule Inference Using Equality Saturation"
  - ant6n 4y ago
    It also only uses one possible ordering for the IR instructions? Still a nice result. It looks like a dynamic programming solution to code generation. Next to the game boy. ;-)
    - ant6n 4y ago
      It’s probably possible to incorporate all possible orderings of instructions, if the set of already computed instructions is part of the state of the dynamic programming algorithm.
ecpottinger 4y ago
This does far more than I did back in my PET and then Amiga days, but one thing I did was write a multi-pass compiler. Each pass at first found ways to make the come better (usually smaller so it ran faster). Even simple code I wrote could see a 10-20% improvement. Of-course, this is because the original code was quick and dirty. I wonder what improvement modern compilers could have added.
- fernly 4y ago
  Geez, 25 years ago I was being boggled by how sophisticated was the code generated by the C compiler we shipped at SGI. For the MIPS architecture, as for most contemporary architectures, re-ordering memory accesses to minimize cache misses was FAR more important to execution speed than the specific selection of machine instructions. Of course for early MIPS there were little things like, don't put a jump in the last word of a 4K page... :-(
  - dwheeler 4y ago
    6502 also had some "little things". E.g., it's jump indirect didn't work across page boundaries: http://www.6502.org/tutorials/6502opcodes.html#JMP http://www.6502.org/tutorials/6502opcodes.html#JMP
ajross 4y ago
Bookmarked this to read about optimizers, because it looks great. That said, I clicked on the link because it had "6502" in the title. And... this isn't very interesting as a retrocomputing activity. To be blunt: there's absolutely no way in hell a compiler architecture like that is ever going to be self-hosting in 64k of memory space.
- geon 4y ago
  Who in their right mind would self host 6502 development?
  - spc476 4y ago
    Plenty of teenagers in the 80s writing games for the various home computers at the time (Apple ][, Atari 400 & 800, Commodore 64).
    - jlokier 4y ago
      That waa me. My 6502 "IDE" was a BBC Micro, with it's excellent BBC BASIC ROM that had inline 6502 assembler built-in to the BASIC language. It was so good and accessible, and documented in the Advanced User Guide, that after learning BASIC starting age 10, I learned 6502 a few months later and was able to reverse engineer and modify other people's games not long after that. I had the luxury of floppy drives which my contemporaries did not have The floppies helped immensely with self-hosted development of larger programs. Imagine losing all your assembler work due to a crash running it because it was tempting to skip rhe time of several minutes saving to tape. Floppies were reasonably fast for saving before running things, but few people I knew had them. It also gained a Z80 second processor (an add-on; and later a 68000), so rhe Z80 helped with development of 6502 code, as a RAM disk and editing scratchpad that survived 6502 crashes. And for running Wordstar, which was a decent editor. Eventually I had someone else's ZX Spectrum hooked up to the BBC with a kind of home-made bit-banging serial port. That's when things started getting fancy, as my BBC's Z80 second processor's flavour of BBC BASIC could assemble Z80 code for the Spectrum, and run some Z80 binaries from other people's Spectrum software, with the BBC's 6502 providing display and sound emulation.
billyjobob 4y ago
All the other compilers in the comparison are C compilers, right? Whereas this compiler is compiling its own home made language? So not sure how the comparison can be valid.
- pubby 4y ago
  FWIW the custom language is very close to C, and the examples are pretty much a 1-1 transposition. I agree with you though on a different note. It's dubious to compare compilers by benchmarking them, because tests are highly arbitrary and are won/lost based on single weak links. It's not really an exact science, but rather something you can start with to figure out how things are behaving. I mostly base my opinions by looking at the assembly code each compiler generates, but a single bar graph is a better presentation for articles.
  - matt_d 4y ago
    It could be fun to compare with Action!--it's been known to compile a reasonably good 6502 assembly (considerably better than other compiled languages for that platform), https://en.wikipedia.org/wiki/Action!_(programming_language) https://en.wikipedia.org/wiki/Action!_(programming_language), It has been released as open-source together with the binaries, https://atariwiki.org/wiki/Wiki.jsp?page=Action https://atariwiki.org/wiki/Wiki.jsp?page=Action You should be able to run these using an Atari 8-bit (XL/XE model) emulator, like Atari800, https://github.com/atari800/atari800/releases https://github.com/atari800/atari800/releases or Altirra, https://www.virtualdub.org/altirra.html https://www.virtualdub.org/altirra.html
- mmphosis 4y ago
  I think NESFab is a medium level programming language targeting the NES 6502. On NES, the Decimal flag has no effect. GNU Compiler Collection no longer targets 6502, but an older version of the GNU C Compiler could. LLVM targeting 6502 is limited. There is also the cc65 cross compiler. [1] LLVM [2] and GCC [3] are compiler and toolchain technologies. The name Low Level Virtual Machine (LLVM) is no longer officially an acronym, and the GNU C Compiler is now the GNU Compiler Collection (GCC). [1] https://www.cc65.org/ https://www.cc65.org/ [2] https://www.llvm.org/ https://www.llvm.org/ [3] https://gcc.gnu.org/ https://gcc.gnu.org/
Scaevolus 4y ago
Does this code generator spill to zero-page? Do you have to do anything special for allocations there?
- pubby 4y ago
  Since it combines register allocation with instruction spilling is innate - there isn't a special spilling phase. Spilled variables are assigned ram addresses after code generation occurs at link time, with the most frequently used going to zeropage.
  - coldacid 4y ago
    Does it avoid ZP addresses with special purpose for the system when doing this?
    - pubby 4y ago
      Yeah it can reserve specific ZP addresses. I do this to implement the runtime. It can also be used to reserve hardware registers, but since my only target is the NES, I don't have to worry about that.
nstbayless 4y ago
I may have misunderstood, but I believe step 1 (eliding loads) is simply a cache scheduling problem. The optimal solution is the greedy "furthest in the future" eviction policy.
- pubby 4y ago
  That's an excellent point. I hadn't heart of furthest in the future, but it looks like it does solve step 1. Past that though, it doubt it can be used because each of the 6502's registers are different and don't support the same operations. It's a good idea though, and might work for some specific RISC architecture where all registers behave the same.
- quag 4y ago
  Is [1] a good way to learn about furthest in the future eviction? [1]: https://blog.henrypoon.com/blog/2014/02/02/proof-of-the-farthest-in-future-optimal-caching-algorithm/ https://blog.henrypoon.com/blog/2014/02/02/proof-of-the-fart...
  - nstbayless 4y ago
    I found that article quite confusing. I think these slides are clearer: https://courses.cs.washington.edu/courses/cse421/18au/lecture/lecture-8.pdf https://courses.cs.washington.edu/courses/cse421/18au/lectur... (provided you know about induction already.)
userbinator 4y ago
I'd like to see this same technique applied to x86, and what the performance is like without the "illegal instructions" (omitting them from generation would probably be trivial). It's relatively well known that one of the ways Asm programmers can beat compilers is on instruction selection, and that's what this technique seems to excel at.
turbobooster 4y ago
Can this make games for NES?

217 points by pubby 4y ago

Excellent read. I am a pro compiler developer and I learned quite a few things from the article.

> my compiler generates faster code than GCC, LLVM, and every other compiler I compared it to GCC and LLVM can target the 6502?!?

binarycrusader 4y ago
For LLVM, I don’t think it’s in the official repo, but yes: https://github.com/llvm-mos/llvm-mos https://github.com/llvm-mos/llvm-mos
- pubby 4y ago
  I think it's possible LLVM-MOS gets into mainline LLVM eventually. The devs have done a good job getting all the kinks ironed out. BTW, mysterymath, one of the most prominent LLVM-MOS contributors, left this comment on their current code gen. (I'm posting it here for visibility): "In LLVM-MOS, we mainly struggle with its register allocator; the rest of the backend is really quite reasonable. The "Greedy register allocator" in LLVM is a just finely tuned priority allocator with nice live-range splitting. It works great for zero page cache locations, but it's just not tuned very well for tight register classes like those involving the processor's three architectural registers. I've half a mind to implement Hack's SSA-based register allocator in LLVM to use on A, X, and Y; this would clean up the oodles of spurious copies LLVM-MOS spits out in the worst cases."
acuozzo 4y ago
GCC: Via an old, unofficial port: https://github.com/itszor/gcc-6502 https://github.com/itszor/gcc-6502

thechao 4y ago

This is a Massalin superoptimizer.

pubby 4y ago
From a quick skim of Massalin's paper, they seem similar in how they generate combinations of instructions and prune, but different in other areas. Superoptimizer spews out every combination of instruction (even invalid ones) in a search for true optimality, and uses boolean logic + emulation to determine equivalent code sequences to prune. 6502 algorithm only generates combinations it knows will work, and uses a symbolic approach to determine equivalence. Its results are not always optimal, and portions like the PBQP stuff is obviously different.
- peterfirefly 4y ago
  I think you'll be (very!) interested in e-graphs: https://en.wikipedia.org/wiki/E-graph https://en.wikipedia.org/wiki/E-graph Google fodder: "Equality Saturation: A New Approach to Optimization" "Denali: A Goal-directed Superoptimizer" "Z3: An Efficient SMT Solver" "Efficient E-matching for SMT Solvers" "egg: Fast and Extensible Equality Saturation" "Rewrite Rule Inference Using Equality Saturation"
- ant6n 4y ago
  It also only uses one possible ordering for the IR instructions? Still a nice result. It looks like a dynamic programming solution to code generation. Next to the game boy. ;-)
  - ant6n 4y ago
    It’s probably possible to incorporate all possible orderings of instructions, if the set of already computed instructions is part of the state of the dynamic programming algorithm.

ecpottinger 4y ago

This does far more than I did back in my PET and then Amiga days, but one thing I did was write a multi-pass compiler. Each pass at first found ways to make the come better (usually smaller so it ran faster). Even simple code I wrote could see a 10-20% improvement. Of-course, this is because the original code was quick and dirty. I wonder what improvement modern compilers could have added.

fernly 4y ago
Geez, 25 years ago I was being boggled by how sophisticated was the code generated by the C compiler we shipped at SGI. For the MIPS architecture, as for most contemporary architectures, re-ordering memory accesses to minimize cache misses was FAR more important to execution speed than the specific selection of machine instructions. Of course for early MIPS there were little things like, don't put a jump in the last word of a 4K page... :-(
- dwheeler 4y ago
  6502 also had some "little things". E.g., it's jump indirect didn't work across page boundaries: http://www.6502.org/tutorials/6502opcodes.html#JMP http://www.6502.org/tutorials/6502opcodes.html#JMP

ajross 4y ago

Bookmarked this to read about optimizers, because it looks great. That said, I clicked on the link because it had "6502" in the title. And... this isn't very interesting as a retrocomputing activity. To be blunt: there's absolutely no way in hell a compiler architecture like that is ever going to be self-hosting in 64k of memory space.

geon 4y ago
Who in their right mind would self host 6502 development?
- spc476 4y ago
  Plenty of teenagers in the 80s writing games for the various home computers at the time (Apple ][, Atari 400 & 800, Commodore 64).
  - jlokier 4y ago
    That waa me. My 6502 "IDE" was a BBC Micro, with it's excellent BBC BASIC ROM that had inline 6502 assembler built-in to the BASIC language. It was so good and accessible, and documented in the Advanced User Guide, that after learning BASIC starting age 10, I learned 6502 a few months later and was able to reverse engineer and modify other people's games not long after that. I had the luxury of floppy drives which my contemporaries did not have The floppies helped immensely with self-hosted development of larger programs. Imagine losing all your assembler work due to a crash running it because it was tempting to skip rhe time of several minutes saving to tape. Floppies were reasonably fast for saving before running things, but few people I knew had them. It also gained a Z80 second processor (an add-on; and later a 68000), so rhe Z80 helped with development of 6502 code, as a RAM disk and editing scratchpad that survived 6502 crashes. And for running Wordstar, which was a decent editor. Eventually I had someone else's ZX Spectrum hooked up to the BBC with a kind of home-made bit-banging serial port. That's when things started getting fancy, as my BBC's Z80 second processor's flavour of BBC BASIC could assemble Z80 code for the Spectrum, and run some Z80 binaries from other people's Spectrum software, with the BBC's 6502 providing display and sound emulation.

billyjobob 4y ago

All the other compilers in the comparison are C compilers, right? Whereas this compiler is compiling its own home made language? So not sure how the comparison can be valid.

pubby 4y ago
FWIW the custom language is very close to C, and the examples are pretty much a 1-1 transposition. I agree with you though on a different note. It's dubious to compare compilers by benchmarking them, because tests are highly arbitrary and are won/lost based on single weak links. It's not really an exact science, but rather something you can start with to figure out how things are behaving. I mostly base my opinions by looking at the assembly code each compiler generates, but a single bar graph is a better presentation for articles.
- matt_d 4y ago
  It could be fun to compare with Action!--it's been known to compile a reasonably good 6502 assembly (considerably better than other compiled languages for that platform), https://en.wikipedia.org/wiki/Action!_(programming_language) https://en.wikipedia.org/wiki/Action!_(programming_language), It has been released as open-source together with the binaries, https://atariwiki.org/wiki/Wiki.jsp?page=Action https://atariwiki.org/wiki/Wiki.jsp?page=Action You should be able to run these using an Atari 8-bit (XL/XE model) emulator, like Atari800, https://github.com/atari800/atari800/releases https://github.com/atari800/atari800/releases or Altirra, https://www.virtualdub.org/altirra.html https://www.virtualdub.org/altirra.html
mmphosis 4y ago
I think NESFab is a medium level programming language targeting the NES 6502. On NES, the Decimal flag has no effect. GNU Compiler Collection no longer targets 6502, but an older version of the GNU C Compiler could. LLVM targeting 6502 is limited. There is also the cc65 cross compiler. [1] LLVM [2] and GCC [3] are compiler and toolchain technologies. The name Low Level Virtual Machine (LLVM) is no longer officially an acronym, and the GNU C Compiler is now the GNU Compiler Collection (GCC). [1] https://www.cc65.org/ https://www.cc65.org/ [2] https://www.llvm.org/ https://www.llvm.org/ [3] https://gcc.gnu.org/ https://gcc.gnu.org/

Scaevolus 4y ago

Does this code generator spill to zero-page? Do you have to do anything special for allocations there?

pubby 4y ago
Since it combines register allocation with instruction spilling is innate - there isn't a special spilling phase. Spilled variables are assigned ram addresses after code generation occurs at link time, with the most frequently used going to zeropage.
- coldacid 4y ago
  Does it avoid ZP addresses with special purpose for the system when doing this?
  - pubby 4y ago
    Yeah it can reserve specific ZP addresses. I do this to implement the runtime. It can also be used to reserve hardware registers, but since my only target is the NES, I don't have to worry about that.

nstbayless 4y ago

I may have misunderstood, but I believe step 1 (eliding loads) is simply a cache scheduling problem. The optimal solution is the greedy "furthest in the future" eviction policy.

pubby 4y ago
That's an excellent point. I hadn't heart of furthest in the future, but it looks like it does solve step 1. Past that though, it doubt it can be used because each of the 6502's registers are different and don't support the same operations. It's a good idea though, and might work for some specific RISC architecture where all registers behave the same.
quag 4y ago
Is [1] a good way to learn about furthest in the future eviction? [1]: https://blog.henrypoon.com/blog/2014/02/02/proof-of-the-farthest-in-future-optimal-caching-algorithm/ https://blog.henrypoon.com/blog/2014/02/02/proof-of-the-fart...
- nstbayless 4y ago
  I found that article quite confusing. I think these slides are clearer: https://courses.cs.washington.edu/courses/cse421/18au/lecture/lecture-8.pdf https://courses.cs.washington.edu/courses/cse421/18au/lectur... (provided you know about induction already.)

userbinator 4y ago

I'd like to see this same technique applied to x86, and what the performance is like without the "illegal instructions" (omitting them from generation would probably be trivial). It's relatively well known that one of the ways Asm programmers can beat compilers is on instruction selection, and that's what this technique seems to excel at.

turbobooster 4y ago

Can this make games for NES?