1、代码优化代码优化第七章第七章 本章要求本章要求 主要内容主要内容：代码优化的主要功能，局代码优化的主要功能，局部优化、全局优化和循环优化的相关部优化、全局优化和循环优化的相关概念，各种优化技术概念，各种优化技术 重点掌握：重点掌握：代码优化技术，基本块、代码优化技术，基本块、流图、流图、DAG的概念，必经结点、回边、的概念，必经结点、回边、循环的概念，各种优化技术。循环的概念，各种优化技术。代码优代码优化化所地所地位和作位和作用：用：7.1 概述概述实际上很多地方可以对代码的执行效率进行改进，主要讲对中间代码的优化 代码优化：对程序进行等价变换，使得从变换后的程代码优化：对程序进行等价变换，使
2、得从变换后的程序出发，能够生成更有效的目标代码。序出发，能够生成更有效的目标代码。优化分类优化分类 按阶段分按阶段分:与机器无关的优化与机器无关的优化-对中间代码进行对中间代码进行 依赖于机器的优化依赖于机器的优化-对目标代码进行对目标代码进行 根据优化所涉及的程序范围分成根据优化所涉及的程序范围分成:(1)(1)局部优化局部优化:(:(基本块基本块)(2)(2)循环优化循环优化:对循环中的代码进行优化对循环中的代码进行优化 (3)(3)全局优化全局优化:大范围的优化大范围的优化 优化的原则优化的原则等价原则：不改变运行结果等价原则：不改变运行结果有效原则：优化后时间更短，占用空间更少有效原则
3、：优化后时间更短，占用空间更少合算原则：应用较低的代价取得较好的优化效果合算原则：应用较低的代价取得较好的优化效果 宗旨：宗旨：获得较好性能的代码（时间，空间）获得较好性能的代码（时间，空间）等价等价意图、结果之间要权衡意图、结果之间要权衡中间代码优化技术中间代码优化技术 优化工作 数据流分析(data-flow analysis)控制流分析(control-flow analysis)变换(transformations)快速排序程序快速排序程序void quicksort(int m,int n)int i,j,v,x;if(nm)return;i=m-1;j=n;v=an;while(1
4、)do i=i+1;while(aiv);if(i=j)break;x=ai;ai=aj;aj=x;x=ai;ai=an;an=x;quicksort(m,j);quicksort(i+1,n);(1)i=m 1(2)j=n(3)T1=4*n(4)v=aT1(5)i=i+1(6)T2=4*i(7)T3=aT2(8)if T3 v goto(9)(13)if i=j goto(23)(14)T6=4*i(15)x=aT6(16)T7=4*i(17)T8=4*j(18)T9=aT8(19)aT7=T9(20)T10=4*j(21)aT10=x(22)goto(5)(23)T11=4*j(24)x=
5、aT11(25)T12=4*i(26)T13=4*n(27)T14=aT13(28)aT12=T14(29)T15=4*n(30)aT15=x中间代码7.2 基本块的优化基本块的优化 基本块基本块：是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句，入口是其第一个语句，出口是其最后一个语句 如果x:=y+z 则称对x定值定值,引用引用y和z 在一个基本块内的一个名字,在程序中的某个给定点是活跃活跃的，是指如果在程序中它的值在该点之后被引用.入口语句：入口语句：1程序的第一个语句；或者，程序的第一个语句；或者，2条件转移语句或无条件转移语句的转移目标条件转移语句或无条件转移语句的
6、转移目标语句（语句（此处的转移语句包括各种控制的转向，如此处的转移语句包括各种控制的转向，如call，return，end，stop等）等）；或者；或者 3紧跟在条件转移语句后面的语句。紧跟在条件转移语句后面的语句。执行：执行：对于一个基本块，执行时只能从其入口进入，对于一个基本块，执行时只能从其入口进入，从其出口退出从其出口退出划分基本块的算法划分基本块的算法求出四元式程序之中各个基本块的入口语句求出四元式程序之中各个基本块的入口语句对每一入口语句，构造其所属的基本块。它对每一入口语句，构造其所属的基本块。它是由该语句到下一入口语句（不包括下一入口是由该语句到下一入口语句（不包括下一入口语句
7、），或到一转移语句（包括该转移语句），语句），或到一转移语句（包括该转移语句），或到一停语句（包括该停语句）之间的语句序或到一停语句（包括该停语句）之间的语句序列组成的。列组成的。凡未被纳入某一基本块的语句，都是程序中凡未被纳入某一基本块的语句，都是程序中控制流程无法到达的语句，因而也是不会被执控制流程无法到达的语句，因而也是不会被执行到的语句，可以把它们删除。行到的语句，可以把它们删除。一般把过程调用语句作为一个单独的基本块一般把过程调用语句作为一个单独的基本块*(1)read x (2)read yB1*(3)r=x mod y (4)if r=0 goto(8)B2*(5)x=y (6)
8、y=r (7)goto(3)B3*(8)write y (9)haltB4例：例：*(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 流图：有向图。将控制流的信息增加到基本块的集合上来表示一个程序。流图以基本块为单位。如果按顺序执行，就画一条有向边。基本块间的关系:(前驱,后继)B1是B2的前驱前驱，B2是B1的后继后继:有一个条件或无条件转移语句从B1的最后一条语句转移到B2的第一条语句；或者 在程序的序列中，B2紧接在B1的后面，并且B1的最后一条语句
9、不是一个无条件转移语句。B1 B2 B4 B3*(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练习练习 f0=0 f1=1 if m=1 goto L3 i=2L1:if i=m goto L3L2:f2=f0+f1 f0=f1 f1=f2 i=i+1 goto L1L3:return m12345f0=0f1=1if m=1 goto L3i=2L1:if i=m goto L3L2:f2=f0+f1f0=f1f1=f2i=i+1goto L1L3:r
10、eturn m1234512345f0=0f1=1if m=1 goto L3i=2L1:if i=m goto L3L2:f2=f0+f1f0=f1f1=f2i=i+1goto L1L3:return m12345快速排序算法中间代码的基本块和流图(1)i=m 1(2)j=n(3)T1=4*n(4)v=aT1(5)i=i+1(6)T2=4*i(7)T3=aT2(8)if T3 v goto(9)(13)if i=j goto(23)(14)T6=4*i(15)x=aT6(16)T7=4*i(17)T8=4*j(18)T9=aT8(19)aT7=T9(20)T10=4*j(21)aT10=x(
11、22)goto(5)(23)T11=4*j(24)x=aT11(25)T12=4*i(26)T13=4*n(27)T14=aT13(28)aT12=T14(29)T15=4*n(30)aT15=x优化技术优化技术1删除公共子表达式删除公共子表达式 如果表达式E已经在前面计算过，并在计算之后E的值没有改变，则称该表达式为公共子表达式。可以避免重复计算。T6=4T6=4*i ix=aT6x=aT6T7=T7=4 4*i iT8=4T8=4*j jT9=aT8T9=aT8aT7=T9aT7=T9T10=T10=4 4*j jaT10=xaT10=xgoto B2goto B2T6=4T6=4*i i
12、x=aT6x=aT6T7=T7=T6T6T8=4T8=4*j jT9=aT8T9=aT8aT7=T9aT7=T9T10=T10=T8T8aT10=xaT10=xgoto B2goto B24*i，4*j重复计算 在更大的范围内删除4*i,4*j的计算，得到：优化技术优化技术2复写传播复写传播T6=T2T6=T2x=Tx=T3 3T7=TT7=T2 2T8=T4T8=T4T9=T9=T5T5aTaT2 2=T=T5 5T10=TT10=T4 4aTaT4 4=T3T3goto B2goto B2T6=T2T6=T2x=aT6x=aT6T7=T6T7=T6T8=T4T8=T4T9=aT8T9=aT
13、8aT7=T9aT7=T9T10=T8T10=T8aT10=xaT10=xgoto B2goto B2T6=T2，x=aT6，之间没有改变T6,因此，可以直接写x=aT2在B2中T3=aT2因此，x=T3优化技术优化技术3删除无用代码删除无用代码aTaT2 2=T=T5 5aTaT4 4=T3T3goto B2goto B2T6=T2T6=T2x=Tx=T3 3T7=TT7=T2 2T8=T4T8=T4T9=T9=T5T5aTaT2 2=T=T5 5T10=TT10=T4 4aTaT4 4=T3T3goto B2goto B2某些变量的赋值无用，在后面的程序中不再有用aTaT2 2=v vaT
14、aT1 1=T3T3B5B6优化技术优化技术4对程序进行代数恒对程序进行代数恒等变换（合并已知量）等变换（合并已知量）T1=2T2=4*T1 T1=2T2=8 优化技术优化技术4对程序进行代数恒等对程序进行代数恒等变换（降低运算强度）变换（降低运算强度）a)i*2=2*i=i+i=i2b)i/2=(int)(i*0.5)c)0-1=-1d)f*2=2.0*f=f+fe)f/2.0=f*0.5优化技术优化技术4对程序进行代数恒对程序进行代数恒等变换（代数化简）等变换（代数化简）x+0=x0+x=xx*1=x1*x=x0/x=0 x-0=xb&true=bb&false=falseb|true=t
15、rueb|false=b基本块的基本块的DAGDAG表示及其应用表示及其应用DAG Directed Acyclic Graph有向无环路图有向无环路图基本块的DAG是在结点上带有标记的DAG DAG表示了基本块的计算过程表示了基本块的计算过程 叶结点表示标识符或常数的值，以标识符或叶结点表示标识符或常数的值，以标识符或常数作为标记常数作为标记 内部结点以运算符作为标记，表示运算结果内部结点以运算符作为标记，表示运算结果 边表示了操作间的前驱和后继的关系边表示了操作间的前驱和后继的关系 每个结点：附加标识符标记，可以是一个或每个结点：附加标识符标记，可以是一个或多个标识符都具有该结点代表的值多
16、个标识符都具有该结点代表的值用用DAG进行基本块的优化进行基本块的优化(0)x=y(1)x=op y(2)x=y op z 基本块的基本块的DAGDAG构造算法构造算法:首先，DAG为空。对基本块的每一四元式，依次执行1，2，3，4步：1.如果NODE(B)无定义，则构造一标记为B的叶结点并定义NODE(B)为这个结点；如果当前四元式是0型，则记NODE(B)的值为n，转4。如果当前四元式是1型，则转2(1)。如果当前四元式是2型，则：(1)如果NODE(C)无定义，则构造一标记为C的叶结点并定义NODE(C)为这个结点；(2)转2(2)2.(1)如果NODE(B)是标记为常数的叶结点，则转2
17、(3)，否则转3(1)。(2)如果NODE(B)和NODE(C)都是标记为常数的叶结点，则转2(4)，否则转3(2)。(3)执行op B（即合并已知量），令得到的新常数为P。如果NODE(B)是处理当前四元式时新构造出来的结点，则删除它。如果NODE(P)无定义，则构造一用P做标记的叶结点n。置NODE(P)=n，转4。(4)执行B op C（即合并已知量），令得到的新常数为P。如果NODE(B)或NODE(C)是处理当前四元式时新构造出来的结点，则删除它。如果NODE(P)无定义，则构造一用P做标记的叶结点n。置NODE(P)=n，转4。3.(1)检查DAG中是否已有一结点，其唯一后继为NO
18、DE(B)，且标记为op（即找公共子表达式）。如果没有，则构造该结点n，否则就把已有的结点作为它的结点并设该结点为n，转4。(2)检查中DAG中是否已有一结点，其左后继为NODE(B)，其右后继为NODE(C)，且标记为op（即找公共子表达式）。如果没有，则构造该结点n，否则就把已有的结点作为它的结点并设该结点为n，转4。4.如果NODE(A)无定义，则把A附加在结点n上并令NODE(A)=n；否则先把A从NODE(A)结点上附加标识符集中删除（注意，如果NODE(A)是叶结点，则其标记A不删除），把A附加到新结点n上并令NODE(A)=n。转处理下一四元式。这样，就可由DAG重新生成原基本块
19、的一个优化的代码序列。例：求下列基本块的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=R-r(10)B=T5*T6(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=R-r(10)B=T5*T6(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=R-r(10
20、)B=T5*T6(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=R-r(10)B=T5*T6(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=R-r(10)B=T5*T6 DAG的应用的应用 根据DAG图，可以更进一步实现优化：合并已知量，如T1，T3 删除冗余赋值，如B的第一次赋值 公共子表达式的提取，如T2和T4 在基本块外被定值并在基本块内被引用的所有标识符，就是作
21、为叶结点上标记的那些标识符 在基本块内被定值且该值能在基本块后面被引用的所有标识符，就是DAG各结点上的那些附加标识符(1)T1=R+r(2)A=6.28*T1(3)T2=R-r(4)B=S*T2 简化后的代码序列简化后的代码序列循环：程序中可能反复执行的代码序列循环：程序中可能反复执行的代码序列,也是也是优化的重点优化的重点7.3 循环优化循环优化程序流图中结点间的关系程序流图中结点间的关系m DOM n m DOM n 定义定义 在程序流图中,对任意两个结点m和n,如果从流图的首结点出发,到达n的任意通路都要经过m,则称m是n的必经结点,记为m DOM n 每个结点是它本身的必经结点；循环
22、的入口是循环中所有结点的必经结点。必经结点集必经结点集定义定义 结点n的所有必经结点的集合,称为结点n的必经结点集,记为D(n).例：例：1 12 24 43 35 56 67 7D(1)=1D(2)=1，2D(3)=1，2，3。D(4)=1，2，4D(5)=1，2，4，5 D(6)=1，2，4，6 D(7)=1，2，4，7循环的查找算法循环的查找算法回边回边：假设：假设ab是流图中的一条有向边，如果是流图中的一条有向边，如果b DOM a，则称，则称ab是流图中的一条回边。是流图中的一条回边。循环的查找循环的查找如果有向边如果有向边ndnd是回边，组成的循环是由结点是回边，组成的循环是由结点
23、d，结，结点点 n以及有通路到达以及有通路到达n而该而该通路不经过通路不经过d的所有结点组的所有结点组成，并且成，并且d是该循环的唯一入口结点。是该循环的唯一入口结点。回边 6 6 循环6 7 4 4,5,6,7 4 2 2,3,4,5,6,7循环(结点序列的性质)1.强连通的(任意两结点间,必有一条通路,且该通路上各结点都属于该结点序列)2.它们中间有且只有一个是入口结点。1 12 24 43 35 56 67 7循环优化循环优化 循环优化的关键 哪些基本块构成一个 循环循环优化的方法 代码外提 强度削弱 删除归纳变量循环的性质循环的性质 两个循环的关系：图中任意两个循环要么是嵌套的，要么不
24、相交（可能有公共的入口结点）内循环：不包含任何其它循环的循环 如果两个自然循环有相同的首结点，且两个循环不是一个嵌在另一个里面时，可以考虑将二者合并，当成是一个循环B0B1B2B3 变量A在某点d的定值到达另一点u，是指流图中从d由一通路到达u且该通路上没有A的其他定值优化技术优化技术5代码外提代码外提 对循环中的有些代码，如果它产生的结果在循环中是不变的，可以提到循环外面while(i=limit-2).t=limit-2while(i10 goto 15(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)T
25、7=T6+T5(10)T8=addr(A)-11(11)T9=T8T7(12)T4T3=T9+1(13)I=I+1(14)goto B2(15)B1B2B3(1)I=1(2)If I10 goto 15(4)T2=10*I(5)T3=T2+T1(8)T6=10*I(9)T7=T6+T5(11)T9=T8T7(12)T4T3=T9+1(13)I=I+1(14)goto B2(15)B1B2B3(3)T1=2*J(6)T4=addr(A)-11(7)T5=2*J(10)T8=addr(A)-11优化技术优化技术6强度削弱强度削弱j=j-1j=j-1T4=4T4=4*j jT5=aT4T5=aT4i
26、f T5v goto B3if T5v goto B3T4=T4=T4-4T4-4T5=aT4T5=aT4if T5v goto B3if T5v goto B3B3J每次减1后再做乘4操作改为先赋值后，T4的计算用减法运算T4=4T4=4*j j 是指把程序中执行时间长的运算替换为执行时间较短的运算优化技术优化技术7删除归纳变量删除归纳变量 基本归纳变量：如果循环中对变量I只有唯一的形如I:=I c的赋值，c是循环不变量 归纳变量：如果I是循环中的基本归纳变量，J在循环中的赋值总是可以化为I的同一线性函数，即J:=C1*I c2。同时称J与I同族 一个基本归纳变量除用于自身的递归定值外，一般在循环中用来计算其他归纳变量及控制循环的进行，此时，可以用与它同族的某一归纳变量来控制循环的进行 删除归纳变量一般是在强度削弱以后进行的(1)i=1(2)If I10 goto 15(4)T2=10*i(5)T3=T2+T1(8)T6=10*i(9)T7=T6+T5(11)T9=T8T7(12)T4T3=T9+1(13)i=i+1(14)goto B2(15)B1B2B3(3)T1=2*j(6)T4=addr(A)-11(7)T5=2*j(10)T8=addr(A)-11删除归纳变量删除归纳变量 当进行强度削弱后，B4中i,j的比较可以使用T2,T4If T2=T4 goto B6
