Annotation of gforth/doc/vmgen.texi, revision 1.23

1.10      anton       1: \input texinfo    @c -*-texinfo-*-
                      2: @comment %**start of header
                      3: @setfilename vmgen.info
1.1       anton       4: @include version.texi
1.10      anton       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: 
1.23    ! anton      13: Copyright @copyright{} 2002, 03 Free Software Foundation, Inc.
1.10      anton      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: 
1.23    ! anton      30: @dircategory Software development
1.10      anton      31: @direntry
1.11      anton      32: * Vmgen: (vmgen).               Interpreter generator
1.10      anton      33: @end direntry
                     34: 
                     35: @titlepage
                     36: @title Vmgen
                     37: @subtitle for Gforth version @value{VERSION}, @value{UPDATED}
1.11      anton      38: @author M. Anton Ertl (@email{anton@@mips.complang.tuwien.ac.at})
1.10      anton      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
1.11      anton      57: * Invoking Vmgen::              
1.10      anton      58: * Example::                     
                     59: * Input File Format::           
1.13      anton      60: * Error messages::              reported by Vmgen
1.10      anton      61: * Using the generated code::    
1.13      anton      62: * Hints::                       VM archictecture, efficiency
                     63: * The future::                  
1.10      anton      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::           
1.18      anton      88: * Store Optimization::          
1.11      anton      89: * Register Machines::           How to define register VM instructions
1.10      anton      90: 
1.17      anton      91: Input File Grammar
                     92: 
                     93: * Eval escapes::                what follows \E
                     94: 
1.10      anton      95: Simple instructions
                     96: 
                     97: * C Code Macros::               Macros recognized by Vmgen
                     98: * C Code restrictions::         Vmgen makes assumptions about C code
1.22      anton      99: * Stack growth direction::      is configurable per stack
1.10      anton     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: 
1.13      anton     110: Hints
                    111: 
                    112: * Floating point::              and stacks
                    113: 
1.10      anton     114: Copying This Manual
                    115: 
                    116: * GNU Free Documentation License::  License for copying this manual.
                    117: 
                    118: @end detailmenu
                    119: @end menu
1.1       anton     120: 
                    121: @c @ifnottex
1.11      anton     122: @c This file documents Vmgen (Gforth @value{VERSION}).
1.1       anton     123: 
1.10      anton     124: @c ************************************************************
                    125: @node Introduction, Why interpreters?, Top, Top
1.2       anton     126: @chapter Introduction
1.1       anton     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: 
1.11      anton     135: The interpreter design strategy supported by Vmgen is to divide the
1.1       anton     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
1.6       anton     152: as for efficiency.  The virtual machine code is typically passed between
                    153: front end and virtual machine interpreter in memory, like in a
1.1       anton     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: 
1.12      anton     162: @cindex functionality features overview
1.11      anton     163: In this setup, Vmgen can generate most of the code dealing with virtual
1.1       anton     164: machine instructions from a simple description of the virtual machine
1.11      anton     165: instructions (@pxref{Input File Format}), in particular:
1.1       anton     166: 
1.13      anton     167: @table @strong
1.1       anton     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
1.12      anton     183: Useful for optimizing the VM interpreter with superinstructions
1.11      anton     184: (@pxref{VM profiler}).
1.1       anton     185: 
                    186: @end table
                    187: 
1.13      anton     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: 
1.12      anton     192: @cindex efficiency features overview
1.11      anton     193: @noindent
                    194: Vmgen supports efficient interpreters though various optimizations, in
1.1       anton     195: particular
                    196: 
1.11      anton     197: @itemize @bullet
1.1       anton     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: 
1.12      anton     211: @cindex speed for JVM
1.11      anton     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
1.1       anton     214: benchmarks; on large benchmarks, which spend more time in the run-time
1.2       anton     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).
1.1       anton     220: 
                    221: VMs are usually designed as stack machines (passing data between VM
1.11      anton     222: instructions on a stack), and Vmgen supports such designs especially
1.12      anton     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.
1.1       anton     226: 
1.2       anton     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
1.13      anton     229: we will consider new features if someone asks for them; so the feature
1.2       anton     230: list above is not exhaustive.
1.1       anton     231: 
1.2       anton     232: @c *********************************************************************
1.10      anton     233: @node Why interpreters?, Concepts, Introduction, Top
1.2       anton     234: @chapter Why interpreters?
1.12      anton     235: @cindex interpreters, advantages
                    236: @cindex advantages of interpreters
                    237: @cindex advantages of vmgen
1.2       anton     238: 
                    239: Interpreters are a popular language implementation technique because
                    240: they combine all three of the following advantages:
                    241: 
1.11      anton     242: @itemize @bullet
1.2       anton     243: 
                    244: @item Ease of implementation
                    245: 
                    246: @item Portability
                    247: 
                    248: @item Fast edit-compile-run cycle
                    249: 
                    250: @end itemize
                    251: 
1.12      anton     252: Vmgen makes it even easier to implement interpreters.
                    253: 
                    254: @cindex speed of interpreters
1.2       anton     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: 
1.12      anton     264: Vmgen supports techniques for building efficient interpreters.
1.2       anton     265: 
                    266: @c ********************************************************************
1.11      anton     267: @node Concepts, Invoking Vmgen, Why interpreters?, Top
1.2       anton     268: @chapter Concepts
                    269: 
1.10      anton     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: 
1.2       anton     276: @c --------------------------------------------------------------------
1.10      anton     277: @node Front end and VM interpreter, Data handling, Concepts, Concepts
                    278: @section Front end and VM interpreter
1.12      anton     279: @cindex modularization of interpreters
1.2       anton     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
1.12      anton     289: @cindex VM instruction
1.2       anton     290: @cindex instruction, VM
1.12      anton     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
1.2       anton     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
1.12      anton     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}.
1.2       anton     308: 
1.11      anton     309: In this framework, Vmgen supports building the VM interpreter and any
1.2       anton     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
1.3       anton     313: techniques, supported by tools like @command{flex} and @command{bison}.
1.2       anton     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
1.13      anton     320: open to feature requests and suggestions.
1.3       anton     321: 
1.10      anton     322: @c --------------------------------------------------------------------
                    323: @node Data handling, Dispatch, Front end and VM interpreter, Concepts
1.3       anton     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
1.13      anton     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
1.3       anton     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: 
1.11      anton     339: You can also implement a register VM with Vmgen (@pxref{Register
                    340: Machines}), and you will still profit from most Vmgen features.
1.3       anton     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
1.11      anton     354: stack in Vmgen.
1.3       anton     355: 
                    356: @cindex garbage collection
                    357: @cindex reference counting
1.12      anton     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).
1.3       anton     363: @c reference counting might be possible by including counting code in 
                    364: @c the conversion macros.
                    365: 
