     [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 reasons.  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).

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

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

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

The 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 no-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 variable 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.

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 # to 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).

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

Stacks, types, and prefixes
===========================

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