第五章-代码优化课件

第五章代码优化5.1 局部优化局部优化5.2 循环优化循环优化第五章代码优化5.1 局部优化1优化的概念优化的概念v代码优化代码优化 对代码进行等价变换，使得变换后的代码具有更高对代码进行等价变换，使得变换后的代码具有更高的时间效率和空间效率。的时间效率和空间效率。v空间效率和时间效率有时是一对矛盾，有时不能兼空间效率和时间效率有时是一对矛盾，有时不能兼顾。顾。v优化要求优化要求必须是等价变换必须是等价变换(保持功能保持功能)为优化的努力必须是值得的为优化的努力必须是值得的优化的概念代码优化2v机器相关性机器相关性机器相关优化：寄存器优化，多处理器优化，特殊指机器相关优化：寄存器优化，多处理器优化，特殊指令优化，无用指令消除等。令优化，无用指令消除等。机器无关优化：对中间代码的优化。机器无关优化：对中间代码的优化。v优化范围优化范围局部优化：单个局部优化：单个基本块基本块范围内的优化，包括常量合并、范围内的优化，包括常量合并、公共子表达式删除、计算强度削弱和无用代码删除等。公共子表达式删除、计算强度削弱和无用代码删除等。全局优化：主要是全局优化：主要是基于循环基于循环的优化，包括循环不变量的优化，包括循环不变量代码外提、删除归纳变量、计算强度削弱等。代码外提、删除归纳变量、计算强度削弱等。v优化语言级优化语言级优化语言级：针对中间代码，针对机器语言。优化语言级：针对中间代码，针对机器语言。代码优化的分类代码优化的分类机器相关性代码优化的分类3v控制流分析控制流分析的主要目的是分析出程序的循环结构。的主要目的是分析出程序的循环结构。循环结构中的代码的效率是整个程序的效率的关键。循环结构中的代码的效率是整个程序的效率的关键。v数据流分析数据流分析进行数据流信息的收集，主要是变量的值进行数据流信息的收集，主要是变量的值 的获得和使用情况的数据流信息。的获得和使用情况的数据流信息。到达到达-定义分析；活跃变量分析；可用表达式分析；定义分析；活跃变量分析；可用表达式分析；v代码变换代码变换：根据上面的分析，对内部中间代码进行等：根据上面的分析，对内部中间代码进行等 价变换。价变换。控制流分析控制流分析数据流分析数据流分析代码变换代码变换代码优化主要完成的工作代码优化主要完成的工作控制流分析的主要目的是分析出程序的循环结构。控制流分析数据流45.1 局部优化局部优化v指基本块内的优化。指基本块内的优化。v基本块：基本块：是指程序（本课本中假设已经是四是指程序（本课本中假设已经是四元式表示的程序了）中一顺序执行的语句序元式表示的程序了）中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。列，其中只有一个入口语句和一个出口语句。5.1 局部优化指基本块内的优化。55.1.1 基本块的划分基本块的划分v入口语句入口语句（1）四元式语句序列的第一个语句；）四元式语句序列的第一个语句；（2）条件转移语句或无条件转移语句转移到的）条件转移语句或无条件转移语句转移到的目标语句；目标语句；（3）紧跟在条件转移语句后面的语句。）紧跟在条件转移语句后面的语句。5.1.1 基本块的划分入口语句6v出口语句出口语句（1）下一个入口语句的前导语句；）下一个入口语句的前导语句；（2）转移语句（包括其自身）；）转移语句（包括其自身）；（3）停语句（包括其自身）。）停语句（包括其自身）。v基本块的划分基本块的划分1、求出四元式程序之中各个基本块的入口语句。、求出四元式程序之中各个基本块的入口语句。2、对每一入口语句，构造其所属的基本块。即由该、对每一入口语句，构造其所属的基本块。即由该入口语句到出口语句之间的语句序列。入口语句到出口语句之间的语句序列。3、凡未被纳入某一基本块的语句，都是程序中控制、凡未被纳入某一基本块的语句，都是程序中控制流程无法到达的语句，因而也是不会被执行到的流程无法到达的语句，因而也是不会被执行到的语句，可以把它们删除。语句，可以把它们删除。出口语句7(1)read(C)(2)A=0(3)B=1(4)L1:A=A+B(5)if B=C goto L2(6)B=B+1(7)goto L1(8)L2:write(A)(9)halt为其划分基本块。为其划分基本块。【例】有四元式代码程序如下：【例】有四元式代码程序如下：【例】有四元式代码程序如下：8第五章-代码优化课件95.1.2 基本块的基本块的DAG表示表示vDAG 指有向无环图（指有向无环图（Directed Acyclic Graph），常），常用来对基本块进行优化。用来对基本块进行优化。v基本块的基本块的 DAG 是是在结点上带有标记在结点上带有标记的的 DAG。叶结点叶结点 代表名字的初值，以唯一的标识符（变量名代表名字的初值，以唯一的标识符（变量名字或常数）标记。通常用字或常数）标记。通常用x0表示变量名字表示变量名字x的初值。的初值。内部结点内部结点 用运算符作为标记。用运算符作为标记。所有结点所有结点都可有都可有一个或多个一个或多个附加标识符，表示这些附加标识符，表示这些变量具有该结点所代表的值。变量具有该结点所代表的值。5.1.2 基本块的DAG表示DAG 指有向无环图（Dir10 （其他四元式的其他四元式的 DAG 结点形式参见教材结点形式参见教材P131图图5-1）DAG 结点结点 A BAop Bop n1 n2BCn1n2n1n3n1n2四元式四元式A=BA=op BA=B op CA运算符标记运算符标记四元式和与其对应的四元式和与其对应的DAGDAG结点形式结点形式 （其他四元式的 DAG 结点形式参见教材P131图5-11 基本块基本块 DAG 表示的构造算法表示的构造算法 设设 A=B,A=op B,A=B op C分别为第分别为第0、1、2型四元式，设型四元式，设函数函数 Node(name)返回最近创建的关联于返回最近创建的关联于 name 的结点。的结点。首先，置首先，置 DAG 为空。为空。对基本块的每一个四元式，依次执行下列步骤：对基本块的每一个四元式，依次执行下列步骤：v若若 Node(B)无定义，则创建一个标记为无定义，则创建一个标记为 B 的叶结点，并令的叶结点，并令Node(B)为这个结点；为这个结点；(1)对于对于2型四元式型四元式，v若若Node(C)无定义，再创建标记为无定义，再创建标记为C 的叶结点，并令的叶结点，并令 Node(C)为这个结点。为这个结点。基本块 DAG 表示的构造算法 设 A=B,A=o12v若若 Node(B)和和 Node(C)都是标记为常数的叶结点，都是标记为常数的叶结点，执行执行B op C，令得到的新常数为，令得到的新常数为p。若若Node(p)无定义，则构造一个用无定义，则构造一个用 p 做标记的叶结做标记的叶结点点 n,置置Node(p)=n。若若 Node(B)或或 Node(C)是处是处理当前语句时新构造出来的结点，则删除它。理当前语句时新构造出来的结点，则删除它。（这一步有（这一步有合并已知量合并已知量的作用）的作用）若 Node(B)和 Node(C)都是标记为常数的叶结点，13v若若 Node(B)或或 Node(C)不是标记为常数的叶结点，不是标记为常数的叶结点，则检查是否存在某个标记为则检查是否存在某个标记为 op 的结点，其左孩的结点，其左孩子是子是 Node(B)，而右孩子是，而右孩子是Node(C)？若无，则创建这样的结点。若无，则创建这样的结点。若有，则把已有的结点作为它的结点并且若有，则把已有的结点作为它的结点并且 无论有无，都令该结点为无论有无，都令该结点为 n。（这一步有（这一步有删除多余运算删除多余运算的作用）的作用）若 Node(B)或 Node(C)不是标记为常数的叶结点14(2)对于对于1型四元式型四元式v若若 Node(B)是标记为常数的叶结点，则执行是标记为常数的叶结点，则执行 op B，令得到的新常数为，令得到的新常数为p.若若 Node(p)无定义，则无定义，则构造一个用构造一个用 p 做标记的叶结点做标记的叶结点 n，置，置node(p)=n。若若Node(B)是处理当前语句时新构造出来的结点，是处理当前语句时新构造出来的结点，则删除它。（这一步有则删除它。（这一步有合并已知量合并已知量的作用）的作用）(2)对于1型四元式15v若若 Node(B)不是标记为常数的叶结点，则不是标记为常数的叶结点，则检查是否存在某个标记为检查是否存在某个标记为 op 的结点，其的结点，其唯一的孩子是唯一的孩子是Node(B)？若无，则创建这样的结点若无，则创建这样的结点;若有，则把已有若有，则把已有的结点作为它的结点；并且无论有无，都的结点作为它的结点；并且无论有无，都令该结点为令该结点为n。（这一步有（这一步有删除多余运算删除多余运算的作用）的作用）若 Node(B)不是标记为常数的叶结点，则检查是否存在某16v若若Node(A)无定义，则把无定义，则把A附加在叶结点附加在叶结点n上上并令并令Node(A)=n；否则，先从；否则，先从Node(A)的附的附加标识符集中将加标识符集中将A删去（如果删去（如果Node(A)是叶是叶结点，则不能将结点，则不能将A删去），然后再把删去），然后再把A附加到附加到新结点新结点n上，并令上，并令Node(A)=n。（这一步有（这一步有删除无用赋值删除无用赋值的作用）的作用）若Node(A)无定义，则把A附加在叶结点n上并令Node(17 基本块基本块 DAG 表示的构造举例表示的构造举例（P132 例例5.15.1）T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T6 基本块 DAG 表示的构造举例（P132 例5.1）T018 n13.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T6 n13.14T0T0=3.1419 n1 n23.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1 n1 n23.14T0T0=3.146.28T120 n5 n1 n2 n3 n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1R0r0+T2 n5 n1 n2 n3 n43.14T21 n6 n5 n1 n2 n3 n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1R0r0+T2*A n6 n5 n1 n2 n3 n422 n6 n5 n1 n2 n3 n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1R0r0+T2*A,B n6 n5 n1 n2 n3 n423 n6 n5 n1 n2 n3 n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1,T3R0r0+T2*A,B n6 n5 n1 n2 n3 n424 n6 n5 n1 n2 n3 n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1,T3R0r0+T2,T4*A,B n6 n5 n1 n2 n3 n425 n6 n5 n1 n2 n3 n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1,T3R0r0+T2,T4*A,B,T5 n6 n5 n1 n2 n3 n426 n6 n5 n7 n1 n2 n3 n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1,T3R0r0+T2,T4*A,B,T5-T6 n6 n5 n7 n1 n2 n327 n8 n6 n5 n7 n1 n2 n3 n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1,T3R0r0+T2,T4*A,T5-T6*B n8 n6 n5 n7 n1 n228 从基本块的从基本块的 DAG 表示可得到等价的基本块表示可得到等价的基本块-从下图的从下图的 DAG 可得到右边的新的基本块可得到右边的新的基本块 （经拓扑排序及添加适当的复写语句）（经拓扑排序及添加适当的复写语句）n8 n6 n5 n7 n1 n2 n3 n43.14T0T0=3.14T1=6.28T3=6.28T2=R+rT4=T2A=6.28*T2T5=AT6=R-rB=A*T66.28T1,T3R0r0+T2,T4*A,T5-T6*B 从基本块的 DAG 表示可得到等价的基本块从下图的 DAG29 从基本块的从基本块的 DAG 表示可得到等价的基本块表示可得到等价的基本块-比较变换前后的基本块比较变换前后的基本块T0=3.14T1=6.28T3=6.28T2=R+rT4=T2A=6.28*T2T5=AT6=R-rB=A*T6T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T6所作的优化所作的优化合并已知量合并已知量删除多余运算删除多余运算删除无用赋值删除无用赋值 从基本块的 DAG 表示可得到等价的基本块 比较变换前30v利用利用DAG进行基本块优化的进行基本块优化的基本思想基本思想：首先按基本块内的四元式序列顺序将所有的首先按基本块内的四元式序列顺序将所有的四元式构造成一个四元式构造成一个DAG，然后按照构造结点，然后按照构造结点的次序将的次序将DAG还原成四元式序列。还原成四元式序列。v注意：注意：由于在构造由于在构造DAG的同时已经做了局部的同时已经做了局部优化，所以最后所得到的就是经过优化过的优化，所以最后所得到的就是经过优化过的四元式序列。四元式序列。利用DAG进行基本块优化的基本思想：315.2 5.2 循环优化循环优化v循环体是优化的重点循环体是优化的重点v控制流图控制流图具有惟一具有惟一首结点首结点的有向图。的有向图。用来给出循环的定义。用来给出循环的定义。给出找出程序中循环的算法。给出找出程序中循环的算法。5.2 循环优化循环体是优化的重点32v循环的定义循环的定义具有唯一入口结点的强连通子图。具有唯一入口结点的强连通子图。v强连通子图强连通子图任意两结点间的通路上各结点属于子图。任意两结点间的通路上各结点属于子图。循环的查找方法见课本P138第5.2.2小节！循环的定义循环的查找方法见课本P138第5.2.2小节！335.2.3 循环优化循环优化v代码外提代码外提v强度削弱强度削弱v删除归纳变量删除归纳变量5.2.3 循环优化代码外提34方法方法 1：代码外提：代码外提v将将循环不变运算循环不变运算移到循环外。移到循环外。【例】【例】有程序如下，试对其进行优化。有程序如下，试对其进行优化。i=0;while(i=20 goto(8)(3)if i=20 goto(8)(3)x=4*i(4)x=4*i(1)36v循环不变运算的定义：循环不变运算的定义：P142v查找循环中不变运算的算法描述：查找循环中不变运算的算法描述：P144v代码外提算法描述：代码外提算法描述：P144循环不变运算的定义：P14237方法方法 2：强度削弱：强度削弱v把程序中执行时间较长的运算替把程序中执行时间较长的运算替换为执行时间较短的运算。换为执行时间较短的运算。X:=K*i+Y相关计算相关计算i=i+C归纳变量归纳变量（K、C、Y 为循环不变量）为循环不变量）改为改为X=X+K*C（设设 X 的初值的初值=Y-K*C）方法 2：强度削弱把程序中执行时间较长的运算替换为执行时间较38(4)x=4*i(5)i=i+1(6)y=t1+x(7)goto(3)(5)x=x+4(6)i=i+1(7)y=t1+x(8)goto(4)(1)i=0(2)t1=z*6(1)i=0(2)t1=z*6(3)x=-4(3)if i=20 goto(8)(4)if i=20 goto(9)(4)x=4*i(5)x=x+4(1)39方法方法 3:消除归纳变量消除归纳变量v利用利用归纳变量归纳变量相关的计算相关的计算代替代替归纳变量归纳变量的计算的计算条件表达式的修改条件表达式的修改无用语句的删除无用语句的删除方法 3:消除归纳变量利用归纳变量相关的计算代替归纳变量40(5)x=x+4(6)i=i+1(7)y=t1+x(8)goto(4)(4)x=x+4(5)y=t1+x(6)goto(3)(1)i=0(2)t1=z*6(3)x=-4(1)t1=z*6(2)x=-4(4)if i=20 goto(9)(3)if x=76 goto(7)(5)x=x+4(4)x=x+4(1)41v强度削弱和删除归纳变量的算法描述：强度削弱和删除归纳变量的算法描述：P147强度削弱和删除归纳变量的算法描述：42代码优化示例代码优化示例本节所用的例子本节所用的例子i=m 1;(1)i=m 1 j=n;(2)j=n v=an;(3)t1=4*n (4)v=at1while(1)do i=i+1;while(aiv);(5)i=i+1 (6)t2=4*i (7)t3=at2 (8)if t3v);(9)j=j 1 (10)t4=4*j (11)t5=at4 (12)if t5v goto(9)代码优化示例本节所用的例子43if(i=j)break;(13)if i=j goto(23)x=ai;(14)t6=4*i (15)x=at6ai=aj;(16)t7=4*i (17)t8=4*j (18)t9=at8 (19)at7=t9 aj=x;(20)t10=4*j (21)at10=x (22)goto(5)第五章-代码优化课件44x=ai;(23)t11=4*i (24)x=at11ai=an;(25)t12=4*i (26)t13=4*n (27)t14=at13 (28)at12=t14an=x;(29)t15=4*n (30)at15=xx=ai;(23)45i=m 1j=nt1=4*nv=at1i=i+1t2=4*it3=at2if t3 v goto B3if i=j goto B6B4B3B5B6i=m 1i=i+1B1B2j=j 1i461、删除公共子表达式、复写传播、删除公共子表达式、复写传播B5 x=ai;ai=aj;aj=x;t6=4*ix=at6t7=4*i t8=4*jt9=at8at7=t9t10=4*jat10=xgoto B21、删除公共子表达式、复写传播t6=4*i47B5 x=ai;ai=aj;aj=x;t6=4*ix=at6t7=4*i t8=4*jt9=at8at7=t9t10=4*jat10=xgoto B2t6=4*i48B5 x=ai;ai=aj;aj=x;t6=4*ix=at6t7=4*i t8=4*jt9=at8at7=t9t10=4*jat10=xgoto B2t6=4*ix=at6t8=4*jt9=at8at6=t9at8=xgoto B2t6=4*it6=4*i49B5 x=ai;ai=aj;aj=x;t6=4*ix=at6t7=4*i t8=4*jt9=at8at7=t9t10=4*jat10=xgoto B2t6=4*ix=at6t8=4*jt9=at8at6=t9at8=xgoto B2x=at2t9=at4at2=t9at4=xgoto B2t6=4*it6=4*ix=at2502、删除无用赋值、删除无用赋值B5 x=ai;ai=aj;aj=x;t6=4*ix=at6t7=4*i t8=4*jt9=at8at7=t9t10=4*jat10=xgoto B2t6=4*ix=at6t8=4*jt9=at8at6=t9at8=xgoto B2x=at2t9=at4at2=t9at4=xgoto B2x=t3at2=t5at4=xgoto B2at2=t5at4=t3goto B22、删除无用赋值t6=4*it6=4*ix 51类似的，类似的，B6 x=ai;ai=an;an=x;t11=4*ix=at11t12=4*i t13=4*nt14=at13at12=t14t15=4*n at15=x at2=vat1=t3 类似的，t11=4*iat2=v52i=m 1j=nt1=4*nv=at1i=i+1t2=4*it3=at2if t3 v goto B2B1B2j=j 1t4=4*jt5=at4if t5 v goto B3if i=j goto B6B4B3B5B6i=m 1i=i+1B1B2j=j 1i53v然后，可以对循环然后，可以对循环B2和和B3进行进行(代码外提）代码外提）、强度削弱强度削弱的优化。的优化。i=i+1t2=t2+4t3=at2if t3v goto B3 B3:t2=4*it4=4*jB2:然后，可以对循环B2和B3进行(代码外提）、强度削弱的优化。54v最后，可以对循环最后，可以对循环B2和和B3进行进行删除归纳变删除归纳变量量的优化。的优化。i=i+1t2=t2+4t3=at2if t3v goto B3 B3:t2=4*it4=4*jB2:最后，可以对循环B2和B3进行删除归纳变量的优化。i=i+155本章结束，谢谢！本章结束，谢谢！本章结束，谢谢！56