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