Explaining my fast 6502 code generator

https://pubby.games/codegen.html

by pubby • 3 years ago

217 49 3 years ago

pubby.games

commandlinefan• 3 years 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• 3 years ago

For LLVM, I don’t think it’s in the official repo, but yes:

https://github.com/llvm-mos/llvm-mos

pubby6• 3 years 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• 3 years ago

GCC: Via an old, unofficial port: https://github.com/itszor/gcc-6502

thechao• 3 years ago

This is a Massalin superoptimizer.

pubby6• 3 years 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• 3 years ago

I think you'll be (very!) interested in e-graphs:

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"

ant6n2• 3 years 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. ;-)

ecpottinger2• 3 years 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• 3 years 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• 3 years 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

ajross5• 3 years 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.

iainmerrick• 3 years ago

Not interesting to you, but other people may differ! A cross-compiler targeting the 6502 is still interesting to some. As the article notes, these compiler techniques weren’t invented in the 70s because computers weren’t powerful enough to make good use of them. What’s wrong with exploring what the original hardware is capable of when freed from those restrictions?

ajross5• 3 years ago

There's nothing "wrong" with it. I'm just saying that if I'm going to read an article about fun 6502 activities, I want to see it hosted on an Apple II. If I want to read about compiler techniques, I'd prefer to see it targetting a more orthogonal (or less weird, anyway) architecture.

ecpottinger2• 3 years ago

It is my understanding the the GEOS system was developed on a more powerful machine than the C64/Atari computers it was used on. This let then have the entire code in memory and then processed for common functions. They could not do this on the the 64K-8 bit computers at the time.

troad• 3 years ago

I don't think of retro-computing as an activity limited solely to the hardware and software that existed at a given time, that's far too restrictive for me.

6502 is an architecture, not a specific machine, nor even the set of machines that supported that architecture in the past. The architecture is and remains interesting on its own! (6502 assembly remains a really good intro to assembly, for instance, even for people that have never even seen a C64.)

There is absolutely scope for people to do fun things with 6502 that could never run on a C64 or an Apple II. The vast majority of 6502 code today runs in emulation, so there's really no reason to artificially gimp it to ape the limitations of any given machine. (Unless emulating that specific machine of course!)

ajross5• 3 years ago

6502 assembly remains a really good intro to assembly

It... really is not, though. It doesn't teach you macro assemblers as they exist in the modern world. It doesn't teach you interaction with the linker except in the simplest ways.

And while the instruction set is "simple" in the sense that it can be understood on a page of paper, lots of critically important ideas don't exist in a meaningful way. Modern techniques like register assignment aren't possible given the limitations and non-orthogonality of the CPU state. There's no "ABI" equivalent you can use to call a standard function, and even something as foundational as "passing arguments" to a function isn't directly expressible, because the "stack pointer" isn't actually a pointer. In point (heh) of fact, no pointers are pointers because the 6502 doesn't actually have an abstraction for a memory address!

Everyone should learn to hack on an Apple II (and good grief, not a Commodore unless you are trying to learn VIC-II or SID hardware), but not to teach themselves "assembly" as a skill they might apply elsewhere.

In fact it's almost the same argument used for why we teach new kids Python and not BASIC. The latter just isn't a useful tool for expressing the concepts you need to learn.

Someone• 3 years ago

The vast majority of 6502 code today runs in emulation

Emulating a 6502 isn’t that popular, so _if_ there’s even a single commercial product still using a 6502, I would guess that could easily run more 6502 cycles in total than are getting emulated.

Now, are there any? I wouldn’t know, but

- it seems you can still buy new (they’re RoHS compliant, so I don’t think they have stocks going back decades that they’re selling) 6502 CPUs (https://www.westerndesigncenter.com/wdc/HowToOrder.php)

- It was true during the Tamagotchi craze (https://hackaday.com/2013/05/24/tamagotchi-rom-dump-and-reve...: “it was a huge chore just to figure out what processor this uses. It turned out to be a 6502 core with a few other things built in”), but that’s over 20 years ago.

So, where, if anywhere, are these things being used?

geon• 3 years ago

Who in their right mind would self host 6502 development?

spc4762• 3 years ago

Plenty of teenagers in the 80s writing games for the various home computers at the time (Apple ][, Atari 400 & 800, Commodore 64).

billyjobob• 3 years 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.

pubby6• 3 years 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• 3 years 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),

It has been released as open-source together with the binaries, 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 or Altirra, https://www.virtualdub.org/altirra.html

mmphosis• 3 years 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/ [2] https://www.llvm.org/ [3] https://gcc.gnu.org/

exDM69• 3 years ago

No, not really. LLVM is not a C compiler, it consumes an intermediate representation. Clang is the C compiler which produces LLVM IR.

Likewise, GCC contains a C compiler but the machine specific parts like the codegen take an intermediate representation (GCC has several) as input.

Almost no compilers out there compile directly from C to machine code, there is one or more intermediate forms in between. C is not a good input language for an optimizing compiler.

It's a good and entirely valid comparison. It's the backend codegen that is being compared, the language frontend does not really play a part in it.

Scaevolus• 3 years ago

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

pubby6• 3 years 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• 3 years ago

Does it avoid ZP addresses with special purpose for the system when doing this?

deterministic• 3 years ago

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

nstbayless2• 3 years 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.

pubby6• 3 years 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• 3 years 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-fart...

nstbayless2• 3 years ago

I found that article quite confusing. I think these slides are clearer: https://courses.cs.washington.edu/courses/cse421/18au/lectur...

(provided you know about induction already.)

userbinator• 3 years 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• 3 years ago

Can this make games for NES?

Explaining my fast 6502 code generator

Related Stories