fbpx
维基百科

強度折減

行進 26, 2023

在軟體工程領域，強度折減（Strength reduction）是一個編譯器最佳化技術，它將昂貴的運算以相同但是相對便宜的運算取代，最經典的範例就是將乘法轉換為使用迴圈的連續加法，這經常使用在陣列的定址。（Cooper，Simpson & Vick 1995，p.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 = x / 8 y = x >> 3
y = x * 64 y = x << 6
y = x * 2 y = x << 1
y = x * 15 y = (x << 4) - x

歸納變數 (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) 所取代。

註解

  1. ^ 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.
  2. ^ 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) 
  • Cooper, Keith; Simpson, Taylor; Vick, Christopher, Operator Strength Reduction (PDF), Rice University, October 1995 [April 22, 2010], （原始内容 (PDF)于2012-06-04） 

本條目部分或全部内容出自以GFDL授權發佈的《自由線上電腦詞典》（FOLDOC）。

行進 26, 2023
強度折減, 在軟體工程領域, strength, reduction, 是一個編譯器最佳化技術, 它將昂貴的運算以相同但是相對便宜的運算取代, 最經典的範例就是將乘法轉換為使用迴圈的連續加法, 這經常使用在陣列的定址, cooper, simpson, vick, 1995, 的範例包含, 使用迴圈及加法取代乘法運算, 使用迴圈及乘法取代指數運算目录, 程式碼分析, 範例, 中間碼, 最佳化, 外層迴圈, 最後的乘法, 其它的運算, 歸納變數, orphan, 註解, 參考文獻程式碼分析, 编辑大部份程式的執行時間. 在軟體工程領域 強度折減 Strength reduction 是一個編譯器最佳化技術 它將昂貴的運算以相同但是相對便宜的運算取代 最經典的範例就是將乘法轉換為使用迴圈的連續加法 這經常使用在陣列的定址 Cooper Simpson amp Vick 1995 p 1 強度折減的範例包含 使用迴圈及加法取代乘法運算 使用迴圈及乘法取代指數運算目录 1 程式碼分析 2 範例 2 1 中間碼 2 2 最佳化 2 3 外層迴圈 2 4 最後的乘法 3 其它強度折減的運算 4 歸納變數 orphan 5 註解 6 參考文獻程式碼分析 编辑大部份程式的執行時間通常都是花費在一些相當小的程式段 這些程式段通常都在迴圈之內不斷的執行 編譯器使用一些方法來辨識迴圈以及迴圈內暫存器數值的特點 編譯器可利用強度折減來辨識 循環不變式 Loop invariants 迴圈內不會改變的數值 歸納變數 Induction variables 在迴圈內每次運行時 都會增加或是減少一個固定量的變數 循環不變式本質上在迴圈內是個常數 但他們的數值可能在迴圈外會改變 歸納變數則是會被改變一個已知的量 而在巢狀回圈的情況之下 一個歸納變數在迴圈外的迴圈內也可以是一個歸納變數 強度折減會找尋涉及循環不變式以及歸納變數 有些可以被簡化 舉例來說 循環不變式c及歸納變數i的乘法 c 8 for i 0 i lt N i y i c i 可以被加法所取代 c 8 k 0 for i 0 i lt N i y i k k k c 範例 编辑以下是一個使用強度折減範例 他會減少所有出現在計算陣列索引位置的迴圈乘法想像一個簡單的迴圈 它設定一個陣列給一個已知的矩陣 for i 0 i lt n i for j 0 j lt n j A i j 0 0 A i i 1 0 中間碼 编辑 編譯器將會視這段程式碼為 0010 for i 0 i lt n i 0020 0030 r1 0 i 0 0040 G0000 0050 load r2 n i lt n 0060 cmp r1 r2 0070 bge G0001 0080 0090 for j 0 j lt n j 0100 0110 r3 0 j 0 0120 G0002 0130 load r4 n j lt 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 lt 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 lt n 0070 bge G0001 0080 0190 r8 r1 r2 計算元素 i n 0310 r13 r1 r2 移除 使用 r8 計算元素 i n 0090 for j 0 j lt n j 0100 0110 r3 0 j 0 0120 G0002 0140 cmp r3 r2 j lt 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 lt n 0145 cmp r9 r20 r8 j lt 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 lt 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 lt r8 n r20 0147 cmp r10 r22 r10 8 r8 j lt 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 lt 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 lt 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 lt n j 0100 0120 G0002 0147 cmp r10 r22 r10 8 r8 j lt 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 lt 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 lt 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 lt n j 0100 0120 G0002 0147 cmp r10 r22 r10 8 r8 j lt 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 lt 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 lt n 0070 bge G0001 0080 0118 r10 r40 強度折減 expression to r40 0090 for j 0 j lt n j 0100 0120 G0002 0147 cmp r10 r22 r10 8 r8 j lt 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 lt 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 lt n 0070 bge G0001 0080 0118 r10 r40 強度折減 expression to r40 0090 for j 0 j lt n j 0100 0120 G0002 0147 cmp r10 r22 r10 8 r8 j lt 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 lt i lt n 則暫存器r40則變成 0 lt r40 lt 8 n n 0010 for i 0 i lt 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 lt n 歸納變數取代 0065 cmp r40 r60 i 8 n lt 8 n n 0070 bge G0001 0080 0118 r10 r40 強度折減 expression to r40 0090 for j 0 j lt n j 0100 0120 G0002 0147 cmp r10 r22 r10 8 r8 j lt 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 其它強度折減的運算 编辑這個部分是有爭議的 dd 強度折減運算子 Operator strength reduction 使用數學的方法 以更快的運算子取代了緩慢的數學操作 這個優勢將會根據目標CPU以及一些程式 不同的CPU有著不同的可用功能 而有所不同 使用2進位的算數位移或是邏輯位移 來取代整數的乘法及除法 1 使用常數結合位移 增加或減少來取代整數的乘法 使用常數的乘法 機器整數上有限值域的優勢來取代整數除法 2 原始的運算 取代的運算y x 8 y x gt gt 3y x 64 y x lt lt 6y x 2 y x lt lt 1y x 15 y x lt lt 4 x歸納變數 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 gt gt 1 evaluates to 2 So in this case the compiler cannot optimize division by two by replacing it by a bit shift Granlund Torbjorn Peter L Montgomery Division by Invariant Integers Using Multiplication PDF 2013 03 09 原始内容存档 PDF 于2019 06 06 引文使用过时参数coauthors 帮助 參考文獻 编辑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 Cooper Keith Simpson Taylor Vick Christopher Operator Strength Reduction PDF Rice University October 1995 April 22 2010 原始内容存档 PDF 于2012 06 04 本條目部分或全部内容出自以GFDL授權發佈的 自由線上電腦詞典 FOLDOC 取自 https zh wikipedia org w index php title 強度折減 amp oldid 66868466, 维基百科，wiki，书籍，书籍，图书馆，

文章

，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。