u-code v.2  improved

from many analysis, the obvious additional instructions are:

immediate, include the smallest set:
  addi, subi, bandi, bori, eqi, lti, lei

others are not use often: muli, divi, bxori, modi
and logical op can be "inverse": nei, gti, gei

using AC as index:  ldxa, ldya
Store instructions can not use the same trick as they require three arguments (base, index, value).

Other instructions that are included are: shl, shr (for completeness). Some instructions are modified or eliminated.  ads is retired as it is used for relocating the data segment only.  pusha is retired and is replaced by push 0 using the zero argument to signify the AC. The "case" instruction should take argument from AC. So, it changes the format to one-arg and to improve the form slightly, "lit hi" is put behind the "case" instead of in front (this is VM after all, it is not intended to be in a real chip).

case lo
lit hi
jump else
jump table
...

it remains to see if "mov" and "mvi" will be included.

Here are the counts:
          mov       mvi     opt
program  get+put% lit+put% put+get%

aes4       0      6.3    2
bubble     0      0.7    0
hanoi      0      5      0
matamul2   3.3    2.4    0
queen2     0      1.7    0
quick      0      1.9    1
sieve      0      0.6    0
compiler   0      6      1

average    0      3      0

"mvi" should be included.  "mov" should not.  However, if immediate mode is used, "mvi" usage may be reduced. Optimisation of "put_x + get_x -> put_x" is not worth doing.

with these instructions, I expect the noi of the whole set of benchmark reduced by 10-20% (and the actual running time too).

22 July 2008

u-code improved

bop    :  add sub mul div band bor bxor mod
          eq ne lt le gt ge 
bim    :  addi subi bandi bori eqi lti lei shli shri
data   :  ld st get put lit ads
vector :  ldx/ stx/ ldy/ sty/ ldxa ldya
control:  jmp jt jf jle/ case call callt ret
extra  :  fun/ sys inc dec not push pusha

total  50 instructions  
(but fun is not really an instruction.  It is a marker)
The two-address instructions are marked with /.

u-code encoding

1   add sub mul div band bor bxor mod eq ne
11  lt le gt ge addi subi bandi bori eqi lti
21  lei shli shri inc dec lit ads sys not push 
31  pusha get put ld st ldxa ldya call ret callt
41  jmp jt jf case ldx/ stx/ ldy/ sty/ jle/ fun/

meaning of new instructions

bopi c    ::  AC = AC bop c
case lo   ::  if lc <= AC <= hi skip 4+2*(AC-lo)
ldxa v    ::  AC = M[v+AC]
ldya ads  ::  AC = M[ads+AC]
push v    ::  if v == 0 push AC else push v

7 Aug 2008

