on HN: "Explaining my fast 6502 code generator"

[Dr Jefyll]

on Hacker News. Here's the article, and here's the HN discussion.

Quote:

Explaining my fast 6502 code generator

To learn how optimizing compilers are made, I built one targeting the 6502 architecture. In a bizarre twist, my compiler generates faster code than GCC, LLVM, and every other compiler I compared it to.

I reckon my compiler isn't doing more when it comes to high-level optimizations, so the gains must be from the code generation side. This makes sense, as most compilers are multi-target, with backends designed for modern RISC-like systems, not the ancient 6502. It doesn't matter how good GCC or LLVM's high-level optimizations are if they falter at the last leg of the race.

Still, my compiler also beats those designed for retro and embedded systems, like VBCC, SDCC, and KickC. For this reason, it seemed like a good idea to write about my technique.

[drogon]

Dr Jefyll wrote:

on Hacker News. Here's the article, and here's the HN discussion.

Quote:

Explaining my fast 6502 code generator

To learn how optimizing compilers are made, I built one targeting the 6502 architecture. In a bizarre twist, my compiler generates faster code than GCC, LLVM, and every other compiler I compared it to.

I reckon my compiler isn't doing more when it comes to high-level optimizations, so the gains must be from the code generation side. This makes sense, as most compilers are multi-target, with backends designed for modern RISC-like systems, not the ancient 6502. It doesn't matter how good GCC or LLVM's high-level optimizations are if they falter at the last leg of the race.

Still, my compiler also beats those designed for retro and embedded systems, like VBCC, SDCC, and KickC. For this reason, it seemed like a good idea to write about my technique.

Intersting stuff.

Just some random points:

• It's a cross compiler.
• It's not a C compiler, but a language with C-like features.
• It won't work on a 65C02. (The compiler deliberately outputs "illegal" opcodes)
• Seems to specifically target the NES platform, but I suspect that may be changeable by hacking the source code.
• Er: Division is unsupported.
• Looks like you can't do separate compilation, but you can compile several files at once - like concatenation, I think.

But it's nice to see something new. Maybe the existing C compiler people can look and adapt some of their stuff?

-Gordon

[CronicBadger]

I've found his write-up on how it's done, and the principles underneath enlightening and very useful.

For the past few years I've been writing a large 6502 application framework and a number of techniques used to squeeze out more performance mirror the ones he's described. He explains simply and concisely those concepts that I have been struggling with in frustration. A great find, Dr Jefyll!

[jfoucher]

I read that post and wondered if some of the later steps where the generated assembly is refined could be applied to hand-written assembly code. I have not been able to find the source code for the compiler though, and most of the algorithms in the post seem way above my head.

Anyone know if the source of this compiler is available? And what do you think about using these techniques to optimize existing assembly code?

[BigEd]

I think this is the source
https://github.com/pubby/nesfab

[Dr Jefyll]

"Explaining my fast 6502 code generator"

I see the same article has once again gotten posted to Hacker News. Perhaps forumites will appreciate a reminder, and may take interest in the ensuing discussion. (The 2023 discussion is here.)

-- Jeff

[BigDumbDinosaur]

Dr Jefyll wrote:

"Explaining my fast 6502 code generator"

I see the same article has once again gotten posted to Hacker News. Perhaps forumites will appreciate a reminder, and may take interest in the ensuing discussion. (The 2023 discussion is here.)

I re-read this fellow’s write-up and again came away with the same thoughts: 1) smoke and mirrors due to the use of undefined opcodes and arcane comp-sci concepts, e.g., continuations, that have a narrow application in general programming and hardly apply to the 6502’s very basic architecture; 2) implementation of a pseudo-language that appears to have been structured to work best in solving a specific set of problems; 3) a skilled assembly language programmer already knows all the described tricks; 4) that same skilled assembly language programmer is likely able to produce the most optimum version as quickly as this fellow’s code generator can compile higher level statements to the same or similar code.

Perhaps the executable code produced by his generator runs faster than the code produced by, say, vbcc, but that comes at the expense of non-portability, paired with making assumptions about how different renditions of the 6502 react to being fed undefined opcodes.  His own graphs tend to indicate that the gains are narrow; I daresay many of them are small or nonexistent when operation is outside of the realm of specific aspects of game play.  Also, my recollection from many years ago is since an undefined opcode is..er...undefined, there is no guarantee that its use with a MOS Technology 6502 will produce the same result when used with a Rockwell or CMD 6502.

Although optimizing C compilers developed for the x86 or MC68000 hardware have gotten very efficient in balancing code size with execution speed, they are able to do so mainly because their target MPUs have been designed with features that support the needs of compiled languages, e.g., the provision of a lot of general-purpose registers, along with an instruction set that readily maps onto higher level language constructs.  The paucity of GP registers, as well as the lack of compiler-friendly instructions (especially stack-management instructions), make the eight-bit members of the 6502 family poor compiler targets.  No amount of smoke-and-mirrors programming is going to change that.

[John West]

It's targeting the NES, and it looks like the aim is to make creating games for it more accessible. I think that's a worthy goal. And with that goal in mind, a language designed to produce decent code for the 6502, and a compiler that does everything it can to help, are perfectly reasonable things to do.

Calling standard compiler-writing techniques "arcane comp-sci concepts" says more about the limits of your learning. Continuations are hardly arcane. In any case, they're used in the compiler itself, not the generated code.

Your recollection of "undefined" opcodes is ... I was about to say out of date, but even back in the day we knew which ones could be reliably used. "Undocumented" might be a better name. Most of them are deterministic, and safe to use once you know what they do. If there was an NMOS 6502 that didn't support them, we'd have heard about it by now. And besides, this compiler isn't having to support any random processor. It's targeting the NES, and the NES alone.

I don't think it's fair to judge this project on criteria that are explicitly not part of its scope. If I wanted to write high-performance code in a high level language, I wouldn't be using any member of the 6502 family. But if I wanted to make games for the NES, and didn't mind sacrificing some speed for ease of coding, this looks like a very useful tool.