L3 Compiler Internals GuideMike De Rosa and Peter Lee15-745 Optimizing CompilersSpring 20061 IntroductionThis is a quick guide to the internals of the L3 compilers for the Spring 2006incarnation of 15-745 Optimizing Compilers. This guide does not providecomprehensive documentation for the compilers, but rather a few startingpoints to help you in your assigned tasks.There are three versions of the compiler. All three versions compile thesame language, called L3. L3 is a safe, simple, C-like language. It is notintended to be a practical language for writing real-world programs, butinstead an object of study for compiler optimizations. The three compilers,which are each written in a different programming language, are designed toprovide a relatively small and simple “sandbox” for experimenting with fairlyrealistic optimization problems. So, while the L3 compilers are not s eriousresearch tools (like MachSUIF do provide most of what you need to reach thecurrent horizon of contemporary research in compiler design. As such, L3 isan excellent “jumping off” point for anyone needing to gain background forresearch in the area.The three L3 compilers are written in Java, Objective CAML, and Stan-dard ML. All three compilers use the standard C preprocessor (cpp) to handlemacro definitions, include files, etc., and produce target files containing theASCII text of x86 assembly code. The x86 code is written in the AT&Tsyntax, for assembly by the GNU assembler (normally accessed via the gccprogram). Note that the AT&T assembly syntax is different than the stan-dard syntax defined by Intel. In particular, in the AT&T assembly syntax,operands are placed in left-to-right order (this is the opposite of the Intel1syntax), and operand length specifications are attached as suffixes to theoperands instead of the operator. So, for example, the instruction to copya 32-bit word from the third stack slot into the %eax register is written inGNU syntax like this:movl 8(%ebp), %eaxwhereas in the Intel syntax it is written as follows:mov eax, word[ebp+8]See the L3 Reference document for more details about the L3 languageand how to build and use the compilers.2 Intermediate RepresentationThe 15-745 course is concerned only with analysis and optimization, andas such we will not describe the front end of the compiler that performsparsing, typechecking, and translation into an intermediate representation(IR). The only exception to this is the description of the top level controlof the compiler, which determines exactly what phases get executed and inwhat order. These things will be described in the next sections. Here, wewill focus on the intermediate representations.The L3 compilers use, mainly, a tree form IR. The IR has constructorsfor representing statements (representing code to be executed for effect) andexpressions (code to be executed for effect and value). In addition to state-ments and expressions, there are tree forms for basic arithmetic, relational,and logical operators, as well as values, which include words, labels, temps,and strings. (Strings are used only for assembly comments.)We now describe the basic structure of the tree IR, followed by theimplementation-specific details for each of the L3 c ompilers. We presenteach statement and expression construct in Backus-Naur Form, along withan informal description of the semantics.2Statement constructorsstm ::= COMMENT string. This has no effect, but generally results ina comment being inserted into the target ass embly file. Useful fordebugging purposes.stm ::= MOVE expdexps. Copy the value of expsinto expd.stm ::= EXP exp. Evaluate exp for effect.stm ::= JUMP label. Transfer control to the statement with label label.stm ::= CJUMP relop exp1exp2labeltlabelf. Compute exp1relop exp2.If true, then transfer control to label labelt, else labelf.stm ::= SEQ stm stm. Execute the statements in sequence.stm ::= LABEL label. Mark this statement as a potential jump destina-tion.stm ::= NOP. Do nothing.Expression constructorsexp ::= CONST word. Defines a constant with a given 32-bit value (in-cluding boolean constants).exp ::= NAME label. Defines a label value.exp ::= TEMP temp. Refers to the value of the pseudo-register, temp.exp ::= BINOP binop exp exp. The value of the specified binary oper-ator, applied to the two operand expressions.exp ::= MEM exp. Evaluates exp as a heap-memory address. In r-valuecontexts, refers to the contents of the heap-memory cell. In l-valuecontexts, refers to the address of the cell.exp ::= CALL symbol exp*. Evaluates the argument expressions and thencalls the named function, returning its return value.exp ::= ESEQ stm exp. Executes the statment for effect, and then eval-uates the expression, returning its value.3Version-specific detailsJava verion. The IR is implemented in package edu.cmu.cs.l3.tree. TheIR has two base classes, IRExpression and IRStatement. In additionto the base IR, there is also an expression-list construct, which can takea number of expressions in sequence, execute them, and return the lastvalue. As a utility class, there is IRPrint, which pretty-prints any IRthat it is given.All IR classes, with the exception of IRPrint, are visitable, using thevisitor interface defined in edu.cmu.cs.l3.general.Visitable.The abstract syntax is translated to the IR and canonicalized in theclass edu.cmu.cs.l3.translate.Translator.Objective CAML ver sion. The IR is implemented in the module Ir, de-fined in the OCaml source file, ir.ml. In addition to the statement andexpression constructors described above, the OCaml version also definestwo constructors, PHI and INVARIANT, though neither are used.The Ir module also provides a number of pretty-printing functions, in-clude pexp and pstmt, which convert expressions and statements intostrings.Abstract syntax trees are translated into IR form by the Translatemodule, and then linearized by the module Canon.Standard ML version. The IR is implemented in module Tree, defined inthe SML source file, trans/tree.sml. The Tree module also providesa number of pretty-printing functions, include pp exp and pp stmt,which convert expressions and statements into strings.Abstract syntax trees are translated into IR form by the Translatemodule, defined in trans/trans.fun, and then linearized by the mod-ule Canon, defined in flow/canon.sml.43 Inserting Optimization PhasesMost of the optimizations in this course will be performed on the IR. However,some optimizations may work best on the tree form
View Full Document
Unlocking...