DOC PREVIEW
Princeton COS 320 - Intermediate Representation

This preview shows page 1-2-24-25 out of 25 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 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 25 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 25 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 25 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 25 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-Strings¯All string operations performed by run-time system functions.¯In Tiger, C, string literal is constant address of memory segment initialized to char-acters in string.– In assembly, label used to refer to this constant address.– Label definition includes directives that reserve and initialize memory.‘‘foo’’:1. Translate module creates new label.2. Tree.NAME() returned: used to refer to string.3. String fragment “foo” created with label. Fragment is handed to code emitter,which emits directives to initialize memory with the characters of “foo” at address.Computer Science 320Prof. David Walker-1-StringsString Representation:Pascal fixed-length character arrays, padded with blanks.C variable-length character sequences, terminated by ‘/000’Tiger any 8-bit code allowed, including ‘/000’foo3label:"foo"Computer Science 320Prof. David Walker-2-Strings¯Need to invoke run-time system functions– string operations– string memory allocation¯Frame.externalCall: string * Tree.exp -> Tree.expFrame.externalCall("stringEqual", [s1, s2])– Implementation takes into account calling conventions of external functions.– Easiest implementation:fun externalCall(s, args) =T.CALL(T.NAME(Temp.namedlabel(s)), args)Computer Science 320Prof. David Walker-3-Array Creationtype intarray = array of intvar a:intarray := intarray[10] of 7Call run-time system function initArray to malloc and initialize array.Frame.externalCall("initArray", [CONST(10), CONST(7)])Computer Science 320Prof. David Walker-4-Array AccessesGiven array variable a,&(a[0]) = a&(a[1]) = a + w, where w is the word-size of machine&(a[2]) = a + (2 * w)...Let e be the IR tree for a:a[i]:MEM(BINOP(PLUS, e, BINOP(MUL, i, CONST(w))))Compiler must emit code to check whether i is out of bounds.Computer Science 320Prof. David Walker-19-Record Creationtype rectype = { f1:int, f2:int, f3:int }var a:rectype := rectype{f1 = 4, f2 = 5, f3 = 6}ESEQ(SEQ( MOVE(TEMP(result),Frame.externalCall("allocRecord",[CONST(12)])),SEQ( MOVE(BINOP(PLUS, TEMP(result), CONST(0*w)),CONST(4)),SEQ( MOVE(BINOP(PLUS, TEMP(result), CONST(1*w)),CONST(5)),SEQ( MOVE(BINOP(PLUS, TEMP(result), CONST(2*w)),CONST(6)))))),TEMP(result))¯allocRecord is an external function which allocates space and returns address.¯result is address returned by allocRecord.Computer Science 320Prof. David Walker-5-Record Accessestype rectype = {f1:int, f2:int, f3:int}|||offset: 0 1 2var a:rectype := rectype{f1=4, f2=5, f3=6}Let e be IR tree for a:a.f3:MEM(BINOP(PLUS, e, BINOP(MUL, CONST(3), CONST(w))))Compiler must emit code to check whether a is nil.Computer Science 320Prof. David Walker-20-Conditional Statementsif e1then e2else e3• Treat e1as Cx expression ⇒ apply unCx.• Treat e2, e3as Ex expressions ⇒ apply unEx.Ex(ESEQ(SEQ(unCx(e1)(t, f),SEQ(LABEL(t),SEQ(MOVE(TEMP(r), unEx(e2)),SEQ(JUMP(NAME(join)),SEQ(LABEL(f),SEQ(MOVE(TEMP(r), unEx(e3)),LABEL(join)))))))TEMP(r)))Computer Science 320Prof. David Walker-21-While LoopsOne layout of a while loop:while CONDITION do BODYtest:if not(CONDITION) goto doneBODYgoto testdone:A break statement within body is a JUMP to label done.transExp and transDec need formal parameter “break”:¯passed done label of nearest enclosing loop¯needed to translate breaks into appropriate jumps¯when translating while loop, transExp recursively called with loop done label inorder to correctly translate body.Computer Science 320Prof. David Walker-6-For LoopsBasic idea: Rewrite AST into let/while AST; call transExp on result.fori:=lotohidobodyBecomes:letvar i := lovar limit := hiinwhile (i <= limit) do(body;i:=i+1)endComplication:If limit == maxint, then increment will overflow in translated version.Computer Science 320Prof. David Walker-7-Function Callsf(a1, a2, ..., an) =>CALL(NAME(l_f), sl::[e1, e2, ..., en])¯sl static link of f (computable at compile-time)¯To compute static link, need:– lf : level of f– lg : level of g, the calling function¯Computation similar to simple variable access.Computer Science 320Prof. David Walker-8-DeclarationsConsider type checking of “let” expression:fun transExp(venv, tenv) =...| trexp(A.LetExp{decs, body, pos}) =letval {venv = venv’, tenv = tenv’} =transDecs(venv, tenv, decs)intransExp(venv’, tenv’) bodyend¯Need level, break.¯What about variable initializations?Computer Science 320Prof. David Walker-9-DeclarationsNeed to modify code to handle IR translation:1. transExp, transDec require level to handle variable references.2. transExp, transDec require break to handle breaks in loops.3. transDec must return Translate.exp list of assignment statements correspondingto variable initializations.¯Will be prepended to body.¯Translate.exp will be empty for function and type declarations.Computer Science 320Prof. David Walker-10-Function Declarations¯Cannot specify function headers with IR tree, only function bodies.¯Special “glue” code used to complete the function.¯Function is translated into assembly language segment with three components:– prologue– body– epilogueComputer Science 320Prof. David Walker-11-Function ProloguePrologue precedes body in assembly version of function:1. Assembly directives that announce beginning of function.2. Label definition for function name.3. Instruction to adjust stack pointer (SP) - allocate new frame.4. Instructions to save escaping arguments into stack frame, instructions to move non-escaping arguments into fresh temporary registers.5. Instructions to store into stack frame any callee-save registers used within function.Computer Science 320Prof. David Walker-12-Function EpilogueEpilogue follows body in assembly version of function:6. Instruction to move function result (return value) into return value register.7. Instructions to restore any callee-save registers used within function.8. Instruction to adjust stack pointer (SP) - deallocate frame.9. Return instructions (jump to return address).10. Assembly directives that announce end of


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?