编译 第八章 代码生成.ppt

《编译 第八章 代码生成.ppt》由会员分享，可在线阅读，更多相关《编译 第八章 代码生成.ppt（77页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第 8 章章 代码生成代码生成n学习目标学习目标n掌握掌握中间代码生成的基本结构中间代码生成的基本结构n理解理解三地址码三地址码;三元式三元式;四元式四元式n代码生成回顾代码生成回顾n代码生成的任务是生成目标机器的可执行代码，代码生成的任务是生成目标机器的可执行代码，这个可执行代码是源代码的忠实体现。这个可执行代码是源代码的忠实体现。n代码生成依赖于代码生成依赖于n源语言的特征源语言的特征n目标结构的细节信息目标结构的细节信息n运行时环境的结构运行时环境的结构n代码生成一般分为以下几步：代码生成一般分为以下几步：1)中间代码生成中间代码生成2)生成某种形式的汇编代码：没有生成真正生成某种形式

2、的汇编代码：没有生成真正的可执行代码的可执行代码3)优化优化为了改进目标代码的速度和大小为了改进目标代码的速度和大小词法分析词法分析语法分析语法分析语义分析语义分析中间代码生成中间代码生成目标代码生成目标代码生成中间代码优化中间代码优化目标代码优化目标代码优化n源程序虽然可以被直接翻译成目标语源程序虽然可以被直接翻译成目标语言，但是使用与机器无关的中间代码言，但是使用与机器无关的中间代码的好处在于：的好处在于：方便于不同目标机的代码生成方便于不同目标机的代码生成:只需为新的只需为新的机器加一个后端即可以生成不同机器的编机器加一个后端即可以生成不同机器的编译器了。译器了。与机器无关的代码优化可应

3、用于中间代码与机器无关的代码优化可应用于中间代码我们将讨论代码生成的一般技术，而不是我们将讨论代码生成的一般技术，而不是针对某种特定的目标机器的详细描述针对某种特定的目标机器的详细描述8.1 中间代码和用于代码生成的数据结构中间代码和用于代码生成的数据结构8.2 基本的代码生成技术基本的代码生成技术8.3控制语句和逻辑表达式的代码生成控制语句和逻辑表达式的代码生成8.4 代码优化技术考察代码优化技术考察8.1 中间代码和用于代码生成的数据结构中间代码和用于代码生成的数据结构n中间表示中间表示(IR)在翻译期间，中间表示代表了源程序的数在翻译期间，中间表示代表了源程序的数据结构据结构例如例如:抽

4、象语法树抽象语法树n中间代码中间代码中间代码的需求中间代码的需求抽象语法树与目标代码极不相像，在控制抽象语法树与目标代码极不相像，在控制流构造的描述上尤为如此流构造的描述上尤为如此中间代码中间代码是语法树用顺序形式表示，更接近目标代是语法树用顺序形式表示，更接近目标代码码中间代码的优点中间代码的优点v当编译器的目标是产生非常高效的代码时，中间当编译器的目标是产生非常高效的代码时，中间代码是极其有用的。代码是极其有用的。v用于生成不同目标机的编译器用于生成不同目标机的编译器中间代码的普遍形式中间代码的普遍形式三地址码三地址码8.1.1 三地址码三地址码n三地址码的最基本用法形如三地址码的最基本用

5、法形如 x=y op z表示算术表达式的求值表示算术表达式的求值x,y,z 是名字，常量或编译器产生的临时变是名字，常量或编译器产生的临时变量名量名op 表示任何一个算术运算符或逻辑运算符，表示任何一个算术运算符或逻辑运算符，例如例如+,and形如这样的形如这样的“三地址码三地址码”，一般来说，一般来说 x,y 和和 z 表示的是三个内存地址。表示的是三个内存地址。例如例如表达式的计算用三地址码表示为：表达式的计算用三地址码表示为：2*a+(b-3)相应的三地址码是相应的三地址码是t1=2*at2=b-3t3=t1+t2其中其中 t1,t2,t3 是临时变量名，它们对应语法树的内是临时变量名，

