6502.org

It's finally up and running, and more importantly, documented:

Acheron VM - Virtual 16-bit CPU for 6502 computers

In a nutshell

• 16-bit fully orthogonal registers, through a 16-wide sliding register window
• 16*16=32-bit integer multiplication, and 32/16 division with remainder
• Carry stack holds 8 prior carry results
• Real exception handling and "finally" clauses, built on general non-local returns
• Inline native 6502 and Acheron code together
• Designed with easy task switching in mind
• Interrupt break & single-stepping hook
• Takes less than 1.5KB
• Dirt simple to expand or modify the instruction set, to customize for size, speed, and features
• Automatic generation of instruction set documentation
• MIT license

Goals

• Significantly increase code density over native code for complex data-oriented operations
• Achieve better speed than other VMs/interpreters (threaded Forth, Sweet16, various BASICs, etc)
• Good compiler target for high level languages
• Collect a contributed stable of custom instructions and modifications to the VM

I'd really appreciate feedback on any aspect you'd care to comment about, and it could use others' testing.

I'm going to move it to a publicly hosted VCS at some point, but for preview it's currently hidden away on my personal site.

Can you contrast this to the UCSD P-machine?

[edit: I think I'm misremembering the p-system as something else... doing some reading]

The ALU is not stack-based. Operations are register-to-register.

add r3, r10 ; r3 = r3 + r10

Operations like that can access locals, parameters, and the caller's registers directly (within a range of 16 regs), so for the majority of cases there's no DUP'ing data around the head of the stack, and no copying in & out of an accumulator. I've got floating point routines written but not tested, and those are reg2reg as well, so no preallocated FACs and their associated copying.

Longer-precision multiplication and division, and a single div gives both quotient & remainder at the same time. Division can be 32/16 or 16/16.

Contains bit-shifting, carry bits, and add/subtract forms which use it.

Return addresses and exception handlers go on the CPU stack, so the register stack only deals with program data.

It's smaller than the p-system, and as easily embeddable as Sweet16.

Sweet16-like 1-byte instructions with an embedded 4-bit parameter.

Instruction implementation code is completely self-contained. There's no manually changing a branch table, assigning opcodes, or creating per-instruction syntactic macros when changing the instruction set. It's as easy as including or removing blocks like this, and the macros take care of the rest:
(rP = the prior primary register that was used, whose offset is preloaded into .X)

That's its real benefit, as far as I'm concerned, to be able to grab a VM and plop some custom instructions in there for particular uses, or easily trim out stuff that won't be used. Plus, the best selection of various other VMs' features can be collected as pluggable options. It's got decrement-and-loop, case, byte & nybble swap, and other handy utility instructions so far, with lots of room left in the opcode space.

I'm looking at how garbage collection would tie in. There's currently no memory allocators at all, just pretty raw asm in that regard.

Well, I think TeamTempest would be the right man to answer this question as he has written a port for the C64 (Wizardry). Here are just a few things:
- stack machine
- very high code density
- comes with pointers to local variables as well as global variables
- special instructions allow access to intermediate variables (used inside local procedures)
- uses the 6502 stack as an evaluation stack (maximum: 128 INTEGER and 64 REAL values)
- parameters are passed on the evaluation stack, not the local variable stack (IOW the stack machine has two stacks)
- INTEGER, CHAR, and BOOLEAN values are always 16 bit. REAL (= floating point) 32 bit. STRINGs can have a size up to 255 chars.
- INTEGER multiplication is always 16x16, division 16/16. Operations MOD and DIV are separate instructions.
- comes with special instructions for
a) data type REAL (= floating point) (There are no preallocated FACs. That's BASIC. )
b) data type SET (up to 512 elements)
c) data type STRING (e.g. string comparison)
d) data type INTEGER[x] = LONG INTEGER (uses BCD arithmetic)
e) loading/storing a series of bits from a given address + bit position (for PACKED data types)
f) array boundary checking (can be omitted) and array indexing
g) loading so-called code segments to allow programs > 64kb (overlay capability).
- The interpreter is rather short. Most of the UCSD system deals with IO: reading from keyboard, writing to a text screen/terminal, printer output, scanning file directory for names, open/close/delete files etc.
- UCSD comes with its own file system. It's more like GEOS but without the graphics.
- Since UCSD is an OS on its own, it's the other way round: you integrate the 6502 code into the P-machine.
- Often used code can be stored in a library (special type of segment) that gets loaded when needed. A library can be written in p-code or 6502 code.
- P-code is relocatable, but added 6502 code is also relocatable due to a special file format.
BTW: A very good book about the P-machine is "p-Source - A Guide to the Apple Pascal System" by Randall Hyde (1983).

