Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Rust on the MOS 6502: Beyond Fibonacci

gergo.erdi.hu

Post reply on HN
Print view View original

21–30 of 40 posts

Re: Rust on the MOS 6502: Beyond Fibonacci

#21

Post by tom_ »

Someone wrote: post #8
cmrdporcupine wrote: post #6

Earlier quoted context omitted.

I haven't looked at this closely, but 6502 really doesn't lend itself to C compilation. Three registers, only one of which works with the ALU, awkward immovable stack, etc. The 65816 is a better target (moveable direct page and stack and some wider registers), but also awkward with its register mode switching.

Not only C, any language that thinks there’s other things than global state. If all your functions are void foo(void) and you don’t use local variables (or your language doesn’t support recursion, in which case all locals can be given a fixed address), targeting 6502 is fine (it also helps if you avoid floating point, use 8-bit variables where possible, etc) Not supporting recursion also means you can statically comp…

I think you could use zero page as the data stack. Treat X is your frame pointer, and the zero page "address" is then the offset into the frame. Most instructions have a zp,X addressing mode. (This scheme works well with (zp,X) too.) LDY zp,X and STY zp,X are available, and the useful read instructions have abs,Y forms. So you can do lookups into global tables with an 8-bit local variable index without having to save X.

You'd need a little region for making use of (zp),Y, probably callee-saved, putting previous values on the return stack with PHA.

Re: Rust on the MOS 6502: Beyond Fibonacci

#22

Post by cmrdporcupine »

royjacobs wrote: post #11
cmrdporcupine wrote: post #6

Earlier quoted context omitted.

I haven't looked at this closely, but 6502 really doesn't lend itself to C compilation. Three registers, only one of which works with the ALU, awkward immovable stack, etc. The 65816 is a better target (moveable direct page and stack and some wider registers), but also awkward with its register mode switching.

They actually address some of that on their project page, see: https://llvm-mos.org/wiki/Findings

It's a good read, but I still maintain that the immovable zero page and stack make the '02 sub-optimal. The 816 lets you move both around, and the WDC C compiler at least does some nice things with this to allow a proper stack frame.

I suspect that an LLVM backend for the 816 would have to be something quite a bit different from the 02.

Re: Rust on the MOS 6502: Beyond Fibonacci

#23

Post by cmrdporcupine »

royjacobs wrote: post #16
Someone wrote: post #8

Earlier quoted context omitted.

Not only C, any language that thinks there’s other things than global state. If all your functions are void foo(void) and you don’t use local variables (or your language doesn’t support recursion, in which case all locals can be given a fixed address), targeting 6502 is fine (it also helps if you avoid floating point, use 8-bit variables where possible, etc) Not supporting recursion also means you can statically comp…

The cool thing about LLVM-MOS specifically it that by using the zero page as virtual registers you sort-of get the same output with 'regular' code as opposed to this 'global variables' style of programming. I recall a tutorial for 'cc65 optimizations'[0] which basically destroys a well-structured C program in order to do all of these optimizations (like making everything global) and it was absolutely terrible, code-w…

Zero page is great, but has limitations, for sure. Lots of moving stuff back and forth into the accumulator in order to do anything with it. And not relocatable like in the 6809 or 65816 "direct page".

Some nice simple extensions to the 02 architecture would be:

1) relocatable direct page and stack like in the 816. 2) some way of aliasing A to a direct page address to avoid doing it by hand.

Re: Rust on the MOS 6502: Beyond Fibonacci

#24

Post by antirez »

Strange exercise because Rust and the 6502 original programming mood are totally different: a word of cleverness and the most obscure side effects in order to squeeze the last clock cycle. But everything is "hack value", I will respect.

Re: Rust on the MOS 6502: Beyond Fibonacci

#25

Post by rob74 »

bluejekyll wrote: post #19
rob74 wrote: post #17

Er... the article doesn't make it clear, but I guess we're talking about cross-compilation here? So it's not "Rust" (or, as he writes later, LLVM) running on the 6502, just the code generated by the Rust compiler. Still cool though!

