演算子強度低減（英語: strength reduction）とはコンパイラ最適化手法の一つで、コストの高い演算式を等価でコストの低い演算式に置き換えるものである。
演算子強度低減では、数学的な同一性を用いて低速な演算式を高速な演算式で置換する。置換したことによるコストと利点は対象の CPU や、時には周辺のコード(CPU 内の機能ユニットが利用できるかどうか)に大きく依存する。
- 整数の乗除算を 2 の累乗と論理シフトや算術シフトで置き換える。
- 整数の乗算をシフト、加減算によって置き換える
帰納変数の強度低減、再帰的な強度低減では、自動的に変化するような結果を返す関数を以前の結果を用いて簡単な演算結果に置き換える。これは、手続き型プログラミングでは、ループ変数に関連する式に適用でき、宣言型プログラミングでは再帰呼び出しの引数に適用できる。 例えば、
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 との等価性を維持している。
脚注
関連項目
- 部分評価
- メモ化