1.10      anton     366: @c --------------------------------------------------------------------
                    367: @node Dispatch,  , Data handling, Concepts
1.6       anton     368: @section Dispatch
1.12      anton     369: @cindex Dispatch of VM instructions
                    370: @cindex main interpreter loop
1.6       anton     371: 
1.11      anton     372: Understanding this section is probably not necessary for using Vmgen,
1.6       anton     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
1.11      anton     376: the next VM instruction (Vmgen calls the dispatch routine @samp{NEXT}).
1.6       anton     377: Vmgen supports two methods of dispatch:
                    378: 
1.13      anton     379: @table @strong
1.6       anton     380: 
                    381: @item switch dispatch
1.12      anton     382: @cindex switch dispatch
1.6       anton     383: In this method the VM interpreter contains a giant @code{switch}
                    384: statement, with one @code{case} for each VM instruction.  The VM
1.12      anton     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.
1.6       anton     390: 
                    391: @item threaded code
1.12      anton     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.
1.6       anton     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
1.11      anton     399: be implemented using GNU C's labels-as-values extension (@pxref{Labels
                    400: as Values, , Labels as Values, gcc.info, GNU C Manual}).
1.6       anton     401: 
1.13      anton     402: @c call threading
1.6       anton     403: @end table
                    404: 
1.12      anton     405: Threaded code can be twice as fast as switch dispatch, depending on the
                    406: interpreter, the benchmark, and the machine.
                    407: 
1.3       anton     408: @c *************************************************************
1.11      anton     409: @node Invoking Vmgen, Example, Concepts, Top
                    410: @chapter Invoking Vmgen
1.12      anton     411: @cindex Invoking Vmgen
1.3       anton     412: 
1.11      anton     413: The usual way to invoke Vmgen is as follows:
1.3       anton     414: 
                    415: @example
1.13      anton     416: vmgen @var{inputfile}
1.3       anton     417: @end example
                    418: 
1.13      anton     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}.
1.3       anton     428: 
1.11      anton     429: The command-line options supported by Vmgen are
1.3       anton     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: 
1.5       anton     448: @c ****************************************************************
1.11      anton     449: @node Example, Input File Format, Invoking Vmgen, Top
1.5       anton     450: @chapter Example
1.12      anton     451: @cindex example of a Vmgen-based interpreter
1.5       anton     452: 
1.10      anton     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
1.5       anton     460: @section Example overview
1.12      anton     461: @cindex example overview
                    462: @cindex @file{vmgen-ex}
                    463: @cindex @file{vmgen-ex2}
1.5       anton     464: 
1.11      anton     465: There are two versions of the same example for using Vmgen:
1.5       anton     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.
1.12      anton     470: 
1.5       anton     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
1.12      anton     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
1.5       anton     478: 
                    479: The files provided with each example are:
1.12      anton     480: @cindex example files
1.5       anton     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:
1.12      anton     506: @cindex wrapper files
1.5       anton     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: 
1.11      anton     517: @noindent
1.5       anton     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,
1.12      anton     531: and then typing @code{make}; you can check that it works with @code{make
1.5       anton     532: check}.  You can run run mini programs like this:
                    533: 
                    534: @example
                    535: ./mini fib.mini
                    536: @end example
                    537: 
1.12      anton     538: To learn about the options, type @code{./mini -h}.
1.5       anton     539: 
1.10      anton     540: @c --------------------------------------------------------------------
                    541: @node Using profiling to create superinstructions,  , Example overview, Example
1.5       anton     542: @section Using profiling to create superinstructions
1.12      anton     543: @cindex profiling example
                    544: @cindex superinstructions example
1.5       anton     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
1.12      anton     582: awk -f seq2rule.awk|  #transform sequences into superinstruction rules
1.5       anton     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
1.13      anton     589: precede larger superinstructions.
1.5       anton     590: 
                    591: Now you can create a version of mini with superinstructions by just
                    592: saying @samp{make}
                    593: 
1.10      anton     594: 
1.3       anton     595: @c ***************************************************************
1.13      anton     596: @node Input File Format, Error messages, Example, Top
1.3       anton     597: @chapter Input File Format
1.12      anton     598: @cindex input file format
                    599: @cindex format, input file
1.3       anton     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: 
1.5       anton     604: Most examples are taken from the example in @file{vmgen-ex}.
1.3       anton     605: 
1.10      anton     606: @menu
                    607: * Input File Grammar::          
                    608: * Simple instructions::         
                    609: * Superinstructions::           
1.18      anton     610: * Store Optimization::          
1.11      anton     611: * Register Machines::           How to define register VM instructions
1.10      anton     612: @end menu
                    613: 
                    614: @c --------------------------------------------------------------------
                    615: @node Input File Grammar, Simple instructions, Input File Format, Input File Format
1.3       anton     616: @section Input File Grammar
1.12      anton     617: @cindex grammar, input file
                    618: @cindex input file grammar
1.3       anton     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: 
1.12      anton     624: @cindex free-format, not
1.15      anton     625: @cindex newlines, significance in syntax
1.3       anton     626: Vmgen input is not free-format, so you have to take care where you put
1.15      anton     627: newlines (and, in a few cases, white space).
1.3       anton     628: 
                    629: @example
1.15      anton     630: description: @{instruction|comment|eval-escape|c-escape@}
1.3       anton     631: 
                    632: instruction: simple-inst|superinst
                    633: 
1.15      anton     634: simple-inst: ident '(' stack-effect ')' newline c-code newline newline
1.3       anton     635: 
1.15      anton     636: stack-effect: @{ident@} '--' @{ident@}
1.3       anton     637: 
1.15      anton     638: super-inst: ident '=' ident @{ident@}  
1.3       anton     639: 
1.12      anton     640: comment:      '\ '  text newline
1.3       anton     641: 
1.13      anton     642: eval-escape:  '\E ' text newline
1.15      anton     643: 
                    644: c-escape:     '\C ' text newline
1.3       anton     645: @end example
                    646: @c \+ \- \g \f \c
                    647: 
                    648: Note that the @code{\}s in this grammar are meant literally, not as
1.5       anton     649: C-style encodings for non-printable characters.
1.3       anton     650: 
1.15      anton     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.
1.3       anton     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: 
1.17      anton     693: @menu
                    694: * Eval escapes::                what follows \E
                    695: @end menu
                    696: 
                    697: @node Eval escapes,  , Input File Grammar, Input File Grammar
1.10      anton     698: @subsection Eval escapes
1.12      anton     699: @cindex escape to Forth
                    700: @cindex eval escape
1.15      anton     701: @cindex @code{\E}
1.13      anton     702: 
1.3       anton     703: @c woanders?
                    704: The text in @code{eval-escape} is Forth code that is evaluated when
1.13      anton     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:
1.3       anton     711: 
                    712: @example
