编译原理第六章 代码优化ok

第六章代码优化6.1概述本节内容一.代码优化概念、目的与原则二.代码优化器的地位和结构三.代码优化分类四.代码优化涉及的各个环节五.四元式的改写六.引例：优化主要方法简介一.代码优化概念、目的与原则优化的目的是为了产生更高效的代码。对程序进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码，我们通常称这种变换为优化。优化的原则：(1)等价原则(3)合算原则(2)有效原则经过优化后不应改变程序运行的结果。使优化后所产生的目标代码运行时间较短，占用的存储空间较小。应尽可能以较低的代价取得较好的优化效果。二.代码优化器的地位和结构编译前端代码生成代码优化器控制流分析代码变换数据流分析三.代码优化分类另一类重要的优化是在生成目标代码时进行的这类优化很大程序上依赖于具体的计算机。优化可在编译的各个阶段进行，不是“最佳化”最主要一类优化是在目标代码生成以前，对语法分析后的中间代码进行的。这类优化不依赖于具体的计算机。1.

按所处阶段分类高级语言的源程序代码优化，由编程人员根据程序设计技术来进行；三.代码优化分类单个基本块内局部优化2.

按所涉及范围循环优化涉及所有代码全局优化可能涉及多个基本块四.代码优化涉及的各个环节选择适当的算法源代码安排适当的实现语句源代码的优化很重要设计语义动作时考虑产生更加高效的中间代码为后面的优化阶段做一些可能的预备工作中间代码安排专门的优化阶段，进行各种等价变换本章讨论的重点目标代码有效地利用寄存器选择指令五.四元式的改写(:=,B,,A)改写成A:=B(op,B,,A)改写成A:=opB(op,B,C,A)改写成A:=BopC(=[],B,C,A)改写成A:=B[C]([]=,B,,D[C])改写成D[C]:=B(jrop,B,C,L)改写成ifBropCgotoL(j,,,L)改写成gotoL6.2局部优化本节内容

一.基本块二.基本块内的优化方法三.流图四.基本块的DAG表示及其应用五.应用DAG时的相关问题一.基本块及流图2.各个操作按代码的排列顺序执行；3.若任一语句被执行，则块内所有语句都被执行；否则，块内语句都不执行。1.入口就是其中的第一个语句；出口就是其中的最后一个语句，都是唯一的局限于基本块范围内的优化称为基本块内的优化，或称为局部优化。所谓基本块，是指程序中一顺序执行的语句序列，其中只有一个入口和一个出口。1.基本块在一个基本块中的一个名字，在程序中的某个给定点是活跃的，是指如果在程序中（包括在本基本块或在其他基本块中）它的值在该点以后被引用如果一条三地址语句为x：=y+z，则称对x定值

并引用y和z此时T2被定值引用了a和b2.定值与引用此点T2是活跃的因为后面两处引用了T2T2T2T21.确定四元式程序中各个基本块的入口语句6.2.1.

划分四元式程序为基本块的算法(1)程序的第一个语句(2)能由条件转移语句或无条件转移语句转移到的语句(3)紧跟在条件转移语句后面的语句2.对以上求出的每一入口语句，构造其所属的基本块它是由该入口语句（开始）到另一入口语句(不包括该入口语句)，或到一停语句(包括该停语句)一转移语句(包括该转移语句)，或到之间的语句序列组成的3.删除无用代码凡未被纳入某一基本块中的语句，都是程序中控制流程无法到达的语句，从而也是不会被执行到的语句，我们可把它们从程序中删除入口语句4.划分基本块示例readXreadYR:=XmodYifR=0goto(8)X:=YY:=Rgoto(3)writeYhalt程序的第一条语句条件转移语句转到的语句在条件转移语句后的语句无条件转移语句转到的语句基本块二.基本块内的优化方法如：对于

T1:=2...T2:=4*T1此时可把T2:=4*T1

变换为T2:=8若两个运算对象都是编译时的已知量。可以在编译时计算出它的值，而不必等到程序运行时再计算。我们称这种变换为合并已知量。1.合并常数和已知量

如：假定在一个基本块里有语句：

（1）T1:=A*B（6）T4:=A*B四元式（1）和（6）中，它们的运算相同而且值不变，因此（6）的运算是多余的，可将它等价变换为：（6'）T4:=T1消除多余运算是指对程序中重复而且结果不变的运算，2.消除多余运算；

