強度折減

范例

以下是一个使用强度折减范例，他会减少所有出现在计算阵列索引位置的循环乘法
想像一个简单的循环，它设定一个阵列给一个已知的矩阵
for (i = 0; i < n; i++)
  {
    for (j = 0; j < n; j++)
      {
         A[i,j] = 0.0;
      } 
    A[i,i] = 1.0;
  }

中间码

编译器将会视这段程式码为

0010  // for (i = 0, i < n; i++)
0020    {
0030      r1 = #0                        // i = 0
0040  G0000:
0050      load r2, n                     // i < n
0060      cmp r1, r2
0070      bge G0001
0080  
0090      // for (j = 0; j < n; j++)
0100        {
0110           r3   = #0                 // j = 0
0120  G0002:
0130           load r4, n                // j < n
0140           cmp r3, r4
0150           bge G0003
0160  
0170           // A[i,j] = 0.0;
0180           load r7, n
0190           r8  = r1 * r7             // 計算元素i * n + j
0200           r9  = r8 + r3
0210           r10 = r9 * #8             // 計算實際位置0220           fr3 = #0.0
0230           fstore fr3, A[r10]
0240  
0250           r3 = r3 + #1              // j++
0260           br G0002
0270        }
0280  G0003:
0290      // A[i,i] = 1.0;
0300      load r12, n                    // 計算元素i * n + i
0310      r13 = r1 * r12               
0320      r14 = r13 + r1
0330      r15 = r14 * #8                 // 計算實際位置0340      fr4 = #1.0
0350      fstore fr4, A[r15]
0360  
0370      //i++
0380      r1 = r1 + #1
0390      br G0000
0400    }
0410  G0001:

最佳化

编译器将会开始进行最佳化（并不只有强度折减），循环内的常数（不变式）将会被放到循环外面（Loop-invariant code motion），常数可以在循环外面载入，例如浮点数暂存器fr3 及 fr4。接着辨识出不会改变的变数，例如常数N，这使得一些暂存器在循环内允许被合并，所以r2、r4、r7、r12可以被合并移置循环外或是消除。r8及r13同时有着相同的运算i*n ，所以他们也可以被合并，最内层的循环（0120-0260）已经从11道指令减少为7道指令，为一个还留在最内层循环的乘法为0210行的乘法运算。

0010  // for (i = 0, i < n; i++)
0020    {
0030      r1 = #0                        // i = 0
0050      load r2, n
0130 //   load r4, n     移除，使用 r2
0180 //   load r7, n     移除，使用 r2
0300 //   load r12, n    移除，使用 r2
0220      fr3 = #0.0
0340      fr4 = #1.0
0040  G0000:
0060      cmp r1, r2                     // i < n
0070      bge G0001
0080  
0190      r8  = r1 * r2                  // 計算元素i * n
0310 //   r13 = r1 * r2  移除，使用 r8  // 計算元素i * n
0090      // for (j = 0; j < n; j++)
0100        {
0110           r3   = #0                 // j = 0
0120  G0002:
0140           cmp r3, r2                // j < n
0150           bge G0003
0160  
0170           // A[i,j] = 0.0;
0200           r9  = r8 + r3             // 計算元素i * n + j
0210           r10 = r9 * #8             // 計算實際位置0230           fstore fr3, A[r10]
0240  
0250           r3 = r3 + #1              // j++
0260           br G0002
0270        }
0280  G0003:
0290      // A[i,i] = 1.0;
0320      r14 = r8  + r1                 // 計算元素i * n + i
0330      r15 = r14 * #8                 // 計算實際位置0350      fstore fr4, A[r15]
0360  
0370      //i++
0380      r1 = r1 + #1
0390      br G0000
0400    }
0410  G0001:
还有更多的最佳化要进行，暂存器r3在最内层的循环是一个主要的变数，它每次循环进行都会加1，暂存器r8（在最内层循环是不变式）会与r3家在一起。编译器则是可以消除r3而使用r9，可以使用r9=r8+0 to r8+n-1来取代控制循环的r3 = 0 to n-1，这样将会增加四个指令，并且移除四个指令，但是在内层循环的指令将会更少：

