删除归纳变量-《编译原理与实践》

删除归纳变量也是一种循环优化技术。首先了解一下什么是归纳变量，然后，再来探讨如何删除归纳变量。

如果循环中对变量I只有唯一的形如I：=I±C的赋值，且其中C为循环不变量，则称I为循环中的基本归纳变量。进一步，如果I是循环中的基本归纳变量，J在循环中的定值总是可以化为I的同一线性函数，即J：=C1*I±C2，C1和C2都是循环不变量，则称J为归纳变量，并称J与I同族。显然，基本归纳变量也是归纳变量。可以在不引用I的值的情况下，根据I的递增或递减规律，来完成J的递增或者递减。如果一个归纳变量在循环的每次迭代中都改变相同的量，这就是线性归纳变量。

循环中的基本归纳变量除用于计算其他归纳变量外，还用来控制循环的进行。如果在循环中有两个或多个同族的归纳变量，可以只用其中的一个来代替基本归纳变量进行循环的控制，而去掉其余的归纳变量，这种做法称为删除归纳变量。

删除归纳变量的算法可以描述如下：

（1）利用循环不变运算信息，找出循环中所有的基本归纳变量I。

（2）找出其他所有的归纳变量J，并找出J与已知基本归纳变量I的同族线性函数关系FJ（I）。(https://www.xing528.com)

（3）对（2）中找出的每一个归纳变量J，进行强度削弱。

（4）删除对归纳变量J的无用赋值。

（5）若基本归纳变量I在循环出口之后不是活跃的，并且在循环中，除在其自身的递归赋值中被引用外，只在形如if I rop X goto L的代码中被引用，则可选取一个与I同族的归纳变量J来替换I进行条件控制，最后，删除循环中对I的递归赋值代码。

强度削弱后，一些归纳变量在循环中根本不被使用，另一些也只是用于和循环做比较。这些归纳变量都可以删除。如果一个变量在循环L的所有出口都是死去的，并且它只用于对自身的定值，L中这个变量是无用的。无用变量的所有定值都可以被删除。如果变量s只是用于与循环不变量进行比较，或者只是用于自身的定值，并且在同一族归纳变量中，还存在着另外某个不是无用的归纳变量，那么s就是一个几乎无用的变量。通过修改循环不变量与这个几乎无用的变量的比较，使之与相关的归纳变量进行比较，可以使一个几乎无用的变量变成一个无用变量。