如：（5）C:=2

（6）T4:=A*B

（7）T5:=18+C

（8）T6:=4*T5

（9）Y:=T6消除无用赋值是指对程序中的无用赋值予以消除。3.消除无用赋值

如：语句

x:=y**2中的乘方运算，通常需要调用一个函数来实现。可以用代数上等价的形式，用简单的运算替换。

x:=y*y对基本块中求值的表达式，用代数上等价的形式替换，以期使复杂运算变成简单运算。我们称这种变换为代数变换。4.

代数变换如果一个表达式E在前面已计算过，并且在这之后E中变量的值没有改变，则称E为公共子表达式。删除公共子表示式(删除多余运算)对于公共子表达式，我们可以避免对它的重复计算，称为删除公共子表达式(有时称删除多余运算)。公共子表达式可以在基本块内，也可以在全局范围内消除。T6：=T2(复写语句)把T2赋给T6，x：=a[T6]中引用了T6的值，而这中间没有改变T6的值。因此，可以把x：=a[T6]变换为x：=a[T2]这种变换称为复写传播。5.复写传播(重复传送)“复写”强调了重复性，传播是由复写引起的复写传播的目的是使对某些变量的赋值变为无用换言之，将来可以删除这些无用赋值语句6.复写传播示例T6:=T2x:=a[T6]x:=a[T2]T6:=T2T7:=T6T7:=T2T6:=T2a[T7]:=T9a[T2]:=T9T7:=T6T8:=T4T9:=a[T8]T9:=a[T4]T8:=T4T10:=T8T10:=T4T8:=T4a[T10]:=xa[T4]:=xT10:=T8在B2中有T3:=a[T2]x:=a[T2]x:=T3在B2中有T3:=a[T2]a[T4]:=xa[T4]:=T3x:=a[T2]在B3中有T5:=a[T4]T9:=a[T4]T9:=T5在B3中有T5:=a[T4]a[T2]:=T9a[T2]:=T5T9:=a[T4]由于某些变量的值在整个程序中不再被使用，因此，这些变量的赋值对程序运算结果没有任何作用。我们可以删除对这些变量赋值的代码。我们称之为删除无用赋值或删除无用代码。7.

删除无用代码(删除无用赋值)8.

删除无用代码示例a[T2]:=T5a[T4]:=T3gotoB2无用代码三.基本块的DAG表示及其应用DAG(DirectedAcyclicGraph)无环路有向图一个基本块的DAG是一种其结点带有下述标记或附加信息的DAG，描述出基本块中每个运算结果如何用于块中后续运算。1.

概念1.叶结点——值3.结点标识符2.其他结点——运算或变量图的叶结点以一标识符(变量名)或常数作为标记，表示该结点代表该变量或常数的值。如果叶结点用来代表某变量A的地址，则用addr(A)作为该结点的标记内部结点以一运算符作为标记，表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果图中各个结点上可能附加一个或多个标识符，表示这些变量具有该结点所代表的值四元式的类型与DAG结点数组元素的赋值A[B]:=C为3型四元式，将在6.2.4节讨论；转移goto(s)是一个孤立结点。2.

构造基本块的DAG的思想对于基本块中的每个四元式A:=BopC

1.如果它们都是叶结点，且其标记均为常数，则直接执行运算BopC，然后建立以其运算结果P为标记的叶结点并把A附加到此结点上去

（如果以B或C为标记的结点是为处理本四元式才建立的，则将它们删除）。首先找出（或建立）代表B和C“当前值”的结点2.如果B或（和）C是内部结点，则建立以op为标记的新结点，此结点分别以B、C所标记的结点为其左、右直接后继结点，并将A附加到新建的结点上。

注意，若在此之前，DAG中已有结点其上有附加标记A，且此结点无前驱，则在建立新结点的同时，应把老结点上附加的A删除，以表示A的当前值由新建立的结点代表；3.若DAG中原来已有代表BopC的结点，则不必建立新的结点，只须把变量A附加到表示BopC之值的结点上去即可。2.

构造基本块的DAG的算法（算法6.2）1.叶结点生成代码类型判断3.查找、处理公共子表达式2.常数参数与非常数参数的判断4.赋值号处理四.基本块的DAG表示及其应用

