在軟體工程領域，強度折減（Strength reduction）是一個編譯器最佳化技術，它將昂貴的運算以相同但是相對便宜的運算取代，最經典的範例就是將乘法轉換為使用迴圈的連續加法，這經常使用在陣列的定址。(Cooper, Simpson & Vick 1995，第1頁)
強度折減的範例包含：
- 使用迴圈及加法取代乘法運算
- 使用迴圈及乘法取代指數運算
程式碼分析
大部份程式的執行時間通常都是花費在一些相當小的程式段，這些程式段通常都在迴圈之內不斷的執行。
編譯器使用一些方法來辨識迴圈以及迴圈內暫存器數值的特點，編譯器可利用強度折減來辨識：
- 循環不變式（Loop invariants），迴圈內不會改變的數值。
- 歸納變數（Induction variables），在迴圈內每次運行時，都會增加或是減少一個固定量的變數。
循環不變式本質上在迴圈內是個常數，但他們的數值可能在迴圈外會改變。歸納變數則是會被改變一個已知的量。而在巢狀回圈的情況之下，一個歸納變數在迴圈外的迴圈內也可以是一個歸納變數。
強度折減會找尋涉及循環不變式以及歸納變數，有些可以被簡化，舉例來說，循環不變式c及歸納變數i的乘法：
c = 8;
for (i = 0; i < N; i++)
{
y[i] = c * i;
}
可以被加法所取代
c = 8;
k = 0;
for (i = 0; i < N; i++)
{
y[i] = k;
k = k + c;
}
範例
以下是一個使用強度折減範例，他會減少所有出現在計算陣列索引位置的迴圈乘法
想像一個簡單的迴圈，它設定一個陣列給一個已知的矩陣
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:
其它強度折減的運算
- 這個部分是有爭議的。
強度折減運算子（Operator strength reduction）使用數學的方法，以更快的運算子取代了緩慢的數學操作，這個優勢將會根據目標CPU以及一些程式（不同的CPU有著不同的可用功能）而有所不同。
- 使用2進位的算數位移或是邏輯位移 來取代整數的乘法及除法。[1]
- 使用常數結合位移、增加或減少來取代整數的乘法。
- 使用常數的乘法、機器整數上有限值域的優勢來取代整數除法。[2]
| 原始的運算
|
取代的運算
|
| y+= 1
|
y++
|
| y%2 != 0
|
y & 1
|
| y = x * 2
|
y = x << 1
|
| y = x / 2
|
y = x >> 1
|
| y = x % 2
|
y = x & 1
|
| y = x * 15
|
y = (x << 4) - x
|
| y = (uint16_t)x / 10
|
y = ((uint32_t)x * (uint32_t)0xCCCD) >> 19)
|
| y = (uint16_t)x / π
|
y = (((uint32_t)x * (uint32_t)0x45F3) >> 16) + x) >> 2)
|
歸納變數 (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) 所取代。
註解
- ^ In languages such as C and Java, integer division has round-towards-zero semantics, whereas a bit-shift always rounds down, requiring special treatment for negative numbers. For example, in Java,
-3 / 2 evaluates to -1, whereas -3 >> 1 evaluates to -2. So in this case, the compiler cannot optimize division by two by replacing it by a bit shift.
- ^ Granlund, Torbjörn; Peter L. Montgomery. Division by Invariant Integers Using Multiplication (PDF). [2013-03-09]. （原始内容存档 (PDF)于2019-06-06）.
参考文献
- Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D., Compilers: Principles, Techniques, and Tools
2nd, 1986, ISBN 978-0-201-10088-4
- Allen, Francis E.; Cocke, John; Kennedy, Ken, Reduction of Operator Strength, Munchnik, Steven S.; Jones, Neil D. (编), Program Flow Analysis: Theory and Applications, Prentice-Hall, 1981, ISBN 978-0-13-729681-1
- Cocke, John; Kennedy, Ken, An algorithm for reduction of operator strength, Communications of the ACM, November 1977, 20 (11): 850–856, S2CID 1092505, doi:10.1145/359863.359888
- Cooper, Keith; Simpson, Taylor; Vick, Christopher, Operator Strength Reduction (PDF), Rice University, October 1995 [April 22, 2010], （原始内容存档 (PDF)于2012-06-04）
本條目部分或全部内容出自以GFDL授權發佈的《自由線上電腦詞典》（FOLDOC）。
