Chap 8: Intermedicate Code GenerationOverviewMotivationWhat We WantRecall ASTs and DAGsAttribute GrammarRepresenting Attribute GrammarsObjectiveThe Intermediate Code Generation MachineTemporariesWhat is Three-Address Coding?Types of Three Address StatementsSlide 13Slide 14Attribute Grammar for AssignmentsSlide 16Three Address Code for While LoopsAttribute Grammar for WhileDeclarationsAttribute Grammar for Memory LayoutHandling Nested Procedure/FunctionsNested Symbol TableCorresponding Attribute GrammarFrom Concatenation to GenerationRevised Attribute Grammar with EmitAttribute Grammar for Boolean ExpressionsGenerated CodeCode Generation - ConceptualSlide 29Review Prof. Michel’s ApproachC--C-- ExampleBigger ExampleSpecial 3-address StatementsBranching StatementsFunction Call SequenceMethod Call SequenceIn CalleeIndexed AssignmentsIndexed Assigments in C-- IRClasses ?Class InheritanceIn practice...Method CallComplete ExampleJumpsImplementationInstruction HierarchyLocation ADTLocation ExamplesDealing With DeclarationsClass DeclarationInstance Variable [aka Attributes]Method DeclarationLocal VariablesAll Other GenerationAssignmentsgenerate(E)LiteralIdentifierMethod InvocationSlide 62Class InstantiationArray AccessArray accessArray Access TemplateMulti-Dimentional Array?Array InstantiationRevisit Array AccessSlide 70Slide 71Field AccessBoolean ExpressionsShort-Circuit EvaluationBoolean ConjunctionBoolean DisjunctionIf-Then-ElseWhileSwitch-caseSwitch StatementSlide 81Back-patching vs symbolic LabelsConcluding Remarks/Looking AheadCH8.1CSE4100Chap 8: Intermedicate Code GenerationChap 8: Intermedicate Code GenerationProf. Steven A. Demurjian Computer Science & Engineering DepartmentThe University of Connecticut371 Fairfield Way, Unit 2155Storrs, CT [email protected]://www.engr.uconn.edu/~steve(860) 486 - 4818Material for course thanks to:Laurent MichelAggelos KiayiasRobert LeBarreCH8.2CSE4100OverviewOverviewGoal: Generate a Machine Independent Intermediate Goal: Generate a Machine Independent Intermediate Form that is Suitable for Optimization and PortabilityForm that is Suitable for Optimization and PortabilityWe’ll Focus on We’ll Focus on Revisit AST and DAGs with Attribute GrammarsIntroduce and Elaborate on Three Address CodingReview 3AC for: DeclarationsAssignments and Boolean ExpressionsCase Statements and Procedure CallsReview Prof. Michel’s Approach to Intermediate Code GenerationConcluding Remarks/Looking AheadCH8.3CSE4100MotivationMotivationWhat we have so far...What we have so far...A Parser treeWith all the program informationKnown to be correct–Well-typed–Nothing missing–No ambiguitiesWhat we need...What we need...Something “Executable”Closer to An operations scheduleActual machine level of abstractionCH8.4CSE4100What We WantWhat We WantA Representation thatA Representation thatIs closer to actual machineIs easy to manipulateIs target neutral (hardware independent)Can be interpretedCH8.5CSE4100Recall ASTs and DAGsRecall ASTs and DAGsIntermediate Forms of a Program:Intermediate Forms of a Program:ASTs: Abstract Syntax Trees (below left)DAGs: Directed Acyclic Graphs (below right)What is the Expression?assigna +* *bcuminusbcuminusassigna +*bcuminusCH8.6CSE4100Attribute GrammarAttribute GrammarAttribute Grammar for Generating an AST as a side Attribute Grammar for Generating an AST as a side Effect of the Translation Process:Effect of the Translation Process:CH8.7CSE4100Representing Attribute GrammarsRepresenting Attribute GrammarsTwo Different Forms:Two Different Forms:Linked Data StructureMulti-Dimensional ArrayCH8.8CSE4100ObjectiveObjectiveDirectly Generate Code From AST or DAG as a Side Directly Generate Code From AST or DAG as a Side Effect of Parsing Process (Attribute Grammar)Effect of Parsing Process (Attribute Grammar)Consider Code Below:Consider Code Below:Each is Referred to as “3 Address Coding (3AC)” since Each is Referred to as “3 Address Coding (3AC)” since there are at Most 3 Addresses per Statementthere are at Most 3 Addresses per StatementOne for Result and At Most 2 for OperandsCH8.9CSE4100The Intermediate Code Generation MachineThe Intermediate Code Generation MachineA Machine withA Machine withInfinite number of temporaries (think registers)Simple instructions3-operandsBranchingCalls with simple calling conventionSimple code structureArray of instructionsLabels to define targets of branches.CH8.10CSE4100TemporariesTemporariesThe machine has an infinite number of temporariesThe machine has an infinite number of temporariesCall them t0, t1, t2, .... Temporaries can hold values of any typeThe type of the temporary is derived from the generationTemporaries go out of scope with the function they are inCH8.11CSE4100What is Three-Address Coding?What is Three-Address Coding?A simple type of instructionA simple type of instruction3 / 2 Operands x,y,zEach operand could beA literalA variableA temporaryExampleExamplex := y op zx := y op zx + y * zx + y * zt0 := y * zt1 := x + t0 t0 := y * zt1 := x + t0 x := op zx := op zCH8.12CSE4100Types of Three Address StatementsTypes of Three Address StatementsAssignment Statements of Form:Assignment Statements of Form:X := Y op Zop is a Binary Arithmetic or Logical OperationAssignment Instructions of Form:Assignment Instructions of Form:X := op Yop is Unary Operation such as Unary Minus, Logical Negative, Shift/Conversion OperationsCopy Statements of Form:Copy Statements of Form:X := Y where value of Y assigned to XUnconditional Jump of Form:Unconditional Jump of Form:goto L which goes to a three address statement labeled with LCH8.13CSE4100Types of Three Address StatementsTypes of Three Address StatementsConditional Jumps of Form:Conditional Jumps of Form:if x relop y goto Lwith relop as relational operators and the goto executed if the x relop y is trueParameter Operations of Form:Parameter Operations of Form:param a (a parameter of function)call p, n (call function p with n parameters)return y (return value y from function – optional)param aparam bparam ccall p, 3CH8.14CSE4100Types of Three Address StatementsTypes of Three Address StatementsIndexed Assignments of Form:Indexed Assignments of Form:X := Y[i] (Set X to i-th memory location of