     [file version.texi not included]

This file documents vmgen (Gforth VERSION).

Introduction
************

Vmgen is a tool for writing efficient interpreters.  It takes a simple virtual machine description and generates efficient C code for dealing with the virtual machine code in various ways (in particular, executing it).  The run-time efficiency of the resulting interpreters is usually within a factor of 10 of machine code produced by an optimizing compiler.

The interpreter design strategy supported by vmgen is to divide the interpreter into two parts:

  * The front end takes the source code of the language to be implemented, and translates it into virtual machine code.  This is similar to an ordinary compiler front end; typically an interpreter front-end performs no optimization, so it is relatively simple to implement and runs fast.

  * The virtual machine interpreter executes the virtual machine code.

Such a division is usually used in interpreters, for modularity as well as for efficiency.  The virtual machine code is typically passed between front end and virtual machine interpreter in memory, like in a load-and-go compiler; this avoids the complexity and time cost of writing the code to a file and reading it again.

A virtual machine (VM) represents the program as a sequence of VM instructions, following each other in memory, similar to real machine code.  Control flow occurs through VM branch instructions, like in a real machine.

In this setup, vmgen can generate most of the code dealing with virtual machine instructions from a simple description of the virtual machine instructions (...), in particular:

VM instruction execution

VM code generation
     Useful in the front end.

VM code decompiler
     Useful for debugging the front end.

VM code tracing
     Useful for debugging the front end and the VM interpreter.  You will typically provide other means for debugging the user's programs at the source level.

VM code profiling
     Useful for optimizing the VM insterpreter with superinstructions (...).

VMgen supports efficient interpreters though various optimizations, in particular

  * Threaded code

  * Caching the top-of-stack in a register

  * Combining VM instructions into superinstructions

  * Replicating VM (super)instructions for better BTB prediction accuracy (not yet in vmgen-ex, but already in Gforth).

As a result, vmgen-based interpreters are only about an order of magintude slower than native code from an optimizing C compiler on small benchmarks; on large benchmarks, which spend more time in the run-time system, the slowdown is often less (e.g., the slowdown of a Vmgen-generated JVM interpreter over the best JVM JIT compiler we measured is only a factor of 2-3 for large benchmarks; some other JITs and all other interpreters we looked at were slower than our interpreter).

VMs are usually designed as stack machines (passing data between VM instructions on a stack), and vmgen supports such designs especially well; however, you can also use vmgen for implementing a register VM and still benefit from most of the advantages offered by vmgen.

There are many potential uses of the instruction descriptions that are not implemented at the moment, but we are open for feature requests, and we will implement new features if someone asks for them; so the feature list above is not exhaustive.

Why interpreters?
*****************

Interpreters are a popular language implementation technique because they combine all three of the following advantages:

  * Ease of implementation

  * Portability

  * Fast edit-compile-run cycle

The main disadvantage of interpreters is their run-time speed.  However, there are huge differences between different interpreters in this area: the slowdown over optimized C code on programs consisting of simple operations is typically a factor of 10 for the more efficient interpreters, and a factor of 1000 for the less efficient ones (the slowdown for programs executing complex operations is less, because the time spent in libraries for executing complex operations is the same in all implementation strategies).

Vmgen makes it even easier to implement interpreters.  It also supports techniques for building efficient interpreters.

Concepts
********

Front-end and virtual machine interpreter
=========================================

Interpretive systems are typically divided into a front end that parses the input language and produces an intermediate representation for the program, and an interpreter that executes the intermediate representation of the program.

For efficient interpreters the intermediate representation of choice is virtual machine code (rather than, e.g., an abstract syntax tree). Virtual machine (VM) code consists of VM instructions arranged sequentially in memory; they are executed in sequence by the VM interpreter, except for VM branch instructions, which implement control structures.  The conceptual similarity to real machine code results in the name virtual machine.

In this framework, vmgen supports building the VM interpreter and any other component dealing with VM instructions.  It does not have any support for the front end, apart from VM code generation support.  The front end can be implemented with classical compiler front-end techniques, supported by tools like flex and bison.

The intermediate representation is usually just internal to the interpreter, but some systems also support saving it to a file, either as an image file, or in a full-blown linkable file format (e.g., JVM). Vmgen currently has no special support for such features, but the information in the instruction descriptions can be helpful, and we are open for feature requests and suggestions.