0110  //       r3   = #0     移除// j = 0
0115           r9   = r8                 // 新的賦值0117           r20  = r8 + r2            // 新的限制0120  G0002:
0140  //       cmp r3, r2    移除// j < n
0145           cmp r9, r20               // r8 + j < r8 + n = r20
0150           bge G0003
0160  
0170           // A[i,j] = 0.0;
0200  //       r9  = r8 + r3 移除// 計算元素i * n + j
0210           r10 = r9 * #8             // 計算實際位置0230           fstore fr3, A[r10]
0240  
0250  //       r3 = r3 + #1  移除// j++
0255           r9 = r9 + #1              // new loop variable
0260           br G0002
现在r9是一个循环变数，但他的行为是与8相乘，这里我们可以进行一些强度折减，与8相成的行为可以被折减为连续的增加8次，那么我们在循环内就没有乘法运算：

0115           r9   = r8                 // 新的賦值0117           r20  = r8 + r2            // 新的限制0118           r10  = r8 * #8            // r10的初始值0120  G0002:
0145           cmp r9, r20               // r8 + j < r8 + n = r20
0150           bge G0003
0160  
0170           // A[i,j] = 0.0;
0210  //       r10 = r9 * #8    移除// 計算實際位置0230           fstore fr3, A[r10]
0240  
0245           r10 = r10 + #8            // 利用強度折減取代乘法0255           r9 = r9 + #1              // 迴圈變數0260           br G0002
暂存器r9 及 r10 （= 8*r9）并非同时需要，r9在循环内可以被消除，现在循环为五个指令

0115  //       r9   = r8         移除0117           r20  = r8 + r2            // 限制
0118           r10  = r8 * #8            // r10的初始值0119           r22  = r20 * #8           // 新的限制0120  G0002:
0145  //       cmp r9, r20       移除// r8 + j < r8 + n = r20
0147           cmp r10, r22              // r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150           bge G0003
0160  
0170           // A[i,j] = 0.0;
0230           fstore fr3, A[r10]
0240  
0245           r10 = r10 + #8            // 利用強度折減取代乘法0255  //       r9 = r9 + #1      移除// 迴圈變數0260           br G0002

外层循环

回到完整的程式:

0010  // for (i = 0, i < n; i++)
0020    {
0030      r1 = #0                        // i = 0
0050      load r2, n
0220      fr3 = #0.0
0340      fr4 = #1.0
0040  G0000:
0060      cmp r1, r2                     // i < n
0070      bge G0001
0080  
0190      r8   = r1 * r2                 // 計算元素i * n
0117      r20  = r8 + r2                 // 限制
0118      r10  = r8 * #8                 // r10的初始值0119      r22  = r20 * #8                // 限制
0090      // for (j = 0; j < n; j++)
0100        {
0120  G0002:
0147           cmp r10, r22              // r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150           bge G0003
0160  
0170           // A[i,j] = 0.0;
0230           fstore fr3, A[r10]
0240  
0245           r10 = r10 + #8            // 利用強度折減取代乘法0260           br G0002
0270        }
0280  G0003:
0290      // A[i,i] = 1.0;
0320      r14 = r8  + r1                 // 計算元素i * n + i
0330      r15 = r14 * #8                 // 計算實際位置0350      fstore fr4, A[r15]
0360  
0370      //i++
0380      r1 = r1 + #1
0390      br G0000
0400    }
0410  G0001:
现在有四个乘法在外层的循环，并且使用到会递增的r1，在0190行的r8 = r1*r2 可以被强度折减，我们可以在进入循环之前（0055）就设置他，并且在循环的最底部进行与r2的运算（0385）。
数值 r8*8 （在0118）可以被强度折减，借由将它初始化（0056）及当r8增加时（0386）才加上8*r2。
在0117，循环内的暂存器r20 可以会加上一个常数（或是不变式）r2 ，在加上之后，在0119行会与8相乘，并且建立一个r22来储存它。乘法运算可以借由在循环内增加8*r2 来进行强度折减。