1.18      anton     713: text: stack-decl|type-prefix-decl|stack-prefix-decl|set-flag
1.3       anton     714: 
1.12      anton     715: stack-decl: 'stack ' ident ident ident
1.3       anton     716: type-prefix-decl: 
1.12      anton     717:     's" ' string '" ' ('single'|'double') ident 'type-prefix' ident
                    718: stack-prefix-decl:  ident 'stack-prefix' string
1.22      anton     719: set-flag: ('store-optimization'|'include-skipped-insts') ('on'|'off')
1.3       anton     720: @end example
                    721: 
                    722: Note that the syntax of this code is not checked thoroughly (there are
1.13      anton     723: many other Forth program fragments that could be written in an
                    724: eval-escape).
1.3       anton     725: 
1.14      anton     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: 
1.3       anton     732: If you know Forth, the stack effects of the non-standard words involved
                    733: are:
1.12      anton     734: @findex stack
                    735: @findex type-prefix
                    736: @findex single
                    737: @findex double
                    738: @findex stack-prefix
1.18      anton     739: @findex store-optimization
1.3       anton     740: @example
1.22      anton     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 )
1.3       anton     749: @end example
                    750: 
1.14      anton     751: An @var{item-size} takes three cells on the stack.
1.5       anton     752: 
1.10      anton     753: @c --------------------------------------------------------------------
                    754: @node Simple instructions, Superinstructions, Input File Grammar, Input File Format
1.3       anton     755: @section Simple instructions
1.12      anton     756: @cindex simple VM instruction
                    757: @cindex instruction, simple VM
1.3       anton     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
1.12      anton     771: @cindex effect, stack
1.3       anton     772: The stack effect specifies that @code{sub} pulls two integers from the
1.12      anton     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
1.3       anton     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: 
1.12      anton     796: @cindex stack definition
                    797: @cindex defining a stack
1.3       anton     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: 
1.12      anton     805: @cindex stack basic type
                    806: @cindex basic type of a stack
                    807: @cindex type of a stack, basic
1.3       anton     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
1.12      anton     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
1.22      anton     813: (@pxref{VM engine}).  By default, stacks grow towards lower addresses in
                    814: Vmgen-erated interpreters (@pxref{Stack growth direction}).
1.3       anton     815: 
1.12      anton     816: @cindex stack prefix
                    817: @cindex prefix, stack
