誘導変数

コンピュータサイエンスにおいて、誘導変数とは、ループの反復ごとに一定量増加または減少する変数、または別の誘導変数の線形関数である変数である。^{[ 1 ]}

たとえば、次のループでは、iとjは誘導変数です。

( i = 0 ; i < 10 ; ++ i )の場合{ j = 17 * i ; }

強度低減への応用

一般的なコンパイラの最適化では、誘導変数の存在を認識し、それをより単純な計算に置き換えます。たとえば、定数の加算は乗算よりもコストが安いという前提で、上記のコードはコンパイラによって次のように書き換えられます。

j = -17 ;( i = 0 ; i < 10 ; ++ i ) { j = j + 17 ; }の場合

場合によっては、この最適化を逆にして、コードから誘導変数を完全に削除することも可能です。例えば、

外部int合計;int foo ( int n ) { int j = 5 ;for ( int i = 0 ; i < n ; ++ i ) { j += 2 ;合計+= j ; }合計を返す; }

この関数のループには2つの誘導変数があります:iとj。どちらももう一方の線形関数として書き直すことができるため、コンパイラはこのコードを次のように記述したかのように最適化する可能性があります。

外部int合計;int foo ( int n ) { for ( int i = 0 ; i < n ; ++ i ) {合計+= 5 + 2 * ( i + 1 ); }合計を返す; }

誘導変数置換は、囲んでいるループのインデックスの関数として表現できる変数を認識し、ループインデックスを含む式に置き換えるコンパイラ変換です。

この変換により、変数とループインデックスの関係が明示的になり、依存関係の分析などの他のコンパイラ分析に役立ちます。

例：

入力コード:

整数c = 10 ;for ( int i = 0 ; i < 10 ; i ++ ) { c = c + 5 ; // ループの繰り返しごとに c が 5 ずつ増加します}

出力コード

整数c = 10 ;for ( int i = 0 ; i < 10 ; i ++ ) { c = 10 + 5 * ( i + 1 ); // c はループインデックスの関数として明示的に表現されます}

同じ最適化は、必ずしもループカウンタの線形関数ではない誘導変数にも適用できます。たとえば、ループ

j = 1 ;( i = 0 ; i < 10 ; ++ i )の場合{ j = j << 1 ; }

変換される可能性があります

( i = 0 ; i < 10 ; ++ i )の場合{ j = 1 << ( i + 1 ); }

^スティーブン・マッチニック、マッチニック・アンド・アソシエイツ（1997年8月15日）『Advanced Compiler Design Implementation』Morgan Kaufmann. ISBN 978-1-55860-320-2.誘導変数。

Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1986)、『コンパイラ：原理、テクニック、ツール』（第2版）、ISBN 978-0-201-10088-4
Allen, Francis E.; Cocke, John ; Kennedy, Ken (1981)「Reduction of Operator Strength」、Munchnik, Steven S.; Jones, Neil D. (eds.)『Program Flow Analysis: Theory and Applications』、Prentice-Hall、ISBN 978-0-13-729681-1
コック、ジョン；ケネディ、ケン（1977年11月）「演算子強度の低減のためのアルゴリズム」、Communications of the ACM、20（11）：850–856、doi：10.1145/359863.359888、S2CID 1092505
Cooper, Keith; Simpson, Taylor; Vick, Christopher (1995), Operator Strength Reduction (PDF) , Rice University , 2010年4月22日閲覧