CODE GENERATION (Chapters 8 and 9) - Now that we know the location of every variable, we can generate code to access those variables and perform computations on them. - Basic problems: + Complexity and correctness - RISC: All computations in registers + registers must be shared + how do we remember what value is in what register? - what Sparc instruction corresponds to what Oberon operation? - how can I generate the code in the right order? + recall that compiler is syntax-directed, one-pass, so we must generate code directly in the actions. + Performance of generated code - choice of instructions that yields fastest, fewest instructions - memory operations are expensive: try to keep values in regs - undecidable in general case: don't know what input will be - even ignoring input patterns, NP-complete problem, basically exponential (generate all possible instruction sequences and check). - not our primary concern here + Performance of code generator - non-issue unless trying hard for optimized code (see above) - Input is program in some form: + Oberon + parse tree + pseudo-assembly - Output is: + Textual assembler + Relocatable, linkable binary (.o) + Absolute binary (a.out) + Virtual machine code (ala Java) + Debugging info for debugging (symbol tables, basically) Reading and Storing Variables - Since we have more variables than registers, a variable can use a register for only a short period of time. (And we have to use registers because the Sparc is a RISC machine.) - To simplify, whenever a variable is used in a computation, we'll load it into memory at that point and use it right away. The value in the register is never reused. The register can be used for another variable right away. - The result is stored to memory as soon as it is computed. - This gives rise to the ``load, load, compute, store'' model of computation: VAR x, y, z : INTEGER; ... BEGIN x := y + z; becomes: load [%gp + 4], r1 ; t1 := y + z load [%gp + 8], r2 add r1, r2, r3 store r3, [%gp + 12] load [%gp + 12], r1 ; x := t1 store r1, [%gp + 0] + Note that we have *two* operations here (+, :=), and so there are two load-compute-store sequences (null compute and only one load in the second case). + This is inefficient but simple, matches syntax-directed translation + Note that the ExprSTO that you've been using for the result type of + can now be used as the temporary variable "t1". + This temporary variable is just like any other variable. You should insert it into the current scope, whatever that is. + Never more than 3 registers in use. Can always use same three (or two) over and over. - Two issues still unresolved: how and when does this code get generated? Syntax-Directed Code Generation - Since we're not using a parse tree, we have to do code generation during parsing (i.e., syntax-directed). Naively: E ::= ID:id { RESULT = symTab.lookup(id); } E ::= E:e1 '+' E:e2 { RESULT = new ExprSTO(); Add.emit(RESULT, e1, e2); } S ::= ID:id ':=' E:e { RESULT = lookup(id); Assign.emit(RESULT, e); } - Once the parser recognizes the Oberon code, we emit semantically identical assembly code. We are mapping Oberon syntax to Sparc syntax. - However, the emit code does not go in the grammar, but in our *.action routines: ExprSTO action(STO a, int op, STO b) { ExprSTO result = new ExprSTO(); // local temporary OpSTO opSTO = (OpSTO) symTab.lookup(Lexer.int_to_name[op]); if (!BinaryExpr.elaborate(result, a, opSTO, b)) oberon.stopCodeGeneration(); else // New code BinaryExpr.emit(result, a, opSTO, b); // New code return result; } - For those with AST's, you can execute these actions during the post-order traversal of your AST - We use the symbol table entries to keep track of *where* results are being read from and stored to. - Results of computations are stored in a variable, often a temporary (e.g., see "+" rule) + For expressions, this means that the location of the result is passed as a synthesized attribute from operations at the leaves to operations higher up in the parse tree. + In example above: - match and lookup "x" and "y" in "E ::= ID" rule - these are passed to "E + E" rule as e1 and e2. - a ExprSTO is allocated to keep track of where result of add will be stored (temporary t1) - code for add is emitted such that addresses for x and y are read from and result is stored to address of temp (t1). - Note that we've separated *when* to emit (when + is seen) from *how* to emit (body of Add::emit not visible here), not to mention *what*. + Basically, *how* is a bunch of println's or similar. + What is Sparc code for add, of course. - Order of generated code is adequate as long as parse order emulates execution order. + this is normally the case, largely because that is what is easier for humans to read + when it doesn't, compiler has to put a jump before ``early'' code, and then jump back to it later. :( + control constructs are tougher EmitX: one emit abstraction per ``operation'' - From prior experience, we already know that we are not doing Add.emit(...), but BinaryExpr.emit(...). But we'll start with addition and move on from there. - Organized around load-load-compute-store. The question is how do we break the code generation problem up into pieces. Recall that: x := y + z is matched by: S : ID := E E : E + E to become: load [%gp + 4], r1 ; t1 := y + z load [%gp + 8], r2 add r1, r2, r3 store r3, [%gp + 12] load [%gp + 12], r1 ; x := t1 store r1, [%gp + 0] - Tasks: + allocate temp storage for result (done) + allocate registers for computation + emit: load operands into registers + emit: compute result into register + emit: store register to memory + allocate: free registers + pass temp var up expression tree (done) /* * NOTES: * * - For +, could generalize for all binary ops (bin-op argument) * * - This is for INTEGER's only; Could extend this for REAL's, or * have separate routine */ void BinaryExpr::emit(ExprSTO t, STO o1, OpSTO opSTO, STO o2) { Register rt, ro1, ro2; rt = Machine.getReg(); /* overkill, since simple reg. alloc. */ ro1 = Machine.getReg(); ro2 = Machine.getReg(); Machine.emitLoad(o1, ro1); Machine.emitLoad(o2, ro2); Machine.emitAdd(ro1, ro2, rt); // WARNING - ADD only! Machine.emitStore(rt, t); // diff. than Assign.emit because takes reg Machine.freeReg(rt); Machine.freeReg(ro1); Machine.freeReg(ro2); } Machine::emitLoad(ExprSTO var, String reg) { eprint("ld [%R + %D], %R\n", var.baseName(), var.offset(), reg); } Machine::emitAdd(Register ro1, Register ro2, Register rt) { eprint("add %R, %R, %R\n", ro1, ro2, rt); } ... - Note that we've separated + operations from load/store (add vs. load) + symbol table from code gen (STO methods, not representation) + compiler conventions from architecture (base ptr from instructions) + local vs. global is transparent ("baseName") + language syntax from assembly syntax + how printing is done from what to print ("eprint": may be extreme) - So how do we generalize this for all BinaryExpr's? - Any other problems or oddities with this design? Register Management - Why have getReg() and freeReg() routines if always do load-load-compute-store on same registers? + might change the registers that you are using + maybe somewhere you'll need four registers + maybe you'll make a mistake - Register getReg(); void freeReg(Register reg); + maybe initRegs() operation + maybe "newLocalRegs()" operation to get things started, since every procedure has its own set of (non-global) registers - Routines above separate code gen from register allocation - Allows changing register allocation strategy without changing emit code - Program structure works on a ``jar'' metaphor: handing out element means no else can have it until returned. + What jar solutions do we have around? - What does the Register class look like? Control Constructs (IF) - Not an ``operation'', need to do tests and jumps - Let's look at the rule and associated example code. By assigning parts of the generated code to parts of the rule, we can figure out what to do: (1) S : IF E THEN S END (2) (3) (4) IF x < y THEN lt x, y, t1 ; E x := x + 1; ifnot t1 goto L1 ; if-then add x, 1, x ; S END; ; S ... L1: ... ; end - Note that if pieces of assembler cannot be assigned to pieces of grammar (for actions), then need to modify assembler (or maybe grammar, etc.) - Straightforward approach has you jumping to place that you don't know of yet. Solution is to use label and let assembler resolve actual address. (Do this without stack at first, note local variable problem and nested-if problem: label is inherited attribute.) Stack LabelStack; ... S ::= IF {: Push(LabelStack, new Label()); :} /* better plan for ELSE */ E:e THEN {: emitFalseCond(e, Top(LabelStack)); :} S END {: emitLabel(Top(LabelStack)); Pop(LabelStack); :} E ::= E:e1 '<' E:e2 {: RESULT = new ExprSTO(); LessThan.emit(RESULT, e1, e2); } - Label abstraction hides details of labels actions + Just a string or integer: L1, L2, ... (use sprintf). - There are more efficient implementations that don't store booleans as variables, but just branch on test. COMPLICATED! - As with operations, process of mapping problem to solution requires respecting our existing partial solutions and the limitations (and strengths) of the technology: (1) Write down grammar for construct (2) Write down example Oberon construct (3) Write down possible Sparc solution (4) Establish correspondence from (2) to (3) on a syntax-wise basis, as required by (1)'s syntax-directed definitions (add interacting grammar rules as needed); correspondence to (1) follows (5) If run into problems, modify (3) so that it can be piecewise generated by (1)'s syntax-directed actions (6) If that doesn't work, consider changing parts of existing solution, such as grammar or handling of STO's. - Note that *without* the grammar and syntax-directed translation, we would have a lot more freedom in defining a mapping from Oberon to assembler, but it would also be a lot harder! The grammar's syntax-directed actions permit a piecewise decomposition of the problem that allows solving problems in small, relatively declarative pieces. Advanced Control Structures - While + A lot like if, but with branch back + How should we emit code for this? S : WHILE E DO SL END SL : SL S | S L1: ; while WHILE x < y DO lt x, y, t1 ; E x := x + 1; ifnot t1 goto L2 ; do add x, 1, x ; SL END; ; SL ... goto L1 ; end-while L2: ... ; end-while + Like this: Stack startLabelStack; Stack endLabelStack; ... S ::= WHILE {: startLabel = Machine.newLabel(); endLabel = Machine.newLabel(); startLabelStack.push(startLabel); endLabelStack.push(endLabel); Machine.emitLabel(startLabel); :} E:e DO {: Machine.emitFalseCond(e, endLabelStack.top()); :} SL END {: Machine.emitGoto(startLabelStack.top())); Machine.emitLabel(endLabelStack.top()); startLabelStack.pop(); endLabelStack.pop(); :} - Exit + Jump to end point of enclosing loop + Must work with multiple loops active S : EXIT WHILE ... ... WHILE x < y DO L1: lt x, y, t1 x := x + 1; ifnot t1 goto L2 if x = 0 then exit end if; add x, 1, x eq x, 0, t2 END; ifnot t2 goto L3 ... goto L2 ; exit L3: goto L1 L2: ... + We recall from our earlier exit-in-loop test that the in-loop information is an inherited attribute, so L2 label must be also S ::= EXIT {: Machine.emitGoto(endLabelStack.top()); :} + Anything else funny here? - can't use endLabelStack because IF has put label on top of it. - separate into X_LoopStack and X_IfStack in WHILE and IF actions - Yet another change! One can hope that the changes are localized, indicating a good modularization. S ::= EXIT {: Machine.emitGoto(endLoopStack.top()); :} - If-Then-Else S : IF E THEN S ELSE S IF x < y THEN lt x, y, t1 ; E x := x + 1; ifnot t1 goto L1 ; if-then add x, 1, x ; S ELSE ; S x := x - 1; goto L2 ; end-then/else L1: sub x, 1, x ; else/S END; ; S ... L2: ... ; end + What are the changes here? Need to branch to else; true part needs to jump around else + Looks like we can reuse pair of label stacks idea Stack elseIfStack; Stack endIfStack; ... S ::= IF E:e THEN {: elseLabel = Machine.newLabel(); endLabel = Machine.newLabel(); elseIfStack.push(elseLabel); endIfStack.push(endLabel); Machine.emitFalseCond(e, elseLabel); :} S ELSE {: Machine.emitGoto(endIfStack.top()); Machine.emitLabel(elseIfStack.top()); :} S END {: Machine.emitLabel(Top(endIfStack)); elseIfStack.pop(); endIfStack.pop(); :} + With a little work, you can see that an ELSE with no statement in it reduces to a normal if-then, meaning that a lot of this code can be combined and reused between the two cases. Lessons Learned: Change is Inevitable + As tools are used, new uses and patterns of use emerge, resulting in demand for new, unanticipated features. - these changes could be anticipated, but this is a ``toy'' problem - even when know change is coming, may want to implement system in pieces + if wait for ``complete'' understanding, may never start! + want to get something running quickly to get concrete feedback - fast enough? - what users really want? + Careful design cannot prevent change, but it can reduce the penalty - splitting WHILE and IF stacks not too bad; mostly a rename - going to pair of stacks is mostly a rename and adding new code - code was not changed very much - design not compromised very much + Design is sound because we matched solution structure (Sparc) to problem (domain) structure (Oberon), while respecting existing solution structure (CUP). - match through grammar eases implementation - use of stacks for inherited attributes simplifies evolution - a counter design is less stable, but still has a usage style that makes substituting a stack not so hard: "++" implies Push, etc.