@White Flame
I've downloaded the file and will take a close look at it. Do you have some more code examples?

Cheers
Miles

I'd be interested in knowing how big the interpreter is including the instruction implementations. I'm assuming most of the things you listed are implemented in p-code or native call-outs, not as primitive bytecode instructions.
Unfortunately not yet. I'm working on porting over code from my previous VMs into this one, including a monitor. I had some messy tests to validate some of the instruction bugs I had; I can see if I can clean those up into proper examples.

As I mentioned, the system is very pliable and I consider this just a "preview" that needs some maturation, even though it's in solid working order. Any suggestions or feedback about the direction it's taking is welcome, especially from people here more familiar with other bytecode systems.

I haven't personally seen any other sliding register window implementation on 8-bit architectures, and I think it makes great use of zeropage speed and avoids a lot of copying. Weighing the pros & cons of that vs more traditional stack machines is a curious thing.

Hard to tell. On the AppleII most of it can be found between $d000 and $d9ff with the jump table at $d000. Floating point routines are located around $ec00. The whole system itself resides inside the 'language card' which is 16kb of additional ram but it also contains routines for accessing the disk drive on very low level (GCR reading/writing, head movement..). Let me know if you want some specific example. If it's not too difficult, I think I can look it up. Opcodes for REAL, SET or STRING values are part of the p-code and usually 2 byte opcodes. All IO routines are done in pure 6502 of course. They are accessed via special routines unitread, unitwrite etc. The data type FILE is implemented in p-code as well as handling the file directory. These routines are also stored inside the 16kb (somewhere in the $fxxx area IIRC). 'Previous?' Not your first attempt then. Sounds familiar. That would be nice. Awww right... You see, that's a .. real .. strange .. coincidence. I joined this forum just a while ago when I noticed that some people are actually working on a new extended 6502 processor: the 65org16, or taking it even further: the 65org32. Until then I had only designed a lot of ISA specifications for virtual processors/stack machines which also includes writing the VM, the assembler/debugger and some code examples (usually a minimalistic kernel). When I began writing code for the 65org16 I thought it might be a good idea to add some kind of VM in order to get some tools running on the target machine without implementing them in assembly language. The reason behind this was to be on the safe side, because the ISA of the 65org16 might still change and there's also the parallel development of the 65org32. The idea then was either to resurrect my old 6502 implementation of a 16 bit RISC processor (as the 65org16 is a 16bit processor) or to use threaded code that is supposed to be generated with a new backend of my compiler. Right now this compiler uses stack machine code as an intermediate language and is also able to produce a special p-code for the 6502 (not compatible with UCSD). Since changing the compiler is rather simple, I decided to rewrite the compiler output, but when I saw your post I just had to look at the old design again. In a way, the evaluation stack could be seen as some kind of sliding register window implementation with one accessible register at the top. TBH I'm not so sure about that. I've also done some experiments with register windows but found them lacking. I might give you some examples later. But also very interesting. A stack machine implementation can be very fast while still providing high code density. Register machines usually find it hard to compete against it. The advantage of a real silicon register machine is the fast access of its registers. This advantage, however, gets lost when you're writing a VM for it. Using registers can also mean that you have to spent some time on extracting the register number (shifting and masking). Anyway, your design looks promising, and it might be a good idea if we could put together some test cases and see how they perform compared to each other regarding speed and code density (all VMs implemented in 6502). What do you think?
Cheers
Miles

Even though individual operations on a stack are fast, data still needs to be copied to the stack head in order to operate on it. It is, like you say, somewhat similar to having a single accumulator register, which auto-loads new values based on the stack order. Attempting to eliminate excessive copying is one of the primary exploration vectors for me.

With a real register bank, if data is reused or the effects of computation are used in complex order, these values are always immediately addressable. It can eliminate the pipeline of pushing vars to stack (or fetching them from deeper in the stack), perform ops, store to vars again; if the local vars simply live in registers. The fact is that one instruction addressing 2 independent registers can effectively perform the task of 3 or more stack operations in certain not-really-degenerate cases.

I'd suspect that performing longer chains of operations on one or two values would prefer a stack machine, while doing small separate operations on more values would prefer register banks. This is also why I have a notion of an implied "prior" register, so you don't continually have to address and decode the same register over and over when chaining together multiple operations.

So yes, the differences really do need to be measured at some level of an entire function doing its thing, or even a whole system performing a task, and I'd be interested in seeing how things match up and if my speculations actually play out in hard testing.