Data handling
=============

Most VMs use one or more stacks for passing temporary data between VM instructions.  Another option is to use a register machine architecture for the virtual machine; however, this option is either slower or significantly more complex to implement than a stack machine architecture.

Vmgen has special support and optimizations for stack VMs, making their implementation easy and efficient.

You can also implement a register VM with vmgen (see Register Machines), and you will still profit from most vmgen features.

Stack items all have the same size, so they typically will be as wide as an integer, pointer, or floating-point value.  Vmgen supports treating two consecutive stack items as a single value, but anything larger is best kept in some other memory area (e.g., the heap), with pointers to the data on the stack.

Another source of data is immediate arguments VM instructions (in the VM instruction stream).  The VM instruction stream is handled similar to a stack in vmgen.

Vmgen has no built-in support for nor restrictions against garbage collection.  If you need garbage collection, you need to provide it in your run-time libraries.  Using reference counting is probably harder, but might be possible (contact us if you are interested).

Dispatch
========

Understanding this section is probably not necessary for using vmgen, but it may help.  You may want to skip it now, and read it if you find statements about dispatch methods confusing.

After executing one VM instruction, the VM interpreter has to dispatch the next VM instruction (vmgen calls the dispatch routine NEXT). Vmgen supports two methods of dispatch:

switch dispatch
     In this method the VM interpreter contains a giant switch statement, with one case for each VM instruction.  The VM instructions are represented by integers (e.g., produced by an enum) in the VM code, and dipatch occurs by loading the next integer from the VM code, switching on it, and continuing at the appropriate case; after executing the VM instruction, jump back to the dispatch code.

threaded code
     This method represents a VM instruction in the VM code by the address of the start of the machine code fragment for executing the VM instruction. Dispatch consists of loading this address, jumping to it, and incrementing the VM instruction pointer.  Typically the threaded-code dispatch code is appended directly to the code for executing the VM instruction.  Threaded code cannot be implemented in ANSI C, but it can be implemented using GNU C's labels-as-values extension (see labels as values).

Invoking vmgen
**************

The usual way to invoke vmgen is as follows:

     vmgen INFILE

Here INFILE is the VM instruction description file, which usually ends in .vmg.  The output filenames are made by taking the basename of infile (i.e., the output files will be created in the current working directory) and replacing .vmg with -vm.i, -disasm.i, -gen.i, -labels.i, -profile.i, and -peephole.i.  E.g., bison hack/foo.vmg will create foo-vm.i etc.

The command-line options supported by vmgen are

--help
-h
     Print a message about the command-line options

--version
-v
     Print version and exit

Example
*******

Example overview
================

There are two versions of the same example for using vmgen: vmgen-ex and vmgen-ex2 (you can also see Gforth as example, but it uses additional (undocumented) features, and also differs in some other respects).  The example implements mini, a tiny Modula-2-like language with a small JavaVM-like virtual machine. The difference between the examples is that vmgen-ex uses many casts, and vmgen-ex2 tries to avoids most casts and uses unions instead.

The files provided with each example are:

     Makefile
     README
     disasm.c           wrapper file
     engine.c           wrapper file
     peephole.c         wrapper file
     profile.c          wrapper file
     mini-inst.vmg      simple VM instructions
     mini-super.vmg     superinstructions (empty at first)
     mini.h             common declarations
     mini.l             scanner
     mini.y             front end (parser, VM code generator)
     support.c          main() and other support functions
     fib.mini           example mini program
     simple.mini        example mini program
     test.mini          example mini program (tests everything)
     test.out           test.mini output
     stat.awk           script for aggregating profile information
     peephole-blacklist list of instructions not allowed in superinstructions
     seq2rule.awk       script for creating superinstructions

For your own interpreter, you would typically copy the following files and change little, if anything:

     disasm.c           wrapper file
     engine.c           wrapper file
     peephole.c         wrapper file
     profile.c          wrapper file
     stat.awk           script for aggregating profile information
     seq2rule.awk       script for creating superinstructions

You would typically change much in or replace the following files:

     Makefile
     mini-inst.vmg      simple VM instructions
     mini.h             common declarations
     mini.l             scanner
     mini.y             front end (parser, VM code generator)
     support.c          main() and other support functions
     peephole-blacklist list of instructions not allowed in superinstructions

