-
Notifications
You must be signed in to change notification settings - Fork 152
Virtual machine design
Clasp uses a simple virtual machine for evaluation of code that doesn’t happen often, e.g. during [the build process](The-Build-Process), or for compile-time code. The virtual machine is designed to be reasonably fast to run while remaining easy to use as a compiler target. The compiler targeting the virtual machine, which is largely separate from the LLVM+Cleavir-based native code compiler, runs very quickly and only performs general optimizations.
The virtual machine is basically a stack machine. Each function call reserves a fixed number (determined by the compiler) of slots on the stack which are used as registers, but can use a variable amount of stack space, both to stack-allocate objects and for multiple-values purposes. Each thread of execution has its own independent virtual machine, i.e. its own VM stack space.
There are basically two intrinsic registers, beyond a function’s register file: the program counter and the multiple values vector. The multiple values vector, referred to as the mv register below, is the usual multiple values vector used also by native Clasp code.
The code is a bytecode, stored in an ordinary (unsigned-byte 8) Lisp vector. Each instruction is an optional prefix, followed by the opcode byte, followed by zero or more byte operands, depending on the particular instruction. Usually each operand is a single byte; if that is not sufficient, the instruction may be preceded by the special `long` prefix byte, which indicates that all of its operands are two bytes long instead. Two-byte operands are interpreted as little-endian sixteen bit integers. Currently, the only prefix is `long`, and it may only be used for instructions that have at least one operand.
The bytecode is organized into modules, each of which has one or more functions. Functions are in the same module if they are compiled together, which is usually because they are internal functions of one another (e.g. due to `flet` or `lambda`). Jumps are only valid within a module, as Lisp functions never `go` or `return-from` to exit points they weren’t compiled together with, by definition. Each module has zero or more constants, which are shared between all of its functions.
Each function conceptually consists of a module, an offset into the module where the function begins, and zero or more closed-over values.
“cells” are the objects Clasp uses to store mutable closure values. A cell is just a structure containing one value. They are used by both the VM and native compiled code. At present, they are cons cells, with the value in the car, and the cdr set to nil.
The particular opcodes are listed below. FOO U U means that the instruction is called FOO, and has two operands, which are interpreted as unsigned integers. An L operand indicates a label; in this case it is a signed integer, and is relative to the start of the instruction (i.e. 0 would be the opcode, or the prefix if it exists). The K operand type is unique to the PARSE-KEY-ARGS instruction and will be explained along with it. In the text, op1 means the first operand, and so on.
Push the op1-th register to the stack.
Push the op1-th constant to the stack.
Push the op1-th closure value to the stack.
Perform a function call. The most recent op1 values on the stack are the arguments for the call. The last argument is the most recent value pushed, the second to last is the second most recent, and so on. The next most recent value after the arguments is the function. Call the function with the arguments, set the mv register to be the values it returns, and then pop all 1+op1 values from the stack. (The arguments are kept on the stack during the call so that the called function can return to them without any copying taking place.)
As CALL, but instead of storing to mv, push the primary return value to the stack. (Note that the function being called may nonetheless write to mv.)
As CALL, but take the op2 first return values and push them to the stack, primary first.
Pop op1 values from the stack, and copy them into the register file starting at op2. The least recent stack value will go into register op2, the next least recent into 1+op2, and so on.
Pop a value from the stack, and set the op1-th register to that. set n is equivalent to bind n n.
Pop a value from the stack. Allocate a new cell object with it as a value, and push that cell to the stack.
Pop a value from the stack; it must be a cell. Push the cell’s value to the stack.
Pop a value from the stack; it must be a cell. Pop another value, and set the cell to hold that value.
Take the op1-th constant, which must be a prototype of a function. The prototype describes how many values the function closes over; pop this many values from the stack. Create a new closure based on the prototype, with the closed-over values being these values popped from the stack. The first closure value will be the least recently pushed value to the stack, and so on.
TODO
Bytecoded functions, which run on the VM, are of class `core:global-bytecode-simple-fun` (GBSF). This class contains a `core:bytecode-module`. Note that closures will be of class `core:closure` as normal, and the underlying simple fun will be a GBSF. The GBSF also contains an index into the module for the start of the function’s code, and a local frame size, which indicates how large a VM register file needs to be allocated during a call - see “The machine” above for details. BGSF’s also serve as function prototypes when making closures.
The actual virtual machine structure is a `core::VirtualMachine` in the runtime. Each Clasp thread has a `VirtualMachine` object. This object keeps track of the virtual machine’s stack memory. Said stack memory is currently allocated on the C++ control stack, but we are planning on moving it to the heap in order to facilitate starting and stopping virtual machines externally.
When a GBSF is called, a trampoline function grabs the module and the start PC, and passes control to the function `bytecode_call`. This function, and the rest of the virtual machine implementation, live in `src/core/bytecode.cc`. `bytecode_call` allocates the register file for the function and then passes control to `bytecode_vm`, which does the actual interpretation of the bytecode. The values returned by `bytecode_vm` are returned by `bytecode_call` and then the function.
For the sake of nonlocal exits, `bytecode_call` pushes a special `VMFrameDynEnv_O` dynenv to the dynenv stack. This environment just records the state of the VM stack before the call. During a nonlocal exit, these dynenvs are unwound by unwinding the VM stack.