构造基本块的DAG的算法流程初始化生成B01生成CB是常数2B不是常数寻找公共子表达式B、C都是常数B或者C不是常数合并已知量生成新常数P处理赋值号处理A合并已知量生成新常数P寻找公共子表达式n13.14T0T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T6:=R–rB:=T5*T6文法GNODE(3.14)无定义，构造一个标记为3.14的结点当前代码为0型，记NODE(3.14)的值为n1,转4T0:=3.14NODE(T0)无定义，将T0附加在结点n1上令NODE(T0)=n1，转处理下一条代码T1:=2*T0NODE(2)无定义，构造一个标记为2的结点当前代码为2型，NODE(T0)已定义，转2（2）NODE(2)和NODE(T0)均已定义，转2（4）执行2*T0，新得到常数6.28,NODE(2)是处理当前代码时新构造出来的，删除之，NODE(6.28)无定义，构造一个标记为6.28的结点n2，置NODE(6.28)=n2，转4NODE(T1)无定义，将T1附加在结点n2上令NODE(T1)=n2，转处理下一条代码n22T1n26.28T2:=R+rNODE(R)无定义，构造一个标记为R的结点n3，令NODE(R)=n3当前代码为2型，NODE(r)无定义，构造一个标记为r的结点n4，令NODE(r)=n4，转2（2）n3Rn4rNODE(R)不是标记为常数的结点，转3（2）DAG中无结点其左后继为NODE(R)，故构造一个结点n5，其左后继为NODE(R)，右后继为NODE(r)，转4n5+NODE(T2)无定义，将T2附加在结点n5上，令NODE(T2)=n5，转处理下一条代码T2A:=T1*T2NODE(T1)已定义，当前代码为2型，NODE(T2)已定义，转2（2）NODE(T1)不是标记为常数的结点，转3（2）DAG中无结点其左后继为NODE(T1)，故构造结点n6，其左后继为NODE(T1)，右后继为NODE(T2)，转4n6*NODE(A)无定义，将A附加到结点n6上，令NODE(A)=n6，转处理下一条代码AB:=ANODE(A)已定义，当前代码为0型，转4NODE(B)无定义，将B附加到结点n6上，令NODE(B)=n6，转处理下一条代码T3:=2*T0NODE(2)无定义，构造一个标记为2的结点n7，令NODE(2)=n7n72当前代码为2型，NODE(T0)已定义，转2（2）NODE(2)和NODE(T0)都为标记为常数的结点，转2（4）执行2*T0，得到6.28，NODE(2)是处理当前代码时构造出来的，删除之；NODE(6.28)已有定义n2，转4NODE(T3)无定义，将T3附加到NODE(6.28)上，即附加到n2上，转处理下一条代码T1,T3A,BT4:=R+rNODE(R)已定义，当前代码为2型，

NODE(r)已定义，转2（2）NODE(R)不是标记为常数的叶结点，转3（2）DAG中结点n5其左后继为NODE(R)，右后继为NODE(r),且其标记为+，故将n5作为当前结点，转4NODE(T4)无定义，将T4附加到结点n5上，令NODE(T4)=n5，转处理下一条代码T2,T4T5:=T3*T4NODE(T3)已定义，当前代码为2型，NODE(T4)已定义，转2（2）NODE(T4)不是标记为常数的叶结点，转3（2）DAG中结点n6其左后继为NODE(T3)，右后继为NODE(T4)，且标记为*，故将n6作为当前结点，转4NODE(T5)无定义，故将T5附加到结点n6上，转处理下一条代码A,B,T5T6:=R–rNODE(R)已定义，当前代码为2型，NODE(r)已定义，转2（2）NODE(R)不是标记为常数的叶结点，转3（2）DAG中无结点其左后继为NODE(R)，右后继为NODE(r)，且标记为-；故构造结点n7，使其左后继为NODE(R)，右后继为NODE(r)，且标记为-，转4n7-NODE(T6)无定义，将T6附加到结点n7上，转处理下一条代码T6B:=T5*T6NODE(T5)已定义，当前代码为2型，NODE(T6)已定义，转2（2）NODE(T5)不是标记为常数的叶结点，转3（2）DAG中无结点其左后继为NODE(T5)，故构造结点n8，使其左后继为NODE(T5)，右后继为NODE(T6)，且标记为*

，转4n8*NODE(B)已定义，故将B从NODE(B)结点（当前为n6）中的附加标识符集中删除A,T5B将B附加到n8上，令NODE(B)=n8，转处理下一条代码所有代码处理完毕，构造过程结束文法G的最终DAG如上图所示4.

