循环优化

本文概述

• 1.代码运动
• 2.感应变量消除
• 3.强度降低

循环优化是最有价值的与机器无关的优化, 因为程序的内部循环占用了程序员大量的时间。

如果我们减少一个内部循环中的指令数量, 那么即使我们增加该循环之外的代码量, 也可以改善程序的运行时间。

对于循环优化, 以下三种技术很重要：

1. 代码运动
2. 感应变量消除
3. 强度降低

1.代码运动

代码运动用于减少循环中的代码量。这种转换采用一条语句或表达式, 该语句或表达式可以移到循环体之外, 而不会影响程序的语义。

例如

在while语句中, limit-2方程是一个循环不变方程。

while (i<=limit-2)     /*statement does not change limit*/
After code motion the result is as follows:
          a= limit-2;
          while(i<=a)    /*statement does not change limit or a*/

2.感应变量消除

归纳变量消除用于替换内部循环中的变量。

它可以减少循环中的添加数量。它改善了代码空间和运行时性能。

在该图中, 我们可以将分配t4：= 4 * j替换为t4：= t4-4。出现的唯一问题是, 当我们第一次进入块B2时, t4没有值。因此, 我们在块B2的入口处放置了一个关系t4 = 4 * j。

3.强度降低

• 强度降低用于在目标机器上以较便宜的价格代替昂贵的操作。
• 常数的加法比乘法便宜。因此, 我们可以在循环内用加法代替乘法。
• 乘法比取幂便宜。因此, 我们可以在循环内用乘法代替幂运算。

例：

while (i<10)
        {
j= 3 * i+1;
a[j]=a[j]-2;
i=i+2;
        }

强度降低后, 代码将为：

s= 3*i+1;
      while (i<10)
       {
            j=s;
            a[j]= a[j]-2;
            i=i+2;
            s=s+6;
       }

在上面的代码中, 计算s = s + 6比j = 3 * i便宜