That's right, but you only have a limited number of registers you can access at one time. If you need more you run into trouble... Agreed. That's an interesting idea, which I'd like to see used in a longer code example. Before I can answer to that I must make sure I've really understood your concept.
Besides the 16 general purpose registers you have the rather invisible instruction pointer (iptr), the global pointer (gptr) and a return stack using the stack pointer of the 6502, which is inaccessible to the Acheron. Correct?
If so, then here is a simple exercise:
1) We need a subroutine 'ConvertToString' that will convert a given unsigned 16bit integer into a string (decimal, binary, hexadecimal, whatever). This subroutine will have two parameters: a) the value, b) a pointer to a string. Let's start with the question: which registers do you use for the parameters?
2) After this task is done, we need another subroutine 'WriteInteger' which will first convert the given unsigned integer into a string (using 'ConvertToString') and then write the string to some device (screen etc). This subroutine will also have two parameters: a) some pointer/handle that specifies to which device the string will be written, b) the value.
Sounds rather simple, I think, and is a realistic example of often used subroutines. Now how will we code that on the Acheron? Any suggestions?

Alright, here's an implementation. http://pastebin.com/Stjdh9ip (edit: uncommented link at the bottom of the post)

I included that as test.asm in the new distribution that you can download (which also includes other changes and additions). make, make test, and run bin/acheron.prg in VICE to watch it print "12345" to the top of the screen.

Now, I had been delaying implementing a number of instructions which don't byte-pack even pairs of 4-bit parameters together. Things like "add rD, imm8" and "stpmb rD" (STore Prior value as Memory Byte at rD) leave a parameter byte only half-used. However, this decodes quickly (they're pre-ASL'd in the byte for alignment) and represent a number of useful instructions. So I started putting some of those in. Remember, just adding an implementation,
anywhere in the VM source automatically sets everything up, including adding the instruction to the documentation.

But how different is that from a stack? You always need to pull variables to a stack's head, while you only need to reload temp work registers when registers are scarce; they stay put otherwise. Loops make this quite apparent, where every iteration needs to restore the same pattern of information for stack processing, while registers can simply hold the iterated state.

I also see value in holding onto register values moreso in longer functions than in smaller ones. You tend to see more references to the same local values in the former.

Parameters are always an issue with copy overhead, though. For any calling convention, you need to put data in the right place, which is always going to end up shuffling something somewhere, unless the functions are single-use, tailored to directly access where the caller already has its data.


While the pastebin uses pre-decrement during string rendering, here's a post-decrement sample that shows using rP: (remainder and buf are just names for registers in the outputString function) There is a certain elegance here that I like, stack-like brevity with a register bank, and avoidance of redundant register decoding. I am hopeful of its speed implications, and am aware that finding how best to chain rP through the instructions will take some time to get right.

Yes. However, iptr, gptr, and all the other implementation zpvars are automatically exported as assembler labels. Therefore, their addresses are still syntactically accessible, e.g. "set r3, gptr" and dereferencing from there.


As a general calling convention, parameters start from r0 from the caller's perspective, then the called function grows the register stack by however many local variables it needs. convertToString does a 'grow 3' to gain a fresh r0, r1, r2 to use, while r3+ are views of r0+ from the caller, which it can still directly read. The function body can write into r3+ to set return values and modify the caller's r0+ values as side effects. It ends with 'rets 3' to return and un-grow the 3 regs away to realign the caller's r0.

Note that this exercise does not specify using any return values, and the complexity is pretty low, so some of the things I've designed Acheron for that I've had issues with, aren't being shown hard. However, I do need to get better debugging tools first before going hardcore with complexity.


edit: Here's a plain version of the functions without any comments, to show the density: http://pastebin.com/pLQKx3hL

Hrmph hrmph, somebody mention my name? Ah, that was mumblety-mumble years ago, but...