6、它们对应语法树的内部结点，并表示计算值部结点，并表示计算值+*-2ab3n三地址码的其他用法说明三地址码的其他用法说明标准程序语言的每种结构的三地址码标准程序语言的每种结构的三地址码1.赋值语句形如赋值语句形如“x=y op z”,其中其中op 为二元运为二元运算符算符2.赋值语句形如赋值语句形如“x=op y”,其中其中 op 是一元运算是一元运算符符3.赋值语句形如赋值语句形如“x=y”，其中将，其中将 y赋值给赋值给 x4.无条件跳转无条件跳转“goto L”5.条件跳转条件跳转,例如例如“if B goto L”,“if_false B goto L”和和“if A rop B got

7、o L”6.语句语句“Label L”表示转移地址的位置表示转移地址的位置7.“read x”8.“write x”9.语句语句“halt”表示代码的结束表示代码的结束例如例如Sample TINY programread x;If 0 x then fact:=1;repeat fact:=fact*x;x:=x-1;until x=0;write factend它的三地址码：它的三地址码：read xt1=0 id=exp|aexpaexp -aexp+factor|factorfactor-(exp)|num|id假设记号假设记号 id 和和 num 已经有一个预先计算已经有一个预先计算

8、过的过的 strval 属性，是属性，是 token的串值。的串值。n生成三地址码的属性文法生成三地址码的属性文法属性属性vtacode 表示三地址码表示三地址码vname 表示表达式中生成的中间结果的临时变表示表达式中生成的中间结果的临时变量名量名符号符号v+表示其间插有换行符的串连接表示其间插有换行符的串连接v|表示其间有空格的串连接表示其间有空格的串连接函数函数vnewtemp():返回一个新的临时变量名返回一个新的临时变量名文法规则文法规则 语义规则语义规则exp1-id=exp2exp1.name=exp2.nameexp1.tacode=exp2.tacode+id.strval|

9、“=”|exp2.nameexp-aexpexp.name=aexp.nameexp.tacode=aexp.tacodeaexp1-aexp2+factor aexp1.name=newtemp()aexp1.tacode=aexp2.code+factor.tacode+aexp1.name|”=”|exp2.name|”+”|factor.nameaexp-factoraexp.name=factor.nameaexp.tacode=factor.tacodefactor-(exp)factor.name=exp.namefactor.tacode=exp.tacodefactor-nu

10、mfactor.name=num.strvalfactor.tacode=“”factor-idfactor.name=id.strvalfactor.tacode=“”表达式表达式“(x=x+3)+4”的的tacode 属性属性name=xname=xname=3name=t1;tacode=“t1=x+3”name=t1;tacode=“t1=x+3 x=t1”name=t1;tacode=“t1=x+3 x=t1”name=4name=t2;tacode=“t1=x+3 x=t1 t2=t1+4”expaexpfactor(exp )id =expaexp +factoraexp +fa

11、ctorfactorid(x)num(3)num(4)aexp(x)name=t1;tacode=“t1=x+3”8.3 控制语句和逻辑表达式的代码生成控制语句和逻辑表达式的代码生成 一个程序包含声明和语句一个程序包含声明和语句声明不会生成中间代码，为每个已声明的名字，声明不会生成中间代码，为每个已声明的名字，我们生成一个符号表入口我们生成一个符号表入口赋值语句和简单算术表达式的代码生成赋值语句和简单算术表达式的代码生成(8.2)控制语句和逻辑表达式的代码生成控制语句和逻辑表达式的代码生成(8.3)8.3.1 If-和和 While-语句的代码生成语句的代码生成nIf-和和 While-语句语

12、句if-stmt-if(exp)stmt|if(exp)stmt else stmtwhile-stmt-while(exp)stmtn这样语句的代码生成的主要问题是：将结这样语句的代码生成的主要问题是：将结构化的控制特性翻译成等价的非结构化转构化的控制特性翻译成等价的非结构化转移移.n典型的代码排列典型的代码排列nIf-语句语句if-stmt-if(exp)stmt|if(exp)stmt else stmtIf语句前的代码语句前的代码if 测试的代码测试的代码条件跳转条件跳转TRUE情况下的代码情况下的代码无条件跳转无条件跳转FALSE情况下的代码情况下的代码If语句后的代码语句后的代码T

