text: ,2008: This feature is not needed and not supported in the 0.6.2 version of 864: vmgen that is documented here (and that is invoked by default). 865: 866: Not all stack effects can be specified using the stack effect 867: specifications above. For VM instructions that have other stack 868: effects, you can specify them explicitly by accessing the stack 869: pointer in the C code; however, you have to notify Vmgen of such 870: explicit stack accesses, otherwise Vmgens optimizations could conflict 871: with your explicit stack accesses. 872: 873: You notify Vmgen by putting @code{...} with the appropriate stack 874: prefix into the stack comment. Then the VM instruction will first 875: take the other stack items specified in the stack effect into C 876: variables, then make sure that all other stack items for that stack 877: are in memory, and that the stack pointer for the stack points to the 878: top-of-stack (by default, unless you change the stack access 879: transformation: @pxref{Stack growth direction}). 880: 881: The general rule is: If you mention a stack pointer in the C code of a 882: VM instruction, you should put a @code{...} for that stack in the stack 883: effect. 884: 885: Consider this example: 886: 887: @example 888: return ( #iadjust S:... target afp i1 -- i2 ) 889: SET_IP(target); 890: sp = (Cell *)(((char *)sp)+iadjust); 891: fp = afp; 892: i2=i1; 893: @end example 894: 895: First the variables @code{target afp i1} are popped off the stack, 896: then the stack pointer @code{sp} is set correctly for the new stack 897: depth, then the C code changes the stack depth and does other things, 898: and finally @code{i2} is pushed on the stack with the new depth. 899: 900: The position of the @code{...} within the stack effect does not 901: matter. You can use several @code{...}s, for different stacks, and 902: also several for the same stack (that has no additional effect). If 903: you use @code{...} without a stack prefix, this specifies all the 904: stacks except the instruction stream. 905: 906: You cannot use @code{...} for the instruction stream, but that is not 907: necessary: At the start of the C code, @code{IP} points to the start 908: of the next VM instruction (i.e., right beyond the end of the current 909: VM instruction), and you can change the instruction pointer with 910: @code{SET_IP} (@pxref{VM engine}). 911: 912: 913: @c -------------------------------------------------------------------- 914: @node C Code Macros, C Code restrictions, Explicit stack access, Simple instructions 915: @subsection C Code Macros 916: @cindex macros recognized by Vmgen 917: @cindex basic block, VM level 918: 919: Vmgen recognizes the following strings in the C code part of simple 920: instructions: 921: 922: @table @code 923: 924: @item SET_IP 925: @findex SET_IP 926: As far as Vmgen is concerned, a VM instruction containing this ends a VM 927: basic block (used in profiling to delimit profiled sequences). On the C 928: level, this also sets the instruction pointer. 929: 930: @item SUPER_END 931: @findex SUPER_END 932: This ends a basic block (for profiling), even if the instruction 933: contains no @code{SET_IP}. 934: 935: @item INST_TAIL; 936: @findex INST_TAIL; 937: Vmgen replaces @samp{INST_TAIL;} with code for ending a VM instruction and 938: dispatching the next VM instruction. Even without a @samp{INST_TAIL;} this 939: happens automatically when control reaches the end of the C code. If 940: you want to have this in the middle of the C code, you need to use 941: @samp{INST_TAIL;}. A typical example is a conditional VM branch: 942: 943: @example 944: if (branch_condition) @{ 945: SET_IP(target); INST_TAIL; 946: @} 947: /* implicit tail follows here */ 948: @end example 949: 950: In this example, @samp{INST_TAIL;} is not strictly necessary, because there 951: is another one implicitly after the if-statement, but using it improves 952: branch prediction accuracy slightly and allows other optimizations. 953: 954: @item SUPER_CONTINUE 955: @findex SUPER_CONTINUE 956: This indicates that the implicit tail at the end of the VM instruction 957: dispatches the sequentially next VM instruction even if there is a 958: @code{SET_IP} in the VM instruction. This enables an optimization that 959: is not yet implemented in the vmgen-ex code (but in Gforth). The 960: typical application is in conditional VM branches: 961: 962: @example 963: if (branch_condition) @{ 964: SET_IP(target); INST_TAIL; /* now this INST_TAIL is necessary */ 965: @} 966: SUPER_CONTINUE; 967: @end example 968: 969: @c !! uncomment for post-0.6.2 docs 970: @c @item VM_JUMP 971: @c @findex VM_JUMP 972: @c @code{VM_JUMP(target)} is equivalent to @code{goto *(target)}, but 973: @c allows Vmgen to do dynamic superinstructions and replication. You 974: @c still need to say @code{SUPER_END}. Also, the goto only happens at 975: @c the end (wherever the VM_JUMP is). Essentially, this just suppresses 976: @c much of the ordinary dispatch mechanism. 977: 978: @end table 979: 980: Note that Vmgen is not smart about C-level tokenization, comments, 981: strings, or conditional compilation, so it will interpret even a 982: commented-out SUPER_END as ending a basic block (or, e.g., 983: @samp{RESET_IP;} as @samp{SET_IP;}). Conversely, Vmgen requires the literal 984: presence of these strings; Vmgen will not see them if they are hiding in 985: a C preprocessor macro. 986: 987: 988: @c -------------------------------------------------------------------- 989: @node C Code restrictions, Stack growth direction, C Code Macros, Simple instructions 990: @subsection C Code restrictions 991: @cindex C code restrictions 992: @cindex restrictions on C code 993: @cindex assumptions about C code 994: 995: @cindex accessing stack (pointer) 996: @cindex stack pointer, access 997: @cindex instruction pointer, access 998: Vmgen generates code and performs some optimizations under the 999: assumption that the user-supplied C code does not access the stack 1000: pointers or stack items, and that accesses to the instruction pointer 1001: only occur through special macros. In general you should heed these 1002: restrictions. However, if you need to break these restrictions, read 1003: the following. 1004: 1005: Accessing a stack or stack pointer directly can be a problem for several 1006: reasons: 1007: @cindex stack caching, restriction on C code 1008: @cindex superinstructions, restrictions on components 1009: 1010: @itemize @bullet 1011: 1012: @item 1013: Vmgen optionally supports caching the top-of-stack item in a local 1014: variable (that is allocated to a register). This is the most frequent 1015: source of trouble. You can deal with it either by not using 1016: top-of-stack caching (slowdown factor 1-1.4, depending on machine), or 1017: by inserting flushing code (e.g., @samp{IF_spTOS(sp[...] = spTOS);}) at 1018: the start and reloading code (e.g., @samp{IF_spTOS(spTOS = sp[0])}) at 1019: the end of problematic C code. Vmgen inserts a stack pointer update 1020: before the start of the user-supplied C code, so the flushing code has 1021: to use an index that corrects for that. In the future, this flushing 1022: may be done automatically by mentioning a special string in the C code. 1023: @c sometimes flushing and/or reloading unnecessary 1024: 1025: @item 1026: The Vmgen-erated code loads the stack items from stack-pointer-indexed 1027: memory into variables before the user-supplied C code, and stores them 1028: from variables to stack-pointer-indexed memory afterwards. If you do 1029: any writes to the stack through its stack pointer in your C code, it 1030: will not affect the variables, and your write may be overwritten by the 1031: stores after the C code. Similarly, a read from a stack using a stack 1032: pointer will not reflect computations of stack items in the same VM 1033: instruction. 1034: 1035: @item 1036: Superinstructions keep stack items in variables across the whole 1037: superinstruction. So you should not include VM instructions, that 1038: access a stack or stack pointer, as components of superinstructions 1039: (@pxref{VM profiler}). 1040: 1041: @end itemize 1042: 1043: You should access the instruction pointer only through its special 1044: macros (@samp{IP}, @samp{SET_IP}, @samp{IPTOS}); this ensure that these 1045: macros can be implemented in several ways for best performance. 1046: @samp{IP} points to the next instruction, and @samp{IPTOS} is its 1047: contents. 1048: 1049: @c -------------------------------------------------------------------- 1050: @node Stack growth direction, , C Code restrictions, Simple instructions 1051: @subsection Stack growth direction 1052: @cindex stack growth direction 1053: 1054: @cindex @code{stack-access-transform} 1055: By default, the stacks grow towards lower addresses. You can change 1056: this for a stack by setting the @code{stack-access-transform} field of 1057: the stack to an xt @code{( itemnum -- index )} that performs the 1058: appropriate index transformation. 1059: 1060: E.g., if you want to let @code{data-stack} grow towards higher 1061: addresses, with the stack pointer always pointing just beyond the 1062: top-of-stack, use this right after defining @code{data-stack}: 1063: 1064: @example 1065: \E : sp-access-transform ( itemnum -- index ) negate 1- ; 1066: \E ' sp-access-transform ' data-stack >body stack-access-transform ! 1067: @end example 1068: 1069: This means that @code{sp-access-transform} will be used to generate 1070: indexes for accessing @code{data-stack}. The definition of 1071: @code{sp-access-transform} above transforms n into -n-1, e.g, 1 into -2. 1072: This will access the 0th data-stack element (top-of-stack) at sp[-1], 1073: the 1st at sp[-2], etc., which is the typical way upward-growing 1074: stacks are used. If you need a different transform and do not know 1075: enough Forth to program it, let me know. 1076: 1077: @c -------------------------------------------------------------------- 1078: @node Superinstructions, Store Optimization, Simple instructions, Input File Format 1079: @section Superinstructions 1080: @cindex superinstructions, defining 1081: @cindex defining superinstructions 1082: 1083: Note: don't invest too much work in (static) superinstructions; a future 1084: version of Vmgen will support dynamic superinstructions (see Ian 1085: Piumarta and Fabio Riccardi, @cite{Optimizing Direct Threaded Code by 1086: Selective Inlining}, PLDI'98), and static superinstructions have much 1087: less benefit in that context (preliminary results indicate only a factor 1088: 1.1 speedup). 1089: 1090: Here is an example of a superinstruction definition: 1091: 1092: @example 1093: lit_sub = lit sub 1094: @end example 1095: 1096: @code{lit_sub} is the name of the superinstruction, and @code{lit} and 1097: @code{sub} are its components. This superinstruction performs the same 1098: action as the sequence @code{lit} and @code{sub}. It is generated 1099: automatically by the VM code generation functions whenever that sequence 1100: occurs, so if you want to use this superinstruction, you just need to 1101: add this definition (and even that can be partially automatized, 1102: @pxref{VM profiler}). 1103: 1104: @cindex prefixes of superinstructions 1105: Vmgen requires that the component instructions are simple instructions 1106: defined before superinstructions using the components. Currently, Vmgen 1107: also requires that all the subsequences at the start of a 1108: superinstruction (prefixes) must be defined as superinstruction before 1109: the superinstruction. I.e., if you want to define a superinstruction 1110: 1111: @example 1112: foo4 = load add sub mul 1113: @end example 1114: 1115: you first have to define @code{load}, @code{add}, @code{sub} and 1116: @code{mul}, plus 1117: 1118: @example 1119: foo2 = load add 1120: foo3 = load add sub 1121: @end example 1122: 1123: Here, @code{sumof4} is the longest prefix of @code{sumof5}, and @code{sumof3} 1124: is the longest prefix of @code{sumof4}. 1125: 1126: Note that Vmgen assumes that only the code it generates accesses stack 1127: pointers, the instruction pointer, and various stack items, and it 1128: performs optimizations based on this assumption. Therefore, VM 1129: instructions where your C code changes the instruction pointer should 1130: only be used as last component; a VM instruction where your C code 1131: accesses a stack pointer should not be used as component at all. Vmgen 1132: does not check these restrictions, they just result in bugs in your 1133: interpreter. 1134: 1135: @cindex include-skipped-insts 1136: The Vmgen flag @code{include-skipped-insts} influences superinstruction 1137: code generation. Currently there is no support in the peephole 1138: optimizer for both variations, so leave this flag alone for now. 1139: 1140: @c ------------------------------------------------------------------- 1141: @node Store Optimization, Register Machines, Superinstructions, Input File Format 1142: @section Store Optimization 1143: @cindex store optimization 1144: @cindex optimization, stack stores 1145: @cindex stack stores, optimization 1146: @cindex eliminating stack stores 1147: 1148: This minor optimization (0.6%--0.8% reduction in executed instructions 1149: for Gforth) puts additional requirements on the instruction descriptions 1150: and is therefore disabled by default. 1151: 1152: What does it do? Consider an instruction like 1153: 1154: @example 1155: dup ( n -- n n ) 1156: @end example 1157: 1158: For simplicity, also assume that we are not caching the top-of-stack in 1159: a register. Now, the C code for dup first loads @code{n} from the 1160: stack, and then stores it twice to the stack, one time to the address 1161: where it came from; that time is unnecessary, but gcc does not optimize 1162: it away, so vmgen can do it instead (if you turn on the store 1163: optimization). 1164: 1165: Vmgen uses the stack item's name to determine if the stack item contains 1166: the same value as it did at the start. Therefore, if you use the store 1167: optimization, you have to ensure that stack items that have the same 1168: name on input and output also have the same value, and are not changed 1169: in the C code you supply. I.e., the following code could fail if you 1170: turn on the store optimization: 1171: 1172: @example 1173: add1 ( n -- n ) 1174: n++; 1175: @end example 1176: 1177: Instead, you have to use different names, i.e.: 1178: 1179: @example 1180: add1 ( n1 -- n2 ) 1181: n2=n1+1; 1182: @end example 1183: 1184: Similarly, the store optimization assumes that the stack pointer is only 1185: changed by Vmgen-erated code. If your C code changes the stack pointer, 1186: use different names in input and output stack items to avoid a (probably 1187: wrong) store optimization, or turn the store optimization off for this 1188: VM instruction. 1189: 1190: To turn on the store optimization, write 1191: 1192: @example 1193: \E store-optimization on 1194: @end example 1195: 1196: at the start of the file. You can turn this optimization on or off 1197: between any two VM instruction descriptions. For turning it off again, 1198: you can use 1199: 1200: @example 1201: \E store-optimization off 1202: @end example 1203: 1204: @c ------------------------------------------------------------------- 1205: @node Register Machines, , Store Optimization, Input File Format 1206: @section Register Machines 1207: @cindex Register VM 1208: @cindex Superinstructions for register VMs 1209: @cindex tracing of register VMs 1210: 1211: If you want to implement a register VM rather than a stack VM with 1212: Vmgen, there are two ways to do it: Directly and through 1213: superinstructions. 1214: 1215: If you use the direct way, you define instructions that take the 1216: register numbers as immediate arguments, like this: 1217: 1218: @example 1219: add3 ( #src1 #src2 #dest -- ) 1220: reg[dest] = reg[src1]+reg[src2]; 1221: @end example 1222: 1223: A disadvantage of this method is that during tracing you only see the 1224: register numbers, but not the register contents. Actually, with an 1225: appropriate definition of @code{printarg_src} (@pxref{VM engine}), you 1226: can print the values of the source registers on entry, but you cannot 1227: print the value of the destination register on exit. 1228: 1229: If you use superinstructions to define a register VM, you define simple 1230: instructions that use a stack, and then define superinstructions that 1231: have no overall stack effect, like this: 1232: 1233: @example 1234: loadreg ( #src -- n ) 1235: n = reg[src]; 1236: 1237: storereg ( n #dest -- ) 1238: reg[dest] = n; 1239: 1240: adds ( n1 n2 -- n ) 1241: n = n1+n2; 1242: 1243: add3 = loadreg loadreg adds storereg 1244: @end example 1245: 1246: An advantage of this method is that you see the values and not just the 1247: register numbers in tracing. A disadvantage of this method is that 1248: currently you cannot generate superinstructions directly, but only 1249: through generating a sequence of simple instructions (we might change 1250: this in the future if there is demand). 1251: 1252: Could the register VM support be improved, apart from the issues 1253: mentioned above? It is hard to see how to do it in a general way, 1254: because there are a number of different designs that different people 1255: mean when they use the term @emph{register machine} in connection with 1256: VM interpreters. However, if you have ideas or requests in that 1257: direction, please let me know (@pxref{Contact}). 1258: 1259: @c ******************************************************************** 1260: @node Error messages, Using the generated code, Input File Format, Top 1261: @chapter Error messages 1262: @cindex error messages 1263: 1264: These error messages are created by Vmgen: 1265: 1266: @table @code 1267: 1268: @cindex @code{# can only be on the input side} error 1269: @item # can only be on the input side 1270: You have used an instruction-stream prefix (usually @samp{#}) after the 1271: @samp{--} (the output side); you can only use it before (the input 1272: side). 1273: 1274: @cindex @code{prefix for this combination must be defined earlier} error 1275: @item the prefix for this superinstruction must be defined earlier 1276: You have defined a superinstruction (e.g. @code{abc = a b c}) without 1277: defining its direct prefix (e.g., @code{ab = a b}), 1278: @xref{Superinstructions}. 1279: 1280: @cindex @code{sync line syntax} error 1281: @item sync line syntax 1282: If you are using a preprocessor (e.g., @command{m4}) to generate Vmgen 1283: input code, you may want to create @code{#line} directives (aka sync 1284: lines). This error indicates that such a line is not in th syntax 1285: expected by Vmgen (this should not happen; please report the offending 1286: line in a bug report). 1287: 1288: @cindex @code{syntax error, wrong char} error 1289: @item syntax error, wrong char 1290: A syntax error. If you do not see right away where the error is, it may 1291: be helpful to check the following: Did you put an empty line in a VM 1292: instruction where the C code is not delimited by braces (then the empty 1293: line ends the VM instruction)? If you used brace-delimited C code, did 1294: you put the delimiting braces (and only those) at the start of the line, 1295: without preceding white space? Did you forget a delimiting brace? 1296: 1297: @cindex @code{too many stacks} error 1298: @item too many stacks 1299: Vmgen currently supports 3 stacks (plus the instruction stream); if you 1300: need more, let us know. 1301: 1302: @cindex @code{unknown prefix} error 1303: @item unknown prefix 1304: The stack item does not match any defined type prefix (after stripping 1305: away any stack prefix). You should either declare the type prefix you 1306: want for that stack item, or use a different type prefix 1307: 1308: @cindex @code{unknown primitive} error 1309: @item unknown primitive 1310: You have used the name of a simple VM instruction in a superinstruction 1311: definition without defining the simple VM instruction first. 1312: 1313: @end table 1314: 1315: In addition, the C compiler can produce errors due to code produced by 1316: Vmgen; e.g., you need to define type cast functions. 1317: 1318: @c ******************************************************************** 1319: @node Using the generated code, Hints, Error messages, Top 1320: @chapter Using the generated code 1321: @cindex generated code, usage 1322: @cindex Using vmgen-erated code 1323: 1324: The easiest way to create a working VM interpreter with Vmgen is 1325: probably to start with @file{vmgen-ex}, and modify it for your purposes. 1326: This chapter explains what the various wrapper and generated files do. 1327: It also contains reference-manual style descriptions of the macros, 1328: variables etc. used by the generated code, and you can skip that on 1329: first reading. 1330: 1331: @menu 1332: * VM engine:: Executing VM code 1333: * VM instruction table:: 1334: * VM code generation:: Creating VM code (in the front-end) 1335: * Peephole optimization:: Creating VM superinstructions 1336: * VM disassembler:: for debugging the front end 1337: * VM profiler:: for finding worthwhile superinstructions 1338: @end menu 1339: 1340: @c -------------------------------------------------------------------- 1341: @node VM engine, VM instruction table, Using the generated code, Using the generated code 1342: @section VM engine 1343: @cindex VM instruction execution 1344: @cindex engine 1345: @cindex executing VM code 1346: @cindex @file{engine.c} 1347: @cindex @file{-vm.i} output file 1348: 1349: The VM engine is the VM interpreter that executes the VM code. It is 1350: essential for an interpretive system. 1351: 1352: Vmgen supports two methods of VM instruction dispatch: @emph{threaded 1353: code} (fast, but gcc-specific), and @emph{switch dispatch} (slow, but 1354: portable across C compilers); you can use conditional compilation 1355: (@samp{defined(__GNUC__)}) to choose between these methods, and our 1356: example does so. 1357: 1358: For both methods, the VM engine is contained in a C-level function. 1359: Vmgen generates most of the contents of the function for you 1360: (@file{@var{name}-vm.i}), but you have to define this function, and 1361: macros and variables used in the engine, and initialize the variables. 1362: In our example the engine function also includes 1363: @file{@var{name}-labels.i} (@pxref{VM instruction table}). 1364: 1365: @cindex tracing VM code 1366: @cindex superinstructions and tracing 1367: In addition to executing the code, the VM engine can optionally also 1368: print out a trace of the executed instructions, their arguments and 1369: results. For superinstructions it prints the trace as if only component 1370: instructions were executed; this allows to introduce new 1371: superinstructions while keeping the traces comparable to old ones 1372: (important for regression tests). 1373: 1374: It costs significant performance to check in each instruction whether to 1375: print tracing code, so we recommend producing two copies of the engine: 1376: one for fast execution, and one for tracing. See the rules for 1377: @file{engine.o} and @file{engine-debug.o} in @file{vmgen-ex/Makefile} 1378: for an example. 1379: 1380: The following macros and variables are used in @file{@var{name}-vm.i}: 1381: 1382: @table @code 1383: 1384: @findex LABEL 1385: @item LABEL(@var{inst_name}) 1386: This is used just before each VM instruction to provide a jump or 1387: @code{switch} label (the @samp{:} is provided by Vmgen). For switch 1388: dispatch this should expand to @samp{case @var{label}:}; for 1389: threaded-code dispatch this should just expand to @samp{@var{label}:}. 1390: In either case @var{label} is usually the @var{inst_name} with some 1391: prefix or suffix to avoid naming conflicts. 1392: 1393: @findex LABEL2 1394: @item LABEL2(@var{inst_name}) 1395: This will be used for dynamic superinstructions; at the moment, this 1396: should expand to nothing. 1397: 1398: @findex NAME 1399: @item NAME(@var{inst_name_string}) 1400: Called on entering a VM instruction with a string containing the name of 1401: the VM instruction as parameter. In normal execution this should be 1402: expand to nothing, but for tracing this usually prints the name, and 1403: possibly other information (several VM registers in our example). 1404: 1405: @findex DEF_CA 1406: @item DEF_CA 1407: Usually empty. Called just inside a new scope at the start of a VM 1408: instruction. Can be used to define variables that should be visible 1409: during every VM instruction. If you define this macro as non-empty, you 1410: have to provide the finishing @samp{;} in the macro. 1411: 1412: @findex NEXT_P0 1413: @findex NEXT_P1 1414: @findex NEXT_P2 1415: @item NEXT_P0 NEXT_P1 NEXT_P2 1416: The three parts of instruction dispatch. They can be defined in 1417: different ways for best performance on various processors (see 1418: @file{engine.c} in the example or @file{engine/threaded.h} in Gforth). 1419: @samp{NEXT_P0} is invoked right at the start of the VM instruction (but 1420: after @samp{DEF_CA}), @samp{NEXT_P1} right after the user-supplied C 1421: code, and @samp{NEXT_P2} at the end. The actual jump has to be 1422: performed by @samp{NEXT_P2} (if you would do it earlier, important parts 1423: of the VM instruction would not be executed). 1424: 1425: The simplest variant is if @samp{NEXT_P2} does everything and the other 1426: macros do nothing. Then also related macros like @samp{IP}, 1427: @samp{SET_IP}, @samp{IP}, @samp{INC_IP} and @samp{IPTOS} are very 1428: straightforward to define. For switch dispatch this code consists just 1429: of a jump to the dispatch code (@samp{goto next_inst;} in our example); 1430: for direct threaded code it consists of something like 1431: @samp{(@{cfa=*ip++; goto *cfa;@})}. 1432: 1433: Pulling code (usually the @samp{cfa=*ip++;}) up into @samp{NEXT_P1} 1434: usually does not cause problems, but pulling things up into 1435: @samp{NEXT_P0} usually requires changing the other macros (and, at least 1436: for Gforth on Alpha, it does not buy much, because the compiler often 1437: manages to schedule the relevant stuff up by itself). An even more 1438: extreme variant is to pull code up even further, into, e.g., NEXT_P1 of 1439: the previous VM instruction (prefetching, useful on PowerPCs). 1440: 1441: @findex INC_IP 1442: @item INC_IP(@var{n}) 1443: This increments @code{IP} by @var{n}. 1444: 1445: @findex SET_IP 1446: @item SET_IP(@var{target}) 1447: This sets @code{IP} to @var{target}. 1448: 1449: @cindex type cast macro 1450: @findex vm_@var{A}2@var{B} 1451: @item vm_@var{A}2@var{B}(a,b) 1452: Type casting macro that assigns @samp{a} (of type @var{A}) to @samp{b} 1453: (of type @var{B}). This is mainly used for getting stack items into 1454: variables and back. So you need to define macros for every combination 1455: of stack basic type (@code{Cell} in our example) and type-prefix types 1456: used with that stack (in both directions). For the type-prefix type, 1457: you use the type-prefix (not the C type string) as type name (e.g., 1458: @samp{vm_Cell2i}, not @samp{vm_Cell2Cell}). In addition, you have to 1459: define a vm_@var{X}2@var{X} macro for the stack's basic type @var{X} 1460: (used in superinstructions). 1461: 1462: @cindex instruction stream, basic type 1463: The stack basic type for the predefined @samp{inst-stream} is 1464: @samp{Cell}. If you want a stack with the same item size, making its 1465: basic type @samp{Cell} usually reduces the number of macros you have to 1466: define. 1467: 1468: @cindex unions in type cast macros 1469: @cindex casts in type cast macros 1470: @cindex type casting between floats and integers 1471: Here our examples differ a lot: @file{vmgen-ex} uses casts in these 1472: macros, whereas @file{vmgen-ex2} uses union-field selection (or 1473: assignment to union fields). Note that casting floats into integers and 1474: vice versa changes the bit pattern (and you do not want that). In this 1475: case your options are to use a (temporary) union, or to take the address 1476: of the value, cast the pointer, and dereference that (not always 1477: possible, and sometimes expensive). 1478: 1479: @findex vm_two@var{A}2@var{B} 1480: @findex vm_@var{B}2two@var{A} 1481: @item vm_two@var{A}2@var{B}(a1,a2,b) 1482: @item vm_@var{B}2two@var{A}(b,a1,a2) 1483: Type casting between two stack items (@code{a1}, @code{a2}) and a 1484: variable @code{b} of a type that takes two stack items. This does not 1485: occur in our small examples, but you can look at Gforth for examples 1486: (see @code{vm_twoCell2d} in @file{engine/forth.h}). 1487: 1488: @cindex stack pointer definition 1489: @cindex instruction pointer definition 1490: @item @var{stackpointer} 1491: For each stack used, the stackpointer name given in the stack 1492: declaration is used. For a regular stack this must be an l-expression; 1493: typically it is a variable declared as a pointer to the stack's basic 1494: type. For @samp{inst-stream}, the name is @samp{IP}, and it can be a 1495: plain r-value; typically it is a macro that abstracts away the 1496: differences between the various implementations of @code{NEXT_P*}. 1497: 1498: @cindex IMM_ARG 1499: @findex IMM_ARG 1500: @item IMM_ARG(access,value) 1501: Define this to expland to ``(access)''. This is just a placeholder for 1502: future extensions. 1503: 1504: @cindex top of stack caching 1505: @cindex stack caching 1506: @cindex TOS 1507: @findex IPTOS 1508: @item @var{stackpointer}TOS 1509: The top-of-stack for the stack pointed to by @var{stackpointer}. If you 1510: are using top-of-stack caching for that stack, this should be defined as 1511: variable; if you are not using top-of-stack caching for that stack, this 1512: should be a macro expanding to @samp{@var{stackpointer}[0]}. The stack 1513: pointer for the predefined @samp{inst-stream} is called @samp{IP}, so 1514: the top-of-stack is called @samp{IPTOS}. 1515: 1516: @findex IF_@var{stackpointer}TOS 1517: @item IF_@var{stackpointer}TOS(@var{expr}) 1518: Macro for executing @var{expr}, if top-of-stack caching is used for the 1519: @var{stackpointer} stack. I.e., this should do @var{expr} if there is 1520: top-of-stack caching for @var{stackpointer}; otherwise it should do 1521: nothing. 1522: 1523: @findex SUPER_END 1524: @item SUPER_END 1525: This is used by the VM profiler (@pxref{VM profiler}); it should not do 1526: anything in normal operation, and call @code{vm_count_block(IP)} for 1527: profiling. 1528: 1529: @findex SUPER_CONTINUE 1530: @item SUPER_CONTINUE 1531: This is just a hint to Vmgen and does nothing at the C level. 1532: 1533: @findex MAYBE_UNUSED 1534: @item MAYBE_UNUSED 1535: This should be defined as @code{__attribute__((unused))} for gcc-2.7 and 1536: higher. It suppresses the warnings about unused variables in the code 1537: for superinstructions. You need to define this only if you are using 1538: superinstructions. 1539: 1540: @findex VM_DEBUG 1541: @item VM_DEBUG 1542: If this is defined, the tracing code will be compiled in (slower 1543: interpretation, but better debugging). Our example compiles two 1544: versions of the engine, a fast-running one that cannot trace, and one 1545: with potential tracing and profiling. 1546: 1547: @findex vm_debug 1548: @item vm_debug 1549: Needed only if @samp{VM_DEBUG} is defined. If this variable contains 1550: true, the VM instructions produce trace output. It can be turned on or 1551: off at any time. 1552: 1553: @findex vm_out 1554: @item vm_out 1555: Needed only if @samp{VM_DEBUG} is defined. Specifies the file on which 1556: to print the trace output (type @samp{FILE *}). 1557: 1558: @findex printarg_@var{type} 1559: @item printarg_@var{type}(@var{value}) 1560: Needed only if @samp{VM_DEBUG} is defined. Macro or function for 1561: printing @var{value} in a way appropriate for the @var{type}. This is 1562: used for printing the values of stack items during tracing. @var{Type} 1563: is normally the type prefix specified in a @code{type-prefix} definition 1564: (e.g., @samp{printarg_i}); in superinstructions it is currently the 1565: basic type of the stack. 1566: 1567: @end table 1568: 1569: 1570: @c -------------------------------------------------------------------- 1571: @node VM instruction table, VM code generation, VM engine, Using the generated code 1572: @section VM instruction table 1573: @cindex instruction table 1574: @cindex opcode definition 1575: @cindex labels for threaded code 1576: @cindex @code{vm_prim}, definition 1577: @cindex @file{-labels.i} output file 1578: 1579: For threaded code we also need to produce a table containing the labels 1580: of all VM instructions. This is needed for VM code generation 1581: (@pxref{VM code generation}), and it has to be done in the engine 1582: function, because the labels are not visible outside. It then has to be 1583: passed outside the function (and assigned to @samp{vm_prim}), to be used 1584: by the VM code generation functions. 1585: 1586: This means that the engine function has to be called first to produce 1587: the VM instruction table, and later, after generating VM code, it has to 1588: be called again to execute the generated VM code (yes, this is ugly). 1589: In our example program, these two modes of calling the engine function 1590: are differentiated by the value of the parameter ip0 (if it equals 0, 1591: then the table is passed out, otherwise the VM code is executed); in our 1592: example, we pass the table out by assigning it to @samp{vm_prim} and 1593: returning from @samp{engine}. 1594: 1595: In our example (@file{vmgen-ex/engine.c}), we also build such a table for 1596: switch dispatch; this is mainly done for uniformity. 1597: 1598: For switch dispatch, we also need to define the VM instruction opcodes 1599: used as case labels in an @code{enum}. 1600: 1601: For both purposes (VM instruction table, and enum), the file 1602: @file{@var{name}-labels.i} is generated by Vmgen. You have to define 1603: the following macro used in this file: 1604: 1605: @table @code 1606: 1607: @findex INST_ADDR 1608: @item INST_ADDR(@var{inst_name}) 1609: For switch dispatch, this is just the name of the switch label (the same 1610: name as used in @samp{LABEL(@var{inst_name})}), for both uses of 1611: @file{@var{name}-labels.i}. For threaded-code dispatch, this is the 1612: address of the label defined in @samp{LABEL(@var{inst_name})}); the 1613: address is taken with @samp{&&} (@pxref{Labels as Values, , Labels as 1614: Values, gcc.info, GNU C Manual}). 1615: 1616: @end table 1617: 1618: 1619: @c -------------------------------------------------------------------- 1620: @node VM code generation, Peephole optimization, VM instruction table, Using the generated code 1621: @section VM code generation 1622: @cindex VM code generation 1623: @cindex code generation, VM 1624: @cindex @file{-gen.i} output file 1625: 1626: Vmgen generates VM code generation functions in @file{@var{name}-gen.i} 1627: that the front end can call to generate VM code. This is essential for 1628: an interpretive system. 1629: 1630: @findex gen_@var{inst} 1631: For a VM instruction @samp{x ( #a b #c -- d )}, Vmgen generates a 1632: function with the prototype 1633: 1634: @example 1635: void gen_x(Inst **ctp, a_type a, c_type c) 1636: @end example 1637: 1638: The @code{ctp} argument points to a pointer to the next instruction. 1639: @code{*ctp} is increased by the generation functions; i.e., you should 1640: allocate memory for the code to be generated beforehand, and start with 1641: *ctp set at the start of this memory area. Before running out of 1642: memory, allocate a new area, and generate a VM-level jump to the new 1643: area (this overflow handling is not implemented in our examples). 1644: 1645: @cindex immediate arguments, VM code generation 1646: The other arguments correspond to the immediate arguments of the VM 1647: instruction (with their appropriate types as defined in the 1648: @code{type_prefix} declaration. 1649: 1650: The following types, variables, and functions are used in 1651: @file{@var{name}-gen.i}: 1652: 1653: @table @code 1654: 1655: @findex Inst 1656: @item Inst 1657: The type of the VM instruction; if you use threaded code, this is 1658: @code{void *}; for switch dispatch this is an integer type. 1659: 1660: @cindex @code{vm_prim}, use 1661: @item vm_prim 1662: The VM instruction table (type: @code{Inst *}, @pxref{VM instruction table}). 1663: 1664: @findex gen_inst 1665: @item gen_inst(Inst **ctp, Inst i) 1666: This function compiles the instruction @code{i}. Take a look at it in 1667: @file{vmgen-ex/peephole.c}. It is trivial when you don't want to use 1668: superinstructions (just the last two lines of the example function), and 1669: slightly more complicated in the example due to its ability to use 1670: superinstructions (@pxref{Peephole optimization}). 1671: 1672: @findex genarg_@var{type_prefix} 1673: @item genarg_@var{type_prefix}(Inst **ctp, @var{type} @var{type_prefix}) 1674: This compiles an immediate argument of @var{type} (as defined in a 1675: @code{type-prefix} definition). These functions are trivial to define 1676: (see @file{vmgen-ex/support.c}). You need one of these functions for 1677: every type that you use as immediate argument. 1678: 1679: @end table 1680: 1681: @findex BB_BOUNDARY 1682: In addition to using these functions to generate code, you should call 1683: @code{BB_BOUNDARY} at every basic block entry point if you ever want to 1684: use superinstructions (or if you want to use the profiling supported by 1685: Vmgen; but this support is also useful mainly for selecting 1686: superinstructions). If you use @code{BB_BOUNDARY}, you should also 1687: define it (take a look at its definition in @file{vmgen-ex/mini.y}). 1688: 1689: You do not need to call @code{BB_BOUNDARY} after branches, because you 1690: will not define superinstructions that contain branches in the middle 1691: (and if you did, and it would work, there would be no reason to end the 1692: superinstruction at the branch), and because the branches announce 1693: themselves to the profiler. 1694: 1695: 1696: @c -------------------------------------------------------------------- 1697: @node Peephole optimization, VM disassembler, VM code generation, Using the generated code 1698: @section Peephole optimization 1699: @cindex peephole optimization 1700: @cindex superinstructions, generating 1701: @cindex @file{peephole.c} 1702: @cindex @file{-peephole.i} output file 1703: 1704: You need peephole optimization only if you want to use 1705: superinstructions. But having the code for it does not hurt much if you 1706: do not use superinstructions. 1707: 1708: A simple greedy peephole optimization algorithm is used for 1709: superinstruction selection: every time @code{gen_inst} compiles a VM 1710: instruction, it checks if it can combine it with the last VM instruction 1711: (which may also be a superinstruction resulting from a previous peephole 1712: optimization); if so, it changes the last instruction to the combined 1713: instruction instead of laying down @code{i} at the current @samp{*ctp}. 1714: 1715: The code for peephole optimization is in @file{vmgen-ex/peephole.c}. 1716: You can use this file almost verbatim. Vmgen generates 1717: @file{@var{file}-peephole.i} which contains data for the peephole 1718: optimizer. 1719: 1720: @findex init_peeptable 1721: You have to call @samp{init_peeptable()} after initializing 1722: @samp{vm_prim}, and before compiling any VM code to initialize data 1723: structures for peephole optimization. After that, compiling with the VM 1724: code generation functions will automatically combine VM instructions 1725: into superinstructions. Since you do not want to combine instructions 1726: across VM branch targets (otherwise there will not be a proper VM 1727: instruction to branch to), you have to call @code{BB_BOUNDARY} 1728: (@pxref{VM code generation}) at branch targets. 1729: 1730: 1731: @c -------------------------------------------------------------------- 1732: @node VM disassembler, VM profiler, Peephole optimization, Using the generated code 1733: @section VM disassembler 1734: @cindex VM disassembler 1735: @cindex disassembler, VM code 1736: @cindex @file{disasm.c} 1737: @cindex @file{-disasm.i} output file 1738: 1739: A VM code disassembler is optional for an interpretive system, but 1740: highly recommended during its development and maintenance, because it is 1741: very useful for detecting bugs in the front end (and for distinguishing 1742: them from VM interpreter bugs). 1743: 1744: Vmgen supports VM code disassembling by generating 1745: @file{@var{file}-disasm.i}. This code has to be wrapped into a 1746: function, as is done in @file{vmgen-ex/disasm.c}. You can use this file 1747: almost verbatim. In addition to @samp{vm_@var{A}2@var{B}(a,b)}, 1748: @samp{vm_out}, @samp{printarg_@var{type}(@var{value})}, which are 1749: explained above, the following macros and variables are used in 1750: @file{@var{file}-disasm.i} (and you have to define them): 1751: 1752: @table @code 1753: 1754: @item ip 1755: This variable points to the opcode of the current VM instruction. 1756: 1757: @cindex @code{IP}, @code{IPTOS} in disassmbler 1758: @item IP IPTOS 1759: @samp{IPTOS} is the first argument of the current VM instruction, and 1760: @samp{IP} points to it; this is just as in the engine, but here 1761: @samp{ip} points to the opcode of the VM instruction (in contrast to the 1762: engine, where @samp{ip} points to the next cell, or even one further). 1763: 1764: @findex VM_IS_INST 1765: @item VM_IS_INST(Inst i, int n) 1766: Tests if the opcode @samp{i} is the same as the @samp{n}th entry in the 1767: VM instruction table. 1768: 1769: @end table 1770: 1771: 1772: @c -------------------------------------------------------------------- 1773: @node VM profiler, , VM disassembler, Using the generated code 1774: @section VM profiler 1775: @cindex VM profiler 1776: @cindex profiling for selecting superinstructions 1777: @cindex superinstructions and profiling 1778: @cindex @file{profile.c} 1779: @cindex @file{-profile.i} output file 1780: 1781: The VM profiler is designed for getting execution and occurence counts 1782: for VM instruction sequences, and these counts can then be used for 1783: selecting sequences as superinstructions. The VM profiler is probably 1784: not useful as profiling tool for the interpretive system. I.e., the VM 1785: profiler is useful for the developers, but not the users of the 1786: interpretive system. 1787: 1788: The output of the profiler is: for each basic block (executed at least 1789: once), it produces the dynamic execution count of that basic block and 1790: all its subsequences; e.g., 1791: 1792: @example 1793: 9227465 lit storelocal 1794: 9227465 storelocal branch 1795: 9227465 lit storelocal branch 1796: @end example 1797: 1798: I.e., a basic block consisting of @samp{lit storelocal branch} is 1799: executed 9227465 times. 1800: 1801: @cindex @file{stat.awk} 1802: @cindex @file{seq2rule.awk} 1803: This output can be combined in various ways. E.g., 1804: @file{vmgen-ex/stat.awk} adds up the occurences of a given sequence wrt 1805: dynamic execution, static occurence, and per-program occurence. E.g., 1806: 1807: @example 1808: 2 16 36910041 loadlocal lit 1809: @end example 1810: 1811: @noindent 1812: indicates that the sequence @samp{loadlocal lit} occurs in 2 programs, 1813: in 16 places, and has been executed 36910041 times. Now you can select 1814: superinstructions in any way you like (note that compile time and space 1815: typically limit the number of superinstructions to 100--1000). After 1816: you have done that, @file{vmgen/seq2rule.awk} turns lines of the form 1817: above into rules for inclusion in a Vmgen input file. Note that this 1818: script does not ensure that all prefixes are defined, so you have to do 1819: that in other ways. So, an overall script for turning profiles into 1820: superinstructions can look like this: 1821: 1822: @example 1823: awk -f stat.awk fib.prof test.prof| 1824: awk '$3>=10000'| #select sequences 1825: fgrep -v -f peephole-blacklist| #eliminate wrong instructions 1826: awk -f seq2rule.awk| #turn into superinstructions 1827: sort -k 3 >mini-super.vmg #sort sequences 1828: @end example 1829: 1830: Here the dynamic count is used for selecting sequences (preliminary 1831: results indicate that the static count gives better results, though); 1832: the third line eliminates sequences containing instructions that must not 1833: occur in a superinstruction, because they access a stack directly. The 1834: dynamic count selection ensures that all subsequences (including 1835: prefixes) of longer sequences occur (because subsequences have at least 1836: the same count as the longer sequences); the sort in the last line 1837: ensures that longer superinstructions occur after their prefixes. 1838: 1839: But before using this, you have to have the profiler. Vmgen supports its 1840: creation by generating @file{@var{file}-profile.i}; you also need the 1841: wrapper file @file{vmgen-ex/profile.c} that you can use almost verbatim. 1842: 1843: @cindex @code{SUPER_END} in profiling 1844: @cindex @code{BB_BOUNDARY} in profiling 1845: The profiler works by recording the targets of all VM control flow 1846: changes (through @code{SUPER_END} during execution, and through 1847: @code{BB_BOUNDARY} in the front end), and counting (through 1848: @code{SUPER_END}) how often they were targeted. After the program run, 1849: the numbers are corrected such that each VM basic block has the correct 1850: count (entering a block without executing a branch does not increase the 1851: count, and the correction fixes that), then the subsequences of all 1852: basic blocks are printed. To get all this, you just have to define 1853: @code{SUPER_END} (and @code{BB_BOUNDARY}) appropriately, and call 1854: @code{vm_print_profile(FILE *file)} when you want to output the profile 1855: on @code{file}. 1856: 1857: @cindex @code{VM_IS_INST} in profiling 1858: The @file{@var{file}-profile.i} is similar to the disassembler file, and 1859: it uses variables and functions defined in @file{vmgen-ex/profile.c}, 1860: plus @code{VM_IS_INST} already defined for the VM disassembler 1861: (@pxref{VM disassembler}). 1862: 1863: @c ********************************************************** 1864: @node Hints, The future, Using the generated code, Top 1865: @chapter Hints 1866: @cindex hints 1867: 1868: @menu 1869: * Floating point:: and stacks 1870: @end menu 1871: 1872: @c -------------------------------------------------------------------- 1873: @node Floating point, , Hints, Hints 1874: @section Floating point 1875: 1876: How should you deal with floating point values? Should you use the same 1877: stack as for integers/pointers, or a different one? This section 1878: discusses this issue with a view on execution speed. 1879: 1880: The simpler approach is to use a separate floating-point stack. This 1881: allows you to choose FP value size without considering the size of the 1882: integers/pointers, and you avoid a number of performance problems. The 1883: main downside is that this needs an FP stack pointer (and that may not 1884: fit in the register file on the 386 arhitecture, costing some 1885: performance, but comparatively little if you take the other option into 1886: account). If you use a separate FP stack (with stack pointer @code{fp}), 1887: using an fpTOS is helpful on most machines, but some spill the fpTOS 1888: register into memory, and fpTOS should not be used there. 1889: 1890: The other approach is to share one stack (pointed to by, say, @code{sp}) 1891: between integer/pointer and floating-point values. This is ok if you do 1892: not use @code{spTOS}. If you do use @code{spTOS}, the compiler has to 1893: decide whether to put that variable into an integer or a floating point 1894: register, and the other type of operation becomes quite expensive on 1895: most machines (because moving values between integer and FP registers is 1896: quite expensive). If a value of one type has to be synthesized out of 1897: two values of the other type (@code{double} types), things are even more 1898: interesting. 1899: 1900: One way around this problem would be to not use the @code{spTOS} 1901: supported by Vmgen, but to use explicit top-of-stack variables (one for 1902: integers, one for FP values), and having a kind of accumulator+stack 1903: architecture (e.g., Ocaml bytecode uses this approach); however, this is 1904: a major change, and it's ramifications are not completely clear. 1905: 1906: @c ********************************************************** 1907: @node The future, Changes, Hints, Top 1908: @chapter The future 1909: @cindex future ideas 1910: 1911: We have a number of ideas for future versions of Vmgen. However, there 1912: are so many possible things to do that we would like some feedback from 1913: you. What are you doing with Vmgen, what features are you missing, and 1914: why? 1915: 1916: One idea we are thinking about is to generate just one @file{.c} file 1917: instead of letting you copy and adapt all the wrapper files (you would 1918: still have to define stuff like the type-specific macros, and stack 1919: pointers etc. somewhere). The advantage would be that, if we change the 1920: wrapper files between versions, you would not need to integrate your 1921: changes and our changes to them; Vmgen would also be easier to use for 1922: beginners. The main disadvantage of that is that it would reduce the 1923: flexibility of Vmgen a little (well, those who like flexibility could 1924: still patch the resulting @file{.c} file, like they are now doing for 1925: the wrapper files). In any case, if you are doing things to the wrapper 1926: files that would cause problems in a generated-@file{.c}-file approach, 1927: please let us know. 1928: 1929: @c ********************************************************** 1930: @node Changes, Contact, The future, Top 1931: @chapter Changes 1932: @cindex Changes from old versions 1933: 1934: User-visible changes between 0.5.9-20020822 and 0.5.9-20020901: 1935: 1936: The store optimization is now disabled by default, but can be enabled by 1937: the user (@pxref{Store Optimization}). Documentation for this 1938: optimization is also new. 1939: 1940: User-visible changes between 0.5.9-20010501 and 0.5.9-20020822: 1941: 1942: There is now a manual (in info, HTML, Postscript, or plain text format). 1943: 1944: There is the vmgen-ex2 variant of the vmgen-ex example; the new 1945: variant uses a union type instead of lots of casting. 1946: 1947: Both variants of the example can now be compiled with an ANSI C compiler 1948: (using switch dispatch and losing quite a bit of performance); tested 1949: with @command{lcc}. 1950: 1951: Users of the gforth-0.5.9-20010501 version of Vmgen need to change 1952: several things in their source code to use the current version. I 1953: recommend keeping the gforth-0.5.9-20010501 version until you have 1954: completed the change (note that you can have several versions of Gforth 1955: installed at the same time). I hope to avoid such incompatible changes 1956: in the future. 1957: 1958: The required changes are: 1959: 1960: @table @code 1961: 1962: @cindex @code{TAIL;}, changes 1963: @item TAIL; 1964: has been renamed into @code{INST_TAIL;} (less chance of an accidental 1965: match). 1966: 1967: @cindex @code{vm_@var{A}2@var{B}}, changes 1968: @item vm_@var{A}2@var{B} 1969: now takes two arguments. 1970: 1971: @cindex @code{vm_two@var{A}2@var{B}}, changes 1972: @item vm_two@var{A}2@var{B}(b,a1,a2); 1973: changed to vm_two@var{A}2@var{B}(a1,a2,b) (note the absence of the @samp{;}). 1974: 1975: @end table 1976: 1977: Also some new macros have to be defined, e.g., @code{INST_ADDR}, and 1978: @code{LABEL}; some macros have to be defined in new contexts, e.g., 1979: @code{VM_IS_INST} is now also needed in the disassembler. 1980: 1981: @c ********************************************************* 1982: @node Contact, Copying This Manual, Changes, Top 1983: @chapter Contact 1984: 1985: To report a bug, use 1986: @url{}. 1987: 1988: For discussion on Vmgen (e.g., how to use it), use the mailing list 1989: @email{bug-vmgen@@mail.freesoftware.fsf.org} (use 1990: @url{} to subscribe). 1991: 1992: You can find vmgen information at 1993: @url{}. 1994: 1995: @c *********************************************************** 1996: @node Copying This Manual, Index, Contact, Top 1997: @appendix Copying This Manual 1998: 1999: @menu 2000: * GNU Free Documentation License:: License for copying this manual. 2001: @end menu 2002: 2003: @node GNU Free Documentation License, , Copying This Manual, Copying This Manual 2004: @appendixsec GNU Free Documentation License 2005: @include fdl.texi 2006: 2007: 2008: @node Index, , Copying This Manual, Top 2009: @unnumbered Index 2010: 2011: @printindex cp 2012: 2013: @bye