演算子強度低減
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/10/11 01:30 UTC 版)
 | この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。（2022年10月） |
演算子強度低減（英語: strength reduction）とはコンパイラ最適化手法の一つで、コストの高い演算式を等価でコストの低い演算式に置き換えるものである。
演算子強度低減では、数学的な同一性を用いて低速な演算式を高速な演算式で置換する。置換したことによるコストと利点は対象の CPU や、時には周辺のコード(CPU 内の機能ユニットが利用できるかどうか)に大きく依存する。
| 元の演算式 | 置き換えた演算式 |
|---|---|
| y = x / 8 | y = x >> 3 |
| y = x * 64 | y = x << 6 |
| y = x * 2 | y = x + x |
| y = x * 15 | y = (x << 4) - x |
帰納変数の強度低減、再帰的な強度低減では、自動的に変化するような結果を返す関数を以前の結果を用いて簡単な演算結果に置き換える。これは、手続き型プログラミングでは、ループ変数に関連する式に適用でき、宣言型プログラミングでは再帰呼び出しの引数に適用できる。 例えば、
f x = ... (2 ** x) ... (f (x + 1)) ...
は、以下のようになる。
f x = f' x (2 ** x)
ここで f' x z = ... z ... (f' (x + 1) (2 * z)) ... である。
このようにして、高価な演算 (2 ** x) は再帰的関数 f' でコストの低い (2 * z) に置換された。いかなる f' の呼び出しに関しても、z = 2 ** x との等価性を維持している。
脚注
- ^ C のような言語では、整数の除算は切捨てであり、負の数に対して特殊な扱いが必要になる
関連項目
- 演算子強度低減のページへのリンク
