编译第八章代码生成.ppt

第 8 章 代码生成,学习目标 掌握 中间代码生成的基本结构 理解 三地址码; 三元式; 四元式,代码生成回顾 代码生成的任务是生成目标机器的可执行代码，这个可执行代码是源代码的忠实体现。 代码生成依赖于 源语言的特征 目标结构的细节信息 运行时环境的结构,代码生成一般分为以下几步： 中间代码生成 生成某种形式的汇编代码：没有生成真正的可执行代码 优化 为了改进目标代码的速度和大小,源程序虽然可以被直接翻译成目标语言，但是使用与机器无关的中间代码的好处在于： 方便于不同目标机的代码生成: 只需为新的机器加一个后端即可以生成不同机器的编译器了。 与机器无关的代码优化可应用于中间代码,我们将讨论代码生成的一般技术，而不是针对某种特定的目标机器的详细描述,8.1 中间代码和用于代码生成的数据结构 8.2 基本的代码生成技术 8.3控制语句和逻辑表达式的代码生成 8.4 代码优化技术考察,8.1 中间代码和用于代码生成的数据结构,中间表示 (IR) 在翻译期间，中间表示代表了源程序的数据结构 例如: 抽象语法树,中间代码 中间代码的需求 抽象语法树与目标代码极不相像，在控制流构造的描述上尤为如此 中间代码 是语法树用顺序形式表示，更接近目标代码,中间代码的优点 当编译器的目标是产生非常高效的代码时，中间代码是极其有用的。 用于生成不同目标机的编译器 中间代码的普遍形式 三地址码,8.1.1 三地址码,三地址码的最基本用法形如 x=y op z 表示算术表达式的求值 x,y,z 是名字，常量或编译器产生的临时变量名 op 表示任何一个算术运算符或逻辑运算符，例如 + ,and 形如这样的“三地址码”，一般来说 x,y 和 z 表示的是三个内存地址。,例如 表达式的计算用三地址码表示为： 2*a+(b-3),相应的三地址码是 t1 = 2*a t2 = b-3 t3 = t1+t2 其中 t1,t2,t3 是临时变量名，它们对应语法树的内部结点，并表示计算值,三地址码的其他用法说明 标准程序语言的每种结构的三地址码 赋值语句形如“x=y op z”, 其中op 为二元运算符 赋值语句形如 “x=op y”, 其中 op 是一元运算符 赋值语句形如 “x=y” ，其中将 y赋值给 x,无条件跳转 “goto L” 条件跳转 ,例如 “if B goto L” , “if_false B goto L” 和 “if A rop B goto L” 语句 “Label L” 表示转移地址的位置 “read x” “write x” 语句 “halt” 表示代码的结束,例如 Sample TINY program read x; If 0x then fact:=1; repeat fact:=fact*x; x:=x-1; until x=0; write fact end,它的三地址码： read x t1=0x if-false t1 goto L1 fact=1 label L2 t2=fact*x fact=t2 t3=x-1 x=t3,t4=x=0 if_false t4 goto L2 write fact Label L1 halt,8.1.2 三地址码的实现,三地址指令是中间代码的抽象形式 在编译器中，这些指令可以通过记录实现，域表示操作符和操作数。 两种这样的表示： 四元式 和 三元式,四元式 每条三地址指令包含四个域: 一个操作符和三个地址 对于那些少于三个地址的指令，将一个或更多的地址域置成 null 或 “empty”,四元式实现 (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, _, _) ,三地址码 label L2 t2=fact*x fact=t2 t3=x-1 x=t3 t4=x=0 if_false t4 goto L2 write fact ,三元式 每条三地址指令包含三个域: 一个操作符和两个地址 用自己的指令来代表临时变量来实现。,三地址码 label L2 t2=fact*x fact=t2 t3=x-1 x=t3 t4=x=0 if_false t4 goto L2 write fact ,三元式实现 (4) (mul, fact, x) (5) (asn, (4), fact) (6) (sub, x, 1) (7) (asn, (6), x) (8) (eq, x, 0) (9) (if_f, (8), (4) (10) (wri, fact, _),注:label 指令被删除，替换为三元式索引的引用,三元式与四元式的比较 三元式是代表三地址码的有效方法，因为空间数量减少了，并且编译器不需要产生临时变量名 三元式使用指令索引表示临时变量，使得三元式的位置移动变得很困难。四元式更便于优化。,8.2 基本的代码生成技术,代码生成的基本方法 (8.2) 单个语言结构的代码生成 (8.3),8.2.1 作为合成属性的中间代码或目标代码,代码生成被看作是属性计算 生成代码被看作一个字符串属性 这个代码就成了一个合成属性，能用属性文法定义，并能在分析期间直接生成或通过语法树的后序遍历生成。,例如 给定表达式的文法，看看代码是如何被定义为合成属性的。 exp - id=exp | aexp aexp - aexp+factor | factor factor - (exp) | num | id 假设记号 id 和 num 已经有一个预先计算过的 strval 属性，是 token的串值。,生成三地址码的属性文法 属性 tacode 表示三地址码 name 表示表达式中生成的中间结果的临时变量名 符号 + 表示其间插有换行符的串连接 | 表示其间有空格的串连接 函数 newtemp( ) :返回一个新的临时变量名,表达式 “(x=x+3)+4” 的tacode 属性,name=x,name=x,name=3,name=t1;tacode=“t1=x+3”,name=t1;tacode=“t1=x+3 x=t1”,name=t1; tacode=“t1=x+3 x=t1”,name=4,name=t2;tacode=“t1=x+3 x=t1 t2=t1+4”,name=t1;tacode=“t1=x+3”,8.3 控制语句和逻辑表达式的代码生成,一个程序包含声明和语句 声明不会生成中间代码，为每个已声明的名字，我们生成一个符号表入口 赋值语句和简单算术表达式的代码生成 (8.2) 控制语句和逻辑表达式的代码生成 (8.3),8.3.1 If- 和 While-语句的代码生成,If- 和 While-语句 if-stmt -if (exp) stmt | if (exp) stmt else stmt while-stmt -while (exp) stmt 这样语句的代码生成的主要问题是：将结构化的控制特性翻译成等价的非结构化转移.,典型的代码排列 If- 语句 if-stmt -if (exp) stmt | if (exp) stmt else stmt,While-语句 while-stmt - while (exp) stmt,注释: 仅有两种跳转 无条件跳转 (goto L) 条件为假时跳转 (if_falsegoto L) 条件为真时无需跳转。 这减少了编译器要产生的跳转的数量。,控制语句的三地址码 “if (E) S1 else S2”的代码模式： if_false t1 goto L1 goto L2 label L1 label L2,“while (E) S” 的代码模式： label L1 if_false t1 goto L2 goto L1 label L2,8.3.2 逻辑表达式的代码生成,1 逻辑表达式 (或布尔表达式) 逻辑表达式有两个主要的作用： 用来计算逻辑值 作为控制语句的测试而使用，如if-then 或 while-do,逻辑表达式的构成 由布尔运算符 (and,or,not) 及布尔遍历或关系表达式组成 关系表达式 形如“E1 relop E2”, 其中E1 和 E2 是 算术表达式, relop 是比较运算符，例如 , =,布尔表达式 由下面文法生成： E-E or E | E and E | not E | (E) | id relop id | true | false or 和 and 是左结合，且运算优先级是 or and not,布尔表达式的代码生成,数值表示的直接计算 逻辑表示的短路计算,2 作为数值表示计算的布尔表达式的翻译,布尔表达式以类似于算术表达式的方式翻译 例如 “a or b and not c” 的翻译是三地址序列 t1= not c t2=b and t1 t3=a or t2,3 作为短路计算的布尔表达式的翻译,短路 一个逻辑运算是短路的，如果不需要再求它的第二个参数 例如 A and B: 若 已计算出A 是 false，则无需查看B即可确定 A and B 的结果是 false A or B: 若已知道 A 是 true, 则无需查看B即可确定A or B 的结果是true,作为条件控制的布尔表达式的翻译,控制语句的文法 S- if E then S1 | if E then S1 else S2 | while E do S1 E 是布尔表达式 翻译方法 当布尔表达式用于控制条件时，并不需要计算表达式的值，而是一旦确定了表达式为真或为假，就将控制转向相应的代码序列。,代码生成中用到的函数 newlabel() 返回每次调用的新标号 属性 E.true(E.false) 是E为真（或假）时的控制转向标号 S.next 表示S后面的代码即将被执行的三地址指令的标号 S.begin 是S代码生成的第一条指令标号,1 S-if E then S1,E.true 指向S1代码的第一条指令 E.false 指向S后面的代码即将被执行的第一条指令,语义规则 E.true=newlabel; E.false=S.next; S.code=E.code | Label E.true | S1.code,2 S-if E then S1 else S2,E.true 指向S1代码的第一条指令 E.false指向S2代码的第一条指令,语义规则 E.true=newlabel; E.false=newlabel; S1.next=S.next; S2.next=S.next S.code=E.code | Label E.true | S1.code |goto S.next | Label E.false | S2.code,3 S-while E do S1,E.true 指向S1代码的第一条指令 E.false指向S后面的代码即将被执行的第一条指令,语义规则 S.begin=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,布尔表达式的翻译 E.code 是一段三地址指令序列，将E计算为一系列的到E.true和E.false中的条件转及无条件转语句 E 形如 a relop b, 生成的代码为 if a relop b goto E.true goto E.false,E 形如 E1 or E2,若 E1 是true, 则 E 是 true,因此 E1.true=E.true 若 E1 是false, 则要判断 E2, 因此 E1.false 是E2代码的第一个语句序号 E2的真假出口分别与 E的相同,“E - E1 or E2”的语义规则 E1.true=E.true; E1.false=newlabel; E2.true=E.true; E2.false=E.false; E.code=E1.code | Label E1.false | E2.code,E 形如 E1 and E2,语义规则 E1.true=newlabel; E1.false=E.false; E2.true=E.true; E2.false=E.false; E.code=E1.code | Label E1.true | E2.code,E 形如 not E1 只需将E1的真假出口调换，即为 E 的真假出口 语义规则 E1.true=E.false; E1.false=E.true; E.code=E1.code;,例如 ab or cd and ef 整个表达式的真假出口表示为 Ltrue 和 Lfalse,E.true=Ltrue E.false=Lfalse,E1.true=Ltrue E1.false=L1,E2.true=Ltrue E2.false=Lfalse,E1.true=L2 E1.false=Lfalse,E.true=Ltrue E.false=Lfalse,if ab goto Ltrue goto L1,if cd goto L2 goto Lfalse,if ef goto Ltrue goto Lfalse,Label L1,label L2,例如 控制语句的代码生成 while ab do if cd then x=y+z else x=y-z,S.next=Lnext S.begin=L1,E.true=L2 E.false=Lnext,S.next=L1,E.true=L3 E.false=L4,S.next=L1,S.next=L1,8.4 代码优化技术考察,代码优化用来提高程序代码的质量（由目标代码的速度和大小来衡量） 编译器编写者必须能判断出哪种技术可以在增加最小编译器复杂度的情况下大大提高代码质量,8.4.1 代码优化的主要来源,寄存器分配 合理使用寄存器是高效代码的最重要特征 寄存器的操作比内存的操作更快 寄存器的数量是有限的，因此，有效使用寄存器对生成好代码特别重要。,不必要操作 避免产生冗余或不必要的操作代码,例 1:公共子表达式删除 公共子表达式是代码中重复出现的表达式，且它们的值相同。可以保存第一次计算值并删除重复计算。,(1) T1 =4*I (2) T2 =addr(A)-4 (3) T3 =T2T1 T4 =4*I,例 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,常量优化 用有关常数信息删除可能得操作或预先计算一些操作。 常量合并 2+3, 可以由编译器计算并用常数5代替 常量传播 确定一个变量在程序局部或全部是否有恒定值，这样变换就可应用于涉及该变量的表达式。,8.4.2 优化分类,两个有用的优化分类 优化在编译过程中的时间 优化的程序范围,优化应用的时间 优化可以在编译的每阶段分别执行。一般将完成主要的优化工作。 中间代码生成时的优化 优化用来转换语法树本身，其中某些子树被删除或替换为简单的子树,中间代码生成后的优化 对很多优化而言，语法树不适合收集信息及实现优化，优化将在中间代码上实现 目标代码生成时 优化依赖于目标机器结构,优化应用的范围 可分为: 局部优化 全局优化 过程间优化,局部优化 局部优化是应用于代码的线性部分, 即, 代码中没有跳进或跳出语句 一个最大的线性代码序列被称为 基本块 局部优化是在基本块中的优化。,全局优化 全局优化是扩展超出基本块，但是限制在单个过程中的优化 过程间优化 过程间优化是扩展出过程边界到整个程序的优化,8.4.3 优化的数据结构和实现技术,优化的两种数据结构 流图 流图是执行全局优化的过程中间代码的图形表示 DAG(无环有向图) DAG 是为每个基本块构造的，执行局部优化的无环有向图,1 流图,流图用于表示每个过程代码的全局信息 流图的结点是基本块 边是条件转或无条件转 (目的是作为其他基本块的开始),流图的构造 A flow graph, together with each of its basic blocks, can be constructed by a single pass over the intermediate code. Each new basic block is identified as follows: The first instruction begins a new basic block Each label that is the target of a jump begins a new basic block Each instruction that follows a conditional jump begins a new basic block,流图,三地址码 read X read Y R:=X mod Y if R=0 goto (8) X:=Y Y:=R goto (3) write Y halt,read X,R:=X mod Y,X:=Y,write Y,解释: 流图是数据流分析的主要数据结构，积累信息用于优化。 不同的信息要求对流图作不同处理，而且收集的信息各不相同，对应于不同的优化要求。,基本块的DAG DAG数据结构跟踪基本块中值和变量的计算和赋值 块中Leaf nodes are values that are used in 格的来自别处的值表示为叶子结点 值上的操作表示为内部结点 新值的赋值表示为将目标变量或临时变量