File:  [gforth] / gforth / doc / vmgen.texi
Revision 1.11: download - view: text, annotated - select for diffs
Wed Aug 14 09:00:22 2002 UTC (17 years, 5 months ago) by anton
Branches: MAIN
CVS tags: HEAD
vmgen documentation changes

    1: \input texinfo    @c -*-texinfo-*-
    2: @comment %**start of header
    3: @setfilename vmgen.info
    4: @include version.texi
    5: @settitle Vmgen (Gforth @value{VERSION})
    6: @c @syncodeindex pg cp
    7: @comment %**end of header
    8: @copying
    9: This manual is for Vmgen
   10: (version @value{VERSION}, @value{UPDATED}),
   11: the virtual machine interpreter generator
   12: 
   13: Copyright @copyright{} 2002 Free Software Foundation, Inc.
   14: 
   15: @quotation
   16: Permission is granted to copy, distribute and/or modify this document
   17: under the terms of the GNU Free Documentation License, Version 1.1 or
   18: any later version published by the Free Software Foundation; with no
   19: Invariant Sections, with the Front-Cover texts being ``A GNU Manual,''
   20: and with the Back-Cover Texts as in (a) below.  A copy of the
   21: license is included in the section entitled ``GNU Free Documentation
   22: License.''
   23: 
   24: (a) The FSF's Back-Cover Text is: ``You have freedom to copy and modify
   25: this GNU Manual, like GNU software.  Copies published by the Free
   26: Software Foundation raise funds for GNU development.''
   27: @end quotation
   28: @end copying
   29: 
   30: @dircategory GNU programming tools
   31: @direntry
   32: * Vmgen: (vmgen).               Interpreter generator
   33: @end direntry
   34: 
   35: @titlepage
   36: @title Vmgen
   37: @subtitle for Gforth version @value{VERSION}, @value{UPDATED}
   38: @author M. Anton Ertl (@email{anton@@mips.complang.tuwien.ac.at})
   39: @page
   40: @vskip 0pt plus 1filll
   41: @insertcopying
   42: @end titlepage
   43: 
   44: @contents
   45: 
   46: @ifnottex
   47: @node Top, Introduction, (dir), (dir)
   48: @top Vmgen
   49: 
   50: @insertcopying
   51: @end ifnottex
   52: 
   53: @menu
   54: * Introduction::                What can Vmgen do for you?
   55: * Why interpreters?::           Advantages and disadvantages
   56: * Concepts::                    VM interpreter background
   57: * Invoking Vmgen::              
   58: * Example::                     
   59: * Input File Format::           
   60: * Using the generated code::    
   61: * Changes::                     from earlier versions
   62: * Contact::                     Bug reporting etc.
   63: * Copying This Manual::         Manual License
   64: * Index::                       
   65: 
   66: @detailmenu
   67:  --- The Detailed Node Listing ---
   68: 
   69: Concepts
   70: 
   71: * Front end and VM interpreter::  Modularizing an interpretive system
   72: * Data handling::               Stacks, registers, immediate arguments
   73: * Dispatch::                    From one VM instruction to the next
   74: 
   75: Example
   76: 
   77: * Example overview::            
   78: * Using profiling to create superinstructions::  
   79: 
   80: Input File Format
   81: 
   82: * Input File Grammar::          
   83: * Simple instructions::         
   84: * Superinstructions::           
   85: * Register Machines::           How to define register VM instructions
   86: 
   87: Simple instructions
   88: 
   89: * C Code Macros::               Macros recognized by Vmgen
   90: * C Code restrictions::         Vmgen makes assumptions about C code
   91: 
   92: Using the generated code
   93: 
   94: * VM engine::                   Executing VM code
   95: * VM instruction table::        
   96: * VM code generation::          Creating VM code (in the front-end)
   97: * Peephole optimization::       Creating VM superinstructions
   98: * VM disassembler::             for debugging the front end
   99: * VM profiler::                 for finding worthwhile superinstructions
  100: 
  101: Copying This Manual
  102: 
  103: * GNU Free Documentation License::  License for copying this manual.
  104: 
  105: @end detailmenu
  106: @end menu
  107: 
  108: @c @ifnottex
  109: @c This file documents Vmgen (Gforth @value{VERSION}).
  110: 
  111: @c ************************************************************
  112: @node Introduction, Why interpreters?, Top, Top
  113: @chapter Introduction
  114: 
  115: Vmgen is a tool for writing efficient interpreters.  It takes a simple
  116: virtual machine description and generates efficient C code for dealing
  117: with the virtual machine code in various ways (in particular, executing
  118: it).  The run-time efficiency of the resulting interpreters is usually
  119: within a factor of 10 of machine code produced by an optimizing
  120: compiler.
  121: 
  122: The interpreter design strategy supported by Vmgen is to divide the
  123: interpreter into two parts:
  124: 
  125: @itemize @bullet
  126: 
  127: @item The @emph{front end} takes the source code of the language to be
  128: implemented, and translates it into virtual machine code.  This is
  129: similar to an ordinary compiler front end; typically an interpreter
  130: front-end performs no optimization, so it is relatively simple to
  131: implement and runs fast.
  132: 
  133: @item The @emph{virtual machine interpreter} executes the virtual
  134: machine code.
  135: 
  136: @end itemize
  137: 
  138: Such a division is usually used in interpreters, for modularity as well
  139: as for efficiency.  The virtual machine code is typically passed between
  140: front end and virtual machine interpreter in memory, like in a
  141: load-and-go compiler; this avoids the complexity and time cost of
  142: writing the code to a file and reading it again.
  143: 
  144: A @emph{virtual machine} (VM) represents the program as a sequence of
  145: @emph{VM instructions}, following each other in memory, similar to real
  146: machine code.  Control flow occurs through VM branch instructions, like
  147: in a real machine.
  148: 
  149: In this setup, Vmgen can generate most of the code dealing with virtual
  150: machine instructions from a simple description of the virtual machine
  151: instructions (@pxref{Input File Format}), in particular:
  152: 
  153: @table @asis
  154: 
  155: @item VM instruction execution
  156: 
  157: @item VM code generation
  158: Useful in the front end.
  159: 
  160: @item VM code decompiler
  161: Useful for debugging the front end.
  162: 
  163: @item VM code tracing
  164: Useful for debugging the front end and the VM interpreter.  You will
  165: typically provide other means for debugging the user's programs at the
  166: source level.
  167: 
  168: @item VM code profiling
  169: Useful for optimizing the VM insterpreter with superinstructions
  170: (@pxref{VM profiler}).
  171: 
  172: @end table
  173: 
  174: @noindent
  175: Vmgen supports efficient interpreters though various optimizations, in
  176: particular
  177: 
  178: @itemize @bullet
  179: 
  180: @item Threaded code
  181: 
  182: @item Caching the top-of-stack in a register
  183: 
  184: @item Combining VM instructions into superinstructions
  185: 
  186: @item
  187: Replicating VM (super)instructions for better BTB prediction accuracy
  188: (not yet in vmgen-ex, but already in Gforth).
  189: 
  190: @end itemize
  191: 
  192: As a result, Vmgen-based interpreters are only about an order of
  193: magnitude slower than native code from an optimizing C compiler on small
  194: benchmarks; on large benchmarks, which spend more time in the run-time
  195: system, the slowdown is often less (e.g., the slowdown of a
  196: Vmgen-generated JVM interpreter over the best JVM JIT compiler we
  197: measured is only a factor of 2-3 for large benchmarks; some other JITs
  198: and all other interpreters we looked at were slower than our
  199: interpreter).
  200: 
  201: VMs are usually designed as stack machines (passing data between VM
  202: instructions on a stack), and Vmgen supports such designs especially
  203: well; however, you can also use Vmgen for implementing a register VM and
  204: still benefit from most of the advantages offered by Vmgen.
  205: 
  206: There are many potential uses of the instruction descriptions that are
  207: not implemented at the moment, but we are open for feature requests, and
  208: we will implement new features if someone asks for them; so the feature
  209: list above is not exhaustive.
  210: 
  211: @c *********************************************************************
  212: @node Why interpreters?, Concepts, Introduction, Top
  213: @chapter Why interpreters?
  214: 
  215: Interpreters are a popular language implementation technique because
  216: they combine all three of the following advantages:
  217: 
  218: @itemize @bullet
  219: 
  220: @item Ease of implementation
  221: 
  222: @item Portability
  223: 
  224: @item Fast edit-compile-run cycle
  225: 
  226: @end itemize
  227: 
  228: The main disadvantage of interpreters is their run-time speed.  However,
  229: there are huge differences between different interpreters in this area:
  230: the slowdown over optimized C code on programs consisting of simple
  231: operations is typically a factor of 10 for the more efficient
  232: interpreters, and a factor of 1000 for the less efficient ones (the
  233: slowdown for programs executing complex operations is less, because the
  234: time spent in libraries for executing complex operations is the same in
  235: all implementation strategies).
  236: 
  237: Vmgen makes it even easier to implement interpreters.  It also supports
  238: techniques for building efficient interpreters.
  239: 
  240: @c ********************************************************************
  241: @node Concepts, Invoking Vmgen, Why interpreters?, Top
  242: @chapter Concepts
  243: 
  244: @menu
  245: * Front end and VM interpreter::  Modularizing an interpretive system
  246: * Data handling::               Stacks, registers, immediate arguments
  247: * Dispatch::                    From one VM instruction to the next
  248: @end menu
  249: 
  250: @c --------------------------------------------------------------------
  251: @node Front end and VM interpreter, Data handling, Concepts, Concepts
  252: @section Front end and VM interpreter
  253: 
  254: @cindex front-end
  255: Interpretive systems are typically divided into a @emph{front end} that
  256: parses the input language and produces an intermediate representation
  257: for the program, and an interpreter that executes the intermediate
  258: representation of the program.
  259: 
  260: @cindex virtual machine
  261: @cindex VM
  262: @cindex instruction, VM
  263: For efficient interpreters the intermediate representation of choice is
  264: virtual machine code (rather than, e.g., an abstract syntax tree).
  265: @emph{Virtual machine} (VM) code consists of VM instructions arranged
  266: sequentially in memory; they are executed in sequence by the VM
  267: interpreter, except for VM branch instructions, which implement control
  268: structures.  The conceptual similarity to real machine code results in
  269: the name @emph{virtual machine}.
  270: 
  271: In this framework, Vmgen supports building the VM interpreter and any
  272: other component dealing with VM instructions.  It does not have any
  273: support for the front end, apart from VM code generation support.  The
  274: front end can be implemented with classical compiler front-end
  275: techniques, supported by tools like @command{flex} and @command{bison}.
  276: 
  277: The intermediate representation is usually just internal to the
  278: interpreter, but some systems also support saving it to a file, either
  279: as an image file, or in a full-blown linkable file format (e.g., JVM).
  280: Vmgen currently has no special support for such features, but the
  281: information in the instruction descriptions can be helpful, and we are
  282: open for feature requests and suggestions.
  283: 
  284: @c --------------------------------------------------------------------
  285: @node Data handling, Dispatch, Front end and VM interpreter, Concepts
  286: @section Data handling
  287: 
  288: @cindex stack machine
  289: @cindex register machine
  290: Most VMs use one or more stacks for passing temporary data between VM
  291: instructions.  Another option is to use a register machine architecture
  292: for the virtual machine; however, this option is either slower or
  293: significantly more complex to implement than a stack machine architecture.
  294: 
  295: Vmgen has special support and optimizations for stack VMs, making their
  296: implementation easy and efficient.
  297: 
  298: You can also implement a register VM with Vmgen (@pxref{Register
  299: Machines}), and you will still profit from most Vmgen features.
  300: 
  301: @cindex stack item size
  302: @cindex size, stack items
  303: Stack items all have the same size, so they typically will be as wide as
  304: an integer, pointer, or floating-point value.  Vmgen supports treating
  305: two consecutive stack items as a single value, but anything larger is
  306: best kept in some other memory area (e.g., the heap), with pointers to
  307: the data on the stack.
  308: 
  309: @cindex instruction stream
  310: @cindex immediate arguments
  311: Another source of data is immediate arguments VM instructions (in the VM
  312: instruction stream).  The VM instruction stream is handled similar to a
  313: stack in Vmgen.
  314: 
  315: @cindex garbage collection
  316: @cindex reference counting
  317: Vmgen has no built-in support for nor restrictions against @emph{garbage
  318: collection}.  If you need garbage collection, you need to provide it in
  319: your run-time libraries.  Using @emph{reference counting} is probably
  320: harder, but might be possible (contact us if you are interested).
  321: @c reference counting might be possible by including counting code in 
  322: @c the conversion macros.
  323: 
  324: @c --------------------------------------------------------------------
  325: @node Dispatch,  , Data handling, Concepts
  326: @section Dispatch
  327: 
  328: Understanding this section is probably not necessary for using Vmgen,
  329: but it may help.  You may want to skip it now, and read it if you find statements about dispatch methods confusing.
  330: 
  331: After executing one VM instruction, the VM interpreter has to dispatch
  332: the next VM instruction (Vmgen calls the dispatch routine @samp{NEXT}).
  333: Vmgen supports two methods of dispatch:
  334: 
  335: @table @asis
  336: 
  337: @item switch dispatch
  338: In this method the VM interpreter contains a giant @code{switch}
  339: statement, with one @code{case} for each VM instruction.  The VM
  340: instructions are represented by integers (e.g., produced by an
  341: @code{enum}) in the VM code, and dipatch occurs by loading the next
  342: integer from the VM code, @code{switch}ing on it, and continuing at the
  343: appropriate @code{case}; after executing the VM instruction, jump back
  344: to the dispatch code.
  345: 
  346: @item threaded code
  347: This method represents a VM instruction in the VM code by the address of
  348: the start of the machine code fragment for executing the VM instruction.
  349: Dispatch consists of loading this address, jumping to it, and
  350: incrementing the VM instruction pointer.  Typically the threaded-code
  351: dispatch code is appended directly to the code for executing the VM
  352: instruction.  Threaded code cannot be implemented in ANSI C, but it can
  353: be implemented using GNU C's labels-as-values extension (@pxref{Labels
  354: as Values, , Labels as Values, gcc.info, GNU C Manual}).
  355: 
  356: @end table
  357: 
  358: @c *************************************************************
  359: @node Invoking Vmgen, Example, Concepts, Top
  360: @chapter Invoking Vmgen
  361: 
  362: The usual way to invoke Vmgen is as follows:
  363: 
  364: @example
  365: vmgen @var{infile}
  366: @end example
  367: 
  368: Here @var{infile} is the VM instruction description file, which usually
  369: ends in @file{.vmg}.  The output filenames are made by taking the
  370: basename of @file{infile} (i.e., the output files will be created in the
  371: current working directory) and replacing @file{.vmg} with @file{-vm.i},
  372: @file{-disasm.i}, @file{-gen.i}, @file{-labels.i}, @file{-profile.i},
  373: and @file{-peephole.i}.  E.g., @command{bison hack/foo.vmg} will create
  374: @file{foo-vm.i} etc.
  375: 
  376: The command-line options supported by Vmgen are
  377: 
  378: @table @option
  379: 
  380: @cindex -h, command-line option
  381: @cindex --help, command-line option
  382: @item --help
  383: @itemx -h
  384: Print a message about the command-line options
  385: 
  386: @cindex -v, command-line option
  387: @cindex --version, command-line option
  388: @item --version
  389: @itemx -v
  390: Print version and exit
  391: @end table
  392: 
  393: @c env vars GFORTHDIR GFORTHDATADIR
  394: 
  395: @c ****************************************************************
  396: @node Example, Input File Format, Invoking Vmgen, Top
  397: @chapter Example
  398: 
  399: @menu
  400: * Example overview::            
  401: * Using profiling to create superinstructions::  
  402: @end menu
  403: 
  404: @c --------------------------------------------------------------------
  405: @node Example overview, Using profiling to create superinstructions, Example, Example
  406: @section Example overview
  407: 
  408: There are two versions of the same example for using Vmgen:
  409: @file{vmgen-ex} and @file{vmgen-ex2} (you can also see Gforth as
  410: example, but it uses additional (undocumented) features, and also
  411: differs in some other respects).  The example implements @emph{mini}, a
  412: tiny Modula-2-like language with a small JavaVM-like virtual machine.
  413: The difference between the examples is that @file{vmgen-ex} uses many
  414: casts, and @file{vmgen-ex2} tries to avoids most casts and uses unions
  415: instead.
  416: 
  417: The files provided with each example are:
  418: 
  419: @example
  420: Makefile
  421: README
  422: disasm.c           wrapper file
  423: engine.c           wrapper file
  424: peephole.c         wrapper file
  425: profile.c          wrapper file
  426: mini-inst.vmg      simple VM instructions
  427: mini-super.vmg     superinstructions (empty at first)
  428: mini.h             common declarations
  429: mini.l             scanner
  430: mini.y             front end (parser, VM code generator)
  431: support.c          main() and other support functions
  432: fib.mini           example mini program
  433: simple.mini        example mini program
  434: test.mini          example mini program (tests everything)
  435: test.out           test.mini output
  436: stat.awk           script for aggregating profile information
  437: peephole-blacklist list of instructions not allowed in superinstructions
  438: seq2rule.awk       script for creating superinstructions
  439: @end example
  440: 
  441: For your own interpreter, you would typically copy the following files
  442: and change little, if anything:
  443: 
  444: @example
  445: disasm.c           wrapper file
  446: engine.c           wrapper file
  447: peephole.c         wrapper file
  448: profile.c          wrapper file
  449: stat.awk           script for aggregating profile information
  450: seq2rule.awk       script for creating superinstructions
  451: @end example
  452: 
  453: @noindent
  454: You would typically change much in or replace the following files:
  455: 
  456: @example
  457: Makefile
  458: mini-inst.vmg      simple VM instructions
  459: mini.h             common declarations
  460: mini.l             scanner
  461: mini.y             front end (parser, VM code generator)
  462: support.c          main() and other support functions
  463: peephole-blacklist list of instructions not allowed in superinstructions
  464: @end example
  465: 
  466: You can build the example by @code{cd}ing into the example's directory,
  467: and then typing @samp{make}; you can check that it works with @samp{make
  468: check}.  You can run run mini programs like this:
  469: 
  470: @example
  471: ./mini fib.mini
  472: @end example
  473: 
  474: To learn about the options, type @samp{./mini -h}.
  475: 
  476: @c --------------------------------------------------------------------
  477: @node Using profiling to create superinstructions,  , Example overview, Example
  478: @section Using profiling to create superinstructions
  479: 
  480: I have not added rules for this in the @file{Makefile} (there are many
  481: options for selecting superinstructions, and I did not want to hardcode
  482: one into the @file{Makefile}), but there are some supporting scripts, and
  483: here's an example:
  484: 
  485: Suppose you want to use @file{fib.mini} and @file{test.mini} as training
  486: programs, you get the profiles like this:
  487: 
  488: @example
  489: make fib.prof test.prof #takes a few seconds
  490: @end example
  491: 
  492: You can aggregate these profiles with @file{stat.awk}:
  493: 
  494: @example
  495: awk -f stat.awk fib.prof test.prof
  496: @end example
  497: 
  498: The result contains lines like:
  499: 
  500: @example
  501:       2      16        36910041 loadlocal lit
  502: @end example
  503: 
  504: This means that the sequence @code{loadlocal lit} statically occurs a
  505: total of 16 times in 2 profiles, with a dynamic execution count of
  506: 36910041.
  507: 
  508: The numbers can be used in various ways to select superinstructions.
  509: E.g., if you just want to select all sequences with a dynamic
  510: execution count exceeding 10000, you would use the following pipeline:
  511: 
  512: @example
  513: awk -f stat.awk fib.prof test.prof|
  514: awk '$3>=10000'|                #select sequences
  515: fgrep -v -f peephole-blacklist| #eliminate wrong instructions
  516: awk -f seq2rule.awk|      #transform sequences into superinstruction rules
  517: sort -k 3 >mini-super.vmg       #sort sequences
  518: @end example
  519: 
  520: The file @file{peephole-blacklist} contains all instructions that
  521: directly access a stack or stack pointer (for mini: @code{call},
  522: @code{return}); the sort step is necessary to ensure that prefixes
  523: preceed larger superinstructions.
  524: 
  525: Now you can create a version of mini with superinstructions by just
  526: saying @samp{make}
  527: 
  528: 
  529: @c ***************************************************************
  530: @node Input File Format, Using the generated code, Example, Top
  531: @chapter Input File Format
  532: 
  533: Vmgen takes as input a file containing specifications of virtual machine
  534: instructions.  This file usually has a name ending in @file{.vmg}.
  535: 
  536: Most examples are taken from the example in @file{vmgen-ex}.
  537: 
  538: @menu
  539: * Input File Grammar::          
  540: * Simple instructions::         
  541: * Superinstructions::           
  542: * Register Machines::           How to define register VM instructions
  543: @end menu
  544: 
  545: @c --------------------------------------------------------------------
  546: @node Input File Grammar, Simple instructions, Input File Format, Input File Format
  547: @section Input File Grammar
  548: 
  549: The grammar is in EBNF format, with @code{@var{a}|@var{b}} meaning
  550: ``@var{a} or @var{b}'', @code{@{@var{c}@}} meaning 0 or more repetitions
  551: of @var{c} and @code{[@var{d}]} meaning 0 or 1 repetitions of @var{d}.
  552: 
  553: Vmgen input is not free-format, so you have to take care where you put
  554: spaces and especially newlines; it's not as bad as makefiles, though:
  555: any sequence of spaces and tabs is equivalent to a single space.
  556: 
  557: @example
  558: description: @{instruction|comment|eval-escape@}
  559: 
  560: instruction: simple-inst|superinst
  561: 
  562: simple-inst: ident " (" stack-effect " )" newline c-code newline newline
  563: 
  564: stack-effect: @{ident@} " --" @{ident@}
  565: 
  566: super-inst: ident " =" ident @{ident@}  
  567: 
  568: comment:      "\ "  text newline
  569: 
  570: eval-escape:  "\e " text newline
  571: @end example
  572: @c \+ \- \g \f \c
  573: 
  574: Note that the @code{\}s in this grammar are meant literally, not as
  575: C-style encodings for non-printable characters.
  576: 
  577: The C code in @code{simple-inst} must not contain empty lines (because
  578: Vmgen would mistake that as the end of the simple-inst.  The text in
  579: @code{comment} and @code{eval-escape} must not contain a newline.
  580: @code{Ident} must conform to the usual conventions of C identifiers
  581: (otherwise the C compiler would choke on the Vmgen output).
  582: 
  583: Vmgen understands a few extensions beyond the grammar given here, but
  584: these extensions are only useful for building Gforth.  You can find a
  585: description of the format used for Gforth in @file{prim}.
  586: 
  587: @subsection Eval escapes
  588: @c woanders?
  589: The text in @code{eval-escape} is Forth code that is evaluated when
  590: Vmgen reads the line.  If you do not know (and do not want to learn)
  591: Forth, you can build the text according to the following grammar; these
  592: rules are normally all Forth you need for using Vmgen:
  593: 
  594: @example
  595: text: stack-decl|type-prefix-decl|stack-prefix-decl
  596: 
  597: stack-decl: "stack " ident ident ident
  598: type-prefix-decl: 
  599:     's" ' string '" ' ("single"|"double") ident "type-prefix" ident
  600: stack-prefix-decl:  ident "stack-prefix" string
  601: @end example
  602: 
  603: Note that the syntax of this code is not checked thoroughly (there are
  604: many other Forth program fragments that could be written there).
  605: 
  606: If you know Forth, the stack effects of the non-standard words involved
  607: are:
  608: 
  609: @example
  610: stack        ( "name" "pointer" "type" -- )
  611:              ( name execution: -- stack )
  612: type-prefix  ( addr u xt1 xt2 n stack "prefix" -- )
  613: single       ( -- xt1 xt2 n )
  614: double       ( -- xt1 xt2 n )
  615: stack-prefix ( stack "prefix" -- )
  616: @end example
  617: 
  618: 
  619: @c --------------------------------------------------------------------
  620: @node Simple instructions, Superinstructions, Input File Grammar, Input File Format
  621: @section Simple instructions
  622: 
  623: We will use the following simple VM instruction description as example:
  624: 
  625: @example
  626: sub ( i1 i2 -- i )
  627: i = i1-i2;
  628: @end example
  629: 
  630: The first line specifies the name of the VM instruction (@code{sub}) and
  631: its stack effect (@code{i1 i2 -- i}).  The rest of the description is
  632: just plain C code.
  633: 
  634: @cindex stack effect
  635: The stack effect specifies that @code{sub} pulls two integers from the
  636: data stack and puts them in the C variables @code{i1} and @code{i2} (with
  637: the rightmost item (@code{i2}) taken from the top of stack) and later
  638: pushes one integer (@code{i}) on the data stack (the rightmost item is
  639: on the top afterwards).
  640: 
  641: How do we know the type and stack of the stack items?  Vmgen uses
  642: prefixes, similar to Fortran; in contrast to Fortran, you have to
  643: define the prefix first:
  644: 
  645: @example
  646: \E s" Cell"   single data-stack type-prefix i
  647: @end example
  648: 
  649: This defines the prefix @code{i} to refer to the type @code{Cell}
  650: (defined as @code{long} in @file{mini.h}) and, by default, to the
  651: @code{data-stack}.  It also specifies that this type takes one stack
  652: item (@code{single}).  The type prefix is part of the variable name.
  653: 
  654: Before we can use @code{data-stack} in this way, we have to define it:
  655: 
  656: @example
  657: \E stack data-stack sp Cell
  658: @end example
  659: @c !! use something other than Cell
  660: 
  661: This line defines the stack @code{data-stack}, which uses the stack
  662: pointer @code{sp}, and each item has the basic type @code{Cell}; other
  663: types have to fit into one or two @code{Cell}s (depending on whether the
  664: type is @code{single} or @code{double} wide), and are converted from and
  665: to Cells on accessing the @code{data-stack} with conversion macros
  666: (@pxref{VM engine}).  Stacks grow towards lower addresses in
  667: Vmgen-erated interpreters.
  668: 
  669: We can override the default stack of a stack item by using a stack
  670: prefix.  E.g., consider the following instruction:
  671: 
  672: @example
  673: lit ( #i -- i )
  674: @end example
  675: 
  676: The VM instruction @code{lit} takes the item @code{i} from the
  677: instruction stream (indicated by the prefix @code{#}), and pushes it on
  678: the (default) data stack.  The stack prefix is not part of the variable
  679: name.  Stack prefixes are defined like this:
  680: 
  681: @example
  682: \E inst-stream stack-prefix #
  683: @end example
  684: 
  685: This definition defines that the stack prefix @code{#} specifies the
  686: ``stack'' @code{inst-stream}.  Since the instruction stream behaves a
  687: little differently than an ordinary stack, it is predefined, and you do
  688: not need to define it.
  689: 
  690: The instruction stream contains instructions and their immediate
  691: arguments, so specifying that an argument comes from the instruction
  692: stream indicates an immediate argument.  Of course, instruction stream
  693: arguments can only appear to the left of @code{--} in the stack effect.
  694: If there are multiple instruction stream arguments, the leftmost is the
  695: first one (just as the intuition suggests).
  696: 
  697: @menu
  698: * C Code Macros::               Macros recognized by Vmgen
  699: * C Code restrictions::         Vmgen makes assumptions about C code
  700: @end menu
  701: 
  702: @c --------------------------------------------------------------------
  703: @node C Code Macros, C Code restrictions, Simple instructions, Simple instructions
  704: @subsection C Code Macros
  705: 
  706: Vmgen recognizes the following strings in the C code part of simple
  707: instructions:
  708: 
  709: @table @samp
  710: 
  711: @item SET_IP
  712: As far as Vmgen is concerned, a VM instruction containing this ends a VM
  713: basic block (used in profiling to delimit profiled sequences).  On the C
  714: level, this also sets the instruction pointer.
  715: 
  716: @item SUPER_END
  717: This ends a basic block (for profiling), without a SET_IP.
  718: 
  719: @item TAIL;
  720: Vmgen replaces @samp{TAIL;} with code for ending a VM instruction and
  721: dispatching the next VM instruction.  This happens automatically when
  722: control reaches the end of the C code.  If you want to have this in the
  723: middle of the C code, you need to use @samp{TAIL;}.  A typical example
  724: is a conditional VM branch:
  725: 
  726: @example
  727: if (branch_condition) @{
  728:   SET_IP(target); TAIL;
  729: @}
  730: /* implicit tail follows here */
  731: @end example
  732: 
  733: In this example, @samp{TAIL;} is not strictly necessary, because there
  734: is another one implicitly after the if-statement, but using it improves
  735: branch prediction accuracy slightly and allows other optimizations.
  736: 
  737: @item SUPER_CONTINUE
  738: This indicates that the implicit tail at the end of the VM instruction
  739: dispatches the sequentially next VM instruction even if there is a
  740: @code{SET_IP} in the VM instruction.  This enables an optimization that
  741: is not yet implemented in the vmgen-ex code (but in Gforth).  The
  742: typical application is in conditional VM branches:
  743: 
  744: @example
  745: if (branch_condition) @{
  746:   SET_IP(target); TAIL; /* now this TAIL is necessary */
  747: @}
  748: SUPER_CONTINUE;
  749: @end example
  750: 
  751: @end table
  752: 
  753: Note that Vmgen is not smart about C-level tokenization, comments,
  754: strings, or conditional compilation, so it will interpret even a
  755: commented-out SUPER_END as ending a basic block (or, e.g.,
  756: @samp{RETAIL;} as @samp{TAIL;}).  Conversely, Vmgen requires the literal
  757: presence of these strings; Vmgen will not see them if they are hiding in
  758: a C preprocessor macro.
  759: 
  760: 
  761: @c --------------------------------------------------------------------
  762: @node C Code restrictions,  , C Code Macros, Simple instructions
  763: @subsection C Code restrictions
  764: 
  765: Vmgen generates code and performs some optimizations under the
  766: assumption that the user-supplied C code does not access the stack
  767: pointers or stack items, and that accesses to the instruction pointer
  768: only occur through special macros.  In general you should heed these
  769: restrictions.  However, if you need to break these restrictions, read
  770: the following.
  771: 
  772: Accessing a stack or stack pointer directly can be a problem for several
  773: reasons: 
  774: 
  775: @itemize @bullet
  776: 
  777: @item
  778: You may cache the top-of-stack item in a local variable (that is
  779: allocated to a register).  This is the most frequent source of trouble.
  780: You can deal with it either by not using top-of-stack caching (slowdown
  781: factor 1-1.4, depending on machine), or by inserting flushing code
  782: (e.g., @samp{IF_spTOS(sp[...] = spTOS);}) at the start and reloading
  783: code (e.g., @samp{IF_spTOS(spTOS = sp[0])}) at the end of problematic C
  784: code.  Vmgen inserts a stack pointer update before the start of the
  785: user-supplied C code, so the flushing code has to use an index that
  786: corrects for that.  In the future, this flushing may be done
  787: automatically by mentioning a special string in the C code.
  788: @c sometimes flushing and/or reloading unnecessary
  789: 
  790: @item
  791: The Vmgen-erated code loads the stack items from stack-pointer-indexed
  792: memory into variables before the user-supplied C code, and stores them
  793: from variables to stack-pointer-indexed memory afterwards.  If you do
  794: any writes to the stack through its stack pointer in your C code, it
  795: will not affact the variables, and your write may be overwritten by the
  796: stores after the C code.  Similarly, a read from a stack using a stack
  797: pointer will not reflect computations of stack items in the same VM
  798: instruction.
  799: 
  800: @item
  801: Superinstructions keep stack items in variables across the whole
  802: superinstruction.  So you should not include VM instructions, that
  803: access a stack or stack pointer, as components of superinstructions.
  804: 
  805: @end itemize
  806: 
  807: You should access the instruction pointer only through its special
  808: macros (@samp{IP}, @samp{SET_IP}, @samp{IPTOS}); this ensure that these
  809: macros can be implemented in several ways for best performance.
  810: @samp{IP} points to the next instruction, and @samp{IPTOS} is its
  811: contents.
  812: 
  813: 
  814: @c --------------------------------------------------------------------
  815: @node Superinstructions, Register Machines, Simple instructions, Input File Format
  816: @section Superinstructions
  817: 
  818: Note: don't invest too much work in (static) superinstructions; a future
  819: version of Vmgen will support dynamic superinstructions (see Ian
  820: Piumarta and Fabio Riccardi, @cite{Optimizing Direct Threaded Code by
  821: Selective Inlining}, PLDI'98), and static superinstructions have much
  822: less benefit in that context.
  823: 
  824: Here is an example of a superinstruction definition:
  825: 
  826: @example
  827: lit_sub = lit sub
  828: @end example
  829: 
  830: @code{lit_sub} is the name of the superinstruction, and @code{lit} and
  831: @code{sub} are its components.  This superinstruction performs the same
  832: action as the sequence @code{lit} and @code{sub}.  It is generated
  833: automatically by the VM code generation functions whenever that sequence
  834: occurs, so if you want to use this superinstruction, you just need to
  835: add this definition (and even that can be partially automatized,
  836: @pxref{VM profiler}).
  837: 
  838: Vmgen requires that the component instructions are simple instructions
  839: defined before superinstructions using the components.  Currently, Vmgen
  840: also requires that all the subsequences at the start of a
  841: superinstruction (prefixes) must be defined as superinstruction before
  842: the superinstruction.  I.e., if you want to define a superinstruction
  843: 
  844: @example
  845: sumof5 = add add add add
  846: @end example
  847: 
  848: you first have to define
  849: 
  850: @example
  851: add ( n1 n2 -- n )
  852: n = n1+n2;
  853: 
  854: sumof3 = add add
  855: sumof4 = add add add
  856: @end example
  857: 
  858: Here, @code{sumof4} is the longest prefix of @code{sumof5}, and @code{sumof3}
  859: is the longest prefix of @code{sumof4}.
  860: 
  861: Note that Vmgen assumes that only the code it generates accesses stack
  862: pointers, the instruction pointer, and various stack items, and it
  863: performs optimizations based on this assumption.  Therefore, VM
  864: instructions that change the instruction pointer should only be used as
  865: last component; a VM instruction that accesses a stack pointer should
  866: not be used as component at all.  Vmgen does not check these
  867: restrictions, they just result in bugs in your interpreter.
  868: 
  869: @node Register Machines,  , Superinstructions, Input File Format
  870: @section Register Machines
  871: 
  872: If you want to implement a register VM rather than a stack VM with
  873: Vmgen, there are two ways to do it: Directly and through
  874: superinstructions.
  875: 
  876: If you use the direct way, you define instructions that take the
  877: register numbers as immediate arguments, like this:
  878: 
  879: @example
  880: add3 ( #src1 #src2 #dest -- )
  881: reg[dest] = reg[src1]+reg[src2];
  882: @end example
  883: 
  884: If you use superinstructions to define a register VM, you define simple
  885: instructions that use a stack, and then define superinstructions that
  886: have no overall stack effect, like this:
  887: 
  888: @example
  889: loadreg ( #src -- n )
  890: n = reg[src];
  891: 
  892: storereg ( n #dest -- )
  893: reg[dest] = n;
  894: 
  895: adds ( n1 n2 -- n )
  896: n = n1+n2;
  897: 
  898: add3 = loadreg loadreg adds storereg
  899: @end example
  900: 
  901: An advantage of this method is that you see the values and not just the
  902: register numbers in tracing (actually, with an appropriate definition of
  903: @code{printarg_src} (@pxref{VM engine}), you can print the values of the
  904: source registers on entry, but you cannot print the value of the
  905: destination register on exit.  A disadvantage of this method is that
  906: currently you cannot generate superinstructions directly, but only
  907: through generating a sequence of simple instructions (we might change
  908: this in the future if there is demand).
  909: 
  910: Could the register VM support be improved, apart from the issues
  911: mentioned above?  It is hard to see how to do it in a general way,
  912: because there are a number of different designs that different people
  913: mean when they use the term @emph{register machine} in connection with
  914: VM interpreters.  However, if you have ideas or requests in that
  915: direction, please let me know (@pxref{Contact}).
  916: 
  917: @c ********************************************************************
  918: @node Using the generated code, Changes, Input File Format, Top
  919: @chapter Using the generated code
  920: 
  921: The easiest way to create a working VM interpreter with Vmgen is
  922: probably to start with one of the examples, and modify it for your
  923: purposes.  This chapter is just the reference manual for the macros
  924: etc. used by the generated code, the other context expected by the
  925: generated code, and what you can do with the various generated files.
  926: 
  927: @menu
  928: * VM engine::                   Executing VM code
  929: * VM instruction table::        
  930: * VM code generation::          Creating VM code (in the front-end)
  931: * Peephole optimization::       Creating VM superinstructions
  932: * VM disassembler::             for debugging the front end
  933: * VM profiler::                 for finding worthwhile superinstructions
  934: @end menu
  935: 
  936: @c --------------------------------------------------------------------
  937: @node VM engine, VM instruction table, Using the generated code, Using the generated code
  938: @section VM engine
  939: 
  940: The VM engine is the VM interpreter that executes the VM code.  It is
  941: essential for an interpretive system.
  942: 
  943: Vmgen supports two methods of VM instruction dispatch: @emph{threaded
  944: code} (fast, but gcc-specific), and @emph{switch dispatch} (slow, but
  945: portable across C compilers); you can use conditional compilation
  946: (@samp{defined(__GNUC__)}) to choose between these methods, and our
  947: example does so.
  948: 
  949: For both methods, the VM engine is contained in a C-level function.
  950: Vmgen generates most of the contents of the function for you
  951: (@file{@var{name}-vm.i}), but you have to define this function, and
  952: macros and variables used in the engine, and initialize the variables.
  953: In our example the engine function also includes
  954: @file{@var{name}-labels.i} (@pxref{VM instruction table}).
  955: 
  956: The following macros and variables are used in @file{@var{name}-vm.i}:
  957: 
  958: @table @code
  959: 
  960: @item LABEL(@var{inst_name})
  961: This is used just before each VM instruction to provide a jump or
  962: @code{switch} label (the @samp{:} is provided by Vmgen).  For switch
  963: dispatch this should expand to @samp{case @var{label}}; for
  964: threaded-code dispatch this should just expand to @samp{case
  965: @var{label}}.  In either case @var{label} is usually the @var{inst_name}
  966: with some prefix or suffix to avoid naming conflicts.
  967: 
  968: @item LABEL2(@var{inst_name})
  969: This will be used for dynamic superinstructions; at the moment, this
  970: should expand to nothing.
  971: 
  972: @item NAME(@var{inst_name_string})
  973: Called on entering a VM instruction with a string containing the name of
  974: the VM instruction as parameter.  In normal execution this should be a
  975: noop, but for tracing this usually prints the name, and possibly other
  976: information (several VM registers in our example).
  977: 
  978: @item DEF_CA
  979: Usually empty.  Called just inside a new scope at the start of a VM
  980: instruction.  Can be used to define variables that should be visible
  981: during every VM instruction.  If you define this macro as non-empty, you
  982: have to provide the finishing @samp{;} in the macro.
  983: 
  984: @item NEXT_P0 NEXT_P1 NEXT_P2
  985: The three parts of instruction dispatch.  They can be defined in
  986: different ways for best performance on various processors (see
  987: @file{engine.c} in the example or @file{engine/threaded.h} in Gforth).
  988: @samp{NEXT_P0} is invoked right at the start of the VM isntruction (but
  989: after @samp{DEF_CA}), @samp{NEXT_P1} right after the user-supplied C
  990: code, and @samp{NEXT_P2} at the end.  The actual jump has to be
  991: performed by @samp{NEXT_P2}.
  992: 
  993: The simplest variant is if @samp{NEXT_P2} does everything and the other
  994: macros do nothing.  Then also related macros like @samp{IP},
  995: @samp{SET_IP}, @samp{IP}, @samp{INC_IP} and @samp{IPTOS} are very
  996: straightforward to define.  For switch dispatch this code consists just
  997: of a jump to the dispatch code (@samp{goto next_inst;} in our example;
  998: for direct threaded code it consists of something like
  999: @samp{(@{cfa=*ip++; goto *cfa;@})}.
 1000: 
 1001: Pulling code (usually the @samp{cfa=*ip;}) up into @samp{NEXT_P1}
 1002: usually does not cause problems, but pulling things up into
 1003: @samp{NEXT_P0} usually requires changing the other macros (and, at least
 1004: for Gforth on Alpha, it does not buy much, because the compiler often
 1005: manages to schedule the relevant stuff up by itself).  An even more
 1006: extreme variant is to pull code up even further, into, e.g., NEXT_P1 of
 1007: the previous VM instruction (prefetching, useful on PowerPCs).
 1008: 
 1009: @item INC_IP(@var{n})
 1010: This increments @code{IP} by @var{n}.
 1011: 
 1012: @item SET_IP(@var{target})
 1013: This sets @code{IP} to @var{target}.
 1014: 
 1015: @item vm_@var{A}2@var{B}(a,b)
 1016: Type casting macro that assigns @samp{a} (of type @var{A}) to @samp{b}
 1017: (of type @var{B}).  This is mainly used for getting stack items into
 1018: variables and back.  So you need to define macros for every combination
 1019: of stack basic type (@code{Cell} in our example) and type-prefix types
 1020: used with that stack (in both directions).  For the type-prefix type,
 1021: you use the type-prefix (not the C type string) as type name (e.g.,
 1022: @samp{vm_Cell2i}, not @samp{vm_Cell2Cell}).  In addition, you have to
 1023: define a vm_@var{X}2@var{X} macro for the stack basic type (used in
 1024: superinstructions).
 1025: 
 1026: The stack basic type for the predefined @samp{inst-stream} is
 1027: @samp{Cell}.  If you want a stack with the same item size, making its
 1028: basic type @samp{Cell} usually reduces the number of macros you have to
 1029: define.
 1030: 
 1031: Here our examples differ a lot: @file{vmgen-ex} uses casts in these
 1032: macros, whereas @file{vmgen-ex2} uses union-field selection (or
 1033: assignment to union fields).
 1034: 
 1035: @item vm_two@var{A}2@var{B}(a1,a2,b)
 1036: @item vm_@var{B}2two@var{A}(b,a1,a2)
 1037: Conversions between two stack items (@code{a1}, @code{a2}) and a
 1038: variable @code{b} of a type that takes two stack items.  This does not
 1039: occur in our small examples, but you can look at Gforth for examples.
 1040: 
 1041: @item @var{stackpointer}
 1042: For each stack used, the stackpointer name given in the stack
 1043: declaration is used.  For a regular stack this must be an l-expression;
 1044: typically it is a variable declared as a pointer to the stack's basic
 1045: type.  For @samp{inst-stream}, the name is @samp{IP}, and it can be a
 1046: plain r-value; typically it is a macro that abstracts away the
 1047: differences between the various implementations of NEXT_P*.
 1048: 
 1049: @item @var{stackpointer}TOS
 1050: The top-of-stack for the stack pointed to by @var{stackpointer}.  If you
 1051: are using top-of-stack caching for that stack, this should be defined as
 1052: variable; if you are not using top-of-stack caching for that stack, this
 1053: should be a macro expanding to @samp{@var{stackpointer}[0]}.  The stack
 1054: pointer for the predefined @samp{inst-stream} is called @samp{IP}, so
 1055: the top-of-stack is called @samp{IPTOS}.
 1056: 
 1057: @item IF_@var{stackpointer}TOS(@var{expr})
 1058: Macro for executing @var{expr}, if top-of-stack caching is used for the
 1059: @var{stackpointer} stack.  I.e., this should do @var{expr} if there is
 1060: top-of-stack caching for @var{stackpointer}; otherwise it should do
 1061: nothing.
 1062: 
 1063: @item SUPER_END
 1064: This is used by the VM profiler (@pxref{VM profiler}); it should not do
 1065: anything in normal operation, and call @code{vm_count_block(IP)} for
 1066: profiling.
 1067: 
 1068: @item SUPER_CONTINUE
 1069: This is just a hint to Vmgen and does nothing at the C level.
 1070: 
 1071: @item VM_DEBUG
 1072: If this is defined, the tracing code will be compiled in (slower
 1073: interpretation, but better debugging).  Our example compiles two
 1074: versions of the engine, a fast-running one that cannot trace, and one
 1075: with potential tracing and profiling.
 1076: 
 1077: @item vm_debug
 1078: Needed only if @samp{VM_DEBUG} is defined.  If this variable contains
 1079: true, the VM instructions produce trace output.  It can be turned on or
 1080: off at any time.
 1081: 
 1082: @item vm_out
 1083: Needed only if @samp{VM_DEBUG} is defined.  Specifies the file on which
 1084: to print the trace output (type @samp{FILE *}).
 1085: 
 1086: @item printarg_@var{type}(@var{value})
 1087: Needed only if @samp{VM_DEBUG} is defined.  Macro or function for
 1088: printing @var{value} in a way appropriate for the @var{type}.  This is
 1089: used for printing the values of stack items during tracing.  @var{Type}
 1090: is normally the type prefix specified in a @code{type-prefix} definition
 1091: (e.g., @samp{printarg_i}); in superinstructions it is currently the
 1092: basic type of the stack.
 1093: 
 1094: @end table
 1095: 
 1096: 
 1097: @c --------------------------------------------------------------------
 1098: @node VM instruction table, VM code generation, VM engine, Using the generated code
 1099: @section VM instruction table
 1100: 
 1101: For threaded code we also need to produce a table containing the labels
 1102: of all VM instructions.  This is needed for VM code generation
 1103: (@pxref{VM code generation}), and it has to be done in the engine
 1104: function, because the labels are not visible outside.  It then has to be
 1105: passed outside the function (and assigned to @samp{vm_prim}), to be used
 1106: by the VM code generation functions.
 1107: 
 1108: This means that the engine function has to be called first to produce
 1109: the VM instruction table, and later, after generating VM code, it has to
 1110: be called again to execute the generated VM code (yes, this is ugly).
 1111: In our example program, these two modes of calling the engine function
 1112: are differentiated by the value of the parameter ip0 (if it equals 0,
 1113: then the table is passed out, otherwise the VM code is executed); in our
 1114: example, we pass the table out by assigning it to @samp{vm_prim} and
 1115: returning from @samp{engine}.
 1116: 
 1117: In our example, we also build such a table for switch dispatch; this is
 1118: mainly done for uniformity.
 1119: 
 1120: For switch dispatch, we also need to define the VM instruction opcodes
 1121: used as case labels in an @code{enum}.
 1122: 
 1123: For both purposes (VM instruction table, and enum), the file
 1124: @file{@var{name}-labels.i} is generated by Vmgen.  You have to define
 1125: the following macro used in this file:
 1126: 
 1127: @table @samp
 1128: 
 1129: @item INST_ADDR(@var{inst_name})
 1130: For switch dispatch, this is just the name of the switch label (the same
 1131: name as used in @samp{LABEL(@var{inst_name})}), for both uses of
 1132: @file{@var{name}-labels.i}.  For threaded-code dispatch, this is the
 1133: address of the label defined in @samp{LABEL(@var{inst_name})}); the
 1134: address is taken with @samp{&&} (@pxref{Labels as Values, , Labels as
 1135: Values, gcc.info, GNU C Manual}).
 1136: 
 1137: @end table
 1138: 
 1139: 
 1140: @c --------------------------------------------------------------------
 1141: @node VM code generation, Peephole optimization, VM instruction table, Using the generated code
 1142: @section VM code generation
 1143: 
 1144: Vmgen generates VM code generation functions in @file{@var{name}-gen.i}
 1145: that the front end can call to generate VM code.  This is essential for
 1146: an interpretive system.
 1147: 
 1148: For a VM instruction @samp{x ( #a b #c -- d )}, Vmgen generates a
 1149: function with the prototype
 1150: 
 1151: @example
 1152: void gen_x(Inst **ctp, a_type a, c_type c)
 1153: @end example
 1154: 
 1155: The @code{ctp} argument points to a pointer to the next instruction.
 1156: @code{*ctp} is increased by the generation functions; i.e., you should
 1157: allocate memory for the code to be generated beforehand, and start with
 1158: *ctp set at the start of this memory area.  Before running out of
 1159: memory, allocate a new area, and generate a VM-level jump to the new
 1160: area (this is not implemented in our examples).
 1161: 
 1162: The other arguments correspond to the immediate arguments of the VM
 1163: instruction (with their appropriate types as defined in the
 1164: @code{type_prefix} declaration.
 1165: 
 1166: The following types, variables, and functions are used in
 1167: @file{@var{name}-gen.i}:
 1168: 
 1169: @table @samp
 1170: 
 1171: @item Inst
 1172: The type of the VM instruction; if you use threaded code, this is
 1173: @code{void *}; for switch dispatch this is an integer type.
 1174: 
 1175: @item vm_prim
 1176: The VM instruction table (type: @code{Inst *}, @pxref{VM instruction table}).
 1177: 
 1178: @item gen_inst(Inst **ctp, Inst i)
 1179: This function compiles the instruction @code{i}.  Take a look at it in
 1180: @file{vmgen-ex/peephole.c}.  It is trivial when you don't want to use
 1181: superinstructions (just the last two lines of the example function), and
 1182: slightly more complicated in the example due to its ability to use
 1183: superinstructions (@pxref{Peephole optimization}).
 1184: 
 1185: @item genarg_@var{type_prefix}(Inst **ctp, @var{type} @var{type_prefix})
 1186: This compiles an immediate argument of @var{type} (as defined in a
 1187: @code{type-prefix} definition).  These functions are trivial to define
 1188: (see @file{vmgen-ex/support.c}).  You need one of these functions for
 1189: every type that you use as immediate argument.
 1190: 
 1191: @end table
 1192: 
 1193: In addition to using these functions to generate code, you should call
 1194: @code{BB_BOUNDARY} at every basic block entry point if you ever want to
 1195: use superinstructions (or if you want to use the profiling supported by
 1196: Vmgen; however, this is mainly useful for selecting superinstructions).
 1197: If you use @code{BB_BOUNDARY}, you should also define it (take a look at
 1198: its definition in @file{vmgen-ex/mini.y}).
 1199: 
 1200: You do not need to call @code{BB_BOUNDARY} after branches, because you
 1201: will not define superinstructions that contain branches in the middle
 1202: (and if you did, and it would work, there would be no reason to end the
 1203: superinstruction at the branch), and because the branches announce
 1204: themselves to the profiler.
 1205: 
 1206: 
 1207: @c --------------------------------------------------------------------
 1208: @node Peephole optimization, VM disassembler, VM code generation, Using the generated code
 1209: @section Peephole optimization
 1210: 
 1211: You need peephole optimization only if you want to use
 1212: superinstructions.  But having the code for it does not hurt much if you
 1213: do not use superinstructions.
 1214: 
 1215: A simple greedy peephole optimization algorithm is used for
 1216: superinstruction selection: every time @code{gen_inst} compiles a VM
 1217: instruction, it looks if it can combine it with the last VM instruction
 1218: (which may also be a superinstruction resulting from a previous peephole
 1219: optimization); if so, it changes the last instruction to the combined
 1220: instruction instead of laying down @code{i} at the current @samp{*ctp}.
 1221: 
 1222: The code for peephole optimization is in @file{vmgen-ex/peephole.c}.
 1223: You can use this file almost verbatim.  Vmgen generates
 1224: @file{@var{file}-peephole.i} which contains data for the peephoile
 1225: optimizer.
 1226: 
 1227: You have to call @samp{init_peeptable()} after initializing
 1228: @samp{vm_prim}, and before compiling any VM code to initialize data
 1229: structures for peephole optimization.  After that, compiling with the VM
 1230: code generation functions will automatically combine VM instructions
 1231: into superinstructions.  Since you do not want to combine instructions
 1232: across VM branch targets (otherwise there will not be a proper VM
 1233: instruction to branch to), you have to call @code{BB_BOUNDARY}
 1234: (@pxref{VM code generation}) at branch targets.
 1235: 
 1236: 
 1237: @c --------------------------------------------------------------------
 1238: @node VM disassembler, VM profiler, Peephole optimization, Using the generated code
 1239: @section VM disassembler
 1240: 
 1241: A VM code disassembler is optional for an interpretive system, but
 1242: highly recommended during its development and maintenance, because it is
 1243: very useful for detecting bugs in the front end (and for distinguishing
 1244: them from VM interpreter bugs).
 1245: 
 1246: Vmgen supports VM code disassembling by generating
 1247: @file{@var{file}-disasm.i}.  This code has to be wrapped into a
 1248: function, as is done in @file{vmgen-ex/disasm.i}.  You can use this file
 1249: almost verbatim.  In addition to @samp{vm_@var{A}2@var{B}(a,b)},
 1250: @samp{vm_out}, @samp{printarg_@var{type}(@var{value})}, which are
 1251: explained above, the following macros and variables are used in
 1252: @file{@var{file}-disasm.i} (and you have to define them):
 1253: 
 1254: @table @samp
 1255: 
 1256: @item ip
 1257: This variable points to the opcode of the current VM instruction.
 1258: 
 1259: @item IP IPTOS
 1260: @samp{IPTOS} is the first argument of the current VM instruction, and
 1261: @samp{IP} points to it; this is just as in the engine, but here
 1262: @samp{ip} points to the opcode of the VM instruction (in contrast to the
 1263: engine, where @samp{ip} points to the next cell, or even one further).
 1264: 
 1265: @item VM_IS_INST(Inst i, int n)
 1266: Tests if the opcode @samp{i} is the same as the @samp{n}th entry in the
 1267: VM instruction table.
 1268: 
 1269: @end table
 1270: 
 1271: 
 1272: @c --------------------------------------------------------------------
 1273: @node VM profiler,  , VM disassembler, Using the generated code
 1274: @section VM profiler
 1275: 
 1276: The VM profiler is designed for getting execution and occurence counts
 1277: for VM instruction sequences, and these counts can then be used for
 1278: selecting sequences as superinstructions.  The VM profiler is probably
 1279: not useful as profiling tool for the interpretive system.  I.e., the VM
 1280: profiler is useful for the developers, but not the users of the
 1281: interpretive system.
 1282: 
 1283: The output of the profiler is: for each basic block (executed at least
 1284: once), it produces the dynamic execution count of that basic block and
 1285: all its subsequences; e.g.,
 1286: 
 1287: @example
 1288:        9227465  lit storelocal 
 1289:        9227465  storelocal branch 
 1290:        9227465  lit storelocal branch 
 1291: @end example
 1292: 
 1293: I.e., a basic block consisting of @samp{lit storelocal branch} is
 1294: executed 9227465 times.
 1295: 
 1296: This output can be combined in various ways.  E.g.,
 1297: @file{vmgen/stat.awk} adds up the occurences of a given sequence wrt
 1298: dynamic execution, static occurence, and per-program occurence.  E.g.,
 1299: 
 1300: @example
 1301:       2      16        36910041 loadlocal lit 
 1302: @end example
 1303: 
 1304: indicates that the sequence @samp{loadlocal lit} occurs in 2 programs,
 1305: in 16 places, and has been executed 36910041 times.  Now you can select
 1306: superinstructions in any way you like (note that compile time and space
 1307: typically limit the number of superinstructions to 100--1000).  After
 1308: you have done that, @file{vmgen/seq2rule.awk} turns lines of the form
 1309: above into rules for inclusion in a Vmgen input file.  Note that this
 1310: script does not ensure that all prefixes are defined, so you have to do
 1311: that in other ways.  So, an overall script for turning profiles into
 1312: superinstructions can look like this:
 1313: 
 1314: @example
 1315: awk -f stat.awk fib.prof test.prof|
 1316: awk '$3>=10000'|                #select sequences
 1317: fgrep -v -f peephole-blacklist| #eliminate wrong instructions
 1318: awk -f seq2rule.awk|            #turn into superinstructions
 1319: sort -k 3 >mini-super.vmg       #sort sequences
 1320: @end example
 1321: 
 1322: Here the dynamic count is used for selecting sequences (preliminary
 1323: results indicate that the static count gives better results, though);
 1324: the third line eliminats sequences containing instructions that must not
 1325: occur in a superinstruction, because they access a stack directly.  The
 1326: dynamic count selection ensures that all subsequences (including
 1327: prefixes) of longer sequences occur (because subsequences have at least
 1328: the same count as the longer sequences); the sort in the last line
 1329: ensures that longer superinstructions occur after their prefixes.
 1330: 
 1331: But before using it, you have to have the profiler.  Vmgen supports its
 1332: creation by generating @file{@var{file}-profile.i}; you also need the
 1333: wrapper file @file{vmgen-ex/profile.c} that you can use almost verbatim.
 1334: 
 1335: The profiler works by recording the targets of all VM control flow
 1336: changes (through @code{SUPER_END} during execution, and through
 1337: @code{BB_BOUNDARY} in the front end), and counting (through
 1338: @code{SUPER_END}) how often they were targeted.  After the program run,
 1339: the numbers are corrected such that each VM basic block has the correct
 1340: count (originally entering a block without executing a branch does not
 1341: increase the count), then the subsequences of all basic blocks are
 1342: printed.  To get all this, you just have to define @code{SUPER_END} (and
 1343: @code{BB_BOUNDARY}) appropriately, and call @code{vm_print_profile(FILE
 1344: *file)} when you want to output the profile on @code{file}.
 1345: 
 1346: The @file{@var{file}-profile.i} is simular to the disassembler file, and
 1347: it uses variables and functions defined in @file{vmgen-ex/profile.c},
 1348: plus @code{VM_IS_INST} already defined for the VM disassembler
 1349: (@pxref{VM disassembler}).
 1350: 
 1351: 
 1352: @c **********************************************************
 1353: @node Changes, Contact, Using the generated code, Top
 1354: @chapter Changes
 1355: 
 1356: Users of the gforth-0.5.9-20010501 version of Vmgen need to change
 1357: several things in their source code to use the current version.  I
 1358: recommend keeping the gforth-0.5.9-20010501 version until you have
 1359: completed the change (note that you can have several versions of Gforth
 1360: installed at the same time).  I hope to avoid such incompatible changes
 1361: in the future.
 1362: 
 1363: The required changes are:
 1364: 
 1365: @table @code
 1366: 
 1367: @item vm_@var{A}2@var{B}
 1368: now takes two arguments.
 1369: 
 1370: @item vm_two@var{A}2@var{B}(b,a1,a2);
 1371: changed to vm_two@var{A}2@var{B}(a1,a2,b) (note the absence of the @samp{;}).
 1372: 
 1373: @end table
 1374: 
 1375: Also some new macros have to be defined, e.g., @code{INST_ADDR}, and
 1376: @code{LABEL}; some macros have to be defined in new contexts, e.g.,
 1377: @code{VM_IS_INST} is now also needed in the disassembler.
 1378: 
 1379: @node Contact, Copying This Manual, Changes, Top
 1380: @chapter Contact
 1381: 
 1382: @node Copying This Manual, Index, Contact, Top
 1383: @appendix Copying This Manual
 1384: 
 1385: @menu
 1386: * GNU Free Documentation License::  License for copying this manual.
 1387: @end menu
 1388: 
 1389: @include fdl.texi
 1390: 
 1391: 
 1392: @node Index,  , Copying This Manual, Top
 1393: @unnumbered Index
 1394: 
 1395: @printindex cp
 1396: 
 1397: @bye

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