定数畳み込み

定数の畳み込みと定数の伝播は、多くの現代のコンパイラで使用されている関連するコンパイラ最適化です。^[1]スパース条件付き定数伝播 と呼ばれる定数伝播の高度な形式は、より正確に定数を伝播し、同時にデッドコードを削除することができます。

定数の畳み込みは、実行時に定数式を計算するのではなく、コンパイル時に定数式を認識して評価するプロセスです。定数式の項は通常、整数リテラルなどの単純なリテラルですが、コンパイル時に値がわかっている変数である場合もあります。次のステートメントを考えてみましょう。 2

  私= 320 * 200 * 32 ;      

ほとんどのコンパイラは、このステートメントに対して実際には 2 つの乗算命令とストアを生成しません。代わりに、コンパイラはこのような構造を識別し、コンパイル時に計算された値 (この場合は2,048,000) を置き換えます。

定数の畳み込みでは算術恒等式を利用できます。 がx数値の場合、0 * xコンパイラが の値を知らない場合でも の値はゼロになります( はInfinity またはNaNになる可能性があるため、これはIEEE 浮動x小数点数には有効ではないことに注意してください。ただし、 GLSLシェーダーなどのパフォーマンスを優先する一部の環境では定数に対してこれを許可しており、場合によってはバグが発生する可能性があります)。 x

定数の折り畳みは、数値以外にも適用できます。文字列リテラルと定数文字列の連結も定数の折り畳みが可能です。 などのコードは"abc" + "def"に置き換えることができます"abcdef"。

クロスコンパイラを実装する場合、ホストアーキテクチャ上の算術演算の動作がターゲットアーキテクチャ上の動作と一致するように注意する必要があります。そうしないと、定数の折りたたみを有効にするとプログラムの動作が変わります。これは、正確な実装が大きく異なる可能性がある浮動小数点演算の場合に特に重要です。

定数の伝播は、コンパイル時に式内の既知の定数の値を置き換えるプロセスです。このような定数には、上記で定義された定数だけでなく、定数値に適用される組み込み関数も含まれます。次の疑似コードを考えてみましょう。

  int x = 14 ; int y = 7 - x / 2 ; y * ( 28 / x + 2 )を返します。   
         
         

x を伝播すると次のようになります:

  int x = 14 ; int y = 7 - 14 / 2 ; y * ( 28 / 14 + 2 )を返します。   
         
         

伝播を続けると、次の結果が生成されます ( x と y の両方のデッドコードを削除することでさらに最適化される可能性があります)。

  int x = 14 ; int y = 0 ; 0を返す;   
     
   

定数伝播は、到達定義分析結果を使用してコンパイラに実装されます。すべての変数の到達定義が、同じ定数を変数に割り当てる同じ割り当てである場合、変数は定数値を持ち、定数に置き換えることができます。

定数伝播により、条件式がコンパイル時に true または false に評価され、唯一の可能な結果が決定できる場合、条件分岐が 1 つ以上の無条件ステートメントに簡略化されることもあります。

定数の折り畳みと伝播は、通常、多くの簡略化と削減を実現するために一緒に使用され、それらのインターリーブされた反復的な適用は、それらの効果がなくなるまで継続されます。

分析を待つ間に不明な数値を返す、最適化されていない疑似コードを検討してください。

  int a = 30 ; int b = 9 - ( a / 5 ); int c = b * 4 ; if ( c > 10 ) { c = c - 10 ; } return c * ( 60 / a );   
         
       
  
      
         
  
       

定数伝播を一度適用し、その後定数折り畳みを適用すると、次のようになります。

  int a = 30 ; int b = 3 ; int c = b * 4 ; if ( c > 10 ) { c = c - 10 ; } return c * 2 ;   
     
       
  
      
         
  
     

両方の手順を 2 回繰り返すと、次の結果が生成されます。

  int a = 30 ; int b = 3 ; int c = 12 ; if ( true ) { c = 2 ; } return c * 2 ;   
     
     
  
    
       
  
     

a変数と定数の使用をすべて置き換えた後b、コンパイラのデッドコード除去がそれらの変数に適用され、次のようになります。

  整数c = 12 ;   

  if ( true ) { c = 2 ; } c * 2を返します。  
       
  
     

(ブール構造は言語やコンパイラによって異なりますが、その詳細 ( trueのステータス、起源、表現など) はこれらの最適化の原則に影響しません。)

従来の定数伝播では、それ以上の最適化は行われず、プログラムの再構築も行われません。

しかし、同様の最適化であるスパース条件付き定数伝播は、適切な条件分岐を選択し、 ^[2]常に真となる条件テストを削除することでさらに進んでいます。したがって、変数はc冗長になり、定数に対する操作のみが残ります。

  4を返します。 

その疑似コードが関数本体を構成する場合、コンパイラは関数が整数定数 に評価されることを認識し4、関数への呼び出しを に置き換えることができる4ため、プログラムの効率がさらに向上します。

• 制御フローグラフ
• 使用定義チェーンとSSAフォーム
• コピーの伝播
• 共通部分式の除去
• 部分的な評価

• マッチニック、スティーブン S. (1997)、高度なコンパイラの設計と実装、モーガン カウフマン、ISBN 9781558603202