You can build the example by cding into the example's directory, and then typing make; you can check that it works with make check.  You can run run mini programs like this:

     ./mini fib.mini

To learn about the options, type ./mini -h.

Using profiling to create superinstructions
===========================================

I have not added rules for this in the Makefile (there are many options for selecting superinstructions, and I did not want to hardcode one into the Makefile), but there are some supporting scripts, and here's an example:

Suppose you want to use fib.mini and test.mini as training programs, you get the profiles like this:

     make fib.prof test.prof #takes a few seconds

You can aggregate these profiles with stat.awk:

     awk -f stat.awk fib.prof test.prof

The result contains lines like:

           2      16        36910041 loadlocal lit

This means that the sequence loadlocal lit statically occurs a total of 16 times in 2 profiles, with a dynamic execution count of 36910041.

The numbers can be used in various ways to select superinstructions. E.g., if you just want to select all sequences with a dynamic execution count exceeding 10000, you would use the following pipeline:

     awk -f stat.awk fib.prof test.prof|
     awk '$3>=10000'|                #select sequences
     fgrep -v -f peephole-blacklist| #eliminate wrong instructions
     awk -f seq2rule.awk|      #transform sequences into superinstruction rules
     sort -k 3 >mini-super.vmg       #sort sequences

The file peephole-blacklist contains all instructions that directly access a stack or stack pointer (for mini: call, return); the sort step is necessary to ensure that prefixes preceed larger superinstructions.

Now you can create a version of mini with superinstructions by just saying make

Input File Format
*****************

Vmgen takes as input a file containing specifications of virtual machine instructions.  This file usually has a name ending in .vmg.

Most examples are taken from the example in vmgen-ex.

Input File Grammar
==================

The grammar is in EBNF format, with A|B meaning ``A or B'', {C} meaning 0 or more repetitions of C and [D] meaning 0 or 1 repetitions of D.

Vmgen input is not free-format, so you have to take care where you put spaces and especially newlines; it's not as bad as makefiles, though: any sequence of spaces and tabs is equivalent to a single space.

     description: {instruction|comment|eval-escape}

     instruction: simple-inst|superinst

     simple-inst: ident " (" stack-effect " )" newline c-code newline newline

     stack-effect: {ident} " --" {ident}

     super-inst: ident " =" ident {ident}

     comment:      "\ "  text newline

     eval-escape:  "\e " text newline

Note that the \s in this grammar are meant literally, not as C-style encodings for non-printable characters.

The C code in simple-inst must not contain empty lines (because vmgen would mistake that as the end of the simple-inst.  The text in comment and eval-escape must not contain a newline. Ident must conform to the usual conventions of C identifiers (otherwise the C compiler would choke on the vmgen output).

Vmgen understands a few extensions beyond the grammar given here, but these extensions are only useful for building Gforth.  You can find a description of the format used for Gforth in prim.

The text in eval-escape is Forth code that is evaluated when vmgen reads the line.  If you do not know (and do not want to learn) Forth, you can build the text according to the following grammar; these rules are normally all Forth you need for using vmgen:

     text: stack-decl|type-prefix-decl|stack-prefix-decl

     stack-decl: "stack " ident ident ident
     type-prefix-decl:
         's" ' string '" ' ("single"|"double") ident "type-prefix" ident
     stack-prefix-decl:  ident "stack-prefix" string

Note that the syntax of this code is not checked thoroughly (there are many other Forth program fragments that could be written there).

If you know Forth, the stack effects of the non-standard words involved are:

     stack        ( "name" "pointer" "type" -- )
                  ( name execution: -- stack )
     type-prefix  ( addr u xt1 xt2 n stack "prefix" -- )
     single       ( -- xt1 xt2 n )
     double       ( -- xt1 xt2 n )
     stack-prefix ( stack "prefix" -- )

Simple instructions
===================

We will use the following simple VM instruction description as example:

     sub ( i1 i2 -- i )
     i = i1-i2;

The first line specifies the name of the VM instruction (sub) and its stack effect (i1 i2 -- i).  The rest of the description is just plain C code.

The stack effect specifies that sub pulls two integers from the data stack and puts them in the C variables i1 and i2 (with the rightmost item (i2) taken from the top of stack) and later
pushes one integer (i)) on the data stack (the rightmost item is
on the top afterwards).