13、RUEFALSEnWhile-语句语句while-stmt-while(exp)stmtWhile语句前的代码语句前的代码while 测试的代码测试的代码条件跳转条件跳转While体的代码体的代码无条件跳转无条件跳转While语句后的代码语句后的代码TRUEFALSE注释注释:仅有两种跳转仅有两种跳转v无条件跳转无条件跳转(goto L)v条件为假时跳转条件为假时跳转(if_falsegoto L)条件为真时无需跳转。条件为真时无需跳转。这减少了编译器要产生的跳转的数量。这减少了编译器要产生的跳转的数量。n控制语句的三地址码控制语句的三地址码n“if (E)S1 else S2”的代码模式：的

14、代码模式：if_false t1 goto L1goto L2label L1label L2n“while(E)S”的代码模式：的代码模式：label L1if_false t1 goto L2goto L1label L28.3.2 逻辑表达式的代码生成逻辑表达式的代码生成1 逻辑表达式逻辑表达式(或布尔表达式或布尔表达式)n逻辑表达式有两个主要的作用：逻辑表达式有两个主要的作用：n用来计算逻辑值用来计算逻辑值n作为控制语句的测试而使用，如作为控制语句的测试而使用，如if-then 或或 while-don逻辑表达式的构成逻辑表达式的构成由布尔运算符由布尔运算符(and,or,not)及布

15、尔遍历或关及布尔遍历或关系表达式组成系表达式组成关系表达式关系表达式 形如形如“E1 relop E2”,其中其中E1 和和 E2 是是 算术表达式算术表达式,relop 是比较运算符，例是比较运算符，例如如 ,=布尔表达式布尔表达式 由下面文法生成：由下面文法生成：E-E or E|E and E|not E|(E)|id relop id|true|falsevor 和和 and 是左结合，且运算优先级是是左结合，且运算优先级是 or and if E then S1|if E then S1 else S2|while E do S1E 是布尔表达式是布尔表达式n翻译方法翻译方法当布尔表

16、达式用于控制条件时，并不需要计算表当布尔表达式用于控制条件时，并不需要计算表达式的值，而是一旦确定了表达式为真或为假，达式的值，而是一旦确定了表达式为真或为假，就将控制转向相应的代码序列。就将控制转向相应的代码序列。代码生成中用到的函数代码生成中用到的函数newlabel()返回每次调用的新标号返回每次调用的新标号属性属性vE.true(E.false)是是E为真（或假）时的控制转为真（或假）时的控制转向标号向标号vS.next 表示表示S后面的代码即将被执行的三地址后面的代码即将被执行的三地址指令的标号指令的标号vS.begin 是是S代码生成的第一条指令标号代码生成的第一条指令标号1 S-

17、if E then S1S1.codeE.codeto E.trueto E.falseE.true:E.false:E.true 指向指向S1代码的第代码的第一条指令一条指令E.false 指向指向S后面的代后面的代码即将被执行的第一条指码即将被执行的第一条指令令语义规则语义规则 E.true=newlabel;E.false=S.next;S.code=E.code|Label E.true|S1.code2 S-if E then S1 else S2E.true 指向指向S1代码的代码的第一条指令第一条指令E.false指向指向S2代码的代码的第一条指令第一条指令语义规则语义规则E.t

18、rue=newlabel;E.false=newlabel;S1.next=S.next;S2.next=S.nextS.code=E.code|Label E.true|S1.code|goto S.next|Label E.false|S2.code to E.trueto E.falseE.true:E.false:S2.codegoto S.nextS1.codeE.codeS.next3 S-while E do S1E.true 指向指向S1代码的代码的第一条指令第一条指令E.false指向指向S后面的代后面的代码即将被执行的第一条码即将被执行的第一条指令指令语义规则语义规则S.b

