[gforth] / gforth / doc / vmgen.texi

gforth: gforth/doc/vmgen.texi

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

CVS Admin

gforth: gforth/doc/vmgen.texi

ViewCVS and CVS Help