intermediate code (S-code)

Som source program is translated into intermediate codes.  The intermediate code (S-code) is a linear sequence of instructions that resemble machine codes.  Hence it is easy to translate the intermediate code to an assembly language of any processor.  The S-code can be executed on a stack-based virtual machine.  This virtual machine enables S-code to be independent of platforms which the code will be executed.  In this regards, S-code is portable across platforms, only the virtual machine needs to be implemented on the target platform to run all Som programs.  

For an executable code, the emphasis is on a small number of instructions, and ease of modification.  The S-code for Som should be reasonably fast when interpreting, and easy to generate machine dependent code for specific purpose, such as, small code size (byte-code, nybble-code), high speed (extended code), or to fit a particular hardware. Therefore, the optimisation of S-code should not be emphasise.  Instead, a "clean" implementation is the goal, so that it is easy to modify or to make a new code generator. Essentially, s-code has only around 40 instructions. Many extensions can be experimented with easily.

A fixed 32-bit instruction is suitable (not compact but easy to generate code and reasonably fast when interpreting).  This format has a fixed length of each code which simplifies code address calculation and allows code and data segment to be the same type (32-bit integer).

S-code instructions

Two types of instructions are: zero-argument and one-argument.  The zero-argument instructions do not have any argument embedded in the instructions.  They take arguments from the evaluation stack, operate and push the result back to the stack.  The most frequently used zero-argument instructions are the binary operators such as add, sub.  The one-argument instruction has one argument embedded in the instruction, mostly this argument is a reference to a local variable.  All control instructions (jmp, call etc) need a displacement as their arguments.  The evaluation stack is implicit and automatic, that means, it can not be explicitly accessed by programmers (the stack pointer is not settable). The top-of-stack is usually cached into a register in the virtual machine to speed up the operation.

n is a 24-bit constant (2-complement)
x is a 32-bit value
v variable reference, for a global variable, it is an index to Data segement, for a local variable, it is an offset to a current activation record in Stack segment.
f is a reference to Code segment.
DS[] data segment, SS[] stack segment, CS[] code segment.
pc is program counter, pointed to the current instruction.
stack notation:   (arg tos -- result)

zero argument instructions (argument field is 0)

stack effect
div, mod
integer arithmetic, take two operands from the stack and push the result.  (a b -- a op b)  
shl, shr take two operands: number, no-of-bit and shift the number and push
the result back.  shr is an arithmetic shift, preserved sign.
 (a n -- a shift n)
band, bor,
bit-wise, take two operands from the stack and push the result.
 (a b -- a bitop b)
