Difference between revisions of "Simple graphics language"
(→Constant generation) |
(→Optimisations) |
||
Line 150: | Line 150: | ||
=== Arithmetic === | === Arithmetic === | ||
*Constant folding | *Constant folding | ||
− | **1 8 lsl | + | **1 8 lsl → 256 (for all arithmetic and logic operations) |
*Strength reduction | *Strength reduction | ||
− | **0 div | + | **0 div → -1 |
− | **1 div | + | **1 div → nop |
− | ** | + | **pow2(n) div → (n - 1) lsr |
− | **1 mul | + | **1 mul → nop |
− | * dup drop | + | **2 mul → dup + |
+ | |||
+ | *No operations | ||
+ | **dup drop → nop | ||
+ | **not not → nop | ||
+ | **dup and → nop | ||
+ | **dup or → nop | ||
+ | |||
+ | |||
=== Loading of constants === | === Loading of constants === | ||
Line 163: | Line 171: | ||
**op_ldc8 0x01 op_ldc8 0x03 op_dup op_ldc8 0x01 op_over | **op_ldc8 0x01 op_ldc8 0x03 op_dup op_ldc8 0x01 op_over | ||
*Applying an eight bit contant and an arithmetic operation to one of the previous numbers. | *Applying an eight bit contant and an arithmetic operation to one of the previous numbers. | ||
− | *Applying an arithmetic operation on the two | + | *Applying an arithmetic operation on the two previous numbers. |
=== Stack reordering === | === Stack reordering === | ||
Optimisation is done by a brute force search generating optimal fragments of up to 7 instructions. | Optimisation is done by a brute force search generating optimal fragments of up to 7 instructions. |
Revision as of 15:31, 8 May 2011
Contents
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:
- To < function name > < code > End
- Constant:
- Define < constant name > < costant > End
- 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 read opcode 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 >> 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 can be 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.
Arithmetic
- Constant folding
- 1 8 lsl → 256 (for all arithmetic and logic operations)
- Strength reduction
- 0 div → -1
- 1 div → nop
- pow2(n) div → (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 contant and an arithmetic operation to one of the previous numbers.
- Applying an arithmetic operation on the two previous numbers.
Stack reordering
Optimisation is done by a brute force search generating optimal fragments of up to 7 instructions.