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

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

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