ループ不変コードの動き

コンピュータ プログラミングでは、ループ不変コードは、プログラムの意味に影響を与えずにループ本体の外部に移動できるステートメントまたは式 (命令型 プログラミング言語) で構成されます。ループ不変コードの移動(巻き上げまたはスカラー プロモーションとも呼ばれる) は、この移動を自動的に実行する コンパイラの最適化です。

次のコードサンプルでは、​​2 つの最適化を適用できます。

int i = 0 ; while ( i < n ) { x = y + z ; a [ i ] = 6 * i + x * x ; ++ i ; }   
    
        
            
    

計算x = y + zと はx * xループ不変ですが、コードをループ外に移動する前に予防措置を講じる必要があります。ループ条件が である可能性がありfalse(たとえば、 がn負の値を保持している場合)、そのような場合は、ループ本体をまったく実行しないでください。正しい動作を保証する 1 つの方法は、ループ外で条件分岐を使用することです。ループ条件の評価には副作用があるため、 構造による追加の評価は、ループを にif置き換えることによって補う必要があります。最初に が使用されるコードの場合、ループ本体が少なくとも 1 回実行されることが保証されているため、保護プロセス全体は必要ありません。 whiledo {} whiledo {} while

int i = 0 ; if ( i < n ) { x = y + z ; int const t1 = x * x ; do { a [ i ] = 6 * i + t1 ; ++ i ; } while ( i < n ); }   
    
        
          
     
              
        
        

このコードは、さらに最適化することができます。たとえば、強度削減により、ループ内の 2 つの乗算 (6*iおよびa[i]) を削除し、誘導変数の削除により、完全に省略することができます。 はそれ自体と同期している必要があるiため、両方を持つ必要はありません。 6 * ii

通常、到達定義分析は、ステートメントまたは式がループ不変であるかどうかを検出するために使用されます。

たとえば、ある単純な式のオペランドのすべての到達定義がループの外側にある場合、その式をループの外に移動できます。

データフロー依存性解析^[1]を使用した最近の研究では、不変コマンドだけでなく、内部ループなどのより大きなコードフラグメントも検出できます。この解析では、任意の程度の準不変、つまりループ本体の一定回数の反復後に不変になるコマンドまたはコードフラグメントも検出されます。

ループから外されたループ不変コードは実行頻度が低くなり、速度が向上します。この変換のもう 1 つの効果は、定数をレジスタに格納できるようになり、反復ごとにアドレスを計算してメモリ (またはキャッシュ ライン) にアクセスする必要がなくなることです。

ただし、変数が多すぎると、レジスタの負荷が高くなります。特に、32 ビットx86などのレジスタが少ないプロセッサではその傾向が顕著です。コンパイラがレジスタを使い果たすと、一部の変数がスピルされます。これに対処するには、逆の最適化、つまり再マテリアライズを実行します。

• コードモーション
• ループ不変

• Aho, Alfred V.; Sethi, Ravi; & Ullman, Jeffrey D. (1986)。コンパイラ：原理、テクニック、ツール。Addison Wesley。ISBN 0-201-10088-6 。

• コンパイラの最適化 - ホイスティング