The STklos Virtual Machine

Internally, the global variables values of a program are stored in a unique array called STk_global_store.

The instructions GLOBAL_REF and GLOBAL_SET do the following:

Steps 1-3 are quite expensive, and shouldn’t need to be done every time the variable is accessed. Thus, the STklos VM patches the original code when we are sure that the variable used is properly defined. Hence, he first time a variable is referenced, the VM goes through all those steps, adds a final step:

For example, in GLOBAL_SET, this step is performed by the following two lines:

See that what is being changed are the two previous bytecode elements, pc[-1] and pc[-2]. Note that the value returned by global_var_index is the index in STk_global_store where the used variable is stored.

So the code:

is translated in

The second and third lines are used for doing this assignment. We can see that the parameter of the GLOBAL_SET instruction is the name of the variable to be set.

Then, after the first time the GLOBAL_SET instruction is performed, the code will patch itself and changed into

where n is the index of this global variable in the STk_global_store array.

The instruction GLOBAL_SET takes two integers to be represented, so when pc[-1] and pc[-2] are changed, what is being changed is the previous argument (0 → n) and the previous instruction (GLOBAL_SET → UGLOBAL_SET).

And, of course, the n-th element of the table contains the value of the variable to be set. We can see this by disassembling the test function defined before:

Once test has been called at least one time, its code is:

Here, 2971 is the index of the global variable a in the array of global variables.

Let’s see now the code of UGLOBAL_SET:

The fetch_global macro is defined earlier in vm.c:

The RELEASE_POSSIBLE_LOCK used here is a macro which deals with the lock needed to patch the code. This lock is necessary since STklos permits to have several threads to execute the same code. All the stuff about locking in the VM is explained in vm.c source file, and is covered (a bit) below.

Of course, all the work detailed about how we optimize access to global variables is also done in all other UGREF_* instructions in a similar way.

That is why, even using a hash table, access to global variables happens with speed not too far from that of access to local variables in STklos. This can be seen in the following rudimentary benchmark:

The operations take the top of stack and val as operands, and leave the result on val.

First the value of a (which is the zero-th local variable) is pushed onto the stack. Then, DEEP-LOCAL-REF brings the value of x, and IM-ADD2 adds the two values, leaving the result on the local variable register.

For fixnums, the analogous opcodes are:

The following variant of those opcodes do not use the stack. They operate on val and an argument:

Example:

With a as a local variable:

First, the value of a is put on val; then it is summed with 2, which comes as an argument to the opcode IN-SINT-ADD2.

These also have fixnum variants:

Example:

These compare the top of stack with val, and leave a boolean on val.

Example:

There are also opcodes for equal?, eqv? and eq?:

Example:

The dissassemble procedures will not, however, show the names of symbols or values of strings (disassemble-expr does, when passed the extra #t argument).

These will build structures with the value in val and store the structure (that is, the tagged word representing it) again on val.

Examples:

The element to be consed is pushed on the stack; then the second element is loaded on val, and then IN-CONS is called.

The special accessor CXR is used to access list parts, as described in the cxr library in the R7RS standard (caar, cadr, …​, up to cddddr). The following example illustrates this.

The constant #:daa is the abbreviation of the operations --(CAADR x) = (CAR (CAR (CDR x))), in reversed order (because that is the order in which they will be applied, and it is more natural for the VM to go from the beginning of the string towards the end.

See that if we turn off the inlining of functions in the compiler, we get a different output:

Not only we have more instructions, but the PREPARE-CALL and INVOKE instructions above are rather expensive.

The following opcodes access and set elements of strings and vectors.

V stands for vector, S stands for string; then, REF and SET mean reference'' and set''.

The instructions will use the object in the stack and the index from the val register.

Examples

In the following example, the CONSTANT-PUSH is including a reference to the string on the stack.

When setting a value, the reference to the vector or string and the index go on the stack (index below the reference to the object – the index is popped first), and the value goes on val, then the setting opcode is used:

The opcodes for `entering `let’' create new environments and push them on the stack, but do not update activation records, since there is no procedure call happening. Then, the `LEAVE_LET opcode removes the environment from the stack.

Examples:

When the let is in tail position, then the opcode used is the ordinary ENTER_TAIL_LET, and no LEAVE_LET is needed:

The following opcode creates a closure.

This opcode fetches two parameters:

Examples:

The following opcodes are used to make procedure calls:

These are handled in the VM as states in the state machine (they are labels used in the CASE`s in `vm/.c).

In vm.c, all these instructions end up sending the control to the FUNCALL: label, which will then check what to do depending on the type of call (tc_instance, tc_closure, tc_next_method, tc_apply, or some primitive, tc_subr…​)

The peephole optimizer will combine PUSH, GLOBAL-REF INVOKE instructions, yielding combined instructions. The following is an excerpt from peephole.stk where these transformations are documented:

The arguments to the INVOKE-like instructions are:

In the next example, GREF-INVOKE is called with arguments 0 and 0. The first value 0 is the address of the procedure in the stack. The IN-SINT-ADD2 procedure is called afterwards to sum 3 with the return from f.

In the next example, GREF-INVOKE is called with arguments 0 and 2. The value 0 is the address of the procedure in the stack; 2 is the number of arguments given in this procedure call. The IN-SINT-ADD2 procedure is called afterwards to sum 5 with the return from f.

Now the next example shows how INVOKE is used to call a procedure that is non-global (it is in the local environment). The INVOKE instruction will use the first value on the stack as the address of the procedure (it’s DEEP-LOCAL-REF 256, since f is defined inside the let). The other two arguments to be popped from the stack are #f (pushed by the FALSE-PUSH instruction) and the global variable y (pushed by the instruction GLOBAL-REF-PUSH 0). After INVOKE calls f, the instruction IN-SINT-ADD2 3 will sum 3 to the result.

There is one global mutex lock for STklos, called global_code_lock, declared in vm.c:

MUT_DECL(global_code_lock); /* Lock to permit code patching */

As per the comment, its purpose is to discipline access to the instructions of the running program. This lock is used when patching code for optimizing further global variables accesses (as explained before). This is necessary since STklos can use several threads. Note that each Scheme thread use its own VM, but the code and the global variables are shared among all the threads.

Three macros are used to control the global lock (a mutex):

After some initial setup, this function will operate as a state machine. Its basic structure is shown below.

The CASE symbol is defined differently, depending on the system, but CASE(x) semantically simialar to case x: (if computed GOTOs are better, then it’s defined as a label instead — see its definition in vm.c).