S-code
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.
notation:
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)
s-code
|
description
|
stack effect
|
add,sub,mul,
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,
bxor
|
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 --
DS[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
s-code
|
description
|
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.
Encoding
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:
case
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
Example
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