1、编译原理与技术编译原理与技术第第11章章 代码优化代码优化 编译原理与技术编译原理与技术2主要内容主要内容u优化的概念优化的概念 u代码优化的基本技术代码优化的基本技术 u局部优化局部优化u机器代码优化窥孔技术机器代码优化窥孔技术 编译原理与技术编译原理与技术311.1 代码优化的概念代码优化的概念u代码优化在整个编译过程的位置代码优化在整个编译过程的位置编译前端中间代码优化目标代码生成中间代码生成源程序目标程序中间代码中间代码目标代码优化中间代码编译前端编译器可以改进过程调用、循环和地址计算目标代码生成中间代码源程序目标程序程序员可以改进算法，改变循环编译器可以利用寄存器，选择指令和窥孔优转
2、换程序员和编译器可能改上程序的位置程序员和编译器可能改上程序的位置 编译原理与技术编译原理与技术411.1 代码优化的概念代码优化的概念u设计和实现编译程序代码优化的原则：设计和实现编译程序代码优化的原则：（1）等价原则：经过优化后的代码应该保持程）等价原则：经过优化后的代码应该保持程序的输入输出，不应改变程序运行的结果。序的输入输出，不应改变程序运行的结果。（2）有效原则：优化后的代码应该在占用空间、）有效原则：优化后的代码应该在占用空间、运行速度这两个方面，或者其中的一个方面运行速度这两个方面，或者其中的一个方面得到改善。得到改善。（3）经济原则：代码优化需要占用计算机和编）经济原则：代码
3、优化需要占用计算机和编译程序的资源，代码优化取得的效果应该超译程序的资源，代码优化取得的效果应该超出优化工作所付出的代价。否则，代码优化出优化工作所付出的代价。否则，代码优化就失去了意义。就失去了意义。编译原理与技术编译原理与技术511.1 代码优化的概念代码优化的概念u代码优化依据机器相关性、优化范围和优化语代码优化依据机器相关性、优化范围和优化语言级别的分类言级别的分类按照与机器相关的程度，可以分为与机器相关的代码按照与机器相关的程度，可以分为与机器相关的代码优化和与机器无关的代码优化。优化和与机器无关的代码优化。l与机器相关的优化一般有寄存器的优化、多处理器的优化、与机器相关的优化一般有
4、寄存器的优化、多处理器的优化、特殊指令的优化以及无用指令的消除等技术。显然，特殊指令的优化以及无用指令的消除等技术。显然，这几这几类优化与具体机器的特性密切相关，例如寄存器的总数，寄类优化与具体机器的特性密切相关，例如寄存器的总数，寄存器的具体使用规定，等等。这类优化通常的在目标代码生存器的具体使用规定，等等。这类优化通常的在目标代码生成之后进行。成之后进行。l与机器无关的优化是在目标代码生成以前进行，主要是根据与机器无关的优化是在目标代码生成以前进行，主要是根据程序的控制信息和数据信息，对程序进行优化，与机器无关。程序的控制信息和数据信息，对程序进行优化，与机器无关。编译原理与技术编译原理与
5、技术611.1 代码优化的概念代码优化的概念根据优化的范围，可以划分为局部优化和全局优化两类。根据优化的范围，可以划分为局部优化和全局优化两类。l考察一个基本块的三地址中间代码序列就可以完成的优化，称为局部优化。考察一个基本块的三地址中间代码序列就可以完成的优化，称为局部优化。而全局优化则必须在考察基本块之间的相互联系与作用的基础上才能完成。而全局优化则必须在考察基本块之间的相互联系与作用的基础上才能完成。l代码优化总是在内部的中间代码和目标代码上进行的。在通常的编译程序代码优化总是在内部的中间代码和目标代码上进行的。在通常的编译程序中，代码优化往往是在中间代码这一级执行，例如对源程序的三地址
6、代码中，代码优化往往是在中间代码这一级执行，例如对源程序的三地址代码或抽象语法树上采取优化措施。相对于在目标代码级别的优化，在中间代或抽象语法树上采取优化措施。相对于在目标代码级别的优化，在中间代码优化的好处是：码优化的好处是：（1）容易从中间代码中识别处进行优化的情况，对目标语言代码的信息识别要困）容易从中间代码中识别处进行优化的情况，对目标语言代码的信息识别要困难，成本较高；难，成本较高；（2）中间代码于机器无关，因此，一个代码优化的程序可以适用于多种型号的机）中间代码于机器无关，因此，一个代码优化的程序可以适用于多种型号的机器。器。l有时也在目标代码语言级上进行代码优化，如寄存器优化等。
7、在目标代码有时也在目标代码语言级上进行代码优化，如寄存器优化等。在目标代码级别上进行全局优化的代价昂贵，本书仅仅讨论局部范围的目标代码优化级别上进行全局优化的代价昂贵，本书仅仅讨论局部范围的目标代码优化技术，即所谓的窥孔优化。技术，即所谓的窥孔优化。编译原理与技术编译原理与技术711.2 代码优化的基本技术代码优化的基本技术 u分类：分类：与机器无关的、在中间代码语言级的代码优与机器无关的、在中间代码语言级的代码优化主要包括：化主要包括：删除公共子表达式删除公共子表达式复写传播复写传播删除无用代码删除无用代码代码外提代码外提强度消弱强度消弱删除归纳变量删除归纳变量其中最后三种是专门针对循环语句
8、的优化。其中最后三种是专门针对循环语句的优化。编译原理与技术编译原理与技术811.2 代码优化的基本技术代码优化的基本技术void quicksort(m,n)int m,n;int i,j,v,x;if(n=m)return;/*程序段开始*/i=m 1;j=n;v=an;while(1)do i=i1;while(ai v);if(i=j)break;x=ai;ai=aj;aj=x;x=ai;ai=an;an=x/*程序段结束*/quicksort(m,j);quicksort(i+1,n);图图11.3 11.3 快速排序的快速排序的C C代码代码(1)i:=m 1(2)j:=n(3)t
9、1:=4n(4)v:=at1(5)i:=i 1(6)t2:=4i(7)t3:=at2(8)if t3 v goto(5)(9)j:=j 1(10)t4:=4j(11)t5:=at4(12)if t5 v goto(9)(13)if i=j goto(23)(14)t6:=4i(15)x:=at6(16)t7:=4i(17)t8:=4j(18)t9:=at8(19)at7:=t9(20)t10:=4j(21)at10:=x(22)goto(5)(23)t11:=ai(24)x:=at11(25)t12:=4i(26)t13:=4n(27)t14:=at12(28)at12:=t14(29)t15
10、:=4n(30)at15:=x 图图11.4 11.4 快速排序部分程序的三地址代码快速排序部分程序的三地址代码编译原理与技术编译原理与技术911.2 代码优化的基本技术代码优化的基本技术u删除公共子表达式删除公共子表达式i:=m 1j:=nt1:=4nv:=at1t11:=4ix:=at11t12:=4it13:=4nt14:=at12at12:=t14t15:=4nat15:=xi:=i 1t2:=4it3:=at2if t3 v goto B1i f i =j goto B6B1B2B4j:=j 1t4:=4jt5:=at4if t5 v goto B3t6:=4ix:=at6t7:=4
11、it8:=4jt9:=at8at7:=t9t10:=4jat10:=xgoto B2B3B5B6如果表达式如果表达式E已经计算过，已经计算过，并且在这之后并且在这之后E中变量的值中变量的值没有改变，那么，没有改变，那么，E的这个的这个再次出现称为公共子表达再次出现称为公共子表达式。如果可以利用先前的式。如果可以利用先前的计算结果，就可以避免表计算结果，就可以避免表达式的重复计算，这种优达式的重复计算，这种优化称为删除公共子表达式。化称为删除公共子表达式。编译原理与技术编译原理与技术1011.2 代码优化的基本技术代码优化的基本技术这是仅限于基本块的局部优化，B5仍然需要计算4*i和4*j。若在
12、整个图11.3的程序来看，它们依然是公共子表达式，4*i在B2中计算并且赋给了t2，4*j在B2中计算并且赋给了t4。继续删除这些公共子表达，在B5中就可以把t6:=4*i 替换为 t6:=t2t8:=4*j 替换为 t8:=t4这是因为在B2中计算的4*i传到B5时，没有改变i的值。同样，在B3中计算的4*j传到B5时，没有改变j的值。对于B6也可以作同样的处理。例如，在图例如，在图11.5的的B5中分别把公中分别把公共子表达式共子表达式4*i和和4*j的值赋给的值赋给t7和和t10，这些重复计算的公共子表达，这些重复计算的公共子表达式可以删除，用式可以删除，用t6代替代替t7，用，用t8代
13、替代替t10，这样就把，这样就把B5变换为如变换为如下的代码：下的代码：B5:t6:=4 ix:=at6t7:=t6t8:=4 jt9:=at8at7:=t9t10:=t8at10:=xgoto B2 编译原理与技术编译原理与技术1111.2 代码优化的基本技术代码优化的基本技术删除公共子表达式后的B5和B6 分别是分别是t6:=t2x:=at6t7:=t6t8:=t4t9:=at8at7:=t9t10:=t8at10:=xgoto B2B5B6t11:=t2x:=at11t12:=t11t13:=t1t14:=at12at12:=t14t15:=t1at15:=x编译原理与技术编译原理与技术
14、1211.2 代码优化的基本技术代码优化的基本技术复写传播复写传播 B5:t6:=t2x:=t3t7:=t2t8:=t4t9:=t5at2:=t5t10:=t4at4:=t3goto B2观察上面观察上面B5中的语句：中的语句：t6:=t2和和x:=at6，t6在赋值完成之后就被引用，而期间没有改在赋值完成之后就被引用，而期间没有改变变t6的值。因此，可以把的值。因此，可以把x:=at6变换为变换为x:=at2。这种变换叫做复写传播，它是对形式。这种变换叫做复写传播，它是对形式为为f:=g的赋值语句（复写）的变换。的赋值语句（复写）的变换。完成上述的复写传播之后，进一步考察可以完成上述的复写传
15、播之后，进一步考察可以发现，在发现，在B2中计算了中计算了t3:=at2，因此，在，因此，在B5中可以删除公共子表达式，把中可以删除公共子表达式，把x:=at2 替换为替换为 x:=t3进而，通过复写传播把进而，通过复写传播把B5中中at4:=x 替换为替换为 at4:=t3同样，同样，B5中的中的t9:=at4 和和at2:=t9可以分可以分别替换为别替换为t9:=t5和和at2:=t5。这样，。这样，B5就就变为变为编译原理与技术编译原理与技术1311.2 代码优化的基本技术代码优化的基本技术i:=m 1j:=nt1:=4nv:=at1i:=i 1t2:=4it3:=at2if t3 v
16、goto B1if i=j goto B6B1B2B4j:=j 1t4:=4jt5:=at4if t5 v goto B3at2:=t5at4:=t3goto B2at2:=vat1:=t3B3B5B6图图11.7 复写传播和删除无用代复写传播和删除无用代码之后码之后删除无用语句删除无用语句 观察经过复写变换之后的B5，可以发现，变量x、t7、t8、t9、t10的值在整个程序汇总不再使用，因此，这些变量的赋值对程序的运算结果没有任何作用，可以把他们删除掉。我们称之为删除无用代码。删除无用赋值语句之后的B5变为：B5:at2:=t5at4:=t3goto B2对B6可以进行同样的处理，结果如图1
17、1.7所示 编译原理与技术编译原理与技术1411.2 代码优化的基本技术代码优化的基本技术u代码外提代码外提 循环是多次重复执行的代码段，在编译程序的优循环是多次重复执行的代码段，在编译程序的优化工作中，循环优化占有十分重要的地位。这是化工作中，循环优化占有十分重要的地位。这是因为，因为，l对于循环次数为对于循环次数为n的一个循环，每节省循环体内一条目标的一个循环，每节省循环体内一条目标指令，运行时间就可以少执行指令，运行时间就可以少执行n条指令；特别地，对于条指令；特别地，对于m重循环的最内循环，每节省一条指令就可以减少执行重循环的最内循环，每节省一条指令就可以减少执行n1*n2*nm条指令
18、。条指令。l此外，现代的高级编程语言中都支持数组、集合、树、此外，现代的高级编程语言中都支持数组、集合、树、图等数据结构，它们广泛地应用在程序中。因此，按照图等数据结构，它们广泛地应用在程序中。因此，按照经济原则，循环优化的效果最为显著。经济原则，循环优化的效果最为显著。编译原理与技术编译原理与技术1511.2 代码优化的基本技术代码优化的基本技术如果它产生的结果在循环中保持不变，就可如果它产生的结果在循环中保持不变，就可以把它提到循环的外边，以避免每次循环都以把它提到循环的外边，以避免每次循环都执行这条代码。例如，对于下面的执行这条代码。例如，对于下面的while语句语句while(i=li
19、mit-2)如果在循环体内如果在循环体内limit的值不变，就可以把它的值不变，就可以把它变换为变换为t:=limit-2;while(i=j goto B6之外，不再被引用。因此，可以删除这些归纳变量i和j，把这个语句变换为if t2=t4 goto B6。经过强度消弱和删除归纳变量，图11.7以及图11.5最后就变换为图11.8。优化的效果:1.B2和B3的代码数从4条减到3条，其中一条从乘法变为加法；2.B5从9条变为3条，B6从8条变为2条。3.尽管B1从4条增加到6条，但是，B1这段代码在程序中仅仅执行一次，所以程序总的运行时间几乎不受B1大小的影响。i:=m 1j:=nt1:=4n
20、v:=at1t2:=4it4:=4jt2:=t2 4t3:=at2if t3 v goto B1if i=j goto B6B1B2B4t4:=t4-4t5:=at4if t5 v goto B3at2:=t5at4:=t3goto B2at2:=vat1:=t3B3B5B6图图11.8 B5和和B6删除公共子表达式以后删除公共子表达式以后编译原理与技术编译原理与技术1811.3 局部优化局部优化 u基本块的变换基本块的变换 除了上面介绍的删除公共子表达式和删除无用代码这除了上面介绍的删除公共子表达式和删除无用代码这两种优化以外，在基本块内可以进行多种等价变换，两种优化以外，在基本块内可以进行
21、多种等价变换，改进代码的质量。改进代码的质量。合并已知量合并已知量l假设在一个基本块内有两条语句：假设在一个基本块内有两条语句：t1:=2t2:=3 t1l如果对如果对t1赋值后，赋值后，t1的值没有改变过，那么，赋值语句的值没有改变过，那么，赋值语句t2:=3 t1右边的两个运算数在编译时刻都是已知量，就可以在编右边的两个运算数在编译时刻都是已知量，就可以在编译时计算出这条赋值语句的右边，而不必等到程序运行时再译时计算出这条赋值语句的右边，而不必等到程序运行时再计算。即，可以把这条语句改为计算。即，可以把这条语句改为t2:=6。这种变换称为合并。这种变换称为合并已知量。已知量。编译原理与技术
22、编译原理与技术1911.3 局部优化局部优化临时变量更名临时变量更名l在一个基本块内有两条语句在一个基本块内有两条语句u:=a+b和和v:=a+b，其中，其中u和和v都是基本快内的临时变量，如果用都是基本快内的临时变量，如果用u替换基本块内的所有替换基本块内的所有v的引用，那么，不改变基本块内的值。事实上，总可以通过的引用，那么，不改变基本块内的值。事实上，总可以通过改变基本块内临时变量的名字而得到一个等价的基本块。改变基本块内临时变量的名字而得到一个等价的基本块。交换语句的次序交换语句的次序l一个基本块内的两条邻近的语句：一个基本块内的两条邻近的语句：u:=a+bz:=x+yl当且仅当当且仅
23、当x和和y都不是都不是u，并且，并且a和和b都不是都不是z时可以改变这两时可以改变这两条语句的位置而不影响基本块。在代码生成的算法中可以发条语句的位置而不影响基本块。在代码生成的算法中可以发现，有时通过改变语句的执行次序，可以产生更高效的目标现，有时通过改变语句的执行次序，可以产生更高效的目标代码。代码。编译原理与技术编译原理与技术2011.3 局部优化局部优化u代数变换代数变换许多代数变换可以简化表达式的运算或加快计算速度，同时保持表达式的值不变。例如，x:=x+0，x:=x0 或x:=x1执行的运算构没有改变x的值，没有任何意义，可以从基本块中删除。又如，x:=y2的指数运算通常要调用一个
24、函数来实现。可以使用等价的代数变换，用简单的乘法运算x:=yy代替幂运算。结合性也可以用于生成公共子表达式。例如，如果源程序a:=b+ce:=c+d+b被翻译成三地址代码：a:=b+ct:=c+de:=t+b如果t的值在基本块之后不再需要了，可以利用加法的结合性和交换性，产生更简洁的代码：a:=b+ce:=a+d编译原理与技术编译原理与技术2111.3 局部优化局部优化u基本块的基本块的DAG实现实现 如果有向图中不存在环路，则称该有向图为如果有向图中不存在环路，则称该有向图为无环有向无环有向图，简称图，简称DAG。本节使用的。本节使用的DAG的结点，带有下属的结点，带有下属标记或附加信息：标
25、记或附加信息：l图的叶结点（无后继结点）用一个标识符（变量名）或常量图的叶结点（无后继结点）用一个标识符（变量名）或常量作标记，表示该结点代表该变量或常数的值。如果叶结点代作标记，表示该结点代表该变量或常数的值。如果叶结点代表某变量表某变量X的地址，则用的地址，则用addr(X)作为该结点的标记。通常作为该结点的标记。通常对叶结点上作为标记的标识符使用下标对叶结点上作为标记的标识符使用下标0以表示它是该变量以表示它是该变量的初始值。的初始值。l图的内部结点（有后继结点）用一个运算符作标记，表示该图的内部结点（有后继结点）用一个运算符作标记，表示该结点代表应用该运算赋对其后继结点所代表的值进行运
26、算的结点代表应用该运算赋对其后继结点所代表的值进行运算的结果。结果。l图上的各个结点还可以附加一个或若干个标识符，表示这些图上的各个结点还可以附加一个或若干个标识符，表示这些变量具有该结点所代表的值。变量具有该结点所代表的值。编译原理与技术编译原理与技术2211.3 局部优化局部优化u基本块的基本块的DAG实现实现n1ABn2Bn1Aopn1ABn2n3C中间代码类型DAG结点（0）A:=B（1）A:=op B（2）A:=B op C=n1An2n3C=n4ABn1n3Cn2(s)n3(s)n1n2ropBCn1(s)（3）A:=BC（4）AC:=B（5）if B rop C goto(s)（
27、6）goto(s)编译原理与技术编译原理与技术2311.3 局部优化局部优化算法算法11.1：基本块的DAG构造算法输入：基本块BBk包含k条语句输出：输出：基本块BBk的DAG图说明：说明：（1）假设DAG结点用一个对象类或结构NODE表示，它包含下列数据成员：label /结点的标记，类型为标识符或常量 left,right/类型为结点NODE，分别指向该结点的左后继结点和右后继结点 labelList/标识符或常量链表，记录结点的附加标识符或常量函数createNode(A)创建并返回一个标记为A的结点，把left，right和labelList初始化为空。（2）假设有一个标识符（常数）
28、与结点的对应表，Node(A)是描述这种对应关系的函数，它对每个标识符给出DAG中一个结点，或者为null表示该标示符还没有定义。NODE n=null,b=null,c=null;/初始化，b和c用以记录是否为当前语句B和C产生了新结点for BB中的每个变量或常量S Node(S)=null;/初始化基本块中的每个变量或常量DAG=null;/可以用链表结构编译原理与技术编译原理与技术2411.3 局部优化局部优化for(i=1;i k;i+)if(Node(B)=null)b=createNode(B);把b加入到DAG中;switch BBi的代码类型case 0型：Node(B)=n
29、;case 1型：if（Node(B)的类型是叶子常量）=op B;/合并已知量if(b!=null)删除结点Node(B)；if(n=Node(p)=null)n=createNode(p);Node(p)=n;else /查找公共子表达式Boolean found=false;while(not found&DAG还没有检查的结点n)if(n.left=Node(B)|n.right=Node(B)&n.label=op)found=true;else 标记该结点为检查过if(not found)n=createNode(op);n.left=Node(B);n.right=Node(C)
30、;/结束case 1的分支语句编译原理与技术编译原理与技术2511.3 局部优化局部优化case 2型：if(Node(C)=null)c=createNode(C);把b加入到DAG中;if(Node(B)的类型是常量&Node(C)的类型是常量）=B op C;/合并已知量if(b!=null)删除结点Node(B)；if(c!=null)删除结点Node(C)；if(n=Node(p)=null)n=createNode(p);Node(p)=n;else /查找公共子表达式Boolean found=false;while(not found&DAG还有没有检查的结点n)if(n.le
31、ft=Node(B)&n.right=Node(C)&n.label=op)found=true;else 标记该结点为检查过if(not found)n=createNode(op);n.left=Node(B);n.right=Node(C);/结束case 2的分支语句/结束分支语句/删除无用赋值语句if(n=Node(A)!=null&n不是叶结点）把A从n.labelList中去掉;把A加入n.labelList;/把A加入结点n的附加信息中Node(A)=n;b=null;c=null;/清除b和c以便记录是否为当前语句的B和C产生了新结点编译原理与技术编译原理与技术2611.3
32、局部优化局部优化例例11.1 构造对下面的基本块构造对下面的基本块B的的DAG。(1)T 0:=3.14(2)T1:=2 T0(3)T2:=R+r(4)A:=T1 T2(5)B:=A(6)T3:=2 T0(7)T 4:=R+r(8)T5:=T3 T4(9)T6:=Rr(10)B:=T5 T6处理每一条语句后构造的处理每一条语句后构造的DAG如图如图11.10所示中各所示中各个子图所示，每个子图对应每条语句。个子图所示，每个子图对应每条语句。编译原理与技术编译原理与技术2711.3 局部优化局部优化图11.10 为例11.1基本块构造的DAG 编译原理与技术编译原理与技术2811.3 局部优化局
33、部优化u基于基于DAG的局部优化的局部优化 将中间代码表示成相应的将中间代码表示成相应的DAG后，就可以对基本块利用后，就可以对基本块利用DAG进进行代码优化。观察行代码优化。观察DAG的构造过程就可以发现：的构造过程就可以发现：算法注释的步骤起到了合并已知量的作用。若参与运算的对算法注释的步骤起到了合并已知量的作用。若参与运算的对象都是编译时刻的已知量，则它并不生成计算该结点值的内部象都是编译时刻的已知量，则它并不生成计算该结点值的内部结点，而是执行该运算，把计算的结果生成一个叶结点。结点，而是执行该运算，把计算的结果生成一个叶结点。算法注释的步骤的作用是检查公共子表达式。对所有具有公算法注
34、释的步骤的作用是检查公共子表达式。对所有具有公共子表达式的语句，它只生成一个计算该表达式值的内部结点，共子表达式的语句，它只生成一个计算该表达式值的内部结点，而把哪些被赋值的变量标识符附加到该结点。这样就可以删除而把哪些被赋值的变量标识符附加到该结点。这样就可以删除冗余运算。冗余运算。算法注释的步骤具有删除无用赋值语句的作用。若某变量被算法注释的步骤具有删除无用赋值语句的作用。若某变量被赋值以后，在它被引用前又被重新赋值，则把该变量从具有前赋值以后，在它被引用前又被重新赋值，则把该变量从具有前一个值的结点上删除。一个值的结点上删除。编译原理与技术编译原理与技术2911.3 局部优化局部优化这样
35、，在一个基本块构造成DAG的过程就已经进行了一些局部优化工作。然后，从DAG就可以重新生成优化过的基本块。例如，将图11.10（10）按照构造结点的顺序重新写成四元式的中间代码，得到下列序列B：(1)T 0:=3.14(2)T1:=6.28(3)T3:=6.28(4)T2:=R+r(5)T4:=T2(6)A:=6.28T2(7)T 5:=A(8)T6:=Rr(9)B:=AT6 和原来的代码相比，可以看出：B中代码（2）和（6）的已知量都被合并了；B中（5）的无用赋值也被删除；B中（3）和（7）的公共子表达式R+r只计算了一次，删除了多余运算。编译原理与技术编译原理与技术3011.3 局部优化局
36、部优化除了可以除了可以DAG进行上述优化以外，还可以从基本块的进行上述优化以外，还可以从基本块的DAG中得中得到一些可以用以优化的信息，包括：到一些可以用以优化的信息，包括：在基本块外被定值并在基本块内被引用的所有标识符，就是作在基本块外被定值并在基本块内被引用的所有标识符，就是作为叶子结点上标记的那些标识符。为叶子结点上标记的那些标识符。在基本块内被定值且该值在基本块后被引用的所有标识符，就在基本块内被定值且该值在基本块后被引用的所有标识符，就是是DAG各结点上的那些附加标识符。各结点上的那些附加标识符。利用这些信息以及有关变量在基本块之后的引用情况（可以通利用这些信息以及有关变量在基本块之
37、后的引用情况（可以通过全局数据流分析得到，参见过全局数据流分析得到，参见10.5节），可以进一步删除基本节），可以进一步删除基本块中其它情况的无用赋值语句。块中其它情况的无用赋值语句。在上面的例子中，加入临时变量在上面的例子中，加入临时变量T0、T1、.、T6在基本块之后在基本块之后都没有被引用，则可以把图都没有被引用，则可以把图10.8（10）中的）中的DAG重新写成下列重新写成下列代码：代码：(1)T2:=R+r(2)A:=6.28 T2(3)T6:=Rr(4)B:=A T6 删除了其中的四个临时变量删除了其中的四个临时变量T1、T3、T4和和T5。编译原理与技术编译原理与技术3111.4
38、 机器代码优化窥孔技术机器代码优化窥孔技术 窥孔优化是在目标代码级上进行局部改进的窥孔优化是在目标代码级上进行局部改进的简单而有效的技术，它只考察一小段目标指简单而有效的技术，它只考察一小段目标指令（窥孔），只要可能，就把它用更快、更令（窥孔），只要可能，就把它用更快、更短的指令替换，提高目标指令的质量。短的指令替换，提高目标指令的质量。这里，窥孔是在目标程序中一个可以移动的这里，窥孔是在目标程序中一个可以移动的窗口。而且，窥孔中的代码不一定是邻接的。窗口。而且，窥孔中的代码不一定是邻接的。窥孔优化的一个特点是，优化后所产生的结窥孔优化的一个特点是，优化后所产生的结果可能会给后面的优化提供进一
39、步的机会。果可能会给后面的优化提供进一步的机会。因此，为了得到最大的优化效果，应该对目因此，为了得到最大的优化效果，应该对目标代码进行若干遍的优化处理。标代码进行若干遍的优化处理。编译原理与技术编译原理与技术3211.4 机器代码优化窥孔技术机器代码优化窥孔技术u冗余存取的删除冗余存取的删除假设在源程序中有下列两条赋值语句：假设在源程序中有下列两条赋值语句：a=ac;c=ad;编译程序为它们生成的目标代码可能是下列指令序列：编译程序为它们生成的目标代码可能是下列指令序列：（1）MOV b,R0（2）ADD c,R0（3）MOV R0,a（4）MOV a,R0（5）SUB d,R0（6）MOV
40、R0,c前三条指令对应第一条语句，后三条指令对应第二条语句，它前三条指令对应第一条语句，后三条指令对应第二条语句，它们都是正确的。然而，不难指令（们都是正确的。然而，不难指令（4）是多余的，因为指令（）是多余的，因为指令（3）表明表明a的值已经在寄存器的值已经在寄存器R0中，可以把指令（中，可以把指令（4）这条多余的存）这条多余的存储删除。但是要注意，如果指令（储删除。但是要注意，如果指令（4）有标号，则有可能抓你指）有标号，则有可能抓你指令从其它指令转移控制来执行这条指令，这样的化就不能删除令从其它指令转移控制来执行这条指令，这样的化就不能删除指令（指令（4），以免不能保证），以免不能保证a
41、的值在的值在R0中。中。编译原理与技术编译原理与技术3311.4 机器代码优化窥孔技术机器代码优化窥孔技术u不可达代码的删除不可达代码的删除如果在一条无条件转移指令之后的代码没有标号，就表示没有控制会转移到这如果在一条无条件转移指令之后的代码没有标号，就表示没有控制会转移到这条代码，这条代码就是不可能执行的不可达代码或死代码，可以删除。不可达条代码，这条代码就是不可能执行的不可达代码或死代码，可以删除。不可达代码的删除可以重复执行，删除一系列指令。代码的删除可以重复执行，删除一系列指令。产生不可达代码的典型情况是处于调试程序的目的，在一个大程序中插入调试产生不可达代码的典型情况是处于调试程序的
42、目的，在一个大程序中插入调试状态变量状态变量debug。在程序的调试状态下（。在程序的调试状态下（debug=1）可以打印调试信息；在程序）可以打印调试信息；在程序正常运行的状态下（正常运行的状态下（debug=0），不打印调试信息。例如，在），不打印调试信息。例如，在C语言程序中，可语言程序中，可以有如下的代码片断：以有如下的代码片断：#define debug 0if(debug=1)打印调试信息打印调试信息翻译的中间代码可能是翻译的中间代码可能是 if debug=1 goto L1 goto L2L1:打印调试信息打印调试信息L2:在非调试状态下，调试状态变量在非调试状态下，调试状态变
43、量debug为常量为常量0，所以，条件，所以，条件debug=1永远不满永远不满足，在无条件代码足，在无条件代码goto L2之后的标号为之后的标号为L1的代码不可能执行，应该把它删除。的代码不可能执行，应该把它删除。编译原理与技术编译原理与技术3411.4 机器代码优化窥孔技术机器代码优化窥孔技术u控制流优化控制流优化 由于源程序书写的任意性和随意性，生成的由于源程序书写的任意性和随意性，生成的目标代码中经常出现各种转移指令，造成连目标代码中经常出现各种转移指令，造成连续的跳转情况。控制流的窥孔优化可以在目续的跳转情况。控制流的窥孔优化可以在目标代码中删除不必要的转移。标代码中删除不必要的转
44、移。编译原理与技术编译原理与技术3511.4 机器代码优化窥孔技术机器代码优化窥孔技术转移到转移转移到转移例如转移序列 goto L1 L1:goto L2可以转换为goto L2 L1:goto L2如果没有别的指令跳到L1，并且L1的前面是无条件转移指令，那么，指令L1:goto L2也可以删除。转移到条件转移转移到条件转移假设有转移序列L0:goto L1 L1:if(b)goto L2L3:如果只有一个转移到L1，并且L1的紧前面是无条件转移指令，那么，上述这些指令可以替换为：L0:if(b)goto L2 goto L3 L1:if(b)goto L2L3:尽管改变前后的指令一样多，
45、但是，改变后的转移更直接了，节省了一次无条件转移。编译原理与技术编译原理与技术3611.4 机器代码优化窥孔技术机器代码优化窥孔技术条件转移到转移条件转移到转移假设有转移序列if(b)goto L1 L1:goto L2可以替换为if(b)goto L2 L1:goto L2改变之后，当b为true时可以节省一次控制转移。编译原理与技术编译原理与技术3711.4 机器代码优化窥孔技术机器代码优化窥孔技术u代数化简与强度消弱代数化简与强度消弱 窥孔优化时，可以利用代数化简，既代数恒窥孔优化时，可以利用代数化简，既代数恒等式进行等价变换，来减弱目标代码，优化等式进行等价变换，来减弱目标代码，优化代
46、码。考虑到优化的代价和效果，仅对经常代码。考虑到优化的代价和效果，仅对经常出现的一些进行代数化简。例如，用出现的一些进行代数化简。例如，用x=x+0和和 x=x 1，删除相应的指令；利用，删除相应的指令；利用x2=x x把耗时的指数运算用简单的乘法预算代替。把耗时的指数运算用简单的乘法预算代替。有些指令可以用更优的指令代替。例如，假有些指令可以用更优的指令代替。例如，假设设shiftleft为左操作指令，则为左操作指令，则MUL R,#2 可替换为可替换为 shiftleft R,#1MUL R,#4 可替换为可替换为 shiftleft R,#2编译原理与技术编译原理与技术3811.4 机器代码优化窥孔技术机器代码优化窥孔技术u特殊指令的使用特殊指令的使用 若目标机器指令系统包含有实现某些操作的若目标机器指令系统包含有实现某些操作的高效指令时，在可能的情况下，应该尽量使高效指令时，在可能的情况下，应该尽量使用目标机的特性而改进目标代码的执行效率。用目标机的特性而改进目标代码的执行效率。例如，如果目标机器指令系统有减例如，如果目标机器指令系统有减1指令指令DEC，对应于赋值语句对应于赋值语句i=i1的目标代码的目标代码MOV i,R0SUB#1,R0MOV R0,i就可以简单地用一条指令代替为：就可以简单地用一条指令代替为：DEC i。