How do we know the type and stack of the stack items?  Vmgen uses
prefixes, similar to Fortran; in contrast to Fortran, you have to
define the prefix first:

     \E s" Cell"   single data-stack type-prefix i

This defines the prefix i to refer to the type Cell (defined as long in mini.h) and, by default, to the data-stack.  It also specifies that this type takes one stack item (single).  The type prefix is part of the variable name.

Before we can use data-stack in this way, we have to define it:

     \E stack data-stack sp Cell

This line defines the stack data-stack, which uses the stack pointer sp, and each item has the basic type Cell; other types have to fit into one or two Cells (depending on whether the type is single or double wide), and are converted from and
to Cells on accessing the data-stack) with conversion macros
(see Conversion macros).  Stacks grow towards lower addresses in
vmgen-erated interpreters.

We can override the default stack of a stack item by using a stack
prefix.  E.g., consider the following instruction:

     lit ( #i -- i )

The VM instruction lit takes the item i from the instruction stream (indicated by the prefix #), and pushes it on the (default) data stack.  The stack prefix is not part of the variable name.  Stack prefixes are defined like this:

     \E inst-stream stack-prefix #

This definition defines that the stack prefix # specifies the ``stack'' inst-stream.  Since the instruction stream behaves a little differently than an ordinary stack, it is predefined, and you do not need to define it.

The instruction stream contains instructions and their immediate arguments, so specifying that an argument comes from the instruction stream indicates an immediate argument.  Of course, instruction stream arguments can only appear to the left of -- in the stack effect. If there are multiple instruction stream arguments, the leftmost is the first one (just as the intuition suggests).

C Code Macros
.............

Vmgen recognizes the following strings in the C code part of simple instructions:

SET_IP
     As far as vmgen is concerned, a VM instruction containing this ends a VM basic block (used in profiling to delimit profiled sequences).  On the C level, this also sets the instruction pointer.

SUPER_END
     This ends a basic block (for profiling), without a SET_IP.

TAIL;
     Vmgen replaces TAIL; with code for ending a VM instruction and dispatching the next VM instruction.  This happens automatically when control reaches the end of the C code.  If you want to have this in the middle of the C code, you need to use TAIL;.  A typical example is a conditional VM branch:

          if (branch_condition) {
            SET_IP(target); TAIL;
          }
          /* implicit tail follows here */

     In this example, TAIL; is not strictly necessary, because there is another one implicitly after the if-statement, but using it improves branch prediction accuracy slightly and allows other optimizations.

SUPER_CONTINUE
     This indicates that the implicit tail at the end of the VM instruction dispatches the sequentially next VM instruction even if there is a SET_IP in the VM instruction.  This enables an optimization that is not yet implemented in the vmgen-ex code (but in Gforth).  The typical application is in conditional VM branches:

          if (branch_condition) {
            SET_IP(target); TAIL; /* now this TAIL is necessary */
          }
          SUPER_CONTINUE;

Note that vmgen is not smart about C-level tokenization, comments, strings, or conditional compilation, so it will interpret even a commented-out SUPER_END as ending a basic block (or, e.g., RETAIL; as TAIL;).  Conversely, vmgen requires the literal presence of these strings; vmgen will not see them if they are hiding in a C preprocessor macro.

C Code restrictions
...................

Vmgen generates code and performs some optimizations under the assumption that the user-supplied C code does not access the stack pointers or stack items, and that accesses to the instruction pointer only occur through special macros.  In general you should heed these restrictions.  However, if you need to break these restrictions, read the following.

Accessing a stack or stack pointer directly can be a problem for several reasons:

  * You may cache the top-of-stack item in a local variable (that is allocated to a register).  This is the most frequent source of trouble. You can deal with it either by not using top-of-stack caching (slowdown factor 1-1.4, depending on machine), or by inserting flushing code (e.g., IF_spTOS(sp[...] = spTOS);) at the start and reloading code (e.g., IF_spTOS(spTOS = sp[0])) at the end of problematic C code.  Vmgen inserts a stack pointer update before the start of the user-supplied C code, so the flushing code has to use an index that corrects for that.  In the future, this flushing may be done automatically by mentioning a special string in the C code.

  * The vmgen-erated code loads the stack items from stack-pointer-indexed memory into variables before the user-supplied C code, and stores them from variables to stack-pointer-indexed memory afterwards.  If you do any writes to the stack through its stack pointer in your C code, it will not affact the variables, and your write may be overwritten by the stores after the C code.  Similarly, a read from a stack using a stack pointer will not reflect computations of stack items in the same VM instruction.

  * Superinstructions keep stack items in variables across the whole superinstruction.  So you should not include VM instructions, that access a stack or stack pointer, as components of superinstructions.

You should access the instruction pointer only through its special macros (IP, SET_IP, IPTOS); this ensure that these macros can be implemented in several ways for best performance. IP points to the next instruction, and IPTOS is its contents.

Superinstructions
=================

Here is an example of a superinstruction definition:

     lit_sub = lit sub

lit_sub is the name of the superinstruction, and lit and sub are its components.  This superinstruction performs the same action as the sequence lit and sub.  It is generated automatically by the VM code generation functions whenever that sequence occurs, so you only need to add this definition if you want to use this superinstruction (and even that can be partially automatized, see ...).

Vmgen requires that the component instructions are simple instructions defined before superinstructions using the components.  Currently, vmgen also requires that all the subsequences at the start of a superinstruction (prefixes) must be defined as superinstruction before the superinstruction.  I.e., if you want to define a superinstruction

     sumof5 = add add add add

you first have to define

     add ( n1 n2 -- n )
     n = n1+n2;

     sumof3 = add add
     sumof4 = add add add

Here, sumof4 is the longest prefix of sumof5, and sumof3 is the longest prefix of sumof4.

Note that vmgen assumes that only the code it generates accesses stack pointers, the instruction pointer, and various stack items, and it performs optimizations based on this assumption.  Therefore, VM instructions that change the instruction pointer should only be used as last component; a VM instruction that accesses a stack pointer should not be used as component at all.  Vmgen does not check these restrictions, they just result in bugs in your interpreter.

Using the generated code
************************

The easiest way to create a working VM interpreter with vmgen is probably to start with one of the examples, and modify it for your purposes.  This chapter is just the reference manual for the macros etc. used by the generated code, and the other context expected by the generated code, and what you can do with the various generated files.

VM engine
=========

The VM engine is the VM interpreter that executes the VM code.  It is essential for an interpretive system.

Vmgen supports two methods of VM instruction dispatch: threaded code (fast, but gcc-specific), and switch dispatch (slow, but portable across C compilers); you can use conditional compilation (defined(__GNUC__)) to choose between these methods, and our example does so.

For both methods, the VM engine is contained in a C-level function. Vmgen generates most of the contents of the function for you (NAME-vm.i), but you have to define this function, and macros and variables used in the engine, and initialize the variables. In our example the engine function also includes NAME-labels.i (see VM instruction table).

The following macros and variables are used in NAME-vm.i:

LABEL(INST_NAME)
     This is used just before each VM instruction to provide a jump or switch label (the : is provided by vmgen).  For switch dispatch this should expand to case LABEL; for threaded-code dispatch this should just expand to case LABEL.  In either case LABEL is usually the INST_NAME with some prefix or suffix to avoid naming conflicts.

NAME(INST_NAME_STRING)
     Called on entering a VM instruction with a string containing the name of the VM instruction as parameter.  In normal execution this should be a noop, but for tracing this usually prints the name, and possibly other information (several VM registers in our example).

DEF_CA
     Usually empty.  Called just inside a new scope at the start of a VM instruction.  Can be used to define variables that should be visible during every VM instruction.  If you define this macro as non-empty, you have to provide the finishing ; in the macro.

NEXT_P0 NEXT_P1 NEXT_P2
     The three parts of instruction dispatch.  They can be defined in different ways for best performance on various processors (see engine.c in the example or engine/threaded.h in Gforth). NEXT_P0 is invoked right at the start of the VM isntruction (but after DEF_CA), NEXT_P1 right after the user-supplied C code, and NEXT_P2 at the end.  The actual jump has to be performed by NEXT_P2.

     The simplest variant is if NEXT_P2 does everything and the other macros do nothing.  Then also related macros like IP, SET_IP, IP, INC_IP and IPTOS are very straightforward to define.  For switch dispatch this code consists just of a jump to the dispatch code (goto next_inst; in our example; for direct threaded code it consists of something like (cfa=*ip++; goto *cfa;).

     Pulling code (usually the cfa=*ip;) up into NEXT_P1 usually does not cause problems, but pulling things up into NEXT_P0 usually requires changing the other macros (and, at least for Gforth on Alpha, it does not buy much, because the compiler often manages to schedule the relevant stuff up by itself).  An even more extreme variant is to pull code up even further, into, e.g., NEXT_P1 of the previous VM instruction (prefetching, useful on PowerPCs).

INC_IP(N)
     This increments IP by N.

vm_A2B(a,b)
     Type casting macro that assigns a (of type A) to b (of type B).  This is mainly used for getting stack items into variables and back.  So you need to define macros for every combination of stack basic type (Cell in our example) and type-prefix types used with that stack (in both directions).  For the type-prefix type, you use the type-prefix (not the C type string) as type name (e.g., vm_Cell2i, not vm_Cell2Cell).  In addition, you have to define a vm_X2X macro for the stack basic type (used in superinstructions).

     The stack basic type for the predefined inst-stream is Cell.  If you want a stack with the same item size, making its basic type Cell usually reduces the number of macros you have to define.

     Here our examples differ a lot: vmgen-ex uses casts in these macros, whereas vmgen-ex2 uses union-field selection (or assignment to union fields).

vm_twoA2B(a1,a2,b)

vm_B2twoA(b,a1,a2)
     Conversions between two stack items (a1, a2) and a variable b of a type that takes two stack items.  This does not occur in our small examples, but you can look at Gforth for examples.

STACKPOINTER
     For each stack used, the stackpointer name given in the stack declaration is used.  For a regular stack this must be an l-expression; typically it is a variable declared as a pointer to the stack's basic type.  For inst-stream, the name is IP, and it can be a plain r-value; typically it is a macro that abstracts away the differences between the various implementations of NEXT_P*.

STACKPOINTERTOS
     The top-of-stack for the stack pointed to by STACKPOINTER.  If you are using top-of-stack caching for that stack, this should be defined as variable; if you are not using top-of-stack caching for that stack, this should be a macro expanding to STACKPOINTER[0].  The stack pointer for the predefined inst-stream is called IP, so the top-of-stack is called IPTOS.

IF_STACKPOINTERTOS(EXPR)
     Macro for executing EXPR, if top-of-stack caching is used for the STACKPOINTER stack.  I.e., this should do EXPR if there is top-of-stack caching for STACKPOINTER; otherwise it should do nothing.

VM_DEBUG
     If this is defined, the tracing code will be compiled in (slower interpretation, but better debugging).  Our example compiles two versions of the engine, a fast-running one that cannot trace, and one with potential tracing and profiling.

vm_debug
     Needed only if VM_DEBUG is defined.  If this variable contains true, the VM instructions produce trace output.  It can be turned on or off at any time.

vm_out
     Needed only if VM_DEBUG is defined.  Specifies the file on which to print the trace output (type FILE *).

printarg_TYPE(VALUE)
     Needed only if VM_DEBUG is defined.  Macro or function for printing VALUE in a way appropriate for the TYPE.  This is used for printing the values of stack items during tracing.  TYPE is normally the type prefix specified in a type-prefix definition (e.g., printarg_i); in superinstructions it is currently the basic type of the stack.

VM instruction table

For threaded code we also need to produce a table containing the labels of all VM instructions.  This is needed for VM code generation (see VM code generation), and it has to be done in the engine function, because the labels are not visible outside.  It then has to be passed outside the function (and assigned to vm_prim), to be used by the VM code generation functions.

This means that the engine function has to be called first to produce the VM instruction table, and later, after generating VM code, it has to be called again to execute the generated VM code (yes, this is ugly). In our example program, these two modes of calling the engine function are differentiated by the value of the parameter ip0 (if it equals 0, then the table is passed out, otherwise the VM code is executed); in our example, we pass the table out by assigning it to vm_prim and returning from engine.

In our example, we also build such a table for switch dispatch; this is mainly done for uniformity.

For switch dispatch, we also need to define the VM instruction opcodes used as case labels in an enum.

For both purposes (VM instruction table, and enum), the file NAME-labels.i is generated by vmgen.  You have to define the following macro used in this file:

INST_ADDR(INST_NAME)
     For switch dispatch, this is just the name of the switch label (the same name as used in LABEL(INST_NAME)), for both uses of NAME-labels.i.  For threaded-code dispatch, this is the address of the label defined in LABEL(INST_NAME)); the address is taken with && (see labels-as-values).

VM code generation
==================

Vmgen generates VM code generation functions in NAME-gen.i that the front end can call to generate VM code.  This is essential for an interpretive system.

For a VM instruction x ( #a b #c -- d ), vmgen generates a function with the prototype

     void gen_x(Inst **ctp, a_type a, c_type c)

The ctp argument points to a pointer to the next instruction. *ctp is increased by the generation functions; i.e., you should allocate memory for the code to be generated beforehand, and start with *ctp set at the start of this memory area.  Before running out of memory, allocate a new area, and generate a VM-level jump to the new area (this is not implemented in our examples).

The other arguments correspond to the immediate arguments of the VM instruction (with their appropriate types as defined in the type_prefix declaration.

The following types, variables, and functions are used in NAME-gen.i:

Inst
     The type of the VM instruction; if you use threaded code, this is void *; for switch dispatch this is an integer type.

vm_prim
     The VM instruction table (type: Inst *, see VM instruction table).

gen_inst(Inst **ctp, Inst i)
     This function compiles the instruction i.  Take a look at it in vmgen-ex/peephole.c.  It is trivial when you don't want to use superinstructions (just the last two lines of the example function), and slightly more complicated in the example due to its ability to use superinstructions (see Peephole optimization).

genarg_TYPE_PREFIX(Inst **ctp, TYPE TYPE_PREFIX)
     This compiles an immediate argument of TYPE (as defined in a type-prefix definition).  These functions are trivial to define (see vmgen-ex/support.c).  You need one of these functions for every type that you use as immediate argument.

In addition to using these functions to generate code, you should call BB_BOUNDARY at every basic block entry point if you ever want to use superinstructions (or if you want to use the profiling supported by vmgen; however, this is mainly useful for selecting superinstructions). If you use BB_BOUNDARY, you should also define it (take a look at its definition in vmgen-ex/mini.y).

You do not need to call BB_BOUNDARY after branches, because you will not define superinstructions that contain branches in the middle (and if you did, and it would work, there would be no reason to end the superinstruction at the branch), and because the branches announce themselves to the profiler.

Peephole optimization
=====================

You need peephole optimization only if you want to use superinstructions.  But having the code for it does not hurt much if you do not use superinstructions.

A simple greedy peephole optimization algorithm is used for superinstruction selection: every time gen_inst compiles a VM instruction, it looks if it can combine it with the last VM instruction (which may also be a superinstruction resulting from a previous peephole optimization); if so, it changes the last instruction to the combined instruction instead of laying down i at the current *ctp.

The code for peephole optimization is in vmgen-ex/peephole.c. You can use this file almost verbatim.  Vmgen generates FILE-peephole.i which contains data for the peephoile optimizer.

You have to call init_peeptable() after initializing vm_prim, and before compiling any VM code to initialize data structures for peephole optimization.  After that, compiling with the VM code generation functions will automatically combine VM instructions into superinstructions.  Since you do not want to combine instructions across VM branch targets (otherwise there will not be a proper VM instruction to branch to), you have to call BB_BOUNDARY (see VM code generation) at branch targets.

VM disassembler
===============

A VM code disassembler is optional for an interpretive system, but highly recommended during its development and maintenance, because it is very useful for detecting bugs in the front end (and for distinguishing them from VM interpreter bugs).

Vmgen supports VM code disassembling by generating FILE-disasm.i.  This code has to be wrapped into a function, as is done in vmgen-ex/disasm.i.  You can use this file almost verbatim.  In addition to vm_A2B(a,b), vm_out, printarg_TYPE(VALUE), which are explained above, the following macros and variables are used in FILE-disasm.i (and you have to define them):

ip
     This variable points to the opcode of the current VM instruction.

IP IPTOS
     IPTOS is the first argument of the current VM instruction, and IP points to it; this is just as in the engine, but here ip points to the opcode of the VM instruction (in contrast to the engine, where ip points to the next cell, or even one further).

VM_IS_INST(Inst i, int n)
     Tests if the opcode i is the same as the nth entry in the VM instruction table.

Invocation

Input Syntax

Concepts: Front end, VM, Stacks,  Types, input stream

Contact

Required changes: vm_...2... -> two arguments "vm_two...2...(arg1,arg2,arg3);" -> "vm_two...2...(arg3,arg1,arg2)" (no ";"). define INST_ADDR and LABEL define VM_IS_INST also for disassembler