《第十章代码优化.ppt》由会员分享，可在线阅读，更多相关《第十章代码优化.ppt（17页珍藏版）》请在三一文库上搜索。
1、1,第十章 代码优化,计算机科学与技术学院 闫健恩,2,代码优化,概述 局部优化 循环优化,3,代码优化概述,优化目的 节约时间：提高运行速度（降低运算强度） 节约空间：精简代码 优化的前提 保持原有功能，进行等价变换。 优化的方法 源程序优化：选择合理的程序结构 中间代码的优化：由编译器完成 目标代码优化：由编译器完成，与机器有关。,4,中间代码的优化 局部优化：对顺序执行语句(基本块)优化 循环优化：对循环语句优化 全局优化：对整个程序优化,代码优化概述,5,局部优化局部优化的种类,基本块：程序中一个顺序执行的语句序列。 合并已知量 例：a=1 可优化为：a=1 b=a+3 b=4 利用公
2、共子表达式 例：x=a+b+4 y=2-(a+b) y中的a+b可以使用x中已经计算出来的结果。 删除无用的赋值 例：x=2 y=3*a+9 x=y+15 这里第一个 x 的赋值没有意义。 强度削弱 X2变成x*x。 2*x或2.0*x 变成x+x,6,使用四元式进行局部优化 表达式的标准顺序：常数简单变量数组子表达式,局部优化局部优化的种类,7,基本块优化的实现,基本块内部优化的实现的主要工具为DAG图。 用DAG图表示各个值的计算/依赖关系。 图中的标记： 叶子节点的标记为标识符（变量名）或常数作为唯一的标记。叶子节点是标识符时，用下标0表示它是初值。 内部节点用运算符号作为标记，表示计算
3、的值。每个节点的值都可以用关于变量初始值的表达式表示。 各节点可能附加有一个或者多个标识符。同一个节点的标识符表示相同的值。,8,DAG图的例子,+ b c a - a d b + b c c - a d d,b0,c0,d0,b,d,a,c,9,四元式的分类,0型：= x _ y 1型：op x _ y(单目运算） 2型：op x y z relop x y z(z是序号),10,基本块DAG图构造算法,输入：一个基本块 输出：相应DAG图 算法说明： 通过逐个扫描四元式来逐步建立DAG图。 函数node(x)表示和标识符x相应的最近建立的节点。他代表扫描到当前的四元式的时候，标识符x的值对
4、应的节点。 步骤1：初始化：无任何节点，node对任何标识符无定义。 步骤2：依次对基本块中的每个四元式op x y z执行如下步骤。 如果node(x)没有定义，建立叶子节点，标记为x，让node(x) 等于这个节点。如果node(y)没有定义，为y建立节点。 如果四元式为0型，n=node(x); 如果四元式为1型，寻找标记为op且子节点为node(x)的节点，如果找不到，建立这样的节点。,11,基本块DAG图构造算法（续）,对于2型四元式，查看是否存在标记为op的节点，且其左右子节点分别为node(x)和node(y)。如果找不到，建立这样的节点。 步骤3：如果z为标识符，从node(z
5、)中删除标识符z，并把z加入到所找到或者建立的节点n的标识符表中，并设置node(z)为n。 说明： 处理2型四元式的时候，如果op是可交换的运算符，可以允许其左右节点可以互换。,12,DAG图的应用,公共子表达式：构造中，寻找是否有标记为op且子节点为node(x), node(y)的节点时，自然完成了公共子表达式的寻找。 在基本块中，其值被引用的标识符：构造了叶子节点的标识符。 结果能够在基本块外被引用的四元式op x y z。设它对应的节点为n，如果DAG图构造结束的时候，n的标志符表不为空。,13,代码优化循环优化,循环优化的种类 代码外提 强度削弱 删除归纳变量 循环展开 循环合并
6、代码外提 将循环体内不变化的四元式，提到循环的外面。 强度削弱 将乘除运算变为加减 。,14,变换循环变量 如果在循环中对变量I只有类似于I:=I+C的赋值形式，其中C是循环不变量，则称I为循环中的基本归纳变量，如果另外一个变量J也可以表示成I的线性函数：J:=aI+b，则称J为I的同族归纳变量。 可以使用与I同族的任一归纳变量替换循环变量I，然后删除I。这种优化方法就是变换循环变量。,15,循环的合并与展开 循环展开： 减少测试控制循环变量的次数， 将原来每次都测试循环变量，改变为多次后测试一次。 循环合并 将两个或多个循环合并成一个循环。 条件：循环次数相同使用同一个（族）循环变量 两个循
7、环中相同变量的操作不能产生冲突。,16,例 循环语句如下，试进行优化,for I=1 to 10 do AI,J*5=J+2 设A为10*10的数组 解：循环的结构图如右,(1) I=1,(2) If I 10 goto 11,(3) T1=J*5 (4) T2=I*10 (5) T3=T2+T1 (6) T4=addr(A)-11 (7) T5=J+2 (8) T4T3=T5 (9) I=I+1 (10) goto B2,前置节点B1,入口节点B2,循环体B3,（一）代码外提 (3)(6)(7)不发生变化 可以外提,17,（二）强度削弱 (4)可以改成T2=T2+10, 在B1中添加T2=0 (三) 变换循环变量 将T2变为循环变量，删除I (2)变为If T2 100 goto 11 删除B3中的I=I+1,