強度折減

範例

以下是一個使用強度折減範例，他會減少所有出現在計算陣列索引位置的迴圈乘法
想像一個簡單的迴圈，它設定一個陣列給一個已知的矩陣
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) 所取代。