构造DAG示例例6.2

对如下的基本块构造基本块DAG：（1）T1:=A*B（2）T2:=3/2（3）T3:=T1-T2（4）X:=T3（5）C:=5（6）T4:=A*B（7）C:=2（8）T5:=18+C（9）T6:=T4*T5（10）Y:=T基本块的优化处理第一，合并常数和已知量的运算，并将产生的运算结果标记为叶结点，不再产生运算的内部结点（见图6-2(b),(g)）T2:=3/2第二，合并公共子表达式基本块内多次出现同一运算的四元式，仅构造第一个四元式运算的内部结点；以后的各次出现，只把要赋予结果的各变量标识符附加到相应内部结点（见图6-2(e)）（1）T1:=A*B（3）T3:=T1-T2（4）X:=T3（6）T4:=A*B第三，消除基本块内无用赋值。在基本块内被多次赋值的变量，若在被引用之前被再次赋值，算法6.2的第（4）步，除了把此变量名附加到新产生的结点之外，还把它从老结点的附加标识符集中逐出（见图6-2(f)），使对该变量的前一次赋值无效

C=5

c=2由DAG重写代码重写中间代码的顺序应遵循(2)转移语句(如果有的话)仍然是基本块的最后一个语句(保证基本块的正确性)(1)其中任一内部结点在其后继结点之前被重写(保证计算的正确性)目的：生成有效目标代码n13.14T0B:=A*T6n26.28n3Rn4rn5+n6*T1,T3T2,T4n7-T6n8*A,T5BT0:=3.14T1:=6.28T3:=6.28T2:=R+rT4:=T2A:=6.28*T2T5:=AT6:=R–rT0T1T3T2T4AT5T6B基本块n1结点标记为常数，故产生T0:=3.14n2结点标记为常数，故产生T1:=6.286.

由DAG重写代码示例n2结点标记为常数，故产生T3:=6.28T4与T2同标记在一个结点，故产生

T4:=T2T5与A同标记在一个结点，故产生

T5:=An2结点标记为常数，故产生A:=6.28*T2重写过程结束，基本块如上所示B:=A*T6T0:=3.14T1:=6.28T3:=6.28T2:=R+rT4:=T2A:=6.28*T2T5:=AT6:=R–rT0:=3.14T1:=2*T0B:=T5*T6T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T6:=R–r基本块G基本块G’优化效果比较消除无用赋值合并公共子表达式合并常数和已知量的运算五.含有数组元素的DAG3型四元式B[C]:=D对应的DAG结点形式五.含有数组元素的DAGx:=a[i]a[j]:=yz:=a[i]四元式序列为：（1）T1:=addr(A)-1（2）X:=T1[i]（3）T2:=addr(A)-1（4）T2[j]:=Y（5）T3:=addr(A)-1（6）Z:=T3[i]例考虑如下的源程序段：基本块的DAG，算法6.2（1）T1:=addr(A)-1（2）X:=T1[i]（3）T2:=addr(A)-1（4）T2[j]:=Y（5）T3:=addr(A)-1（6）Z:=T3[i]；优化：（1）T1:=addr(A)-1（2）X:=T1[i]（3）Z:=X（4）T1[j]:=Y原因：对一个数组元素赋值时，可能改变表达式a[i]的值，所以即使a和i都没有改变，其值可能已改变了。优化前x:=a[i]a[j]:=yz:=a[i]此时Z=y优化后x:=a[i]z:=xa[j]:=y此时Z=a[i]例：在i=j并且y!=a[i]时，2.

数组元素引用问题解决方法在建立对一个数组A的元素赋值的结点时，“封锁”那些以addr(A)作为它的后代之一、且所标记的运算符为“=[]”的结点。

谓封锁一个结点，是指在该结点上做一个标志Δ，表示不允许在这些结点上再附加任何新的标识符，从而取消了它作为公共子表达式的资格。所构造的DAG优化后的四元式序列

（1）T1:=addr(A)-1（2）X:=T1[i]（3）T1[j]:=Y（4）Z:=T1[i]与原四元式是完全等价6.3全局优化全局优化需要在整个程序范围内，对程序中的全部变量的定值和引用之间的关系进行分析，这一分析过程称为数据流分析。确切地查找基本块中的无用赋值，不仅需要了解基本块中对变量的定值和引用的情况，还应知道在基本块外变量是否被引用。数据流分析作用：对消除无用赋值提供了可靠的依据，循环优化和全局优化一种强有力的工具程序流图流图以基本块为结点。如果一个结点的入口语句是程序的第一条语句，则称此结点为首结点。通过构造一个有向图，称之为流图，我们可以将控制流的信息增加到基本块的集合上来表示一个程序。1.