The p-machine core was portable across the C64, C128 and Apple II (also the Atari, but SirTech decided not to port Wizardry there). The Apple II use was so SirTech could avoid paying royalties for the run-time system. Main differences between them were all in the I/O area (C64/128 used multi-color text screens, Apple II a bitmapped one, for instance). Total assembled sizes, including custom I/O, were in the 11-13K range.
Yes
Yes. Cute tricks with variable-size integer values in there.
P-codes to directly load and store the first eight (no stacking of offset + base address then, so faster)
Not sure I remember these specifically. I do remember I thought it was a pain to have to keep track of procedure chains so as to be able to access the variables of the parents of procedures nested arbitrarily deep.
Yes. "TSX" got used a lot.
yes. Though my implementation of the local variable stack worked, I think I'd do it differently today. I intermixed the p-code segments and the local variable stack on the assumption that no local variable could belong to a segment that wasn't in memory (hence it was safe to intermix). The idea was to leave space at one end of memory for heap allocation by the running program. Today I'd take advantage of p-code's inherent relocatability to move it when heap space is needed and keep the local stack "pure" at the other end of memory from the heap.
Maybe. I never could clarify that to my satisfaction. I wrote pushes to the evaluation stack in terms of two bytes for the sake of speed, but I also always checked for an odd number of bytes. Possibly wasted effort, but I never could get assurance it wasn't.
Those were fun. Lots of hacks to check for high-byte values of zero so I could speed them up by shifting whole bytes. David Bradley later ripped out those in the Apple II version so he could implement a random number generator he liked better (C64/128 used the white noise voice of the SID chip for that).
Nope. Wizardry was integer only, although it had its own p-coded "bignum" routines. All those REAL p-codes pointed to a trap that halted execution.
Yes.
16-bit binary, not BCD.
Probably. Some of those p-codes can do complex things when you string them together.
I think we had to give up bounds checking when we first discovered that Wizardry used negative indices in some places as a hack to read size information stored just before an allocated block.
Yes. That and UCSD's determination not to allow code segments beyond a certain size in order to encourage modularity. These interpeters went a bit beyond the standard UCSD versions because they could use any extra RAM to stash code segments for fast loading. The C64 version used RAM "under" the Kernel to store the two most commonly used segments and could use a RAM expander if one was attached. The C128 version used the second 64K bank rather than RAM under the Kernel (ooh, lots of segments!) and eventually the 80-column chip 16- or 64K RAM as well as any RAM expander. The game simply cached segments at startup as long as an interpreter kept reporting "yes, there's more room".

Overlays coming out of a RAM expander were pretty darn quick.
Yes. 512-byte sectors and dedicated device numbers that have to be mapped onto whatever hardware you have.
Yes, but in the case of Wizardry a number of special routines were required by fiat to be implemented as part of the interpreter itself rather than this way. Speeding up common string operations, data decompression, one virtual disk spanning more than one physical disk, the caching system, things like that.

Not saying anything against Acheron VM, but as one who has used Forth a lot and written a very extensive 65816 Forth kernel, I'll say that it's not always necessary to bring things to (or near) the top of a stack to use them (although we normally do in secondaries, as opposed to primitives), and that the stack reduces the need for variables. For the return stack, the '816 has a stack-relative addressing mode that lets you address for example the sixth item on the stack without messing with the five above it, and without having to do the TSX trick that the 6502 requires, which is nice because we want to keep X for the indexing into the data stack.

Yeah, I'm talking about secondaries here; the user-level code and what it needs to commonly do in order to perform high-level data and imperative processing via the language primitives.

"The stack reduces the need for variables". If you mean it reduces the need for load/store variables, yes. But you could just as well consider the transient depth of the stack "owned" by a routine to be its list of variables, in formal terms. I think the most important advantage of a stack is that it reduces the need for addressing these variables, via effectively auto-loading an accumulator and its potential parameters at the head.

In specific cases when the ordering or reuse of values on the stack becomes an issue, a stream of DUPs/OVERs/ROTs/etc is generally not as efficient as directly addressed register-to-register operations, especially when the native machine word size is less than the virtual word size in all of that shuffling. (On actual hardware stack processors, it can be a lot closer.) However, those additional register-naming parameters become less-useful overhead to the interpreter if that's the only way it can ever address its variables even in easy cases.

I'm trying to integrate the best of both worlds there with something relatively different: The ability to implicitly address the "prior" register in Acheron brings a lot of what I consider the stack's best advantage in expression evaluation; the register orthogonality reduces data shuffling vs both stack & accumulator-based systems; and the sliding window mitigates the hit of manually saving regs between calls and dealing with register partitioning, and gives elbow room to avoid becoming register-starved (it can be grown/shrunk at any time, not just at function boundaries).

I am also sticking with the basic NMOS 6502 architecture. It just gets too easy on the others.

Miles: I annotated the string exercise with instruction sizes, and it came to 57 bytes for all 3 functions, though I could probably reduce that by another 1 or 2: http://pastebin.com/8VD9JYKf

Do you have an example of this optimized for a stack machine to compare density? I know that besides the division operator, most of this would probably be written in 6502 in a real system anyway, since it's dealing with bytes and a small buffer size.

Hi White Flame! Thanks for the examples. Sorry about the delay. I'm already working on a code example based on the virtual risc processor for comparison (just finished the assembler and disassembler, VM almost finished but needs some testing). I think I can also write a p-code example. Please allow me a day or two to finish this task (sorry, couldn't work on it yesterday).
Cheers
Miles

Oh, no rush. I just noticed that I hadn't actually shown the size or running time. I've yet to actually time the routine, going to use the 6522's timer for that (and I wrote it more for clarity and smaller size than speed).