0010  // for (i = 0, i < n; i++)
0020    {
0030      r1 = #0                        // i = 0
0050      load r2, n
0220      fr3 = #0.0
0340      fr4 = #1.0
0055      r8  = r1 * r2                  // 設置 r8 的初始值0056      r40 = r8 * #8                  // 設置初始值為r8 * 8
0057      r30 = r2 * #8                  // 為了 r40 而增加0058      r20 = r8 + r2                  // 從 0117 複製過來0058      r22 = r20 * #8                 // r22的初始值0040  G0000:
0060      cmp r1, r2                     // i < n
0070      bge G0001
0080  
0190  //  r8   = r1 * r2    移除// 計算元素i * n
0117  //  r20  = r8 + r2    移除- 無用的程式碼0118      r10  = r40                     // 強度折減： expression to r40
0119  //  r22  = r20 * #8   移除// 強度折減0090      // for (j = 0; j < n; j++)
0100        {
0120  G0002:
0147           cmp r10, r22              // r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150           bge G0003
0160  
0170           // A[i,j] = 0.0;
0230           fstore fr3, A[r10]
0240  
0245           r10 = r10 + #8            // 利用強度折減取代乘法0260           br G0002
0270        }
0280  G0003:
0290      // A[i,i] = 1.0;
0320      r14 = r8  + r1                 // 計算元素i * n + i
0330      r15 = r14 * #8                 // 計算實際位置0350      fstore fr4, A[r15]
0360
0370      //i++
0380      r1  = r1 + #1
0385      r8  = r8 + r2                  // 強度折減： r8 = r1 * r2
0386      r40 = r40 + r30                // 強度折減： 消除運算式r8 * 8
0388      r22 = r22 + r30                // 強度折減： r22 = r20 * 8  
0390      br G0000
0400    }
0410  G0001:

最后的乘法

最后留在两个循环内的，仅剩下一个乘法运算（0330行）在外层的循环，而在内的循环则已经没有任何的层法运算：

0010  // for (i = 0, i < n; i++)
0020    {
0030      r1 = #0                        // i = 0
0050      load r2, n
0220      fr3 = #0.0
0340      fr4 = #1.0
0055      r8  = r1 * r2                  // 設置 r8 的初始值0056      r40 = r8 * #8                  // 將初始值設定為r8 * 8
0057      r30 = r2 * #8                  // 為了 r40 而增加0058      r20 = r8 + r2                  // 從 0117 複製過來0058      r22 = r20 * #8                 // 設置 r22 的初始值0040  G0000:
0060      cmp r1, r2                     // i < n
0070      bge G0001
0080  
0118      r10  = r40                     // 強度折減： expression to r40
0090      // for (j = 0; j < n; j++)
0100        {
0120  G0002:
0147           cmp r10, r22              // r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150           bge G0003
0160  
0170           // A[i,j] = 0.0;
0230           fstore fr3, A[r10]
0240  
0245           r10 = r10 + #8            // 用強度折減消除乘法0260           br G0002
0270        }
0280  G0003:
0290      // A[i,i] = 1.0;
0320      r14 = r8  + r1                 // 計算元素i * n + i
0330      r15 = r14 * #8                 // 計算元素位置0350      fstore fr4, A[r15]
0360
0370      //i++
0380      r1  = r1 + #1
0385      r8  = r8 + r2                  // 強度折減： r8 = r1 * r2
0386      r40 = r40 + r30                // 強度折減：消除運算式r8 * 8
0388      r22 = r22 + r30                // 強度折減： r22 = r20 * 8  
0390      br G0000
0400    }
0410  G0001:
在0320行，r14是r8及r1的总和，而r8及r1在循环内将被增加，暂存器r8则与r2 (=n)相加，而r1则与1相机。所以，r14则借由每次在循环内与n+1相加，最后一个循环乘法在0330行，可以借由增加(r2+1)*8 来进行强度折减。