19、egin=newlabel;E.true=newlabel;E.false=S.next;S1.next=S.begin;S.code=Label S.begin|E.code|Label E.true|S1.code|goto S.begin to E.falseto E.trueE.true:E.false:goto S.beginS1.codeE.codeS.begin:n布尔表达式的翻译布尔表达式的翻译E.code 是一段三地址指令序列，将是一段三地址指令序列，将E计算计算为一系列的到为一系列的到E.true和和E.false中的条件转中的条件转及无条件转语句及无条件转语句E 形如形如

20、 a relop b,生成的代码为生成的代码为if a relop b goto E.truegoto E.falseE 形如形如 E1 or E2E1.codeE2.codeE1.falseE2.falseE.falseE1.trueE2.trueE.truev若若 E1 是是true,则则 E 是是 true,因此因此 E1.true=E.truev若若 E1 是是false,则要判断则要判断 E2,因此因此 E1.false 是是E2代码的第一个语句序号代码的第一个语句序号vE2的真假出口分别与的真假出口分别与 E的相同的相同v“E-E1 or E2”的语义规则的语义规则E1.true=

21、E.true;E1.false=newlabel;E2.true=E.true;E2.false=E.false;E.code=E1.code|Label E1.false|E2.codeE 形如形如 E1 and E2E1.codeE2.codeE1.falseE2.falseE.falseE1.trueE2.trueE.true语义规则语义规则 E1.true=newlabel;E1.false=E.false;E2.true=E.true;E2.false=E.false;E.code=E1.code|Label E1.true|E2.codeE 形如形如 not E1只需将只需将E1的

22、真假出口调换，即为的真假出口调换，即为 E 的真假出口的真假出口 语义规则语义规则E1.true=E.false;E1.false=E.true;E.code=E1.code;例如例如ab or cd and ef整个表达式的真假出口表示为整个表达式的真假出口表示为 Ltrue 和和 LfalseE.true=LtrueE.false=LfalseE1.true=LtrueE1.false=L1E2.true=LtrueE2.false=LfalseE1.true=L2E1.false=LfalseE.true=LtrueE.false=LfalseEE1orE2a bE1and E2c de

23、 fif ab goto Ltruegoto L1if cd goto L2goto Lfalseif ef goto Ltruegoto LfalseLabel L1label L2例如例如控制语句的代码生成控制语句的代码生成while ab do if cd thenx=y+zelse x=y-zS.next=LnextS.begin=L1E.true=L2E.false=LnextS.next=L1E.true=L3E.false=L4S.next=L1S.next=L1while-stmtEa bif-stmtEAss-stmtAss-stmtxEExy +zy -zc dLabel

24、L1 if ab goto L2 goto Lnext Label L2goto L1if cd goto L3 goto L4 Label L3 t1=y+z z=t1goto L1 Label L4 t2=y-z x=t28.4 代码优化技术考察代码优化技术考察代码优化用来提高程序代码的质量（由目代码优化用来提高程序代码的质量（由目标代码的速度和大小来衡量）标代码的速度和大小来衡量）编译器编写者必须能判断出哪种技术可以编译器编写者必须能判断出哪种技术可以在增加最小编译器复杂度的情况下大大提在增加最小编译器复杂度的情况下大大提高代码质量高代码质量8.4.1 代码优化的主要来源代码优化的主要来

25、源1.寄存器分配寄存器分配合理使用寄存器是高效代码的最重要特征合理使用寄存器是高效代码的最重要特征寄存器的操作比内存的操作更快寄存器的操作比内存的操作更快寄存器的数量是有限的，因此，有效使用寄存器的数量是有限的，因此，有效使用寄存器对生成好代码特别重要。寄存器对生成好代码特别重要。2.不必要操作不必要操作避免产生冗余或不必要的操作代码避免产生冗余或不必要的操作代码例例 1:公共子表达式删除公共子表达式删除公共子表达式是代码中重复出现的表达式，公共子表达式是代码中重复出现的表达式，且它们的值相同。可以保存第一次计算值并且它们的值相同。可以保存第一次计算值并删除重复计算。删除重复计算。(1)T1=

