第十章代码优化

第十章代码优化内容摘要：

r(v1=v10。 v1v1f。 v1++) { D2 = D1+C2’*V20。 for(v2=v20。 v2v2f。 v2++) { … *D2…。 D2+=C2’。 } D1+= C1’。 } 下标地址优化计算的条件  相应的数组是常界数组：数组的上下界都是常量。  下标变量中的下标表达式是循环控制变量的线性表达式。  满足上述条件的称为可优化下标变量。  在 C语言中，要求循环控制变量每次循环的变动是常数。 循环优化的实现  循环结构的识别  数据流分析  代码转换 循环结构的识别  对于源程序来说，识别循环是比较方便的。 但是代码的优化是针对四元式序列的，所以识别循环必须针对流图进行。  定义 如果流图中，从某个初始节点出发，每一条到达节点 n的路径都必须经过 m，那么称 m是节点 n的支配节点。 记为 m dom n。  任何节点都是自己的支配节点。  m为 n的前驱， n为 m的后继。  直接支配节点：从初始节点到达 n的所有路径上，节点n的最后一个支配节点称为直接支配节点。 循环满足的条件  循环必须有唯一的入口节点，称为首节点。  对于循环中任何一个节点，必定至少有一个路径回到首节点。 回边和自然循环  定义 假定流图中存在两个节点 M和 N满足 M dom N。 如果存在从节点 N到 M的有向边NM，那么这条边称为 回边。  定义 在流图中，给定一个回边 NM，与这个回边对应的自然循环为： M，以及所有可以不经过 M而到达 N的节点。 M为该循环的首节点。  用节点的集合表示自然循环。 自然循环的例子  3 dom 4  回边 43  4 dom 7  回边 74  107的自然循环{7， 8， 10}  74的自然循环{4,5,6,7,8,10}  43， 83的自然循环{3,4,5,6,7,8,10} 1 2 3 4 5 6 7 8 9 10 回边寻找算法  首先列出所有从首节点开始，不带圈的路径。  节点 N的 支配节点集 是满足以下条件的节点 M：  所有包含 N的路径 P, M都在 N的前面出现。  回边集合如下：  {NM | N是一个节点， M在 N的支配节点集中 } 寻找自然循环的算法  输入 :回边 {NM}。 输出 : 回边对应的自然循环 .  算法 : 设置 loop={N,M}。 push(stack, N)。 while nonempty(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中。  如果 NM不是回边，那么，首节点会被加入到 loop中。 此时算法不能得到自然循环。 相关概念  通常，循环互不相交，或者一个在另外一个里面。  内循环：不包含其他循环的循环称为内循环。  如果两个循环具有相同的首节点，那么很难说一个包含另外一个。 此时把两个循环合并。 B0 B1 B2 B3 可归约流图  可归约流图 ：删除了其中回边之后，可以构成无环有向图的流图。  特性：不存在循环外向循环内部的转移，进入循环必须通过其首节点。  实际的程序对应的流图一般都是可归约的流图。  没有 goto语句的结构化程序的流图总是可归约的。 一般使用 goto语句的程序也是可归约的。 B1 B2 B3 数据流分析相关概念  变量获得值的方式：  通过赋值语句；  通过输入语句；  通过过程形式参数；  点 ：流图基本块中的位置，包括：第一个四元式之前，两个相邻四元式之间，和最后的四元式之后。  定义 ：使变量 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 is in P[B]  OUT[B] = GEN[B] U (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 is in P[B]。 OUT[B] = GEN[B] ∪ (IN[B]KILL[B])。 oldout = OUT[B]。 if(OUT[B] != oldout) change = TRUE。 } } 算法例子  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} d1: m 1 i d2: = n j d3: = u2 a d4: + i 1 i d5: j 1 j d6: = u2 a d7: = u3 i B1 B2 B3 B4 计算过程  初始化：  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}。  IN[B4]={d3,d4,d5,d6}。 OUT[B4]={d3,d5,d6,d7}。 活跃变量数据流方程  判断在基本块出口之后，变量的值是否还被引用的这种判断工作称为 活跃变量分析。  消除复制四元式的依据就是对活跃变量的分析。 如果某个变量的值在以后不被引用，那么该复制四元式可以被消除。  对于变量 x和流图上的某个点 p，如果在流图中沿着从p开始的某条路径可以引用 x在 p点的值，则称变量 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] U(L_OUT[B]L_DEF[B])  L_OUT[B] = U L_IN[s]，其中 s遍历 B的所有后继。  变量在某点活跃，表示变量在该点的值在以后会被使用。  第一个方程表示：  如果某个变量在 B中没有定义就使用了，显然，变量在在入口处的值会被使用。  如果这个变量在 B的出口处活跃，并且 B中没有对他进行定义，那么变量在入口处也是活跃的。  第二个方程表示：  在 B的某个后继中会使用该后继的入口处的值，那么他其实也可能使用 B的出口处的值。 活跃变量数据流方程求解  设置初值： L_IN[Bi]=空。  重复执行一下步骤直到 L_IN[Bi]不再改变： for(i=1。 in。 i++) { L_OUT[Bi]=U L_IN[s]。 s是 Bi的后继； L_IN[Bi]=L_USE[Bi] U (L_OUT[Bi]L_DEF[Bi])。 } 活跃变量数据流方程例子  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} d1: m 1 i d2: = n j d3: = u2 a d4: + i 1 i d5: j 1 j d6: = u2 a d7: = u3 i 迭代过程  第一次循环：  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。  表达式的全集：在计算某个流图中的可用表达式的时候，表达。