概念程序流图的结点集就是程序的基本块集。构造程序流图的方法是：对于程序中的两个基本块Bi和Bj，如果Bj紧接着Bi被执行，则从Bi引一条有向边到结点Bj，称Bi为Bj的直接前驱，Bj为Bi的直接后继。规则1：按基本块在程序中排列的自然次序，Bj紧跟在Bi之后，且Bi的出口语句不是无条件转移或停语句；规则2：Bi的出口语句是一个无条件转移或条件转移语句，且其目标是Bj的入口语句。2.构造程序流图示例

(1)readX(2)readYB1(3)R:=XmodY(4)ifR=0goto(8)B2(5)X:=Y(6)Y:=R(7)goto(3)B3(8)writeY(9)haltB4程序流图示例(1)I:=0(2)I:=I+1(3)IfI<=Ngoto（5）(4)goto（8）(5)T:=M+I(6)M:=T(7)goto（2）(8)stop6.3.2到达－定值数据流方程为了进行循环优化和全局优化，需要分析程序中所有变量的定值（指对变量赋值）和引用之间的关系，这一工作称为数据流分析

一、作用

分析程序中所有变量的定值(指对变量的赋值或输入值)和引用之间的关系、基本块出口的活跃变量信息等，以进行循环优化和全局优化。二、方法1、使用变量到达－定值数据流方程和变量引用－定值链2、使用活跃变量数据流方程三、基本概念a)点程序中某一四元式的位置(序号或地址)b)定值点对某变量赋值或输入值的四元式的位置c)引用点引用某变量的四元式的位置d)变量A的到达与定值若d点是变量A的一个定值点，u点是A的一个引用点，存在一条从d到u的通路，并在此通路上没有对A的其他定值点，则称d点对A的定值能达到u点。e)引用－定值链假定在程序中某点u引用了变量A，则把能到达u的A的所有定值点的全体，称为A在引用点u的引用－定值链(ud链)到达－定值数据流方程求解a)基本量1)IN[B]

能到达基本块B入口点的各个变量的定值点集合。B入口集合

2)OUT[B]

能到达基本块B出口点的各变量全部定值点集合。B出口集合

3)GEN[B]

基本块B中定值并能到达B出口点的所有定值点集合。B中“生成”的集合

4)KILL[B]

因B中定值而注销所有与它相关变量的定值点集合。B中“杀死”的集合3.

示例(1)a:=d(2)ifa=bthengotoB2(3)b:=1(4)c:=1(5)a:=a+bB1B2B3B4(1)a:=d基本块InGenKillOutB1∅{1}∅{1}B2{1}{3}∅{1，3}B3{1}{4}∅{1，4}B4134{5}{1}345(3)b:=1(4)c:=1(5)a:=a+baab集合GEN[B]及KILL[B]可以根据程序流图，对基本块B的DAG叶结点所标记的标识符及内部结点的附加标识符进行考察，确定各个定值点。对程序流图中的所有基本块B求出相应IN[B]之后，按如下规则确定到达B中点P的任一变量A的全部定值点。规则1：如果B中P点之前有A的定值（可能为多个），则这些定值点中，离P最近的那个点就是能到达P的唯一定值点；规则2：如果B中P点之前无A的定值，则能到达P的A的定值点是包含在集合IN[B]中的那些A的定值点。四个集合之间内在的关系首先，程序中某一点d对变量A的定值可到达基本块B的出口之后，当且仅当（1）此定值能到达基本块B的入口之前，且B中不再对A重新定值（即d∈IN[B]-KILL[B]）；（2）或者点d在B中，且对A的定值能到达B的出口之后（即d∈GEN[B]）

OUT[B]=IN[B]–KILL[B]GEN[B](6.1)其次，程序中某一点d对变量A的定值可到达基本块B的入口之前，当且仅当此定值能到达B的某一直接前驱之后。（6.2）。

IN[B]=(Pred[B]代表B的所有前驱基本块集合)b)基本方程OUT[B]=IN[B]–KILL[B]GEN[B](6.1)IN[B]=（6.2）