1.3       anton     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
1.5       anton     826: instruction stream (indicated by the prefix @code{#}), and pushes it on
1.3       anton     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: 
1.5       anton     834: This definition defines that the stack prefix @code{#} specifies the
1.3       anton     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: 
1.12      anton     839: @cindex instruction stream
1.3       anton     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: 
1.10      anton     847: @menu
                    848: * C Code Macros::               Macros recognized by Vmgen
                    849: * C Code restrictions::         Vmgen makes assumptions about C code
1.22      anton     850: * Stack growth direction::      is configurable per stack
1.10      anton     851: @end menu
                    852: 
                    853: @c --------------------------------------------------------------------
                    854: @node C Code Macros, C Code restrictions, Simple instructions, Simple instructions
                    855: @subsection C Code Macros
1.12      anton     856: @cindex macros recognized by Vmgen
                    857: @cindex basic block, VM level
1.5       anton     858: 
                    859: Vmgen recognizes the following strings in the C code part of simple
                    860: instructions:
                    861: 
1.12      anton     862: @table @code
1.5       anton     863: 
                    864: @item SET_IP
1.12      anton     865: @findex SET_IP
1.11      anton     866: As far as Vmgen is concerned, a VM instruction containing this ends a VM
1.5       anton     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
1.12      anton     871: @findex SUPER_END
                    872: This ends a basic block (for profiling), even if the instruction
                    873: contains no @code{SET_IP}.
1.5       anton     874: 
1.13      anton     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
1.12      anton     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
1.13      anton     881: @samp{INST_TAIL;}.  A typical example is a conditional VM branch:
1.5       anton     882: 
                    883: @example
1.11      anton     884: if (branch_condition) @{
1.13      anton     885:   SET_IP(target); INST_TAIL;
1.11      anton     886: @}
1.5       anton     887: /* implicit tail follows here */
                    888: @end example
                    889: 
1.13      anton     890: In this example, @samp{INST_TAIL;} is not strictly necessary, because there
1.5       anton     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
1.12      anton     895: @findex SUPER_CONTINUE
1.5       anton     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
1.11      anton     903: if (branch_condition) @{
1.13      anton     904:   SET_IP(target); INST_TAIL; /* now this INST_TAIL is necessary */
1.11      anton     905: @}
1.5       anton     906: SUPER_CONTINUE;
                    907: @end example
                    908: 
                    909: @end table
                    910: 
1.11      anton     911: Note that Vmgen is not smart about C-level tokenization, comments,
1.5       anton     912: strings, or conditional compilation, so it will interpret even a
                    913: commented-out SUPER_END as ending a basic block (or, e.g.,
1.13      anton     914: @samp{RESET_IP;} as @samp{SET_IP;}).  Conversely, Vmgen requires the literal
1.11      anton     915: presence of these strings; Vmgen will not see them if they are hiding in
1.5       anton     916: a C preprocessor macro.
                    917: 
                    918: 
1.10      anton     919: @c --------------------------------------------------------------------
1.22      anton     920: @node C Code restrictions, Stack growth direction, C Code Macros, Simple instructions
1.10      anton     921: @subsection C Code restrictions
1.12      anton     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
1.5       anton     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: 
1.12      anton     938: @cindex stack caching, restriction on C code
                    939: @cindex superinstructions, restrictions on components
1.5       anton     940: 
1.11      anton     941: @itemize @bullet
1.5       anton     942: 
                    943: @item
1.12      anton     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.
1.5       anton     954: @c sometimes flushing and/or reloading unnecessary
                    955: 
                    956: @item
1.11      anton     957: The Vmgen-erated code loads the stack items from stack-pointer-indexed
1.5       anton     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
1.13      anton     961: will not affect the variables, and your write may be overwritten by the
1.5       anton     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
1.12      anton     969: access a stack or stack pointer, as components of superinstructions
                    970: (@pxref{VM profiler}).
1.5       anton     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: 
1.22      anton     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.
1.5       anton    1007: 
1.10      anton    1008: @c --------------------------------------------------------------------
1.18      anton    1009: @node Superinstructions, Store Optimization, Simple instructions, Input File Format
1.3       anton    1010: @section Superinstructions
1.12      anton    1011: @cindex superinstructions, defining
                   1012: @cindex defining superinstructions
1.5       anton    1013: 
1.8       anton    1014: Note: don't invest too much work in (static) superinstructions; a future
1.11      anton    1015: version of Vmgen will support dynamic superinstructions (see Ian
1.8       anton    1016: Piumarta and Fabio Riccardi, @cite{Optimizing Direct Threaded Code by
                   1017: Selective Inlining}, PLDI'98), and static superinstructions have much
1.12      anton    1018: less benefit in that context (preliminary results indicate only a factor
                   1019: 1.1 speedup).
1.8       anton    1020: 
1.5       anton    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
1.11      anton    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}).
1.5       anton    1034: 
1.12      anton    1035: @cindex prefixes of superinstructions
1.5       anton    1036: Vmgen requires that the component instructions are simple instructions
1.11      anton    1037: defined before superinstructions using the components.  Currently, Vmgen
1.5       anton    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
1.12      anton    1043: foo4 = load add sub mul
1.5       anton    1044: @end example
                   1045: 
1.12      anton    1046: you first have to define @code{load}, @code{add}, @code{sub} and
                   1047: @code{mul}, plus
1.5       anton    1048: 
                   1049: @example
1.12      anton    1050: foo2 = load add
                   1051: foo3 = load add sub
1.5       anton    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: 
1.11      anton    1057: Note that Vmgen assumes that only the code it generates accesses stack
1.5       anton    1058: pointers, the instruction pointer, and various stack items, and it
                   1059: performs optimizations based on this assumption.  Therefore, VM
1.12      anton    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.
1.5       anton    1065: 
1.22      anton    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: 
1.12      anton    1071: @c -------------------------------------------------------------------
1.18      anton    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: 
1.22      anton    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: 
1.18      anton    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
1.11      anton    1137: @section Register Machines
1.12      anton    1138: @cindex Register VM
                   1139: @cindex Superinstructions for register VMs
                   1140: @cindex tracing of register VMs
1.11      anton    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: 
1.12      anton    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: 
1.11      anton    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
1.12      anton    1178: register numbers in tracing.  A disadvantage of this method is that
1.11      anton    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: 
1.5       anton    1190: @c ********************************************************************
1.13      anton    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
1.20      anton    1206: @item the prefix for this superinstruction must be defined earlier
1.13      anton    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
1.16      anton    1216: expected by Vmgen (this should not happen; please report the offending
                   1217: line in a bug report).
1.13      anton    1218: 
                   1219: @cindex @code{syntax error, wrong char} error
1.22      anton    1220: @item syntax error, wrong char
1.16      anton    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?
1.13      anton    1227: 
                   1228: @cindex @code{too many stacks} error
                   1229: @item too many stacks
1.16      anton    1230: Vmgen currently supports 3 stacks (plus the instruction stream); if you
                   1231: need more, let us know.
1.13      anton    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: 
1.22      anton    1239: @cindex @code{unknown primitive} error
1.13      anton    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
1.5       anton    1251: @chapter Using the generated code
1.12      anton    1252: @cindex generated code, usage
                   1253: @cindex Using vmgen-erated code
1.5       anton    1254: 
1.11      anton    1255: The easiest way to create a working VM interpreter with Vmgen is
1.12      anton    1256: probably to start with @file{vmgen-ex}, and modify it for your purposes.
1.13      anton    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.
1.5       anton    1261: 
1.10      anton    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
1.6       anton    1270: 
1.10      anton    1271: @c --------------------------------------------------------------------
                   1272: @node VM engine, VM instruction table, Using the generated code, Using the generated code
1.5       anton    1273: @section VM engine
1.12      anton    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
1.5       anton    1279: 
                   1280: The VM engine is the VM interpreter that executes the VM code.  It is
                   1281: essential for an interpretive system.
                   1282: 
1.6       anton    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: 
1.12      anton    1296: @cindex tracing VM code
1.13      anton    1297: @cindex superinstructions and tracing
1.12      anton    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: 
1.6       anton    1311: The following macros and variables are used in @file{@var{name}-vm.i}:
1.5       anton    1312: 
                   1313: @table @code
                   1314: 
1.12      anton    1315: @findex LABEL
1.5       anton    1316: @item LABEL(@var{inst_name})
                   1317: This is used just before each VM instruction to provide a jump or
1.11      anton    1318: @code{switch} label (the @samp{:} is provided by Vmgen).  For switch
1.13      anton    1319: dispatch this should expand to @samp{case @var{label}:}; for
                   1320: threaded-code dispatch this should just expand to @samp{@var{label}:}.
1.12      anton    1321: In either case @var{label} is usually the @var{inst_name} with some
                   1322: prefix or suffix to avoid naming conflicts.
1.5       anton    1323: 
1.12      anton    1324: @findex LABEL2
1.9       anton    1325: @item LABEL2(@var{inst_name})
                   1326: This will be used for dynamic superinstructions; at the moment, this
                   1327: should expand to nothing.
                   1328: 
1.12      anton    1329: @findex NAME
1.5       anton    1330: @item NAME(@var{inst_name_string})
                   1331: Called on entering a VM instruction with a string containing the name of
1.13      anton    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).
1.5       anton    1335: 
1.12      anton    1336: @findex DEF_CA
1.5       anton    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: 
1.12      anton    1343: @findex NEXT_P0
                   1344: @findex NEXT_P1
                   1345: @findex NEXT_P2
1.5       anton    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).
1.12      anton    1350: @samp{NEXT_P0} is invoked right at the start of the VM instruction (but
1.5       anton    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
1.13      anton    1353: performed by @samp{NEXT_P2} (if you would do it earlier, important parts
                   1354: of the VM instruction would not be executed).
1.5       anton    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
1.12      anton    1360: of a jump to the dispatch code (@samp{goto next_inst;} in our example);
1.5       anton    1361: for direct threaded code it consists of something like
1.11      anton    1362: @samp{(@{cfa=*ip++; goto *cfa;@})}.
1.5       anton    1363: 
1.12      anton    1364: Pulling code (usually the @samp{cfa=*ip++;}) up into @samp{NEXT_P1}
1.5       anton    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: 
1.12      anton    1372: @findex INC_IP
1.5       anton    1373: @item INC_IP(@var{n})
1.8       anton    1374: This increments @code{IP} by @var{n}.
                   1375: 
1.12      anton    1376: @findex SET_IP
1.8       anton    1377: @item SET_IP(@var{target})
                   1378: This sets @code{IP} to @var{target}.
1.5       anton    1379: 
1.12      anton    1380: @cindex type cast macro
                   1381: @findex vm_@var{A}2@var{B}
1.5       anton    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
1.12      anton    1390: define a vm_@var{X}2@var{X} macro for the stack's basic type @var{X}
                   1391: (used in superinstructions).
1.5       anton    1392: 
1.12      anton    1393: @cindex instruction stream, basic type
1.5       anton    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: 
1.12      anton    1399: @cindex unions in type cast macros
                   1400: @cindex casts in type cast macros
                   1401: @cindex type casting between floats and integers
1.5       anton    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
1.12      anton    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).
1.5       anton    1409: 
1.12      anton    1410: @findex vm_two@var{A}2@var{B}
                   1411: @findex vm_@var{B}2two@var{A}
