编译原理chapter9优化.ppt

第十章 代 码 优 化,通过程序变换（局部变换和全局变换）来改进程序，称为优化 介绍独立于机器的优化，即不考虑任何目标机器性质的优化变换 流图中循环的识别 数据流分析 代码改进变换,10.1 引言,10.1.1 代码改进变换的标准 代码变换必须保程序的含义 采取安全稳妥的策略 变换减少程序的运行时间平均达到一个可度量的值 变换所作的努力是值得的,10.1 引言,10.1.2 性能的提高 优化可以在源程序阶段也可以在编译阶段进行。算法有优劣，有适用范围。源程序设计时算法的选择极需斟酌，需要在时间复杂性、空间复杂性上作出比较以决定对算法的取舍。例如对N个元素排序，插入排序需要2.02N2s，而快速排序则为12Nlog2Ns，当N=100时两者速度差2.5倍，而当N=100000时，速度差1000余倍。很明显，源程序阶段的优化不是编译程序能够和应该完成的。,10.1 引言,10.1.3 优化编译器的组织 实现高级结构的操作在中间代码中是显式的 中间代码基本上独立于目标机器,10.2 优化的主要种类,本节所用的例子 i = m 1; j = n; v = an; (1) i := m 1 while (1) (2) j := n do i = i +1; while(aiv); (4) v := at1 if (i = j) break; (5) i := i + 1 x=ai; ai=aj; aj=x; (6) t2 := 4 * i (7) t3 := at2 x=ai; ai=an; an=x; (8) if t3v goto (5),10.2 优化的主要种类,本节所用的例子 i = m 1; j = n; v = an; (9) j := j 1 while (1) (10) t4 := 4 * j do i = i +1; while(aiv); (12) if t5v goto (9) if (i = j) break; (13) if i =j goto (23) x=ai; ai=aj; aj=x; (14) t6 := 4 * i (15 ) x := at6 x=ai; ai=an; an=x; . . .,10.2 优化的主要种类,10.2.1 局部优化,t6 := 4 * I x := at6 t7 := 4 * i t8 := 4 * j t9 := at8 at7 := t9 t10 := 4 * j at10 := x goto B2,t11 := 4 * i x := at11 t12 := 4 * i t13 := 4 * n t14 := at13 at12 := t14 t15 := 4 * n at15 := x,10.2.2 公共子表达式删除,如果表达式E先前已计算，并且从先前的计算到E的再次出现，E中变量的值没有改变，那么E的这个再次出现称为公共子表达式,10.2.2 公共子表达式删除,B5 x=ai; ai=aj; aj=x;,t6 := 4 * i x := at6 t7 := 4 * i t8 := 4 * j t9 := at8 at7 := t9 t10 := 4 * j at10 := x goto B2,10.2.2 公共子表达式删除,B5 x=ai; ai=aj; aj=x;,t6 := 4 * i x := at6 t7 := 4 * i t8 := 4 * j t9 := at8 at7 := t9 t10 := 4 * j at10 := x goto B2,10.2.2 公共子表达式删除,B5 x=ai; ai=aj; aj=x;,t6 := 4 * i x := at6 t7 := 4 * i t8 := 4 * j t9 := at8 at7 := t9 t10 := 4 * j at10 := x goto B2,t6 := 4 * i x := at6 t8 := 4 * j t9 := at8 at6 := t9 at8 := x goto B2,10.2.2 公共子表达式删除,10.2.3 复写传播,形成为f := g的赋值叫做复写语句 优化过程中会大量引入复写,10.2.3 复写传播,形成为f := g的赋值叫做复写语句 优化过程中会大量引入复写 复写传播变换的做法是在复写语句f := g后，尽可能用g代表f,x := t3 at2 := t5 at4 := t3 goto B2,x := t3 at2 := t5 at4 := x goto B2,10.2.3 复写传播,成为f := g的赋值叫做复写语句 优化过程中会大量引入复写 复写传播变换的做法是在复写语句f := g后，尽可能用g代表f 复写传播变换本身并不是优化，但它给其它优化带来机会 常量合并 死代码删除,10.2.4 死代码删除,死代码是指计算的结果决不被引用的语句 一些优化变换可能会引起死代码 例： debug := true; debug := false; . . . 测试后改成 . . . if (debug) print if (debug) print ,10.2.4 死代码删除,代码是指计算的结果决不被引用的语句 一些优化变换可能会引起死代码 例：复写传播可能会引起死代码删除,x := t3 at2 := t5 at4 := t3 goto B2,at2 := t5 at4 := t3 goto B2,10.2.5 循环优化,代码外提 归纳变量删除 强度削弱,10.2.6 代码外提,代码外提是循环优化的一种 例：while (i = limit 2 ) 变换成 t = limit 2; while (i = t ) ,10.2.7 强度削弱和归纳变量删除,j和t4的值步伐一致地变化 这样的变量叫做归纳变量 在循环中有多个归纳变量时， 也许只需要留下一个 这个操作由归纳变量删除 过程来完成 对本例可以先做强度削弱 它给删除归纳变量创造机会,10.2.7 强度削弱和归纳变量删除,j := j 1 t4 := 4 * j t5 := at4 if t5 v goto B3,B3,除第一次外， t4 = 4 * j在B3的入口 一定保持 在j := j 1后， 关系t4 = 4 * j + 4也 保持,10.2.7 强度削弱和归纳变量删除,10.2.7 强度削弱和归纳变量删除,10.3 基本块的变换,DAG,10.4 流图中的循环,10.4.1 必经结点 结点d是结点n的必经结点， 如果从初始结点起，每条 到达n的路径都要经过d， 写成d dom n 每个结点是它本身的必经 结点 循环的入口是循环中所有 结点的必经结点,10.4 流图中的循环,10.4.2 自然循环 循环 循环必须有唯一的入口点，叫做首结点，首结点是循环中所有结点的必经结点 至少有一种办法重复循环，也就是至少有一条路径回到首结点 回边 如果有a dom b ，那么边b a叫做回边 寻找流图中所有循环的一个办法是找出流图的回边,10.4 流图中的循环,由回边n d确定的自然循环中的所有结点的集合loop。 方法 由结点n开始，考虑已置入loop的每个结点m，md，以保证m的前驱也能置入loop，这个算法在图9.11中给出。loop中的每个结点，除了d以外，一旦加入stack，它的前驱就要被检查。注意，因为d是初始时置入循环，我们决不会考察它的前驱，因此仅找出那些不经过d可以到达n的结点。,10.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 回边9 1 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,10.4 流图中的循环,10.4.3 内循环 若一个循环的结点集合是另一个循环的结点集合的子集。 两个循环有相同的首结点, 但并非一个结点集是另一个 的子集，则看成一个 循环。,10.4 流图中的循环,10.4.4 前置结点 某些变换要求我们移动语句到首结点的前面,10.4 流图中的循环,10.4.5 可归纳流图 一个流图G是可归约的，当且仅当 有向边集合=正向边子集回边子集，并有性质: 正向边子集形成有向无环图，在这个图中，每个结点可以从G的初始结点到达 回边子集仅由前面所讲的回边组成,10.4 流图中的循环,10.4 流图中的循环,非归约流图的例子 初始结点是1 2 3和3 2都不是回边 该图不是无环的 从结点2和3两处进入由 它们构成的环,10.5 全局数据流分析介绍,编译器需要把程序流图作为一个整体来收集信息 并把这些信息分配给流图的各个基本块 数据流信息可以通过建立和解数据流方程来收集 典型方程 out B = gen B (in B kill B ),10.5 全局数据流分析介绍,建立和解数据流方程依赖三个因素 out B = gen B (in B kill B ) 产生和注销的概念依赖于数据流方程所要解决的问题，也会出现反向前进，由outB来定义inB 数据流分析受程序控制结构影响 过程调用、通过指针赋值、甚至对数组变量的赋值等的存在使得数据流分析大大复杂,10.5 全局数据流分析介绍,10.5.1 点和路径 点 基本块中，两个相邻的语句之间为程序的一个点 基本块的开始点和结束点 路径 点序列p1, p2, , pn，对1和n - 1间的每个i，满足 pi是先于一个语句的点，pi1是同一块中位于该语句后的点，或者 pi是某块的结束点，pi1是后继块的开始点,10.5.2 到达-定值,确切定值：赋值语句或读语句 可能定值：过程调用,别名,通过指针来赋值 确切引用 可能引用 在给出简单的例子加以区别后，我们将不考虑过程调用,别名,通过指针来赋值等引起不确定性的情况。,10.5.2 到达-定值,x的定值语句d能到达点p d: x := d: x := d: x := . . . . d1: x := d1: *y := . . . p p p d到达p d不能到达p d到达p d被注销 d1也能到达p,10.5.2 到达-定值,i := m 1和j := n 都能到达B2的开始点 j := j 1也能到达 B2的开始点 j := n不能到 B4,10.5.2 到达-定值,d: x := d: x := d: x := . . . . d1: x := d1: *y := . . . p p p D可以到达p d不能到达p d能到达p d被注销 d1也能到达p 到达-定值是不精确的，但是稳妥的 会使我们失去某些实际是安全的变换,10.6 迭代算法,10.6.1 到达-定值的迭代算法,到达-定值的迭代算法 gen B：B中能到达B的结束点的定值语句 kill B：整个程序中决不会到达B结束点的定值 in B：能到达B的开始点的定值集合 out B：能到达B的结束点的定值集合 两组方程（根据gen和kill求解in和out） in B = out P P是B的前驱 out B = gen B (in B kill B),10.6.2到达-定值的迭代算法,in B B1 000 0000 B2 000 0000 B3 000 0000 B4 000 0000,gen B1 = d1, d2, d3 kill B1=d4, d5, d6, d7,gen B2 = d4, d5 kill B2 = d1, d2, d7,gen B3 = d6 kill B3 = d3,gen B4 = d7 kill B4 = d1, d4,10.6.2到达-定值的迭代算法,in B out B B1 000 0000 111 0000 B2 000 0000 000 1100 B3 000 0000 000 0010 B4 000 0000 000 0001,gen B1 = d1, d2, d3 kill B1=d4, d5, d6, d7,gen B2 = d4, d5 kill B2 = d1, d2, d7,gen B3 = d6 kill B3 = d3,gen B4 = d7 kill B4 = d1, d4,10.6.2到达-定值的迭代算法,in B out B B1 000 0000 111 0000 B2 111 0001 000 1100 B3 000 0000 000 0010 B4 000 0000 000 0001,gen B1 = d1, d2, d3 kill B1=d4, d5, d6, d7,gen B2 = d4, d5 kill B2 = d1, d2, d7,gen B3 = d6 kill B3 = d3,gen B4 = d7 kill B4 = d1, d4,10.6.2到达-定值的迭代算法,in B out B B1 000 0000 111 0000 B2 111 0001 001 1100 B3 000 0000 000 0010 B4 000 0000 000 0001,gen B1 = d1, d2, d3 kill B1=d4, d5, d6, d7,gen B2 = d4, d5 kill B2 = d1, d2, d7,gen B3 = d6 kill B3 = d3,gen B4 = d7 kill B4 = d1, d4,10.6.2到达-定值的迭代算法,in B out B B1 000 0000 111 0000 B2 111 0001 001 1100 B3 001 1100 000 0010 B4 000 0000 000 0001,gen B1 = d1, d2, d3 kill B1=d4, d5, d6, d7,gen B2 = d4, d5 kill B2 = d1, d2, d7,gen B3 = d6 kill B3 = d3,gen B4 = d7 kill B4 = d1, d4,10.6.2到达-定值的迭代算法,in B out B B1 000 0000 111 0000 B2 111 0001 001 1100 B3 001 1100 000 1110 B4 000 0000 000 0001,gen B1 = d1, d2, d3 kill B1=d4, d5, d6, d7,gen B2 = d4, d5 kill B2 = d1, d2, d7,gen B3 = d6 kill B3 = d3,gen B4 = d7 kill B4 = d1, d4,10.3 全局数据流分析介绍,in B out B B1 000 0000 111 0000 B2 111 0001 001 1100 B3 001 1100 000 1110 B4 001 1110 000 0001,gen B1 = d1, d2, d3 kill B1=d4, d5, d6, d7,gen B2 = d4, d5 kill B2 = d1, d2, d7,gen B3 = d6 kill B3 = d3,gen B4 = d7 kill B4 = d1, d4,10.6.2到达-定值的迭代算法,in B out B B1 000 0000 111 0000 B2 111 0001 001 1100 B3 001 1100 000 1110 B4 001 1110 001 0111,gen B1 = d1, d2, d3 kill B1=d4, d5, d6, d7,gen B2 = d4, d5 kill B2 = d1, d2, d7,gen B3 = d6 kill B3 = d3,gen B4 = d7 kill B4 = d1, d4,10.6.2到达-定值的迭代算法,in B out B B1 000 0000 111 0000 B2 111 0111 001 1100 B3 001 1100 000 1110 B4 001 1110 001 0111,gen B1 = d1, d2, d3 kill B1=d4, d5, d6, d7,gen B2 = d4, d5 kill B2 = d1, d2, d7,gen B3 = d6 kill B3 = d3,gen B4 = d7 kill B4 = d1, d4,10.6.2到达-定值的迭代算法,in B out B B1 000 0000 111 0000 B2 111 0111 001 1110 B3 001 1100 000 1110 B4 001 1110 001 0111,gen B1 = d1, d2, d3 kill B1=d4, d5, d6, d7,gen B2 = d4, d5 kill B2 = d1, d2, d7,gen B3 = d6 kill B3 = d3,gen B4 = d7 kill B4 = d1, d4,10.6.2到达-定值的迭代算法,in B out B B1 000 0000 111 0000 B2 111 0111 001 1110 B3 001 1110 000 1110 B4 001 1110 001 0111,gen B1 = d1, d2, d3 kill B1=d4, d5, d6, d7,gen B2 = d4, d5 kill B2 = d1, d2, d7,gen B3 = d6 kill B3 = d3,gen B4 = d7 kill B4 = d1, d4,10.6.3 可用表达式,in B = out P P是B的前驱 out B = gen B (in B kill B) 到达-定值方程是正向的方程，另一类数据流方程是反向的 到达-定值方程的合流算符是求并集，另一类数据流方程的合流算符是求交集 到达-定值的信息存储为引用-定值链（或叫ud链），指能到达变量的某个引用的所有定值,10.6.3 可用表达式,x := y + z x := y + z x := y + z . . . . y := z := . . . p p p y + z 在p点 y + z 在p点 y + z 在p点 可用 不可用 不可用,10.6.3 可用表达式,10.6.3 可用表达式,计算可用表达式的方程 out B = e_gen B (in B e_kill B ) in B = out P （B不是初始块） P是B的前驱 in B1 = （B1是初始块） 和到达-定值方程的区别 初始块的in处理为特殊情况 合流算符是交集运算而不是并集运算 到达-定值求最小解，可用表达式求最大解,10.6.3 可用表达式,in集合的不同初值比较 in B2 = out B1 out B2 （以B2为例） out B2 = G (in B2 K),10.6.4 活跃变量分析,x的值在p点开始的路径上被引用，我们说x在p点活跃，否则称x在p点是死亡的 in B：开始点的活跃变量集合 outB：结束点的活跃变量集合 defB：块B中有定值且该定值前无引用的变量集 useB：块B中有引用且在该引用前无定值的变量集,10.6.4 活跃变量分析,in B：开始点的活跃变量集合 outB：结束点的活跃变量集合 defB：块B中有定值且该定值前无引用的变量集 useB：块B中有引用且在该引用前无定值的变量集 in B = use B (out B def B ) outB = in S S是B的后继,10.6.5定值引用链（du链）,定值引用链（du链） du链问题是计算对变量（如x）定值的所有引用语句s的集合 可以建立数据流方程来求解定值引用信息,数据流问题的讨论合流问题,向前流（forward-flow)(信息流的方向与控制流是一致的)和向后流（backward flow） 对每个基本块有一个IN集合和一个Out集合,在同一基本块中，In和Out集合的关系 对于向前流问题：Out (B) = Used (B) (In(B) Killed (B) 对于向后流问题：In (B) = Used (B) (Out (B) Killed (B) 作为一个边界条件，向前流问题中的起始基本块的In和向后流问题中最后一个基本块的Out集合必须指明，通常，这些边界条件集或者为空，或者包含所有可能的值，因问题而定。 如：到达-定值数据流方程 OUTB=(INB-KILLB)GENB 活跃变量数据流方程 LiveIn(B)=LiveUse(B)(LiveOut(B)-Def(B),数据流问题的讨论路径问题,任意路径数据流分析 讨论的数据流假定这么一个性质，即某条路径为真，（如果存在某条路径上被引用这个变量就认为是活跃的；如果存在任何一条路径上被定值，则就认为这个变量是被定值的）。这种数据流问题被称为任意路径问题。任意路径问题的解不能保证所需的性质一定会满足，仅仅是可能满足。 全路径数据流分析 数据流问题也可以用全路径（all- path）形式来解决，使所需的性质在所有可能的路径都满足。对于全路径问题的解，所需的性质可以保证总是满足。,10.7 代码改进变换,依赖于上节收集的数据流信息进行代码改进变换 有些变换可以一起完成，但这里是逐个讨论 代替不了局部变换,10.7.1 公共子表达式删除,算法: 对每个s: x := y + z，若y + z 在块的开始点可用, 在s前没有y或z的定值，则执行下面的步骤： 从该块开始反向搜索，找出到达该块开始点的y + z的计算 建立新变量u 把上面找到的每个语句w := y + z改成 u := y + z w := u 用x := u代替语句s,10.7.1 公共子表达式删除,例,10.7.1 公共子表达式删除,该方法并非都是改进 （若运行时主要走那条红色路径）,10.7.1 公共子表达式删除,只能删除明显的公共子表达式 a := x + y 和 c := x + y b := a * z d := c * z 漏掉了a * z和c * z有相同的值这个事实 但是若和复写传播联系起来，可以找出这样的 公共子表达式,10.7.1 公共子表达式删除,10.7.2 复写传播,10.4.2 复写传播 s: x := y . . . u: := x 用y代替x的前提是： 语句s是到达u的唯一的x定值 从s到u的每条路径，包括穿过u若干次的路径上，没有对y的赋值,10.7.2 复写传播,建立新的数据流分析方程来解决第二个前提 in B 和 out B：复写语句s: x := y的集合 c_gen B：出现在块B中的s: x := y，且块B中该语句的后面没有对x或y的定值 c_kill B：不在块B中的s: x := y，且x或y在块B中赋值,10.7.2 复写传播,建立新的数据流分析方程来解决第二个前提 in B 和 out B：复写语句s: x := y的集合 c_gen B：出现在块B中的s: x := y ，且块B中该语句的后面没有对x或y的定值 c_kill B：不在块B中的s: x := y，且x或y在块B中赋值 out B = c_gen B (in B c_kill B) in B = out P （B不是初始块） P是B的前驱 in B1 = （B1是初始块）,10.7.2 复写传播,c_gen B1 = x := y c_gen B3 = x := z c_kill B1 = x := z c_kill B2 = x := y c_kill B3 = x := y in B1= , in B2 = in B3 = out B1 = x := y out B2 =, out B3 = in B4 = out B4 = x := z in B5 = out B2 out B4 = ,10.7.3 寻找循环不变计算,输入 循环L，对L的每个三地址语句，有ud链可用。 输出 从控制进入L一直到离开L，每次都计算同样值的三地址语句被输出。 方法 把运算对象都是常量（或其所有的到达定值都在L外）的语句，标记为“不变”语句。 重复下一步，直到没有新的语句标记为“不变”为止 给下面的语句标记“不变”：它们先前没有标记，并且所有的运算对象都是下列三种情况之一： （a）常量；（b）其所有的到达定值都在L外； （c）只有一个到达定值，这个定值是循环中已标记为“不变”的语句。,10.7.4 代码外提,10.4.4 代码外提 将循环不变语句提到循环的前置结点中 并不是所有的循环不变语句都可以外提 我们讨论三个条件（并非是必要条件）,10.7.4 代码外提,语句s : x := y+ z可以外提的条件 含s的块是循环所有出口结点的必经结点,10.7.4 代码外提,语句s : x := y+ z可以外提的条件 循环中没有其它语句对x定值,10.7.4 代码外提,语句s : x := y+ z可以外提的条件 x的其它定值都不能到达循环中x的引用,10.7.4 代码外提,(1) 寻找循环L中所有不变运算。 (2)对不变运算P：x:=y op z或x:=op y或x:=y，如果它满足下述两组条件中的一组 P点所在基本块是L所有出口结点之必经结点； x在L中没有其他定值点；L中引用x处只有P点的定值才能到达。 x在出L之后不再活跃；x在L中没有其他定值点 L中引用x处只有P点的定值才能到达。 则将满足条件的不变运算,按查不变运 运算次序,依次外提到L的前置结点中。,10.7.5 归纳变量删除,循环归纳变量:在循环中，其值的每次改变都增加或减少某个固定的常量 基本归纳变量：在循环中只有一个形如i := i c的i，其中c是常量 其它归纳变量:在循环中仅定值一次，并且其值是某个基本归纳变量的线性函数。,10.7.5 归纳变量删除,寻找归纳变量 找出所有基本归纳变量i := i c，描述为(i, 1, 0)的形式 寻找只有一个赋值的k，其形式为 k := j*b, k := b*j, k := j / b, k := j b, k := b j 其中b是常数，j是基本的或非基本的归纳变量 若j 是基本的且k := j * b，则k属j族，为(j,b,0) 若j属I族，为(i, c, d)，k := b * j，则k属I族，为(i, b * c, b * d ),10.7.5 归纳变量删除,循环B2 i族 i: (i, 1, 0) i族 t2 : (i, 4, 0) 循环B3 j族 j: (j, 1, 0) j族 t4 : (j, 4, 0) 循环B2、 B3、 B4和B5 和上面一样的i族和j族,10.7.5 归纳变量删除,归纳变量的强度削弱 i族 j: (i,c,d) 用j := s代替j的赋值 在每个赋值i := i + n的后面，紧接着它加上 s := s + c * n i族 s: (s,c,d) 在前置块的末尾加上 s := c * i /* 如果c为1，则s := i */ s := s + d /* 如果d为0则被省略 */,10.7.5 归纳变量删除,循环B2 i族 i: (i, 1, 0) i族 t2 : (i, 4, 0) s2 := 4 * i（前置结点） s2 := s2 + 4（循环内） t2 := s2 （循环内） 循环B3 j族 j: (j, 1, 0) j族 t4 : (j, 4, 0) s4 := 4 * j（前置结点） s4 := s4 + 4（循环内） t4 := s4 （循环内）,10.7.5 归纳变量删除,归纳变量删除 if i relop x goto B的测试（x不是归纳变量） 取i族的某个j，优先取c=1和d = 0 的j:(i,c,d） 把每个含i的测试改成对j的测试(假定c为正) r := c * x /* 如果c等于1，则r := x */ r := r + d /* 如果d为0，则省略 */ if j relop r goto B,10.7.5 归纳变量删除,归纳变量删除 if i relop x goto B的测试（x不是归纳变量） 取i族的某个j，优先取c=1和d = 0 的j:(i,c,d） 把每个含i的测试改成对j的测试(假定c为正) r := c * x /* 如果c等于1，则r := x */ r := r + d /* 如果d为0，则省略 */ if j relop r goto B if i1 relop i2 goto B的测试 最简单的情况是j1:(i1,c1,d1)和j2:(i2,c2,d2)，还有c1=c2且d1=d2 那么，i1 relop i2等价于j1 relop j2,10.7.5 归纳变量删除,归纳变量删除 if i relop x goto B的测试（x不是归纳变量） 取i族的某个j，优先取c=1和d = 0 的j:(i,c,d） 把每个含i的测试改成对j的测试(假定c为正) r := c * x /* 如果c等于1，则r := x */ r := r + d /* 如果d为0，则省略 */ if j relop r goto B if i1 relop i2 goto B的测试 最简单的情况是j1:(i1,c1,d1)和j2:(i2,c2,d2)，还有c1=c2且d1=d2 那么，i1 relop i2等价于j1 relop j2 更复杂的情况，测试的替换可能没有价值,10.7.5 归纳变量删除,循环B2 i族 i: (i, 1, 0) i族 t2 : (i, 4, 0) s2 := s2 + 4（循环内） s2 := 4 * i（前置结点） 循环B3 j族 j: (j, 1, 0) j族 t4 : (j, 4, 0) s4 := s4 + 4（循环内） s4 := 4 * j（前置结点）,10.7.5 归纳变量删除,循环B2 i族 i: (i, 1, 0) i族 t2 : (i, 4, 0) s2 := s2 + 4（循环内） s2 := 4 * i（前置结点） 循环B3 j族 j: (j, 1, 0) j族 t4 : (j, 4, 0) s4 := s4 + 4（循环内） s4 := 4 * j（前置结点） 测试 i = j由s2 = s4代替，i和j都被删除,10.7.5 归纳变量删除,强度削弱和删除归纳变量算法可描述如下： (1) 寻找循环中的所有基本归纳变量i 。 (2)寻找与基本归纳变量同族的归纳变量j 及其线性函数，通常它们具有下列形式： j:=c*i，j:=i*c，j:=i/c，j:=ic，j:=ci。 (3)设归纳变量j 与基本归纳变量i 的函数为j=c1*i+c2，可按下列步骤作强度削弱： 在前置结点原有代码后增加s:=c1*I, s:=s+c2,其中s为增设的临时变量，c2=0时，后一语句可省略,10.7.5 归纳变量删除, 循环中原来j的赋值改为j:=s； 在基本归纳变量递归赋值语句i:= ic0后增加 t:=c1*c0 s:=st 其中t为增设的临时变量。,10.7.5 归纳变量删除,(4) 上述复写j:=s至循环中引用j 处的通路上没有对s的重新定值，j 在循环出口后不活跃,则作复写传播,即删除j:=s，所有引用j处改为引用s。 (5) 基本归纳变量i在循环出口后不活跃，循环中除递归赋值本身外，只在形如if i rop x goto A或if x rop i goto A控制语句中被引用，则按下 列步骤删除归纳变量。 选一与i同族的归纳变量j,使j=c1*i+c2的函数应最简单, j在循环出口之后是活跃的，或j在循环中还有其他引用；,10.7.5 归纳变量删除,用下列语句 x:=c1*x x:= x+c2 if j rop x goto A(或if x rop j goto A) 来代替if i rop x gotoA(或if x rop i goto A)； 删除循环中i的递归赋值语句，i:=ic。,10.8 各种优化的综合考虑,考虑三个问题: 中间代码形式 各种优化的次序 进行优化的代价,10.8 各种优化的综合考虑,各种优化的次序 1 数据流分析(DU,UD链,活跃变量) 2 优化 a. 循环优化(代码外提,强度削弱,删除归纳变量) b.全局优化(合并已知量,常数传播) c.基本块内优化(删除局部公共子表达式,合并已知量,删除无用赋值),10.8 各种优化的综合考虑,d. 全局复写传播 (删除无用复写) e.复写传播 可能产生新的公共子表达式,重复a-e.,本 章 要 点,对各类优化的理解，包括常量合并、公共子表达式删除、复写传播、死代码删除、循环优化（代码外提、归纳变量删除、强度削弱）等 掌握建立程序流图的算法和流图中自然循环的识别算法 对各种数据流分析方程的认识和区分，和对这些方程迭代求解方法的理解 了解如何利用控制流分析的信息和各种数据流分析的信息进行各类代码改进变换,例题与习题解答,例10。1试对以下基本块B1应用DAG进行优化。 B1: A:=B*C D:=B/C E:=A+D F:=E*2 G:=B*C H:=G*G F:=H*G L:=F M:=L 并就以下两种情况分别写出优化后的四元式序列：,（1）假设G、L、M在基本块后面背引用； （2）假设只有L在基本块后被引用。 解：对于B1其DAG图：,n1,B,n2,C,n3,*,A,G,n4,/,D,n5,+,E,n6,2,n7,F,*,n8,*,H,n9,*,F,L,M,(1)若只有G、L、M在基本块后被引用，则优化为： G := B*C H := G*G L := H*G M := L,(2) 若只有L在基本块后被引用，则优化为： G := B*C H :=G*G L := H*G 例10。2 试写出以下程序段 for I := 1 to M do for j := 1 to N do AI, j := BI, j 的三地址代码，然后求出其中的循环，并进行循环优化。 解： 三地址代码：,(1) I := 1 (2) j := 1,B1,(3) If IM goto (30),(4) If jN goto (13),(5) T1 := I * N (6) T2 := T1 + j (7) T3 := N + 1 (8) T4 := add(A)-T3 (9) T5 := add(B)-T3 (10) T4T2 := T5T2 (11) j := j + 1 (12) Goto (4),(13) I := I+1 (14) j :=1 (15) goto (3),(30),B2,B3,B4,B5,B6,代码外提：,（1）I := 1 (2) j := 1,(7) T3 := N + 1 (8) T4 := add(A)-T3 (9) T5 := add(B)-T3,(3) If IM goto (30),(5) T1 := I * N,(4) If j N goto (13),(6) T2 := T1 + j (10) T4T2 := T5T2 (11) j := j + 1 (12) goto (4),(13) I := I + 1 (14) j := 1 (15) goto (3),(30),B1,B2,B2,B3,B3,B4,B5,B6,强度消弱：,I := 1 j := 1,(7) T3 := N + 1 (8) T4 :=add(A)- T3 (9) T5 :=add(B)-T3 (5) T1 :=I * N,(3) if I M goto (30),(4) If j N goto (13),(6) T2 := T1 + j (10) T4T2 := T5T2 (11) j := j + 1 (12) Goto (4),(13) I := I + 1 (5) T1 := T1 + N (14) j := 1 (15) Goto (3),(30),B1,B2,B2,B3,B4,B5,B6,强度消弱(1):,（1）I := 1 (2) j := 1,(7) T3 := N + 1 (8) T4 := add(A)-T3 (9) T5 := add(B)-T3 (5) T1 := I * N,(3) If IM goto (30),(5) T2 := T1 + j,(4) If j N goto (13),(10) T4T2 := T5T2 (11) j := j + 1 (6) T2 := T2 + 1 (12) goto (4),(13) I := I + 1 (5) T1 := I + N (14) j := 1 (15) goto (3),(30),B1,B2,B2,B3,B3,B4,B5,B6,删除归纳变量：,I := 1 j := 1,(7) T3 := N + 1 (8) T4 := add(A) T3 (9) T5 := add(B) T3 (5) T1 := I*N (3) R := M*N,(3) If T1 R goto (30),(4) Q := T1 + N,(4) If T2 Q goto (13),(10) T4T2 := T5T2 (11) T2 := T2 + 1 (12) Goto (4),(13) T1 := T1 + 1 (14) T2 := T1 + 1 (15) Goto (3),(30),B1,B2,B2,B3,B3,B4,B5,B6,例10。3给出下面循环语句的流图并进行优化： 语句： for I := 1 to 10 do AI, J*5 := J+2 （其中 A 为10X10二维数组） 解:,（1）I := 1,(2) If I10 goto (11),(3) T1:= J*5 (4) T2 := I*10 (5) T3 := T1 + T2 (6）T4 := add(A)-11 (7) T5 := J + 2 (8) T4T3 := T5 (9) I := I + 1 (10) Goto B2,(11),B1,B2,B3,B4,代码外提：,（1） I := 1,(3）T1 := J* 5 (6) T4 :=add(A) 11 (7) T5 := J + 2,(2) If I10 goto (11),(4) T2 :=I * 10 (5) T3 := T1 + T2 (8) T4T3 ：= T5 (9) I := I + 1 (10) Goto B2,(11),B1,B2,B2,B3,B4,强度消弱：,（1） I := 1,(3) T1 := J * 5 (6）T4 := Add(A) 11 (7) T5 := J + 2 (4) T2 := I * 10 (5) T3 := T1 + T2,(2) If I10 goto (11),(8)T4T3 := T5 (9) I := I + 1 (4) T2 := T2 + 10 (5) T3 := T3 + 10 (10) goto B2,(11),B1,B2,B2,B3,B4,删除归纳变量：,(1) I := 1,(3) T1 := J * 5 (6) T4 := Add(A) 11 (7) T5 := J + 2 (4) T2 := I * 10 (5) T3 := T1 + T2 (2) R := T1 + 100,(2) If T3 R goto (11),(8) T4T3 := T5 (5) T3 := T3 + 10 (10) Goto B2,(11),例 题 1,UNIX 下的C编译命令cc的选择项g和O的解释如下, 其中 dbx的解释是“dbx is an utility for source-l