注：1)由于所有KILL[B]和GEN[B]可从给定的流图中直接求出，所以，上述等式是关于变量IN[B]和OUT[B]的线性联立方程组，称为到达—定值数据流方程。

2)流图中若有n个基本块，则此方程共有2n个，其中GEN[B]就是基本块内DAG图上的附标，

KILL[B]指若Ai在本块内定值，就将所有Ai定值点(除本定值点)均注销。(Pred[B]代表B的所有前驱基本块集合)算法6.3迭代法求解集合方程组(6.1)-(6.2)1for(i=1;i<=N;i++){2IN[Bi]=φ;3OUT[Bi]=GEN[Bi];}4CHANGE=1;5while(CHANGE){6CHANGE=0;7for(i=1;i<=N;i++){8NEWIN=;9if(NEWIN!=IN[Bi]){10CHANGE=1;11IN[Bi]=NEWIN;12OUT[Bi]=(IN[Bi]-KILL[Bi])∪GEN[Bi];}}}例6.4图6-66.3.3引用－定值链(ud链)的计算及应用1、定义假定在程序中某点u引用了变量A，到达u的变量A的定值点集合称为变量A在u点的ud链。2、构成规则a)在基本块B中，变量A在引用点u前有定值点d，并且d点的定值链能到达u，则A在u点的ud链={d}.(6.5)b)若在基本块B中，在u点之前无对A的定值点，则变量A在u点的ud链={IN[B]中有关A定值的集合}注：这里，链是指将集合中各定值点连在一起构成链，以便于检索。(6.6)例6.5

变量I的引用点为d2和d6，J的引用为d4，d5和d7。求出它们的ud链。对于基本块B1，由于I的引用点d2之前有唯一的定值点d1，因此，

I在d2的ud链为{d1}。对基本块B3，由于J的引用点d4之前无J的块内定值点，故J在d4的ud链为IN[B3]中所包含的J点的定值点，即

{d2，d4，d5}。常数传播及相应地合并已知量如果能到达某一点P有变量A的唯一定值点d：A:=c（c为常数）P是A的一个引用点，那么，在P点A的值也必然为c，故可将P点对A的引用代之以常数c，这种操作称为常数传播。在图6-6中，由于IN[B5]={d3，d4，d5}，故能到达d6的I的定值点是唯一的，即d3：I:=1从而可知在d6对I的引用可替之以常数1，也就是可将d6改写为d6：I:=6算法6.4

常数传播和合并已知量的处理CHANGE=1;while(CHANGE){CHANGE=0;for(程序中的每个语句s){for(s的每个运算量v)

if(v在引用点s的ud链仅含一个d且语句d为v=C(C为常数)){把s中所有对v的引用均替换为C;CHANGE=1;}

if(s右端含有运算符且每个运算量都为常数){C=s的右端表达式；把语句s替换为A=C(A为语句的s左部量);CHANGE=1;}}}6.3.4活跃变量及数据流方程1、活跃变量变量A在程序中某一点P是活跃的，是指在程序流图中，存在一条从P到A的引用点的通路。显然，如果变量A在基本块B中的P点定值，且从P开始直到B的出口都没有A的引用点，若A在B的出口之后也不活跃，则A在P点的定值就必然是无用赋值2、活跃变量数据流方程a)基本量1)INL[B]

基本块B入口点之前活跃变量集合。

2)OUTL[B]

基本块B出口点之后活跃变量集合。3)DEF[B]

基本块B内定值的，但在定值前未曾在B中引用过的变量集合。4)USE[B]

基本块B中引用，但引用前未曾在B中定值的变量集合(即DAG中叶结点的标识符)。2、活跃变量数据流方程b)基本方程

INL[B]=OUTL[B]–DEF[B]USE[B](6.3)OUTL[B]=(6.4)

注：1)USE[B]和DEF[B]可在各基本块内直接求得。2)假定数据流有n个基本块，则上述方程有2n个。3)可通过联立方程组求得各基本块的INL[B]和OUTL[B]。算法6.5求解活跃变量数据流方程(6.3)-(6.4)的迭代算法p160(Succ[Bi]代表Bi的所有后继基本块集合)例6.6