1.5       anton    1412: @item vm_two@var{A}2@var{B}(a1,a2,b)
                   1413: @item vm_@var{B}2two@var{A}(b,a1,a2)
1.12      anton    1414: Type casting between two stack items (@code{a1}, @code{a2}) and a
1.5       anton    1415: variable @code{b} of a type that takes two stack items.  This does not
1.12      anton    1416: occur in our small examples, but you can look at Gforth for examples
                   1417: (see @code{vm_twoCell2d} in @file{engine/forth.h}).
1.5       anton    1418: 
1.12      anton    1419: @cindex stack pointer definition
                   1420: @cindex instruction pointer definition
1.5       anton    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
1.12      anton    1427: differences between the various implementations of @code{NEXT_P*}.
1.22      anton    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.
1.5       anton    1434: 
1.12      anton    1435: @cindex top of stack caching
                   1436: @cindex stack caching
                   1437: @cindex TOS
                   1438: @findex IPTOS
1.5       anton    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: 
1.12      anton    1447: @findex IF_@var{stackpointer}TOS
1.5       anton    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: 
1.12      anton    1454: @findex SUPER_END
1.8       anton    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: 
1.12      anton    1460: @findex SUPER_CONTINUE
1.8       anton    1461: @item SUPER_CONTINUE
1.11      anton    1462: This is just a hint to Vmgen and does nothing at the C level.
1.8       anton    1463: 
1.12      anton    1464: @findex VM_DEBUG
1.5       anton    1465: @item VM_DEBUG
                   1466: If this is defined, the tracing code will be compiled in (slower
                   1467: interpretation, but better debugging).  Our example compiles two
                   1468: versions of the engine, a fast-running one that cannot trace, and one
                   1469: with potential tracing and profiling.
                   1470: 
1.12      anton    1471: @findex vm_debug
1.5       anton    1472: @item vm_debug
                   1473: Needed only if @samp{VM_DEBUG} is defined.  If this variable contains
                   1474: true, the VM instructions produce trace output.  It can be turned on or
                   1475: off at any time.
                   1476: 
1.12      anton    1477: @findex vm_out
1.5       anton    1478: @item vm_out
                   1479: Needed only if @samp{VM_DEBUG} is defined.  Specifies the file on which
                   1480: to print the trace output (type @samp{FILE *}).
                   1481: 
1.12      anton    1482: @findex printarg_@var{type}
1.5       anton    1483: @item printarg_@var{type}(@var{value})
                   1484: Needed only if @samp{VM_DEBUG} is defined.  Macro or function for
                   1485: printing @var{value} in a way appropriate for the @var{type}.  This is
                   1486: used for printing the values of stack items during tracing.  @var{Type}
                   1487: is normally the type prefix specified in a @code{type-prefix} definition
                   1488: (e.g., @samp{printarg_i}); in superinstructions it is currently the
                   1489: basic type of the stack.
                   1490: 
                   1491: @end table
                   1492: 
1.6       anton    1493: 
1.10      anton    1494: @c --------------------------------------------------------------------
                   1495: @node VM instruction table, VM code generation, VM engine, Using the generated code
                   1496: @section VM instruction table
1.12      anton    1497: @cindex instruction table
                   1498: @cindex opcode definition
                   1499: @cindex labels for threaded code
                   1500: @cindex @code{vm_prim}, definition
                   1501: @cindex @file{-labels.i} output file
1.6       anton    1502: 
                   1503: For threaded code we also need to produce a table containing the labels
                   1504: of all VM instructions.  This is needed for VM code generation
                   1505: (@pxref{VM code generation}), and it has to be done in the engine
                   1506: function, because the labels are not visible outside.  It then has to be
                   1507: passed outside the function (and assigned to @samp{vm_prim}), to be used
                   1508: by the VM code generation functions.
                   1509: 
                   1510: This means that the engine function has to be called first to produce
                   1511: the VM instruction table, and later, after generating VM code, it has to
                   1512: be called again to execute the generated VM code (yes, this is ugly).
                   1513: In our example program, these two modes of calling the engine function
                   1514: are differentiated by the value of the parameter ip0 (if it equals 0,
                   1515: then the table is passed out, otherwise the VM code is executed); in our
                   1516: example, we pass the table out by assigning it to @samp{vm_prim} and
                   1517: returning from @samp{engine}.
                   1518: 
1.12      anton    1519: In our example (@file{vmgen-ex/engine.c}), we also build such a table for
                   1520: switch dispatch; this is mainly done for uniformity.
1.6       anton    1521: 
                   1522: For switch dispatch, we also need to define the VM instruction opcodes
                   1523: used as case labels in an @code{enum}.
                   1524: 
                   1525: For both purposes (VM instruction table, and enum), the file
1.11      anton    1526: @file{@var{name}-labels.i} is generated by Vmgen.  You have to define
1.6       anton    1527: the following macro used in this file:
1.5       anton    1528: 
1.12      anton    1529: @table @code
1.5       anton    1530: 
1.12      anton    1531: @findex INST_ADDR
1.5       anton    1532: @item INST_ADDR(@var{inst_name})
                   1533: For switch dispatch, this is just the name of the switch label (the same
1.6       anton    1534: name as used in @samp{LABEL(@var{inst_name})}), for both uses of
                   1535: @file{@var{name}-labels.i}.  For threaded-code dispatch, this is the
                   1536: address of the label defined in @samp{LABEL(@var{inst_name})}); the
1.11      anton    1537: address is taken with @samp{&&} (@pxref{Labels as Values, , Labels as
                   1538: Values, gcc.info, GNU C Manual}).
1.5       anton    1539: 
                   1540: @end table
                   1541: 
                   1542: 
1.10      anton    1543: @c --------------------------------------------------------------------
                   1544: @node VM code generation, Peephole optimization, VM instruction table, Using the generated code
1.6       anton    1545: @section VM code generation
1.12      anton    1546: @cindex VM code generation
                   1547: @cindex code generation, VM
                   1548: @cindex @file{-gen.i} output file
1.6       anton    1549: 
                   1550: Vmgen generates VM code generation functions in @file{@var{name}-gen.i}
                   1551: that the front end can call to generate VM code.  This is essential for
                   1552: an interpretive system.
                   1553: 
