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