求出程序流图6-6的各基本块的OUTL集和INL集。6.3.5定值-引用链对于变量A的定值点P，从P出发能到达的全部A的引用点所组成的集合，称为A在定值点P的定值-引用链（简称为du链）。显然，求变量A在其定值点的du链的问题，恰好是求变量A在其引用点的ud链的逆问题。6.4循环优化本节内容

一.循环优化概述二.代码外提三.强度削弱四.删除归纳变量

循环优化概述循环中存储空间变化一般不大因为循环中代码可能要反复执行，所以，进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大的作用。（尤其要注意优化内层循环）循环就是程序中那些可能反复执行的代码序列。1.概念在程序流图中，循环为：1.有唯一的入口结点，从循环外到循环内任何结点的所有通路，都必通过此入口结点。2.组内的结点是强连通的。即从组内的任一结点出发，都能到达组中任一的结点。特别是，当组内仅含一个结点时，必有从此结点到其自身的有向边。此性质说明，如果一组结点不是强连通的，则至少其中存在一部分结点不能被重复地执行。循环优化方法可以对循环代码实行优化：代码外提、强度削弱、删除归纳变量。循环中的某些代码，其运算的结果往往是不变的。对于这种不变运算，我们可以把它外提到循环外。这样，程序的运行结果仍保持不变，但程序的运行速度却提高了。我们称这种优化为代码外提。一.代码外提代码外提需解决如下三个问题：1.如何识别循环中的不变运算代码？2.把循环中的不变运算代码提到循环外的什么地方？3.何种循环不变运算代码可以外提，而且不会给整个程序的执行带来副作用？或者说在什么条件下才能实现代码外提？1.如何识别循环中的不变运算代码？根据循环L中的每个变量在其各引用点的ud链，便可确定能到达这些引用点相应变量的定值点是否在L之外。2外提到哪里？？循环前置结点2.循环的前置结点前置结点的构造：1新结点在循环入口结点前面建立一个新结点(基本块)，称为循环的前置结点入口结点循环L前置结点2输出循环前置结点以循环入口结点为其唯一后继3输入

原来流图中从循环外引到循环入口结点的有向边，改成引到循环前置结点3.例一左图B3中I:=2是循环不变运算，能否将其外提（如右图所示）呢？？当X=30Y=25时I=1I=2代码外提后程序结果发生改变，故此时不能外提X所谓出口结点，是指循环中从该结点有一有向边引到循环外的某结点。此处即为B4错误原因分析：B3不是此循环的必经结点（左图），而将I:=2外提后，将其从非必经结点放入了必经结点（右图），故程序结果有所不同解决方法：当把一不变运算外提到循环前置结点时，要求该不变运算所在的结点是循环所有出口结点的必经结点。4.例二右图B4中I:=2能否外提？I:=1B1ifX<YgotoB3B2A:=I+1X:=X+1B3

I:=2Y:=Y-1ifY<=0gotoB5B4J:=AB5I:=2当X=0Y=2时，执行顺序为B2B3B4B2B4B5原始结果J=2外提后结果J=3I:=1B1ifX<YgotoB3B2A:=I+1X:=X+1B3

Y:=Y-1ifY<=0gotoB5B4J:=AB5I:=2B2’I:=2原始流图如右图所示代码外提后流图如右图所示原因分析：外提前A赋值时I的定值为B1中的I:=1，且循环中的I:=2定值不能到达A的定值点故A最终值为2外提后A赋值时I的定值为B2’中的I:=2，故A最终值为3解决方法：当把循环不变运算A：=BopC外提时，要求循环中A的所有引用点都是而且仅仅是这个定值所能到达的。依次查看L中各基本块的每个代码，如果它的每个运算对象5.查找循环L的不变运算的算法或为常数或者定值点在L外则将此代码标记为“不变运算”。(以上两点根据数据流分析可知)重复第(3)步直至没有新的代码被标记为“不变运算”为止。依次查看尚未被标记为“不变运算”的代码，如果它的每个运算对象或为常数或者定值点在L外则将此代码标记为“不变运算”或只有一个到达一定值点且该点上的代码已标记为“不变运算”(1)不变运算的初始标记(2)循环(3)不变运算的传播6.

