File:  [gforth] / gforth / doc / vmgen.texi
Revision 1.7: download - view: text, annotated - select for diffs
Thu Aug 8 08:33:06 2002 UTC (18 years, 3 months ago) by anton
Branches: MAIN
CVS tags: HEAD
more documentation

    1: @include version.texi
    3: @c @ifnottex
    4: This file documents vmgen (Gforth @value{VERSION}).
    6: @chapter Introduction
    8: Vmgen is a tool for writing efficient interpreters.  It takes a simple
    9: virtual machine description and generates efficient C code for dealing
   10: with the virtual machine code in various ways (in particular, executing
   11: it).  The run-time efficiency of the resulting interpreters is usually
   12: within a factor of 10 of machine code produced by an optimizing
   13: compiler.
   15: The interpreter design strategy supported by vmgen is to divide the
   16: interpreter into two parts:
   18: @itemize @bullet
   20: @item The @emph{front end} takes the source code of the language to be
   21: implemented, and translates it into virtual machine code.  This is
   22: similar to an ordinary compiler front end; typically an interpreter
   23: front-end performs no optimization, so it is relatively simple to
   24: implement and runs fast.
   26: @item The @emph{virtual machine interpreter} executes the virtual
   27: machine code.
   29: @end itemize
   31: Such a division is usually used in interpreters, for modularity as well
   32: as for efficiency.  The virtual machine code is typically passed between
   33: front end and virtual machine interpreter in memory, like in a
   34: load-and-go compiler; this avoids the complexity and time cost of
   35: writing the code to a file and reading it again.
   37: A @emph{virtual machine} (VM) represents the program as a sequence of
   38: @emph{VM instructions}, following each other in memory, similar to real
   39: machine code.  Control flow occurs through VM branch instructions, like
   40: in a real machine.
   42: In this setup, vmgen can generate most of the code dealing with virtual
   43: machine instructions from a simple description of the virtual machine
   44: instructions (@pxref...), in particular:
   46: @table @emph
   48: @item VM instruction execution
   50: @item VM code generation
   51: Useful in the front end.
   53: @item VM code decompiler
   54: Useful for debugging the front end.
   56: @item VM code tracing
   57: Useful for debugging the front end and the VM interpreter.  You will
   58: typically provide other means for debugging the user's programs at the
   59: source level.
   61: @item VM code profiling
   62: Useful for optimizing the VM insterpreter with superinstructions
   63: (@pxref...).
   65: @end table
   67: VMgen supports efficient interpreters though various optimizations, in
   68: particular
   70: @itemize
   72: @item Threaded code
   74: @item Caching the top-of-stack in a register
   76: @item Combining VM instructions into superinstructions
   78: @item
   79: Replicating VM (super)instructions for better BTB prediction accuracy
   80: (not yet in vmgen-ex, but already in Gforth).
   82: @end itemize
   84: As a result, vmgen-based interpreters are only about an order of
   85: magintude slower than native code from an optimizing C compiler on small
   86: benchmarks; on large benchmarks, which spend more time in the run-time
   87: system, the slowdown is often less (e.g., the slowdown of a
   88: Vmgen-generated JVM interpreter over the best JVM JIT compiler we
   89: measured is only a factor of 2-3 for large benchmarks; some other JITs
   90: and all other interpreters we looked at were slower than our
   91: interpreter).
   93: VMs are usually designed as stack machines (passing data between VM
   94: instructions on a stack), and vmgen supports such designs especially
   95: well; however, you can also use vmgen for implementing a register VM and
   96: still benefit from most of the advantages offered by vmgen.
   98: There are many potential uses of the instruction descriptions that are
   99: not implemented at the moment, but we are open for feature requests, and
  100: we will implement new features if someone asks for them; so the feature
  101: list above is not exhaustive.
  103: @c *********************************************************************
  104: @chapter Why interpreters?
  106: Interpreters are a popular language implementation technique because
  107: they combine all three of the following advantages:
  109: @itemize
  111: @item Ease of implementation
  113: @item Portability
  115: @item Fast edit-compile-run cycle
  117: @end itemize
  119: The main disadvantage of interpreters is their run-time speed.  However,
  120: there are huge differences between different interpreters in this area:
  121: the slowdown over optimized C code on programs consisting of simple
  122: operations is typically a factor of 10 for the more efficient
  123: interpreters, and a factor of 1000 for the less efficient ones (the
  124: slowdown for programs executing complex operations is less, because the
  125: time spent in libraries for executing complex operations is the same in
  126: all implementation strategies).
  128: Vmgen makes it even easier to implement interpreters.  It also supports
  129: techniques for building efficient interpreters.
  131: @c ********************************************************************
  132: @chapter Concepts
  134: @c --------------------------------------------------------------------
  135: @section Front-end and virtual machine interpreter
  137: @cindex front-end
  138: Interpretive systems are typically divided into a @emph{front end} that
  139: parses the input language and produces an intermediate representation
  140: for the program, and an interpreter that executes the intermediate
  141: representation of the program.
  143: @cindex virtual machine
  144: @cindex VM
  145: @cindex instruction, VM
  146: For efficient interpreters the intermediate representation of choice is
  147: virtual machine code (rather than, e.g., an abstract syntax tree).
  148: @emph{Virtual machine} (VM) code consists of VM instructions arranged
  149: sequentially in memory; they are executed in sequence by the VM
  150: interpreter, except for VM branch instructions, which implement control
  151: structures.  The conceptual similarity to real machine code results in
  152: the name @emph{virtual machine}.
  154: In this framework, vmgen supports building the VM interpreter and any
  155: other component dealing with VM instructions.  It does not have any
  156: support for the front end, apart from VM code generation support.  The
  157: front end can be implemented with classical compiler front-end
  158: techniques, supported by tools like @command{flex} and @command{bison}.
  160: The intermediate representation is usually just internal to the
  161: interpreter, but some systems also support saving it to a file, either
  162: as an image file, or in a full-blown linkable file format (e.g., JVM).
  163: Vmgen currently has no special support for such features, but the
  164: information in the instruction descriptions can be helpful, and we are
  165: open for feature requests and suggestions.
  167: @section Data handling
  169: @cindex stack machine
  170: @cindex register machine
  171: Most VMs use one or more stacks for passing temporary data between VM
  172: instructions.  Another option is to use a register machine architecture
  173: for the virtual machine; however, this option is either slower or
  174: significantly more complex to implement than a stack machine architecture.
  176: Vmgen has special support and optimizations for stack VMs, making their
  177: implementation easy and efficient.
  179: You can also implement a register VM with vmgen (@pxref{Register
  180: Machines}), and you will still profit from most vmgen features.
  182: @cindex stack item size
  183: @cindex size, stack items
  184: Stack items all have the same size, so they typically will be as wide as
  185: an integer, pointer, or floating-point value.  Vmgen supports treating
  186: two consecutive stack items as a single value, but anything larger is
  187: best kept in some other memory area (e.g., the heap), with pointers to
  188: the data on the stack.
  190: @cindex instruction stream
  191: @cindex immediate arguments
  192: Another source of data is immediate arguments VM instructions (in the VM
  193: instruction stream).  The VM instruction stream is handled similar to a
  194: stack in vmgen.
  196: @cindex garbage collection
  197: @cindex reference counting
  198: Vmgen has no built-in support for nor restrictions against @emph{garbage
  199: collection}.  If you need garbage collection, you need to provide it in
  200: your run-time libraries.  Using @emph{reference counting} is probably
  201: harder, but might be possible (contact us if you are interested).
  202: @c reference counting might be possible by including counting code in 
  203: @c the conversion macros.
  205: @section Dispatch
  207: Understanding this section is probably not necessary for using vmgen,
  208: but it may help.  You may want to skip it now, and read it if you find statements about dispatch methods confusing.
  210: After executing one VM instruction, the VM interpreter has to dispatch
  211: the next VM instruction (vmgen calls the dispatch routine @samp{NEXT}).
  212: Vmgen supports two methods of dispatch:
  214: @table
  216: @item switch dispatch
  217: In this method the VM interpreter contains a giant @code{switch}
  218: statement, with one @code{case} for each VM instruction.  The VM
  219: instructions are represented by integers (e.g., produced by an
  220: @code{enum}) in the VM code, and dipatch occurs by loading the next
  221: integer from the VM code, @code{switch}ing on it, and continuing at the
  222: appropriate @code{case}; after executing the VM instruction, jump back
  223: to the dispatch code.
  225: @item threaded code
  226: This method represents a VM instruction in the VM code by the address of
  227: the start of the machine code fragment for executing the VM instruction.
  228: Dispatch consists of loading this address, jumping to it, and
  229: incrementing the VM instruction pointer.  Typically the threaded-code
  230: dispatch code is appended directly to the code for executing the VM
  231: instruction.  Threaded code cannot be implemented in ANSI C, but it can
  232: be implemented using GNU C's labels-as-values extension (@pxref{labels
  233: as values}).
  235: @end table
  237: @c *************************************************************
  238: @chapter Invoking vmgen
  240: The usual way to invoke vmgen is as follows:
  242: @example
  243: vmgen @var{infile}
  244: @end example
  246: Here @var{infile} is the VM instruction description file, which usually
  247: ends in @file{.vmg}.  The output filenames are made by taking the
  248: basename of @file{infile} (i.e., the output files will be created in the
  249: current working directory) and replacing @file{.vmg} with @file{-vm.i},
  250: @file{-disasm.i}, @file{-gen.i}, @file{-labels.i}, @file{-profile.i},
  251: and @file{-peephole.i}.  E.g., @command{bison hack/foo.vmg} will create
  252: @file{foo-vm.i} etc.
  254: The command-line options supported by vmgen are
  256: @table @option
  258: @cindex -h, command-line option
  259: @cindex --help, command-line option
  260: @item --help
  261: @itemx -h
  262: Print a message about the command-line options
  264: @cindex -v, command-line option
  265: @cindex --version, command-line option
  266: @item --version
  267: @itemx -v
  268: Print version and exit
  269: @end table
  273: @c ****************************************************************
  274: @chapter Example
  276: @section Example overview
  278: There are two versions of the same example for using vmgen:
  279: @file{vmgen-ex} and @file{vmgen-ex2} (you can also see Gforth as
  280: example, but it uses additional (undocumented) features, and also
  281: differs in some other respects).  The example implements @emph{mini}, a
  282: tiny Modula-2-like language with a small JavaVM-like virtual machine.
  283: The difference between the examples is that @file{vmgen-ex} uses many
  284: casts, and @file{vmgen-ex2} tries to avoids most casts and uses unions
  285: instead.
  287: The files provided with each example are:
  289: @example
  290: Makefile
  291: README
  292: disasm.c           wrapper file
  293: engine.c           wrapper file
  294: peephole.c         wrapper file
  295: profile.c          wrapper file
  296: mini-inst.vmg      simple VM instructions
  297: mini-super.vmg     superinstructions (empty at first)
  298: mini.h             common declarations
  299: mini.l             scanner
  300: mini.y             front end (parser, VM code generator)
  301: support.c          main() and other support functions
  302:           example mini program
  303:        example mini program
  304:          example mini program (tests everything)
  305: test.out  output
  306: stat.awk           script for aggregating profile information
  307: peephole-blacklist list of instructions not allowed in superinstructions
  308: seq2rule.awk       script for creating superinstructions
  309: @end example
  311: For your own interpreter, you would typically copy the following files
  312: and change little, if anything:
  314: @example
  315: disasm.c           wrapper file
  316: engine.c           wrapper file
  317: peephole.c         wrapper file
  318: profile.c          wrapper file
  319: stat.awk           script for aggregating profile information
  320: seq2rule.awk       script for creating superinstructions
  321: @end example
  323: You would typically change much in or replace the following files:
  325: @example
  326: Makefile
  327: mini-inst.vmg      simple VM instructions
  328: mini.h             common declarations
  329: mini.l             scanner
  330: mini.y             front end (parser, VM code generator)
  331: support.c          main() and other support functions
  332: peephole-blacklist list of instructions not allowed in superinstructions
  333: @end example
  335: You can build the example by @code{cd}ing into the example's directory,
  336: and then typing @samp{make}; you can check that it works with @samp{make
  337: check}.  You can run run mini programs like this:
  339: @example
  340: ./mini
  341: @end example
  343: To learn about the options, type @samp{./mini -h}.
  345: @section Using profiling to create superinstructions
  347: I have not added rules for this in the @file{Makefile} (there are many
  348: options for selecting superinstructions, and I did not want to hardcode
  349: one into the @file{Makefile}), but there are some supporting scripts, and
  350: here's an example:
  352: Suppose you want to use @file{} and @file{} as training
  353: programs, you get the profiles like this:
  355: @example
  356: make #takes a few seconds
  357: @end example
  359: You can aggregate these profiles with @file{stat.awk}:
  361: @example
  362: awk -f stat.awk
  363: @end example
  365: The result contains lines like:
  367: @example
  368:       2      16        36910041 loadlocal lit
  369: @end example
  371: This means that the sequence @code{loadlocal lit} statically occurs a
  372: total of 16 times in 2 profiles, with a dynamic execution count of
  373: 36910041.
  375: The numbers can be used in various ways to select superinstructions.
  376: E.g., if you just want to select all sequences with a dynamic
  377: execution count exceeding 10000, you would use the following pipeline:
  379: @example
  380: awk -f stat.awk|
  381: awk '$3>=10000'|                #select sequences
  382: fgrep -v -f peephole-blacklist| #eliminate wrong instructions
  383: awk -f seq2rule.awk|      #transform sequences into superinstruction rules
  384: sort -k 3 >mini-super.vmg       #sort sequences
  385: @end example
  387: The file @file{peephole-blacklist} contains all instructions that
  388: directly access a stack or stack pointer (for mini: @code{call},
  389: @code{return}); the sort step is necessary to ensure that prefixes
  390: preceed larger superinstructions.
  392: Now you can create a version of mini with superinstructions by just
  393: saying @samp{make}
  395: @c ***************************************************************
  396: @chapter Input File Format
  398: Vmgen takes as input a file containing specifications of virtual machine
  399: instructions.  This file usually has a name ending in @file{.vmg}.
  401: Most examples are taken from the example in @file{vmgen-ex}.
  403: @section Input File Grammar
  405: The grammar is in EBNF format, with @code{@var{a}|@var{b}} meaning
  406: ``@var{a} or @var{b}'', @code{@{@var{c}@}} meaning 0 or more repetitions
  407: of @var{c} and @code{[@var{d}]} meaning 0 or 1 repetitions of @var{d}.
  409: Vmgen input is not free-format, so you have to take care where you put
  410: spaces and especially newlines; it's not as bad as makefiles, though:
  411: any sequence of spaces and tabs is equivalent to a single space.
  413: @example
  414: description: {instruction|comment|eval-escape}
  416: instruction: simple-inst|superinst
  418: simple-inst: ident " (" stack-effect " )" newline c-code newline newline
  420: stack-effect: {ident} " --" {ident}
  422: super-inst: ident " =" ident {ident}  
  424: comment:      "\ "  text newline
  426: eval-escape:  "\e " text newline
  427: @end example
  428: @c \+ \- \g \f \c
  430: Note that the @code{\}s in this grammar are meant literally, not as
  431: C-style encodings for non-printable characters.
  433: The C code in @code{simple-inst} must not contain empty lines (because
  434: vmgen would mistake that as the end of the simple-inst.  The text in
  435: @code{comment} and @code{eval-escape} must not contain a newline.
  436: @code{Ident} must conform to the usual conventions of C identifiers
  437: (otherwise the C compiler would choke on the vmgen output).
  439: Vmgen understands a few extensions beyond the grammar given here, but
  440: these extensions are only useful for building Gforth.  You can find a
  441: description of the format used for Gforth in @file{prim}.
  443: @subsection
  444: @c woanders?
  445: The text in @code{eval-escape} is Forth code that is evaluated when
  446: vmgen reads the line.  If you do not know (and do not want to learn)
  447: Forth, you can build the text according to the following grammar; these
  448: rules are normally all Forth you need for using vmgen:
  450: @example
  451: text: stack-decl|type-prefix-decl|stack-prefix-decl
  453: stack-decl: "stack " ident ident ident
  454: type-prefix-decl: 
  455:     's" ' string '" ' ("single"|"double") ident "type-prefix" ident
  456: stack-prefix-decl:  ident "stack-prefix" string
  457: @end example
  459: Note that the syntax of this code is not checked thoroughly (there are
  460: many other Forth program fragments that could be written there).
  462: If you know Forth, the stack effects of the non-standard words involved
  463: are:
  465: @example
  466: stack        ( "name" "pointer" "type" -- )
  467:              ( name execution: -- stack )
  468: type-prefix  ( addr u xt1 xt2 n stack "prefix" -- )
  469: single       ( -- xt1 xt2 n )
  470: double       ( -- xt1 xt2 n )
  471: stack-prefix ( stack "prefix" -- )
  472: @end example
  475: @section Simple instructions
  477: We will use the following simple VM instruction description as example:
  479: @example
  480: sub ( i1 i2 -- i )
  481: i = i1-i2;
  482: @end example
  484: The first line specifies the name of the VM instruction (@code{sub}) and
  485: its stack effect (@code{i1 i2 -- i}).  The rest of the description is
  486: just plain C code.
  488: @cindex stack effect
  489: The stack effect specifies that @code{sub} pulls two integers from the
  490: data stack and puts them in the C variables @code{i1} and @code{i2} (with
  491: the rightmost item (@code{i2}) taken from the top of stack) and later
  492: pushes one integer (@code{i)) on the data stack (the rightmost item is
  493: on the top afterwards).
  495: How do we know the type and stack of the stack items?  Vmgen uses
  496: prefixes, similar to Fortran; in contrast to Fortran, you have to
  497: define the prefix first:
  499: @example
  500: \E s" Cell"   single data-stack type-prefix i
  501: @end example
  503: This defines the prefix @code{i} to refer to the type @code{Cell}
  504: (defined as @code{long} in @file{mini.h}) and, by default, to the
  505: @code{data-stack}.  It also specifies that this type takes one stack
  506: item (@code{single}).  The type prefix is part of the variable name.
  508: Before we can use @code{data-stack} in this way, we have to define it:
  510: @example
  511: \E stack data-stack sp Cell
  512: @end example
  513: @c !! use something other than Cell
  515: This line defines the stack @code{data-stack}, which uses the stack
  516: pointer @code{sp}, and each item has the basic type @code{Cell}; other
  517: types have to fit into one or two @code{Cell}s (depending on whether the
  518: type is @code{single} or @code{double} wide), and are converted from and
  519: to Cells on accessing the @code{data-stack) with conversion macros
  520: (@pxref{Conversion macros}).  Stacks grow towards lower addresses in
  521: vmgen-erated interpreters.
  523: We can override the default stack of a stack item by using a stack
  524: prefix.  E.g., consider the following instruction:
  526: @example
  527: lit ( #i -- i )
  528: @end example
  530: The VM instruction @code{lit} takes the item @code{i} from the
  531: instruction stream (indicated by the prefix @code{#}), and pushes it on
  532: the (default) data stack.  The stack prefix is not part of the variable
  533: name.  Stack prefixes are defined like this:
  535: @example
  536: \E inst-stream stack-prefix #
  537: @end example
  539: This definition defines that the stack prefix @code{#} specifies the
  540: ``stack'' @code{inst-stream}.  Since the instruction stream behaves a
  541: little differently than an ordinary stack, it is predefined, and you do
  542: not need to define it.
  544: The instruction stream contains instructions and their immediate
  545: arguments, so specifying that an argument comes from the instruction
  546: stream indicates an immediate argument.  Of course, instruction stream
  547: arguments can only appear to the left of @code{--} in the stack effect.
  548: If there are multiple instruction stream arguments, the leftmost is the
  549: first one (just as the intuition suggests).
  551: @subsubsection C Code Macros
  553: Vmgen recognizes the following strings in the C code part of simple
  554: instructions:
  556: @table @samp
  558: @item SET_IP
  559: As far as vmgen is concerned, a VM instruction containing this ends a VM
  560: basic block (used in profiling to delimit profiled sequences).  On the C
  561: level, this also sets the instruction pointer.
  563: @item SUPER_END
  564: This ends a basic block (for profiling), without a SET_IP.
  566: @item TAIL;
  567: Vmgen replaces @samp{TAIL;} with code for ending a VM instruction and
  568: dispatching the next VM instruction.  This happens automatically when
  569: control reaches the end of the C code.  If you want to have this in the
  570: middle of the C code, you need to use @samp{TAIL;}.  A typical example
  571: is a conditional VM branch:
  573: @example
  574: if (branch_condition) {
  575:   SET_IP(target); TAIL;
  576: }
  577: /* implicit tail follows here */
  578: @end example
  580: In this example, @samp{TAIL;} is not strictly necessary, because there
  581: is another one implicitly after the if-statement, but using it improves
  582: branch prediction accuracy slightly and allows other optimizations.
  584: @item SUPER_CONTINUE
  585: This indicates that the implicit tail at the end of the VM instruction
  586: dispatches the sequentially next VM instruction even if there is a
  587: @code{SET_IP} in the VM instruction.  This enables an optimization that
  588: is not yet implemented in the vmgen-ex code (but in Gforth).  The
  589: typical application is in conditional VM branches:
  591: @example
  592: if (branch_condition) {
  593:   SET_IP(target); TAIL; /* now this TAIL is necessary */
  594: }
  596: @end example
  598: @end table
  600: Note that vmgen is not smart about C-level tokenization, comments,
  601: strings, or conditional compilation, so it will interpret even a
  602: commented-out SUPER_END as ending a basic block (or, e.g.,
  603: @samp{RETAIL;} as @samp{TAIL;}).  Conversely, vmgen requires the literal
  604: presence of these strings; vmgen will not see them if they are hiding in
  605: a C preprocessor macro.
  608: @subsubsection C Code restrictions
  610: Vmgen generates code and performs some optimizations under the
  611: assumption that the user-supplied C code does not access the stack
  612: pointers or stack items, and that accesses to the instruction pointer
  613: only occur through special macros.  In general you should heed these
  614: restrictions.  However, if you need to break these restrictions, read
  615: the following.
  617: Accessing a stack or stack pointer directly can be a problem for several
  618: reasons: 
  620: @itemize
  622: @item
  623: You may cache the top-of-stack item in a local variable (that is
  624: allocated to a register).  This is the most frequent source of trouble.
  625: You can deal with it either by not using top-of-stack caching (slowdown
  626: factor 1-1.4, depending on machine), or by inserting flushing code
  627: (e.g., @samp{IF_spTOS(sp[...] = spTOS);}) at the start and reloading
  628: code (e.g., @samp{IF_spTOS(spTOS = sp[0])}) at the end of problematic C
  629: code.  Vmgen inserts a stack pointer update before the start of the
  630: user-supplied C code, so the flushing code has to use an index that
  631: corrects for that.  In the future, this flushing may be done
  632: automatically by mentioning a special string in the C code.
  633: @c sometimes flushing and/or reloading unnecessary
  635: @item
  636: The vmgen-erated code loads the stack items from stack-pointer-indexed
  637: memory into variables before the user-supplied C code, and stores them
  638: from variables to stack-pointer-indexed memory afterwards.  If you do
  639: any writes to the stack through its stack pointer in your C code, it
  640: will not affact the variables, and your write may be overwritten by the
  641: stores after the C code.  Similarly, a read from a stack using a stack
  642: pointer will not reflect computations of stack items in the same VM
  643: instruction.
  645: @item
  646: Superinstructions keep stack items in variables across the whole
  647: superinstruction.  So you should not include VM instructions, that
  648: access a stack or stack pointer, as components of superinstructions.
  650: @end itemize
  652: You should access the instruction pointer only through its special
  653: macros (@samp{IP}, @samp{SET_IP}, @samp{IPTOS}); this ensure that these
  654: macros can be implemented in several ways for best performance.
  655: @samp{IP} points to the next instruction, and @samp{IPTOS} is its
  656: contents.
  659: @section Superinstructions
  661: Here is an example of a superinstruction definition:
  663: @example
  664: lit_sub = lit sub
  665: @end example
  667: @code{lit_sub} is the name of the superinstruction, and @code{lit} and
  668: @code{sub} are its components.  This superinstruction performs the same
  669: action as the sequence @code{lit} and @code{sub}.  It is generated
  670: automatically by the VM code generation functions whenever that sequence
  671: occurs, so you only need to add this definition if you want to use this
  672: superinstruction (and even that can be partially automatized,
  673: @pxref{...}).
  675: Vmgen requires that the component instructions are simple instructions
  676: defined before superinstructions using the components.  Currently, vmgen
  677: also requires that all the subsequences at the start of a
  678: superinstruction (prefixes) must be defined as superinstruction before
  679: the superinstruction.  I.e., if you want to define a superinstruction
  681: @example
  682: sumof5 = add add add add
  683: @end example
  685: you first have to define
  687: @example
  688: add ( n1 n2 -- n )
  689: n = n1+n2;
  691: sumof3 = add add
  692: sumof4 = add add add
  693: @end example
  695: Here, @code{sumof4} is the longest prefix of @code{sumof5}, and @code{sumof3}
  696: is the longest prefix of @code{sumof4}.
  698: Note that vmgen assumes that only the code it generates accesses stack
  699: pointers, the instruction pointer, and various stack items, and it
  700: performs optimizations based on this assumption.  Therefore, VM
  701: instructions that change the instruction pointer should only be used as
  702: last component; a VM instruction that accesses a stack pointer should
  703: not be used as component at all.  Vmgen does not check these
  704: restrictions, they just result in bugs in your interpreter.
  706: @c ********************************************************************
  707: @chapter Using the generated code
  709: The easiest way to create a working VM interpreter with vmgen is
  710: probably to start with one of the examples, and modify it for your
  711: purposes.  This chapter is just the reference manual for the macros
  712: etc. used by the generated code, and the other context expected by the
  713: generated code, and what you can do with the various generated files.
  716: @section VM engine
  718: The VM engine is the VM interpreter that executes the VM code.  It is
  719: essential for an interpretive system.
  721: Vmgen supports two methods of VM instruction dispatch: @emph{threaded
  722: code} (fast, but gcc-specific), and @emph{switch dispatch} (slow, but
  723: portable across C compilers); you can use conditional compilation
  724: (@samp{defined(__GNUC__)}) to choose between these methods, and our
  725: example does so.
  727: For both methods, the VM engine is contained in a C-level function.
  728: Vmgen generates most of the contents of the function for you
  729: (@file{@var{name}-vm.i}), but you have to define this function, and
  730: macros and variables used in the engine, and initialize the variables.
  731: In our example the engine function also includes
  732: @file{@var{name}-labels.i} (@pxref{VM instruction table}).
  734: The following macros and variables are used in @file{@var{name}-vm.i}:
  736: @table @code
  738: @item LABEL(@var{inst_name})
  739: This is used just before each VM instruction to provide a jump or
  740: @code{switch} label (the @samp{:} is provided by vmgen).  For switch
  741: dispatch this should expand to @samp{case @var{label}}; for
  742: threaded-code dispatch this should just expand to @samp{case
  743: @var{label}}.  In either case @var{label} is usually the @var{inst_name}
  744: with some prefix or suffix to avoid naming conflicts.
  746: @item NAME(@var{inst_name_string})
  747: Called on entering a VM instruction with a string containing the name of
  748: the VM instruction as parameter.  In normal execution this should be a
  749: noop, but for tracing this usually prints the name, and possibly other
  750: information (several VM registers in our example).
  752: @item DEF_CA
  753: Usually empty.  Called just inside a new scope at the start of a VM
  754: instruction.  Can be used to define variables that should be visible
  755: during every VM instruction.  If you define this macro as non-empty, you
  756: have to provide the finishing @samp{;} in the macro.
  758: @item NEXT_P0 NEXT_P1 NEXT_P2
  759: The three parts of instruction dispatch.  They can be defined in
  760: different ways for best performance on various processors (see
  761: @file{engine.c} in the example or @file{engine/threaded.h} in Gforth).
  762: @samp{NEXT_P0} is invoked right at the start of the VM isntruction (but
  763: after @samp{DEF_CA}), @samp{NEXT_P1} right after the user-supplied C
  764: code, and @samp{NEXT_P2} at the end.  The actual jump has to be
  765: performed by @samp{NEXT_P2}.
  767: The simplest variant is if @samp{NEXT_P2} does everything and the other
  768: macros do nothing.  Then also related macros like @samp{IP},
  769: @samp{SET_IP}, @samp{IP}, @samp{INC_IP} and @samp{IPTOS} are very
  770: straightforward to define.  For switch dispatch this code consists just
  771: of a jump to the dispatch code (@samp{goto next_inst;} in our example;
  772: for direct threaded code it consists of something like
  773: @samp{({cfa=*ip++; goto *cfa;})}.
  775: Pulling code (usually the @samp{cfa=*ip;}) up into @samp{NEXT_P1}
  776: usually does not cause problems, but pulling things up into
  777: @samp{NEXT_P0} usually requires changing the other macros (and, at least
  778: for Gforth on Alpha, it does not buy much, because the compiler often
  779: manages to schedule the relevant stuff up by itself).  An even more
  780: extreme variant is to pull code up even further, into, e.g., NEXT_P1 of
  781: the previous VM instruction (prefetching, useful on PowerPCs).
  783: @item INC_IP(@var{n})
  784: This increments IP by @var{n}.
  786: @item vm_@var{A}2@var{B}(a,b)
  787: Type casting macro that assigns @samp{a} (of type @var{A}) to @samp{b}
  788: (of type @var{B}).  This is mainly used for getting stack items into
  789: variables and back.  So you need to define macros for every combination
  790: of stack basic type (@code{Cell} in our example) and type-prefix types
  791: used with that stack (in both directions).  For the type-prefix type,
  792: you use the type-prefix (not the C type string) as type name (e.g.,
  793: @samp{vm_Cell2i}, not @samp{vm_Cell2Cell}).  In addition, you have to
  794: define a vm_@var{X}2@var{X} macro for the stack basic type (used in
  795: superinstructions).
  797: The stack basic type for the predefined @samp{inst-stream} is
  798: @samp{Cell}.  If you want a stack with the same item size, making its
  799: basic type @samp{Cell} usually reduces the number of macros you have to
  800: define.
  802: Here our examples differ a lot: @file{vmgen-ex} uses casts in these
  803: macros, whereas @file{vmgen-ex2} uses union-field selection (or
  804: assignment to union fields).
  806: @item vm_two@var{A}2@var{B}(a1,a2,b)
  807: @item vm_@var{B}2two@var{A}(b,a1,a2)
  808: Conversions between two stack items (@code{a1}, @code{a2}) and a
  809: variable @code{b} of a type that takes two stack items.  This does not
  810: occur in our small examples, but you can look at Gforth for examples.
  812: @item @var{stackpointer}
  813: For each stack used, the stackpointer name given in the stack
  814: declaration is used.  For a regular stack this must be an l-expression;
  815: typically it is a variable declared as a pointer to the stack's basic
  816: type.  For @samp{inst-stream}, the name is @samp{IP}, and it can be a
  817: plain r-value; typically it is a macro that abstracts away the
  818: differences between the various implementations of NEXT_P*.
  820: @item @var{stackpointer}TOS
  821: The top-of-stack for the stack pointed to by @var{stackpointer}.  If you
  822: are using top-of-stack caching for that stack, this should be defined as
  823: variable; if you are not using top-of-stack caching for that stack, this
  824: should be a macro expanding to @samp{@var{stackpointer}[0]}.  The stack
  825: pointer for the predefined @samp{inst-stream} is called @samp{IP}, so
  826: the top-of-stack is called @samp{IPTOS}.
  828: @item IF_@var{stackpointer}TOS(@var{expr})
  829: Macro for executing @var{expr}, if top-of-stack caching is used for the
  830: @var{stackpointer} stack.  I.e., this should do @var{expr} if there is
  831: top-of-stack caching for @var{stackpointer}; otherwise it should do
  832: nothing.
  834: @item VM_DEBUG
  835: If this is defined, the tracing code will be compiled in (slower
  836: interpretation, but better debugging).  Our example compiles two
  837: versions of the engine, a fast-running one that cannot trace, and one
  838: with potential tracing and profiling.
  840: @item vm_debug
  841: Needed only if @samp{VM_DEBUG} is defined.  If this variable contains
  842: true, the VM instructions produce trace output.  It can be turned on or
  843: off at any time.
  845: @item vm_out
  846: Needed only if @samp{VM_DEBUG} is defined.  Specifies the file on which
  847: to print the trace output (type @samp{FILE *}).
  849: @item printarg_@var{type}(@var{value})
  850: Needed only if @samp{VM_DEBUG} is defined.  Macro or function for
  851: printing @var{value} in a way appropriate for the @var{type}.  This is
  852: used for printing the values of stack items during tracing.  @var{Type}
  853: is normally the type prefix specified in a @code{type-prefix} definition
  854: (e.g., @samp{printarg_i}); in superinstructions it is currently the
  855: basic type of the stack.
  857: @end table
  860: @section{VM instruction table}
  862: For threaded code we also need to produce a table containing the labels
  863: of all VM instructions.  This is needed for VM code generation
  864: (@pxref{VM code generation}), and it has to be done in the engine
  865: function, because the labels are not visible outside.  It then has to be
  866: passed outside the function (and assigned to @samp{vm_prim}), to be used
  867: by the VM code generation functions.
  869: This means that the engine function has to be called first to produce
  870: the VM instruction table, and later, after generating VM code, it has to
  871: be called again to execute the generated VM code (yes, this is ugly).
  872: In our example program, these two modes of calling the engine function
  873: are differentiated by the value of the parameter ip0 (if it equals 0,
  874: then the table is passed out, otherwise the VM code is executed); in our
  875: example, we pass the table out by assigning it to @samp{vm_prim} and
  876: returning from @samp{engine}.
  878: In our example, we also build such a table for switch dispatch; this is
  879: mainly done for uniformity.
  881: For switch dispatch, we also need to define the VM instruction opcodes
  882: used as case labels in an @code{enum}.
  884: For both purposes (VM instruction table, and enum), the file
  885: @file{@var{name}-labels.i} is generated by vmgen.  You have to define
  886: the following macro used in this file:
  888: @table @samp
  890: @item INST_ADDR(@var{inst_name})
  891: For switch dispatch, this is just the name of the switch label (the same
  892: name as used in @samp{LABEL(@var{inst_name})}), for both uses of
  893: @file{@var{name}-labels.i}.  For threaded-code dispatch, this is the
  894: address of the label defined in @samp{LABEL(@var{inst_name})}); the
  895: address is taken with @samp{&&} (@pxref{labels-as-values}).
  897: @end table
  900: @section VM code generation
  902: Vmgen generates VM code generation functions in @file{@var{name}-gen.i}
  903: that the front end can call to generate VM code.  This is essential for
  904: an interpretive system.
  906: For a VM instruction @samp{x ( #a b #c -- d )}, vmgen generates a
  907: function with the prototype
  909: @example
  910: void gen_x(Inst **ctp, a_type a, c_type c)
  911: @end example
  913: The @code{ctp} argument points to a pointer to the next instruction.
  914: @code{*ctp} is increased by the generation functions; i.e., you should
  915: allocate memory for the code to be generated beforehand, and start with
  916: *ctp set at the start of this memory area.  Before running out of
  917: memory, allocate a new area, and generate a VM-level jump to the new
  918: area (this is not implemented in our examples).
  920: The other arguments correspond to the immediate arguments of the VM
  921: instruction (with their appropriate types as defined in the
  922: @code{type_prefix} declaration.
  924: The following types, variables, and functions are used in
  925: @file{@var{name}-gen.i}:
  927: @table @samp
  929: @item Inst
  930: The type of the VM instruction; if you use threaded code, this is
  931: @code{void *}; for switch dispatch this is an integer type.
  933: @item vm_prim
  934: The VM instruction table (type: @code{Inst *}, @pxref{VM instruction table}).
  936: @item gen_inst(Inst **ctp, Inst i)
  937: This function compiles the instruction @code{i}.  Take a look at it in
  938: @file{vmgen-ex/peephole.c}.  It is trivial when you don't want to use
  939: superinstructions (just the last two lines of the example function), and
  940: slightly more complicated in the example due to its ability to use
  941: superinstructions (@pxref{Peephole optimization}).
  943: @item genarg_@var{type_prefix}(Inst **ctp, @var{type} @var{type_prefix})
  944: This compiles an immediate argument of @var{type} (as defined in a
  945: @code{type-prefix} definition).  These functions are trivial to define
  946: (see @file{vmgen-ex/support.c}).  You need one of these functions for
  947: every type that you use as immediate argument.
  949: @end table
  951: In addition to using these functions to generate code, you should call
  952: @code{BB_BOUNDARY} at every basic block entry point if you ever want to
  953: use superinstructions (or if you want to use the profiling supported by
  954: vmgen; however, this is mainly useful for selecting superinstructions).
  955: If you use @code{BB_BOUNDARY}, you should also define it (take a look at
  956: its definition in @file{vmgen-ex/mini.y}).
  958: You do not need to call @code{BB_BOUNDARY} after branches, because you
  959: will not define superinstructions that contain branches in the middle
  960: (and if you did, and it would work, there would be no reason to end the
  961: superinstruction at the branch), and because the branches announce
  962: themselves to the profiler.
  965: @section Peephole optimization
  967: You need peephole optimization only if you want to use
  968: superinstructions.  But having the code for it does not hurt much if you
  969: do not use superinstructions.
  971: A simple greedy peephole optimization algorithm is used for
  972: superinstruction selection: every time @code{gen_inst} compiles a VM
  973: instruction, it looks if it can combine it with the last VM instruction
  974: (which may also be a superinstruction resulting from a previous peephole
  975: optimization); if so, it changes the last instruction to the combined
  976: instruction instead of laying down @code{i} at the current @samp{*ctp}.
  978: The code for peephole optimization is in @file{vmgen-ex/peephole.c}.
  979: You can use this file almost verbatim.  Vmgen generates
  980: @file{@var{file}-peephole.i} which contains data for the peephoile
  981: optimizer.
  983: You have to call @samp{init_peeptable()} after initializing
  984: @samp{vm_prim}, and before compiling any VM code to initialize data
  985: structures for peephole optimization.  After that, compiling with the VM
  986: code generation functions will automatically combine VM instructions
  987: into superinstructions.  Since you do not want to combine instructions
  988: across VM branch targets (otherwise there will not be a proper VM
  989: instruction to branch to), you have to call @code{BB_BOUNDARY}
  990: (@pxref{VM code generation}) at branch targets.
  993: @section VM disassembler
  995: A VM code disassembler is optional for an interpretive system, but
  996: highly recommended during its development and maintenance, because it is
  997: very useful for detecting bugs in the front end (and for distinguishing
  998: them from VM interpreter bugs).
 1000: Vmgen supports VM code disassembling by generating
 1001: @file{@var{file}-disasm.i}.  This code has to be wrapped into a
 1002: function, as is done in @file{vmgen-ex/disasm.i}.  You can use this file
 1003: almost verbatim.  In addition to @samp{vm_@var{A}2@var{B}(a,b)},
 1004: @samp{vm_out}, @samp{printarg_@var{type}(@var{value})}, which are
 1005: explained above, the following macros and variables are used in
 1006: @file{@var{file}-disasm.i} (and you have to define them):
 1008: @table @samp
 1010: @item ip
 1011: This variable points to the opcode of the current VM instruction.
 1013: @item IP IPTOS
 1014: @samp{IPTOS} is the first argument of the current VM instruction, and
 1015: @samp{IP} points to it; this is just as in the engine, but here
 1016: @samp{ip} points to the opcode of the VM instruction (in contrast to the
 1017: engine, where @samp{ip} points to the next cell, or even one further).
 1019: @item VM_IS_INST(Inst i, int n)
 1020: Tests if the opcode @samp{i} is the same as the @samp{n}th entry in the
 1021: VM instruction table.
 1023: @end table
 1026: @section VM profiler
 1028: The VM profiler is designed for getting execution and occurence counts
 1029: for VM instruction sequences, and these counts can then be used for
 1030: selecting sequences as superinstructions.  The VM profiler is probably
 1031: not useful as profiling tool for the interpretive system (i.e., the VM
 1032: profiler is useful for the developers, but not the users of the
 1033: interpretive system).
 1042: Invocation
 1044: Input Syntax
 1046: Concepts: Front end, VM, Stacks,  Types, input stream
 1048: Contact
 1051: Required changes:
 1052: vm_...2... -> two arguments
 1053: "vm_two...2...(arg1,arg2,arg3);" -> "vm_two...2...(arg3,arg1,arg2)" (no ";").
 1054: define INST_ADDR and LABEL
 1055: define VM_IS_INST also for disassembler

FreeBSD-CVSweb <>