File:  [gforth] / gforth / doc / vmgen.texi
Revision 1.5: download - view: text, annotated - select for diffs
Thu Aug 1 21:14:25 2002 UTC (18 years, 4 months ago) by anton
Branches: MAIN
CVS tags: HEAD
documentation changes

    1: @include version.texi
    2: 
    3: @c @ifnottex
    4: This file documents vmgen (Gforth @value{VERSION}).
    5: 
    6: @chapter Introduction
    7: 
    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.
   14: 
   15: The interpreter design strategy supported by vmgen is to divide the
   16: interpreter into two parts:
   17: 
   18: @itemize @bullet
   19: 
   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.
   25: 
   26: @item The @emph{virtual machine interpreter} executes the virtual
   27: machine code.
   28: 
   29: @end itemize
   30: 
   31: Such a division is usually used in interpreters, for modularity as well
   32: as for efficiency reasons.  The virtual machine code is typically passed
   33: between 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.
   36: 
   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.
   41: 
   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:
   45: 
   46: @table @emph
   47: 
   48: @item VM instruction execution
   49: 
   50: @item VM code generation
   51: Useful in the front end.
   52: 
   53: @item VM code decompiler
   54: Useful for debugging the front end.
   55: 
   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.
   60: 
   61: @item VM code profiling
   62: Useful for optimizing the VM insterpreter with superinstructions
   63: (@pxref...).
   64: 
   65: @end table
   66: 
   67: VMgen supports efficient interpreters though various optimizations, in
   68: particular
   69: 
   70: @itemize
   71: 
   72: @item Threaded code
   73: 
   74: @item Caching the top-of-stack in a register
   75: 
   76: @item Combining VM instructions into superinstructions
   77: 
   78: @item
   79: Replicating VM (super)instructions for better BTB prediction accuracy
   80: (not yet in vmgen-ex, but already in Gforth).
   81: 
   82: @end itemize
   83: 
   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).
   92: 
   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.
   97: 
   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.
  102: 
  103: @c *********************************************************************
  104: @chapter Why interpreters?
  105: 
  106: Interpreters are a popular language implementation technique because
  107: they combine all three of the following advantages:
  108: 
  109: @itemize
  110: 
  111: @item Ease of implementation
  112: 
  113: @item Portability
  114: 
  115: @item Fast edit-compile-run cycle
  116: 
  117: @end itemize
  118: 
  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).
  127: 
  128: Vmgen makes it even easier to implement interpreters.  It also supports
  129: techniques for building efficient interpreters.
  130: 
  131: @c ********************************************************************
  132: 
  133: @chapter Concepts
  134: 
  135: @c --------------------------------------------------------------------
  136: @section Front-end and virtual machine interpreter
  137: 
  138: @cindex front-end
  139: Interpretive systems are typically divided into a @emph{front end} that
  140: parses the input language and produces an intermediate representation
  141: for the program, and an interpreter that executes the intermediate
  142: representation of the program.
  143: 
  144: @cindex virtual machine
  145: @cindex VM
  146: @cindex instruction, VM
  147: For efficient interpreters the intermediate representation of choice is
  148: virtual machine code (rather than, e.g., an abstract syntax tree).
  149: @emph{Virtual machine} (VM) code consists of VM instructions arranged
  150: sequentially in memory; they are executed in sequence by the VM
  151: interpreter, except for VM branch instructions, which implement control
  152: structures.  The conceptual similarity to real machine code results in
  153: the name @emph{virtual machine}.
  154: 
  155: In this framework, vmgen supports building the VM interpreter and any
  156: other component dealing with VM instructions.  It does not have any
  157: support for the front end, apart from VM code generation support.  The
  158: front end can be implemented with classical compiler front-end
  159: techniques, supported by tools like @command{flex} and @command{bison}.
  160: 
  161: The intermediate representation is usually just internal to the
  162: interpreter, but some systems also support saving it to a file, either
  163: as an image file, or in a full-blown linkable file format (e.g., JVM).
  164: Vmgen currently has no special support for such features, but the
  165: information in the instruction descriptions can be helpful, and we are
  166: open for feature requests and suggestions.
  167: 
  168: @section Data handling
  169: 
  170: @cindex stack machine
  171: @cindex register machine
  172: Most VMs use one or more stacks for passing temporary data between VM
  173: instructions.  Another option is to use a register machine architecture
  174: for the virtual machine; however, this option is either slower or
  175: significantly more complex to implement than a stack machine architecture.
  176: 
  177: Vmgen has special support and optimizations for stack VMs, making their
  178: implementation easy and efficient.
  179: 
  180: You can also implement a register VM with vmgen (@pxref{Register
  181: Machines}), and you will still profit from most vmgen features.
  182: 
  183: @cindex stack item size
  184: @cindex size, stack items
  185: Stack items all have the same size, so they typically will be as wide as
  186: an integer, pointer, or floating-point value.  Vmgen supports treating
  187: two consecutive stack items as a single value, but anything larger is
  188: best kept in some other memory area (e.g., the heap), with pointers to
  189: the data on the stack.
  190: 
  191: @cindex instruction stream
  192: @cindex immediate arguments
  193: Another source of data is immediate arguments VM instructions (in the VM
  194: instruction stream).  The VM instruction stream is handled similar to a
  195: stack in vmgen.
  196: 
  197: @cindex garbage collection
  198: @cindex reference counting
  199: Vmgen has no built-in support for nor restrictions against @emph{garbage
  200: collection}.  If you need garbage collection, you need to provide it in
  201: your run-time libraries.  Using @emph{reference counting} is probably
  202: harder, but might be possible (contact us if you are interested).
  203: @c reference counting might be possible by including counting code in 
  204: @c the conversion macros.
  205: 
  206: @c *************************************************************
  207: @chapter Invoking vmgen
  208: 
  209: The usual way to invoke vmgen is as follows:
  210: 
  211: @example
  212: vmgen @var{infile}
  213: @end example
  214: 
  215: Here @var{infile} is the VM instruction description file, which usually
  216: ends in @file{.vmg}.  The output filenames are made by taking the
  217: basename of @file{infile} (i.e., the output files will be created in the
  218: current working directory) and replacing @file{.vmg} with @file{-vm.i},
  219: @file{-disasm.i}, @file{-gen.i}, @file{-labels.i}, @file{-profile.i},
  220: and @file{-peephole.i}.  E.g., @command{bison hack/foo.vmg} will create
  221: @file{foo-vm.i} etc.
  222: 
  223: The command-line options supported by vmgen are
  224: 
  225: @table @option
  226: 
  227: @cindex -h, command-line option
  228: @cindex --help, command-line option
  229: @item --help
  230: @itemx -h
  231: Print a message about the command-line options
  232: 
  233: @cindex -v, command-line option
  234: @cindex --version, command-line option
  235: @item --version
  236: @itemx -v
  237: Print version and exit
  238: @end table
  239: 
  240: @c env vars GFORTHDIR GFORTHDATADIR
  241: 
  242: @c ****************************************************************
  243: @chapter Example
  244: 
  245: @section Example overview
  246: 
  247: There are two versions of the same example for using vmgen:
  248: @file{vmgen-ex} and @file{vmgen-ex2} (you can also see Gforth as
  249: example, but it uses additional (undocumented) features, and also
  250: differs in some other respects).  The example implements @emph{mini}, a
  251: tiny Modula-2-like language with a small JavaVM-like virtual machine.
  252: The difference between the examples is that @file{vmgen-ex} uses many
  253: casts, and @file{vmgen-ex2} tries to avoids most casts and uses unions
  254: instead.
  255: 
  256: The files provided with each example are:
  257: 
  258: @example
  259: Makefile
  260: README
  261: disasm.c           wrapper file
  262: engine.c           wrapper file
  263: peephole.c         wrapper file
  264: profile.c          wrapper file
  265: mini-inst.vmg      simple VM instructions
  266: mini-super.vmg     superinstructions (empty at first)
  267: mini.h             common declarations
  268: mini.l             scanner
  269: mini.y             front end (parser, VM code generator)
  270: support.c          main() and other support functions
  271: fib.mini           example mini program
  272: simple.mini        example mini program
  273: test.mini          example mini program (tests everything)
  274: test.out           test.mini output
  275: stat.awk           script for aggregating profile information
  276: peephole-blacklist list of instructions not allowed in superinstructions
  277: seq2rule.awk       script for creating superinstructions
  278: @end example
  279: 
  280: For your own interpreter, you would typically copy the following files
  281: and change little, if anything:
  282: 
  283: @example
  284: disasm.c           wrapper file
  285: engine.c           wrapper file
  286: peephole.c         wrapper file
  287: profile.c          wrapper file
  288: stat.awk           script for aggregating profile information
  289: seq2rule.awk       script for creating superinstructions
  290: @end example
  291: 
  292: You would typically change much in or replace the following files:
  293: 
  294: @example
  295: Makefile
  296: mini-inst.vmg      simple VM instructions
  297: mini.h             common declarations
  298: mini.l             scanner
  299: mini.y             front end (parser, VM code generator)
  300: support.c          main() and other support functions
  301: peephole-blacklist list of instructions not allowed in superinstructions
  302: @end example
  303: 
  304: You can build the example by @code{cd}ing into the example's directory,
  305: and then typing @samp{make}; you can check that it works with @samp{make
  306: check}.  You can run run mini programs like this:
  307: 
  308: @example
  309: ./mini fib.mini
  310: @end example
  311: 
  312: To learn about the options, type @samp{./mini -h}.
  313: 
  314: @section Using profiling to create superinstructions
  315: 
  316: I have not added rules for this in the @file{Makefile} (there are many
  317: options for selecting superinstructions, and I did not want to hardcode
  318: one into the @file{Makefile}), but there are some supporting scripts, and
  319: here's an example:
  320: 
  321: Suppose you want to use @file{fib.mini} and @file{test.mini} as training
  322: programs, you get the profiles like this:
  323: 
  324: @example
  325: make fib.prof test.prof #takes a few seconds
  326: @end example
  327: 
  328: You can aggregate these profiles with @file{stat.awk}:
  329: 
  330: @example
  331: awk -f stat.awk fib.prof test.prof
  332: @end example
  333: 
  334: The result contains lines like:
  335: 
  336: @example
  337:       2      16        36910041 loadlocal lit
  338: @end example
  339: 
  340: This means that the sequence @code{loadlocal lit} statically occurs a
  341: total of 16 times in 2 profiles, with a dynamic execution count of
  342: 36910041.
  343: 
  344: The numbers can be used in various ways to select superinstructions.
  345: E.g., if you just want to select all sequences with a dynamic
  346: execution count exceeding 10000, you would use the following pipeline:
  347: 
  348: @example
  349: awk -f stat.awk fib.prof test.prof|
  350: awk '$3>=10000'|                #select sequences
  351: fgrep -v -f peephole-blacklist| #eliminate wrong instructions
  352: awk -f seq2rule.awk|      #transform sequences into superinstruction rules
  353: sort -k 3 >mini-super.vmg       #sort sequences
  354: @end example
  355: 
  356: The file @file{peephole-blacklist} contains all instructions that
  357: directly access a stack or stack pointer (for mini: @code{call},
  358: @code{return}); the sort step is necessary to ensure that prefixes
  359: preceed larger superinstructions.
  360: 
  361: Now you can create a version of mini with superinstructions by just
  362: saying @samp{make}
  363: 
  364: @c ***************************************************************
  365: @chapter Input File Format
  366: 
  367: Vmgen takes as input a file containing specifications of virtual machine
  368: instructions.  This file usually has a name ending in @file{.vmg}.
  369: 
  370: Most examples are taken from the example in @file{vmgen-ex}.
  371: 
  372: @section Input File Grammar
  373: 
  374: The grammar is in EBNF format, with @code{@var{a}|@var{b}} meaning
  375: ``@var{a} or @var{b}'', @code{@{@var{c}@}} meaning 0 or more repetitions
  376: of @var{c} and @code{[@var{d}]} meaning 0 or 1 repetitions of @var{d}.
  377: 
  378: Vmgen input is not free-format, so you have to take care where you put
  379: spaces and especially newlines; it's not as bad as makefiles, though:
  380: any sequence of spaces and tabs is equivalent to a single space.
  381: 
  382: @example
  383: description: {instruction|comment|eval-escape}
  384: 
  385: instruction: simple-inst|superinst
  386: 
  387: simple-inst: ident " (" stack-effect " )" newline c-code newline newline
  388: 
  389: stack-effect: {ident} " --" {ident}
  390: 
  391: super-inst: ident " =" ident {ident}  
  392: 
  393: comment:      "\ "  text newline
  394: 
  395: eval-escape:  "\e " text newline
  396: @end example
  397: @c \+ \- \g \f \c
  398: 
  399: Note that the @code{\}s in this grammar are meant literally, not as
  400: C-style encodings for non-printable characters.
  401: 
  402: The C code in @code{simple-inst} must not contain empty lines (because
  403: vmgen would mistake that as the end of the simple-inst.  The text in
  404: @code{comment} and @code{eval-escape} must not contain a newline.
  405: @code{Ident} must conform to the usual conventions of C identifiers
  406: (otherwise the C compiler would choke on the vmgen output).
  407: 
  408: Vmgen understands a few extensions beyond the grammar given here, but
  409: these extensions are only useful for building Gforth.  You can find a
  410: description of the format used for Gforth in @file{prim}.
  411: 
  412: @subsection
  413: @c woanders?
  414: The text in @code{eval-escape} is Forth code that is evaluated when
  415: vmgen reads the line.  If you do not know (and do not want to learn)
  416: Forth, you can build the text according to the following grammar; these
  417: rules are normally all Forth you need for using vmgen:
  418: 
  419: @example
  420: text: stack-decl|type-prefix-decl|stack-prefix-decl
  421: 
  422: stack-decl: "stack " ident ident ident
  423: type-prefix-decl: 
  424:     's" ' string '" ' ("single"|"double") ident "type-prefix" ident
  425: stack-prefix-decl:  ident "stack-prefix" string
  426: @end example
  427: 
  428: Note that the syntax of this code is not checked thoroughly (there are
  429: many other Forth program fragments that could be written there).
  430: 
  431: If you know Forth, the stack effects of the non-standard words involved
  432: are:
  433: 
  434: @example
  435: stack        ( "name" "pointer" "type" -- )
  436:              ( name execution: -- stack )
  437: type-prefix  ( addr u xt1 xt2 n stack "prefix" -- )
  438: single       ( -- xt1 xt2 n )
  439: double       ( -- xt1 xt2 n )
  440: stack-prefix ( stack "prefix" -- )
  441: @end example
  442: 
  443: 
  444: @section Simple instructions
  445: 
  446: We will use the following simple VM instruction description as example:
  447: 
  448: @example
  449: sub ( i1 i2 -- i )
  450: i = i1-i2;
  451: @end example
  452: 
  453: The first line specifies the name of the VM instruction (@code{sub}) and
  454: its stack effect (@code{i1 i2 -- i}).  The rest of the description is
  455: just plain C code.
  456: 
  457: @cindex stack effect
  458: The stack effect specifies that @code{sub} pulls two integers from the
  459: data stack and puts them in the C variables @code{i1} and @code{i2} (with
  460: the rightmost item (@code{i2}) taken from the top of stack) and later
  461: pushes one integer (@code{i)) on the data stack (the rightmost item is
  462: on the top afterwards).
  463: 
  464: How do we know the type and stack of the stack items?  Vmgen uses
  465: prefixes, similar to Fortran; in contrast to Fortran, you have to
  466: define the prefix first:
  467: 
  468: @example
  469: \E s" Cell"   single data-stack type-prefix i
  470: @end example
  471: 
  472: This defines the prefix @code{i} to refer to the type @code{Cell}
  473: (defined as @code{long} in @file{mini.h}) and, by default, to the
  474: @code{data-stack}.  It also specifies that this type takes one stack
  475: item (@code{single}).  The type prefix is part of the variable name.
  476: 
  477: Before we can use @code{data-stack} in this way, we have to define it:
  478: 
  479: @example
  480: \E stack data-stack sp Cell
  481: @end example
  482: @c !! use something other than Cell
  483: 
  484: This line defines the stack @code{data-stack}, which uses the stack
  485: pointer @code{sp}, and each item has the basic type @code{Cell}; other
  486: types have to fit into one or two @code{Cell}s (depending on whether the
  487: type is @code{single} or @code{double} wide), and are converted from and
  488: to Cells on accessing the @code{data-stack) with conversion macros
  489: (@pxref{Conversion macros}).  Stacks grow towards lower addresses in
  490: vmgen-erated interpreters.
  491: 
  492: We can override the default stack of a stack item by using a stack
  493: prefix.  E.g., consider the following instruction:
  494: 
  495: @example
  496: lit ( #i -- i )
  497: @end example
  498: 
  499: The VM instruction @code{lit} takes the item @code{i} from the
  500: instruction stream (indicated by the prefix @code{#}), and pushes it on
  501: the (default) data stack.  The stack prefix is not part of the variable
  502: name.  Stack prefixes are defined like this:
  503: 
  504: @example
  505: \E inst-stream stack-prefix #
  506: @end example
  507: 
  508: This definition defines that the stack prefix @code{#} specifies the
  509: ``stack'' @code{inst-stream}.  Since the instruction stream behaves a
  510: little differently than an ordinary stack, it is predefined, and you do
  511: not need to define it.
  512: 
  513: The instruction stream contains instructions and their immediate
  514: arguments, so specifying that an argument comes from the instruction
  515: stream indicates an immediate argument.  Of course, instruction stream
  516: arguments can only appear to the left of @code{--} in the stack effect.
  517: If there are multiple instruction stream arguments, the leftmost is the
  518: first one (just as the intuition suggests).
  519: 
  520: @subsubsection C Code Macros
  521: 
  522: Vmgen recognizes the following strings in the C code part of simple
  523: instructions:
  524: 
  525: @table @samp
  526: 
  527: @item SET_IP
  528: As far as vmgen is concerned, a VM instruction containing this ends a VM
  529: basic block (used in profiling to delimit profiled sequences).  On the C
  530: level, this also sets the instruction pointer.
  531: 
  532: @item SUPER_END
  533: This ends a basic block (for profiling), without a SET_IP.
  534: 
  535: @item TAIL;
  536: Vmgen replaces @samp{TAIL;} with code for ending a VM instruction and
  537: dispatching the next VM instruction.  This happens automatically when
  538: control reaches the end of the C code.  If you want to have this in the
  539: middle of the C code, you need to use @samp{TAIL;}.  A typical example
  540: is a conditional VM branch:
  541: 
  542: @example
  543: if (branch_condition) {
  544:   SET_IP(target); TAIL;
  545: }
  546: /* implicit tail follows here */
  547: @end example
  548: 
  549: In this example, @samp{TAIL;} is not strictly necessary, because there
  550: is another one implicitly after the if-statement, but using it improves
  551: branch prediction accuracy slightly and allows other optimizations.
  552: 
  553: @item SUPER_CONTINUE
  554: This indicates that the implicit tail at the end of the VM instruction
  555: dispatches the sequentially next VM instruction even if there is a
  556: @code{SET_IP} in the VM instruction.  This enables an optimization that
  557: is not yet implemented in the vmgen-ex code (but in Gforth).  The
  558: typical application is in conditional VM branches:
  559: 
  560: @example
  561: if (branch_condition) {
  562:   SET_IP(target); TAIL; /* now this TAIL is necessary */
  563: }
  564: SUPER_CONTINUE;
  565: @end example
  566: 
  567: @end table
  568: 
  569: Note that vmgen is not smart about C-level tokenization, comments,
  570: strings, or conditional compilation, so it will interpret even a
  571: commented-out SUPER_END as ending a basic block (or, e.g.,
  572: @samp{RETAIL;} as @samp{TAIL;}).  Conversely, vmgen requires the literal
  573: presence of these strings; vmgen will not see them if they are hiding in
  574: a C preprocessor macro.
  575: 
  576: 
  577: @subsubsection C Code restrictions
  578: 
  579: Vmgen generates code and performs some optimizations under the
  580: assumption that the user-supplied C code does not access the stack
  581: pointers or stack items, and that accesses to the instruction pointer
  582: only occur through special macros.  In general you should heed these
  583: restrictions.  However, if you need to break these restrictions, read
  584: the following.
  585: 
  586: Accessing a stack or stack pointer directly can be a problem for several
  587: reasons: 
  588: 
  589: @itemize
  590: 
  591: @item
  592: You may cache the top-of-stack item in a local variable (that is
  593: allocated to a register).  This is the most frequent source of trouble.
  594: You can deal with it either by not using top-of-stack caching (slowdown
  595: factor 1-1.4, depending on machine), or by inserting flushing code
  596: (e.g., @samp{IF_spTOS(sp[...] = spTOS);}) at the start and reloading
  597: code (e.g., @samp{IF_spTOS(spTOS = sp[0])}) at the end of problematic C
  598: code.  Vmgen inserts a stack pointer update before the start of the
  599: user-supplied C code, so the flushing code has to use an index that
  600: corrects for that.  In the future, this flushing may be done
  601: automatically by mentioning a special string in the C code.
  602: @c sometimes flushing and/or reloading unnecessary
  603: 
  604: @item
  605: The vmgen-erated code loads the stack items from stack-pointer-indexed
  606: memory into variables before the user-supplied C code, and stores them
  607: from variables to stack-pointer-indexed memory afterwards.  If you do
  608: any writes to the stack through its stack pointer in your C code, it
  609: will not affact the variables, and your write may be overwritten by the
  610: stores after the C code.  Similarly, a read from a stack using a stack
  611: pointer will not reflect computations of stack items in the same VM
  612: instruction.
  613: 
  614: @item
  615: Superinstructions keep stack items in variables across the whole
  616: superinstruction.  So you should not include VM instructions, that
  617: access a stack or stack pointer, as components of superinstructions.
  618: 
  619: @end itemize
  620: 
  621: You should access the instruction pointer only through its special
  622: macros (@samp{IP}, @samp{SET_IP}, @samp{IPTOS}); this ensure that these
  623: macros can be implemented in several ways for best performance.
  624: @samp{IP} points to the next instruction, and @samp{IPTOS} is its
  625: contents.
  626: 
  627: 
  628: @section Superinstructions
  629: 
  630: Here is an example of a superinstruction definition:
  631: 
  632: @example
  633: lit_sub = lit sub
  634: @end example
  635: 
  636: @code{lit_sub} is the name of the superinstruction, and @code{lit} and
  637: @code{sub} are its components.  This superinstruction performs the same
  638: action as the sequence @code{lit} and @code{sub}.  It is generated
  639: automatically by the VM code generation functions whenever that sequence
  640: occurs, so you only need to add this definition if you want to use this
  641: superinstruction (and even that can be partially automatized,
  642: @pxref{...}).
  643: 
  644: Vmgen requires that the component instructions are simple instructions
  645: defined before superinstructions using the components.  Currently, vmgen
  646: also requires that all the subsequences at the start of a
  647: superinstruction (prefixes) must be defined as superinstruction before
  648: the superinstruction.  I.e., if you want to define a superinstruction
  649: 
  650: @example
  651: sumof5 = add add add add
  652: @end example
  653: 
  654: you first have to define
  655: 
  656: @example
  657: add ( n1 n2 -- n )
  658: n = n1+n2;
  659: 
  660: sumof3 = add add
  661: sumof4 = add add add
  662: @end example
  663: 
  664: Here, @code{sumof4} is the longest prefix of @code{sumof5}, and @code{sumof3}
  665: is the longest prefix of @code{sumof4}.
  666: 
  667: Note that vmgen assumes that only the code it generates accesses stack
  668: pointers, the instruction pointer, and various stack items, and it
  669: performs optimizations based on this assumption.  Therefore, VM
  670: instructions that change the instruction pointer should only be used as
  671: last component; a VM instruction that accesses a stack pointer should
  672: not be used as component at all.  Vmgen does not check these
  673: restrictions, they just result in bugs in your interpreter.
  674: 
  675: @c ********************************************************************
  676: @chapter Using the generated code
  677: 
  678: The easiest way to create a working VM interpreter with vmgen is
  679: probably to start with one of the examples, and modify it for your
  680: purposes.  This chapter is just the reference manual for the macros
  681: etc. used by the generated code, and the other context expected by the
  682: generated code, and what you can do with the various generated files.
  683: 
  684: @section VM engine
  685: 
  686: The VM engine is the VM interpreter that executes the VM code.  It is
  687: essential for an interpretive system.
  688: 
  689: The main file generated for the VM interpreter is
  690: @file{@var{name}-vm.i}.  It uses the following macros and variables (and
  691: you have to define them):
  692: 
  693: @table @code
  694: 
  695: @item LABEL(@var{inst_name})
  696: This is used just before each VM instruction to provide a jump or
  697: @code{switch} label (the @samp{:} is provided by vmgen).  For switch
  698: dispatch this should expand to @samp{case @var{label}}; for
  699: threaded-code dispatch this should just expand to @samp{case
  700: @var{label}}.  In either case @var{label} is usually the @var{inst_name}
  701: with some prefix or suffix to avoid naming conflicts.
  702: 
  703: @item NAME(@var{inst_name_string})
  704: Called on entering a VM instruction with a string containing the name of
  705: the VM instruction as parameter.  In normal execution this should be a
  706: noop, but for tracing this usually prints the name, and possibly other
  707: information (several VM registers in our example).
  708: 
  709: @item DEF_CA
  710: Usually empty.  Called just inside a new scope at the start of a VM
  711: instruction.  Can be used to define variables that should be visible
  712: during every VM instruction.  If you define this macro as non-empty, you
  713: have to provide the finishing @samp{;} in the macro.
  714: 
  715: @item NEXT_P0 NEXT_P1 NEXT_P2
  716: The three parts of instruction dispatch.  They can be defined in
  717: different ways for best performance on various processors (see
  718: @file{engine.c} in the example or @file{engine/threaded.h} in Gforth).
  719: @samp{NEXT_P0} is invoked right at the start of the VM isntruction (but
  720: after @samp{DEF_CA}), @samp{NEXT_P1} right after the user-supplied C
  721: code, and @samp{NEXT_P2} at the end.  The actual jump has to be
  722: performed by @samp{NEXT_P2}.
  723: 
  724: The simplest variant is if @samp{NEXT_P2} does everything and the other
  725: macros do nothing.  Then also related macros like @samp{IP},
  726: @samp{SET_IP}, @samp{IP}, @samp{INC_IP} and @samp{IPTOS} are very
  727: straightforward to define.  For switch dispatch this code consists just
  728: of a jump to the dispatch code (@samp{goto next_inst;} in our example;
  729: for direct threaded code it consists of something like
  730: @samp{({cfa=*ip++; goto *cfa;})}.
  731: 
  732: Pulling code (usually the @samp{cfa=*ip;}) up into @samp{NEXT_P1}
  733: usually does not cause problems, but pulling things up into
  734: @samp{NEXT_P0} usually requires changing the other macros (and, at least
  735: for Gforth on Alpha, it does not buy much, because the compiler often
  736: manages to schedule the relevant stuff up by itself).  An even more
  737: extreme variant is to pull code up even further, into, e.g., NEXT_P1 of
  738: the previous VM instruction (prefetching, useful on PowerPCs).
  739: 
  740: @item INC_IP(@var{n})
  741: This increments IP by @var{n}.
  742: 
  743: @item vm_@var{A}2@var{B}(a,b)
  744: Type casting macro that assigns @samp{a} (of type @var{A}) to @samp{b}
  745: (of type @var{B}).  This is mainly used for getting stack items into
  746: variables and back.  So you need to define macros for every combination
  747: of stack basic type (@code{Cell} in our example) and type-prefix types
  748: used with that stack (in both directions).  For the type-prefix type,
  749: you use the type-prefix (not the C type string) as type name (e.g.,
  750: @samp{vm_Cell2i}, not @samp{vm_Cell2Cell}).  In addition, you have to
  751: define a vm_@var{X}2@var{X} macro for the stack basic type (used in
  752: superinstructions).
  753: 
  754: The stack basic type for the predefined @samp{inst-stream} is
  755: @samp{Cell}.  If you want a stack with the same item size, making its
  756: basic type @samp{Cell} usually reduces the number of macros you have to
  757: define.
  758: 
  759: Here our examples differ a lot: @file{vmgen-ex} uses casts in these
  760: macros, whereas @file{vmgen-ex2} uses union-field selection (or
  761: assignment to union fields).
  762: 
  763: @item vm_two@var{A}2@var{B}(a1,a2,b)
  764: @item vm_@var{B}2two@var{A}(b,a1,a2)
  765: Conversions between two stack items (@code{a1}, @code{a2}) and a
  766: variable @code{b} of a type that takes two stack items.  This does not
  767: occur in our small examples, but you can look at Gforth for examples.
  768: 
  769: @item @var{stackpointer}
  770: For each stack used, the stackpointer name given in the stack
  771: declaration is used.  For a regular stack this must be an l-expression;
  772: typically it is a variable declared as a pointer to the stack's basic
  773: type.  For @samp{inst-stream}, the name is @samp{IP}, and it can be a
  774: plain r-value; typically it is a macro that abstracts away the
  775: differences between the various implementations of NEXT_P*.
  776: 
  777: @item @var{stackpointer}TOS
  778: The top-of-stack for the stack pointed to by @var{stackpointer}.  If you
  779: are using top-of-stack caching for that stack, this should be defined as
  780: variable; if you are not using top-of-stack caching for that stack, this
  781: should be a macro expanding to @samp{@var{stackpointer}[0]}.  The stack
  782: pointer for the predefined @samp{inst-stream} is called @samp{IP}, so
  783: the top-of-stack is called @samp{IPTOS}.
  784: 
  785: @item IF_@var{stackpointer}TOS(@var{expr})
  786: Macro for executing @var{expr}, if top-of-stack caching is used for the
  787: @var{stackpointer} stack.  I.e., this should do @var{expr} if there is
  788: top-of-stack caching for @var{stackpointer}; otherwise it should do
  789: nothing.
  790: 
  791: @item VM_DEBUG
  792: If this is defined, the tracing code will be compiled in (slower
  793: interpretation, but better debugging).  Our example compiles two
  794: versions of the engine, a fast-running one that cannot trace, and one
  795: with potential tracing and profiling.
  796: 
  797: @item vm_debug
  798: Needed only if @samp{VM_DEBUG} is defined.  If this variable contains
  799: true, the VM instructions produce trace output.  It can be turned on or
  800: off at any time.
  801: 
  802: @item vm_out
  803: Needed only if @samp{VM_DEBUG} is defined.  Specifies the file on which
  804: to print the trace output (type @samp{FILE *}).
  805: 
  806: @item printarg_@var{type}(@var{value})
  807: Needed only if @samp{VM_DEBUG} is defined.  Macro or function for
  808: printing @var{value} in a way appropriate for the @var{type}.  This is
  809: used for printing the values of stack items during tracing.  @var{Type}
  810: is normally the type prefix specified in a @code{type-prefix} definition
  811: (e.g., @samp{printarg_i}); in superinstructions it is currently the
  812: basic type of the stack.
  813: 
  814: @end table
  815: 
  816: The file @file{@var{name}-labels.i} is used for enumerating or listing
  817: all virtual machine instructions and uses the following macro:
  818: 
  819: @table @samp
  820: 
  821: @item INST_ADDR(@var{inst_name})
  822: For switch dispatch, this is just the name of the switch label (the same
  823: name as used in @samp{LABEL(@var{inst_name})}).  For threaded-code
  824: dispatch, this is the address of the label defined in
  825: @samp{LABEL(@var{inst_name})}); the address is taken with @samp{&&}
  826: (@pxref{labels-as-values}).
  827: 
  828: @end table
  829: 
  830: 
  831: 
  832: @section Stacks, types, and prefixes
  833: 
  834: 
  835: 
  836: Invocation
  837: 
  838: Input Syntax
  839: 
  840: Concepts: Front end, VM, Stacks,  Types, input stream
  841: 
  842: Contact
  843: 
  844: 
  845: Required changes:
  846: vm_...2... -> two arguments
  847: "vm_two...2...(arg1,arg2,arg3);" -> "vm_two...2...(arg3,arg1,arg2)" (no ";").
  848: define INST_ADDR and LABEL
  849: define VM_IS_INST also for disassembler

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>