编译原理教学课件：Chapter 7 - Code Generation

1、2022-4-261Code Generation2022-4-262nGenerate executable code for a target machine that is a faithful representation of the semantics of the source codenCode generation depends qthe characteristics of the source language qdetailed information about the target architectureqthe structure of the runtime

2、 environmentqthe operating system running on the target machine2022-4-263Code generation is typically broken into several steps1.Intermediate code generation2.Generate some form of assembly code instead of actual executable code3.OptimizationnTo improve the speed and size of the target codenIn this

3、chapter, we will talk about general techniques of code generation rather than present a detailed description for a particular target machine2022-4-2647.1 Intermediate Code and Data Structures for Code Generation2022-4-265Intermediate Representation (IR)nA data structure that represents the source pr

4、ogram during translation is called an intermediate representation, or IR, for shortqFor example: abstract syntax treenSuch an intermediate representation that resembles target code is called intermediate code2022-4-266Intermediate codenThe need for intermediate codeqAbstract syntax tree does not res

5、emble target code, particularly in its representation of control flow constructsnIntermediate codeqRepresentation of the syntax tree in sequential form that more closely resembles target code2022-4-267nAdvantage of intermediate codeqIntermediate code is particularly useful when the goal of the compi

6、ler is to produce extremely efficient code;qIntermediate code can also be useful in making a compiler more easily retargetable.nPopular forms of intermediate codeqThree-address codeqP-code2022-4-2687.1.1 Three-Address Code2022-4-269nThe most basic instruction of three address code has the general fo

7、rm x = y op zqwhich represents the evaluation of expressionsqx, y, z are names, constants or compiler-generated temporary namesqop stands for any arithmetic or logical operator, such as + ,andn“Three-address code” comes form this form of instruction, since in general each of x, y and z represents an

8、 address in memory2022-4-26102*a+(b-3) with syntax treeThe corresponding three-address code ist1 = 2 * at2 = b - 3t3 = t1 + t2where t1, t2, t3 are names for temporaries, they correspond to the interior nodes of the syntax tree and represent their computed values+* -2ab32022-4-2611Other instructions

9、of three-address codenThree-address code for each construction of a standard programming language1.Assignment statement has the formx=y op zwhere op is a binary operation2.Assignment statement has the form x=op ywhere op is a unary operation3.Copy statement has the formx=y where the value of y is as

10、signed to x2022-4-26124.The unconditional jump goto L5.Conditional jumps, such as if B goto Lif_false B goto Lif A rop B goto L6.Statement “Label L” represents the position of the jump address7.“read x” 8.“write x”9.Statement “halt” serves to mark the end of the code2022-4-2613Figure 7.1 Sample TINY

11、 program: sample program in TINY language - computes factorial read x ; input an integer if 0 x then dont compute if x = 0 fact:=1;repeat fact:=fact*x;x:=x-1until x=0;write fact output factorial of x ends2022-4-2614nThe Three-address codes for above TINY programread x ; if 0 0if_false t1 goto L1fact

12、=1label L2t2=fact*xfact=t2t3=x-1x=t3t4= x=0if_false t4 goto L2write factlabel L1halt2022-4-26157.1.2 The Implementation of Three-Address Code2022-4-2616nA three-address statement is an abstract form of intermediate code.nIn a compiler, these statements can be implemented as records with fields for t

13、he operator and operands.nTwo such representations are quadruples and triples2022-4-2617QuadruplenEach three-address instruction contains four fields: one for the operation and three for the addressnFor those instructions that need fewer than three addresses, one or more of the address fields is giv

14、en a null or “empty” value2022-4-2618 (rd, x , _ , _ )(gt, x, 0, t1 )(if_f, t1, L1, _ )(asn, 1,fact, _ )(lab, L2, _ , _ )(mul, fact, x, t2 )(asn, t2, fact, _ )(sub, x, 1, t3 )(asn, t3, x, _ )(eq, x, 0, t4 )(if_f, t4, L2, _)(wri, fact, _, _ )(lab, L1, _ , _ )(halt, _, _, _ )read xt1=x0if_false t1 got

15、o L1fact=1label L2t2=fact*xfact=t2t3=x-1x=t3t4= x=0if_false t4 goto L2write factlabel L1haltQuadruple implementation for the three-address code of the previous example2022-4-2619TriplenEach three-address instruction contains three fields: one for the operation and two for the addressnThis implementa

