A Virtual Machine for Guile
===========================

Guile has both an interpreter and a compiler. To a user, the difference is transparent---interpreted and compiled procedures can call each other as they please.

The difference is that the compiler creates and interprets bytecode for a custom virtual machine, instead of interpreting the S-expressions directly. Loading and running compiled code is faster than loading and running source code.

The virtual machine that does the bytecode interpretation is a part of Guile itself. This section describes the nature of Guile's virtual machine.

Why a VM?
---------

For a long time, Guile only had an interpreter. Guile's interpreter operated directly on the S-expression representation of Scheme source code.

But while the interpreter was highly optimized and hand-tuned, it still performed many needless computations during the course of evaluating an expression. For example, application of a function to arguments needlessly consed up the arguments in a list. Evaluation of an expression always had to figure out what the car of the expression is -- a procedure, a memoized form, or something else. All values have to be allocated on the heap. Et cetera.

The solution to this problem was to compile the higher-level language, Scheme, into a lower-level language for which all of the checks and dispatching have already been done---the code is instead stripped to the bare minimum needed to ``do the job''.

The question becomes then, what low-level language to choose? There are many options. We could compile to native code directly, but that poses portability problems for Guile, as it is a highly cross-platform project.

So we want the performance gains that compilation provides, but we also want to maintain the portability benefits of a single code path. The obvious solution is to compile to a virtual machine that is present on all Guile installations.

The easiest (and most fun) way to depend on a virtual machine is to implement the virtual machine within Guile itself. This way the virtual machine provides what Scheme needs (tail calls, multiple values, call/cc) and can provide optimized inline instructions for Guile (cons, struct-ref, etc.).

So this is what Guile does. The rest of this section describes that VM that Guile implements, and the compiled procedures that run on it.

Before moving on, though, we should note that though we spoke of the interpreter in the past tense, Guile still has an interpreter. The difference is that before, it was Guile's main evaluator, and so was implemented in highly optimized C; now, it is actually implemented in Scheme, and compiled down to VM bytecode, just like any other program. (There is still a C interpreter around, used to bootstrap the compiler, but it is not normally used at runtime.)

The upside of implementing the interpreter in Scheme is that we preserve tail calls and multiple-value handling between interpreted and compiled code. The downside is that the interpreter in Guile 2.2 is still slower than the interpreter in 1.8. We hope the that the compiler's speed makes up for the loss.  In any case, once we have native compilation for Scheme code, we expect the new self-hosted interpreter to beat the old hand-tuned C implementation.

Also note that this decision to implement a bytecode compiler does not preclude native compilation. We can compile from bytecode to native code at runtime, or even do ahead of time compilation. More possibilities are discussed in Extending the Compiler.

VM Concepts
-----------

Compiled code is run by a virtual machine (VM).  Each thread has its own VM.  The virtual machine executes the sequence of instructions in a procedure.

Each VM instruction starts by indicating which operation it is, and then follows by encoding its source and destination operands.  Each procedure declares that it has some number of local variables, including the function arguments.  These local variables form the available operands of the procedure, and are accessed by index.

The local variables for a procedure are stored on a stack.  Calling a procedure typically enlarges the stack, and returning from a procedure shrinks it.  Stack memory is exclusive to the virtual machine that owns it.

In addition to their stacks, virtual machines also have access to the global memory (modules, global bindings, etc) that is shared among other parts of Guile, including other VMs.

The registers that a VM has are as follows:

  * ip - Instruction pointer

  * sp - Stack pointer

  * fp - Frame pointer

In other architectures, the instruction pointer is sometimes called the ``program counter'' (pc). This set of registers is pretty typical for virtual machines; their exact meanings in the context of Guile's VM are described in the next section.

Stack Layout
------------

The stack of Guile's virtual machine is composed of frames. Each frame corresponds to the application of one compiled procedure, and contains storage space for arguments, local variables, and some bookkeeping information (such as what to do after the frame is finished).

While the compiler is free to do whatever it wants to, as long as the semantics of a computation are preserved, in practice every time you call a function, a new frame is created. (The notable exception of course is the tail call case, see Tail Calls.)

The structure of the top stack frame is as follows:

        /------------------\ <- top of stack
        | Local N-1        | <- sp
        | ...              |
        | Local 1          |
        | Local 0          | <- fp = SCM_FRAME_LOCALS_ADDRESS (fp)
        +==================+
        | Return address   |
        | Dynamic link     | <- fp - 2 = SCM_FRAME_LOWER_ADDRESS (fp)
        +==================+
        |                  | <- fp - 3 = SCM_FRAME_PREVIOUS_SP (fp)

In the above drawing, the stack grows upward.  Usually the procedure being applied is in local 0, followed by the arguments from local 1. After that are enough slots to store the various lexically-bound and temporary values that are needed in the function's application.

The return address is the ip that was in effect before this program was applied.  When we return from this activation frame, we will jump back to this ip.  Likewise, the dynamic link is the fp in effect before this program was applied.

To prepare for a non-tail application, Guile's VM will emit code that shuffles the function to apply and its arguments into appropriate stack slots, with two free slots below them.  The call then initializes those free slots with the current ip and fp, and updates ip to point to the function entry, and fp to point to the new call frame.

In this way, the dynamic link links the current frame to the previous frame.  Computing a stack trace involves traversing these frames.

Variables and the VM
--------------------

Consider the following Scheme code as an example:

       (define (foo a)
         (lambda (b) (list foo a b)))

Within the lambda expression, foo is a top-level variable, a is a lexically captured variable, and b is a local variable.

