第十章代码优化哈工大王宏志.ppt
《第十章代码优化哈工大王宏志.ppt》由会员分享,可在线阅读,更多相关《第十章代码优化哈工大王宏志.ppt(117页珍藏版)》请在三一文库上搜索。
1、第十章 代码优化,优化的概念,编译时刻为改进目标程序的质量而进行的各项工作。 空间效率 时间效率 空间效率和时间效率有时是一对矛盾,有时不能兼顾。 优化的要求: 必须是等价变换 为优化的努力必须是值得的。 有时优化后的代码的效率反而会下降。,优化的分类,机器相关性: 机器相关优化:寄存器优化,多处理器优化,特殊指令优化,无用指令消除等。 无关的优化: 优化范围: 局部优化:单个基本块范围内的优化,常量合并优化,公共子表达式删除,计算强度削弱和无用代码删除。 全局优化:主要是基于循环的优化:循环不变优化,归纳变量删除,计算强度削减。 优化语言级: 优化语言级:针对中间代码,针对机器语言。,代码优
2、化程序的结构,控制流分析的主要目的是分析出程序的循环结构。循环结构中的代码的效率是整个程序的效率的关键。 数据流分析进行数据流信息的收集,主要是变量的值的获得和使用情况的数据流信息。 到达-定义分析;活跃变量;可用表达式; 代码变换:根据上面的分析,对内部中间代码进行等价变换。,控制流分析,数据流分析,代码变换,基本块和流图,基本块中,控制流是由第一个四元式进入,到达最后一个四元式离开。 流图:把一个程序的中间表示中所有的基本块作为节点集合。有边从节点n到节点n当且仅当控制流可能从n的最后的一个四元式到达n的第一个四元式。 首节点:对应的基本块的第一个四元式是程序的第一个四元式。,流图的构造,
3、以所有的基本块为节点集合。 有B1到B2的边(B2是B1的后继)当且仅当: B1的最后一个四元式有条件或无条件地转移到B2的第一个四元式。 B2是紧紧跟随在B1后面的四元式,且B1的最后四元式不是无条件转向语句。,流图的例子,在转移语句中,目标标号转变称为基本块的编号,可以避免因为四元式的变动而引起的麻烦。,= 1 _ i = 1 _ f = 0 _ a,= i 10 B4,= f _ b + f a t1 = t1 _ f = b _ a + i 1 t2 = t2 _ i GO B2,= f fib,B1,B2,B3,B4,基本块的优化,常量合并 公共子表达式删除 强度削弱 无用代码删除,
4、常量合并,例子:l = 2*3.14*r * 2 3.14 t1 * t1 r t2 = t2 l 2*3.1415926的值在编译时刻就可以确定。 * 6.28 r t2 = t2 l,公共子表达式删除,+ b c a - a d b + b c c - a d d 显然,第2和4个四元式计算的是同一个值,所以第四个四元式可以修改为 = b _ d。 对于第1和3个四元式,虽然都是计算b+c,但是他们的值其实是不同的,所以不能完成处理。 公共子表达式:如果某个表达式先前已经计算,且从上次计算到现在,E中的变量的值没有改变。那么E的这次出现就称为公共子表达式。 利用先前的计算结果,可以避免对公
5、共子表达式的重复计算。,例子,x+y*t-a*(x+y*t)/(y*t) * y t t1 + x t1 t2 * y t t3 + x t3 t4 * a t4 t5 * y t t6 / t5 t1 t7 - t2 t7 t8 消除公共子表达式之后: * y t t1 + x t1 t2 * a t2 t5 / t5 t1 t7 - t2 t7 t8,强度削弱,实现同样的运算可以有多种方式。用计算较快的运算代替较慢的运算。 X2 变成 x*x。 2*x或2.0*x 变成 x+x x/2 变成 x*0.5 anxn+an-1xn-1+a1x+a0变成 (anx+an-1)x+ an-2)x+
6、a1)x+a0,无用代码删除,如果四元式op x y z之后,z的值再也没有被使用到,那么这个四元式是无用的。 无用的四元式往往意味着程序的错误,一般不会出现在正确的程序里面。 多数无用四元式是由优化引起的。 = t1 t3,如果我们尽量用t1替代t3,可能使t3不被使用,从而这个四元式称为无用的四元式。,等价变换的分类,保结构等价变换 删除公共子表达式和删除无用代码,重新命名临时变量和交换独立四元式的顺序等。 + x y t变成+ x y u + a b t1 + x y t2变成 + x y t2 + a b t1 代数等价变换利用了代数恒等性质, 强度削弱。2x=x+x, B and t
7、rue = B. 需要考虑双目运算符的可交换特性。,基本块优化的实现,基本块内部优化的实现的主要工具为DAG图。 用DAG图表示各个值的计算/依赖关系。 图中的标记: 叶子节点的标记为标识符(变量名)或常数作为唯一的标记。叶子节点是标识符时,用下标0表示它时初值。 内部节点用运算符号作为标记,表示计算的值。每个节点的值都可以用关于变量初始值的表达式表示。 各节点可能附加有一个或者多个标识符。同一个节点的标识符表示相同的值。,DAG图的例子,+ b c a - a d b + b c c - a d d,四元式的分类,0型: = x _ y 1型: op x _ y(单目运算) 2型: op x
8、 y z relop x y z(z是序号),基本块DAG图构造算法,输入:一个基本块 输出:相应DAG图 算法说明: 通过逐个扫描四元式来逐步建立DAG图。 函数node(x)表示和标识符x相应的最近建立的节点。他代表扫描到当前的四元式的时候,标识符x的值对应的节点。 步骤1:初始化:无任何节点,node对任何标识符无定义。 步骤2:依次对基本块中的每个四元式op x y z执行如下步骤。 如果node(x)没有定义,建立叶子节点,标记为x,让node(x) 等于这个节点。如果node(y)没有定义,为y建立节点。 如果四元式为0型,n=node(x); 如果四元式为1型,寻找标记为op且子
9、节点为node(x)的节点,如果找不到,建立这样的节点n。,基本块DAG图构造算法(续),对于2型四元式,查看是否存在标记为op的节点,且其左右子节点分别为node(x)和node(y)。如果找不到,建立这样的节点n。 步骤3:如果z为标识符,从node(z)中删除标识符z,并把z加入到找到或者建立的节点n的标识符表中,并设置node(z)为n。 说明: 处理2型四元式的时候,如果op是可交换的运算符,可以允许其左右节点可以互换。,生成DAG图的例子,* 4 i t1 = a t1 t2 * 4 i t3 = b t3 t4 * t2 t4 t5 + prod t5 t6 = t6 prod
10、+ i 1 t7 = t7 i = i 20 (3),DAG图的应用,公共子表达式:构造中,寻找是否有标记为op且子节点为node(x), node(y)的节点时,自然完成了公共子表达式的寻找。 在基本块中,其值被引用的标识符:构造了叶子节点的标识符。 结果能够在基本块外被引用的四元式op x y z。设它对应的节点为n,如果DAG图构造结束的时候,n的标志符表不为空。,=和&=运算符的处理,对数组的赋值需要特别的处理,这是因为数组的下标是变量。对于数组元素的赋值可能改变数组中任何一个元素的值。 = A i t1 = A j t2 &= y t2 t2 = A i t3 Ai并不是公共子表达式
11、。 在处理对数组A的元素的赋值四元式的时候,应该注销所有以=为标记,A为左节点的节点。从而不可能在此节点的标识符表中再附上其他的标识符。 处理对指针所指空间的赋值的时候,同样要注销相应的节点。如果不能确定指针指向的范围,那么,需要注销所有的节点。,A,i,=,j,=,t1,t2,y,&=,=,从DAG图到四元式序列,在DAG图中,有些运算已经进行了合并。 如果不考虑=和&=算符,可以依照DAG图中的拓扑排序得到的次序进行。但是,有了=和&=算符之后,计算的次序必须修正。 实际上,我们可以按照各个节点生成的顺序来从DAG图生成四元式序列。,从DAG重建四元式序列算法,按照DAG图中各个节点的生成
12、次序对每个节点作如下处理: 若是叶子节点,且附加标识符表为空,不生成四元式。 若是叶子节点,标记为x,附加标识符为z,生成= x z。 若是内部节点,附加标识符为z,根据其标记op和子节点数目,生成下列4种形式的四元式。 Op不是=或者=,也不是relop,有两个子节点,生成 op x y z 如果是=或者=,生成op x y z。 如果是relop,生成 relop x y z,z是基本块序号。 只有一个子节点,生成 op x _ z。,从DAG重建四元式序列算法(续),若是内部节点,且无附加标识符,则添加一个局部于本基本块的临时性附加标识符,按照上一情况生成。 如果节点的标识符重包含多个附
13、加标识符z1,z2,zk时: 若是叶子节点,标记为z,生成一系列四元式 = z z1 = z z2 = z zn 不是叶子节点,生成四元式序列: = z z2 = z zn,使用DAG图进行优化的例子 (四元式序列),四元式序列片断: * 4 i t10 = A t10 t11 = t11 x * 4 i t12 = A t12 t13 * 4 j t14 = A t14 t15 &= t15 t13 t13 * 4 j t16 = A t16 t17 &= x t17 t17 i j B2,使用DAG图进行优化的例子 (DAG图),在第10个节点生成后, node(t11)变成无定义.,1:
14、 4,2: i,3: *,t10,4: A,t12,5:=,t11,6:=,t13,8:*,7: j,t14,9: =,t15,10:&=,t16,11:=,t17,12: &=,13: ,B2,x,从DAG图到四元式序列,* 4 i t10 (3) = A t10 t11 (5) := t11 x (5) = A t10 t13 (6) * 4 j t14 (8) = A t14 t15 (9) &= t15 t13 t13 (10) = A t14 t17 (11) &= x t17 t17 (12) i j B2 (13),DAG的其他应用,常量合并: * 2 pi t1 * t1 r
15、t2 = t2 l 无用代码删除: 对于= t10 t12,如果t12不需要使用,那么,这个四元式不需要生成。,与循环有关的优化,循环不变表达式外提。 归纳变量删除。 计算强度削弱,循环不变式(代码)外提,有些表达式位于循环之内,但是该表达式的值不随着循环的重复执行而改变,该表达式被称为循环的不变表达式。 如果按照前面讲的代码生成方案,每一次循环都讲计算一次。 如果把这个表达式提取到循环外面,该计算就只被执行一次。从而可以获得更加好的效率。,循环不变式的例子,计算半径为r的从10度到360度的扇形的面积: for(n=1; n36; n+) S:=10/360*pi*r*r*n; printf
16、(“Area is %f”, S); 显然,表达式10/360*pi*r*r中的各个量在循环过程中不改变。可以修改程序如下: C= 10/360*pi*r*r*n; for(n=1; n36; n+) S:=C*n; printf(“Area is %f”, S); 修改后的程序中,C的值只需要被计算一次,而原来的程序需要计算36次。,四元式的循环不变式,(1)= 1 n (2) n 36 (21) (3)GOF (4) (4)/ 10 360 tl (5)* tl pi t2 (6)* t2 r t3 (7)* t3 r t4 (8)* t4 n t5 (9)= t5 S (18)+ n 1
17、 t9 (19)= t9 n (20)GO (4) (21) 其中,四元式4,5,6,7是循环不变四元式。,循环不变四元式的相对性,对于多重嵌套的循环,循环不变四元式是相对于某个循环而言的。可能对于更加外层的循环,它就不是循环不变式。 例子: for(i = 1; i10; i+) for(n=1; n360/(5*i); n+) S:=(5*i)/360*pi*r*r*n;. 5*i和(5*i)/360*pi*r*r对于n的循环(内层循环)是不变表达式,但是对于外层循环,它们不是循环不变表达式。,循环不变表达式优化需要解决的问题,如何识别循环中的不变表达式? 把循环表达式外提到什么地方? 什
18、么条件下,不变表达式可以外提?,归纳变量的删除(例子),例子: Prod=0; i = 1; for(i = 1; i= 20; i+) prod += prod+A4*i*B4*i; * 4 i t1 = a t1 t2 * 4 i t3 = b t3 t4 * t2 t4 t5 + prod t5 t6 = t6 prod + i 1 t7 = t7 i = i 20 B2 i作为计数器。每次重复,i的值增加1,而Ai, Bi对应的地址t1, t3增加4。 我们可以删除i,而使用t1或者t3进行循环结束条件的测试。,归纳变量的删除,在循环中,如果变量i的值随着循环的每次重复都固定地增加或者
19、减少某个常量,则称i为循环的归纳变量。 如果在一个循环中有多个归纳变量,归纳变量的个数往往可以减少,甚至减少到1个。减少归纳变量的优化称为归纳变量的删除。,归纳变量的删除(四元式例子),= 0 prod = l i,* 4 i t1 = a t1 t2 * 4 i t3 = b t3 t4 * t2 t4 t5 + prod t5 t6 = t6 prod + i 1 t7 = t7 i = i 20 B2,= 0 prod = 0 t1,+ 4 t1 t1 + 4 t3 t3 = a t1 t2 = b t3 t4 * t2 t4 t5 + prod t5 t6 = t6 prod = t1
20、 80 B2,归纳变量的删除,归纳变量的删除一方面可以删除变量,减少四元式,另外,删除归纳变量同时也削减了计算强度。 为了进行归纳变量删除优化,必要的是找出归纳变量。,计算强度削弱,在删除归纳变量的过程中,已经将一些乘法运算转换成为加法运算。 还有一类经常可以被应用的是对于下标变量地址的计算。,计算强度削减(下标变量),对于数组T an1n2nm,其下标变量ai1i2i3im的地址计算如下: base+d;其中base为a000的地址。 d=(i1*n2+i2)*n3+i3)*nm+im)*sizeof(T); 当满足某些情况的时候,地址的计算可以使用加法来代替乘法。,下标变量计算强度的削减(
21、例子),for(v1=v10; v1v1f; v1+) for(v2=v20; v2v2f; v2+) Ai1i2i3 i1, i2, i3都可以表示成为:Ck0+Ck1*V1+Ck2*V2(k=1,2,3); Ai1i2i3的地址为base+d; d=(i1*n2*n3+i2*n3+i3); 将i1,i2,i3的表达式代入d的表达式,可以得到d=C0+C1*V1+C2*V2.,下标变量计算强度的削减(例子),显然,在上面的例子中,每次内循环d的值增加C2;每次外循环, d的值增加C1(但是V2被重置)。 显然我们可以这样计算Ai1i2i3的地址: 在循环开始的时候,设置初值d1=(base+
22、C0)+C1*V10; 在进入外层循环后,进入内存循环前,设置d2=d1+C2*V20 在内存循环,使用d2作为地址获取Ai1i2i3的值。 内存循环体每次运行结束之前,将d2的值增加C2。 每次外层循环体运行结束之前,将d1的值增加C1。 显然,对于Ai1i2i3的地址计算变成了加法运算。,下标变量计算强度的削减结果,D1 = base+C0+C1*V10; for(v1=v10; v1v1f; v1+) D2 = D1+C2*V20; for(v2=v20; v2v2f; v2+) *D2; D2+=C2; D1+= C1; ,下标地址优化计算的条件,相应的数组是常界数组:数组的上下界都是
23、常量。 下标变量中的下标表达式是循环控制变量的线性表达式。 满足上述条件的称为可优化下标变量。 在C语言中,要求循环控制变量每次循环的变动是常数。,循环优化的实现,循环结构的识别 数据流分析 代码转换,循环结构的识别,对于源程序来说,识别循环是比较方便的。但是代码的优化是针对四元式序列的,所以识别循环必须针对流图进行。 定义8.3 如果流图中,从某个初始节点出发,每一条到达节点n的路径都必须经过m,那么称m是节点n的必经节点。记为m dom n。 任何节点都是自己的必经节点。 m为n的前驱,n为m的后继。 直接必经节点:从初始节点到达n的所有路径上,节点n的最后一个必经节点称为直接必经节点。,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第十 代码 优化 哈工大 王宏志
链接地址:https://www.31doc.com/p-2262357.html