CSc 453Compilers and Systems Software13 : Intermediate Code IDepartment of Computer ScienceUniversity of [email protected]° 2009 Christian CollbergIntroductionCompiler PhasesWe are here!ASTasmSemanticAnalyserInterm.Code GenIRMachineCode GenIRASTLexertokenssourceerrorsParsererrorsOptimizeerrorsIntermediate RepresentationsSome compilers use the AST as the only intermediaterepresentation. Optimizations (code improvements) areperformed directly on the AST, and machine code isgenerated directly from the AST.The AST is OK for machine-independent optimizations, suchas inlining (replacing a procedure call with the calledprocedure’s code).The AST is a bit too high-level for machine code generationand machine-dependent optimizations.Intermediate Representations. . .For this reason, some compilers generate a lower level(simpler, closer to machine code) representation from theAST. This representation is used during code generation andcode optimization.Intermediate CodeAdvantages of:1Fitting many front-ends to many back-ends,2Different development teams for front- and back-end,3Debugging is simplified,4Portable optimization.Requirements:1Architecture independent,2Language independent,3Easy to generate,4Easy to optimize,5Easy to produce machine code from.Mix-and-Match CompilersINTERMEDIATE REPRESENTATIONPascalPascal68k−compilerAdaMips−compiler Mips−compilerENDRONTFAda Pascal Modula−2 C++BACKSparcMips68000IBM/370ENDUNCOLA representation which is both architecture and languageindependent is known as an UNCOL, a Universal CompilerOriented Language.UNCOL is the holy grail of compiler design – many havesearch for it, but no-one has found it. Problems:1Programming language semantics differ from one language toanother,2Machine architectures differ.Intermediate Code. . .There are several different types of intermediaterepresentations:1Tree-Based.2Graph-Based.3Tuple-Based.4Linear representations.All representations contain the same information. Some areeasier to generate, some are easy to generate simple machinecode from, some are easy to generate good code from.IR — Intermediate Representation.Postfix NotationPostfix Notation*assignba 2 a 2+*Infix: b := (a ∗ 2) + (a ∗ 2)Postfix: b a 2 * a 2 * + :=Postfix notation is a parenthesis free notation for arithmeticexpression. It is essentially a linearized representation of anabstract syntax tree.In postfix notation an operator appears after its operands.Very simple to generate, very compact, easy to generatestraight-forward machine code from, difficult to generategood machine code from.Tree & DAG RepresentationsTree & DAG RepresentationTrees make good intermediate representations. We canrepresent the program as a sequence of expression trees.Each assignment, procedure call, or jump becomes oneindividual tree in the forest.Common Subexpression Elimination (CSE): Even if thesame (sub-) expression appears more than once in aprocedure, we should only compute its value once, and savethe result for future reference.One way of doing this is to build a graph representation,rather than a tree. In the following slides we see how theexpression a ∗ 2 gets two subtrees in the tree representationand one subtree in the DAG representation.Tree & DAG Representation. . .b := (a ∗ 2) + (a ∗ 2)*assignba 2 a 2+*Linearized TreeNr Op Arg1Arg21 ident a2 int 23 mul 1 24 ident a5 int 26 mul 4 57 add 3 68 ident b9 assign 8 7Tree & DAG Representation. . .b := (a ∗ 2) + (a ∗ 2)*assignb +a 2Linearized DagNr Op Arg1Arg21 ident a2 int 23 mul 1 24 add 3 35 ident b6 assign 5 4Sequence of Expression TreesX := 20;WHILE X < 10 DOX := X-1;A[X] := 10;IF X = 4 THENX := X - 2;ENDIF;ENDDO;Y := X + 5;XX:=20gotoB3:=XY+5gotoEXIT>=10B4X:=X−1X[]A X:=10X4B6<>:=X−2gotoB2EXIT:B4:B3:B5:B6:B2:Building DAGs. . .Repeatedly add subtrees to build DAG. Only add subtrees notalready in DAG. Store subtrees in a hash table. This is thevalue-number algorithm.For every insertion ofa subtree, check if(X OP Y ) ∈ DAG.X YOPPROCEDURE InsertNode (OP : Operator; L, R : Node) : Node;BEGINV := hashfunc (OP, L, R);N := HashTab.Lookup (V , OP, L, R);IF N = NullNode THENN := NewNode (OP, L, R);HashTab.Insert (V , N);END;RETURN N;Building DAGs – Example34625A+BAB+AB134625A+BAB(A+B)*CC+ABC*134625+ABC*+(A+B)*C+(A+B)A+BAB(A+B)*CC1Building DAGsFrom an expression/expression tree such as the one on the leftwe might generate the machine code (for some fictitiousarchitecture) on the right:a ∗ (b + c)41235+a*cbLOAD b, r0LOAD c, r1ADD r0, r1, r2LOAD a, r3MUL r2, r3, r4Can we generate better code from a DAG than a tree?Building DAGs. . .Example Expression:[(a + b) ∗ c + {(a + b) + e} ∗ (e + f )] ∗ [(a + b) ∗ c]Tree Representation:++a bc*+e f+a b+e*+a bc**Building DAGs. . .[(a + b) ∗ c + {(a + b) + e} ∗ (e + f )] ∗ [(a + b) ∗ c]DAG Representation:e*++a bc* *+ +fBuilding DAGs. . .Generating machine code from the tree yields 21 instructions.Code from TreeLOAD a, r0 ; aLOAD b, r1 ; bADD r0, r1, r2 ; a + bLOAD c, r0 ; cMUL r0, r2, r3 ; (a + b) ∗ cLOAD a, r0 ; aLOAD b, r1 ; bADD r0, r1, r2 ; a + bLOAD e, r0 ; eADD r2, r0, r4 ; (a + b) + eLOAD f, r0 ; fLOAD e, r1 ; eADD r0, r1, r0 ; f + eMUL r4, r0, r4 ; {(a + b) + e}∗; (e + f )ADD r3, r4, r4; Code for (a + b) ∗ c into r3MUL r4, r3, r0Building DAGs. . .Generating machine code from the DAG yields only 12instructions.Code from DAGLOAD a, r0 ; aLOAD b, r1 ; bADD r0, r1, r2 ; a + bLOAD c, r0 ; cMUL r0, r2, r3 ; (a + b) ∗ cLOAD e, r4 ; eADD r4, r2, r1 ; (a + b) +LOAD f, r0 ; fADD r0, r4, r0 ; f + eMUL r1, r0, r0ADD r0, r3, r0MUL r0, r3, r0Tuple CodesThree-Address CodeAnother common representation is three-address code. It isakin to assembly code, but uses an infinite number oftemporaries (registers) to store the results of operations.There are three common realizations of three-address code:quadruples, triples and indirect triples.Types of 3-Addr Statements:x := y op z Binary arithmetic or logical operation. Example:Mul, And.x := op y Unary arithmetic, conversion, or logical operation.Example: Abs, UnaryMinus, Float.x := y Copy statement.Three-Address Code. . .goto L Unconditional jump.if x relop y goto L Conditional jump. relop is one of <,>,<=,etc. If x relop y evaluates to True, then jump tolabel L. Otherwise continue with the next tuple.param X ; call P, n Make X the next parameter; make aprocedure call to P with n parameters.x := y[i] Indexed assignment. Set x to the value in thelocation i memory units beyond