26、4*I(2)T2=addr(A)-4(3)T3=T2T1(4)T4=4*I(4)T4:=T1例例 2:避免存储不再使用的变量或临时变量的值避免存储不再使用的变量或临时变量的值（1）I=1（2）T1=4（3）T3=T2T1（4）T4=T1 （5）I=I+1（6）T1=T1+4（7）if T180 goto(3)（2）T1:=4（3）T3:=T2 T1（6）T1:=T1+4（7）if T180 goto (3)3.高代价操作高代价操作通过使用代价更低的实现操作方式减少必通过使用代价更低的实现操作方式减少必要操作的代价要操作的代价例如例如:减轻强度减轻强度可以用移位操作实现乘可以用移位操作实现乘2常

27、量优化常量优化用有关常数信息删除可能得操作或预先计用有关常数信息删除可能得操作或预先计算一些操作。算一些操作。v常量合并常量合并2+3,可以由编译器计算并用常数可以由编译器计算并用常数5代替代替v常量传播常量传播确定一个变量在程序局部或全部是否有恒确定一个变量在程序局部或全部是否有恒定值，这样变换就可应用于涉及该变量的定值，这样变换就可应用于涉及该变量的表达式。表达式。8.4.2 优化分类优化分类n两个有用的优化分类两个有用的优化分类优化在编译过程中的时间优化在编译过程中的时间优化的程序范围优化的程序范围1.优化应用的时间优化应用的时间优化可以在编译的每阶段分别执行。一般优化可以在编译的每阶段

28、分别执行。一般将完成主要的优化工作。将完成主要的优化工作。中间代码生成时的优化中间代码生成时的优化优化用来转换语法树本身，其中某些子树优化用来转换语法树本身，其中某些子树被删除或替换为简单的子树被删除或替换为简单的子树中间代码生成后的优化中间代码生成后的优化对很多优化而言，语法树不适合收集信息对很多优化而言，语法树不适合收集信息及实现优化，优化将在中间代码上实现及实现优化，优化将在中间代码上实现目标代码生成时目标代码生成时优化依赖于目标机器结构优化依赖于目标机器结构2.优化应用的范围优化应用的范围可分为可分为:局部优化局部优化全局优化全局优化过程间优化过程间优化n局部优化局部优化局部优化是应用

29、于局部优化是应用于代码的线性部分代码的线性部分,即即,代代码中没有跳进或跳出语句码中没有跳进或跳出语句一个最大的线性代码序列被称为一个最大的线性代码序列被称为 基本块基本块局部优化是在基本块中的优化。局部优化是在基本块中的优化。n全局优化全局优化全局优化是扩展超出基本块，但是限制在全局优化是扩展超出基本块，但是限制在单个过程中的优化单个过程中的优化n过程间优化过程间优化过程间优化是扩展出过程边界到整个程序过程间优化是扩展出过程边界到整个程序的优化的优化8.4.3 优化的数据结构和实现技术优化的数据结构和实现技术n优化的两种数据结构优化的两种数据结构1.流图流图流图是执行全局优化的过程中间代码的

30、图流图是执行全局优化的过程中间代码的图形表示形表示2.DAG(无环有向图无环有向图)DAG 是为每个基本块构造的，执行局部是为每个基本块构造的，执行局部优化的无环有向图优化的无环有向图1 流图流图流图用于表示每个过程代码的全局信息流图用于表示每个过程代码的全局信息流图的结点是基本块流图的结点是基本块边是条件转或无条件转边是条件转或无条件转(目的是作为其他基目的是作为其他基本块的开始本块的开始)n流图的构造流图的构造A flow graph,together with each of its basic blocks,can be constructed by a single pass ove

31、r the intermediate code.Each new basic block is identified as follows:1.The first instruction begins a new basic block2.Each label that is the target of a jump begins a new basic block3.Each instruction that follows a conditional jump begins a new basic block(1)read X(2)read Y(3)R=X mod Y(4)if R=0 g

