7 Code generation from parse trees -------------------------------- 7.1 Aim and structure of the code generator --------------------------------------- The section "expressc.c" takes as input a parse tree and generates suitable Z-code to calculate the result of the expression which the parse tree embodies. As a result, its main output is a stream of function calls to "asm.c" (see chapter 5 for details). The syntax analyser calls only one routine: assembly_operand code_generate(assembly_operand AO, int context, int label) where AO is expected to be the output from a previous run through "expressp.c". The contexts are the same as those for expression parsing, except that only VOID_CONTEXT, CONDITION_CONTEXT and QUANTITY_CONTEXT are allowed. The "label" is only meaningful in CONDITION_CONTEXT: if label >= 0, branch to this label if the expression is false as a condition; if label == -3, rfalse if the expression is true; if label == -4, rtrue if the expression is true. (Note that the presence of rfalse/rtrue here allows better code generation for statements in the form if ( ... ) return; owing to a feature of the Z-machine's architecture for branch instructions.) The return AO is only meaningful in QUANTITY_CONTEXT; it holds the result of the expression, often the stack pointer variable (meaning, the answer is on the top of the stack) but not always: e.g., from j++, 2 the result would be SHORT_CONSTANT_OT 2. Similarly, from the expression 2 the code generator returns 2 without actually generating code. 7.2 Annotation for conditions ------------------------- The first thing the code generator does is to "annotate" the tree for conditions. Annotation is the process of assigning useful values to every node on the tree, usually in such a way that either the value at one node determines the values for its children, or vice versa. (Such values are called "attributes" and this inductive definition of them is called "synthesis": see ASU, p.280.) The explanation of this algorithm is about five times longer than its source code! We wish to assign a pair of values written (on paper) in the form a | b to every conditional node (that is, every node which is a conditional operator such as "~=" or "ofclass", or is a logical operator such as "&&"). This is to be read as "branch to label a if true, or label b if false". Inform has four special label numbers: -1 means "carry on rather than branch" -2 means "branch to the immediately following instruction" -3 means "return false rather than branch" -4 means "return true rather than branch" (-2 is used in the assembly of instructions like get_child_zc, which is a conditional branch in Z-machine terms but which Inform wants to ignore the branch result from. We can ignore -2 here: it behaves exactly like -1.) One of the two numbers a and b must always be other than -1 (otherwise we would have rendered a branch meaningless, which must be a mistake). Ideally exactly one of them is -1, so that the node can generate a single branch instruction. There are two points where these a | b attributes start to appear in the tree. Firstly, in condition context they'll appear at the root node: for example, in CONDITION_CONTEXT with label 40 the top node would be labelled -1 | 40 ("jump to L40 if false"). Secondly, at condition subexpressions used as values, e.g. in the tree: = / \ v == / \ t 1 This is trickier: the result of == is not a branch somewhere, but a numerical value (which must be 0 or 1). To cope with such conversions, two more attributes are provided: to_expression, label_after A node flagged as "to_expression" is one where a condition is being converted to a numerical value; the "==" node above would have this flag set. "label_after" is either -1 or the number of a label which the code generator is to assemble after code generation for the node is complete. So here are the rules for generating these attributes for node N. Each node is sent a pair of values a | b from its parent (in the case of the root node, from the code_generate() routine). annotate N with a | b if N is &&, || or a conditional operator, and a | b is -1 | -1, then this must be a condition used as a value: so re-annotate N with to_expression = TRUE label_after = a new label L L | -1 if N is an && operator: a label for "go here if false" is going to be needed to provide a destination for the branch generated by the lefthand operand. So, if b = -1, re-annotate N with: label_after = a new label L a | L if N is an || operator: a label for "go here if true" is going to be needed to provide a destination for the branch generated by the lefthand operand. So, if a = -1, re-annotate N with: label_after = a new label L L | b Finally, we need to pass a pair of values down to each child of the node. In the case of all nodes except && and ||, the values passed down are -1 | -1 (because the operator expects numerical operands). In the case of && and ||, let x | y be the annotation which was finally made for this node. We pass values down as follows: && || / \ / \ -1 | y x | y x | -1 x | y (Here "condition node" means a conditional or logical operator. Recall that the ~~ operator was eliminated earlier.) For example, consider the condition in if (x == 1 || y >= 2) ... The syntax analyser decides to generate code which will branch to L23 if the condition is false. The parse tree || || -1 | 23, l_a = 50 / \ / \ == >= is annotated to == 50 | -1 >= 50 | 23 / \ / \ / \ / \ x 1 y 2 x 1 y 2 where the annotation routine created label 50 as a point to branch to if the first condition turned out to be true. Note that it's actually a little wasteful to annotate this way: the node >= is annotated with 50 | 23, but label L50 will appear immediately after the code generated for this node anyway, so it might as well be annotated -1 | 23. The annotation routine does indeed make this simplification. Lemma: One of the values a, b sent down to any node is always -1. Proof: By induction down through the tree. The values sent down to the root node are either -1 | L, -3 | -1 or -4 | -1, so the property holds for the root node. Now suppose such a pair a | b is sent down to node N. Unless N is && or ||, it sends -1 | -1 to its children, so the property holds for the children of N. If N is &&, then it has two children, left and right. The left child is always sent -1 | y, so it has the property. The right child is sent x | y, unless y is a new label appearing after N, in which case it is sent x | -1. Note, though, that N itself was sent a pair in which one number was -1 (by inductive hypothesis) and so x | y can only have both numbers other than -1 if a new label was created by N. Since N is an && operator this label must be y; and therefore the child is sent x | -1, which means the right child also has the property. The argument for || is symmetrical to this. Corollary: In the annotation "a | b" of every node other than a && or || operator, either a is -1 and b is not, or vice versa. The annotation values a | b are only used to generate code for condition operators, so we now have the desired result. 7.3 Main traversal -------------- The main algorithm is simple. We make a depth-first (i.e., bottom-up) traversal of the parse tree, pruning off sub-expressions as code is generated for them. In the tree * / \ a + / \ b c we first descend to the +, and convert that into @add b c -> sp and prune the tree to * / \ a sp so that the next instruction generated is @mul a sp -> sp and the tree is now just sp and the result is therefore on the stack. A complication, however, is what order in which to remove the subexpressions. Faced with the tree - / \ * + / \ / \ a b c d do we go left first from the top -, or right first? This decision is taken for us by the Z-machine's architecture. When the Z-machine executes the instruction @sub sp sp -> x; it takes the two operands off the stack in the order left to right, i.e., it pulls the first operand first and then the second. (Most stack machines work the other way, to make RPN expressions easy to evaluate. The Z-machine was designed for forward Polish notation, though, because Infocom's own language for it was a Lisp-variant with syntax like (PLUS 2 3).) This means that we need to push the second operand first, then the first operand. In other words, we have to code generate the + operation first, and then the * operation. Therefore we need to traverse the tree depth-first and right-to-left. But there is a complication: the && and || nodes need to have their children code-generated left-to-right. (Although "and" is logically commutative, so that it shouldn't matter, "&&" is not computationally commutative, because the language specification requires that the left condition is never evaluated if the right condition was false.) There is one other left-to-right node: the comma operator. For example, if the original value of x is 10, then , / \ ++ x / x must evaluate to 11, not 10, because "x++, x" must evaluate "x++" first, throw the result away and then evaluate "x". 7.4 Void context ------------ As the above example demonstrates, in some cases sub-expressions need to produce a result and in other cases they must not do so. If the "++" operator had left a value on the stack, then it would still be there long after the expression had been evaluated. Therefore, when code generating each node it is essential to know where the result of the expression is supposed to go. A flag called void_flag is passed down to indicate this: if set, then the operator is being evaluated in "void context", meaning that the value should be thrown away. The rules are: if the expression is in VOID_CONTEXT, then the root node is; the left operand of a comma operator is in void context; if a comma operator is in void context, its right operand also is. Not every subexpression is permitted to be in void context. For instance, 3*x, y++; generates the error Result of expression is thrown away because the * calculation was pointless. Numerical values or variables are not allowed in void context, and nor are any operators which have no "side effect": i.e., whose evaluation causes nothing in the Z-machine to change. The operators with side effects are: = in its various forms (5 of them) ++ in its various forms (10 of them) -- in its various forms (10 of them) function call (including message sending) It is only now, at code generation time, that the error message above is generated. (In C this would only cause a warning, but I didn't want to waste effort making the code generator assemble code to explicitly throw results away.) 7.5 Results of subexpressions ------------------------- By the rules above, then, either an operator is in void context and its result should be thrown away, or it isn't and the result should go onto the stack. However, this would be wasteful, as an expression like "x = 4 + y" (where x is a local variable, say) would then generate @add 4 y -> sp @pull x and give result "x". In fact we want to generate @add 4 y -> x and give the result "x". Therefore, when code-generating an operator with a result (such as @add), we look at the operator above (which is guaranteed still to exist): if it is then we get its left operand, write the result of the operator (such as @add) to that, and replace the operator with the variable. For instance, set-var-equal x / \ x + becomes just / \ 4 y One method used to throw away the results of expressions in void context is to write the result to temporary variable 255 rather than the stack. This is how unwanted function call return values are disposed of (well, unless the Z-machine version number is 5 or more, in which case instructions for call-but-throw-away-result are used directly). A few other optimisations are used in void context: for example, ++ used as postfix on variable | var generates the code @push var @inc var with result "sp" in a quantity context. In void context, it generates simply @inc var This is quite an important optimisation since postfix-++ is used very often in void context (in "for" statements and just as an assignment). 7.6 Conditional and logical operators --------------------------------- The above account covers code generation for arithmetic and assignment operators. In generating && and ||, nothing needs to be done except possibly to assemble a label (if the attribute label_after isn't -1). Generating for conditions like == is in principle easy but in practice difficult. Recall that we have three attributes to go on: a | b labels to branch to on true | false, one which is -1 meaning "carry on" to_expression flag indicating "convert to numerical value" One problem is that, because of the "or" operator, a condition like == may have an arbitrary number of children: if (x == a or b or c or d or e) ... for instance, must be assembled into the instructions: @je x a b c ?L2 @je x d e ?~L1 .L2 ... .L1 (and if x is a use of the stack pointer, it must be pulled into some temporary variable so that it can be non-destructively read more than once). The code to achieve this is baroque but uninteresting. The second question is how to convert a condition to a numerical value: either 0 (false) or 1 (true). At present, this is not very optimised, and the code looks like: @push 0 @jump L2 .L1 @push 1 @jump L2 with the result being "sp". 7.7 System functions ---------------- When generating the operator, Inform looks at the leftmost operand (the function to call) to see if it's the name of a system function. (Note that if the system function has been Replaced, then it will have been filtered out long since and the name will have been treated as the symbol name for a function in the usual way.) These are all implemented as short inline functions (sometimes only one instruction long) except for "metaclass", implemented as a veneer routine. Note that random / | | a b c .... nodes are generated by creating a word array whose contents are a, b, c, ... and then assembling code to read a random entry from this array. (An error is issued if a, b, c, etc. are found not to be constant values.) 7.8 Strict mode assertions ---------------------- When the compiler runs in "Strict" mode, with the -S switch set, it compiles otherwise wasteful code to protect the programmer from crashing the Z-machine through programming errors. For instance, the statement x = child(nothing); would otherwise compile to Z-code which is technically illegal: @get_child nothing -> x ?L0; .L0; because the "get_child" opcode should have a legal Z-machine object number as first opcode. Most interpreters would overlook this technical breach of the Z-machine specification. A more serious example might be my_array --> 34000 = 1; which would compile code trying to use @storew to write a value way outside the Z-machine's dynamic memory area: this would typically crash an interpreter. The generic term for mistakes like these, coined by Mr David Glasser, is "vile zero errors from hell". In strict mode, Inform aims to compile code such that no program (which does not contain @ assembly language) can possibly violate the Z-machine specification in any respect. In effect it compiles what other compilers have called "assertions" before any use of a dangerous opcode whose operands have been supplied by the user's program. For example "storew" will not be executed until its operand value has been checked to lie in range. That is, the statement z = x-->y; compiles in non-strict mode to @storew x y -> z but in strict mode to @call_vs RT__ChSTW x y -> z where RT__ChSTW is a veneer routine ("run-time check store word") which verifies only that x+2*y lies between 0 and the top of dynamic memory: if so, the routine performs the required opcode; if not, it causes the error message [** Programming error: tried to read outside memory using --> **] to be printed up. Not all the protected opcodes are replaced simply by function calls, as this could be very slow: some are replaced by in-line code, which is quicker. For example, if the source code contained z = my_array-->y; where "my_array" had been declared as an array, then Inform would instead compile this: jl y short_0 to L1 if TRUE jl y to L0 if TRUE .L1 call_vn2 RT__Err short_28 y short_6 short_5 short_1 jump L2 .L0 loadb long_680 y -> z .L2 This has wasted some 23 bytes, but is faster than calling a function, and directly checks that 0 <= y < where is the 1 more than the highest legal entry of my_array, which Inform knows thanks to having already compiled my_array. The long run of numbers fed to the veneer's run-time error system specify the error number (28), the index tried (y) and so forth, enabling it to print an error like so: [** Programming error: tried to write to -->14 in the array my_array, which has entries 0 up to 9 **] The current list of assertions is as follows: Inform syntax Assertion ============= ========= child(x) metaclass(x) == Object, children(x) i.e., is the number of a Z-machine object elder(x) but isn't a class-object eldest(x) parent(x) sibling(x) younger(x) youngest(x) x in y metaclass(x) == Object or Class x notin y i.e. x is the number of a Z-machine object (y, however, is unrestricted: the second operand of @jin does not have to be a valid object number) x has y metaclass(x) == Object or Class, x hasnt y y is a valid attribute number give x y metaclass(x) == Object remove x move x to y metaclass(x) == metaclass(y) == Object, and the object tree remains a tree if x is moved to y x/y y ~= 0 x%y x.y = z metaclass(x) == Object, y is a valid property, ++x.y and x provides y x.y++ --x.y x.y-- x.y (used as value) metaclass(x) == Object, y is a valid property, and x provides y or else y is a common property x.&y metaclass(x) == Object, y is a valid property x.#y (not necessarily provided by x) x-->y = z x+2*y,x+2*y+1 lie within "alterable memory" x-->y++ (see below) x-->y-- Moreover, if x is the name of a declared array, ++x-->y x+2*y,x+2*y+1 lie within the bounds of the array --x-->y (and not the length entry 0 if a table or string) x-->y (used as value) x+2*y,x+2*y+1 lie within byte-accessible memory Similarly for declared arrays, though entry 0 can be read x->y = z x+y lies within "alterable memory" (see below) x->y++ x->y-- Moreover, if x is the name of a declared array, ++x->y x+y lies within the bounds of the array --x->y (and not the length entry 0 if a table or string) x->y (used as value) x+y lies within byte-accessible memory Similarly for declared arrays, though entry 0 can be read print (char) x x is a valid ZSCII character for output, as defined in section 3.8 of the Z-Machine Standards Document print (address) x x lies within Z-machine byte-accessible memory print (string) x metaclass(x) == String print (object) x metaclass(x) == Object or Class The definition of "alterable memory" is: either (a) within the array space area; or (b) within the object common property values table; or (c) within the object individual property values table; or (d) being the word "Flags 2" in the Z-machine header, at address $0010, $0011. All other areas in byte-accessible memory can be read but are "write-protected": in particular the global variable values table, which needs to be defended as corrupting the contents during a loop can cause the Z-machine to hang. A further assertion is compiled into loops of the form objectloop (x in something) { ... } where "something" is any simple term (but not a calculated expression): at the end of the loop, the assertion checks that x is still in "something" and has not been removed or moved elsewhere in the object tree, causing the iteration to go awry. (This is a popular Inform coding mistake and often arises from code like "objectloop(x in player) remove x;".) Note that the veneer code is always compiled in non-strict-mode, which is necessary to prevent some circular problems (e.g. can't do X without calling the veneer to ask permission, but then the veneer has to call itself to ask permission, but then...); and also enables the veneer to do horrid things to class objects in ways which the outside program isn't allowed to.