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 Intermediate Representation Suppose we wish to build compilers for n source languages and m target machines Case 1 no IR Need separate compiler for each source language target machine combination A total of n m compilers necessary Front end becomes cluttered with machine specific details back end becomes cluttered with source language specific details Case 2 IR present Need just n front ends m back ends Computer Science 320 Prof David Walker 2 Intermediate Representation Java ML Java Sparc Sparc ML MIPS Pascal Pascal MIPS IR Pentium Pentium C C FIGURE 7 1 Computer Science 320 Prof David Walker C Alpha C Compilers for five languages and four target machines left without an IR right with an IR From Modern Compiler Implementation in ML c Cambridge University Press 1998 Andrew W Appel 3 Alpha IR properties Must be convenient for semantic analysis phase to produce Must be convenient to translate into real assembly code for all desired target machines RISC processors execute operations that are rather simple Examples load store add shift branch IR should represent abstract load abstract store abstract add etc CISC processors execute more complex operations Examples multiply add add to from memory Simple operations in IR may be clumped together during instruction selection to form complex operations Computer Science 320 Prof David Walker 4 IR expression trees The IR may be represented in many forms Liberty IMPACT and Elcor compilers use pseudo assembly gcc and the class project use expression trees Intel s Electron and HP s production compiler use both Expression trees exp constructs that compute some value possibly with side effects stm constructs that perform side effects and control flow signature TREE sig datatype exp CONST of int NAME of Temp label TEMP of Temp temp BINOP of binop exp exp MEM of exp CALL of exp exp list ESEQ of stm exp Computer Science 320 Prof David Walker 5 IR expression trees TREE continued and stm and binop and relop MOVE of exp exp EXP of exp JUMP of exp Temp label list CJUMP of relop exp exp Temp label Temp label SEQ of stm stm LABEL of Temp label PLUS MINUS MUL DIV AND OR LSHIFT RSHIFT ARSHIFT XOR EQ NE LT GT LE GE ULT ULE UGT UGE end Computer Science 320 Prof David Walker 6 Expressions Expressions compute some value possibly with side effects CONST i integer constant i NAME n symbolic constant n corresponding to assembly language label abstract name for memory address TEMP t temporary t or abstract virtual register t BINOP op e1 e2 e1 op e2 e1 evaluated before e2 integer arithmetic operators PLUS MINUS MUL DIV integer bit wise operators AND OR XOR integer logical shift operators LSHIFT RSHIFT integer arithmetic shift operator ARSHIFT Computer Science 320 Prof David Walker 7 Expressions MEM e contents of wordSize bytes of memory starting at address e wordSize is defined in Frame module if MEM is used as left operand of MOVE statement store if MEM is used as right operand of MOVE statement load CALL f l application of function f to argument list l subexpression f is evaluated first arguments in list l are evaluated left to right ESEQ s e the statement s evaluated for side effects e evaluated next for result Computer Science 320 Prof David Walker 8 Statements Statements have side effects and perform control flow MOVE TEMP t e evaluate e and move result into temporary t MOVE MEM e1 e2 evaluate e1 yielding address a evaluate e2 store result in wordSize bytes of memory stating at address a EXP e evaluate expression e discard result JUMP e labs jump to address e e may be literal label NAME l or address calculated by expression labs specifies all locations that e can evaluate to used for dataflow analysis jump to literal label l JUMP NAME l l CJUMP op e1 e2 t f evaluate e1 then e2 compare results using op if true jump to t else jump to f EQ NE signed unsigned integer equality and non equality LT GT LE GE signed integer inequality ULT UGT ULE UGE unsigned integer inequality Computer Science 320 Prof David Walker 9 Statements SEQ s1 s2 statement s1 followed by s2 LABEL l label definition constant value of l defined to be current machine code address similar to label definition in assembly language use NAME l to specify jump target calls etc The statements and expressions in TREE can specify function bodies Function entry and exit sequences are machine specific and will be added later Computer Science 320 Prof David Walker 10 Translation of Abstract Syntax if Absyn exp computes value Tree exp if Absyn exp does not compute value Tree stm if Absyn exp has boolean value Tree stm and Temp labels datatype exp Ex of Tree exp Nx of Tree stm Cx of Temp label Temp label Tree stm Ex expression represented as a Tree exp Nx no result represented as a Tree stm Cx conditional represented as a function Given a false destination label and a true destination label it will produce a Tree stm which evaluates some conditionals and jumps to one of the destinations Computer Science 320 Prof David Walker 11 Translation of Abstract Syntax Conditionals Conditional x y Cx fn t f CJUMP GT x y t f a b c d Cx fn t f SEQ CJUMP GT a b t z SEQ LABEL z CJUMP LT c d t f May need to convert conditional to value a x y Cx corresponding to x y must be converted into Tree exp e MOVE TEMP a e Need three conversion functions val unEx exp Tree exp val unNx exp Tree stm val unCx exp Temp label Temp label Tree stm Computer Science 320 Prof David Walker 12 Translation of Abstract Syntax Conditionals The three conversion functions val unEx exp Tree exp val unNx exp Tree stm val unCx exp Temp label Temp label Tree stm a x y MOVE TEMP a unEx Cx t f unEx makes a Tree exp even though e was Cx Computer Science 320 Prof David Walker 13 Translation of Abstract Syntax Implementation of function UnEx structure T Tree fun unEx Ex e e unEx Nx s T ESEQ s T CONST 0 unEx Cx genstm let val r Temp newtemp val t Temp newlabel val f Temp newlabel in T ESEQ seq T MOVE T TEMP r T CONST 1 genstm t f T LABEL f T MOVE T TEMP r T CONST 0 T LABEL t T TEMP r end Computer Science