32、oto (8)(5)X=Y(6)Y=R(7)goto (3)(8)write Y(9)halt流图流图三地址码三地址码 (1)read X(2)read Y(3)R:=X mod Y(4)if R=0 goto (8)(5)X:=Y(6)Y:=R(7)goto (3)(8)write Y(9)halt(1)read X(3)R:=X mod Y(5)X:=Y(8)write Y解释解释:流图是数据流分析的主要数据结构，积累流图是数据流分析的主要数据结构，积累信息用于优化。信息用于优化。不同的信息要求对流图作不同处理，而且不同的信息要求对流图作不同处理，而且收集的信息各不相同，对应于不同的优化收

33、集的信息各不相同，对应于不同的优化要求。要求。n基本块的基本块的DAGDAG数据结构跟踪基本块中值和变量的计数据结构跟踪基本块中值和变量的计算和赋值算和赋值块中块中Leaf nodes are values that are used in 格的来自别处的值表示为叶子结点格的来自别处的值表示为叶子结点值上的操作表示为内部结点值上的操作表示为内部结点新值的赋值表示为将目标变量或临时变量新值的赋值表示为将目标变量或临时变量的名字附加到表示赋值的结点上。的名字附加到表示赋值的结点上。2 DAG(无环有向图无环有向图)例如例如 基本块基本块label L2t2=fact*xfact=t2t3=x-1x

34、=t3t4=x=0if_false t4 goto L2这个基本块的这个基本块的DAG*-=factxfact,t2x,t310t4标记基本块的开始和最后的跳转一般不包括在标记基本块的开始和最后的跳转一般不包括在DAG中。中。Labels at the beginning of basic blocks and jumps at the end are usually not included in the DAG拷贝操作不生成新的结点，仅仅在表示拷贝值的结点处增加新拷贝操作不生成新的结点，仅仅在表示拷贝值的结点处增加新标记标记相同值的重复使用也在相同值的重复使用也在DAG中表示中表示nDAG

35、 的构造的构造轮流处理块中的每条语句轮流处理块中的每条语句形如形如 x=y+z的语句的语句v查找表示查找表示y和和z的的“当前当前”值的结点值的结点v若若y 和和 z 是常量是常量,则生成一个结点表示则生成一个结点表示y+z 的结果值，的结果值，并标记为结点并标记为结点x。若。若x和和y已生成则删除该结点，否已生成则删除该结点，否则生成一个标记为则生成一个标记为+，且两个孩子分别为，且两个孩子分别为y和和z的结的结点，标记这个结点为点，标记这个结点为+v然而，若已经存在一个结点表示然而，若已经存在一个结点表示y+z相同的值，则相同的值，则我们不需要在我们不需要在DAG中增加新的结点，而只需要在

36、已中增加新的结点，而只需要在已存在的结点处再标记存在的结点处再标记x需要注意三个细节需要注意三个细节v对于对于 x=y+z,如果如果 y 和和 z 是常数是常数,不需要生成为不需要生成为+的内部结点的内部结点,而执行而执行 y+z(常量合并常量合并)v对于对于 x=y+z,若已经有结点表示若已经有结点表示y+z 相同的值，相同的值，我们无需生成新的结点，而只需要在已存在的结我们无需生成新的结点，而只需要在已存在的结点处再标记个点处再标记个x(局部公共子表达式删除局部公共子表达式删除)v若若 x 以前已经在某些结点标记了，我们删除那个以前已经在某些结点标记了，我们删除那个标记，因为刚生成标记，因为刚生成x的的“当前当前”值值(删除无用赋值删除无用赋值)例：例：基本块的基本块的DAG(1)T0:=3.14(2)T1:=2*T0(3)T2:=R+r(4)A:=T1*T2 (5)B:=A(6)T3:=2*T0(7)T4:=R+r(8)T5:=T3*T4(9)T6:=Rr(10)B:=T5*T6 T6T5T3T0 T46.28Rr3.14B2T1T2A B2+-*