Intermediate Representation Source Lexer Stream of Tokens Parser Abstract Syntax Tree Semantic Analysis IR Back End Intermediate Representation IR An abstract machine language Expresses operations of target machine Not specific to any particular machine Independent of source language IR code generation not necessary Semantic analysis phase can generate real assembly code directly Hinders portability and modularity Computer Science 320 Prof David Walker 1 Target Strings All string operations performed by run time system functions In Tiger C string literal is constant address of memory segment initialized to characters in string In assembly label used to refer to this constant address Label definition includes directives that reserve and initialize memory foo 1 Translate module creates new label 2 Tree NAME returned used to refer to string 3 String fragment foo created with label Fragment is handed to code emitter which emits directives to initialize memory with the characters of foo at address Computer Science 320 Prof David Walker 1 Strings String Representation Pascal fixed length character arrays padded with blanks C variable length character sequences terminated by 000 Tiger any 8 bit code allowed including 000 foo label 3 f o o Computer Science 320 Prof David Walker 2 Strings Need to invoke run time system functions string operations string memory allocation Frame externalCall string Tree exp Tree exp Frame externalCall stringEqual s1 s2 Implementation takes into account calling conventions of external functions Easiest implementation fun externalCall s args T CALL T NAME Temp namedlabel s args Computer Science 320 Prof David Walker 3 Array Creation type intarray array of int var a intarray intarray 10 of 7 Call run time system function initArray to malloc and initialize array Frame externalCall initArray CONST 10 CONST 7 Computer Science 320 Prof David Walker 4 Array Accesses Given array variable a a 0 a a 1 a w where w is the word size of machine a 2 a 2 w Let e be the IR tree for a a i MEM BINOP PLUS e BINOP MUL i CONST w Compiler must emit code to check whether i is out of bounds Computer Science 320 Prof David Walker 19 Record Creation type rectype f1 int f2 int f3 int var a rectype rectype f1 4 f2 5 f3 6 ESEQ SEQ MOVE TEMP result Frame externalCall allocRecord CONST 12 SEQ MOVE BINOP PLUS TEMP result CONST 0 w CONST 4 SEQ MOVE BINOP PLUS TEMP result CONST 1 w CONST 5 SEQ MOVE BINOP PLUS TEMP result CONST 2 w CONST 6 TEMP result allocRecord is an external function which allocates space and returns address result is address returned by allocRecord Computer Science 320 Prof David Walker 5 Record Accesses type rectype f1 int f2 int f3 int offset 0 1 2 var a rectype rectype f1 4 f2 5 f3 6 Let e be IR tree for a a f3 MEM BINOP PLUS e BINOP MUL CONST 3 CONST w Compiler must emit code to check whether a is nil Computer Science 320 Prof David Walker 20 Conditional Statements if e1 then e2 else e3 Treat e1 as Cx expression apply unCx Treat e2 e3 as Ex expressions apply unEx Ex ESEQ SEQ unCx e1 t f SEQ LABEL t SEQ MOVE TEMP r unEx e2 SEQ JUMP NAME join SEQ LABEL f SEQ MOVE TEMP r unEx e3 LABEL join TEMP r Computer Science 320 Prof David Walker 21 While Loops One layout of a while loop while CONDITION do BODY test if not CONDITION goto done BODY goto test done A break statement within body is a JUMP to label done transExp and transDec need formal parameter break passed done label of nearest enclosing loop needed to translate breaks into appropriate jumps when translating while loop transExp recursively called with loop done label in order to correctly translate body Computer Science 320 Prof David Walker 6 For Loops Basic idea Rewrite AST into let while AST call transExp on result for i lo to hi do body Becomes let var i lo var limit hi in while i limit do body i i 1 end Complication If limit maxint then increment will overflow in translated version Computer Science 320 Prof David Walker 7 Function Calls f a1 a2 an CALL NAME l f sl e1 e2 en sl static link of f computable at compile time To compute static link need l f level of f l g level of g the calling function Computation similar to simple variable access Computer Science 320 Prof David Walker 8 Declarations Consider type checking of let expression fun transExp venv tenv trexp A LetExp decs body pos let val venv venv tenv tenv transDecs venv tenv decs in transExp venv tenv body end Need level break What about variable initializations Computer Science 320 Prof David Walker 9 Declarations Need to modify code to handle IR translation 1 transExp transDec require level to handle variable references 2 transExp transDec require break to handle breaks in loops 3 transDec must return Translate exp list of assignment statements corresponding to variable initializations Will be prepended to body Translate exp will be empty for function and type declarations Computer Science 320 Prof David Walker 10 Function Declarations Cannot specify function headers with IR tree only function bodies Special glue code used to complete the function Function is translated into assembly language segment with three components prologue body epilogue Computer Science 320 Prof David Walker 11 Function Prologue Prologue precedes body in assembly version of function 1 Assembly directives that announce beginning of function 2 Label definition for function name 3 Instruction to adjust stack pointer SP allocate new frame 4 Instructions to save escaping arguments into stack frame instructions to move nonescaping arguments into fresh temporary registers 5 Instructions to store into stack frame any callee save registers used within function Computer Science 320 Prof David Walker 12 Function Epilogue Epilogue follows body in assembly version of function 6 Instruction to move function result return value into return value register 7 Instructions to restore any callee save registers used within function 8 Instruction to adjust stack pointer SP deallocate frame 9 Return instructions jump to return address 10 Assembly directives that announce end of function Steps 1 3 8 10 depend on exact size of stack frame These are generated late after register allocation Step 6 MOVE TEMP RV unEx body Computer Science 320 Prof David Walker 13 Fragments signature FRAME sig datatype frag STRING of Temp label string PROC of body Tree stm frame frame end Each function declaration translated into fragment Fragment translated into assembly body field is instruction sequence 4 5 6 7 frame