16、tion uses the instructions themselves to represent the temporariesnIt requires that each three-address instruction be reference-able, either as an index in an array or as a pointer in a linked list.2022-4-2620(0) (rd, x , _ )(1) (gt, x, 0)(2) (if_f, (1), halt )(3) (asn, 1,fact )(4) (mul, fact, x)(5)

17、 (asn, (4), fact )(6) (sub, x, 1 )(7) (asn, (6), x)(8) (eq, x, 0 )(9) (if_f, (8), ? )(10) (wri, fact, _ )(11) (halt, _, _)A representation of the three-address code of the previous example as triplesNote: label instructions are eliminated and replaced by references to the triple indicesread xt1=x0if

18、_false t1 goto L1fact=1label L2t2=fact*xfact=t2t3=x-1x=t3t4= x=0if_false t4 goto L2write factlabel L1halt(11)(4)2022-4-2621Compare Triples to QuadruplesnTriples are an efficient way to represent three-address code, since the amount of space is reduced, and since the compiler does not need to generat

19、e names for temporariesnTriples use the instruction indices to represent the temporaries, then any movement of their positions becomes difficult. Quadruples are more suitable for optimization 2022-4-26227.2 Basic Code Generation Techniques2022-4-26237.2.1 Intermediate Code or Target Code as a Synthe

20、sized Attribute2022-4-2624nCode generation can be viewed as an attribute computationqThe generated code is viewed as a string attributeqIt becomes a synthesized attribute that can be defined using an attribute grammar and generated either directly during parsing or by a postorder traversal of the sy

21、ntax tree2022-4-2625nExampleGiven the grammar of expressions, to see how code can be defined as a synthesized attributeexp id=exp | aexpaexp aexp+factor | factorfactor (exp) | num | id2022-4-2626Attribute grammar for generating three-address codenAttributeqtacode for three-address codeqname for temp

22、orary name generated for intermediate results in expressionsnSymbolq+ is used for string concatenation with a newlineq| is used for string concatenation with a spacenFunctionqnewtemp(): return a new temporary name2022-4-2627Grammar RuleSemantic Rulesexp1 id==exp1.tacode=exp2.ta

23、code+id.strval| “=”| exp =exp.tacode=aexp.tacodeaexp1 aexp2+=newtemp()aexp1.tacode=aexp2.code + factor.tacode+ | ”=” ||”+”|aexp =aexp.tacode=factor.tacodefactor (exp)=factor.taco

24、de=exp.tacodefactor =num.strvalfactor.tacode=“”factor =id.strvalfactor.tacode=“”2022-4-2628Code Generation for Expression “(x=x+3)+4”name=x ; tacode=“ ”name=x ; tacode=“ ”name=3; tacode=“ ”name=t1; tacode=“t1=x+3”name=t1; tacode=name=4 ; tacode=“ ”name=t2; tacode=name=t1;

25、tacode=“t1=x+3”“t1=x+3 x=t1 t2=t1+4”“t1=x+3 x=t1”name=t1; tacode= “ t1=x+3 x=t1 ”t1=x+3 x=t1 t2=t1+4expaexpfactor ( exp )id = expaexp + factoraexp + factorfactorid (x)num (3)num (4)aexp (x)2022-4-26297.3 Code Generation of Control Statements and Logical Expressions2022-4-2630nIntermediate code gener

26、ation for control statements involvesqThe generation of labelsThey stand for addresses in the target code to which jumps are madeqBackpatchIf a code jumps to locations that are not yet known, this code must be 2022-4-26317.3.1 Code Generation for If- and While- Statements2022-4-2632Two forms of the

27、if- and while-statementsnIf- and While-statementsif-stmt if (exp) stmt| if (exp) stmt else stmtwhile-stmt while (exp) stmtThe chief problem in generating code for such statements is to translate the structured control features into an “unstructured” equivalent involving jumps2022-4-2633Typical code

28、arrangementnIf-statementscode before ifcode for if testconditional jumpcode for TRUE caseTRUEunconditional jumpcode for FALSE caseFALSEif-stmt if (exp) stmt | if (exp) stmt else stmtcode after if2022-4-2634Typical code arrangementnWhile-statementswhile-stmt while (exp) stmtcode before whilecode for

29、while testconditional jumpcode for body of whileTRUEunconditional jumpcode after whileFALSE2022-4-2635NotenThere needs only two kinds of jumpsqUnconditional jumps (goto L)qJumps when the condition is false (if_falsegoto L)nThe true case is always a “fall-through” case that needs no jump.nThis reduce

