五章-代码优化课件

1、第五章代码优化5.1 局部优化5.2 循环优化第五章代码优化5.1 局部优化优化的概念代码优化 对代码进行等价变换，使得变换后的代码具有更高的时间效率和空间效率。空间效率和时间效率有时是一对矛盾，有时不能兼顾。优化要求必须是等价变换(保持功能)为优化的努力必须是值得的优化的概念代码优化机器相关性机器相关优化：寄存器优化，多处理器优化，特殊指令优化，无用指令消除等。机器无关优化：对中间代码的优化。优化范围局部优化：单个基本块范围内的优化，包括常量合并、公共子表达式删除、计算强度削弱和无用代码删除等。全局优化：主要是基于循环的优化，包括循环不变量代码外提、删除归纳变量、计算强度削弱等。优化语言级优

2、化语言级：针对中间代码，针对机器语言。代码优化的分类机器相关性代码优化的分类控制流分析的主要目的是分析出程序的循环结构。 循环结构中的代码的效率是整个程序的效率的关键。数据流分析进行数据流信息的收集，主要是变量的值 的获得和使用情况的数据流信息。到达-定义分析；活跃变量分析；可用表达式分析；代码变换：根据上面的分析，对内部中间代码进行等 价变换。控制流分析数据流分析代码变换代码优化主要完成的工作控制流分析的主要目的是分析出程序的循环结构。控制流分析数据流5.1 局部优化指基本块内的优化。基本块：是指程序（本课本中假设已经是四元式表示的程序了）中一顺序执行的语句序列，其中只有一个入口语句和一个出

