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