Another way to refer to a and b is to say that a is a ``free'' variable, since it is not defined within the lambda, and b is a ``bound'' variable. These are the terms used in the lambda calculus, a mathematical notation for describing functions. The lambda calculus is useful because it is a language in which to reason precisely about functions and variables.  It is especially good at describing scope relations, and it is for that reason that we mention it here.

Guile allocates all variables on the stack. When a lexically enclosed procedure with free variables---a closure---is created, it copies those variables into its free variable vector. References to free variables are then redirected through the free variable vector.

If a variable is ever set!, however, it will need to be heap-allocated instead of stack-allocated, so that different closures that capture the same variable can see the same value. Also, this allows continuations to capture a reference to the variable, instead of to its value at one point in time. For these reasons, set! variables are allocated in ``boxes''---actually, in variable cells. See Variables, for more information. References to set! variables are indirected through the boxes.

Thus perhaps counterintuitively, what would seem ``closer to the metal'', viz set!, actually forces an extra memory allocation and indirection.

Going back to our example, b may be allocated on the stack, as it is never mutated.

a may also be allocated on the stack, as it too is never mutated. Within the enclosed lambda, its value will be copied into (and referenced from) the free variables vector.

foo is a top-level variable, because foo is not lexically bound in this example.

Compiled Procedures are VM Programs
-----------------------------------

By default, when you enter in expressions at Guile's REPL, they are first compiled to bytecode.  Then that bytecode is executed to produce a value.  If the expression evaluates to a procedure, the result of this process is a compiled procedure.

A compiled procedure is a compound object consisting of its bytecode and a reference to any captured lexical variables.  In addition, when a procedure is compiled, it has associated metadata written to side tables, for instance a line number mapping, or its docstring.  You can pick apart these pieces with the accessors in (system vm program).  See Compiled Procedures, for a full API reference.

A procedure may reference data that was statically allocated when the procedure was compiled.  For example, a pair of immediate objects (see Immediate objects) can be allocated directly in the memory segment that contains the compiled bytecode, and accessed directly by the bytecode.

Another use for statically allocated data is to serve as a cache for a bytecode.  Top-level variable lookups are handled in this way.  If the toplevel-box instruction finds that it does not have a cached variable for a top-level reference, it accesses other static data to resolve the reference, and fills in the cache slot.  Thereafter all access to the variable goes through the cache cell.  The variable's value may change in the future, but the variable itself will not.

