编译原理教程05代码优化.ppt

代码优化的含义 进行代码优化的时间 代码优化的种类 DAG构造过程 DAG构造过程 DAG构造过程 DAG构造过程 DAG构造过程 DAG构造过程 DAG构造过程 DAG构造过程 DAG构造过程 　　3．删除归纳变量 　　如果循环中对变量I只有惟一的形如I=I±C的赋值，且其中C为循环不变量，则称I为循环中的基本归纳变量。 　　如果I是循环中一基本归纳变量，J在循环中的定值总是可化归为I的同一线性函数，也即J=C1*I±C2，其中C1和C2都是循环不变量，则称J是归纳变量，并称它与I同族。一个基本归纳变量也是一归纳变量。 　　一个基本归纳变量除用于其自身的递归定值外，往往只在循环中用来计算其它归纳变量以及控制循环的进行。此时，可以用同族的某一归纳变量来替换循环控制条件中的这个基本归纳变量，从而达到将这个基本归纳变量从程序流图中删去的目的。这种优化称为删除归纳变量或变换循环控制条件。 　　由于删除归纳变量是在强度削弱以后进行的，因此，我们一并给出强度削弱和删除归纳变量的算法如下： 　　(1) 利用循环不变运算信息，找出循环中所有的基本归纳变量。 　　(2) 找出所有其它归纳变量A，并找出A与已知基本归纳变量X的同族线性函数关系FA(X)；即： 　　① 在L中找出形如A=B*C、A=C*B、A=B/C、A=B±C、A=C±B的四元式，其中B是归纳变量，C是循环不变量。 　　② 假设找出的四元式为S：A=C*B，这时有： 　　i. 如果B就是基本归纳变量，则X就是B，A与基本归纳变量B是同族的归纳变量，且A与B的函数关系就是FA(B)=C*B。 　　ii. 如果B不是基本归纳变量，假设B与基本归纳变量D同族且它们的函数关系为FB(D)，那么如果L外B的定值点不能到达S且L中B的定值点与S之间未曾对D定值，则X就是D，A与基本归纳变量D是同族的归纳变量，且A与D的函数关系是FA(D)=C*B=　C*FB(D)。 　　寻找由回边组成循环的算法如下： main (?) { stack=空; /*stack是一个工作栈*/ loop={d}; /*loop是所求的循环*/ insert(m); while (stack非空) { 弹出stack栈顶元素m; for (p∈P(m)) /*P(m)为结点m的前驱结点集*/ { insert (p); } } } void insert (m) { if (mloop) { 　loop=loop∪{m}; 　　把m压入栈stack; } } 　　此算法中求回边n→d组成循环的所有结点的方法是：由于循环以d为其惟一入口，n是循环的一个出口，因而只要n不同时是循环入口d，那么n的所有前驱就应属于循环。在求出n的所有前驱之后，只要它们不是循环入口d，就应再继续求出它们的前驱，而这些新求出的所有前驱也应属于循环。然后再对新求出的所有前驱重复上述过程，直到所求出的前驱都是d为止。 　　3．可归约流图 　　一个流图被称为可归约的，当且仅当流图中除去回边之外，其余的边构成一个无环路流图。例如，图5–4中的流图就是一个可归约流图，而图5–6则是一个不可归约流图，因为图5–6中虽然有2→3，但没有3 DOM 2，即2→3不是一个回边，对3→2也是如此。 　　如果程序流图是可归约的，那么程序中任何可能反复执行的代码都会被求回边的算法纳入到一个循环当中。 图5–6 不可归约流图 　　可归约流图是一类非常重要的流图，从代码优化的角度来说，它具有下述重要的性质： 　　(1) 图中任何直观意义下的环路都属于我们所定义的循环。 　　(2) 只要找出图中的所有回边，对回边应用查找循环的方法，就可以找出流图中的所有循环。 　　(3) 图中任意两个循环要么嵌套，要么不相交(除了可能有公共的入口结点)，对这类流图进行循环优化较为容易。 　　应用结构程序设计原则写出的程序，其流图总是可归约的；而应用高级语言写出的程序，其流图往往也是可归约的。 　　例5.5 四元式序列如下： 　　(1) J=0； 　　(2) L1： I=0； 　　(3) if I 8 goto L3; 　　(4) L2： A=B+C； 　　(5) B=D*C; 　　(6) L3： if B=0 goto L4; 　　(7) write B; 　　(8) goto L5; 　　(9) L4 ： I= I+1; 　　(10) if I8 goto L2; 　　(