close-circle
Close

Accumulator Machine Implementation

A project log for Cat-644

An 8-bit computer based around an AVR ATMega-644 and junk-box SRAM.

Mark Sherman 03/11/2017 at 21:113 Comments

I've begun work on the virtual machine interpreter that will run on the Cat-644. I am writing it as a separate Atmel Studio project, as I could see this being useful outside of this.

The interpreter assumes that once it is invoked, it will never exit. Any interrupts already 'hooked up' to C functions will still operate normally. The interpreter can call out to single user-defined function called 'syscall.' Syscall is free to call out to other C functions, as the C stack will be available and left intact for this purpose.

simavr Windows Port (small side project)

I am mostly a Linux user. An exception to that rule is AVR development. I really like Atmel Studio's IDE, especially the AVR simulator in single-step mode. Every hardware peripheral is right there, clock by clock, in a nice graphical way. You can use gdb for this, but it is simply more convient to press the single-step key and watch port registers turn on and off. It was extremely useful for debugging the PS/2 keyboard and VGA signal code. What is not good about it is the lack of serial port support. You can watch a byte appear on the serial register, and you can poke 1 byte at a time into the register, but it is a pain to do so. This is where the simavr open source AVR simulator really shines. It has full serial port emulation, and on linux even gives you a pty you can attach a terminal to. When developing a bytecode interpreter, I want both: I want to single-step through code in Atmel Studio on Windows, especially when watching things like that stack frame and or studying the timings of different routines. And then, I want to run a program at full speed, and interact with it like it is on a serial port. What I needed was simavr on Windows. SImavr had mingw support, but I didn't want to set up mingw just for this, and I was curious what it would take to get it to run on Visual Studio. I got it working well enough for my current project: https://github.com/carangil/simavr-visualstudio

Small Interpreter

The goal is for the interpreter handlers of all of these instructions to fit within 256 instruction words on the AVR. This is because of the way I am fetching these instructions. All the instruction handlers fit on a single 256 word page of flash, so they all have the have MSB address. This is so the ZH register can be set up once. The instruction bytes themselves are directly loaded into the ZL register, and an IJMP is performed. At least all the entry points for all the instructions must fit in this page: If certain instructions are long, the handler can jump out another routine.


Registers

The virtual machine has 4 16-bit registers, labeled A, B, C and D.

Register 'A' is the special Accumulator register, and most instructions require its use. This is to keep the number of possible instruction encodings as small as possible. All instructions that don't have immediate data are 1 byte long, and instruction that need data are followed by 1 or 2 bytes.

There is a stack, managed by the 'Y' 16-bit index register of the AVR. This is separate from the C stack. This doesn't have to be, but this is the case at the moment.

