基本介紹
- 中文名：強度折減
- 外文名：Strength reduction
簡介,程式碼分析,最佳化,其它強度折減的運算,
簡介
在軟體工程領域，強度折減（Strength reduction）是一個編譯器最佳化技術，它將昂貴的運算以相同但是相對便宜的運算取代，最經典的範例就是將乘法轉換為使用循環的連續加法，這經常使用在陣列的定址。
強度折減的範例包含：
- 使用循環及加法取代乘法運算
- 使用循環及乘法取代指數運算
程式碼分析
大部分程式的執行時間通常都是花費在一些相當小的程式段，這些程式段通常都在循環之內不斷的執行。
編譯器使用一些方法來辨識循環以及循環內暫存器數值的特點，編譯器可利用強度折減來辨識：
- 循環不變式（Loop invariants），循環內不會改變的數值。
- 歸納變數（Induction variables），在循環內每次運行時變數都會增加或是減少一個固定的量。
循環不變式本質上在循環內是個常數，但他們的數值可能在循環外會改變。歸納變數則是會被改變一個已知的量。而在巢狀迴圈的情況之下，一個歸納變數在循環外的循環內也可以是一個歸納變數。
強度折減會找尋涉及循環不變式以及歸納變數，有些可以被簡化，舉例來說，循環不變式c及歸納變數i的乘法：
c = 8;
for (i = 0; i < N; i++)
{
y[i] = c * i;
}
最佳化
編譯器將會開始進行最佳化（並不只有強度折減），循環內的常數（不變式）將會被放到循環外面（Loop-invariant code motion），常數可以在循環外面載入，例如浮點數暫存器 fr3 及 fr4。接著辨識出不會改變的變數，例如常數N，這使得一些暫存器在循環內允許被合併，所以r2、r4、r7、r12可以被合併移置循環外或是消除。r8及r13同時有著相同的運算 i*n ，所以他們也可以被合併，最內層的循環（0120-0260）已經從11道指令減少為7道指令，為一個還留在最內層循環的乘法為0210行的乘法運算。
其它強度折減的運算
強度折減運運算元（Operator strength reduction）使用數學的方法，以更快的運運算元取代了緩慢的數學操作，這個優勢將會根據目標CPU以及一些程式（不同的CPU有著不同的可用功能）而有所不同。
- 使用2進位的算數位移或是邏輯位移來取代整數的乘法及除法。
- 使用常數結合位移、增加或減少來取代整數的乘法。
- 使用常數的乘法、機器整數上有限值域的優勢來取代整數除法。
原始的運算 | 取代的運算 |
|---|---|
y = x / 8 | y = x >> 3 |
y = x * 64 | y = x << 6 |
y = x * 2 | y = x << 1 |
y = x * 15 | y = (x << 4) - x |