not logical, takes one operand and push the result.  (a -- 0/1)
eq, ne, lt,
le, ge, gt
logical, take two operands from the stack and push (T/1, F/0).  (a b -- 0/1)
ldx take an address, an index and return DS[ads+idx].  (ads idx --
stx take an address, an index, a value x, and store x to DS[ads+idx].  (ads idx x -- )
case take a value (key), compare it to the range of label, goto
the matched label, or goto else/exit if the key is out of range.
 (key -- )
array allocate x words in Data segment, return ref v to the allocated data.
 (x -- v)

one argument instructions

stack effect
lit n push n
 ( -- n )             
inc v increment local variable, SS[fp-v]++.  ( -- )
dec v decrement local variable, SS[fp-v]--.  ( -- )
ld v load a global variable, push DS[v].  ( -- DS[v])
st v store a global variable, take a value x and store to DS[v] = x.  (x -- )
get v get local variable v.  ( -- SS[fp-v])
put v store a value x to local variable v, SS[fp-v] = x.
 (x -- )
call f call a function, create new activation record, goto f in CS.  ( args -- )
callt f     
tail call, use old activation record.
 ( args -- )
ret n return from a function call, n is the size of activation record. remove
the current activation record, return a value if function returns a value.

fun n function header, n is the number of local variables.
jmp n goto  pc+n in CS
jt n goto pc+n if top of stack != 0, pop  (0/1 --)
jf n goto pc+n if top of stack = 0, pop  (0/1 --)
sys n call a system function n, interface to external functions, the
arguments are in the stack, the number of arguments can vary.
 (args -- )

S-code format

Each instruction is 32-bit.  Right most 8-bit is the operational code.  Left most 24-bit is an optional argument. This format allows simple opcode extraction by bitwise-and with a mask without shifting, but needs 8-bit right shift to extract an argument.  Because zero arg. instruction is more frequent, this format is fast for decoding an instruction. 


1  add     2  sub     3  mul     4  div     5  band
6  bor     7  bxor    8  not     9  eq      10 ne
11 lt      12 le      13 ge      14 gt      15 shl
16 shr     17 mod     18 ldx     19 stx     20 ret
[21 - ]    22 array   [23 - ]    24 get     25 put
26 ld      27 st      28 jmp     29 jt      30 jf
31 lit     32 call    33 callt   34 inc     35 dec
36 sys     37 case    38 fun

[- ]  reserved  [21 retv] [23 end]

[ calli which is used in interactive mode, requires symbol table to be presented, and compilation for non-interactive use]

Activation record (run-time data structure)

An activation record stored a computation state.  It is resides in the stack segment. The computation state consists of: pc (retads), fp, all locals (local var and parameters).  sp needs not be stored as it will be recovered when ret, because the argument of ret is the size of activation record.  The following diagram shows the layout of an activation record in the stack segment:

hi address

retads'    <- sp
fp'        <- fp
lv         <- lv 1
pv         // no. of pv, arity of func
...        <- lv n
           <- sp'', sp after return

lo address

A function call creates a new activation record.  The new fp is sp + lv + 1.  The value lv + 1 is the argument of "fun m", m = lv + 1.  A local variable is indexed by an offset from the current fp.  When returning, "ret n", n is the size of activation record + 1.  Restoring sp by (not considering the return value yet)  

sp'' = fp - n  

The arity of the function can be calculated from  

arity = n - m

A function call does the following:

1  decode m at func header
2  stack overflow check
3  SS[sp+m] = fp    // new AR, save fp
4  fp = sp + m      // new fp
5  sp = fp + 1      // new sp
6  SS[sp] = pc + 1  // save retads
7  pc = arg + 1     // goto body of func

A tail-call (callt) does not create a new activation record,  it reuses the old one.  The function parameters are copied to the old activation record.

A return does the following:

1  pc = SS[fp+1]    // restore pc
2  if there is a return value
3    a = the return value  
4    sp = fp-n+1    // restore sp
5    fp = SS[fp]    // restore fp
6    SS[sp] = a     // push ret value
7  else             // not return a value
8    sp = fp - n    // restore sp
9    fp = SS[fp]    // restore fp

case instruction

The layout of code in "case" is as follows:

lit low
lit hi
jmp else
jump table

code of each case

 case does:

1  extract range of label: low, hi
2  if key < low or key > hi
3    pc = pc + 3        // goto else-case
4  else
5    pc = pc+key-low+4  // goto matched label

In this implementation, the jump-table is fully-filled with the labels in the range, hence, finding the matched label is simply an index calculation, a constant time operation.  This enables the case to be fast but it consumes the memory in the code segment as large as the range of label.  This is wasteful if the label is not densed.  For the case of sparse label, a binary search can be used.  The jump-table is the sorted label of the pair (label, goto code).  This is not implemented as it is not suitable to be converted into a machine specific instruction (maps to a real processor).

system call

27 Sept 2004


Here is some source snippet (from bubble sort), data[] is a global array, maxdata = 20.

to swap a b | t =
  t = data[a]
  data[a] = data[b]
  data[b] = t

to sort | i j =
  for i 0 maxdata-1
    for j 0 maxdata-2
      if data[j+1] < data[j]
        swap j j+1

and the output listing of S-code  (from Som v 2.4).  The left column is the function swap.  The right column is the inner for-loop of sort. The loval variable is numbered in reversed order (to fit the offset from fp). For example, in swap: a is 3, b is 2, t is 1.

45 Fun swap
46 Ld data
47 Get 3
48 Ldx
49 Put 1
50 Ld data
51 Get 3
52 Ld data
53 Get 2
54 Ldx
55 Stx
56 Ld data
57 Get 2
58 Get 1
59 Stx
60 Ret 4
69 Lit 0
70 Put 3
71 Lit 20
72 Lit 2
73 Sub
74 Put 1
75 Jmp 92
76 Ld data
77 Get 3
78 Lit 1
79 Add
80 Ldx
81 Ld data
82 Get 3
83 Ldx
84 Lt
85 Jf 91
86 Get 3
87 Get 3
88 Lit 1
89 Add
90 Call swap
91 Inc 3
92 Get 3
93 Get 1
94 Le
95 Jt 76
96 Inc 4
97 Get 4
98 Get 2
99 Le
100 Jt 69

last update  26 Nov 2009