A simple graphics language for microcontrollers

We start with a very simple reverse polish notation interpreter with a preprocessor stage

Sample code:

to circle 360 for 1 forward 1 right next end

Registers:

0 X (nn.ff)
1 Y
2 Angle
3 Scale
4 Colour
5 Pen up/down
6 Local variable pointer
7 Program counter

Stack diagrams

( things read from the stack -- things written on the stack )
x - x position
y - y position
n - number
Examples:
  ( n n -- n )
  This means that two numbers were read from the stack, then one number was written back.
  For example a simple addition reads two numbers and writes back the result.

  ( a b c -- c b a )
  Reading threee values from the stack and write them back in the opposite order.

Definitions

Function:
- The compiler/optimiser is free to inline functions for speed reasons.
- Functions that depend on exact knowledge of the return stack should use a Define instead.
- To < function name > < code > End
Constant:
- Every instance of < constant name > in the source code will be replaced by < costant >
- Define < constant name > < constant > End
Macro:
- The macro code will be executed at compile time and the output will be compiled (TODO: Figure out if this is wise)
- Hint: Magical constants and look-up tables can be generated by a macro
- Macro < macro name > < code > End
Comments:
- ( everything here is a comment ( and so is here ) )

Commands

Absolute commands
  setcolour     ( colour -- )
  readcolour    ( -- colour )
  setpos        ( x y -- )
  readpos       ( -- x y )
  load          ( address -- data )
  store         ( data address -- )

Variables:
  var           ( n -- )( create n variables of value 0 on the return stack ) 
  unvar         ( n -- )( delete n variables from the return stack )
  ldl           ( index -- )( load local variable )
  stl           ( n index -- )( store local variable )

Relative commands:
  penup         ( -- )
  pendown       ( -- )
  forward       ( length -- )
  backward      ( length -- )
  left          ( angle -- )
  right         ( angle -- )
 
Loops:
  for           ( n -- )
  next          ( -- )
  do            ( -- )
  again         ( -- )

Conditionals:
  if            ( n -- )
  else          ( -- )
  endif         ( --  )

Data processing:
  +             ( n n -- n )        ( to +  >r 0 r> - - end )
  -             ( n n -- n )        ( fundamental )
  *             ( n n -- n )        ( to * 0 do over 1 and if rot dup >r -rot r> + endif rot 1 lsl rot 1 lsr rot over if again endif >r drop -rot drop drop end ) 
  /             ( n n -- n )
  lsl           ( n n -- n )        ( to lsl for dup + next end )
  lsr           ( n n -- n )        ( to lsr for 31 for dup 0x80000000 and swap 1 lsl swap if 1 + endif next 0x7fffffff and next end )
  and           ( n n -- n )        ( fundamental )
  or            ( n n -- n )        ( to or over not and + end )
  eor           ( n n -- n )        ( to eor over over or -rot and not and end )
  not           ( n -- n )          ( to not >r -1 r> - end )

Stack manipulation:
 drop           ( n -- )           ( to drop if endif end )
 dup            ( n -- n n )       ( fundamental )
 swap           ( a b -- b a )     ( to swap dup >r >r dup r> eor dup >r eor r> r> eor end )
 over           ( a b -- a b a )   ( to over >r dup r> swap end ) 
 rot            ( a b c -- b c a ) ( to rot >r swap r> swap end ) 
 -rot           ( a b c -- c a b ) ( to -rot swap >r swap r> end )
 >r             ( n -- )           ( fundamental )
 r>             ( -- n )           ( fundamental )

Optimal stack reordering in Forth

Compiler

Stage 1 (not implemented in version 1)

Definitions are expanded
Macros are executed

Stage 2

Functions are added to the dictionary

Stage 3

All words are looked up in the dictionary and the opcode stored in the program array
The address of each function is stored in the function jump table in the same order as the functions were added to the dictionary

The dictionary

The dictionary used to convert a command into an opcode. It is a zero terminated string like "setcolour,readcolour,setpos,readpos,",0 that is searched linearly from start to end. A comma marks the end of a word. All functions are added to the end of this table in stage 2 of the compiling process.

The function jump table

This table contains the address of each function, in the same order as the functions appear in the dictionary. It is filled in during stage 3 when the actual code position is known.

Interpreter

The opcode pointer always ppoints to the next byte to be processed.

do
  opcode = program(opcodepointer)
  opcodepointer += 1
  switch opcode
    case 0
      push 0
    case 1-4
      read byte(s)
      value = byte0 or (byte1<<8) or (byte2<<16) or (byte3<<24) 
      push value
    case command
      execute command
    case function
      pushr localpointer
      pushr opcodepointer
      opcodepointer = jumptable(function)
   end switch
again

Opcodes

enum operands {op_ldc0, op_ldc8, op_ldc16, op_ldc24, op_ldc32, op_lds, op_end, op_setcolour, op_readcolour, op_setpos, op_readpos, op_load8, op_load16, op_load32, op_store8, op_store16, op_store32, op_var, op_unvar, op_ldl, op_stl, op_penup, op_pendown, op_forward, op_backward, op_left, op_right, op_call, op_for, op_next, op_do, op_again, op_if, op_else, op_endif, op_add, op_sub, op_mul, op_umul, op_div, op_udiv, op_lsl, op_lsr, op_asr, op_and, op_or, op_eor, op_not, op_drop, op_dup, op_swap, op_over, op_rot, op_nrot, op_dtor, op_rtod, op_nop};

DIV, MUL and LSR are unsigned.
Opcodes larger than op_nop are local function calls.

Constants

op_ldc0, op_ldc8, op_ldc16, op_ldc24, op_ldc32

If the two or three most significant bytes are 0xff then shorter code is generated by:
- op_ldc16 0xnn 0xnn op_not
- op_ldc8 0xnn op_not

Optimisations

The bytecode is optimised in several separate steps after the compilation. Unused instruction slots are padded with nops. After each stage the code is compacted and the nops removed.

Arithmetic and logic

Constant folding
- 1 8 lsl → 256 (for all arithmetic and logic operations)

Strength reduction
- 0 div → -1 (TODO: check if this is what the interpreter would normally do...)
- 1 div → nop
- pow2(n) div → (n - 1) asr
- pow2(n) udiv → (n - 1) lsr
- 1 mul → nop
- 2 mul → dup +

No operations
- dup drop → nop
- not not → nop
- dup and → nop
- dup or → nop

Loading of constants

Repeating numbers are shortened by using op_dup and op_over, 1 3 3 1 3 can be shortened to:
- op_ldc8 0x01 op_ldc8 0x03 op_dup op_ldc8 0x01 op_over
Applying an eight bit constant and an operation on a copy of one of the two previous numbers.
Applying an operation on copies of the two previous numbers.

Stack reordering

Optimisation is done by a brute force search generating optimal fragments of up to 7 instructions.

Just In Time compiler

The JIT compiler can be made very fast if the code quality is not very important. So loops can be compiled without considering how many times they will be executed. If they are executed more than 3 times there will be a benefit.

A possible first experiment can have a code block containing assembly functions for each op_code, then the loop will be compiled into a string of Branch-Link instructions.

Simple graphics language

Contents