I have been following this topic with interest. Some of the ideas could be applied to other accumulator based processors. The 6809 comes to mind.

I wonder how long before someone comes up with a processor that directly executes the VM.

_________________
http://www.finitron.ca

While I've not looked at the VM produced by LLVM, something similar (ish) happened in the 80's in the form of the Inmos Transputer. From what I can tell, its microcoded instruction set was influenced by the Cintcode instructions generated by the BCPL compiler - this is a stack based VM (only 2 stack registers in Cintcode) with a variable width instruction set which was more "orthogonalised" in the Transputer. (4-bit wide base instructions and 3 registers in the push-down stack) I'd love to create a microcoded CPU that executed the BCPL Cintcode directly - but it's relatively easy to interpret on a modern 32-bit CPU. Harder on an '816 though, but possible (because I've done it)

-Gordon

_________________
--
Gordon Henderson.
See my Ruby 6502 and 65816 SBC projects here: https://projects.drogon.net/ruby/

Major Update!

Alright, I've finally finished going through and auditing the compiler for correctness and C99 completeness.

Not a lot changed, but I'll call the fixes out below. The main significance of this milestone is that it's now optimization time! (Finally! )

First up, I'll be getting our automated test suite capable of producing size and cycle count figures for the Dhrystone included with LLVM. I'll post those figures once I have them. From there, I'll be optimizing the crud out of it, and we'll see how small we can get it! (And no cheating; I'll avoid "optimizations" that make Dhrystone faster and other programs slower.)

Fixes:
https://github.com/llvm-mos/llvm-mos/issues/27
Due to the 6502 indexing bug, indexed addressing may cause spurious reads to memory one page below the final location. This could be a problem if the spurious read hit an I/O register with hardware behavior triggered on read. To deal with this, I've disabled indexed addressing entirely for loads and stores to volatile objects. If the address is dynamic, it's issued through "LDY #0; xDA (ptr),Y" to ensure pages aren't crossed. It's on the programmer to ensure that all indexed accesses to values one page above I/O registers occur through volatile objects. Shouldn't be too onerous, since I/O registers are typically contiguous in high address space, and you usually need volatile objects to refer to those registers anyway.

https://github.com/llvm-mos/llvm-mos/issues/7
The soft stack pointer was always set in low then high order. When decreasing the stack pointer on function entry, if a borrow occurs, the 16-bit stack pointer might temporarily increase past its value on entry to the function. Were an interrupt to occur at this point, the interrupt might overwrite the stack of the interrupted function's caller. There are broadly 3 ways to fix this:
1. A interrupt-dedicated soft stack
2. Disabling interrupts while updating SP
3. Always set the high byte first when decreasing SP.

(1) requires an additional burden on the programmer and time to swap out the stack pointers. (2) doesn't work for NMIs without an additional target-specific mechanism present. (3)'s only downside, AFAICT, is an additional 2 bytes and 7 cycles of PHA/PLA on entry to a function that uses the soft stack. Given the tradeoffs, I went with (3).

https://github.com/llvm-mos/llvm-mos/issues/73
Finally, I was able to remove 3 bytes of compiler temporaries, so these no longer need to be allocated by the linker or saved and restored by interrupt handlers. This decreases the number of bytes (beyond A, X, and Y) of memory that an interrupt handler needs to save and restore in the worst case to 6, and 4 of those bytes are in the zero page.

Ta ta for now!

oh i didn't realize this was designed around the NMOS 6502 instead of the CMOS one.
i hope sometime in the future it will be able to make use of the 65C02's feature and lack of hardware bugs.

either way i'm following this project with great interest, as i hope to use a somewhat final version of it as a learning tool for getting into writing an LLVM backend myself.
the CPU0 example from online didn't really work for me, so i'm hoping a backend based around a CPU i know will allow me to better understand what is going on with the various files and fomats.

Thanks for the correction giving credit where it's due to the 6800. I should mention that, though low cost was certainly a huge factor in the 6502's success, the 6502 was not entirely without innovation on the ISA front.

In particular, the ability to do indirect indexed access with addresses stored in the zero page is something that doesn't exist on the 6800 and is a very handy feature, giving you essentially dozens of index registers. (That comes theoretically at some cost in access time, but in practice not much at all since the 6800 did not well optimize its indexed access.) It's handy enough that, now having done about as much 6800 programming as 6502 programming, I'd say it easily makes up for the many other limitations the 6502 introduced (8-bit index registers, loss of an accumulator, loss off useful instructions like BRA, tiny stack, etc.).

(This is probably getting rather off-topic for this thread, so if anybody's interested in getting into a substantive discussion about this it's probably best to start a new thread.)

_________________
Curt J. Sampson - github.com/0cjs

Interesting. When I had to make that decision for vbcc, I immediately chose (1). What burden on the programmer do you see?

Slowing down every (stack using) function in the code to reduce the overhead of an interrupt handler is something I can understand for specific use-cases (although it would usually not be my choice). However, if the interrupt handler calls other (stack using) C functions, will you not loose that improvement in your sub-functions (which, I assume, will have the overhead of the stack pointer adjustment)? Maybe I am overlooking something, but it does not seem beneficial to me.

But more important, as I understand it, this mechanism may incur an additional up to 255 bytes of stack-usage, depending on a - possibly very rare - race condition as well as the layout of the stack. I think you can even produce cases where reducing the stack usage of a function will effectively increase the total stack usage. That seems pretty unmaintainable to me.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Right, but how do you decrement (or increment) a 16-bit stack (or other) pointer atomically on a 6502? It's easy if there's no carry/borrow, but if there is it seems to me that you always have a period between updating the LSB and MSB where the pointer is invalid.

_________________
Curt J. Sampson - github.com/0cjs

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

It's possible that you've a different version of (1) in mind. The way I could manage to think of interrupt-specific stacks working, you'd have to find a place in the memory map for each of them, such that they wouldn't conflict with one another or run into anything else. If an interrupt could be interrupted, then you'd need two stacks, and so on. In general, it seems like this ends up being essentially how threads work; dynamically allocated fixed-size stacks per thread. But one of the advantages of the C runtime model is that you can get asynchronicity working on just one stack, and I hoped to preserve this advantage.



I'm hoping to avoid use of the soft stack as much as possible, and a PHA/PLA is a rounding error given the current state of the compiler. I've been trading off performance for simplicity of implementation at every stage of the compiler so far, since I'm working on correctness in a vacuum. This will definitely be something I'll have to revisit, in the context where I can compare its impact to other forms of optimization.

Along those lines, there's another approach with a different tradeoff, too. The SP can never be seen to be more than one page above it's true value, so an interrupt handler could be required to summarily increase SP by one page. This removes the PHA/PLA from every non-interrupt function, and adds a SP increment/decrement to the interrupt handler (only if it doesn't already have one). The downside is that 256 bytes are wasted for every interrupt on the call stack, which is the absolute worst case of the PHA/PLA approach. For PHA/PLA, usually zero bytes will be wasted, since usually interrupts don't occur within SP increments. The chances of multiple interrupt invocations wasting space decrease exponentially with the number of interrupt invocations on the stack.



That's similar in spirit to what I ended up with, just generalizing for the usual case where we're decrementing the stack by a 16-bit constant. Compute the low byte, stash it on the hard stack, and then feed its carry into the high byte sum. Set the high byte, then set the low byte from the stashed value.

In the case where you're decrementing by 1, the carry into the high byte sum reduces to the compare of the low byte with zero, and the use of that carry reduces to the control flow avoiding the decrement of the the high byte.

Sounds like this would do the job:



That actually looks like a much better solution to me.


Which happens to be exactly the space you want to assign to your stack. Code that exhibits its worst-case stack usage during each execution is a dream. Code that only exhibits it every thousand hours, depending on the phase of the moon, is a nightmare to test. So I would actually see this as a benefit. Of course I still think sacrificing 256 bytes of RAM is rarely worth it on a 6502.

The determinism argument is pretty convincing to me; I created https://github.com/llvm-mos/llvm-mos/issues/77 for this work. Probably won't get to it for the initial release, but definitely before we establish backwards compatibility guarantees.

My goal for the default ISR prologue/epilogue is to establish safe defaults that are as easy to use as possible, and improving the determinism of this behavior should help with that. As you've mentioned, there's always an easy out performance wise: you can disable the ISR prologue/epilogue generation and write your own that sets SP to a dedicated stack. This is also an improvement over the way I have things now, since you can't currently turn off the PHA/PLA in function prologues.

The impact of wasting 256 bytes should also be mitigatible in the long run; I've thought off and on about establishing a weird sort of 1-page red zone above the stack pointer, and doing so very carefully would remove the need for ISRs to increase SP at all (the non-atomic SP would always be in a memory region without live values). That's a ton of additional work though, and I haven't designed it end-to-end, just in bits and pieces.

First Benchmark Results!

I removed the malloc from LLVM's copy of Dhrystone v1.1 and got it running.

I also modified our simulator to spin until it takes as much CPU time as an imaginary 10MHz NMOS 6502 would (this time obtained by cycle counting). This allows us to run the tests fairly quickly, while still giving meaningful results for a 1MHz 6502; just divide by 10. We can use LLVM's built in execution time tracking too.

With that configuration, 2,000,000 loops of Dhrystone takes 26.565 sec on our imaginary 10MHz 6502, so it would have taken 265.65 seconds on a 1MHz one, for a final figure of:

EDIT: These figures were wrong by a factor of 10; the correct number of loops was 200,000.

Dhrystone v1.1 is a benchmark known to be extremely sensitive to compiler optimizations; hopefully this will be the case for us as well. High level optimizations have already taken a huge chunk out of the work this benchmark is doing, as seen by the huge jump from O0 to Os.

These numbers may or may not be comparable to any other compiler, but they're definitely comparable to themselves. I'll be back with the new figures once I start picking through the generated assembly.

EDIT: High level optimization might be a bit too effective for this particular benchmark; there's only about 400 lines of assembly left afterwards, and it's all slurped right into main. Everything uses static stack as a result too. Still, there's some pretty bad assembly here, even in this example. Onward!

Great to see numbers!

Even 240 is pretty good - high 30s were mentioned in this earlier thread.

Well this is embarassing; I missed a zero when counting the number of iterations for the previous post, my figures were inflated by a factor of 10.

The correct figures should be:
At -Os: 753 Dhrystones / second.
At -O0: 24 Dhrystones / second.

Sincerest apologies.