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