File:  [gforth] / gforth / doc / vmgen.texi
Revision 1.26: download - view: text, annotated - select for diffs
Mon Aug 25 08:02:58 2003 UTC (20 years, 7 months ago) by anton
Branches: MAIN
CVS tags: v0-6-2, HEAD
gforth-prof is no longer generated by default
turned off dynamic-default for hppa
minor changes to make testdist work
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, 03,2003 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 Software development
   31: @direntry
   32: * Vmgen: (vmgen).               Virtual machine 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: * Error messages::              reported by Vmgen
   61: * Using the generated code::    
   62: * Hints::                       VM archictecture, efficiency
   63: * The future::                  
   64: * Changes::                     from earlier versions
   65: * Contact::                     Bug reporting etc.
   66: * Copying This Manual::         Manual License
   67: * Index::                       
   68: 
   69: @detailmenu
   70:  --- The Detailed Node Listing ---
   71: 
   72: Concepts
   73: 
   74: * Front end and VM interpreter::  Modularizing an interpretive system
   75: * Data handling::               Stacks, registers, immediate arguments
   76: * Dispatch::                    From one VM instruction to the next
   77: 
   78: Example
   79: 
   80: * Example overview::            
   81: * Using profiling to create superinstructions::  
   82: 
   83: Input File Format
   84: 
   85: * Input File Grammar::          
   86: * Simple instructions::         
   87: * Superinstructions::           
   88: * Store Optimization::          
   89: * Register Machines::           How to define register VM instructions
   90: 
   91: Input File Grammar
   92: 
   93: * Eval escapes::                what follows \E
   94: 
   95: Simple instructions
   96: 
   97: * C Code Macros::               Macros recognized by Vmgen
   98: * C Code restrictions::         Vmgen makes assumptions about C code
   99: * Stack growth direction::      is configurable per stack
  100: 
  101: Using the generated code
  102: 
  103: * VM engine::                   Executing VM code
  104: * VM instruction table::        
  105: * VM code generation::          Creating VM code (in the front-end)
  106: * Peephole optimization::       Creating VM superinstructions
  107: * VM disassembler::             for debugging the front end
  108: * VM profiler::                 for finding worthwhile superinstructions
  109: 
  110: Hints
  111: 
  112: * Floating point::              and stacks
  113: 
  114: Copying This Manual
  115: 
  116: * GNU Free Documentation License::  License for copying this manual.
  117: 
  118: @end detailmenu
  119: @end menu
  120: 
  121: @c @ifnottex
  122: @c This file documents Vmgen (Gforth @value{VERSION}).
  123: 
  124: @c ************************************************************
  125: @node Introduction, Why interpreters?, Top, Top
  126: @chapter Introduction
  127: 
  128: Vmgen is a tool for writing efficient interpreters.  It takes a simple
  129: virtual machine description and generates efficient C code for dealing
  130: with the virtual machine code in various ways (in particular, executing
  131: it).  The run-time efficiency of the resulting interpreters is usually
  132: within a factor of 10 of machine code produced by an optimizing
  133: compiler.
  134: 
  135: The interpreter design strategy supported by Vmgen is to divide the
  136: interpreter into two parts:
  137: 
  138: @itemize @bullet
  139: 
  140: @item The @emph{front end} takes the source code of the language to be
  141: implemented, and translates it into virtual machine code.  This is
  142: similar to an ordinary compiler front end; typically an interpreter
  143: front-end performs no optimization, so it is relatively simple to
  144: implement and runs fast.
  145: 
  146: @item The @emph{virtual machine interpreter} executes the virtual
  147: machine code.
  148: 
  149: @end itemize
  150: 
  151: Such a division is usually used in interpreters, for modularity as well
  152: as for efficiency.  The virtual machine code is typically passed between
  153: front end and virtual machine interpreter in memory, like in a
  154: load-and-go compiler; this avoids the complexity and time cost of
  155: writing the code to a file and reading it again.
  156: 
  157: A @emph{virtual machine} (VM) represents the program as a sequence of
  158: @emph{VM instructions}, following each other in memory, similar to real
  159: machine code.  Control flow occurs through VM branch instructions, like
  160: in a real machine.
  161: 
  162: @cindex functionality features overview
  163: In this setup, Vmgen can generate most of the code dealing with virtual
  164: machine instructions from a simple description of the virtual machine
  165: instructions (@pxref{Input File Format}), in particular:
  166: 
  167: @table @strong
  168: 
  169: @item VM instruction execution
  170: 
  171: @item VM code generation
  172: Useful in the front end.
  173: 
  174: @item VM code decompiler
  175: Useful for debugging the front end.
  176: 
  177: @item VM code tracing
  178: Useful for debugging the front end and the VM interpreter.  You will
  179: typically provide other means for debugging the user's programs at the
  180: source level.
  181: 
  182: @item VM code profiling
  183: Useful for optimizing the VM interpreter with superinstructions
  184: (@pxref{VM profiler}).
  185: 
  186: @end table
  187: 
  188: To create parts of the interpretive system that do not deal with VM
  189: instructions, you have to use other tools (e.g., @command{bison}) and/or
  190: hand-code them.
  191: 
  192: @cindex efficiency features overview
  193: @noindent
  194: Vmgen supports efficient interpreters though various optimizations, in
  195: particular
  196: 
  197: @itemize @bullet
  198: 
  199: @item Threaded code
  200: 
  201: @item Caching the top-of-stack in a register
  202: 
  203: @item Combining VM instructions into superinstructions
  204: 
  205: @item
  206: Replicating VM (super)instructions for better BTB prediction accuracy
  207: (not yet in vmgen-ex, but already in Gforth).
  208: 
  209: @end itemize
  210: 
  211: @cindex speed for JVM
  212: As a result, Vmgen-based interpreters are only about an order of
  213: magnitude slower than native code from an optimizing C compiler on small
  214: benchmarks; on large benchmarks, which spend more time in the run-time
  215: system, the slowdown is often less (e.g., the slowdown of a
  216: Vmgen-generated JVM interpreter over the best JVM JIT compiler we
  217: measured is only a factor of 2-3 for large benchmarks; some other JITs
  218: and all other interpreters we looked at were slower than our
  219: interpreter).
  220: 
  221: VMs are usually designed as stack machines (passing data between VM
  222: instructions on a stack), and Vmgen supports such designs especially
  223: well; however, you can also use Vmgen for implementing a register VM
  224: (@pxref{Register Machines}) and still benefit from most of the advantages
  225: offered by Vmgen.
  226: 
  227: There are many potential uses of the instruction descriptions that are
  228: not implemented at the moment, but we are open for feature requests, and
  229: we will consider new features if someone asks for them; so the feature
  230: list above is not exhaustive.
  231: 
  232: @c *********************************************************************
  233: @node Why interpreters?, Concepts, Introduction, Top
  234: @chapter Why interpreters?
  235: @cindex interpreters, advantages
  236: @cindex advantages of interpreters
  237: @cindex advantages of vmgen
  238: 
  239: Interpreters are a popular language implementation technique because
  240: they combine all three of the following advantages:
  241: 
  242: @itemize @bullet
  243: 
  244: @item Ease of implementation
  245: 
  246: @item Portability
  247: 
  248: @item Fast edit-compile-run cycle
  249: 
  250: @end itemize
  251: 
  252: Vmgen makes it even easier to implement interpreters.
  253: 
  254: @cindex speed of interpreters
  255: The main disadvantage of interpreters is their run-time speed.  However,
  256: there are huge differences between different interpreters in this area:
  257: the slowdown over optimized C code on programs consisting of simple
  258: operations is typically a factor of 10 for the more efficient
  259: interpreters, and a factor of 1000 for the less efficient ones (the
  260: slowdown for programs executing complex operations is less, because the
  261: time spent in libraries for executing complex operations is the same in
  262: all implementation strategies).
  263: 
  264: Vmgen supports techniques for building efficient interpreters.
  265: 
  266: @c ********************************************************************
  267: @node Concepts, Invoking Vmgen, Why interpreters?, Top
  268: @chapter Concepts
  269: 
  270: @menu
  271: * Front end and VM interpreter::  Modularizing an interpretive system
  272: * Data handling::               Stacks, registers, immediate arguments
  273: * Dispatch::                    From one VM instruction to the next
  274: @end menu
  275: 
  276: @c --------------------------------------------------------------------
  277: @node Front end and VM interpreter, Data handling, Concepts, Concepts
  278: @section Front end and VM interpreter
  279: @cindex modularization of interpreters
  280: 
  281: @cindex front-end
  282: Interpretive systems are typically divided into a @emph{front end} that
  283: parses the input language and produces an intermediate representation
  284: for the program, and an interpreter that executes the intermediate
  285: representation of the program.
  286: 
  287: @cindex virtual machine
  288: @cindex VM
  289: @cindex VM instruction
  290: @cindex instruction, VM
  291: @cindex VM branch instruction
  292: @cindex branch instruction, VM
  293: @cindex VM register
  294: @cindex register, VM
  295: @cindex opcode, VM instruction
  296: @cindex immediate argument, VM instruction
  297: For efficient interpreters the intermediate representation of choice is
  298: virtual machine code (rather than, e.g., an abstract syntax tree).
  299: @emph{Virtual machine} (VM) code consists of VM instructions arranged
  300: sequentially in memory; they are executed in sequence by the VM
  301: interpreter, but VM branch instructions can change the control flow and
  302: are used for implementing control structures.  The conceptual similarity
  303: to real machine code results in the name @emph{virtual machine}.
  304: Various terms similar to terms for real machines are used; e.g., there
  305: are @emph{VM registers} (like the instruction pointer and stack
  306: pointer(s)), and the VM instruction consists of an @emph{opcode} and
  307: @emph{immediate arguments}.
  308: 
  309: In this framework, Vmgen supports building the VM interpreter and any
  310: other component dealing with VM instructions.  It does not have any
  311: support for the front end, apart from VM code generation support.  The
  312: front end can be implemented with classical compiler front-end
  313: techniques, supported by tools like @command{flex} and @command{bison}.
  314: 
  315: The intermediate representation is usually just internal to the
  316: interpreter, but some systems also support saving it to a file, either
  317: as an image file, or in a full-blown linkable file format (e.g., JVM).
  318: Vmgen currently has no special support for such features, but the
  319: information in the instruction descriptions can be helpful, and we are
  320: open to feature requests and suggestions.
  321: 
  322: @c --------------------------------------------------------------------
  323: @node Data handling, Dispatch, Front end and VM interpreter, Concepts
  324: @section Data handling
  325: 
  326: @cindex stack machine
  327: @cindex register machine
  328: Most VMs use one or more stacks for passing temporary data between VM
  329: instructions.  Another option is to use a register machine architecture
  330: for the virtual machine; we believe that using a stack architecture is
  331: usually both simpler and faster.
  332: 
  333: however, this option is slower or
  334: significantly more complex to implement than a stack machine architecture.
  335: 
  336: Vmgen has special support and optimizations for stack VMs, making their
  337: implementation easy and efficient.
  338: 
  339: You can also implement a register VM with Vmgen (@pxref{Register
  340: Machines}), and you will still profit from most Vmgen features.
  341: 
  342: @cindex stack item size
  343: @cindex size, stack items
  344: Stack items all have the same size, so they typically will be as wide as
  345: an integer, pointer, or floating-point value.  Vmgen supports treating
  346: two consecutive stack items as a single value, but anything larger is
  347: best kept in some other memory area (e.g., the heap), with pointers to
  348: the data on the stack.
  349: 
  350: @cindex instruction stream
  351: @cindex immediate arguments
  352: Another source of data is immediate arguments VM instructions (in the VM
  353: instruction stream).  The VM instruction stream is handled similar to a
  354: stack in Vmgen.
  355: 
  356: @cindex garbage collection
  357: @cindex reference counting
  358: Vmgen has no built-in support for, nor restrictions against
  359: @emph{garbage collection}.  If you need garbage collection, you need to
  360: provide it in your run-time libraries.  Using @emph{reference counting}
  361: is probably harder, but might be possible (contact us if you are
  362: interested).
  363: @c reference counting might be possible by including counting code in 
  364: @c the conversion macros.
  365: 
  366: @c --------------------------------------------------------------------
  367: @node Dispatch,  , Data handling, Concepts
  368: @section Dispatch
  369: @cindex Dispatch of VM instructions
  370: @cindex main interpreter loop
  371: 
  372: Understanding this section is probably not necessary for using Vmgen,
  373: but it may help.  You may want to skip it now, and read it if you find statements about dispatch methods confusing.
  374: 
  375: After executing one VM instruction, the VM interpreter has to dispatch
  376: the next VM instruction (Vmgen calls the dispatch routine @samp{NEXT}).
  377: Vmgen supports two methods of dispatch:
  378: 
  379: @table @strong
  380: 
  381: @item switch dispatch
  382: @cindex switch dispatch
  383: In this method the VM interpreter contains a giant @code{switch}
  384: statement, with one @code{case} for each VM instruction.  The VM
  385: instruction opcodes are represented by integers (e.g., produced by an
  386: @code{enum}) in the VM code, and dispatch occurs by loading the next
  387: opcode, @code{switch}ing on it, and continuing at the appropriate
  388: @code{case}; after executing the VM instruction, the VM interpreter
  389: jumps back to the dispatch code.
  390: 
  391: @item threaded code
  392: @cindex threaded code
  393: This method represents a VM instruction opcode by the address of the
  394: start of the machine code fragment for executing the VM instruction.
  395: Dispatch consists of loading this address, jumping to it, and
  396: incrementing the VM instruction pointer.  Typically the threaded-code
  397: dispatch code is appended directly to the code for executing the VM
  398: instruction.  Threaded code cannot be implemented in ANSI C, but it can
  399: be implemented using GNU C's labels-as-values extension (@pxref{Labels
  400: as Values, , Labels as Values, gcc.info, GNU C Manual}).
  401: 
  402: @c call threading
  403: @end table
  404: 
  405: Threaded code can be twice as fast as switch dispatch, depending on the
  406: interpreter, the benchmark, and the machine.
  407: 
  408: @c *************************************************************
  409: @node Invoking Vmgen, Example, Concepts, Top
  410: @chapter Invoking Vmgen
  411: @cindex Invoking Vmgen
  412: 
  413: The usual way to invoke Vmgen is as follows:
  414: 
  415: @example
  416: vmgen @var{inputfile}
  417: @end example
  418: 
  419: Here @var{inputfile} is the VM instruction description file, which
  420: usually ends in @file{.vmg}.  The output filenames are made by taking
  421: the basename of @file{inputfile} (i.e., the output files will be created
  422: in the current working directory) and replacing @file{.vmg} with
  423: @file{-vm.i}, @file{-disasm.i}, @file{-gen.i}, @file{-labels.i},
  424: @file{-profile.i}, and @file{-peephole.i}.  E.g., @command{vmgen
  425: hack/foo.vmg} will create @file{foo-vm.i}, @file{foo-disasm.i},
  426: @file{foo-gen.i}, @file{foo-labels.i}, @file{foo-profile.i} and
  427: @file{foo-peephole.i}.
  428: 
  429: The command-line options supported by Vmgen are
  430: 
  431: @table @option
  432: 
  433: @cindex -h, command-line option
  434: @cindex --help, command-line option
  435: @item --help
  436: @itemx -h
  437: Print a message about the command-line options
  438: 
  439: @cindex -v, command-line option
  440: @cindex --version, command-line option
  441: @item --version
  442: @itemx -v
  443: Print version and exit
  444: @end table
  445: 
  446: @c env vars GFORTHDIR GFORTHDATADIR
  447: 
  448: @c ****************************************************************
  449: @node Example, Input File Format, Invoking Vmgen, Top
  450: @chapter Example
  451: @cindex example of a Vmgen-based interpreter
  452: 
  453: @menu
  454: * Example overview::            
  455: * Using profiling to create superinstructions::  
  456: @end menu
  457: 
  458: @c --------------------------------------------------------------------
  459: @node Example overview, Using profiling to create superinstructions, Example, Example
  460: @section Example overview
  461: @cindex example overview
  462: @cindex @file{vmgen-ex}
  463: @cindex @file{vmgen-ex2}
  464: 
  465: There are two versions of the same example for using Vmgen:
  466: @file{vmgen-ex} and @file{vmgen-ex2} (you can also see Gforth as
  467: example, but it uses additional (undocumented) features, and also
  468: differs in some other respects).  The example implements @emph{mini}, a
  469: tiny Modula-2-like language with a small JavaVM-like virtual machine.
  470: 
  471: The difference between the examples is that @file{vmgen-ex} uses many
  472: casts, and @file{vmgen-ex2} tries to avoids most casts and uses unions
  473: instead.  In the rest of this manual we usually mention just files in
  474: @file{vmgen-ex}; if you want to use unions, use the equivalent file in
  475: @file{vmgen-ex2}.
  476: @cindex unions example
  477: @cindex casts example
  478: 
  479: The files provided with each example are:
  480: @cindex example files
  481: 
  482: @example
  483: Makefile
  484: README
  485: disasm.c           wrapper file
  486: engine.c           wrapper file
  487: peephole.c         wrapper file
  488: profile.c          wrapper file
  489: mini-inst.vmg      simple VM instructions
  490: mini-super.vmg     superinstructions (empty at first)
  491: mini.h             common declarations
  492: mini.l             scanner
  493: mini.y             front end (parser, VM code generator)
  494: support.c          main() and other support functions
  495: fib.mini           example mini program
  496: simple.mini        example mini program
  497: test.mini          example mini program (tests everything)
  498: test.out           test.mini output
  499: stat.awk           script for aggregating profile information
  500: peephole-blacklist list of instructions not allowed in superinstructions
  501: seq2rule.awk       script for creating superinstructions
  502: @end example
  503: 
  504: For your own interpreter, you would typically copy the following files
  505: and change little, if anything:
  506: @cindex wrapper files
  507: 
  508: @example
  509: disasm.c           wrapper file
  510: engine.c           wrapper file
  511: peephole.c         wrapper file
  512: profile.c          wrapper file
  513: stat.awk           script for aggregating profile information
  514: seq2rule.awk       script for creating superinstructions
  515: @end example
  516: 
  517: @noindent
  518: You would typically change much in or replace the following files:
  519: 
  520: @example
  521: Makefile
  522: mini-inst.vmg      simple VM instructions
  523: mini.h             common declarations
  524: mini.l             scanner
  525: mini.y             front end (parser, VM code generator)
  526: support.c          main() and other support functions
  527: peephole-blacklist list of instructions not allowed in superinstructions
  528: @end example
  529: 
  530: You can build the example by @code{cd}ing into the example's directory,
  531: and then typing @code{make}; you can check that it works with @code{make
  532: check}.  You can run run mini programs like this:
  533: 
  534: @example
  535: ./mini fib.mini
  536: @end example
  537: 
  538: To learn about the options, type @code{./mini -h}.
  539: 
  540: @c --------------------------------------------------------------------
  541: @node Using profiling to create superinstructions,  , Example overview, Example
  542: @section Using profiling to create superinstructions
  543: @cindex profiling example
  544: @cindex superinstructions example
  545: 
  546: I have not added rules for this in the @file{Makefile} (there are many
  547: options for selecting superinstructions, and I did not want to hardcode
  548: one into the @file{Makefile}), but there are some supporting scripts, and
  549: here's an example:
  550: 
  551: Suppose you want to use @file{fib.mini} and @file{test.mini} as training
  552: programs, you get the profiles like this:
  553: 
  554: @example
  555: make fib.prof test.prof #takes a few seconds
  556: @end example
  557: 
  558: You can aggregate these profiles with @file{stat.awk}:
  559: 
  560: @example
  561: awk -f stat.awk fib.prof test.prof
  562: @end example
  563: 
  564: The result contains lines like:
  565: 
  566: @example
  567:       2      16        36910041 loadlocal lit
  568: @end example
  569: 
  570: This means that the sequence @code{loadlocal lit} statically occurs a
  571: total of 16 times in 2 profiles, with a dynamic execution count of
  572: 36910041.
  573: 
  574: The numbers can be used in various ways to select superinstructions.
  575: E.g., if you just want to select all sequences with a dynamic
  576: execution count exceeding 10000, you would use the following pipeline:
  577: 
  578: @example
  579: awk -f stat.awk fib.prof test.prof|
  580: awk '$3>=10000'|                #select sequences
  581: fgrep -v -f peephole-blacklist| #eliminate wrong instructions
  582: awk -f seq2rule.awk|  #transform sequences into superinstruction rules
  583: sort -k 3 >mini-super.vmg       #sort sequences
  584: @end example
  585: 
  586: The file @file{peephole-blacklist} contains all instructions that
  587: directly access a stack or stack pointer (for mini: @code{call},
  588: @code{return}); the sort step is necessary to ensure that prefixes
  589: precede larger superinstructions.
  590: 
  591: Now you can create a version of mini with superinstructions by just
  592: saying @samp{make}
  593: 
  594: 
  595: @c ***************************************************************
  596: @node Input File Format, Error messages, Example, Top
  597: @chapter Input File Format
  598: @cindex input file format
  599: @cindex format, input file
  600: 
  601: Vmgen takes as input a file containing specifications of virtual machine
  602: instructions.  This file usually has a name ending in @file{.vmg}.
  603: 
  604: Most examples are taken from the example in @file{vmgen-ex}.
  605: 
  606: @menu
  607: * Input File Grammar::          
  608: * Simple instructions::         
  609: * Superinstructions::           
  610: * Store Optimization::          
  611: * Register Machines::           How to define register VM instructions
  612: @end menu
  613: 
  614: @c --------------------------------------------------------------------
  615: @node Input File Grammar, Simple instructions, Input File Format, Input File Format
  616: @section Input File Grammar
  617: @cindex grammar, input file
  618: @cindex input file grammar
  619: 
  620: The grammar is in EBNF format, with @code{@var{a}|@var{b}} meaning
  621: ``@var{a} or @var{b}'', @code{@{@var{c}@}} meaning 0 or more repetitions
  622: of @var{c} and @code{[@var{d}]} meaning 0 or 1 repetitions of @var{d}.
  623: 
  624: @cindex free-format, not
  625: @cindex newlines, significance in syntax
  626: Vmgen input is not free-format, so you have to take care where you put
  627: newlines (and, in a few cases, white space).
  628: 
  629: @example
  630: description: @{instruction|comment|eval-escape|c-escape@}
  631: 
  632: instruction: simple-inst|superinst
  633: 
  634: simple-inst: ident '(' stack-effect ')' newline c-code newline newline
  635: 
  636: stack-effect: @{ident@} '--' @{ident@}
  637: 
  638: super-inst: ident '=' ident @{ident@}  
  639: 
  640: comment:      '\ '  text newline
  641: 
  642: eval-escape:  '\E ' text newline
  643: 
  644: c-escape:     '\C ' text newline
  645: @end example
  646: @c \+ \- \g \f \c
  647: 
  648: Note that the @code{\}s in this grammar are meant literally, not as
  649: C-style encodings for non-printable characters.
  650: 
  651: There are two ways to delimit the C code in @code{simple-inst}:
  652: 
  653: @itemize @bullet
  654: 
  655: @item
  656: If you start it with a @samp{@{} at the start of a line (i.e., not even
  657: white space before it), you have to end it with a @samp{@}} at the start
  658: of a line (followed by a newline).  In this case you may have empty
  659: lines within the C code (typically used between variable definitions and
  660: statements).
  661: 
  662: @item
  663: You do not start it with @samp{@{}.  Then the C code ends at the first
  664: empty line, so you cannot have empty lines within this code.
  665: 
  666: @end itemize
  667: 
  668: The text in @code{comment}, @code{eval-escape} and @code{c-escape} must
  669: not contain a newline.  @code{Ident} must conform to the usual
  670: conventions of C identifiers (otherwise the C compiler would choke on
  671: the Vmgen output), except that idents in @code{stack-effect} may have a
  672: stack prefix (for stack prefix syntax, @pxref{Eval escapes}).
  673: 
  674: @cindex C escape
  675: @cindex @code{\C}
  676: @cindex conditional compilation of Vmgen output
  677: The @code{c-escape} passes the text through to each output file (without
  678: the @samp{\C}).  This is useful mainly for conditional compilation
  679: (i.e., you write @samp{\C #if ...} etc.).
  680: 
  681: @cindex sync lines
  682: @cindex @code{#line}
  683: In addition to the syntax given in the grammer, Vmgen also processes
  684: sync lines (lines starting with @samp{#line}), as produced by @samp{m4
  685: -s} (@pxref{Invoking m4, , Invoking m4, m4.info, GNU m4}) and similar
  686: tools.  This allows associating C compiler error messages with the
  687: original source of the C code.
  688: 
  689: Vmgen understands a few extensions beyond the grammar given here, but
  690: these extensions are only useful for building Gforth.  You can find a
  691: description of the format used for Gforth in @file{prim}.
  692: 
  693: @menu
  694: * Eval escapes::                what follows \E
  695: @end menu
  696: 
  697: @node Eval escapes,  , Input File Grammar, Input File Grammar
  698: @subsection Eval escapes
  699: @cindex escape to Forth
  700: @cindex eval escape
  701: @cindex @code{\E}
  702: 
  703: @c woanders?
  704: The text in @code{eval-escape} is Forth code that is evaluated when
  705: Vmgen reads the line.  You will normally use this feature to define
  706: stacks and types.
  707: 
  708: If you do not know (and do not want to learn) Forth, you can build the
  709: text according to the following grammar; these rules are normally all
  710: Forth you need for using Vmgen:
  711: 
  712: @example
  713: text: stack-decl|type-prefix-decl|stack-prefix-decl|set-flag
  714: 
  715: stack-decl: 'stack ' ident ident ident
  716: type-prefix-decl: 
  717:     's" ' string '" ' ('single'|'double') ident 'type-prefix' ident
  718: stack-prefix-decl:  ident 'stack-prefix' string
  719: set-flag: ('store-optimization'|'include-skipped-insts') ('on'|'off')
  720: @end example
  721: 
  722: Note that the syntax of this code is not checked thoroughly (there are
  723: many other Forth program fragments that could be written in an
  724: eval-escape).
  725: 
  726: A stack prefix can contain letters, digits, or @samp{:}, and may start
  727: with an @samp{#}; e.g., in Gforth the return stack has the stack prefix
  728: @samp{R:}.  This restriction is not checked during the stack prefix
  729: definition, but it is enforced by the parsing rules for stack items
  730: later.
  731: 
  732: If you know Forth, the stack effects of the non-standard words involved
  733: are:
  734: @findex stack
  735: @findex type-prefix
  736: @findex single
  737: @findex double
  738: @findex stack-prefix
  739: @findex store-optimization
  740: @example
  741: stack                 ( "name" "pointer" "type" -- )
  742:                       ( name execution: -- stack )
  743: type-prefix           ( addr u item-size stack "prefix" -- )
  744: single                ( -- item-size )
  745: double                ( -- item-size )
  746: stack-prefix          ( stack "prefix" -- )
  747: store-optimization    ( -- addr )
  748: include-skipped-insts ( -- addr )
  749: @end example
  750: 
  751: An @var{item-size} takes three cells on the stack.
  752: 
  753: @c --------------------------------------------------------------------
  754: @node Simple instructions, Superinstructions, Input File Grammar, Input File Format
  755: @section Simple instructions
  756: @cindex simple VM instruction
  757: @cindex instruction, simple VM
  758: 
  759: We will use the following simple VM instruction description as example:
  760: 
  761: @example
  762: sub ( i1 i2 -- i )
  763: i = i1-i2;
  764: @end example
  765: 
  766: The first line specifies the name of the VM instruction (@code{sub}) and
  767: its stack effect (@code{i1 i2 -- i}).  The rest of the description is
  768: just plain C code.
  769: 
  770: @cindex stack effect
  771: @cindex effect, stack
  772: The stack effect specifies that @code{sub} pulls two integers from the
  773: data stack and puts them in the C variables @code{i1} and @code{i2}
  774: (with the rightmost item (@code{i2}) taken from the top of stack;
  775: intuition: if you push @code{i1}, then @code{i2} on the stack, the
  776: resulting stack picture is @code{i1 i2}) and later pushes one integer
  777: (@code{i}) on the data stack (the rightmost item is on the top
  778: afterwards).
  779: 
  780: @cindex prefix, type
  781: @cindex type prefix
  782: @cindex default stack of a type prefix
  783: How do we know the type and stack of the stack items?  Vmgen uses
  784: prefixes, similar to Fortran; in contrast to Fortran, you have to
  785: define the prefix first:
  786: 
  787: @example
  788: \E s" Cell"   single data-stack type-prefix i
  789: @end example
  790: 
  791: This defines the prefix @code{i} to refer to the type @code{Cell}
  792: (defined as @code{long} in @file{mini.h}) and, by default, to the
  793: @code{data-stack}.  It also specifies that this type takes one stack
  794: item (@code{single}).  The type prefix is part of the variable name.
  795: 
  796: @cindex stack definition
  797: @cindex defining a stack
  798: Before we can use @code{data-stack} in this way, we have to define it:
  799: 
  800: @example
  801: \E stack data-stack sp Cell
  802: @end example
  803: @c !! use something other than Cell
  804: 
  805: @cindex stack basic type
  806: @cindex basic type of a stack
  807: @cindex type of a stack, basic
  808: This line defines the stack @code{data-stack}, which uses the stack
  809: pointer @code{sp}, and each item has the basic type @code{Cell}; other
  810: types have to fit into one or two @code{Cell}s (depending on whether the
  811: type is @code{single} or @code{double} wide), and are cast from and to
  812: Cells on accessing the @code{data-stack} with type cast macros
  813: (@pxref{VM engine}).  By default, stacks grow towards lower addresses in
  814: Vmgen-erated interpreters (@pxref{Stack growth direction}).
  815: 
  816: @cindex stack prefix
  817: @cindex prefix, stack
  818: We can override the default stack of a stack item by using a stack
  819: prefix.  E.g., consider the following instruction:
  820: 
  821: @example
  822: lit ( #i -- i )
  823: @end example
  824: 
  825: The VM instruction @code{lit} takes the item @code{i} from the
  826: instruction stream (indicated by the prefix @code{#}), and pushes it on
  827: the (default) data stack.  The stack prefix is not part of the variable
  828: name.  Stack prefixes are defined like this:
  829: 
  830: @example
  831: \E inst-stream stack-prefix #
  832: @end example
  833: 
  834: This definition defines that the stack prefix @code{#} specifies the
  835: ``stack'' @code{inst-stream}.  Since the instruction stream behaves a
  836: little differently than an ordinary stack, it is predefined, and you do
  837: not need to define it.
  838: 
  839: @cindex instruction stream
  840: The instruction stream contains instructions and their immediate
  841: arguments, so specifying that an argument comes from the instruction
  842: stream indicates an immediate argument.  Of course, instruction stream
  843: arguments can only appear to the left of @code{--} in the stack effect.
  844: If there are multiple instruction stream arguments, the leftmost is the
  845: first one (just as the intuition suggests).
  846: 
  847: @menu
  848: * C Code Macros::               Macros recognized by Vmgen
  849: * C Code restrictions::         Vmgen makes assumptions about C code
  850: * Stack growth direction::      is configurable per stack
  851: @end menu
  852: 
  853: @c --------------------------------------------------------------------
  854: @node C Code Macros, C Code restrictions, Simple instructions, Simple instructions
  855: @subsection C Code Macros
  856: @cindex macros recognized by Vmgen
  857: @cindex basic block, VM level
  858: 
  859: Vmgen recognizes the following strings in the C code part of simple
  860: instructions:
  861: 
  862: @table @code
  863: 
  864: @item SET_IP
  865: @findex SET_IP
  866: As far as Vmgen is concerned, a VM instruction containing this ends a VM
  867: basic block (used in profiling to delimit profiled sequences).  On the C
  868: level, this also sets the instruction pointer.
  869: 
  870: @item SUPER_END
  871: @findex SUPER_END
  872: This ends a basic block (for profiling), even if the instruction
  873: contains no @code{SET_IP}.
  874: 
  875: @item INST_TAIL;
  876: @findex INST_TAIL;
  877: Vmgen replaces @samp{INST_TAIL;} with code for ending a VM instruction and
  878: dispatching the next VM instruction.  Even without a @samp{INST_TAIL;} this
  879: happens automatically when control reaches the end of the C code.  If
  880: you want to have this in the middle of the C code, you need to use
  881: @samp{INST_TAIL;}.  A typical example is a conditional VM branch:
  882: 
  883: @example
  884: if (branch_condition) @{
  885:   SET_IP(target); INST_TAIL;
  886: @}
  887: /* implicit tail follows here */
  888: @end example
  889: 
  890: In this example, @samp{INST_TAIL;} is not strictly necessary, because there
  891: is another one implicitly after the if-statement, but using it improves
  892: branch prediction accuracy slightly and allows other optimizations.
  893: 
  894: @item SUPER_CONTINUE
  895: @findex SUPER_CONTINUE
  896: This indicates that the implicit tail at the end of the VM instruction
  897: dispatches the sequentially next VM instruction even if there is a
  898: @code{SET_IP} in the VM instruction.  This enables an optimization that
  899: is not yet implemented in the vmgen-ex code (but in Gforth).  The
  900: typical application is in conditional VM branches:
  901: 
  902: @example
  903: if (branch_condition) @{
  904:   SET_IP(target); INST_TAIL; /* now this INST_TAIL is necessary */
  905: @}
  906: SUPER_CONTINUE;
  907: @end example
  908: 
  909: @end table
  910: 
  911: Note that Vmgen is not smart about C-level tokenization, comments,
  912: strings, or conditional compilation, so it will interpret even a
  913: commented-out SUPER_END as ending a basic block (or, e.g.,
  914: @samp{RESET_IP;} as @samp{SET_IP;}).  Conversely, Vmgen requires the literal
  915: presence of these strings; Vmgen will not see them if they are hiding in
  916: a C preprocessor macro.
  917: 
  918: 
  919: @c --------------------------------------------------------------------
  920: @node C Code restrictions, Stack growth direction, C Code Macros, Simple instructions
  921: @subsection C Code restrictions
  922: @cindex C code restrictions
  923: @cindex restrictions on C code
  924: @cindex assumptions about C code
  925: 
  926: @cindex accessing stack (pointer)
  927: @cindex stack pointer, access
  928: @cindex instruction pointer, access
  929: Vmgen generates code and performs some optimizations under the
  930: assumption that the user-supplied C code does not access the stack
  931: pointers or stack items, and that accesses to the instruction pointer
  932: only occur through special macros.  In general you should heed these
  933: restrictions.  However, if you need to break these restrictions, read
  934: the following.
  935: 
  936: Accessing a stack or stack pointer directly can be a problem for several
  937: reasons: 
  938: @cindex stack caching, restriction on C code
  939: @cindex superinstructions, restrictions on components
  940: 
  941: @itemize @bullet
  942: 
  943: @item
  944: Vmgen optionally supports caching the top-of-stack item in a local
  945: variable (that is allocated to a register).  This is the most frequent
  946: source of trouble.  You can deal with it either by not using
  947: top-of-stack caching (slowdown factor 1-1.4, depending on machine), or
  948: by inserting flushing code (e.g., @samp{IF_spTOS(sp[...] = spTOS);}) at
  949: the start and reloading code (e.g., @samp{IF_spTOS(spTOS = sp[0])}) at
  950: the end of problematic C code.  Vmgen inserts a stack pointer update
  951: before the start of the user-supplied C code, so the flushing code has
  952: to use an index that corrects for that.  In the future, this flushing
  953: may be done automatically by mentioning a special string in the C code.
  954: @c sometimes flushing and/or reloading unnecessary
  955: 
  956: @item
  957: The Vmgen-erated code loads the stack items from stack-pointer-indexed
  958: memory into variables before the user-supplied C code, and stores them
  959: from variables to stack-pointer-indexed memory afterwards.  If you do
  960: any writes to the stack through its stack pointer in your C code, it
  961: will not affect the variables, and your write may be overwritten by the
  962: stores after the C code.  Similarly, a read from a stack using a stack
  963: pointer will not reflect computations of stack items in the same VM
  964: instruction.
  965: 
  966: @item
  967: Superinstructions keep stack items in variables across the whole
  968: superinstruction.  So you should not include VM instructions, that
  969: access a stack or stack pointer, as components of superinstructions
  970: (@pxref{VM profiler}).
  971: 
  972: @end itemize
  973: 
  974: You should access the instruction pointer only through its special
  975: macros (@samp{IP}, @samp{SET_IP}, @samp{IPTOS}); this ensure that these
  976: macros can be implemented in several ways for best performance.
  977: @samp{IP} points to the next instruction, and @samp{IPTOS} is its
  978: contents.
  979: 
  980: @c --------------------------------------------------------------------
  981: @node Stack growth direction,  , C Code restrictions, Simple instructions
  982: @subsection Stack growth direction
  983: @cindex stack growth direction
  984: 
  985: @cindex @code{stack-access-transform}
  986: By default, the stacks grow towards lower addresses.  You can change
  987: this for a stack by setting the @code{stack-access-transform} field of
  988: the stack to an xt @code{( itemnum -- index )} that performs the
  989: appropriate index transformation.
  990: 
  991: E.g., if you want to let @code{data-stack} grow towards higher
  992: addresses, with the stack pointer always pointing just beyond the
  993: top-of-stack, use this right after defining @code{data-stack}:
  994: 
  995: @example
  996: \E : sp-access-transform ( itemnum -- index ) negate 1- ;
  997: \E ' sp-access-transform ' data-stack >body stack-access-transform !
  998: @end example
  999: 
 1000: This means that @code{sp-access-transform} will be used to generate
 1001: indexes for accessing @code{data-stack}.  The definition of
 1002: @code{sp-access-transform} above transforms n into -n-1, e.g, 1 into -2.
 1003: This will access the 0th data-stack element (top-of-stack) at sp[-1],
 1004: the 1st at sp[-2], etc., which is the typical way upward-growing
 1005: stacks are used.  If you need a different transform and do not know
 1006: enough Forth to program it, let me know.
 1007: 
 1008: @c --------------------------------------------------------------------
 1009: @node Superinstructions, Store Optimization, Simple instructions, Input File Format
 1010: @section Superinstructions
 1011: @cindex superinstructions, defining
 1012: @cindex defining superinstructions
 1013: 
 1014: Note: don't invest too much work in (static) superinstructions; a future
 1015: version of Vmgen will support dynamic superinstructions (see Ian
 1016: Piumarta and Fabio Riccardi, @cite{Optimizing Direct Threaded Code by
 1017: Selective Inlining}, PLDI'98), and static superinstructions have much
 1018: less benefit in that context (preliminary results indicate only a factor
 1019: 1.1 speedup).
 1020: 
 1021: Here is an example of a superinstruction definition:
 1022: 
 1023: @example
 1024: lit_sub = lit sub
 1025: @end example
 1026: 
 1027: @code{lit_sub} is the name of the superinstruction, and @code{lit} and
 1028: @code{sub} are its components.  This superinstruction performs the same
 1029: action as the sequence @code{lit} and @code{sub}.  It is generated
 1030: automatically by the VM code generation functions whenever that sequence
 1031: occurs, so if you want to use this superinstruction, you just need to
 1032: add this definition (and even that can be partially automatized,
 1033: @pxref{VM profiler}).
 1034: 
 1035: @cindex prefixes of superinstructions
 1036: Vmgen requires that the component instructions are simple instructions
 1037: defined before superinstructions using the components.  Currently, Vmgen
 1038: also requires that all the subsequences at the start of a
 1039: superinstruction (prefixes) must be defined as superinstruction before
 1040: the superinstruction.  I.e., if you want to define a superinstruction
 1041: 
 1042: @example
 1043: foo4 = load add sub mul
 1044: @end example
 1045: 
 1046: you first have to define @code{load}, @code{add}, @code{sub} and
 1047: @code{mul}, plus
 1048: 
 1049: @example
 1050: foo2 = load add
 1051: foo3 = load add sub
 1052: @end example
 1053: 
 1054: Here, @code{sumof4} is the longest prefix of @code{sumof5}, and @code{sumof3}
 1055: is the longest prefix of @code{sumof4}.
 1056: 
 1057: Note that Vmgen assumes that only the code it generates accesses stack
 1058: pointers, the instruction pointer, and various stack items, and it
 1059: performs optimizations based on this assumption.  Therefore, VM
 1060: instructions where your C code changes the instruction pointer should
 1061: only be used as last component; a VM instruction where your C code
 1062: accesses a stack pointer should not be used as component at all.  Vmgen
 1063: does not check these restrictions, they just result in bugs in your
 1064: interpreter.
 1065: 
 1066: @cindex include-skipped-insts
 1067: The Vmgen flag @code{include-skipped-insts} influences superinstruction
 1068: code generation.  Currently there is no support in the peephole
 1069: optimizer for both variations, so leave this flag alone for now.
 1070: 
 1071: @c -------------------------------------------------------------------
 1072: @node  Store Optimization, Register Machines, Superinstructions, Input File Format
 1073: @section Store Optimization
 1074: @cindex store optimization
 1075: @cindex optimization, stack stores
 1076: @cindex stack stores, optimization
 1077: @cindex eliminating stack stores
 1078: 
 1079: This minor optimization (0.6\%--0.8\% reduction in executed instructions
 1080: for Gforth) puts additional requirements on the instruction descriptions
 1081: and is therefore disabled by default.
 1082: 
 1083: What does it do?  Consider an instruction like
 1084: 
 1085: @example
 1086: dup ( n -- n n )
 1087: @end example
 1088: 
 1089: For simplicity, also assume that we are not caching the top-of-stack in
 1090: a register.  Now, the C code for dup first loads @code{n} from the
 1091: stack, and then stores it twice to the stack, one time to the address
 1092: where it came from; that time is unnecessary, but gcc does not optimize
 1093: it away, so vmgen can do it instead (if you turn on the store
 1094: optimization).
 1095: 
 1096: Vmgen uses the stack item's name to determine if the stack item contains
 1097: the same value as it did at the start.  Therefore, if you use the store
 1098: optimization, you have to ensure that stack items that have the same
 1099: name on input and output also have the same value, and are not changed
 1100: in the C code you supply.  I.e., the following code could fail if you
 1101: turn on the store optimization:
 1102: 
 1103: @example
 1104: add1 ( n -- n )
 1105: n++;
 1106: @end example
 1107: 
 1108: Instead, you have to use different names, i.e.:
 1109: 
 1110: @example
 1111: add1 ( n1 -- n1 )
 1112: n2=n1+1;
 1113: @end example
 1114: 
 1115: Similarly, the store optimization assumes that the stack pointer is only
 1116: changed by Vmgen-erated code.  If your C code changes the stack pointer,
 1117: use different names in input and output stack items to avoid a (probably
 1118: wrong) store optimization, or turn the store optimization off for this
 1119: VM instruction.
 1120: 
 1121: To turn on the store optimization, write
 1122: 
 1123: @example
 1124: \E store-optimization on
 1125: @end example
 1126: 
 1127: at the start of the file.  You can turn this optimization on or off
 1128: between any two VM instruction descriptions.  For turning it off again,
 1129: you can use
 1130: 
 1131: @example
 1132: \E store-optimization off
 1133: @end example
 1134: 
 1135: @c -------------------------------------------------------------------
 1136: @node Register Machines,  , Store Optimization, Input File Format
 1137: @section Register Machines
 1138: @cindex Register VM
 1139: @cindex Superinstructions for register VMs
 1140: @cindex tracing of register VMs
 1141: 
 1142: If you want to implement a register VM rather than a stack VM with
 1143: Vmgen, there are two ways to do it: Directly and through
 1144: superinstructions.
 1145: 
 1146: If you use the direct way, you define instructions that take the
 1147: register numbers as immediate arguments, like this:
 1148: 
 1149: @example
 1150: add3 ( #src1 #src2 #dest -- )
 1151: reg[dest] = reg[src1]+reg[src2];
 1152: @end example
 1153: 
 1154: A disadvantage of this method is that during tracing you only see the
 1155: register numbers, but not the register contents.  Actually, with an
 1156: appropriate definition of @code{printarg_src} (@pxref{VM engine}), you
 1157: can print the values of the source registers on entry, but you cannot
 1158: print the value of the destination register on exit.
 1159: 
 1160: If you use superinstructions to define a register VM, you define simple
 1161: instructions that use a stack, and then define superinstructions that
 1162: have no overall stack effect, like this:
 1163: 
 1164: @example
 1165: loadreg ( #src -- n )
 1166: n = reg[src];
 1167: 
 1168: storereg ( n #dest -- )
 1169: reg[dest] = n;
 1170: 
 1171: adds ( n1 n2 -- n )
 1172: n = n1+n2;
 1173: 
 1174: add3 = loadreg loadreg adds storereg
 1175: @end example
 1176: 
 1177: An advantage of this method is that you see the values and not just the
 1178: register numbers in tracing.  A disadvantage of this method is that
 1179: currently you cannot generate superinstructions directly, but only
 1180: through generating a sequence of simple instructions (we might change
 1181: this in the future if there is demand).
 1182: 
 1183: Could the register VM support be improved, apart from the issues
 1184: mentioned above?  It is hard to see how to do it in a general way,
 1185: because there are a number of different designs that different people
 1186: mean when they use the term @emph{register machine} in connection with
 1187: VM interpreters.  However, if you have ideas or requests in that
 1188: direction, please let me know (@pxref{Contact}).
 1189: 
 1190: @c ********************************************************************
 1191: @node Error messages, Using the generated code, Input File Format, Top
 1192: @chapter Error messages
 1193: @cindex error messages
 1194: 
 1195: These error messages are created by Vmgen:
 1196: 
 1197: @table @code
 1198: 
 1199: @cindex @code{# can only be on the input side} error
 1200: @item # can only be on the input side
 1201: You have used an instruction-stream prefix (usually @samp{#}) after the
 1202: @samp{--} (the output side); you can only use it before (the input
 1203: side).
 1204: 
 1205: @cindex @code{prefix for this combination must be defined earlier} error
 1206: @item the prefix for this superinstruction must be defined earlier
 1207: You have defined a superinstruction (e.g. @code{abc = a b c}) without
 1208: defining its direct prefix (e.g., @code{ab = a b}),
 1209: @xref{Superinstructions}.
 1210: 
 1211: @cindex @code{sync line syntax} error
 1212: @item sync line syntax
 1213: If you are using a preprocessor (e.g., @command{m4}) to generate Vmgen
 1214: input code, you may want to create @code{#line} directives (aka sync
 1215: lines).  This error indicates that such a line is not in th syntax
 1216: expected by Vmgen (this should not happen; please report the offending
 1217: line in a bug report).
 1218: 
 1219: @cindex @code{syntax error, wrong char} error
 1220: @item syntax error, wrong char
 1221: A syntax error.  If you do not see right away where the error is, it may
 1222: be helpful to check the following: Did you put an empty line in a VM
 1223: instruction where the C code is not delimited by braces (then the empty
 1224: line ends the VM instruction)?  If you used brace-delimited C code, did
 1225: you put the delimiting braces (and only those) at the start of the line,
 1226: without preceding white space?  Did you forget a delimiting brace?
 1227: 
 1228: @cindex @code{too many stacks} error
 1229: @item too many stacks
 1230: Vmgen currently supports 3 stacks (plus the instruction stream); if you
 1231: need more, let us know.
 1232: 
 1233: @cindex @code{unknown prefix} error
 1234: @item unknown prefix
 1235: The stack item does not match any defined type prefix (after stripping
 1236: away any stack prefix).  You should either declare the type prefix you
 1237: want for that stack item, or use a different type prefix
 1238: 
 1239: @cindex @code{unknown primitive} error
 1240: @item unknown primitive
 1241: You have used the name of a simple VM instruction in a superinstruction
 1242: definition without defining the simple VM instruction first.
 1243: 
 1244: @end table
 1245: 
 1246: In addition, the C compiler can produce errors due to code produced by
 1247: Vmgen; e.g., you need to define type cast functions.
 1248: 
 1249: @c ********************************************************************
 1250: @node Using the generated code, Hints, Error messages, Top
 1251: @chapter Using the generated code
 1252: @cindex generated code, usage
 1253: @cindex Using vmgen-erated code
 1254: 
 1255: The easiest way to create a working VM interpreter with Vmgen is
 1256: probably to start with @file{vmgen-ex}, and modify it for your purposes.
 1257: This chapter explains what the various wrapper and generated files do.
 1258: It also contains reference-manual style descriptions of the macros,
 1259: variables etc. used by the generated code, and you can skip that on
 1260: first reading.
 1261: 
 1262: @menu
 1263: * VM engine::                   Executing VM code
 1264: * VM instruction table::        
 1265: * VM code generation::          Creating VM code (in the front-end)
 1266: * Peephole optimization::       Creating VM superinstructions
 1267: * VM disassembler::             for debugging the front end
 1268: * VM profiler::                 for finding worthwhile superinstructions
 1269: @end menu
 1270: 
 1271: @c --------------------------------------------------------------------
 1272: @node VM engine, VM instruction table, Using the generated code, Using the generated code
 1273: @section VM engine
 1274: @cindex VM instruction execution
 1275: @cindex engine
 1276: @cindex executing VM code
 1277: @cindex @file{engine.c}
 1278: @cindex @file{-vm.i} output file
 1279: 
 1280: The VM engine is the VM interpreter that executes the VM code.  It is
 1281: essential for an interpretive system.
 1282: 
 1283: Vmgen supports two methods of VM instruction dispatch: @emph{threaded
 1284: code} (fast, but gcc-specific), and @emph{switch dispatch} (slow, but
 1285: portable across C compilers); you can use conditional compilation
 1286: (@samp{defined(__GNUC__)}) to choose between these methods, and our
 1287: example does so.
 1288: 
 1289: For both methods, the VM engine is contained in a C-level function.
 1290: Vmgen generates most of the contents of the function for you
 1291: (@file{@var{name}-vm.i}), but you have to define this function, and
 1292: macros and variables used in the engine, and initialize the variables.
 1293: In our example the engine function also includes
 1294: @file{@var{name}-labels.i} (@pxref{VM instruction table}).
 1295: 
 1296: @cindex tracing VM code
 1297: @cindex superinstructions and tracing
 1298: In addition to executing the code, the VM engine can optionally also
 1299: print out a trace of the executed instructions, their arguments and
 1300: results.  For superinstructions it prints the trace as if only component
 1301: instructions were executed; this allows to introduce new
 1302: superinstructions while keeping the traces comparable to old ones
 1303: (important for regression tests).
 1304: 
 1305: It costs significant performance to check in each instruction whether to
 1306: print tracing code, so we recommend producing two copies of the engine:
 1307: one for fast execution, and one for tracing.  See the rules for
 1308: @file{engine.o} and @file{engine-debug.o} in @file{vmgen-ex/Makefile}
 1309: for an example.
 1310: 
 1311: The following macros and variables are used in @file{@var{name}-vm.i}:
 1312: 
 1313: @table @code
 1314: 
 1315: @findex LABEL
 1316: @item LABEL(@var{inst_name})
 1317: This is used just before each VM instruction to provide a jump or
 1318: @code{switch} label (the @samp{:} is provided by Vmgen).  For switch
 1319: dispatch this should expand to @samp{case @var{label}:}; for
 1320: threaded-code dispatch this should just expand to @samp{@var{label}:}.
 1321: In either case @var{label} is usually the @var{inst_name} with some
 1322: prefix or suffix to avoid naming conflicts.
 1323: 
 1324: @findex LABEL2
 1325: @item LABEL2(@var{inst_name})
 1326: This will be used for dynamic superinstructions; at the moment, this
 1327: should expand to nothing.
 1328: 
 1329: @findex NAME
 1330: @item NAME(@var{inst_name_string})
 1331: Called on entering a VM instruction with a string containing the name of
 1332: the VM instruction as parameter.  In normal execution this should be
 1333: expand to nothing, but for tracing this usually prints the name, and
 1334: possibly other information (several VM registers in our example).
 1335: 
 1336: @findex DEF_CA
 1337: @item DEF_CA
 1338: Usually empty.  Called just inside a new scope at the start of a VM
 1339: instruction.  Can be used to define variables that should be visible
 1340: during every VM instruction.  If you define this macro as non-empty, you
 1341: have to provide the finishing @samp{;} in the macro.
 1342: 
 1343: @findex NEXT_P0
 1344: @findex NEXT_P1
 1345: @findex NEXT_P2
 1346: @item NEXT_P0 NEXT_P1 NEXT_P2
 1347: The three parts of instruction dispatch.  They can be defined in
 1348: different ways for best performance on various processors (see
 1349: @file{engine.c} in the example or @file{engine/threaded.h} in Gforth).
 1350: @samp{NEXT_P0} is invoked right at the start of the VM instruction (but
 1351: after @samp{DEF_CA}), @samp{NEXT_P1} right after the user-supplied C
 1352: code, and @samp{NEXT_P2} at the end.  The actual jump has to be
 1353: performed by @samp{NEXT_P2} (if you would do it earlier, important parts
 1354: of the VM instruction would not be executed).
 1355: 
 1356: The simplest variant is if @samp{NEXT_P2} does everything and the other
 1357: macros do nothing.  Then also related macros like @samp{IP},
 1358: @samp{SET_IP}, @samp{IP}, @samp{INC_IP} and @samp{IPTOS} are very
 1359: straightforward to define.  For switch dispatch this code consists just
 1360: of a jump to the dispatch code (@samp{goto next_inst;} in our example);
 1361: for direct threaded code it consists of something like
 1362: @samp{(@{cfa=*ip++; goto *cfa;@})}.
 1363: 
 1364: Pulling code (usually the @samp{cfa=*ip++;}) up into @samp{NEXT_P1}
 1365: usually does not cause problems, but pulling things up into
 1366: @samp{NEXT_P0} usually requires changing the other macros (and, at least
 1367: for Gforth on Alpha, it does not buy much, because the compiler often
 1368: manages to schedule the relevant stuff up by itself).  An even more
 1369: extreme variant is to pull code up even further, into, e.g., NEXT_P1 of
 1370: the previous VM instruction (prefetching, useful on PowerPCs).
 1371: 
 1372: @findex INC_IP
 1373: @item INC_IP(@var{n})
 1374: This increments @code{IP} by @var{n}.
 1375: 
 1376: @findex SET_IP
 1377: @item SET_IP(@var{target})
 1378: This sets @code{IP} to @var{target}.
 1379: 
 1380: @cindex type cast macro
 1381: @findex vm_@var{A}2@var{B}
 1382: @item vm_@var{A}2@var{B}(a,b)
 1383: Type casting macro that assigns @samp{a} (of type @var{A}) to @samp{b}
 1384: (of type @var{B}).  This is mainly used for getting stack items into
 1385: variables and back.  So you need to define macros for every combination
 1386: of stack basic type (@code{Cell} in our example) and type-prefix types
 1387: used with that stack (in both directions).  For the type-prefix type,
 1388: you use the type-prefix (not the C type string) as type name (e.g.,
 1389: @samp{vm_Cell2i}, not @samp{vm_Cell2Cell}).  In addition, you have to
 1390: define a vm_@var{X}2@var{X} macro for the stack's basic type @var{X}
 1391: (used in superinstructions).
 1392: 
 1393: @cindex instruction stream, basic type
 1394: The stack basic type for the predefined @samp{inst-stream} is
 1395: @samp{Cell}.  If you want a stack with the same item size, making its
 1396: basic type @samp{Cell} usually reduces the number of macros you have to
 1397: define.
 1398: 
 1399: @cindex unions in type cast macros
 1400: @cindex casts in type cast macros
 1401: @cindex type casting between floats and integers
 1402: Here our examples differ a lot: @file{vmgen-ex} uses casts in these
 1403: macros, whereas @file{vmgen-ex2} uses union-field selection (or
 1404: assignment to union fields).  Note that casting floats into integers and
 1405: vice versa changes the bit pattern (and you do not want that).  In this
 1406: case your options are to use a (temporary) union, or to take the address
 1407: of the value, cast the pointer, and dereference that (not always
 1408: possible, and sometimes expensive).
 1409: 
 1410: @findex vm_two@var{A}2@var{B}
 1411: @findex vm_@var{B}2two@var{A}
 1412: @item vm_two@var{A}2@var{B}(a1,a2,b)
 1413: @item vm_@var{B}2two@var{A}(b,a1,a2)
 1414: Type casting between two stack items (@code{a1}, @code{a2}) and a
 1415: variable @code{b} of a type that takes two stack items.  This does not
 1416: occur in our small examples, but you can look at Gforth for examples
 1417: (see @code{vm_twoCell2d} in @file{engine/forth.h}).
 1418: 
 1419: @cindex stack pointer definition
 1420: @cindex instruction pointer definition
 1421: @item @var{stackpointer}
 1422: For each stack used, the stackpointer name given in the stack
 1423: declaration is used.  For a regular stack this must be an l-expression;
 1424: typically it is a variable declared as a pointer to the stack's basic
 1425: type.  For @samp{inst-stream}, the name is @samp{IP}, and it can be a
 1426: plain r-value; typically it is a macro that abstracts away the
 1427: differences between the various implementations of @code{NEXT_P*}.
 1428: 
 1429: @cindex IMM_ARG
 1430: @findex IMM_ARG
 1431: @item IMM_ARG(access,value)
 1432: Define this to expland to ``(access)''.  This is just a placeholder for
 1433: future extensions.
 1434: 
 1435: @cindex top of stack caching
 1436: @cindex stack caching
 1437: @cindex TOS
 1438: @findex IPTOS
 1439: @item @var{stackpointer}TOS
 1440: The top-of-stack for the stack pointed to by @var{stackpointer}.  If you
 1441: are using top-of-stack caching for that stack, this should be defined as
 1442: variable; if you are not using top-of-stack caching for that stack, this
 1443: should be a macro expanding to @samp{@var{stackpointer}[0]}.  The stack
 1444: pointer for the predefined @samp{inst-stream} is called @samp{IP}, so
 1445: the top-of-stack is called @samp{IPTOS}.
 1446: 
 1447: @findex IF_@var{stackpointer}TOS
 1448: @item IF_@var{stackpointer}TOS(@var{expr})
 1449: Macro for executing @var{expr}, if top-of-stack caching is used for the
 1450: @var{stackpointer} stack.  I.e., this should do @var{expr} if there is
 1451: top-of-stack caching for @var{stackpointer}; otherwise it should do
 1452: nothing.
 1453: 
 1454: @findex SUPER_END
 1455: @item SUPER_END
 1456: This is used by the VM profiler (@pxref{VM profiler}); it should not do
 1457: anything in normal operation, and call @code{vm_count_block(IP)} for
 1458: profiling.
 1459: 
 1460: @findex SUPER_CONTINUE
 1461: @item SUPER_CONTINUE
 1462: This is just a hint to Vmgen and does nothing at the C level.
 1463: 
 1464: @findex MAYBE_UNUSED
 1465: @item MAYBE_UNUSED
 1466: This should be defined as @code{__attribute__((unused))} for gcc-2.7 and
 1467: higher.  It suppresses the warnings about unused variables in the code
 1468: for superinstructions.  You need to define this only if you are using
 1469: superinstructions.
 1470: 
 1471: @findex VM_DEBUG
 1472: @item VM_DEBUG
 1473: If this is defined, the tracing code will be compiled in (slower
 1474: interpretation, but better debugging).  Our example compiles two
 1475: versions of the engine, a fast-running one that cannot trace, and one
 1476: with potential tracing and profiling.
 1477: 
 1478: @findex vm_debug
 1479: @item vm_debug
 1480: Needed only if @samp{VM_DEBUG} is defined.  If this variable contains
 1481: true, the VM instructions produce trace output.  It can be turned on or
 1482: off at any time.
 1483: 
 1484: @findex vm_out
 1485: @item vm_out
 1486: Needed only if @samp{VM_DEBUG} is defined.  Specifies the file on which
 1487: to print the trace output (type @samp{FILE *}).
 1488: 
 1489: @findex printarg_@var{type}
 1490: @item printarg_@var{type}(@var{value})
 1491: Needed only if @samp{VM_DEBUG} is defined.  Macro or function for
 1492: printing @var{value} in a way appropriate for the @var{type}.  This is
 1493: used for printing the values of stack items during tracing.  @var{Type}
 1494: is normally the type prefix specified in a @code{type-prefix} definition
 1495: (e.g., @samp{printarg_i}); in superinstructions it is currently the
 1496: basic type of the stack.
 1497: 
 1498: @end table
 1499: 
 1500: 
 1501: @c --------------------------------------------------------------------
 1502: @node VM instruction table, VM code generation, VM engine, Using the generated code
 1503: @section VM instruction table
 1504: @cindex instruction table
 1505: @cindex opcode definition
 1506: @cindex labels for threaded code
 1507: @cindex @code{vm_prim}, definition
 1508: @cindex @file{-labels.i} output file
 1509: 
 1510: For threaded code we also need to produce a table containing the labels
 1511: of all VM instructions.  This is needed for VM code generation
 1512: (@pxref{VM code generation}), and it has to be done in the engine
 1513: function, because the labels are not visible outside.  It then has to be
 1514: passed outside the function (and assigned to @samp{vm_prim}), to be used
 1515: by the VM code generation functions.
 1516: 
 1517: This means that the engine function has to be called first to produce
 1518: the VM instruction table, and later, after generating VM code, it has to
 1519: be called again to execute the generated VM code (yes, this is ugly).
 1520: In our example program, these two modes of calling the engine function
 1521: are differentiated by the value of the parameter ip0 (if it equals 0,
 1522: then the table is passed out, otherwise the VM code is executed); in our
 1523: example, we pass the table out by assigning it to @samp{vm_prim} and
 1524: returning from @samp{engine}.
 1525: 
 1526: In our example (@file{vmgen-ex/engine.c}), we also build such a table for
 1527: switch dispatch; this is mainly done for uniformity.
 1528: 
 1529: For switch dispatch, we also need to define the VM instruction opcodes
 1530: used as case labels in an @code{enum}.
 1531: 
 1532: For both purposes (VM instruction table, and enum), the file
 1533: @file{@var{name}-labels.i} is generated by Vmgen.  You have to define
 1534: the following macro used in this file:
 1535: 
 1536: @table @code
 1537: 
 1538: @findex INST_ADDR
 1539: @item INST_ADDR(@var{inst_name})
 1540: For switch dispatch, this is just the name of the switch label (the same
 1541: name as used in @samp{LABEL(@var{inst_name})}), for both uses of
 1542: @file{@var{name}-labels.i}.  For threaded-code dispatch, this is the
 1543: address of the label defined in @samp{LABEL(@var{inst_name})}); the
 1544: address is taken with @samp{&&} (@pxref{Labels as Values, , Labels as
 1545: Values, gcc.info, GNU C Manual}).
 1546: 
 1547: @end table
 1548: 
 1549: 
 1550: @c --------------------------------------------------------------------
 1551: @node VM code generation, Peephole optimization, VM instruction table, Using the generated code
 1552: @section VM code generation
 1553: @cindex VM code generation
 1554: @cindex code generation, VM
 1555: @cindex @file{-gen.i} output file
 1556: 
 1557: Vmgen generates VM code generation functions in @file{@var{name}-gen.i}
 1558: that the front end can call to generate VM code.  This is essential for
 1559: an interpretive system.
 1560: 
 1561: @findex gen_@var{inst}
 1562: For a VM instruction @samp{x ( #a b #c -- d )}, Vmgen generates a
 1563: function with the prototype
 1564: 
 1565: @example
 1566: void gen_x(Inst **ctp, a_type a, c_type c)
 1567: @end example
 1568: 
 1569: The @code{ctp} argument points to a pointer to the next instruction.
 1570: @code{*ctp} is increased by the generation functions; i.e., you should
 1571: allocate memory for the code to be generated beforehand, and start with
 1572: *ctp set at the start of this memory area.  Before running out of
 1573: memory, allocate a new area, and generate a VM-level jump to the new
 1574: area (this overflow handling is not implemented in our examples).
 1575: 
 1576: @cindex immediate arguments, VM code generation
 1577: The other arguments correspond to the immediate arguments of the VM
 1578: instruction (with their appropriate types as defined in the
 1579: @code{type_prefix} declaration.
 1580: 
 1581: The following types, variables, and functions are used in
 1582: @file{@var{name}-gen.i}:
 1583: 
 1584: @table @code
 1585: 
 1586: @findex Inst
 1587: @item Inst
 1588: The type of the VM instruction; if you use threaded code, this is
 1589: @code{void *}; for switch dispatch this is an integer type.
 1590: 
 1591: @cindex @code{vm_prim}, use
 1592: @item vm_prim
 1593: The VM instruction table (type: @code{Inst *}, @pxref{VM instruction table}).
 1594: 
 1595: @findex gen_inst
 1596: @item gen_inst(Inst **ctp, Inst i)
 1597: This function compiles the instruction @code{i}.  Take a look at it in
 1598: @file{vmgen-ex/peephole.c}.  It is trivial when you don't want to use
 1599: superinstructions (just the last two lines of the example function), and
 1600: slightly more complicated in the example due to its ability to use
 1601: superinstructions (@pxref{Peephole optimization}).
 1602: 
 1603: @findex genarg_@var{type_prefix}
 1604: @item genarg_@var{type_prefix}(Inst **ctp, @var{type} @var{type_prefix})
 1605: This compiles an immediate argument of @var{type} (as defined in a
 1606: @code{type-prefix} definition).  These functions are trivial to define
 1607: (see @file{vmgen-ex/support.c}).  You need one of these functions for
 1608: every type that you use as immediate argument.
 1609: 
 1610: @end table
 1611: 
 1612: @findex BB_BOUNDARY
 1613: In addition to using these functions to generate code, you should call
 1614: @code{BB_BOUNDARY} at every basic block entry point if you ever want to
 1615: use superinstructions (or if you want to use the profiling supported by
 1616: Vmgen; but this support is also useful mainly for selecting
 1617: superinstructions).  If you use @code{BB_BOUNDARY}, you should also
 1618: define it (take a look at its definition in @file{vmgen-ex/mini.y}).
 1619: 
 1620: You do not need to call @code{BB_BOUNDARY} after branches, because you
 1621: will not define superinstructions that contain branches in the middle
 1622: (and if you did, and it would work, there would be no reason to end the
 1623: superinstruction at the branch), and because the branches announce
 1624: themselves to the profiler.
 1625: 
 1626: 
 1627: @c --------------------------------------------------------------------
 1628: @node Peephole optimization, VM disassembler, VM code generation, Using the generated code
 1629: @section Peephole optimization
 1630: @cindex peephole optimization
 1631: @cindex superinstructions, generating
 1632: @cindex @file{peephole.c}
 1633: @cindex @file{-peephole.i} output file
 1634: 
 1635: You need peephole optimization only if you want to use
 1636: superinstructions.  But having the code for it does not hurt much if you
 1637: do not use superinstructions.
 1638: 
 1639: A simple greedy peephole optimization algorithm is used for
 1640: superinstruction selection: every time @code{gen_inst} compiles a VM
 1641: instruction, it checks if it can combine it with the last VM instruction
 1642: (which may also be a superinstruction resulting from a previous peephole
 1643: optimization); if so, it changes the last instruction to the combined
 1644: instruction instead of laying down @code{i} at the current @samp{*ctp}.
 1645: 
 1646: The code for peephole optimization is in @file{vmgen-ex/peephole.c}.
 1647: You can use this file almost verbatim.  Vmgen generates
 1648: @file{@var{file}-peephole.i} which contains data for the peephole
 1649: optimizer.
 1650: 
 1651: @findex init_peeptable
 1652: You have to call @samp{init_peeptable()} after initializing
 1653: @samp{vm_prim}, and before compiling any VM code to initialize data
 1654: structures for peephole optimization.  After that, compiling with the VM
 1655: code generation functions will automatically combine VM instructions
 1656: into superinstructions.  Since you do not want to combine instructions
 1657: across VM branch targets (otherwise there will not be a proper VM
 1658: instruction to branch to), you have to call @code{BB_BOUNDARY}
 1659: (@pxref{VM code generation}) at branch targets.
 1660: 
 1661: 
 1662: @c --------------------------------------------------------------------
 1663: @node VM disassembler, VM profiler, Peephole optimization, Using the generated code
 1664: @section VM disassembler
 1665: @cindex VM disassembler
 1666: @cindex disassembler, VM code
 1667: @cindex @file{disasm.c}
 1668: @cindex @file{-disasm.i} output file
 1669: 
 1670: A VM code disassembler is optional for an interpretive system, but
 1671: highly recommended during its development and maintenance, because it is
 1672: very useful for detecting bugs in the front end (and for distinguishing
 1673: them from VM interpreter bugs).
 1674: 
 1675: Vmgen supports VM code disassembling by generating
 1676: @file{@var{file}-disasm.i}.  This code has to be wrapped into a
 1677: function, as is done in @file{vmgen-ex/disasm.c}.  You can use this file
 1678: almost verbatim.  In addition to @samp{vm_@var{A}2@var{B}(a,b)},
 1679: @samp{vm_out}, @samp{printarg_@var{type}(@var{value})}, which are
 1680: explained above, the following macros and variables are used in
 1681: @file{@var{file}-disasm.i} (and you have to define them):
 1682: 
 1683: @table @code
 1684: 
 1685: @item ip
 1686: This variable points to the opcode of the current VM instruction.
 1687: 
 1688: @cindex @code{IP}, @code{IPTOS} in disassmbler
 1689: @item IP IPTOS
 1690: @samp{IPTOS} is the first argument of the current VM instruction, and
 1691: @samp{IP} points to it; this is just as in the engine, but here
 1692: @samp{ip} points to the opcode of the VM instruction (in contrast to the
 1693: engine, where @samp{ip} points to the next cell, or even one further).
 1694: 
 1695: @findex VM_IS_INST
 1696: @item VM_IS_INST(Inst i, int n)
 1697: Tests if the opcode @samp{i} is the same as the @samp{n}th entry in the
 1698: VM instruction table.
 1699: 
 1700: @end table
 1701: 
 1702: 
 1703: @c --------------------------------------------------------------------
 1704: @node VM profiler,  , VM disassembler, Using the generated code
 1705: @section VM profiler
 1706: @cindex VM profiler
 1707: @cindex profiling for selecting superinstructions
 1708: @cindex superinstructions and profiling
 1709: @cindex @file{profile.c}
 1710: @cindex @file{-profile.i} output file
 1711: 
 1712: The VM profiler is designed for getting execution and occurence counts
 1713: for VM instruction sequences, and these counts can then be used for
 1714: selecting sequences as superinstructions.  The VM profiler is probably
 1715: not useful as profiling tool for the interpretive system.  I.e., the VM
 1716: profiler is useful for the developers, but not the users of the
 1717: interpretive system.
 1718: 
 1719: The output of the profiler is: for each basic block (executed at least
 1720: once), it produces the dynamic execution count of that basic block and
 1721: all its subsequences; e.g.,
 1722: 
 1723: @example
 1724:        9227465  lit storelocal 
 1725:        9227465  storelocal branch 
 1726:        9227465  lit storelocal branch 
 1727: @end example
 1728: 
 1729: I.e., a basic block consisting of @samp{lit storelocal branch} is
 1730: executed 9227465 times.
 1731: 
 1732: @cindex @file{stat.awk}
 1733: @cindex @file{seq2rule.awk}
 1734: This output can be combined in various ways.  E.g.,
 1735: @file{vmgen-ex/stat.awk} adds up the occurences of a given sequence wrt
 1736: dynamic execution, static occurence, and per-program occurence.  E.g.,
 1737: 
 1738: @example
 1739:       2      16        36910041 loadlocal lit 
 1740: @end example
 1741: 
 1742: @noindent
 1743: indicates that the sequence @samp{loadlocal lit} occurs in 2 programs,
 1744: in 16 places, and has been executed 36910041 times.  Now you can select
 1745: superinstructions in any way you like (note that compile time and space
 1746: typically limit the number of superinstructions to 100--1000).  After
 1747: you have done that, @file{vmgen/seq2rule.awk} turns lines of the form
 1748: above into rules for inclusion in a Vmgen input file.  Note that this
 1749: script does not ensure that all prefixes are defined, so you have to do
 1750: that in other ways.  So, an overall script for turning profiles into
 1751: superinstructions can look like this:
 1752: 
 1753: @example
 1754: awk -f stat.awk fib.prof test.prof|
 1755: awk '$3>=10000'|                #select sequences
 1756: fgrep -v -f peephole-blacklist| #eliminate wrong instructions
 1757: awk -f seq2rule.awk|            #turn into superinstructions
 1758: sort -k 3 >mini-super.vmg       #sort sequences
 1759: @end example
 1760: 
 1761: Here the dynamic count is used for selecting sequences (preliminary
 1762: results indicate that the static count gives better results, though);
 1763: the third line eliminates sequences containing instructions that must not
 1764: occur in a superinstruction, because they access a stack directly.  The
 1765: dynamic count selection ensures that all subsequences (including
 1766: prefixes) of longer sequences occur (because subsequences have at least
 1767: the same count as the longer sequences); the sort in the last line
 1768: ensures that longer superinstructions occur after their prefixes.
 1769: 
 1770: But before using this, you have to have the profiler.  Vmgen supports its
 1771: creation by generating @file{@var{file}-profile.i}; you also need the
 1772: wrapper file @file{vmgen-ex/profile.c} that you can use almost verbatim.
 1773: 
 1774: @cindex @code{SUPER_END} in profiling
 1775: @cindex @code{BB_BOUNDARY} in profiling
 1776: The profiler works by recording the targets of all VM control flow
 1777: changes (through @code{SUPER_END} during execution, and through
 1778: @code{BB_BOUNDARY} in the front end), and counting (through
 1779: @code{SUPER_END}) how often they were targeted.  After the program run,
 1780: the numbers are corrected such that each VM basic block has the correct
 1781: count (entering a block without executing a branch does not increase the
 1782: count, and the correction fixes that), then the subsequences of all
 1783: basic blocks are printed.  To get all this, you just have to define
 1784: @code{SUPER_END} (and @code{BB_BOUNDARY}) appropriately, and call
 1785: @code{vm_print_profile(FILE *file)} when you want to output the profile
 1786: on @code{file}.
 1787: 
 1788: @cindex @code{VM_IS_INST} in profiling
 1789: The @file{@var{file}-profile.i} is similar to the disassembler file, and
 1790: it uses variables and functions defined in @file{vmgen-ex/profile.c},
 1791: plus @code{VM_IS_INST} already defined for the VM disassembler
 1792: (@pxref{VM disassembler}).
 1793: 
 1794: @c **********************************************************
 1795: @node Hints, The future, Using the generated code, Top
 1796: @chapter Hints
 1797: @cindex hints
 1798: 
 1799: @menu
 1800: * Floating point::              and stacks
 1801: @end menu
 1802: 
 1803: @c --------------------------------------------------------------------
 1804: @node Floating point,  , Hints, Hints
 1805: @section Floating point
 1806: 
 1807: How should you deal with floating point values?  Should you use the same
 1808: stack as for integers/pointers, or a different one?  This section
 1809: discusses this issue with a view on execution speed.
 1810: 
 1811: The simpler approach is to use a separate floating-point stack.  This
 1812: allows you to choose FP value size without considering the size of the
 1813: integers/pointers, and you avoid a number of performance problems.  The
 1814: main downside is that this needs an FP stack pointer (and that may not
 1815: fit in the register file on the 386 arhitecture, costing some
 1816: performance, but comparatively little if you take the other option into
 1817: account).  If you use a separate FP stack (with stack pointer @code{fp}),
 1818: using an fpTOS is helpful on most machines, but some spill the fpTOS
 1819: register into memory, and fpTOS should not be used there.
 1820: 
 1821: The other approach is to share one stack (pointed to by, say, @code{sp})
 1822: between integer/pointer and floating-point values.  This is ok if you do
 1823: not use @code{spTOS}.  If you do use @code{spTOS}, the compiler has to
 1824: decide whether to put that variable into an integer or a floating point
 1825: register, and the other type of operation becomes quite expensive on
 1826: most machines (because moving values between integer and FP registers is
 1827: quite expensive).  If a value of one type has to be synthesized out of
 1828: two values of the other type (@code{double} types), things are even more
 1829: interesting.
 1830: 
 1831: One way around this problem would be to not use the @code{spTOS}
 1832: supported by Vmgen, but to use explicit top-of-stack variables (one for
 1833: integers, one for FP values), and having a kind of accumulator+stack
 1834: architecture (e.g., Ocaml bytecode uses this approach); however, this is
 1835: a major change, and it's ramifications are not completely clear.
 1836: 
 1837: @c **********************************************************
 1838: @node The future, Changes, Hints, Top
 1839: @chapter The future
 1840: @cindex future ideas
 1841: 
 1842: We have a number of ideas for future versions of Vmgen.  However, there
 1843: are so many possible things to do that we would like some feedback from
 1844: you.  What are you doing with Vmgen, what features are you missing, and
 1845: why?
 1846: 
 1847: One idea we are thinking about is to generate just one @file{.c} file
 1848: instead of letting you copy and adapt all the wrapper files (you would
 1849: still have to define stuff like the type-specific macros, and stack
 1850: pointers etc. somewhere).  The advantage would be that, if we change the
 1851: wrapper files between versions, you would not need to integrate your
 1852: changes and our changes to them; Vmgen would also be easier to use for
 1853: beginners.  The main disadvantage of that is that it would reduce the
 1854: flexibility of Vmgen a little (well, those who like flexibility could
 1855: still patch the resulting @file{.c} file, like they are now doing for
 1856: the wrapper files).  In any case, if you are doing things to the wrapper
 1857: files that would cause problems in a generated-@file{.c}-file approach,
 1858: please let us know.
 1859: 
 1860: @c **********************************************************
 1861: @node Changes, Contact, The future, Top
 1862: @chapter Changes
 1863: @cindex Changes from old versions
 1864: 
 1865: User-visible changes between 0.5.9-20020822 and 0.5.9-20020901:
 1866: 
 1867: The store optimization is now disabled by default, but can be enabled by
 1868: the user (@pxref{Store Optimization}).  Documentation for this
 1869: optimization is also new.
 1870: 
 1871: User-visible changes between 0.5.9-20010501 and 0.5.9-20020822:
 1872: 
 1873: There is now a manual (in info, HTML, Postscript, or plain text format).
 1874: 
 1875: There is the vmgen-ex2 variant of the vmgen-ex example; the new
 1876: variant uses a union type instead of lots of casting.
 1877: 
 1878: Both variants of the example can now be compiled with an ANSI C compiler
 1879: (using switch dispatch and losing quite a bit of performance); tested
 1880: with @command{lcc}.
 1881: 
 1882: Users of the gforth-0.5.9-20010501 version of Vmgen need to change
 1883: several things in their source code to use the current version.  I
 1884: recommend keeping the gforth-0.5.9-20010501 version until you have
 1885: completed the change (note that you can have several versions of Gforth
 1886: installed at the same time).  I hope to avoid such incompatible changes
 1887: in the future.
 1888: 
 1889: The required changes are:
 1890: 
 1891: @table @code
 1892: 
 1893: @cindex @code{TAIL;}, changes
 1894: @item TAIL;
 1895: has been renamed into @code{INST_TAIL;} (less chance of an accidental
 1896: match).
 1897: 
 1898: @cindex @code{vm_@var{A}2@var{B}}, changes
 1899: @item vm_@var{A}2@var{B}
 1900: now takes two arguments.
 1901: 
 1902: @cindex @code{vm_two@var{A}2@var{B}}, changes
 1903: @item vm_two@var{A}2@var{B}(b,a1,a2);
 1904: changed to vm_two@var{A}2@var{B}(a1,a2,b) (note the absence of the @samp{;}).
 1905: 
 1906: @end table
 1907: 
 1908: Also some new macros have to be defined, e.g., @code{INST_ADDR}, and
 1909: @code{LABEL}; some macros have to be defined in new contexts, e.g.,
 1910: @code{VM_IS_INST} is now also needed in the disassembler.
 1911: 
 1912: @c *********************************************************
 1913: @node Contact, Copying This Manual, Changes, Top
 1914: @chapter Contact
 1915: 
 1916: To report a bug, use
 1917: @url{https://savannah.gnu.org/bugs/?func=addbug&group_id=2672}.
 1918: 
 1919: For discussion on Vmgen (e.g., how to use it), use the mailing list
 1920: @email{bug-vmgen@@mail.freesoftware.fsf.org} (use
 1921: @url{http://mail.gnu.org/mailman/listinfo/help-vmgen} to subscribe).
 1922: 
 1923: You can find vmgen information at
 1924: @url{http://www.complang.tuwien.ac.at/anton/vmgen/}.
 1925: 
 1926: @c ***********************************************************
 1927: @node Copying This Manual, Index, Contact, Top
 1928: @appendix Copying This Manual
 1929: 
 1930: @menu
 1931: * GNU Free Documentation License::  License for copying this manual.
 1932: @end menu
 1933: 
 1934: @include fdl.texi
 1935: 
 1936: 
 1937: @node Index,  , Copying This Manual, Top
 1938: @unnumbered Index
 1939: 
 1940: @printindex cp
 1941: 
 1942: @bye

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