We can see how these concepts tie together by disassembling the foo function we defined earlier to see what is going on:

     scheme@(guile-user)> (define (foo a) (lambda (b) (list foo a b)))
     scheme@(guile-user)> ,x foo
     Disassembly of #<procedure foo (a)> at #x203be34:

        0    (assert-nargs-ee/locals 2 1)    ;; 1 arg, 1 local     at (unknown file):1:0
        1    (make-closure 2 6 1)            ;; anonymous procedure at #x203be50 (1 free var)
        4    (free-set! 2 1 0)               ;; free var 0
        6    (return 2)

     ----------------------------------------
     Disassembly of anonymous procedure at #x203be50:

        0    (assert-nargs-ee/locals 2 3)    ;; 1 arg, 3 locals    at (unknown file):1:0
        1    (toplevel-box 2 73 57 71 #t)    ;; `foo'
        6    (box-ref 2 2)
        7    (make-short-immediate 3 772)    ;; ()
        8    (cons 3 1 3)
        9    (free-ref 4 0 0)                ;; free var 0
       11    (cons 3 4 3)
       12    (cons 2 2 3)
       13    (return 2)

First there's some prelude, where foo checks that it was called with only 1 argument.  Then at ip 1, we allocate a new closure and store it in slot 2.  The `6' in the (make-closure 2 6 1) is a relative offset from the instruction pointer of the code for the closure.

A closure is code with data.  We already have the code part initialized; what remains is to set the data.  Ip 4 initializes free variable 0 in the new closure with the value from local variable 1, which corresponds to the first argument of foo: `a'.  Finally we return the closure.

The second stanza disassembles the code for the closure.  After the prelude, we load the variable for the toplevel variable foo into local variable 2.  This lookup occurs lazily, the first time the variable is actually referenced, and the location of the lookup is cached so that future references are very cheap.  See Top-Level Environment Instructions, for more details.  The box-ref dereferences the variable cell, replacing the contents of local 2.

What follows is a sequence of conses to build up the result list. Ip 7 makes the tail of the list.  Ip 8 conses on the value in local 1, corresponding to the first argument to the closure: `b'. Ip 9 loads free variable 0 of local 0 -- the procedure being called -- into slot 4, then ip 11 conses it onto the list. Finally we cons local 2, containing the foo toplevel, onto the front of the list, and we return it.

Object File Format
------------------

To compile a file to disk, we need a format in which to write the compiled code to disk, and later load it into Guile.  A good object file format has a number of characteristics:

  * Above all else, it should be very cheap to load a compiled file.

  * It should be possible to statically allocate constants in the file.  For example, a bytevector literal in source code can be emitted directly into the object file.

  * The compiled file should enable maximum code and data sharing between different processes.

  * The compiled file should contain debugging information, such as line numbers, but that information should be separated from the code itself.  It should be possible to strip debugging information if space is tight.

These characteristics are not specific to Scheme.  Indeed, mainstream languages like C and C++ have solved this issue many times in the past. Guile builds on their work by adopting ELF, the object file format of GNU and other Unix-like systems, as its object file format.  Although Guile uses ELF on all platforms, we do not use platform support for ELF. Guile implements its own linker and loader.  The advantage of using ELF is not sharing code, but sharing ideas.  ELF is simply a well-designed object file format.

An ELF file has two meta-tables describing its contents.  The first meta-table is for the loader, and is called the program table or sometimes the segment table.  The program table divides the file into big chunks that should be treated differently by the loader. Mostly the difference between these segments is their permissions.

Typically all segments of an ELF file are marked as read-only, except that part that represents modifiable static data or static data that needs load-time initialization.  Loading an ELF file is as simple as mmapping the thing into memory with read-only permissions, then using the segment table to mark a small sub-region of the file as writable. This writable section is typically added to the root set of the garbage collector as well.

One ELF segment is marked as ``dynamic'', meaning that it has data of interest to the loader.  Guile uses this segment to record the Guile version corresponding to this file.  There is also an entry in the dynamic segment that points to the address of an initialization thunk that is run to perform any needed link-time initialization.  (This is like dynamic relocations for normal ELF shared objects, except that we compile the relocations as a procedure instead of having the loader interpret a table of relocations.)  Finally, the dynamic segment marks the location of the ``entry thunk'' of the object file.  This thunk is returned to the caller of load-thunk-from-memory or load-thunk-from-file.  When called, it will execute the ``body'' of the compiled expression.

The other meta-table in an ELF file is the section table.  Whereas the program table divides an ELF file into big chunks for the loader, the section table specifies small sections for use by introspective tools like debuggers or the like.  One segment (program table entry) typically contains many sections.  There may be sections outside of any segment, as well.

Typical sections in a Guile .go file include:

.rtl-text
     Bytecode.

.data
     Data that needs initialization, or which may be modified at runtime.

.rodata
     Statically allocated data that needs no run-time initialization, and which therefore can be shared between processes.

.dynamic
     The dynamic section, discussed above.

.symtab
.strtab
     A table mapping addresses in the .rtl-text to procedure names. .strtab is used by .symtab.

.guile.procprops
.guile.arities
.guile.arities.strtab
.guile.docstrs
.guile.docstrs.strtab
     Side tables of procedure properties, arities, and docstrings.

.debug_info
.debug_abbrev
.debug_str
.debug_loc
.debug_line
     Debugging information, in DWARF format.  See the DWARF specification, for more information.

.shstrtab
     Section name string table.

For more information, see the elf(5) man page.  See the DWARF specification (http://dwarfstd.org/) for more on the DWARF debugging format.  Or if you are an adventurous explorer, try running readelf or objdump on compiled .go files.  It's good times!

Instruction Set
---------------

There are currently about 130 instructions in Guile's virtual machine. These instructions represent atomic units of a program's execution. Ideally, they perform one task without conditional branches, then dispatch to the next instruction in the stream.

Instructions themselves are composed of 1 or more 32-bit units.  The low 8 bits of the first word indicate the opcode, and the rest of instruction describe the operands.  There are a number of different ways operands can be encoded.

uN
     An unsigned N-bit integer.  Usually indicates the index of a local variable, but some instructions interpret these operands as immediate values.

l24
     An offset from the current ip, in 32-bit units, as a signed 24-bit value.  Indicates a bytecode address, for a relative jump.

i16
i32
     An immediate Scheme value (see Immediate objects), encoded directly in 16 or 32 bits.

a32
b32
     An immediate Scheme value, encoded as a pair of 32-bit words. a32 and b32 values always go together on the same opcode, and indicate the high and low bits, respectively.  Normally only used on 64-bit systems.

n32
     A statically allocated non-immediate.  The address of the non-immediate is encoded as a signed 32-bit integer, and indicates a relative offset in 32-bit units.  Think of it as SCM x = ip + offset.

s32
     Indirect scheme value, like n32 but indirected.  Think of it as SCM *x = ip + offset.

l32

lo32
     An ip-relative address, as a signed 32-bit integer.  Could indicate a bytecode address, as in make-closure, or a non-immediate address, as with static-patch!.

     l32 and lo32 are the same from the perspective of the virtual machine.  The difference is that an assembler might want to allow an lo32 address to be specified as a label and then some number of words offset from that label, for example when patching a field of a statically allocated object.

b1
     A boolean value: 1 for true, otherwise 0.

xN
     An ignored sequence of N bits.

An instruction is specified by giving its name, then describing its operands.  The operands are packed by 32-bit words, with earlier operands occupying the lower bits.

For example, consider the following instruction specification:

 -- Instruction: free-set! u12:DST u12:SRC x8:_ u24:IDX
     Set free variable IDX from the closure DST to SRC.

The first word in the instruction will start with the 8-bit value corresponding to the FREE-SET! opcode in the low bits, followed by DST and SRC as 12-bit values.  The second word starts with 8 dead bits, followed by the index as a 24-bit immediate value.

Sometimes the compiler can figure out that it is compiling a special case that can be run more efficiently. So, for example, while Guile offers a generic test-and-branch instruction, it also offers specific instructions for special cases, so that the following cases all have their own test-and-branch instructions:

     (if pred then else)
     (if (not pred) then else)
     (if (null? l) then else)
     (if (not (null? l)) then else)

In addition, some Scheme primitives have their own inline implementations.  For example, in the previous section we saw cons.

Guile's instruction set is a complete instruction set, in that it provides the instructions that are suited to the problem, and is not concerned with making a minimal, orthogonal set of instructions. More instructions may be added over time.

Lexical Environment Instructions
................................

These instructions access and mutate the lexical environment of a compiled procedure---its free and bound variables.  See Stack Layout, for more information on the format of stack frames.

 -- Instruction: mov u12:DST u12:SRC
 -- Instruction: long-mov u24:DST x8:_ u24:SRC
     Copy a value from one local slot to another.

     As discussed previously, procedure arguments and local variables are allocated to local slots.  Guile's compiler tries to avoid shuffling variables around to different slots, which often makes mov instructions redundant.  However there are some cases in which shuffling is necessary, and in those cases, mov is the thing to use.

 -- Instruction: make-closure u24:DST l32:OFFSET x8:_ u24:NFREE
     Make a new closure, and write it to DST.  The code for the closure will be found at OFFSET words from the current ip. OFFSET is a signed 32-bit integer.  Space for NFREE free variables will be allocated.

     The size of a closure is currently two words, plus one word per free variable.

 -- Instruction: free-ref u12:DST u12:SRC x8:_ u24:IDX
     Load free variable IDX from the closure SRC into local slot DST.

 -- Instruction: free-set! u12:DST u12:SRC x8:_ u24:IDX
     Set free variable IDX from the closure DST to SRC.

     This instruction is usually used when initializing a closure's free variables, but not to mutate free variables, as variables that are assigned are boxed.

Recall that variables that are assigned are usually allocated in boxes, so that continuations and closures can capture their identity and not their value at one point in time.  Variables are also used in the implementation of top-level bindings; see the next section for more information.

 -- Instruction: box u12:DST u12:SRC
     Create a new variable holding SRC, and place it in DST.

 -- Instruction: box-ref u12:DST u12:SRC
     Unpack the variable at SRC into DST, asserting that the variable is actually bound.

 -- Instruction: box-set! u12:DST u12:SRC
     Set the contents of the variable at DST to SET.

Top-Level Environment Instructions
..................................

These instructions access values in the top-level environment: bindings that were not lexically apparent at the time that the code in question was compiled.

The location in which a toplevel binding is stored can be looked up once and cached for later. The binding itself may change over time, but its location will stay constant.

 -- Instruction: current-module u24:DST
     Store the current module in DST.

 -- Instruction: resolve u24:DST b1:BOUND? x7:_ u24:SYM
     Resolve SYM in the current module, and place the resulting variable in DST.  An error will be signalled if no variable is found.  If BOUND? is true, an error will be signalled if the variable is unbound.

 -- Instruction: define! u12:SYM u12:VAL
     Look up a binding for SYM in the current module, creating it if necessary.  Set its value to VAL.

 -- Instruction: toplevel-box u24:DST s32:VAR-OFFSET s32:MOD-OFFSET n32:SYM-OFFSET b1:BOUND? x31:_
     Load a value.  The value will be fetched from memory, VAR-OFFSET 32-bit words away from the current instruction pointer. VAR-OFFSET is a signed value.  Up to here, toplevel-box is like static-ref.

     Then, if the loaded value is a variable, it is placed in DST, and control flow continues.

     Otherwise, we have to resolve the variable.  In that case we load the module from MOD-OFFSET, just as we loaded the variable.  Usually the module gets set when the closure is created.  SYM-OFFSET specifies the name, as an offset to a symbol.

     We use the module and the symbol to resolve the variable, placing it in DST, and caching the resolved variable so that we will hit the cache next time.  If BOUND? is true, an error will be signalled if the variable is unbound.

 -- Instruction: module-box u24:DST s32:VAR-OFFSET n32:MOD-OFFSET n32:SYM-OFFSET b1:BOUND? x31:_
     Like toplevel-box, except MOD-OFFSET points at a module identifier instead of the module itself.  A module identifier is a module name, as a list, prefixed by a boolean.  If the prefix is true, then the variable is resolved relative to the module's public interface instead of its private interface.

Procedure Call and Return Instructions
......................................

As described earlier (see Stack Layout), Guile's calling convention is that arguments are passed and values returned on the stack.

For calls, both in tail position and in non-tail position, we require that the procedure and the arguments already be shuffled into place befor the call instruction.  ``Into place'' for a tail call means that the procedure should be in slot 0, and the arguments should follow.  For a non-tail call, if the procedure is in slot N, the arguments should follow from slot N+1, and there should be two free slots at N-1 and N-2 in which to save the ip and fp.

Returning values is similar.  Multiple-value returns should have values already shuffled down to start from slot 1 before emitting return-values.  There is a short-cut in the single-value case, in that return handles the trivial shuffling itself.  We start from slot 1 instead of slot 0 to make tail calls to values trivial.

In both calls and returns, the sp is used to indicate to the callee or caller the number of arguments or return values, respectively. After receiving return values, it is the caller's responsibility to restore the frame by resetting the sp to its former value.

 -- Instruction: call u24:PROC x8:_ u24:NLOCALS
     Call a procedure.  PROC is the local corresponding to a procedure. The two values below PROC will be overwritten by the saved call frame data.  The new frame will have space for NLOCALS locals: one for the procedure, and the rest for the arguments which should already have been pushed on.

     When the call returns, execution proceeds with the next instruction. There may be any number of values on the return stack; the precise number can be had by subtracting the address of PROC from the post-call sp.

 -- Instruction: tail-call u24:NLOCALS
     Tail-call a procedure.  Requires that the procedure and all of the arguments have already been shuffled into position.  Will reset the frame to NLOCALS.

 -- Instruction: tail-call/shuffle u24:FROM
     Tail-call a procedure.  The procedure should already be set to slot 0. The rest of the args are taken from the frame, starting at FROM, shuffled down to start at slot 0.  This is part of the implementation of the call-with-values builtin.

 -- Instruction: receive u12:DST u12:PROC x8:_ u24:NLOCALS
     Receive a single return value from a call whose procedure was in PROC, asserting that the call actually returned at least one value.  Afterwards, resets the frame to NLOCALS locals.

 -- Instruction: receive-values u24:PROC b1:ALLOW-EXTRA? x7:_ u24:NVALUES
     Receive a return of multiple values from a call whose procedure was in PROC.  If fewer than NVALUES values were returned, signal an error.  Unless ALLOW-EXTRA? is true, require that the number of return values equals NVALUES exactly.  After receive-values has run, the values can be copied down via mov, or used in place.

 -- Instruction: return u24:SRC
     Return a value.

 -- Instruction: return-values x24:_
     Return a number of values from a call frame.  This opcode corresponds to an application of values in tail position.  As with tail calls, we expect that the values have already been shuffled down to a contiguous array starting at slot 1.  We also expect the frame has already been reset.

 -- Instruction: call/cc x24:_
     Capture the current continuation, and tail-apply the procedure in local slot 1 to it.  This instruction is part of the implementation of call/cc, and is not generated by the compiler.

Function Prologue Instructions
..............................

A function call in Guile is very cheap: the VM simply hands control to the procedure. The procedure itself is responsible for asserting that it has been passed an appropriate number of arguments. This strategy allows arbitrarily complex argument parsing idioms to be developed, without harming the common case.

For example, only calls to keyword-argument procedures ``pay'' for the cost of parsing keyword arguments. (At the time of this writing, calling procedures with keyword arguments is typically two to four times as costly as calling procedures with a fixed set of arguments.)

 -- Instruction: assert-nargs-ee u24:EXPECTED
 -- Instruction: assert-nargs-ge u24:EXPECTED
 -- Instruction: assert-nargs-le u24:EXPECTED
     If the number of actual arguments is not ==, >=, or <= EXPECTED, respectively, signal an error.

     The number of arguments is determined by subtracting the frame pointer from the stack pointer (sp + 1 - fp). See Stack Layout, for more details on stack frames.  Note that EXPECTED includes the procedure itself.

 -- Instruction: br-if-nargs-ne u24:EXPECTED x8:_ l24:OFFSET
 -- Instruction: br-if-nargs-lt u24:EXPECTED x8:_ l24:OFFSET
 -- Instruction: br-if-nargs-gt u24:EXPECTED x8:_ l24:OFFSET
     If the number of actual arguments is not equal, less than, or greater than EXPECTED, respectively, add OFFSET, a signed 24-bit number, to the current instruction pointer.  Note that EXPECTED includes the procedure itself.

     These instructions are used to implement multiple arities, as in case-lambda. See Case-lambda, for more information.

 -- Instruction: alloc-frame u24:NLOCALS
     Ensure that there is space on the stack for NLOCALS local variables, setting them all to SCM_UNDEFINED, except those values that are already on the stack.

 -- Instruction: reset-frame u24:NLOCALS
     Like alloc-frame, but doesn't check that the stack is big enough, and doesn't initialize values to SCM_UNDEFINED.  Used to reset the frame size to something less than the size that was previously set via alloc-frame.

 -- Instruction: assert-nargs-ee/locals u12:EXPECTED u12:NLOCALS
     Equivalent to a sequence of assert-nargs-ee and reserve-locals.  The number of locals reserved is EXPECTED + NLOCALS.

 -- Instruction: br-if-npos-gt u24:NREQ x8:_ u24:NPOS x8:_ l24:OFFSET
     Find the first positional argument after NREQ.  If it is greater than NPOS, jump to OFFSET.

     This instruction is only emitted for functions with multiple clauses, and an earlier clause has keywords and no rest arguments. See Case-lambda, for more on how case-lambda chooses the clause to apply.

 -- Instruction: bind-kwargs u24:NREQ u8:FLAGS u24:NREQ-AND-OPT x8:_ u24:NTOTAL n32:KW-OFFSET
     FLAGS is a bitfield, whose lowest bit is ALLOW-OTHER-KEYS, second bit is HAS-REST, and whose following six bits are unused.

     Find the last positional argument, and shuffle all the rest above NTOTAL.  Initialize the intervening locals to SCM_UNDEFINED.  Then load the constant at KW-OFFSET words from the current IP, and use it and the ALLOW-OTHER-KEYS flag to bind keyword arguments.  If HAS-REST, collect all shuffled arguments into a list, and store it in NREQ-AND-OPT.  Finally, clear the arguments that we shuffled up.

     The parsing is driven by a keyword arguments association list, looked up using KW-OFFSET.  The alist is a list of pairs of the form (KW . INDEX), mapping keyword arguments to their local slot indices.  Unless allow-other-keys is set, the parser will signal an error if an unknown key is found.

     A macro-mega-instruction.

 -- Instruction: bind-rest u24:DST
     Collect any arguments at or above DST into a list, and store that list at DST.

Trampoline Instructions
.......................

Though most applicable objects in Guile are procedures implemented in bytecode, not all are.  There are primitives, continuations, and other procedure-like objects that have their own calling convention.  Instead of adding special cases to the call instruction, Guile wraps these other applicable objects in VM trampoline procedures, then provides special support for these objects in bytecode.

Trampoline procedures are typically generated by Guile at runtime, for example in response to a call to scm_c_make_gsubr.  As such, a compiler probably shouldn't emit code with these instructions.  However, it's still interesting to know how these things work, so we document these trampoline instructions here.

 -- Instruction: subr-call u24:PTR-IDX
     Call a subr, passing all locals in this frame as arguments.  Fetch the foreign pointer from PTR-IDX, a free variable.  Return from the calling frame.

 -- Instruction: foreign-call u12:CIF-IDX u12:PTR-IDX
     Call a foreign function.  Fetch the CIF and foreign pointer from CIF-IDX and PTR-IDX, both free variables.  Return from the calling frame.  Arguments are taken from the stack.

 -- Instruction: continuation-call u24:CONTREGS
     Return to a continuation, nonlocally.  The arguments to the continuation are taken from the stack.  CONTREGS is a free variable containing the reified continuation.

 -- Instruction: compose-continuation u24:CONT
     Compose a partial continution with the current continuation.  The arguments to the continuation are taken from the stack.  CONT is a free variable containing the reified continuation.

 -- Instruction: tail-apply x24:_
     Tail-apply the procedure in local slot 0 to the rest of the arguments. This instruction is part of the implementation of apply, and is not generated by the compiler.

 -- Instruction: builtin-ref u12:DST u12:IDX
     Load a builtin stub by index into DST.

Branch Instructions
...................

All offsets to branch instructions are 24-bit signed numbers, which count 32-bit units.  This gives Guile effectively a 26-bit address range for relative jumps.

 -- Instruction: br l24:OFFSET
     Add OFFSET to the current instruction pointer.

All the conditional branch instructions described below have an INVERT parameter, which if true reverses the test: br-if-true becomes br-if-false, and so on.

 -- Instruction: br-if-true u24:TEST b1:INVERT x7:_ l24:OFFSET
     If the value in TEST is true for the purposes of Scheme, add OFFSET to the current instruction pointer.

 -- Instruction: br-if-null u24:TEST b1:INVERT x7:_ l24:OFFSET
     If the value in TEST is the end-of-list or Lisp nil, add OFFSET to the current instruction pointer.

 -- Instruction: br-if-nil u24:TEST b1:INVERT x7:_ l24:OFFSET
     If the value in TEST is false to Lisp, add OFFSET to the current instruction pointer.

 -- Instruction: br-if-pair u24:TEST b1:INVERT x7:_ l24:OFFSET
     If the value in TEST is a pair, add OFFSET to the current instruction pointer.

 -- Instruction: br-if-struct u24:TEST b1:INVERT x7:_ l24:OFFSET
     If the value in TEST is a struct, add OFFSET number to the current instruction pointer.

 -- Instruction: br-if-char u24:TEST b1:INVERT x7:_ l24:OFFSET
     If the value in TEST is a char, add OFFSET to the current instruction pointer.

 -- Instruction: br-if-tc7 u24:TEST b1:INVERT u7:TC7 l24:OFFSET
     If the value in TEST has the TC7 given in the second word, add OFFSET to the current instruction pointer.  TC7 codes are part of the way Guile represents non-immediate objects, and are deep wizardry. See libguile/tags.h for all the details.

 -- Instruction: br-if-eq u12:A u12:B b1:INVERT x7:_ l24:OFFSET
 -- Instruction: br-if-eqv u12:A u12:B b1:INVERT x7:_ l24:OFFSET
 -- Instruction: br-if-equal u12:A u12:B b1:INVERT x7:_ l24:OFFSET
     If the value in A is eq?, eqv?, or equal? to the value in B, respectively, add OFFSET to the current instruction pointer.

 -- Instruction: br-if-= u12:A u12:B b1:INVERT x7:_ l24:OFFSET
 -- Instruction: br-if-< u12:A u12:B b1:INVERT x7:_ l24:OFFSET
 -- Instruction: br-if-<= u12:A u12:B b1:INVERT x7:_ l24:OFFSET
     If the value in A is =, <, or <= to the value in B, respectively, add OFFSET to the current instruction pointer.

Constant Instructions
.....................

The following instructions load literal data into a program.  There are two kinds.

The first set of instructions loads immediate values.  These instructions encode the immediate directly into the instruction stream.

 -- Instruction: make-short-immediate u8:DST i16:LOW-BITS
     Make an immediate whose low bits are LOW-BITS, and whose top bits are 0.

 -- Instruction: make-long-immediate u24:DST i32:LOW-BITS
     Make an immediate whose low bits are LOW-BITS, and whose top bits are 0.

 -- Instruction: make-long-long-immediate u24:DST a32:HIGH-BITS b32:LOW-BITS
     Make an immediate with HIGH-BITS and LOW-BITS.

Non-immediate constant literals are referenced either directly or indirectly.  For example, Guile knows at compile-time what the layout of a string will be like, and arranges to embed that object directly in the compiled image.  A reference to a string will use make-non-immediate to treat a pointer into the compilation unit as a SCM value directly.

 -- Instruction: make-non-immediate u24:DST n32:OFFSET
     Load a pointer to statically allocated memory into DST.  The object's memory is will be found OFFSET 32-bit words away from the current instruction pointer.  Whether the object is mutable or immutable depends on where it was allocated by the compiler, and loaded by the loader.

Some objects must be unique across the whole system.  This is the case for symbols and keywords.  For these objects, Guile arranges to initialize them when the compilation unit is loaded, storing them into a slot in the image.  References go indirectly through that slot. static-ref is used in this case.

 -- Instruction: static-ref u24:DST s32:OFFSET
     Load a SCM value into DST.  The SCM value will be fetched from memory, OFFSET 32-bit words away from the current instruction pointer.  OFFSET is a signed value.

Fields of non-immediates may need to be fixed up at load time, because we do not know in advance at what address they will be loaded.  This is the case, for example, for a pair containing a non-immediate in one of its fields.  static-ref and static-patch! are used in these situations.

 -- Instruction: static-set! u24:SRC lo32:OFFSET
     Store a SCM value into memory, OFFSET 32-bit words away from the current instruction pointer.  OFFSET is a signed value.

 -- Instruction: static-patch! x24:_ lo32:DST-OFFSET l32:SRC-OFFSET
     Patch a pointer at DST-OFFSET to point to SRC-OFFSET.  Both offsets are signed 32-bit values, indicating a memory address as a number of 32-bit words away from the current instruction pointer.

Many kinds of literals can be loaded with the above instructions, once the compiler has prepared the statically allocated data.  This is the case for vectors, strings, uniform vectors, pairs, and procedures with no free variables.  Other kinds of data might need special initializers; those instructions follow.

 -- Instruction: string->number u12:DST u12:SRC
     Parse a string in SRC to a number, and store in DST.

 -- Instruction: string->symbol u12:DST u12:SRC
     Parse a string in SRC to a symbol, and store in DST.

 -- Instruction: symbol->keyword u12:DST u12:SRC
     Make a keyword from the symbol in SRC, and store it in DST.

 -- Instruction: load-typed-array u8:DST u8:TYPE u8:SHAPE n32:OFFSET u32:LEN
     Load the contiguous typed array located at OFFSET 32-bit words away from the instruction pointer, and store into DST.  LEN is a byte length.  OFFSET is signed.

Dynamic Environment Instructions
................................

Guile's virtual machine has low-level support for dynamic-wind, dynamic binding, and composable prompts and aborts.

 -- Instruction: abort x24:_
     Abort to a prompt handler.  The tag is expected in slot 1, and the rest of the values in the frame are returned to the prompt handler.  This corresponds to a tail application of abort-to-prompt.

     If no prompt can be found in the dynamic environment with the given tag, an error is signalled.  Otherwise all arguments are passed to the prompt's handler, along with the captured continuation, if necessary.

     If the prompt's handler can be proven to not reference the captured continuation, no continuation is allocated.  This decision happens dynamically, at run-time; the general case is that the continuation may be captured, and thus resumed.  A reinstated continuation will have its arguments pushed on the stack from slot 1, as if from a multiple-value return, and control resumes in the caller.  Thus to the calling function, a call to abort-to-prompt looks like any other function call.

 -- Instruction: prompt u24:TAG b1:ESCAPE-ONLY? x7:_ u24:PROC-SLOT x8:_ l24:HANDLER-OFFSET
     Push a new prompt on the dynamic stack, with a tag from TAG and a handler at HANDLER-OFFSET words from the current IP.

     If an abort is made to this prompt, control will jump to the handler. The handler will expect a multiple-value return as if from a call with the procedure at PROC-SLOT, with the reified partial continuation as the first argument, followed by the values returned to the handler. If control returns to the handler, the prompt is already popped off by the abort mechanism.  (Guile's prompt implements Felleisen's --F-- operator.)

     If ESCAPE-ONLY? is nonzero, the prompt will be marked as escape-only, which allows an abort to this prompt to avoid reifying the continuation.

     See Prompts, for more information on prompts.

 -- Instruction: wind u12:WINDER u12:UNWINDER
     Push wind and unwind procedures onto the dynamic stack. Note that neither are actually called; the compiler should emit calls to wind and unwind for the normal dynamic-wind control flow.  Also note that the compiler should have inserted checks that they wind and unwind procs are thunks, if it could not prove that to be the case.  See Dynamic Wind.

 -- Instruction: unwind x24:_
     A normal exit from the dynamic extent of an expression. Pop the top entry off of the dynamic stack.

 -- Instruction: push-fluid u12:FLUID u12:VALUE
     Dynamically bind VALUE to FLUID by creating a with-fluids object and pushing that object on the dynamic stack.  See Fluids and Dynamic States.

 -- Instruction: pop-fluid x24:_
     Leave the dynamic extent of a with-fluid* expression, restoring the fluid to its previous value.  push-fluid should always be balanced with pop-fluid.

 -- Instruction: fluid-ref u12:DST u12:SRC
     Reference the fluid in SRC, and place the value in DST.

 -- Instruction: fluid-set u12:FLUID u12:VAL
     Set the value of the fluid in DST to the value in SRC.

Miscellaneous Instructions
..........................

 -- Instruction: halt x24:_
     Bring the VM to a halt, returning all the values from the stack.  Used in the ``boot continuation'', which is used when entering the VM from C.

Inlined Scheme Instructions
...........................

The Scheme compiler can recognize the application of standard Scheme procedures.  It tries to inline these small operations to avoid the overhead of creating new stack frames.  This allows the compiler to optimize better.

 -- Instruction: make-vector/immediate u8:DST u8:LENGTH u8:INIT
     Make a short vector of known size and write it to DST.  The vector will have space for LENGTH slots, an immediate value.  They will be filled with the value in slot INIT.

 -- Instruction: vector-length u12:DST u12:SRC
     Store the length of the vector in SRC in DST.

 -- Instruction: vector-ref u8:DST u8:SRC u8:IDX
     Fetch the item at position IDX in the vector in SRC, and store it in DST.

 -- Instruction: vector-ref/immediate u8:DST u8:SRC u8:IDX
     Fill DST with the item IDX elements into the vector at SRC.  Useful for building data types using vectors.

 -- Instruction: vector-set! u8:DST u8:IDX u8:SRC
     Store SRC into the vector DST at index IDX.

 -- Instruction: vector-set!/immediate u8:DST u8:IDX u8:SRC
     Store SRC into the vector DST at index IDX.  Here IDX is an immediate value.

 -- Instruction: struct-vtable u12:DST u12:SRC
     Store the vtable of SRC into DST.

 -- Instruction: allocate-struct/immediate u8:DST u8:VTABLE u8:NFIELDS
     Allocate a new struct with VTABLE, and place it in DST.  The struct will be constructed with space for NFIELDS fields, which should correspond to the field count of the VTABLE.

 -- Instruction: struct-ref/immediate u8:DST u8:SRC u8:IDX
     Fetch the item at slot IDX in the struct in SRC, and store it in DST.  IDX is an immediate unsigned 8-bit value.

 -- Instruction: struct-set!/immediate u8:DST u8:IDX u8:SRC
     Store SRC into the struct DST at slot IDX.  IDX is an immediate unsigned 8-bit value.

 -- Instruction: class-of u12:DST u12:TYPE
     Store the vtable of SRC into DST.

 -- Instruction: make-array u12:DST u12:TYPE x8:_ u12:FILL u12:BOUNDS
     Make a new array with TYPE, FILL, and BOUNDS, storing it in DST.

 -- Instruction: string-length u12:DST u12:SRC
     Store the length of the string in SRC in DST.

 -- Instruction: string-ref u8:DST u8:SRC u8:IDX
     Fetch the character at position IDX in the string in SRC, and store it in DST.

 -- Instruction: cons u8:DST u8:CAR u8:CDR
     Cons CAR and CDR, and store the result in DST.

 -- Instruction: car u12:DST u12:SRC
     Place the car of SRC in DST.

 -- Instruction: cdr u12:DST u12:SRC
     Place the cdr of SRC in DST.

 -- Instruction: set-car! u12:PAIR u12:CAR
     Set the car of DST to SRC.

 -- Instruction: set-cdr! u12:PAIR u12:CDR
     Set the cdr of DST to SRC.

Note that caddr and friends compile to a series of car and cdr instructions.

Inlined Mathematical Instructions
.................................

Inlining mathematical operations has the obvious advantage of handling fixnums without function calls or allocations. The trick, of course, is knowing when the result of an operation will be a fixnum, and there might be a couple bugs here.

More instructions could be added here over time.

All of these operations place their result in their first operand, DST.

 -- Instruction: add u8:DST u8:A u8:B
     Add A to B.

 -- Instruction: add1 u12:DST u12:SRC
     Add 1 to the value in SRC.

 -- Instruction: sub u8:DST u8:A u8:B
     Subtract B from A.

 -- Instruction: sub1 u12:DST u12:SRC
     Subtract 1 from SRC.

 -- Instruction: mul u8:DST u8:A u8:B
     Multiply A and B.

 -- Instruction: div u8:DST u8:A u8:B
     Divide A by B.

 -- Instruction: quo u8:DST u8:A u8:B
     Divide A by B.

 -- Instruction: rem u8:DST u8:A u8:B
     Divide A by B.

 -- Instruction: mod u8:DST u8:A u8:B
     Compute the modulo of A by B.

 -- Instruction: ash u8:DST u8:A u8:B
     Shift A arithmetically by B bits.

 -- Instruction: logand u8:DST u8:A u8:B
     Compute the bitwise and of A and B.

 -- Instruction: logior u8:DST u8:A u8:B
     Compute the bitwise inclusive or of A with B.

 -- Instruction: logxor u8:DST u8:A u8:B
     Compute the bitwise exclusive or of A with B.

Inlined Bytevector Instructions
...............................

Bytevector operations correspond closely to what the current hardware can do, so it makes sense to inline them to VM instructions, providing a clear path for eventual native compilation. Without this, Scheme programs would need other primitives for accessing raw bytes -- but these primitives are as good as any.

 -- Instruction: bv-u8-ref u8:DST u8:SRC u8:IDX
 -- Instruction: bv-s8-ref u8:DST u8:SRC u8:IDX
 -- Instruction: bv-u16-ref u8:DST u8:SRC u8:IDX
 -- Instruction: bv-s16-ref u8:DST u8:SRC u8:IDX
 -- Instruction: bv-u32-ref u8:DST u8:SRC u8:IDX
 -- Instruction: bv-s32-ref u8:DST u8:SRC u8:IDX
 -- Instruction: bv-u64-ref u8:DST u8:SRC u8:IDX
 -- Instruction: bv-s64-ref u8:DST u8:SRC u8:IDX
 -- Instruction: bv-f32-ref u8:DST u8:SRC u8:IDX
 -- Instruction: bv-f64-ref u8:DST u8:SRC u8:IDX

     Fetch the item at byte offset IDX in the bytevector SRC, and store it in DST.  All accesses use native endianness.

 -- Instruction: bv-u8-set! u8:DST u8:IDX u8:SRC
 -- Instruction: bv-s8-set! u8:DST u8:IDX u8:SRC
 -- Instruction: bv-u16-set! u8:DST u8:IDX u8:SRC
 -- Instruction: bv-s16-set! u8:DST u8:IDX u8:SRC
 -- Instruction: bv-u32-set! u8:DST u8:IDX u8:SRC
 -- Instruction: bv-s32-set! u8:DST u8:IDX u8:SRC
 -- Instruction: bv-u64-set! u8:DST u8:IDX u8:SRC
 -- Instruction: bv-s64-set! u8:DST u8:IDX u8:SRC
 -- Instruction: bv-f32-set! u8:DST u8:IDX u8:SRC
 -- Instruction: bv-f64-set! u8:DST u8:IDX u8:SRC

     Store SRC into the bytevector DST at byte offset IDX. Multibyte values are written using native endianness.