The LARD Virtual Machine
The language output by the LARD compiler is an assembler-like
language. This document describes this language and the way in which
it is used in compiled LARD programs.
The virtual machine has three forms of storage:
- Registers: there is a small set of word-wide genral
purpose registers and a program counter.
- Stacks: there is a small number of unbounded-size stacks,
- The Heap: there is an unbounded region of memory managed by
Allocate and Free operations.
Many threads may exist. Each thread has a private set of registers
and stacks, but the heap is shared. A new thread inherits copies of
its parent's registers and empty stacks. Threads are scheduled
Flow of control
The program counter is a normal register and branches are effected by
assigning a value to the PC.
The instruction set comprises these instructions:
- ALLOC R1 R2
Allocate space in the heap. R1 is number of words to allocate. R2 is
register to store address of block in.
- FREE R
Free block of memory pointed to by R.
- PUSH S R
Push value from R onto stack S.
- POP S R
Pop value from S into R.
- LOAD RA RD
Load value from address given by RA into register RD.
- STORE RA RD
Store value from register RD into address RA.
- SETN R N
Set register R to value N.
- SETS R S
Set register R to the displacement of string S into the string table.
- SETC R C
Set register R to character C.
- SETR R1 R2
Set register R1 to value from R2.
- ADD R1 R2
R1 := R1 + R2
- SUB R1 R2
R1 := R1 - R2
- MUL R1 R2
R1 := R1 * R2
- DIV R1 R2
R1 := R1 / R2
- MOD R1 R2
R1 := R1 mod R2
- NOT R1
R1 := ~R1
- AND R1 R2
R1 := R1 & R2
- OR R1 R2
R1 := R1 | R2
- XOR R1 R2
R1 := R1 ^ R2
- SHL R1 R2
R1 := R1 << R2
- SHR R1 R2
R1 := R1 >> R2
- INC R
R := R + 1
- DEC R
R := R - 1
- INC4 R
R := R + 4
- DEC4 R
R := R - 4
- CMPEQ R1 R2 R3
R1 := (R2=R3)
- CMPNEQ R1 R2 R3
R1 := (R2!=R3)
- CMPLT R1 R2 R3
R1 := (R2<R3)
- CMPLTEQ R1 R2 R3
R1 := (R2<=R3)
- CMPGT R1 R2 R3
R1 := (R2>R3)
- CMPGTEQ R1 R2 R3
R1 := (R2>=R3)
- SETNNZ R1 R2 N
Set register R2 to N if R1 is not zero
- BUILTIN B
Call the foreign function B. B's definition is statically linked into
- FORK R
Fork the current thread. In the parent thread, the thread number of
the child thread is stored in R. In the child thread, zero is stored
in R. The child thread's other registers are copied from the parent
thread. The child thread's stacks are empty.
Schedule another thread
- RUNCHECK R1 R2
R2 := (is thread R1 running?)
- LINE FN LN
Note current line number and file number
- DEBUG FMT ARGS...
- Send a message to the debugger. FMT is a string containing
conversion characters, as in printf. %reg takes a register and
inserts the contents of that register in decimal. %sreg takes a
register and inserts a string taken from the address given by the
Use of the Virtual Machine
On top of this basic virtual machine, another level of abstraction is
provided by the particular use of registers and memory to accomodate
the compiled LARD program.
The registers are:
|PC || The program counter.
|T1..T8 || Temporary registers.
|CXP || The "current context pointer". This is a pointer to
a structure in the heap (the "current context"); see later.
|FPNUM || This thread's forpar number.
|STRBASE || Address of start of string area.
|TID || This thread's thread number.
The stacks are:
|PS || The parameter stack. Used to pass parameters to
functions and to return their results.
|RAS || The return address stack. Used to store subroutine
call return addresses.
|CXS || The context stack. Used to store values of the CXP
register over subroutine calls.
Structures in the Heap:
The Current Context is a structure in the heap pointer to by
the CXP register with the following form:
pointer to context of static parent
pointer to first local
pointer to second local
So any local that is in scope can be found by following the parent
context pointers as far as necessary to find the current context for
the local where it is declared, and adding a displacement based on
which local it is within that context.
The entries in the current context are pointers to the actual values
Parameter Passing Mechanism
Parameters passed on the PS have the following forms:
Parameters are popped in left-to-right order and so must be pushed in
right-to-left order. Any implicit parameters are pushed before the
explicit parameters that they corespond to.
- The size of the type is passed.
- Values of the scalar types are stored in single stack entries.
Structured types are stored in a sequence of stack entries, described
- Parameters of class var() are passed as pointers to the
- Parameters of class expr() are passed as a pair of stack
entities; the first pushed is the address of the code that evaluates
the expression and the second pushed is a pointer to the context
(i.e. CXP value) that should apply during its execution.
Function Call Mechanism
The Caller Must:
The callee must:
- Push the parameters onto the PS;
- Push its context onto the CXS;
- Set the CXP to point to the static parent of the callee;
- Push its return address onto the RAS;
- Set the PC to the start of the callee.
Before returning, the callee must:
- Allocate its CX;
- Set the parent pointer in the CX to passed CXP (its static parent);
- Set CXP to point to its CX;
- Pop each parameter from the PS:
- For type, val and expr parameters, it must allocate space to
store the parameter, copy the parameter from the PS into this
space, and set the appropriate entry in the CX to point to this
- For val parameters it must copy the address of the parameter from
the PS into the appropriate entry of the CX.
On return, the caller must:
- The result must be pushed onto the PS;
- For type, val and expr parameters, it must free the space pointed
to by the CX entry.
- The CX must be freed;
- The PC must be loaded with the return address from the RAS.
- pop its CXP from the CXS.
Body of a Function
Although the class of a function defintion is expr(something), this
does not mean that the execution of the body must return an
enevaluated expression! The function is only actually called when the
unevaluated expression is evaluated.
So the function must actually EVAL its body expression.
To evaluate an expression, the current context must be stored on the
CXS and a return address is stored on the RAS. The CXP is then loaded
with the context of the expression and the PC is loaded with the
address of the expression. When the expression completes the CXP
must be restored from the CXS.
Expressions and subexpressions
Expressions that have no locals simply
Expressions that have locals
- Push their parameter exprssions onto the PS;
- Call their function.
- Allocate a CX for themselves;
- Allocate space for their locals and make the CX entries point to
- Push their parameter expressions onto the PS;
- Call their function;
- Free the space used by the locals;
- Free the CX.
Read is an example of a builtin "val" function. Its implementation is
hardcoded in core.icode.pre. Val functions are called as follows:
- The parameters are pushed onto the PS;
- The function is called.
A vector is represented by the representations of each of the elements
of the array in turn.
A record is represented by the representations of each of the fields
of the record in turn.