DOC PREVIEW
Princeton COS 320 - Intermediate Representation

This preview shows page 1-2-20-21 out of 21 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Intermediate RepresentationLexer Parser Back EndSourceStream ofTokensAbstractSyntax Tree TargetIR’’’SemanticAnalysisIntermediate Representation (IR):• An abstract machine language• Expresses operations of target machine• Not specific to any particular machine• Independent of source languageIR code generation not necessary:• Semantic analysis phase can generate real assembly code directly.• Hinders portability and modularity.Computer Science 320Prof. David Walker-1-Intermediate RepresentationSuppose 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 clut-tered with source language specific details.Case 2: IR present• Need just n front-ends, m back ends.Computer Science 320Prof. David Walker-2-Intermediate RepresentationJavaMLPascalCC++SparcMIPSPentiumAlphaJavaMLPascalCC++SparcMIPSPentiumAlphaIRFIGURE 7.1. Compilers for five languages and four target machines:(left) without an IR, (right) with an IR.FromModern Compiler Implementation in ML,Cambridge University Press,c1998 Andrew W. AppelComputer Science 320Prof. David Walker-3-IR properties• Must be convenient for semantic analysis phase to produce.• Must be convenient to translate into real assembly code for all desired target ma-chines.– 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 selec-tion to form complex operations.Computer Science 320Prof. David Walker-4-IR expression treesThe 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 = sigdatatype 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 * expComputer Science 320Prof. David Walker-5-IR expression treesTREE continued:and stm = 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.labeland binop = PLUS|MINUS|MUL|DIV|AND|OR|LSHIFT|RSHIFT|ARSHIFT|XORand relop = EQ|NE|LT|GT|LE|GE|ULT|ULE|UGT|UGEendComputer Science 320Prof. David Walker-6-ExpressionsExpressions compute some value, possibly with side effects.CONST(i) integer constant iNAME(n) symbolic constant n corresponding to assembly language label (abstractname for memory address)TEMP(t) temporary t, or abstract/virtual register tBINOP(op, e1, e2) e1op e2, e1evaluated 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: ARSHIFTComputer Science 320Prof. David Walker-7-ExpressionsMEM(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 ⇒ loadCALL(f, l) application of function f to argument list l• subexpression f is evaluated first• arguments in list l are evaluated left to rightESEQ(s, e) the statement s evaluated for side-effects, e evaluated next for resultComputer Science 320Prof. David Walker-8-StatementsStatements 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 inwordSize bytes of memory stating at address aEXP(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 inequalityComputer Science 320Prof. David Walker-9-StatementsSEQ(s1, s2) statement s1followed by s2LABEL(l) label definition - constant value of l defined to be current machine codeaddress• 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 320Prof. 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.labelsdatatype 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 atrue-destination label, it will produce a Tree.stm which evaluates some condi-tionals and jumps to one of the destinations.Computer Science 320Prof. David Walker-11-Translation of Abstract Syntax - ConditionalsConditional: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.expval unNx: exp -> Tree.stmval unCx: exp -> (Temp.label * Temp.label -> Tree.stm)Computer Science 320Prof. David Walker-12-Translation of Abstract Syntax - ConditionalsThe three conversion functions:val unEx: exp -> Tree.expval unNx: exp -> Tree.stmval unCx: exp -> (Temp.label * Temp.label -> Tree.stm)a:=x>y:MOVE(TEMP(a), unEx(Cx(t,f) =>


View Full Document

Princeton COS 320 - Intermediate Representation

Download Intermediate Representation
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Intermediate Representation and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Intermediate Representation 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?