Available Instructions

  1. LI (Load immediate) Can load an immediate 16-bit value into any register A,B,C,D
  2. Swap: Swap the contents of A with either B,C or D
  3. Arithmetic Instructions: Performs an operation between registers B,C,D and A, and stores result in the accumulator (register A)
    1. add
    2. sub
    3. subr (not yet implemented: performs reg-=A instead of A-=reg
    4. and
    5. or
    6. xor
    7. cmp Does a trial subtraction, but doesn't modify registers. Sets internal flags.
    8. adc: Add-with-carry, allowing 32-bit and higher math.
  4. Syscall The C function 'syscall' is called, with 2 16-bit arguments. The first argument is the contents of A, and the second argument is the contents of B. The return value of the C function is returned to the interpreted program in register A. The rest of the registers are unmodified. Complex, operating-system like operations will be done here, in native AVR code, as opposed to being code in the interpreter. This will include serial i/o, disk i/o, graphics routines, memory allocation, etc.
  5. Jump instructions (some of these implemented) All jumps are to relative addresses
    1. jmpr: jump to 16-bit address
    2. Accumulator value jumps: looks at value in register 'A', not the result of the last operation
      1. janz: jump if A is not zero
      2. jaz: jump if A is zero
      3. jan: jump if A is negative (if MSB bit set)
    3. Arithmetic comparison jumps: looks at the result of 'cmp, add, etc
      1. je: jump if values were equal
      2. jne: jump if value were not equal
      3. ja: jump if unsigned value in accumulator was larger than register (A > reg)
      4. jb: jump if unsigned value in accumulator was smaller than register (A < reg)
  6. Stack Instructions These can go under 'memory instructions', but are a little bit of a special case
    1. push reg : Push any register to the stack
    2. pop reg: pop any register into the stack
    3. pop <immediate> pop n items off the stack (items are discarded, not loaded anywhere)
    4. pick reg, <immediate> load the nth item on stack into any register
    5. put reg, <immediate> store any register into the nth position on the stack
  7. Memory Instructions I wanted to keep memory access simple: The other instructions don't access memory at all. I wasn't sure if it was going to be more common to store a register in a computed address (where the Accumulator is probably where the computed address ends up), or it was going to be more common to store the result of a computation (in the accumulator) to an address already contained in another register. I decided to support both cases. This results in 4 instructions:
    1. ld A, *reg (Load value pointed to by register A,B,C or D into A) (4 encodings)
    2. st *reg, A (Store value A to memory pointed to by B,C or D (3 encodings)
    3. ld reg, *A (Load value pointed to by A into B, C or D) (3 encodings)
    4. st *A, reg (Load value in B C or D to memory pointer to by A) (3 encodings)
  8. Subroutines I am undecided if the VM data stack should be used for this, or a separate stack instead. Forth has a separate stack, and it comes in handy to not have the return address in the way.

I feel like the above is a pretty comprehensive instruction set for the kind of machine I am making. I chose 16-bit instead of 8-bit, because for many of the operations, it only requires 1 additional clock cycle per instruction. Often on an 8-bit machine, two operations are cascaded to make 16-bit operations anyway. Basic arithmetic instructions complete one every 6 AVR clock cycles (20mhz avr = 3.3 million arithmetic instructions per second), and instructions involving data memory (push, pop, ld, st) take around 12 clock cycles. (1.6 million per second.) The cat-644 in fast mode (every other line on the display is dropped) runs at an effective rate of 10mhz, so divide the numbers above in half. When compared to a 1 Mhz 6502, which is often cited as 300 to 400 k instructions per second), I think this interpreter pulls ahead.

Next Steps

I need to finish some instruction handlers. I also need to write an assembler, since hand assembling bytecode is a little annoying. Also, every time I change a handler, the bytecodes change, because the bytecode is the offset into the interpreter code. I need an automated way to dump out the addresses of all the handlers, and use that to generate the bytecodes.

Discussions

Mark Sherman wrote 04/16/2017 at 03:50 point

I have shift left and shift right 1 place.  That is what the hardware supports.  The avr can do a 8 by 8 multiply in 2 clocks so its faster to multiply by 8 than it is to shift left 3 places.  If I see lots of repeated SHR instructions may add multi space shift support.

I've also recently realized that the way my handlers are written, some 'illegal' instructions may be useful.  The 16 bit ops are built by performing two 8 bit instructions.  If  I intentionally offset an opcode, the VM will run only part of a handler.  For many of these instructions it creates an 8 bit instruction that operates on the high byte of a register.

  Are you sure? yes | no

esot.eric wrote 04/16/2017 at 08:43 point

ah hah! hadn't thought about the multiply-instead-of-shift factor of AVRs. Good point!

Clever hack, too with 8-bit instructions.

  Are you sure? yes | no

esot.eric wrote 04/14/2017 at 17:15 point

I'm convinced. Sounds like this'll be significant improvement over a 6502, being 16-bit, and all. How about comparison with an 8086? Those guys are allegedly ~300KIPS, as well... and 16-bit. Your instruction-set may be smaller, but theirs is so wonky, with different-length instructions, I'm surprised they can even claim KIPS estimates.

Erm, no bit-shift instructions?

  Are you sure? yes | no