1.12      anton    1554: @findex gen_@var{inst}
1.11      anton    1555: For a VM instruction @samp{x ( #a b #c -- d )}, Vmgen generates a
1.6       anton    1556: function with the prototype
                   1557: 
                   1558: @example
                   1559: void gen_x(Inst **ctp, a_type a, c_type c)
                   1560: @end example
                   1561: 
                   1562: The @code{ctp} argument points to a pointer to the next instruction.
                   1563: @code{*ctp} is increased by the generation functions; i.e., you should
                   1564: allocate memory for the code to be generated beforehand, and start with
                   1565: *ctp set at the start of this memory area.  Before running out of
                   1566: memory, allocate a new area, and generate a VM-level jump to the new
1.12      anton    1567: area (this overflow handling is not implemented in our examples).
1.6       anton    1568: 
1.12      anton    1569: @cindex immediate arguments, VM code generation
1.6       anton    1570: The other arguments correspond to the immediate arguments of the VM
                   1571: instruction (with their appropriate types as defined in the
                   1572: @code{type_prefix} declaration.
                   1573: 
                   1574: The following types, variables, and functions are used in
                   1575: @file{@var{name}-gen.i}:
                   1576: 
1.12      anton    1577: @table @code
1.6       anton    1578: 
1.12      anton    1579: @findex Inst
1.6       anton    1580: @item Inst
                   1581: The type of the VM instruction; if you use threaded code, this is
                   1582: @code{void *}; for switch dispatch this is an integer type.
                   1583: 
1.12      anton    1584: @cindex @code{vm_prim}, use
1.6       anton    1585: @item vm_prim
                   1586: The VM instruction table (type: @code{Inst *}, @pxref{VM instruction table}).
                   1587: 
1.12      anton    1588: @findex gen_inst
1.6       anton    1589: @item gen_inst(Inst **ctp, Inst i)
                   1590: This function compiles the instruction @code{i}.  Take a look at it in
                   1591: @file{vmgen-ex/peephole.c}.  It is trivial when you don't want to use
                   1592: superinstructions (just the last two lines of the example function), and
                   1593: slightly more complicated in the example due to its ability to use
                   1594: superinstructions (@pxref{Peephole optimization}).
                   1595: 
1.12      anton    1596: @findex genarg_@var{type_prefix}
1.6       anton    1597: @item genarg_@var{type_prefix}(Inst **ctp, @var{type} @var{type_prefix})
                   1598: This compiles an immediate argument of @var{type} (as defined in a
                   1599: @code{type-prefix} definition).  These functions are trivial to define
                   1600: (see @file{vmgen-ex/support.c}).  You need one of these functions for
                   1601: every type that you use as immediate argument.
                   1602: 
                   1603: @end table
                   1604: 
1.12      anton    1605: @findex BB_BOUNDARY
1.6       anton    1606: In addition to using these functions to generate code, you should call
                   1607: @code{BB_BOUNDARY} at every basic block entry point if you ever want to
                   1608: use superinstructions (or if you want to use the profiling supported by
1.12      anton    1609: Vmgen; but this support is also useful mainly for selecting
                   1610: superinstructions).  If you use @code{BB_BOUNDARY}, you should also
                   1611: define it (take a look at its definition in @file{vmgen-ex/mini.y}).
1.6       anton    1612: 
                   1613: You do not need to call @code{BB_BOUNDARY} after branches, because you
                   1614: will not define superinstructions that contain branches in the middle
                   1615: (and if you did, and it would work, there would be no reason to end the
                   1616: superinstruction at the branch), and because the branches announce
                   1617: themselves to the profiler.
                   1618: 
                   1619: 
1.10      anton    1620: @c --------------------------------------------------------------------
                   1621: @node Peephole optimization, VM disassembler, VM code generation, Using the generated code
1.6       anton    1622: @section Peephole optimization
1.12      anton    1623: @cindex peephole optimization
                   1624: @cindex superinstructions, generating
                   1625: @cindex @file{peephole.c}
                   1626: @cindex @file{-peephole.i} output file
1.6       anton    1627: 
                   1628: You need peephole optimization only if you want to use
                   1629: superinstructions.  But having the code for it does not hurt much if you
                   1630: do not use superinstructions.
                   1631: 
                   1632: A simple greedy peephole optimization algorithm is used for
                   1633: superinstruction selection: every time @code{gen_inst} compiles a VM
1.12      anton    1634: instruction, it checks if it can combine it with the last VM instruction
1.6       anton    1635: (which may also be a superinstruction resulting from a previous peephole
                   1636: optimization); if so, it changes the last instruction to the combined
                   1637: instruction instead of laying down @code{i} at the current @samp{*ctp}.
                   1638: 
                   1639: The code for peephole optimization is in @file{vmgen-ex/peephole.c}.
                   1640: You can use this file almost verbatim.  Vmgen generates
                   1641: @file{@var{file}-peephole.i} which contains data for the peephoile
                   1642: optimizer.
                   1643: 
1.12      anton    1644: @findex init_peeptable
1.6       anton    1645: You have to call @samp{init_peeptable()} after initializing
                   1646: @samp{vm_prim}, and before compiling any VM code to initialize data
                   1647: structures for peephole optimization.  After that, compiling with the VM
                   1648: code generation functions will automatically combine VM instructions
                   1649: into superinstructions.  Since you do not want to combine instructions
                   1650: across VM branch targets (otherwise there will not be a proper VM
                   1651: instruction to branch to), you have to call @code{BB_BOUNDARY}
                   1652: (@pxref{VM code generation}) at branch targets.
                   1653: 
                   1654: 
1.10      anton    1655: @c --------------------------------------------------------------------
                   1656: @node VM disassembler, VM profiler, Peephole optimization, Using the generated code
1.6       anton    1657: @section VM disassembler
1.12      anton    1658: @cindex VM disassembler
                   1659: @cindex disassembler, VM code
                   1660: @cindex @file{disasm.c}
                   1661: @cindex @file{-disasm.i} output file
1.6       anton    1662: 
                   1663: A VM code disassembler is optional for an interpretive system, but
                   1664: highly recommended during its development and maintenance, because it is
                   1665: very useful for detecting bugs in the front end (and for distinguishing
                   1666: them from VM interpreter bugs).
                   1667: 
                   1668: Vmgen supports VM code disassembling by generating
                   1669: @file{@var{file}-disasm.i}.  This code has to be wrapped into a
1.12      anton    1670: function, as is done in @file{vmgen-ex/disasm.c}.  You can use this file
1.6       anton    1671: almost verbatim.  In addition to @samp{vm_@var{A}2@var{B}(a,b)},
                   1672: @samp{vm_out}, @samp{printarg_@var{type}(@var{value})}, which are
                   1673: explained above, the following macros and variables are used in
                   1674: @file{@var{file}-disasm.i} (and you have to define them):
                   1675: 
1.12      anton    1676: @table @code
1.6       anton    1677: 
                   1678: @item ip
                   1679: This variable points to the opcode of the current VM instruction.
                   1680: 
1.12      anton    1681: @cindex @code{IP}, @code{IPTOS} in disassmbler
1.6       anton    1682: @item IP IPTOS
                   1683: @samp{IPTOS} is the first argument of the current VM instruction, and
                   1684: @samp{IP} points to it; this is just as in the engine, but here
                   1685: @samp{ip} points to the opcode of the VM instruction (in contrast to the
                   1686: engine, where @samp{ip} points to the next cell, or even one further).
                   1687: 
1.12      anton    1688: @findex VM_IS_INST
1.6       anton    1689: @item VM_IS_INST(Inst i, int n)
                   1690: Tests if the opcode @samp{i} is the same as the @samp{n}th entry in the
                   1691: VM instruction table.
                   1692: 
                   1693: @end table
                   1694: 
                   1695: 
1.10      anton    1696: @c --------------------------------------------------------------------
                   1697: @node VM profiler,  , VM disassembler, Using the generated code
1.7       anton    1698: @section VM profiler
1.12      anton    1699: @cindex VM profiler
                   1700: @cindex profiling for selecting superinstructions
                   1701: @cindex superinstructions and profiling
                   1702: @cindex @file{profile.c}
                   1703: @cindex @file{-profile.i} output file
1.7       anton    1704: 
                   1705: The VM profiler is designed for getting execution and occurence counts
                   1706: for VM instruction sequences, and these counts can then be used for
                   1707: selecting sequences as superinstructions.  The VM profiler is probably
1.8       anton    1708: not useful as profiling tool for the interpretive system.  I.e., the VM
1.7       anton    1709: profiler is useful for the developers, but not the users of the
1.8       anton    1710: interpretive system.
1.7       anton    1711: 
1.8       anton    1712: The output of the profiler is: for each basic block (executed at least
                   1713: once), it produces the dynamic execution count of that basic block and
                   1714: all its subsequences; e.g.,
1.7       anton    1715: 
1.8       anton    1716: @example
                   1717:        9227465  lit storelocal 
                   1718:        9227465  storelocal branch 
                   1719:        9227465  lit storelocal branch 
                   1720: @end example
1.7       anton    1721: 
1.8       anton    1722: I.e., a basic block consisting of @samp{lit storelocal branch} is
                   1723: executed 9227465 times.
1.6       anton    1724: 
1.12      anton    1725: @cindex @file{stat.awk}
                   1726: @cindex @file{seq2rule.awk}
1.8       anton    1727: This output can be combined in various ways.  E.g.,
1.12      anton    1728: @file{vmgen-ex/stat.awk} adds up the occurences of a given sequence wrt
1.8       anton    1729: dynamic execution, static occurence, and per-program occurence.  E.g.,
1.3       anton    1730: 
1.8       anton    1731: @example
                   1732:       2      16        36910041 loadlocal lit 
                   1733: @end example
1.2       anton    1734: 
1.12      anton    1735: @noindent
1.8       anton    1736: indicates that the sequence @samp{loadlocal lit} occurs in 2 programs,
                   1737: in 16 places, and has been executed 36910041 times.  Now you can select
                   1738: superinstructions in any way you like (note that compile time and space
                   1739: typically limit the number of superinstructions to 100--1000).  After
                   1740: you have done that, @file{vmgen/seq2rule.awk} turns lines of the form
1.11      anton    1741: above into rules for inclusion in a Vmgen input file.  Note that this
1.8       anton    1742: script does not ensure that all prefixes are defined, so you have to do
                   1743: that in other ways.  So, an overall script for turning profiles into
                   1744: superinstructions can look like this:
1.2       anton    1745: 
1.8       anton    1746: @example
                   1747: awk -f stat.awk fib.prof test.prof|
                   1748: awk '$3>=10000'|                #select sequences
                   1749: fgrep -v -f peephole-blacklist| #eliminate wrong instructions
                   1750: awk -f seq2rule.awk|            #turn into superinstructions
                   1751: sort -k 3 >mini-super.vmg       #sort sequences
                   1752: @end example
1.2       anton    1753: 
1.8       anton    1754: Here the dynamic count is used for selecting sequences (preliminary
                   1755: results indicate that the static count gives better results, though);
1.12      anton    1756: the third line eliminates sequences containing instructions that must not
1.8       anton    1757: occur in a superinstruction, because they access a stack directly.  The
                   1758: dynamic count selection ensures that all subsequences (including
                   1759: prefixes) of longer sequences occur (because subsequences have at least
                   1760: the same count as the longer sequences); the sort in the last line
                   1761: ensures that longer superinstructions occur after their prefixes.
                   1762: 
1.12      anton    1763: But before using this, you have to have the profiler.  Vmgen supports its
1.8       anton    1764: creation by generating @file{@var{file}-profile.i}; you also need the
                   1765: wrapper file @file{vmgen-ex/profile.c} that you can use almost verbatim.
                   1766: 
1.12      anton    1767: @cindex @code{SUPER_END} in profiling
                   1768: @cindex @code{BB_BOUNDARY} in profiling
1.8       anton    1769: The profiler works by recording the targets of all VM control flow
                   1770: changes (through @code{SUPER_END} during execution, and through
                   1771: @code{BB_BOUNDARY} in the front end), and counting (through
                   1772: @code{SUPER_END}) how often they were targeted.  After the program run,
                   1773: the numbers are corrected such that each VM basic block has the correct
1.12      anton    1774: count (entering a block without executing a branch does not increase the
                   1775: count, and the correction fixes that), then the subsequences of all
                   1776: basic blocks are printed.  To get all this, you just have to define
                   1777: @code{SUPER_END} (and @code{BB_BOUNDARY}) appropriately, and call
                   1778: @code{vm_print_profile(FILE *file)} when you want to output the profile
                   1779: on @code{file}.
1.8       anton    1780: 
1.12      anton    1781: @cindex @code{VM_IS_INST} in profiling
                   1782: The @file{@var{file}-profile.i} is similar to the disassembler file, and
1.8       anton    1783: it uses variables and functions defined in @file{vmgen-ex/profile.c},
                   1784: plus @code{VM_IS_INST} already defined for the VM disassembler
                   1785: (@pxref{VM disassembler}).
                   1786: 
1.13      anton    1787: @c **********************************************************
                   1788: @node Hints, The future, Using the generated code, Top
                   1789: @chapter Hints
                   1790: @cindex hints
                   1791: 
                   1792: @menu
                   1793: * Floating point::              and stacks
                   1794: @end menu
                   1795: 
                   1796: @c --------------------------------------------------------------------
                   1797: @node Floating point,  , Hints, Hints
                   1798: @section Floating point
                   1799: 
                   1800: How should you deal with floating point values?  Should you use the same
                   1801: stack as for integers/pointers, or a different one?  This section
                   1802: discusses this issue with a view on execution speed.
                   1803: 
                   1804: The simpler approach is to use a separate floating-point stack.  This
                   1805: allows you to choose FP value size without considering the size of the
                   1806: integers/pointers, and you avoid a number of performance problems.  The
                   1807: main downside is that this needs an FP stack pointer (and that may not
                   1808: fit in the register file on the 386 arhitecture, costing some
                   1809: performance, but comparatively little if you take the other option into
                   1810: account).  If you use a separate FP stack (with stack pointer @code{fp}),
                   1811: using an fpTOS is helpful on most machines, but some spill the fpTOS
                   1812: register into memory, and fpTOS should not be used there.
                   1813: 
                   1814: The other approach is to share one stack (pointed to by, say, @code{sp})
                   1815: between integer/pointer and floating-point values.  This is ok if you do
                   1816: not use @code{spTOS}.  If you do use @code{spTOS}, the compiler has to
                   1817: decide whether to put that variable into an integer or a floating point
                   1818: register, and the other type of operation becomes quite expensive on
                   1819: most machines (because moving values between integer and FP registers is
                   1820: quite expensive).  If a value of one type has to be synthesized out of
                   1821: two values of the other type (@code{double} types), things are even more
                   1822: interesting.
                   1823: 
                   1824: One way around this problem would be to not use the @code{spTOS}
                   1825: supported by Vmgen, but to use explicit top-of-stack variables (one for
                   1826: integers, one for FP values), and having a kind of accumulator+stack
                   1827: architecture (e.g., Ocaml bytecode uses this approach); however, this is
                   1828: a major change, and it's ramifications are not completely clear.
1.10      anton    1829: 
                   1830: @c **********************************************************
1.13      anton    1831: @node The future, Changes, Hints, Top
                   1832: @chapter The future
                   1833: @cindex future ideas
                   1834: 
1.21      anton    1835: We have a number of ideas for future versions of Vmgen.  However, there
1.13      anton    1836: are so many possible things to do that we would like some feedback from
                   1837: you.  What are you doing with Vmgen, what features are you missing, and
                   1838: why?
                   1839: 
                   1840: One idea we are thinking about is to generate just one @file{.c} file
                   1841: instead of letting you copy and adapt all the wrapper files (you would
                   1842: still have to define stuff like the type-specific macros, and stack
                   1843: pointers etc. somewhere).  The advantage would be that, if we change the
                   1844: wrapper files between versions, you would not need to integrate your
                   1845: changes and our changes to them; Vmgen would also be easier to use for
                   1846: beginners.  The main disadvantage of that is that it would reduce the
                   1847: flexibility of Vmgen a little (well, those who like flexibility could
                   1848: still patch the resulting @file{.c} file, like they are now doing for
                   1849: the wrapper files).  In any case, if you are doing things to the wrapper
                   1850: files that would cause problems in a generated-@file{.c}-file approach,
                   1851: please let us know.
                   1852: 
                   1853: @c **********************************************************
                   1854: @node Changes, Contact, The future, Top
1.8       anton    1855: @chapter Changes
1.12      anton    1856: @cindex Changes from old versions
1.8       anton    1857: 
1.19      anton    1858: User-visible changes between 0.5.9-20020822 and 0.5.9-20020901:
                   1859: 
                   1860: The store optimization is now disabled by default, but can be enabled by
                   1861: the user (@pxref{Store Optimization}).  Documentation for this
                   1862: optimization is also new.
                   1863: 
                   1864: User-visible changes between 0.5.9-20010501 and 0.5.9-20020822:
1.17      anton    1865: 
                   1866: There is now a manual (in info, HTML, Postscript, or plain text format).
                   1867: 
                   1868: There is the vmgen-ex2 variant of the vmgen-ex example; the new
                   1869: variant uses a union type instead of lots of casting.
                   1870: 
                   1871: Both variants of the example can now be compiled with an ANSI C compiler
                   1872: (using switch dispatch and losing quite a bit of performance); tested
                   1873: with @command{lcc}.
                   1874: 
1.11      anton    1875: Users of the gforth-0.5.9-20010501 version of Vmgen need to change
1.8       anton    1876: several things in their source code to use the current version.  I
                   1877: recommend keeping the gforth-0.5.9-20010501 version until you have
                   1878: completed the change (note that you can have several versions of Gforth
                   1879: installed at the same time).  I hope to avoid such incompatible changes
                   1880: in the future.
1.2       anton    1881: 
1.8       anton    1882: The required changes are:
                   1883: 
                   1884: @table @code
1.13      anton    1885: 
                   1886: @cindex @code{TAIL;}, changes
                   1887: @item TAIL;
                   1888: has been renamed into @code{INST_TAIL;} (less chance of an accidental
                   1889: match).
1.2       anton    1890: 
1.12      anton    1891: @cindex @code{vm_@var{A}2@var{B}}, changes
1.8       anton    1892: @item vm_@var{A}2@var{B}
                   1893: now takes two arguments.
                   1894: 
1.12      anton    1895: @cindex @code{vm_two@var{A}2@var{B}}, changes
1.8       anton    1896: @item vm_two@var{A}2@var{B}(b,a1,a2);
                   1897: changed to vm_two@var{A}2@var{B}(a1,a2,b) (note the absence of the @samp{;}).
                   1898: 
                   1899: @end table
1.2       anton    1900: 
1.8       anton    1901: Also some new macros have to be defined, e.g., @code{INST_ADDR}, and
                   1902: @code{LABEL}; some macros have to be defined in new contexts, e.g.,
                   1903: @code{VM_IS_INST} is now also needed in the disassembler.
1.4       anton    1904: 
1.12      anton    1905: @c *********************************************************
1.10      anton    1906: @node Contact, Copying This Manual, Changes, Top
1.8       anton    1907: @chapter Contact
1.17      anton    1908: 
                   1909: To report a bug, use
                   1910: @url{https://savannah.gnu.org/bugs/?func=addbug&group_id=2672}.
                   1911: 
                   1912: For discussion on Vmgen (e.g., how to use it), use the mailing list
                   1913: @email{bug-vmgen@@mail.freesoftware.fsf.org} (use
                   1914: @url{http://mail.gnu.org/mailman/listinfo/help-vmgen} to subscribe).
                   1915: 
                   1916: You can find vmgen information at
                   1917: @url{http://www.complang.tuwien.ac.at/anton/vmgen/}.
1.4       anton    1918: 
1.12      anton    1919: @c ***********************************************************
1.10      anton    1920: @node Copying This Manual, Index, Contact, Top
                   1921: @appendix Copying This Manual
                   1922: 
                   1923: @menu
                   1924: * GNU Free Documentation License::  License for copying this manual.
                   1925: @end menu
                   1926: 
                   1927: @include fdl.texi
                   1928: 
                   1929: 
                   1930: @node Index,  , Copying This Manual, Top
                   1931: @unnumbered Index
                   1932: 
                   1933: @printindex cp
                   1934: 
                   1935: @bye

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