30、s the number of jumps that the compiler needs to generate2022-4-2636Three-Address code for control statementsnCode pattern for “if (E) S1 else S2”1.2.if_false t1 goto 3.6.code before ifcode for if testconditional jumpcode for TRUE caseTRUEunconditional jumpcode for FALSE caseFALSEcode after if2022-4

31、-2637Three-Address code for control statementsnCode pattern for “while (E) S” 2.3.if_false t1 goto 4.5.goto code before whilecode for while testconditional jumpTRUEunconditional jumpcode after whileFALSEcode for body of while2022-4-2638Problems in intermediate code generation of control statementsnI

32、n some cases, jumps to a label must be generated prior to the definition of the label itselfnA code generation routine can call the label generation procedure when a label is needed to generate a forward jump and save the label name (locally or on the stack) until the label location is known2022-4-2

33、6397.3.2 Code Generation of Logical Expressions2022-4-26401. Logical Expressions (or Boolean Expressions)nLogical expressions have two primary purposeqThey are used to compute logical valuesqThey are used as test in control statements, such as if-then or while-do2022-4-2641nComponent of Logical expr

34、essions qThey are composed of the Boolean operators (and, or, not) applied to elements that are Boolean variables or relational expressionsqRelational expressions are of the form where E1 and E2 are arithmetic expressions, relop is a comparison operator such as , , =2022-4-2642Code generation for Bo

35、olean ExpressionsnIf they are used to compute logical values, code can be generated in a manner similar to arithmetic expressionsnIf they are used as test in control statements, the value of Boolean expression is not saved in a temporary but represented by a position reached in a program2022-4-2643n

36、Boolean expressions generated by the following grammarE E or E | E and E | not E | (E) | id relop id | true | falseor and and are left-associative, and or has lowest precedence, then and, then not2022-4-2644Translation of Boolean expressions as arithmetic expressionsnBoolean expressions are translat

37、ed in a manner similar to arithmetic expressionsnFor example:qThe translation for “” is the three-address sequence: 1.t1= not c2.t2=b and t13.t3=a or t22022-4-2645Translation of Boolean Expressions is a sequence of three-address statements that evaluates E as a sequence of conditional and unconditio

38、nal jumps to one of two location: and nE is of the form , the generated code is: e.g. ab can be translated into:(1) if ab goto (4)(2) t=0(3) goto (5)(4) t=1(5)2022-4-2646E is of the form nif E1 is true, then E is true, so E1.true=E.truenif E1 is false, then E2 must be evaluated, so E1.false is the f

39、irst statement in the code for E2nThe true and false exits of E2 is the same as E respectivelyE1.codeE2.codeE1.falseE2.falseE1.trueE2.true2022-4-2647E is of the form Semantic Rules for “EE1 or E2”1.E1.true=E.true;2.E1.false=newlabel;3.E2.true=E.true;4.E2.false=E.false;5.E.code=E1.code + Label E1.fal

40、se + E2.codeE1.codeE2.codeE1.falseE2.falseE1.trueE2.true2022-4-2648E is of the form E1.codeE2.codeE1.falseE2.falseE1.trueE2.trueSemantic Rules for “EE1 and E2”1.E1.true=newlabel;2.E1.false=E.false;3.E2.true=E.true;4.E2.false=E.false;5.E.code=E1.code + Label E1.true + E2.code2022-4-2649E is of the fo

41、rm Semantic Rules for “Enot E1”1.E1.true=E.false;2.E1.false=E.true;3.E.code=E1.code;E1.codeE1.falseE1.true2022-4-2650Example: Suppose the true and false exits for the entire expression have been set to and ( )E.true=LtrueE.false=LfalseE1.true=LtrueE1.false=L1E2.true=LtrueE2.false=LfalseE3.true=L2E3.

42、false=LfalseE4.true=LtrueE4.false=Lfalseora bandc de fSemantic Rules1.if ab goto2.goto L13.Label L14.if cd goto L25.goto Lfalse6.label L27.if ef goto 8.goto LfalseE1E3EE2E4Grammar: E E or E | E and E | not E | (E) | id relop id | true | falseL1:L2:2022-4-2651Translation of Boolean expressions in the

43、 context of control statementsnGrammar for control statementsS if E then S1 | if E then S1 else S2| while E do S1qE is the Boolean expressionnTranslation MethodThe value of Boolean expression is not saved in a temporary but represented by a position reached in a program2022-4-2652nFunctions used in code generation returns a new label each time it is callednAttributes() is the label to which control flows if E is true (false) is