第十章代码优化哈工大王宏志_英语_高中教育_教育专区。第十章 代码优化 优化的概念 编译时刻为改进目标程序的质量而进行的各项工 作。 空间效率 时间效率 空间效率和时间效率有时是一对矛盾，有时不能 兼顾。 优化的要求： 必须是等价变换

　　第十章 代码优化 优化的概念 编译时刻为改进目标程序的质量而进行的各项工 作。 空间效率 时间效率 空间效率和时间效率有时是一对矛盾，有时不能 兼顾。 优化的要求： 必须是等价变换 为优化的努力必须是值得的。 有时优化后的代码的效率反而会下降。 优化的分类 机器相关性： 机器相关优化：寄存器优化，多处理器优化，特殊 指令优化，无用指令消除等。 无关的优化： 优化范围： 局部优化：单个基本块范围内的优化，常量合并优 化，公共子表达式删除，计算强度削弱和无用代码 删除。 全局优化：主要是基于循环的优化：循环不变优化， 归纳变量删除，计算强度削减。 优化语言级： 优化语言级：针对中间代码，针对机器语言。 代码优化程序的结构 控制流分析 数据流分析 代码变换 控制流分析的主要目的是分析出程序的循环结 构。循环结构中的代码的效率是整个程序的效 率的关键。 数据流分析进行数据流信息的收集，主要是变 量的值的获得和使用情况的数据流信息。 到达-定义分析；活跃变量；可用表达式； 代码变换：根据上面的分析，对内部中间 代码进行等价变换。 基本块和流图 基本块中，控制流是由个四元式进 入，到达后一个四元式离开。 流图：把一个程序的中间表示中所有的 基本块作为节点集合。有边从节点n到节 点n’当且仅当控制流可能从n的后的一 个四元式到达n’的个四元式。 首节点：对应的基本块的个四元式 是程序的个四元式。 流图的构造 以所有的基本块为节点集合。 有B1到B2的边（B2是B1的后继）当且 仅当： B1的后一个四元式有条件或无条件地转 移到B2的个四元式。 B2是紧紧跟随在B1后面的四元式，且B1的 后四元式不是无条件转向语句。 流图的例子 B1 = 1 _ i = 1 _ f = 0 _ a B2 = i 10 B4 B3 = f _ b + f a t1 = t1 _ f = b _ a + i 1 t2 = t2 _ i GO B2 B4 =f fib 在转移语句中，目标标号转变称为基本块的编号， 可以避免因为四元式的变动而引起的麻烦。 基本块的优化 常量合并 公共子表达式删除 强度削弱 无用代码删除 常量合并 例子：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 - adb + b c c - add 显然，第2和4个四元式计算的是同一个值，所以第四个四元式 可以修改为 =b _ d。 对于和3个四元式，虽然都是计算b+c，但是他们的值其实 是不同的，所以不能完成处理。 公共子表达式：如果某个表达式先前已经计算，且从上次计算 到现在，E中的变量的值没有改变。那么E的这次出现就称为公 共子表达式。 利用先前的计算结果，可以避免对公共子表达式的重复计算。 例子 x+y*t-a*(x+y*t)/(y*t) * y t t1 + * y t t3 + * a t4 t5 * / t5 t1 t7 - 消除公共子表达式之后： * y t t1 + * a t2 t5 / - t2 t7 t8 x t1 t2 x t3 t4 y t t6 t2 t7 t8 x t1 t2 t5 t1 t7 强度削弱 实现同样的运算可以有多种方式。用计算 较快的运算代替较慢的运算。 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+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 true = B. 需要考虑双目运算符的可交换特性。 基本块优化的实现 基本块内部优化的实现的主要工具为DAG图。 用DAG图表示各个值的计算/依赖关系。 图中的标记： 叶子节点的标记为标识符（变量名）或常数作为的标 记。叶子节点是标识符时，用下标0表示它时初值。 内部节点用运算符号作为标记，表示计算的值。每个节点 的值都可以用关于变量初始值的表达式表示。 各节点可能附加有一个或者多个标识符。同一个节点的标 识符表示相同的值。 DAG图的例子 + b c a - a d b + b c c - a d d b0 + - b,d +a d0 c0 四元式的分类 0型： = x _ y 1型： op x _ y(单目运算） 2型： op x 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且子节点为node(x)的节点， 基本块DAG图构造算法（续） 对于2型四元式，查看是否存在标记为op的节点，且其左 右子节点分别为node(x)和node(y)。如果找不到，建立 这样的节点n。 步骤3：如果z为标识符，从node(z)中删除标识符z，并把z加 入到找到或者建立的节点n的标识符表中，并设置node(z)为 n。 说明： 处理2型四元式的时候，如果op是可交换的运算符， 可以允许其左右节点可以互换。 DAG图的应用 公共子表达式：构造中，寻找是否有标记为op 且子节点为node(x), node(y)的节点时，自 然完成了公共子表达式的寻找。 在基本块中，其值被引用的标识符：构造了叶 子节点的标识符。 结果能够在基本块外被引用的四元式op x y z。 设它对应的节点为n，如果DAG图构造结束的 时候，n的标志符表不为空。 []=和&=运算符的处理 &= t1 =[] []= t2 =[] A i j y 对数组的赋值需要特别的处理，这是因为数组的下标是变量。 对于数组元素的赋值可能改变数组中任何一个元素的值。 =[] A i t1 []= A j t2 &= y t2 t2 =[] A i t3 A[i]并不是公共子表达式。 在处理对数组A的元素的赋值四元式的时候，应该注销所有以 =[]为标记，A为左节点的节点。从而不可能在此节点的标识 符表中再附上其他的标识符。 处理对指针所指空间的赋值的时候，同样要注销相应的节点。 如果不能确定指针指向的范围，那么，需要注销所有的节点。 从DAG图到四元式序列 在DAG图中，有些运算已经进行了合并。 如果不考虑[]=和&=算符，可以依照 DAG图中的拓扑排序得到的次序进行。 但是，有了[]=和&=算符之后，计算的 次序必须修正。 实际上，我们可以按照各个节点生成的 顺序来从DAG图生成四元式序列。 从DAG重建四元式序列算法 按照DAG图中各个节点的生成次序对每个节点作如下处理： 若是叶子节点，且附加标识符表为空，不生成四元式。 若是叶子节点，标记为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重建四元式序列算法 (续) 若是内部节点，且无附加标识符，则添加一个局部于本基本 块的临时性附加标识符，按照上一情况生成。 如果节点的标识符重包含多个附加标识符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 B2 t17 t17 i j 使用DAG图进行优化的例子 (DAG图) 在0个节点生成后, node(t11)变成无定义. 10:&= 13: B2 12: &= 5:=[] t11 x 6:[]= t13 9: =[] t15 11:[]= t17 3: * t10 t12 4: A 1: 4 2: i 8:* t14 t16 7: j 从DAG图到四元式序列 * =[] := []= * =[] &= []= &= 4i t10 (3) A t10 t11 (5) t11 x (5) A t10 t13 (6) 4j 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 * r0 2 pi * t1 r t2 = t2 l 无用代码删除: 对于= t10 t12，如果t12不需要 使用，那么，这个四元式不需要 生成。 与循环有关的优化 循环不变表达式外提。 归纳变量删除。 计算强度削弱 循环不变式（代码）外提 有些表达式位于循环之内，但是该表达 式的值不随着循环的重复执行而改变， 该表达式被称为循环的不变表达式。 如果按照前面讲的代码生成方案，每一 次循环都讲计算一次。 如果把这个表达式提取到循环外面，该 计算就只被执行一次。从而可以获得更 加好的效率。 循环不变式的例子 计算半径为r的从10度到360度的扇形的面积： for(n=1; n36; n++) {S:=10/360*pi*r*r*n; printf(“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 (3)GOF (4) (4)/ 10 (5)* tl pi t2 (6)* t2 (7)* t3 r t4 (8)* t4 (9)= t5 S … … (18)+ n 1 t9 (19)= t9 (20)GO (4) (21) 其中，四元式4,5,6,7是循环不变四元式。 (21) 360 tl r t3 n t5 … … n 循环不变四元式的相对性 对于多重嵌套的循环，循环不变四元式是相对于某个 循环而言的。可能对于更加外层的循环，它就不是循 环不变式。 例子： 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的循环（内层循环）是 不变表达式，但是对于外层循环，它们不是循环不变 表达式。 循环不变表达式优化需要 解决的问题 如何识别循环中的不变表达式？ 把循环表达式外提到什么地方？ 什么条件下，不变表达式可以外提？ 归纳变量的删除（例子） 例子： Prod=0; i = 1; for(i = 1; i= 20; i++) prod += prod+A[4*i]*B[4*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，而A[i], B[i]对应的地址t1, t3增加4。 我们可以删除i，而使用t1或者t3进行循环结束条件的测试。 归纳变量的删除 在循环中，如果变量i的值随着循环的每 次重复都固定地增加或者减少某个常量， 则称i为循环的归纳变量。 如果在一个循环中有多个归纳变量，归 纳变量的个数往往可以减少，甚至减少 到1个。减少归纳变量的优化称为归纳变 量的删除。 归纳变量的删除（四元式例子） =0 prod =0 prod =l i =0 t1 *4i t1 =[] a t1 t2 *4i t3 =[] b t3 t4 * t2 t4 t5 + prod t5 t6 = t6 prod +i 1 t7 = t7 i = i 20 B2 + 4 t1 t1 + 4 t3 t3 =[] a t1 t2 =[] b t3 t4 * t2 t4 t5 + prod t5 t6 = t6 prod = t1 80 B2 归纳变量的删除 归纳变量的删除一方面可以删除变量， 减少四元式，另外，删除归纳变量同时 也削减了计算强度。 为了进行归纳变量删除优化，必要的是 找出归纳变量。 计算强度削弱 在删除归纳变量的过程中,已经将一些乘 法运算转换成为加法运算。 还有一类经常可以被应用的是对于下标 变量地址的计算。 计算强度削减（下标变量） 对于数组T a[n1][n2]…[nm]，其下标变量 a[i1][i2][i3]…[im]的地址计算如下： base+d；其中base为a[0][0]…[0]的地址。 d=((…((i1*n2+i2)*n3+i3)…)*nm+im)*sizeof( T); 当满足某些情况的时候，地址的计算可以使用 加法来代替乘法。 下标变量计算强度的削减（例子） for(v1=v10; v1v1f; v1++) for(v2=v20; v2v2f; v2++) {… A[i1][i2][i3]…} i1, i2, i3都可以表示成为： Ck0+Ck1*V1+Ck2*V2(k=1,2,3); A[i1][i2][i3]的地址为base+d; d=(i1*n2*n3+i2*n3+i3); 将i1,i2,i3的表达式代入d的表达式，可以得到 d=C0’+C1’*V1+C2’*V2. 下标变量计算强度的削减（例子） 显然，在上面的例子中，每次内循环d的值增加C2’； 每次外循环, d的值增加C1’（但是V2被重置）。 显然我们可以这样计算A[i1][i2][i3]的地址： 在循环开始的时候，设置初值d1=(base+C0’)+C1’*V10; 在进入外层循环后，进入内存循环前，设置 d2=d1+C2’*V20 在内存循环，使用d2作为地址获取A[i1][i2][i3]的值。 内存循环体每次运行结束之前，将d2的值增加C2’。 每次外层循环体运行结束之前，将d1的值增加C1’。 显然，对于A[i1][i2][i3]的地址计算变成了加法运算。 下标变量计算强度的削减结果 D1 = base+C0+C1’*V10; for(v1=v10; v1v1f; v1++) { D2 = D1+C2’*V20; for(v2=v20; v2v2f; v2++) { … *D2…; D2+=C2’;} D1+= C1’; } 下标地址优化计算的条件 相应的数组是常界数组：数组的上下界 都是常量。 下标变量中的下标表达式是循环控制变 量的线性表达式。 满足上述条件的称为可优化下标变量。 在C语言中，要求循环控制变量每次循环 的变动是常数。 循环优化的实现 循环结构的识别 数据流分析 代码转换 循环结构的识别 对于源程序来说，识别循环是比较方便的。但是代码 的优化是针对四元式序列的，所以识别循环必须针对 流图进行。 定义8.3 如果流图中，从某个初始节点出发，每一 条到达节点n的路径都必须经过m，那么称m是节点n 的必经节点。记为m dom n。 任何节点都是自己的必经节点。 m为n的前驱，n为m的后继。 直接必经节点：从初始节点到达n的所有路径上，节点 n的后一个必经节点称为直接必经节点。 循环满足的条件 循环必须有的入口节点，称为首节点。 对于循环中任何一个节点，必定至少有一个 路径回到首节点。 回边和自然循环 定义8.4 假定流图中存在两个节点M和N满 足M dom N。如果存在从节点N到M的有 向边N-M，那么这条边称为回边。 定义8.5 在流图中，给定一个回边N-M， 对应与这个回边的自然循环为：M，以及所 有可以不经过M而到达N的节点。M为该循 环的首节点。 用节点的集合表示自然循环。 自然循环的例子 1 3 dom 4 回边4-3 4 dom 7 回边7-4 10-7的自然循 环{7，8，10} 7-4的自然循环 {4,5,6,7,8,10} 4-3，8-3的自 然循环 {3,4,5,6,7,8,10} 2 3 4 5 6 7 8 9 10 回边寻找算法 首先列出所有从首节点开始，不带圈的 路径。 节点N的必经节点的集合为满足以下条 件的节点M： 所有包含N的路径P, M都在N的前面出现。 回边集合如下： {N--M N是一个节点，M在N的必经节 点集合中} 寻找自然循环的算法 输入:回边{N-M}; 输出: 回边对应的自然循环. 算法: 设置loop={N,M}; push(stack, N); while non-empty(stack) do {m = top(stack); pop(stack); for m的每个前驱节点p {if p is_not_in loop then {loop += p; push(stack,p);} } 算法的说明 节点M在初始时刻已经在loop中所以, M的前驱不可能被加入到loop中。 如果N-M不是回边，那么，首节点会 被加入到loop中。此时算法不能得到自 然循环。 相关概念 通常，循环互不相交，或者一个在另外一个里面。 内循环：不包含其他循环的循环称为内循环。 如果两个循环具有相同的首节点，那么很难说一个包 含另外一个。此时把两个循环合并。 B0 B1 B2 B3 可归约流图 可归约流图：删除了其中回边之后， 可以构成无环有向图的流图。 B1 特性：不存在循环外向循环内部 的转移，进入循环必须通过其首 节点。 B2 B3 实际的程序对应的流图一般都是可 归约的流图。 没有goto语句的结构化程序的流 图总是可归约的。一般使用goto 语句的程序也是可归约的。 数据流分析相关概念 变量获得值的方式： 通过赋值语句； 通过输入语句； 通过过程形式参数； 点：流图基本块中的位置，包括：个四元式之前，两 个相邻四元式之间，和后的四元式之间。 定值：使变量x获得值的四元式称为对x的定值，一般用四 元式的位置表示。 引用点：引用某个变量x的四元式的位置称为x的引用点。 数据流分析的种类 到达-定义数据流方程 活跃变量数据流方程 可用表达式数据流方程 到达-定义数据流方程 到达-定义：假定x有定义d，如果存在一个路径，从紧 随d的点到达某点p，并且此路径上面没有被注销，则 称x的定义d到达p。这表明，在p点使用变量x的时候， x的值可能是由d点赋予的。 引用-定义链：设变量x有一个引用点u，变量x的所有 能过到达u的一切定义称为x在u点处的引用-定义链， 简称ud链。 显然，通过变量x在引用点u的ud链，可以判断x是否 循环不变的。 到达定义数据流方程（记号） IN[B]: 表示基本块B的入口点处各个变量的定点集合。 如果B中点p之前有x的定义点d，且这个定义能够到达 p，则点p处x的ud链是{d}。 否则，点p处x的ud链就是IB[B]中关于x的定义点的集 合。 P[B]：B的所有前驱基本块的集合。 GEN[B]：各个变量在B内定义，并能够到达B的出口点的 所有定义的集合。 OUT[B]：各个变量的能够到达基本块B的出口点的所有定 义的集合。 KILL[B]：是各个变量在基本块B中重新定义，即在此块内 部被注销的定义点的集合。 到达定义数据流方程 IN[B] = ∪OUT[p] where p isin P[B] OUT[B] = GEN[B]∪(IN[B]-KILL[B]) 其中： GEN[B]可以从基本块中求出：使用DAG图就可以 得到。 KILL[B]中，对于整个流图中的所有x的定义点，如 果B中有对x的定义，那么该定义点在KILL[B]中。 方程求解算法 使用迭代方法。 初始值设置为：IN[Bi]=空；OUT[B]=GEN[Bi]; change = TRUE; while(change) { change = FALSE; for each B do {IN[B] = ∪OUT[p] where p isin P[B]; OUT[B] = GEN[B]∪(IN[B]-KILL[B]); oldout = OUT[B]; if(OUT[B] != oldout) change = TRUE;} } 算法例子 B1 d1: - m 1 d2: = n d3: = u2 B2 d4: + i 1 d5: - j 1 B3 d6: = u2 B4 a d7: = u3 i GEN[B1]={d1,d2,d3} j KILL[B1]={d4,d5,d6,d7} a GEN[B2]={d4,d5} i KILL[B2]={d1,d2,d7} j GEN[B3]={d6} KILL[B3]={d3} GEN[B4]={d7} KILL[B4]={d1,d4} i 计算过程 初始化： IN[B1] = IN[B2] = IN[B3] = IN[B4] =空 OUT[B1]={d1,d2,d3}, OUT[B2]={d4,d5} OUT[B3]={d6}, OUT[B4]={d7}. 次循环： IN[B1]=空; IN[B2] ={d1,d2,d3,d7}; IN[B3]={d4,d5}; IN[B4]={d4,d5,d6}; OUT[B1]={d1,d2,d3}; OUT[B2]={d3,d4,d5}… 结果： IN[B1]=空；OUT[B1]={d1,d2,d3}; IN[B2]={d1,d2,d3,d5,d6,d7}; OUT[B2]={d3,d4,d5,d6}; IN[B3]={d3,d4,d5,d6}; OUT[B3]={d4,d5,d6}; 活跃变量数据流方程 判断在基本块出口之后，变量的值是否还被引用的这 种判断工作称为活跃变量分析。 消除复写四元式的依据就是对活跃变量的分析。如果 某个变量的值在以后不被引用，那么该复写四元式可 以被消除。 对于变量x和流图上的某个点p，存在一条从p开始的 路径，在此路径上在对x定值之前引用变量x的值， 则称变量x在点p是活跃变量，否则称x在点p不活跃。 无用赋值：对于x在点p的定值，在所有基本块内不 被引用，且在基本块出口之后又是不活跃的，那么x 在点p的定义是无用的。 记号 L_IN[B]: 基本块B的入口点的活跃变量集合。 L_OUT[B]: 是在基本块B的出口点的活跃变量 集合。 L_DEF[B]: 是在基本块b内的定值，但是在定义 前在B中没有被引用的变量的集合。 L_USE[B]: 表示在基本块中引用，但是引用前 在B中没有被定义的变量集合。 其中，L_DEF[B]和L_USE[B]是可以从基本块B 中直接求得的量，因此在方程中作为已知量。 活跃变量数据流方程 L_IN[B] = L_USE[B]∪(L_OUT[B]-L_DEF[B]) L_OUT[B] = ∪L_IN[s]，其中s遍历B的所有后继。 变量在某点活跃，表示变量在该点的值在以后会被使用。 个方程表示： 如果某个变量在B中没有定义就使用了，显然，变量在在 入口处的值会被使用。 如果这个变量在B的出口处活跃，并且B中没有对他进行定 义，那么变量在入口处也是活跃的。 第二个方程表示： 在B的某个后记中会使用该后继的入口处的值，那么他其 实也可能使用B的出口处的值。 活跃变量数据流方程求解 设置初值：L_IN[Bi]=空; 重复执行一下步骤直到L_IN[Bi]不再改变： for(i=1; in; i++) { L_OUT[Bi]= ∪L_IN[s]; s是Bi的后继； L_IN[Bi]=L_USE[Bi]∪(L_OUT[Bi]-L_DEF[Bi]); } 活跃变量数据流方程例子 d1: - m 1 i d2: = n j d3: = u1 a d4: + i d5: - j 1i 1j d6: = u2 a d7: = u3 i L_DEF[B1]={i,j,a} L_USE[B1]={m,n, u1} L_DEF[B2]=空 L_USE[B2]={i,j} L_DEF[B3]={a} L_USE[B3]={u2} L_DEF[B4]={i} L_USE[B4]={u3} 迭代过程 次循环： L_OUT[B1]=空 L_IN[B1]={m,n,u1} L_OUT[B2]=空 L_IN[B2]={i,j} L_OUT[B3]={i,j} L_IN[B3]={i,j,u2} L_OUT[B4]={i,j,u2} L_IN[B4]={j,u2,u3} 第二次循环： L_OUT[B1]={i,j,u2,u3} L_IN[B1]={m,n,u1,u2,u3} L_OUT[B2]={i,j,u2,u3} L_IN[B2]={i,j,u2,u3} L_OUT[B3]={i,j,u2,u3} L_IN[B3]={i,j,u2,u3} L_OUT[B4]={i,j,u2,u3} L_IN[B4]={j,u2,u3} 第三次循环各个值不再改变，完成求解。 可用表达式数据流方程 如果一个流图的首节点到达点p的每个路径上面都有对 x op y的计算，并且在后一个这样的计算到点p之间 没有对x,y进行定值，那么表达式x op y在点p是可用的。 表达式可用的直观意义：在点p上，x op y已经在之前 被计算过，不需要重新计算。 注意：如果对于有间接赋值四元式的情况，需要保证 后的计算x op y的点之间不会间接改变x,或者y的值： 比如指针不会指向x或者y的存储区域，特别是当x为某 个数组的时候。 书上的讲解是针对没有间接赋值四元式的情况处理的。 概念 对表达式的注销：如果某个基本块B对x或者y 定值，且以后没有重新计算x op y，那么称B 注销表达式x op y。 表达式的产生：如果某个基本块B对x op y进 行计算，而以后并没有在对x或者y重新定值， 那么称B产生表达式x op y。 表达式的全集：在计算某个流图中的可用表达 式的时候，表达式的讨论范围被限定在该出现 在流图中的四元式对应的表达式。 记号 E_OUT[B]：在基本块出口处的可用表达式集合。 E_IN[B]：在基本块入口处的可用表达式集合。 E_GEN[B]：基本块B所产生的可用表达式的集合。 E_KILL[B]：基本块B所注销掉的可用表达式的集合。 E_GEN[B]和E_KILL[B]的值可以直接从流图计算出 来。因此在数据流方程中，可以将E_GEN[B]和 E_KILL[B]当作已知量看待。 E_GEN[B]的计算 对于一个基本块B，E_GEN[B]的计算过 程如下： 初始设置：E_GEN[B]=空； 顺序扫描每个四元式： 对于四元式op x y z，把x op y加入 E_GEN[B]， 从E_GEN[B]中删除和z相关的表达式。 后的E_GEN[B]就是相应的集合。 E_KILL[B]的计算 设流图的表达式全集为E; 初始设置：EK = 空； 顺序扫描基本块的每个四元式： 对于四元式op x y z，把表达式x op y从EK 中消除； 把E中所有和z相关的四元式加入到EK中。 扫描完所有的四元式之后，EK就是所求的 E_KILL[B]。单词优化 数据流方程 p1 p2 p3 IN GEN 1. E_OUT[B]=(E_IN[B]-E_KILL[B])U E_GEN[B] 2. E_IN[B]= ∩E_OUT[p] B!=B1, p是B的前驱。 3. E_IN[B1]=空集 说明： 在程序开始的时候，无可用表达式。(3) 一个表达式在某个基本块的入口点可用，必 须要求它在所有前驱的出口点也可用。（2） 一个表达式在某个基本块的出口点可用，或 者该表达式是由它的产生的；或者该表达式 在入口点可用，且没有被注销掉。（1） B -KILL OUT 方程求解算法 迭代算法 初始化：E_IN[B1]=空; E_OUT[B1]=E_GEN[B1];E_OUT[Bi]=UE_KILL[Bi](i=2) 重复执行下列算法直到E_OUT稳定: FOR（i=2; i=n ;i++) { E_IN[Bi]= ∩E_OUT[p], p是Bi的前驱； E_OUT[Bi]=E_GEN[Bi] ∪(E_IN[Bi]-E_KILL[Bi]); } 算法说明 初始化值和前面的两个算法不同。 E_OUT[Bi]的初值大于实际的值。 在迭代的过程中，E_OUT[Bi]的值逐渐 缩小直到稳定。 U表示四元式的全集，就是四元式序列中 所有表达式x op y的集合。 寻找循环不变表达式算法 输入：循环L，已经建立的UD链 输出：不变四元式 步骤1：若四元式的运算分量或者是常数，或者其 所有定义点在循环外部，则标记此四元式为不变。 步骤2：重复执行下面的步骤： 如果一个四元式没有被加过标记，且运算分量要么是常 数，要么其UD链中的定义点在循环外，或者该定义点已 经被加过标记，则标记此四元式为不变。 说明：一个四元式的是不变的，当且仅当其分量在 循环中是不变的。主要有三种情况：常量，定义点 在循环外部，或者定义点的四元式也是不变的。 不变四元式外提方法 对于不变四元式，可 以在进入循环之前首 先计算该四元式的值， 然后在循环内部使用 该值。 可以将四元式的值外 体到紧靠循环之前。 首节点 前置节点 首节点 代码外提不合法的情况（1） =1 i u v B3 =2 i +u1u =1 i =2 i u v B3 +u1u - v1v = v 20 B5 - v1v = v 20 B5 =i j =i j 代码外提不合法的情况（2） =1 i =3 i u v B3 =2 i +u1u - v1v = v 20 B5 =i j =1 i =3 i u v B3 =2 i +u1u - v1v = v 20 B5 =i j 代码外提不合法的情况（3） =1 i =0 k u v B3 =i k +u1u =2 i - v1v = v 20 B5 =1 i =0 k =2 i u v B3 =i k +u1u - v1v = v 20 B5 =i j =i j 不变四元式外提的条件 不变四元式s=op x y z可以外提的条 件： s所在的基本块节点是循环所有出口节点的必 经节点。出口节点是指有后继节点在循环外的 节点。（反例：情况1） 循环中z没有其他的定值点。（反例：情况2） 循环中z的引用点仅由s到达。（反例：情况3） 外提算法 步骤1：寻找一切不变四元式。 步骤2：对于找到的每个循环，检查是否 满足上面说的三个条件。 步骤3：按照不变四元式找出的次序，把 所找到的满足上述条件的四元式外提到 前置节点中。 如果四元式有分量在循环中定值，只有将定 值点外提后，该四元式才可以外提。 循环不变式外提的例子 =1 i =0 k 1) + i 1 k 2) * 2 k t u v B3 +u1u - v1v = v 20 B5 =1 i =0 k 1)+ i 1 k 2)* 2 k t u v B3 +u1u - v1v = v 20 B5 =i j =i j 关于归纳变量的优化 基本归纳变量：如果循环中，对于i的定值只有 形状如i = i + c的定值，那么i称为循环的基本 归纳变量。单词优化 归纳变量族：如果循环中对变量j的定值都是形 状如j=C1*i+C2，且i为基本归纳变量，那么 称j为归纳变量，且属于i族。i属于i族。 对于定值为C1*i+C2的i族归纳变量j，我们用 (i,C1, C2)来表示。 对于i族的归纳变量(i,C1, C2)，要求循环内部 对此变量进行定值的时候，一定是赋给 C1*i+C2。 例子（源程序） for(i = 0; i100; i++) { j = 4*i; printf(“%i”, j); } i是基本归纳变量。j是i族归纳变量，可以表示为(i, 4, 0)。 寻找循环的归纳变量算法 步骤1：扫描循环的四元式，找出所有基本归纳变量。对 应于每个基本归纳变量的三元组如(i,1,0)。 步骤2：寻找循环中只有一个赋值的变量k，且对它的定值 为如下形式，k=j*b, k=b*j, k=j/b, k=j+(-)b, k=b+(-)j。 其中j为基本归纳变量，或者已经找到的归纳变量。 如果j为基本归纳变量，那么k属于j族。k对应的三元式 可以确定。 如果j不是基本归纳变量，且属于i族，那么我们还要求： 循环中对j的赋值以及和对k的赋值之间没有对i的赋 值，且 没有j在循环外的定值可以到达k的这个定值点。 j的三元式可以相应确定。 算法说明 关于j不是基本归纳变量的时候，算法中 的两个要求实际上是保证：对k进行赋值 的时候，j变量当时的值一定等于C1*（i 当时的值）+C2。 归纳变量的计算强度削弱算法 对于每个基本归纳变量i，对其族中的每个归纳 变量j(i, c, d)执行下列步骤： 建立新的临时变量t。 用= t j四元式代替对j的赋值。 对于每个定值i=i+n之后，添加t=t+c*n。 在前置节点的末尾，添加四元式* c i t和+ t d t。使得在循环开始的时候, t=c*i+t。 当两个归纳变量具有同样的三元式的时候，可以 只建立一个临时变量。 算法的说明 在优化过程中，为j(i,c,d)引入的变量t保 证了在任何时刻(不包括在对i新定值后并 且在t重新定值前，但是由于两者的四元 式时紧连的）都满足t=c*i+d。 如果在某些情况下，程序运行时对j的定 值的次数远远少于对i的定值，经过优化 的程序需要对t多次赋值，实际的效率可 能降低。 归纳变量的删除 有些归纳变量的作用就是控制循环的次 数。如果循环出口处的判断可以使用其 它的变量代替，那么可以删除这些归纳 变量。 归纳变量的删除算法 步骤1：对于每个基本归纳变量，取i族的某个归纳变量j（尽量 使得c,d简单）。把每个对i的测试修改称为用j代替。 relop i x B修改为relop i c*x+d B。 relop i1 i2 B，如果能够找到三元组(i1, c,d)和(i2,c,d)， 那么可以将其修改为relop j1 j2 B(假设c0)。 如果归纳变量不再被引用，那么可以删除和它相关的四元 式。 如果基本归纳变量在循环出口处活跃，上面的算法不可以 直接使用。 步骤2：考虑对j的赋值= t j。如果每次对j引用和这个赋值 四元式之间没有任何对t的赋值（此时，每次使用j的时候都有 t=j)，可以在引用j的地方用t代替，同时删除四元式= t j （如果j在循环的出口处活跃，需要增加= t j）。 全局公共子表达式消除 对于循环中某个四元式op x y z，如果在所有到达 这个四元式的路径上，已经计算了x op y，且计算 之后x,y的值再没有修改过，那么显然我们可以使 用以前计算得到的值。 可用表达式表达的就是这个概念。 如果有四元式op x y z，且在四元式前，表达式x op y可用，那么我们可以用下面的方法优化：在 前面不同的地方计算x op y时，把值记录到同一个 临时变量u里面。把这个四元式改变为= u z。 全局公共子表达式删除 对于四元式Q(op x y z)，如果x op y再 Q之前可用，那么执行如下步骤： 从Q开始逆向寻找，找到所有离Q近的计 算了x op y四元式。 建立新的临时变量u。 把步骤1中找到的四元式op x y t用下列 四元式代替：op x y u和= u t。 用= u t替代Q。 全局公共子表达式消除(图示) …… *xyk …… …… *xyt …… …… *xyu =u k …… …… *xyu =u t …… …… *xyl …… …… =u l …… 复制四元式的消除 中间代码的生成可能产生四元式。 消除公共子表达式和删除归纳变量的时候，也会产 生复制四元式。 通过复制四元式传播的变量大多数是临时变量。而 对临时变量可以使用复制传播来消除复制四元式。 原理：= x y的效果是x和y的值相等。如果某 个引用y的四元式运行的时候，x和y的值一定相等。 那么我们可以使用对y的引用来替代对x的引用。这 样做有时可以消除复制四元式= x y。 消除复制四元式的条件 对于复制四元式d: = x y，如果对y 对应于d点的一切引用点u满足下列条件， 那么我们可以删除d，并且在这些引用点 上用对x的引用代替对y的引用。 此定义点是d到达u的的y的定义。 从d到达u的路径（可以包含圈和多个u，但 是不包含多个d）上，没有对x的定义。 这两个条件实际上是说，当程序运行到 达u点的时候，x和y的值总是相等。 记号 C_GEN[B]：在基本块B中的所有复制四元式= x y， 并且从该四元式开始到B的出口，x和y都没有再定义。 C_KILL[B]：包含了所有在流图中出现并且满足下列条 件的复制四元式= x y：B中存在对x或者y的定 义，并且之后在没有复制四元式= x y出现。 C_IN[B]：表示在B的入口点，有效的复制四元式= x y的集合，也就是到达入口的路径上都要经过= x y并且之后没有对x或者y定义。 C_OUT[B]：表示在B的出口点有效的复制四元式的集 合。 数据流方程 C_OUT[B] = C_GEN[B] ∪(C_IN[B]C_KILL[B]) C_IN[B] = ∩E_OUT[p]；其中B不等于B1， p是B的前驱。 C_IN[B1] = 空集。 其中C_GEN[B]和C_IN[B]可以直接从流图 得到，所以在方程中作为已知量处理。 求解方法和可用表达式的求解相同。 复制传播算法 对于每个复制四元式d: = x y执行下 列步骤。 找出该y定义所能够到达的那些对y的引用。 确定是否对于每个这样的y，d都在C_IN[B] 中，B是包含这个引用的基本块，而且B中 该引用的前面没有x或者y的定义。 如果d满足条件(2)，删除d，且把步骤1中 找到的的对y的引用用x代替。 复制传播算法的例子 =x y =x y + x1 y * y 2t * y 3 t2 循环优化的例子(原始流图） B1 - m 1 t1 = t1 i =n j * 4 n t2 =[] A t2 t3 = t3 v B2 + i 1 t4 = t4 i * 4 i t5 =[] A t5 t6 t9 v B3 B3 - j 1 t7 B6 i j B2 = t7 j * 4 j t8 =[] A t8 t9 t9 v B3 B7 * 4 i t18 =[] A t18 t19 = t19 x B4 = i j B6 * 4 i t20 []= A t20 t21 B5 * 4 i t10 =[] A t10 t11 = t11 x * 4 i t12 []= A t12 t13 ………… * 4 n t22 =[] A t22 t23 &= t23 t21 t21 * 4 n t24 []= A t24 t25 &= x t25 t25 寻找回边以及自然循环 回边有：B2B2, B3B3, B6B2。 B2B2对应的循环是{B2} B3B3对应的循环是{B3} B6B2对应的循环是{B2,B3,B4,B5,B6} 删除回边之后，得到的图是无回路的， 所以这个流图是可归纳流图。 寻找公共子表达式 4*i：在B5，B7入口处可用(U1)。 A[4*i]：在B5，B7的入口处可用(U2)。 4*j：在B5的入口处可用(U3)。 A[4*j]：在B5的入口处可用(U4)。 4*n：在B7的入口处可用(U5)。 A[4*n]：在B7的入口处可用(U6)。 公共子表达式的优化 - m 1 t1 B1 = t1 i =n j * 4 n u5 = u5 t2 =[] A t2 u6 = u6 t3 = t3 v + i 1 t4 = t4 i * 4 i u1 = u1 t5 =[] A t5 u2 = u2 t6 t9 v B3 B3 - j 1 t7 = t7 j * 4 j u3 = u3 t8 =[] A t8 u4 = u4 t9 t9 v B3 B4 = i j B6 B5 = u1 t10 = u2 t11 = t11 x * 4 i t12 []= A t12 t13 ………… B6 i j B2 B7 = u1 t18 = u2 t19 = t19 x = u1 t20 []= A t20 t21 = u5 t22 = u6 t23 &= t23 t21 t21 = u5 t24 []= A t24 t25 &= x t25 t25 寻找归纳变量 基本归纳变量有i，j。 归纳变量有： u1：i族，(i, 4, 0) u2：j族，( j, 4, 0) 如果分析得更加深入，会发现[]= 四元式得到 的地址也是归纳变量。但是，由于我们不考虑 对间接赋值的优化，同时地址的处理也不在范 围之内，所以我们没有列出。 - m 1 t1 = t1 i =n j B1 * 4 n u5 = u5 t2 =[] A t2 u6 = u6 t3 = t3 v * 4 i u1 * 4 j u3 + i 1 t4 = t4 i + u1 4 u1 =[] A u1 u2 = u2 t6 t9 v B3 归纳变量的优化 B3 - j 1 t7 = t7 j - u3 4 u3 =[] A u3 u4 = u4 t9 t9 v B3 B4 = u1 u3 B6 B5 = u2 t11 = t11 x = u1 t12 []= A t12 t13 ………… B6 u1 u3 B2 B7 = u2 t19 = t19 x = u1 t20 []= A t20 t21 = u5 t22 = u6 t23 &= t23 t21 t21 = u5 t24 []= A t24 t25 &= x t25 t25 - m 1 t1 = t1 i =n j B1 * 4 n u5 = u5 t2 =[] A t2 u6 = u6 t3 = t3 v * 4 i u1 * 4 j u3 + u1 4 u1 =[] A u1 u2 = u2 t6 t9 v B3 优化结果 B3- u3 4 u3 =[] A u3 u4 = u4 t9 t9 v B3 B4 = u1 u3 B6 B5 = u2 t11 = t11 x = u1 t12 []= A t12 t13 ………… B6 u1 u3 B2 B7 = u2 t19 = t19 x = u1 t20 []= A t20 t21 = u5 t22 = u6 t23 &= t23 t21 t21 = u5 t24 []= A t24 t25 &= x t25 t25 窥孔优化 是指对代码局部进行改进的简单有效的 技术。只考虑目标代码中的指令序列， 把可能的指令序列替换成为更短更快的 指令。 冗余指令删除。 控制流优化 代数化简 特殊指令使用 冗余指令删除 多余存取指令的删除： MOV b R0 ADD c R0 MOV R0 a MOV a R0 SUB d R0 MOV R0 c 第四条指令没有任何效果，可以删除。 如果有标号转向第四条指令，则不可以删除。 冗余指令删除 无用代码删除： 将不会被执行的代码删除。 如果目标代码中有无条件转移指令，且其后的指令 标号，那么后面的指令可以删除。 产生无用代码的原因可以是调试信息，或者优 化的结果。 对于条件转移指令，如果其条件永远成立或者 永远不成立，可以转换成为等价的无条件转移 指令。 控制流优化 在代码中出现转移指令到转移指令的情况时， 某些条件下可以使用一个转移指令来代替。 转移到转移 GOTO L1; …… L1: GOTO L2; 显然个转移指令可以替代为GOTO L2. 如果在没有其他的指令转移到L1，那么第二个 指令可以被删除。 控制流优化（续） 转移到条件转移： L0: GOTO L1 …… L1: IF b THEN GOTO L2; L3: … … 如果只有一个转移指令到达L1，且L1前面是无条件转 移指令，那么可以修改成为： IF b THEN GOTO L2; GOTO L3 L3: … … 控制流优化（续） 条件转移到转移 IF b THEN … … GOTO L3 可以被修改为 IF b THEN … … GOTO L3 GOTO L1 GOTO L3 代数化简 利用代数规则来优化代码。 例如： 利用x=x+0和x=x*1来删除相应的指 令。 利用x2=x*x来削减计算强度。 特殊指令的使用 充分利用目标系统的某些高效的特殊指 令来提高代码效率。 这些指令只可以在某些情况下使用。而 识别这样的情况是优化的基础。 例如：INC指令可以用来替代加1的操作。
以上信息由常州声谷信息科技有限公司整理编辑，了解更多网站优化,网站优化代理,单词优化,网站优化哪家好,单词优化代理,正规网站优化代理信息请访问http://www.shengguxinxi.com