代码外提示例(2)ifI>10goto(15)B2(15)...B3(3)T1:=2*J(4)T2:=10*I(5)T3:=T2+T1(6)T4:=addr(A)-11(7)T5:=2*J(8)T6:=10*I(9)T7:=T6+T5(10)T8:=ddr(A)-11(11)T9:=T8[T7](12)T4[T3]:=T9+1(13)I:=I+1(14)gotoB2(3)T1:=2*J(6)T4:=addr(A)-11(7)T5:=2*J(10)T8:=ddr(A)-11查找不变运算J的定值点在循环外边addr(A)的定值点在循环外边代码外提B2’(2)ifI>10goto(15)B2(15)...B3(4)T2:=10*I(5)T3:=T2+T1(8)T6:=10*I(9)T7:=T6+T5(11)T9:=T8[T7](12)T4[T3]:=T9+1(13)I:=I+1(14)gotoB2(3)T1:=2*J(6)T4:=addr(A)-11(7)T5:=2*J(10)T8:=ddr(A)-11B2’强度削弱可以强度削弱是指把程序中执行时间较长的运算替换为执行时间较短的运算。（即将复杂（高阶）运算用“递归+低阶运算”代替）二.强度削弱对乘法运算使用变址器对加法运算2.强度削弱示例--对乘法运算(2)ifI>10goto(15)B2(15)...(3)T1:=2*J(6)T4:=addr(A)-11(7)T5:=2*J(10)T8:=ddr(A)-11B2’B3中I是递归赋值变量，每循环一次其值增加1B3中T2是I的线性函数，每循环一次其值增加10故可将(4)提到B2’中，并在(13)后增加代码给T2加常量10，如此程序运行结果保持不变(3)T1:=2*J(6)T4:=addr(A)-11(7)T5:=2*J(10)T8:=addr(A)-11B2’(4)T2:=10*IB3(5)T3:=T2+T1(8)T6:=10*I(9)T7:=T6+T5(11)T9:=T8[T7](12)T4[T3]:=T9+1(13)I:=I+1(14)gotoB2B3(4)T2:=10*I(5)T3:=T2+T1(8)T6:=10*I(9)T7:=T6+T5(11)T9:=T8[T7](12)T4[T3]:=T9+1(13)I:=I+1(14)gotoB2B3(4’)T2:=T2+10(5)T3:=T2+T1(8)T6:=10*I(9)T7:=T6+T5(11)T9:=T8[T7](12)T4[T3]:=T9+1(13)I:=I+1(14)gotoB2同理，可将(8)提到B2’中，并在(4’)后增加代码给T6加常量10，如此程序运行结果保持不变(5)T3:=T2+T1B3(4’)T2:=T2+10(9)T7:=T6+T5(11)T9:=T8[T7](12)T4[T3]:=T9+1(13)I:=I+1(14)gotoB2(3)T1:=2*J(6)T4:=addr(A)-11(7)T5:=2*J(10)T8:=addr(A)-11B2’(4)T2:=10*I(8)T6:=10*IB3(4’)T2:=T2+10(9)T7:=T6+T5(11)T9:=T8[T7](12)T4[T3]:=T9+1(13)I:=I+1(14)gotoB2(5)T3:=T2+T1(8’)T6:=T6+10(4)T2:=10*I(4’)T2:=T2+10(8)T6:=10*I(8)T6:=10*I如此即对原程序中的乘法运算(4)、(8)进行了强度削弱(8’)T6:=T6+10(13)I:=I+1(4)T2:=10*I(4)T2:=10*I基本归纳变量的作用：如果循环中对变量I只有唯一的形如I：=I±C的赋值，且其中C为循环不变量，则称I为循环中的基本归纳变量。三.删除归纳变量用于其自身的递归定值在循环中用来计算其它归纳变量用来控制循环的进行归纳变量的确定——找与基本归纳变量存在的线性关系如果I是循环中一基本归纳变量，J在循环中的定值总是可化归为I的同一线性函数，也即J=C1*I±C2，其中C1和C2都是循环不变量，则称J是归纳变量，并称它与I同族。2.归纳变量(15)...(2)ifI>10goto(15)B2(9)T7:=T6+T5(3)T1:=2*J(6)T4:=addr(A)-11(7)T5:=2*J(10)T8:=ddr(A)-11B2’(4)T2:=10*I(8)T6:=10*I(5)T3:=T2+T1B3(4’)T2:=T2+10(11)T9:=T8[T7](12)T4[T3]:=T9+1(13)I:=I+1(14)gotoB2(5’)T3:=T3+10(8’)T6:=T6+10(9’)T7:=T7+103.示例由B3中(13)可以看出，I是循环的基本归纳变量由B2