Intermediate Code Generation Reading List Aho Sethi Ullman Chapter 2 3 Chapter 6 1 6 2 Chapter 6 3 6 10 Note Glance through it only for intuitive understanding 01 14 19 course cpeg421 08s Topic 2a ppt 1 Component Based Approach to Building Compilers Source program in Language 1 Source program in Language 2 Language 1 Front End Language 2 Front End Non optimized Intermediate Code Intermediate code Optimizer Optimized Intermediate Code 01 14 19 Target 1 Code Generator Target 2 Code Generator Target 1 machine code Target 2 machine code course cpeg421 08s Topic 2a ppt 2 Intermediate Representation IR A kind of abstract machine language that can express the target machine operations without committing to too much machine details Why IR 01 14 19 course cpeg421 08s Topic 2a ppt 3 Without IR 01 14 19 C SPARC Pascal HP PA FORTRAN x86 C IBM PPC course cpeg421 08s Topic 2a ppt 4 With IR C SPARC Pascal HP PA IR 01 14 19 FORTRAN x86 C IBM PPC course cpeg421 08s Topic 2a ppt 5 With IR C Pascal IR Common Backend FORTRAN C 01 14 19 course cpeg421 08s Topic 2a ppt 6 Advantages of Using an Intermediate Language 1 Retargeting Build a compiler for a new machine by attaching a new code generator to an existing front end 2 Optimization reuse intermediate code optimizers in compilers for different languages and different machines Note the terms intermediate code intermediate language and intermediate representation are all used interchangeably 01 14 19 course cpeg421 08s Topic 2a ppt 7 Issues in Designing an IR Whether to use an existing IR if target machine architecture is similar if the new language is similar Whether the IR is appropriate for the kind of optimizations to be performed e g speculation and predication some transformations may take much longer than they would on a different IR 01 14 19 course cpeg421 08s Topic 2a ppt 8 Issues in Designing an IR Designing a new IR needs to consider Level how machine dependent it is Structure Expressiveness Appropriateness for general and special optimizations Appropriateness for code generation Whether multiple IRs should be used 01 14 19 course cpeg421 08s Topic 2a ppt 9 Multiple Level IR Source Program Semantic Check 01 14 19 High level IR High level Optimization Low level IR Target code Low level Optimization course cpeg421 08s Topic 2a ppt 10 Using Multiple level IR Translating from one level to another in the compilation process Preserving an existing technology investment Some representations may be more appropriate for a particular task 01 14 19 course cpeg421 08s Topic 2a ppt 11 Commonly Used IR Possible IR forms Graphical representations such as syntax trees AST Abstract Syntax Trees DAG Postfix notation Three address code SSA Static Single Assignment form IR should have individual components that describe simple things 01 14 19 course cpeg421 08s Topic 2a ppt 12 DAG Representation A variant of syntax tree Example D A B C A B C C D A 01 14 19 DAG Direct Acyclic Graph B C course cpeg421 08s Topic 2a ppt 13 Postfix Notation PN A mathematical notation wherein every operator follows all of its operands Examples The PN of expression 9 5 2 is 952 How about a b c d 01 14 19 ab cd course cpeg421 08s Topic 2a ppt 14 Postfix Notation PN Cont d Form Rules 1 If E is a variable constant the PN of E is E itself 2 If E is an expression of the form E1 op E2 the PN of E is E1 E2 op E1 and E2 are the PN of E1 and E2 respectively 3 If E is a parenthesized expression of form E1 the PN of E is the same as the PN of E1 01 14 19 course cpeg421 08s Topic 2a ppt 15 Three Address Statements A popular form of intermediate code used in optimizing compilers is three address statements Source statement x a b c d Three address statements with temporaries t1 and t2 t 1 b c t2 a t 1 x t2 d 01 14 19 course cpeg421 08s Topic 2a ppt 16 Three Address Code The general form x y op z x y and z are names constants compiler generated temporaries op stands for any operator such as x 5 y might be translated as t1 x 5 t2 t1 y 01 14 19 course cpeg421 08s Topic 2a ppt 17 Syntax Directed Translation Into Three Address Temporary In general when generating three address statements the compiler has to create new temporary variables temporaries as needed We use a function newtemp that returns a new temporary each time it is called Recall Topic 2 when talking about this topic 01 14 19 course cpeg421 08s Topic 2a ppt 18 Syntax Directed Translation Into Three Address The syntax directed definition for E in a production id E has two attributes 1 E place the location variable name or offset that holds the value corresponding to the nonterminal 2 E code the sequence of three address statements representing the code for the nonterminal 01 14 19 course cpeg421 08s Topic 2a ppt 19 Example Syntax Directed Definition term ID term place ID place term code term1 term2 ID term1 place newtemp term1 code term2 code ID code gen term1 place term2 place ID place expr term expr place term place expr code term code expr1 expr2 term expr1 place newtemp expr1 code expr2 code term code gen expr1 place expr2 place term place 01 14 19 course cpeg421 08s Topic 2a ppt 20 Syntax tree vs Three address code Expression A B C B A B B A B C A B T1 B C T2 A T1 T3 B T4 T3 A T5 T2 T4 T6 T5 B Three address code is a linearized representation of a syntax tree or a DAG in which explicit names temporaries correspond to the interior nodes of the graph 01 14 19 course cpeg421 08s Topic 2a ppt 21 DAG vs Three address code Expression D A B C A B C C D A B C T1 A T2 C T3 B T2 T4 T1 T3 T5 T1 T3 T6 T4 T5 T7 T2 T8 T6 T7 D T8 T1 B C T2 A T1 T3 A T1 T4 T2 T3 T5 C T6 T4 T5 D T6 Question Which IR code sequence is better 01 14 19 course cpeg421 08s Topic 2a ppt 22 Implementation of Three Address Code Quadruples Four fields op arg1 arg2 result Array of struct op arg1 arg2 result x y op z is represented as op y z x arg1 arg2 and result are usually pointers to symbol table entries May need to use many temporary names Many assembly instructions are like quadruple but arg1 arg2 and result are real registers 01 14 19 course cpeg421 08s Topic 2a ppt 23 Implementation of Three Address Code Con t Triples Three fields op arg1 and arg2 Result is implicit arg1 and arg2 are either pointers to the symbol table or index pointers to the triple structure Example d a …