誘導変数

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

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

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

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

17 = 0 ;  

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

この最適化は強度削減の特殊なケースです。

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

外部int合計;  

int foo ( int n ) { int j = 5 ;   
       

    ( int i = 0 ; i < n ; ++ i ) { j + = 2 ;合計+= j ; }         
          
          
    

    合計を返す; } 

iこの関数のループには、とという2つの誘導変数があります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 はループインデックスの関数として明示的に表現されます}         
              

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

1 = 1 ;  

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

変換される可能性がある

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

• 数学的帰納法

• 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
• クーパー、キース、シンプソン、テイラー、ヴィック、クリストファー (1995)、Operator Strength Reduction (PDF)、ライス大学、 2010 年4 月 22 日取得