Loading article…
コンピュータサイエンスでは、誘導変数とは、ループの各反復で一定量だけ増減する変数、または別の誘導変数の線形関数である変数のことです。[ 1 ]
例えば、次のループでは、iおよびjは誘導変数です。
for ( i = 0 ; i < 10 ; ++ i ) { j = 17 * i ; }一般的なコンパイラ最適化手法の一つは、誘導変数の存在を認識し、より単純な計算に置き換えることです。例えば、定数の加算が乗算よりも安価であるという前提のもと、上記のコードはコンパイラによって次のように書き換えられる可能性があります。
j = -17 ;for ( i = 0 ; i < 10 ; ++ i ) { j = j + 17 ; }この最適化は、強度低減の特殊なケースである。
場合によっては、この最適化を逆に行うことで、コードから誘導変数を完全に削除することが可能です。例えば、次のようになります。
extern int sum ;int foo ( int n ) { int j = 5 ;for ( int i = 0 ; i < n ; ++ i ) { j += 2 ; sum += j ; }合計を返す; }iこの関数のループには、と という2 つの誘導変数がありますj。どちらか一方をもう一方の線形関数として書き直すことができるため、コンパイラはこのコードを と記述したかのように最適化する可能性があります。
extern int sum ;int foo ( int n ) { for ( int i = 0 ; i < n ; ++ i ) { sum += 5 + 2 * ( i + 1 ); }合計を返す; }誘導変数置換とは、コンパイラが、囲んでいるループのインデックスの関数として表現できる変数を認識し、ループインデックスを含む式に置き換える変換処理である。
この変換により、変数とループインデックスの関係が明確になり、依存関係分析などの他のコンパイラ分析に役立ちます。
例：
入力コード:
int c = 10 ;for ( int i = 0 ; i < 10 ; i ++ ) { c = c + 5 ; // c はループの各反復で 5 ずつ増加します}出力コード
int c = 10 ;for ( int i = 0 ; i < 10 ; i ++ ) { c = 10 + 5 * ( i + 1 ); // c はループインデックスの関数として明示的に表現されています}ループカウンタの線形関数ではない誘導変数にも同じ最適化を適用できます。たとえば、ループ
j = 1 ;for ( i = 0 ; i < 10 ; ++ i ) { j = j << 1 ; }変換可能
for ( i = 0 ; i < 10 ; ++ i ) { j = 1 << ( i + 1 ); }