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