0010  // for (i = 0, i < n; i++)
0020    {
0030      r1 = #0                        // i = 0
0050      load r2, n
0220      fr3 = #0.0
0340      fr4 = #1.0
0055      r8  = r1 * r2                  // 設置 r8 的初始值0056      r40 = r8 * #8                  // 將初始值設定為r8 * 8
0057      r30 = r2 * #8                  // 為了 r40 而增加0058      r20 = r8 + r2                  // 從 0117 複製過來0058      r22 = r20 * #8                 // 設置 r22 的初始值005A      r14 = r8 + #1                  // 從 0320 複製過來005B      r15 = r14 * #8                 // r15的初始值(0330)
005C      r49 = r2 + 1
005D      r50 = r49 * #8                 // 強度折減：increment
0040  G0000:
0060      cmp r1, r2                     // i < n
0070      bge G0001
0080  
0118      r10  = r40                     // 強度折減： expression to r40
0090      // for (j = 0; j < n; j++)
0100        {
0120  G0002:
0147           cmp r10, r22              // r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150           bge G0003
0160  
0170           // A[i,j] = 0.0;
0230           fstore fr3, A[r10]
0240  
0245           r10 = r10 + #8            // 用強度折減消除乘法0260           br G0002
0270        }
0280  G0003:
0290      // A[i,i] = 1.0;
0320  //  r14 = r8  + r1     移除// 無用的程式碼0330  //  r15 = r14 * #8     移除// 強度折減0350      fstore fr4, A[r15]
0360
0370      //i++
0380      r1  = r1 + #1
0385      r8  = r8 + r2                  // 強度折減： r8 = r1 * r2
0386      r40 = r40 + r30                // 強度折減： 消除運算式r8 * 8
0388      r22 = r22 + r30                // 強度折減： r22 = r20 * 8
0389      r15 = r15 + r50                // 強度折減： r15 = r14 * 8  
0390      br G0000
0400    }
0410  G0001:
但是仍然还有一些工作要做，一开始常数折叠将会辨识出r1=0 ，许多指令将会被清除，暂存器r8 并不会在循环内被使用，所以他也可以消失
接着，r1只会被使用在控制循环，所以r1可以被许多归纳变数取代，像是r40。当i为0 <= i < n，则暂存器r40则变成0 <= r40 < 8 * n * n。

0010  // for (i = 0, i < n; i++)
0020    {
0030  //  r1 = #0                        // i = 0, 變成無用程式碼0050      load r2, n
0220      fr3 = #0.0
0340      fr4 = #1.0
0055  //  r8  = #0         移除// r8 不再被使用0056      r40 = #0                       // r8 * 8的初始值0057      r30 = r2 * #8                  // 為了 r40 增加
0058  //  r20 = r2         移除// r8 = 0, 變成無用程式碼0058      r22 = r2  * #8                 // r20 = r2
005A  //  r14 =       #1   移除// r8 = 0, 變成無用程式碼005B      r15 =       #8                 // r14 = 1
005C      r49 = r2 + 1
005D      r50 = r49 * #8                 // 強度折減： increment
005D      r60 = r2 * r30                 // r40新的限制0040  G0000:
0060  //  cmp r1, r2       移除// i < n; 歸納變數取代0065      cmp r40, r60                   // i * 8 * n < 8 * n * n
0070      bge G0001
0080  
0118      r10  = r40                     // 強度折減： expression to r40
0090      // for (j = 0; j < n; j++)
0100        {
0120  G0002:
0147           cmp r10, r22              // r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150           bge G0003
0160  
0170           // A[i,j] = 0.0;
0230           fstore fr3, A[r10]
0240  
0245           r10 = r10 + #8            // 用強度折減消除乘法0260           br G0002
0270        }
0280  G0003:
0290      // A[i,i] = 1.0;
0350      fstore fr4, A[r15]
0360
0370      //i++
0380  //  r1  = r1 + #1      移除// 無用的程式碼(r40 控制了迴圈)
0385  //  r8  = r8 + r2      移除// 無用的程式碼0386      r40 = r40 + r30                // 強度折減： expression r8 * 8
0388      r22 = r22 + r30                // 強度折減： r22 = r20 * 8
0389      r15 = r15 + r50                // 強度折減： r15 = r14 * 8  
0390      br G0000
0400    }
0410  G0001:

归纳变数(orphan)

归纳变数（Induction variable）或是递回强度折减利用简单运算取代了一个函数内有系统化的来改变变数，这个运算使用了函数之前的数值。在程序编程，这将会涉及到一个包含循环变数的运算式，在宣告式编程，这将会影响到递归 (计算机科学)的参数，举例来说：

f x = ... (2 ** x) ... (f (x + 1)) ...
会变成

f x = f' x 1
where
  f' x z = ... z ... (f' (x + 1) (2 * z)) ...
昂贵的运算(2 ** x) 已经被递回函式中相对便宜的(2 * x) 所取代。