Don’t most people generally mean the target binary from the compiler and not the compiler itself when someone says “see * running on this architecture”? I can see for some dynamic languages there being a destination between the two, but for compiled binaries, generally Rust on X, it doesn’t seem important if rustc also runs on X (especially when discussing micro-controllers since one would rarely run a full compiler…

Well, when someone says "see Doom running on this architecture", they usually do mean that Doom is running on the architecture. So "Rust for the MOS 6502" or something like that would have been better. But yeah, maybe I'm too nitpicky and unfair to a non-native speaker...

Re: Rust on the MOS 6502: Beyond Fibonacci

#26

Post by fmakunbound »

bluejekyll wrote: post #19
rob74 wrote: post #17

Er... the article doesn't make it clear, but I guess we're talking about cross-compilation here? So it's not "Rust" (or, as he writes later, LLVM) running on the 6502, just the code generated by the Rust compiler. Still cool though!

Don’t most people generally mean the target binary from the compiler and not the compiler itself when someone says “see * running on this architecture”? I can see for some dynamic languages there being a destination between the two, but for compiled binaries, generally Rust on X, it doesn’t seem important if rustc also runs on X (especially when discussing micro-controllers since one would rarely run a full compiler…

> Don’t most people

And the rest are Forth users happily running interactive, extensible compilers with built in assemblers, block IO, screen editors in a multiuser, multitasking environment.

Re: Rust on the MOS 6502: Beyond Fibonacci

#27

Post by retrac »

dhosek wrote: post #13
gergoerdi wrote: post #10

Earlier quoted context omitted.

From what I understand, LLVM-MOS treats large parts of the zero page as virtual ("imaginary") registers, so you have no shortage of that ( https://llvm-mos.org/wiki/Imaginary_registers ). Then, sufficiently advanced compiler technology improves the stack situation ( https://llvm-mos.org/wiki/C_calling_convention ).

6502 assembly has the distinct advantage of having special page-0 instructions for reading/writing from memory, including, if I recall correctly, the ability to take a 2-byte sequence and treat it as a 16-bit value (or was that in the AppleSoft ROM?)

The main way to do pointer indirection (without self-modifying code) is to use the zeropage-specific indirect addressing modes, which use a 2-byte address stored in zero page as a pointer to a byte in memory. (And on the original 6502, the only available addressing modes for this forced you to use the X or Y register as an index, so you had to set it to 0 first!)

Re: Rust on the MOS 6502: Beyond Fibonacci

#28

Post by codedokode »

I am not sure if it is a good idea to compile code targeted to modern processors to 8-bit CPUs like 6502. For example:

Languages like C (or Rust) allocate variables on the stack because it is cheap with modern CPUs, but 8-bit CPUs don't have addressing modes to access them easily. (by the way, some modern CPUs like ARM also cannot add a register to a variable on the stack).

The solution is not to use the stack for variables and instead use zero-page locations. As there are only 256 zero-page bytes, same locations should be reused for variables in different functions. This cannot be used with recursive functions, but such code is ineffecient anyway so it is better not to use them at all and use loops instead.

Another thing is heap and closures (that allocate variables on the heap). Instead of heap the code for 8-bit CPUs should use static allocation.

The article contains an example of 6502 code compiled from Rust and this code is inefficient. It uses too much locations for variables (rc6-rc39) and it wastes time saving and restoring those locations in prologue/epilogue.

No wonder that programs run slowly. It would be much better to compile CHIP-8 directly to 6502 assembly.

Re: Rust on the MOS 6502: Beyond Fibonacci

#29

Post by mysterymath »

royjacobs wrote: post #2

That is so cool. I saw some posts about LLVM-MOS a while ago, but at that point I thought it would be just another in a fairly long list of attempts to try and get LLVM to output 6502 instructions. I never expected it to come together this well! Especially considering that the author of the article mentions there were so many issues with LLVM-AVR, you'd expect them to exist in LLVM-MOS as well. Apparently not! I gues…

Up until just a few weeks ago, 100% of the codegen work we've put into LLVM-MOS has been to get it feature-complete and rock-solid. It's awesome to see that that work has paid off!

We're just now starting to really optimize the compiler; there's definitely a long road ahead of us, but our preliminary investigations suggest that we'll be able to get the thing to emit really quite good 6502 assembly.

Right now, it emits near-garbage in a large number of common cases, as seen in the article. This is mostly due to technical debt intentionally accrued while getting the thing working, though; we did stuff like use the default LLVM lowering for comparisons, which are ridiculously trash on the 6502. But there's only really a couple major technical hurdles left to overcome; everything else is just painstakingly teaching LLVM what the best 6502 assembly patterns are for various situations.

Re: Rust on the MOS 6502: Beyond Fibonacci

#30

Post by Someone »

royjacobs wrote: post #16
Someone wrote: post #8

Earlier quoted context omitted.

Not only C, any language that thinks there’s other things than global state. If all your functions are void foo(void) and you don’t use local variables (or your language doesn’t support recursion, in which case all locals can be given a fixed address), targeting 6502 is fine (it also helps if you avoid floating point, use 8-bit variables where possible, etc) Not supporting recursion also means you can statically comp…

The cool thing about LLVM-MOS specifically it that by using the zero page as virtual registers you sort-of get the same output with 'regular' code as opposed to this 'global variables' style of programming. I recall a tutorial for 'cc65 optimizations'[0] which basically destroys a well-structured C program in order to do all of these optimizations (like making everything global) and it was absolutely terrible, code-w…

Nice article, but it doesn’t mention the really gnarly stuff such as using the fact that a subroutine happens to return with some flags set, or with some fixed value in the X register to shave of some initialization instruction in the code calling it.

A main advantage of the 6502 is that it only has 64 kilobytes of memory ;-). That means sufficiently advanced and motivated programmers can keep the entire program in their head, and also nudges them to avoid bloat such as the use of 16-bit integers.

Post reply on HN