编译器笔记56-代码优化-作用于归纳变量的强度削弱和归纳变量的删

作用于归纳变量的强度削弱

• 对于一个变量x，如果存在一个正的或负的常量c，使得每次x被赋值时，它的值总是增加c，则称x为归纳变量。
• 如果循环L中的变量i只有形如i =i+c的定值(c是常量)，则称i为循环L的基本归纳变量。
• 如果j = c×i+d，其中i是基本归纳变量，c和d是常量，则j也是一个归纳变量，称j属于i。(基本归纳变量i属于它自己的族)
• 每个归纳变量都关联一个三元组。如果j = c×i+d，其中i是基本归纳变量，c和d是常量，则与j相关联的三元组是(i, c, d)。

例.png

归纳变量检测算法

输入：带有循环不变计算信息和到达定值信息的循环L
输出：一组归纳变量

方法：

1. 扫描L的语句，找出所有基本归纳变量。在此要用到循环不变计算信息。与每个基本归纳变量i相关联的三元组是(i, 1, 0)。

2. 寻找L中只有一次定值的变量k，它具有下面的形式：k=c′×j+d′ 。其中c′和d′是常量，j是基本的或非基本的归纳变量

• 如果j是基本归纳变量，那么k属于j族。k对应的三元组可以通过其定值语句
• 如果j不是基本归纳变量，假设其属于i族， k的三元组可以通过j 的三元组和k的定值语句来计算，此时我们还要求：

xxx.png

作用于归纳变量的强度削弱算法

输入：带有到达定值信息和已计算出的归纳变量族的循环L
输出：修改后的循环
方法：对于每个基本归纳变量i，对其族中的每个归纳变量j ：(i, c, d)
执行下列步骤

1. 建立新的临时变量t。如果变量j1和j2具有相同的三元组，则只为它们建立一个新变量。
2. 用j=t代替对j的赋值。
3. 在L中紧跟定值i=i+n之后，添加t=t+c*n。将t放入i族，其三元组为(i, c, d)。
4. 在前置节点的末尾，添加语句t=ci和t=t+d，使得在循环开始的时候t=ci+d=j。

例.png

归纳变量的删除

对于在强度削弱算法中引入的复制语句j=t，如果在归纳变量j的所有引用点都可以用对t的引用代替对j的引用，在循环的出口处不活跃，则可以删除复制语句j=t。

例.png

对于在强度削弱算法中引入的复制语句j=t，如果在归纳变量j的所有引用点都可以用对t的引用代替对j的引用，并且j在循环的出口处不活跃，则可以删除复制语句j=t。

强度削弱后，有些归纳变量的作用只是用于测试。如果可以用对其它归纳变量的测试代替对这种归纳变量的测试，那么可以删除这种归纳变量。

删除仅用于测试的归纳变量

• 对于仅用于测试的基本归纳变量i ，取i 族的某个归纳变量j(尽量使得c、d 简单，即c=1或d=0的情况)。把每个对i的测试替换成为对j的测试。

1. (relop i x B)替换为(relop j c*x+d B) ，其中x不是归纳变量，并假设c>0。

2. (relop i1 i2 B)，如果能够找到三元组j1(i1, c, d)和j2(i2, c, d)，那么可以将其替换为(relop j1 j2 B) (假设c>0)。否则，测试的替换可能是没有价值的

• 如果归纳变量i不再被引用，那么可以删除和它相关的指令。