3、口语句。5.1 局部优化指基本块内的优化。5.1.1 基本块的划分入口语句（1）四元式语句序列的第一个语句；（2）条件转移语句或无条件转移语句转移到的目标语句；（3）紧跟在条件转移语句后面的语句。5.1.1 基本块的划分入口语句出口语句（1）下一个入口语句的前导语句；（2）转移语句（包括其自身）；（3）停语句（包括其自身）。基本块的划分1、求出四元式程序之中各个基本块的入口语句。2、对每一入口语句，构造其所属的基本块。即由该入口语句到出口语句之间的语句序列。3、凡未被纳入某一基本块的语句，都是程序中控制流程无法到达的语句，因而也是不会被执行到的语句，可以把它们删除。出口语句(1) read (

4、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为其划分基本块。【例】有四元式代码程序如下：【例】有四元式代码程序如下：第五章-代码优化课件5.1.2 基本块的DAG表示DAG 指有向无环图（ Directed Acyclic Graph ），常用来对基本块进行优化。基本块的 DAG 是在结点上带有标记的 DAG。 叶结点 代表名字的初值，以唯一的标识符（变量名字或常数）标记。通常用x0表示变量名字x的初值。 内部结点 用运算符作为标记。 所有结点都

5、可有一个或多个附加标识符，表示这些变量具有该结点所代表的值。5.1.2 基本块的DAG表示DAG 指有向无环图（ Dir （其他四元式的 DAG 结点形式参见教材P131图5-1）DAG 结点 A BAop Bop n1 n2BCn1n2n1n3n1n2四元式A=BA=op BA= B op CA运算符标记四元式和与其对应的DAG结点形式 （其他四元式的 DAG 结点形式参见教材P131图5- 基本块 DAG 表示的构造算法 设 A=B, A=op B, A=B op C分别为第0、1、2型四元式，设函数 Node(name) 返回最近创建的关联于 name 的结点。 首先，置 DAG 为空。

6、 对基本块的每一个四元式，依次执行下列步骤： 若 Node(B) 无定义，则创建一个标记为 B 的叶结点，并令Node(B) 为这个结点； (1) 对于2型四元式，若Node(C) 无定义，再创建标记为C 的叶结点，并令 Node(C) 为这个结点。 基本块 DAG 表示的构造算法 设 A=B, A=o若 Node(B)和 Node(C)都是标记为常数的叶结点，执行B op C，令得到的新常数为p。 若Node(p) 无定义，则构造一个用 p 做标记的叶结点 n,置Node(p)=n。 若 Node(B) 或 Node(C)是处理当前语句时新构造出来的结点，则删除它。 （这一步有合并已知量的作

7、用）若 Node(B)和 Node(C)都是标记为常数的叶结点，若 Node(B) 或 Node(C)不是标记为常数的叶结点，则检查是否存在某个标记为 op 的结点，其左孩子是 Node(B) ，而右孩子是Node(C) ？ 若无，则创建这样的结点。 若有，则把已有的结点作为它的结点并且 无论有无，都令该结点为 n。（这一步有删除多余运算的作用）若 Node(B) 或 Node(C)不是标记为常数的叶结点(2)对于1型四元式若 Node(B) 是标记为常数的叶结点，则执行 op B，令得到的新常数为p. 若 Node(p)无定义，则构造一个用 p 做标记的叶结点 n，置node(p)=n。 若

8、Node(B) 是处理当前语句时新构造出来的结点，则删除它。（这一步有合并已知量的作用）(2)对于1型四元式若 Node(B) 不是标记为常数的叶结点，则检查是否存在某个标记为 op 的结点，其唯一的孩子是Node(B)？ 若无，则创建这样的结点;若有，则把已有的结点作为它的结点；并且无论有无，都令该结点为n。 （这一步有删除多余运算的作用）若 Node(B) 不是标记为常数的叶结点，则检查是否存在某若Node(A)无定义，则把A附加在叶结点n上并令Node(A)=n；否则，先从Node(A)的附加标识符集中将A删去（如果Node(A) 是叶结点，则不能将A删去），然后再把A附加到新结点n上，

9、并令Node(A)=n。（这一步有删除无用赋值的作用）若Node(A)无定义，则把A附加在叶结点n上并令Node( 基本块 DAG 表示的构造举例（P132 例5.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）T0 n13.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T6 n13.14T0T0=3.14 n1 n23.14T0T0=3.14T1=2*T0T2=R+rA=

10、T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1 n1 n23.14T0T0=3.146.28T1 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.14T 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

11、 n1 n2 n3 n4 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 n4 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 n4 n6 n5 n1 n2 n3 n43.14T0T0=3.14T1=2*

12、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 n4 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 n4 n6 n5 n7 n1 n2 n3 n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+r

13、T5=T3*T4T6=R-rB=T5*T66.28T1, T3R0r0+T2,T4*A, B, T5-T6 n6 n5 n7 n1 n2 n3 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 n2 从基本块的 DAG 表示可得到等价的基本块从下图的 DAG 可得到右边的新的基本块 （经拓扑排序及添加适当的复写语句） n8 n6 n5 n7 n1 n2 n3 n43.

14、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 表示可得到等价的基本块从下图的 DAG 从基本块的 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所作的优化合并已知量删除多余运算删除无用赋值 从

15、基本块的 DAG 表示可得到等价的基本块 比较变换前利用DAG进行基本块优化的基本思想： 首先按基本块内的四元式序列顺序将所有的四元式构造成一个DAG，然后按照构造结点的次序将DAG还原成四元式序列。注意：由于在构造DAG的同时已经做了局部优化，所以最后所得到的就是经过优化过的四元式序列。利用DAG进行基本块优化的基本思想：5.2 循环优化循环体是优化的重点控制流图具有惟一首结点的有向图。用来给出循环的定义。给出找出程序中循环的算法。5.2 循环优化循环体是优化的重点循环的定义具有唯一入口结点的强连通子图。强连通子图任意两结点间的通路上各结点属于子图。循环的查找方法见课本P138第5.2.2小

16、节！循环的定义循环的查找方法见课本P138第5.2.2小节！5.2.3 循环优化代码外提强度削弱删除归纳变量5.2.3 循环优化代码外提方法 1：代码外提将循环不变运算移到循环外。【例】 有程序如下，试对其进行优化。i = 0;while( i = 20 goto (8)(3) if i = 20 goto (8)(3) x = 4 * i(4) x = 4 * i(1) 循环不变运算的定义：P142查找循环中不变运算的算法描述：P144代码外提算法描述：P144循环不变运算的定义：P142方法 2：强度削弱把程序中执行时间较长的运算替换为执行时间较短的运算。X : = K * i + Y相关

17、计算i = i + C归纳变量（ K、C、Y 为循环不变量）改为X = X + K * C（ 设 X 的初值 = Y - K * C ）方法 2：强度削弱把程序中执行时间较长的运算替换为执行时间较(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 (

18、9)(4) x = 4 * i(5) x = x + 4(1) 方法 3: 消除归纳变量利用归纳变量相关的计算代替归纳变量的计算条件表达式的修改无用语句的删除方法 3: 消除归纳变量利用归纳变量相关的计算代替归纳变量(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

19、)(5) x = x + 4(4) x = x + 4(1) 强度削弱和删除归纳变量的算法描述： P147强度削弱和删除归纳变量的算法描述：代码优化示例本节所用的例子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 g

20、oto (9) 代码优化示例本节所用的例子if (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) 第五章-代码优化课件x=ai; (23) t11=4*i (24) x=at11ai=an; (25) t12=4*i (26) t13=4*n (27) t14=at13 (28) at12=t14an=

21、x; (29) t15=4*n (30) at15=xx=ai; (23) i = m 1j = nt1 = 4 * nv = at1i = i + 1t2 = 4 * it3 = at2if t3 v goto B3if i = j goto B6B4B3B5B6i = m 1i = i + 1B1B2j = j 1i1、删除公共子表达式、复写传播B5 x=ai; ai=aj; aj=x;t6 = 4 * ix = at6t7 = 4 * i t8 = 4 * jt9 = at8at7 = t9t10 = 4 * jat10 = xgoto B21、删除公共子表达式、复写传播t6 = 4 *

22、 iB5 x=ai; ai=aj; aj=x;t6 = 4 * ix = at6t7 = 4 * i t8 = 4 * jt9 = at8at7 = t9t10 = 4 * jat10 = xgoto B2t6 = 4 * iB5 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 * iB5 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 = at22、删除无用赋值B5 x=ai; ai=aj; aj=x;t6 = 4 * ix = at6t7 = 4 * i t8 = 4 * jt9 =