维基百科

强度折减

在软件工程领域，强度折减（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) 所取代。

注解

编辑
  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）. 

参考文献

编辑

本条目部分或全部内容出自以GFDL授权发布的《自由线上电脑词典》（FOLDOC）。

检索自“https://zh.wikipedia.org/w/index.php?title=強度折減&oldid=83953294”