4

私はさまざまなコンパイラの機能について調べていて、多くのコンパイラが実行すると報告されている「積極的な最適化」という用語に出くわしました。たとえば、LLVM は、次のコンパイル時の最適化機能を挙げています。

  • メモリ/ポインタ固有
  • ループ変換
  • データフロー
  • 算術
  • デッドコードの排除
  • インライン化

これは具体的にどういう意味ですか？次のコード スニペットがあるとします。生成されたバイト コードを最適化して、コンパイラが生成したものよりも速く実行するにはどうすればよいでしょうか? 特に、C#、Java、Flash などの JIT を利用したランタイムのバイトコードの最適化に関心があります。JIT はプロセッサが通常実行するオペコードのサブセットのみをサポートし、実行できる最適化の量が制限されるため、これは注意が必要です。それでも、私は何が可能で、正確にどのような変換が VM の限界を押し上げることができるかを知りたいと思っています。

架空のコード ブロック:

for (i = 0; i < 100; i++){
    in = dataIn[i];
    if ((in % 5) == 0){
        out = ((in / 2) >> 16) - 10;
    }else{
        out = ((in << 5) / 2) * 50 + 10;
    }
    dataOut[i] = out;
}

Flash Player などのスタックベースの JIT VM 用に、コンパイラによって生成されたおおよその疑似コード: (間違いがあった場合はご容赦ください。これは完全に手書きです!)

// i = 0
label: "forInit"
   push 0
   writeTo "i"

// while i < 100
label: "forStart"
   push "i"
   push 100
   jumpIfMoreThan "forEnd"

       // in = dataIn[i];
       push "i"
       push "dataIn"
       readProp
       saveTo "in"

       // if ((in % 5) == 0)
       push "in"
       push 5
       mod
       push 0
       jumpIfNotEquals "ifPart2"
       label: ifPart1

           // out = ((in / 2) >> 16) - 10;
           push "in"
           push 2
           divide
           push 16
           rightshift
           push 10
           minus
           writeTo "out"
           goto "ifEnd"

       // else
       label: ifPart2

           // out = ((in << 5) / 2) * 50 + 10;
           push "in"
           push 5
           leftshift
           push 2
           divide
           push 50
           multiply
           push 10
           add
           writeTo "out"

       // dataOut[i] = out;
       label: ifEnd
           push "out"
           push "i"
           push "dataOut"
           writeProp

       // i++
       push "i"
       increment
       writeTo "i"

   // while i < 100
   goto "forStart"
label: "forEnd"
4

3 に答える 3

6

私はこれにも取り組んでいます.LLVMが実行する変換の完全なリストは、ヘッダーの下に整理されています:

  • デッドコードの除去
    • 積極的なデッドコードの排除
    • デッドコードの排除
    • デッド引数の削除
    • デッドタイプの排除
    • デッド命令の削除
    • デッドストアの排除
    • デッドグローバルエリミネーション
    • デッドループを削除する
  • 不要なデータの削除
    • モジュールからすべてのシンボルを取り除く
    • 未使用のシンボルのデバッグ情報を取り除く
    • 未使用の関数プロトタイプを取り除く
    • すべての llvm.dbg.declare 組み込み関数を取り除きます
    • モジュールから dbg シンボルを除くすべてのシンボルを取り除きます
    • 重複するグローバル定数をマージする
    • 未使用の例外処理情報を削除
  • 関数のインライン化
    • マージ機能
    • 部分インライナー
    • 関数の統合/インライン化
  • ループの最適化
    • ループ クローズド SSA フォーム パス
    • ループ不変コード モーション
    • ループを新しい関数に抽出する
    • 多くても 1 つのループを新しい関数に抽出します
    • ループ強度の低下
    • ループを回転
    • 自然なループを正規化する
    • ループを展開する
    • ループの切り替えを解除
  • その他
    • 「参照による」引数をスカラーにプロモートする
    • 基本ブロック内で命令を組み合わせてベクトル命令を形成する
    • プロファイル ガイド付き基本ブロックの配置
    • CFG のクリティカル エッジをブレーク
    • コード生成の最適化
    • 単純定数伝播
    • 関数属性の推定
    • グローバル変数オプティマイザー
    • グローバル値の番号付け
    • 誘導変数の正規化
    • エッジ プロファイリング用のインストルメンテーションの挿入
    • エッジ プロファイリングに最適な計測器を挿入
    • 冗長な命令を組み合わせる
    • グローバル シンボルを内部化する
    • 手続き間の定数の伝播
    • プロシージャ間のスパース条件付き定数の伝播
    • ジャンプスレッド
    • アトミック組み込み関数を非アトミック形式に下げる
    • アンワインドのないコード ジェネレーターの場合、呼び出しとアンワインドを下げる
    • SwitchInst をブランチに下げる
    • メモリを登録に昇格
    • MemCpy の最適化
    • 関数出口ノードを統一する
    • 式を再関連付けする
    • すべての値をスタック スロットに降格する
    • 集計のスカラー置換 (DT)
    • スパース条件付き定数伝播
    • よく知られたライブラリ呼び出しを簡素化する
    • CFG を簡素化する
    • コード沈没
    • sret 引数を複数の ret 値にプロモートする
    • テールコールの除去
    • テール複製
于 2012-06-17T16:02:53.457 に答える
2

これはあなたの質問への回答ではありませんが、生成されたマシン コードを最適化するために C++ コンパイラが実行する次の変換に遭遇しました。

  • 強度削減--- データ インデックスとして使用される反復変数は、データ ユニットのサイズに一致するレートでインクリメントされます
  • 隠しパラメータ--- 構造体を返す関数は、実際には隠しパラメータが指す領域に書き込みます
  • 整数除算--- 特定の式を使用して、既知の除数の場合に整数除算をより効率的に評価できます
  • 浮動小数点条件--- 浮動小数点条件は、浮動小数点ステータスを設定および照会する複雑な一連の命令に変換されます。
  • 複雑な数学 --- 複雑な乗算または除算がライブラリ呼び出しに変換されます
  • ネイティブ ルーチン--- memcpy()、memset()、strcmp()、または strlen() 操作は、rep mov、rep sto、rep zcmp、または rep zscas に変換されます。
  • 短絡--- 複雑な条件が基本ブロックのツリーで評価されます
  • ユニオンのあいまいさ--- ユニオンのどのメンバーが意図されているかに関する情報が失われます
  • コピーの断片化--- 大きな double または集計値が単語ごとにコピーされます
  • テストの断片化--- 長整数値の条件は、その値の個々の単語に対する個別のテストで構成されます
  • スイッチのフラグメンテーション--- スイッチ ステートメントは、値に対する条件のネストに置き換えられます
  • ループ ヘッダー コピー--- ループは、ループに入るかどうかを決定する条件で拡張されます。
  • ループ展開--- ループは、ループ本体の複製されたコピーに置き換えられます
  • 関数 のインライン化 --- 関数呼び出しは関数本体のコピーに置き換えられます
于 2012-06-17T15:39:49.170 に答える
1

コンパイラが実行できる 2 つの簡単な最適化を次に示します。

out = ((i / 2) >> 16) - 10;

に減らすことができます

out = (i >> 17) - 10;

と

out = ((i << 5) / 2) * 50 + 10;

に減らすことができます

out = (i << 4) * 50 + 10;

あなたの質問に答えるには、「生成されたバイトコードを最適化して、コンパイラが生成したものよりも速く実行するにはどうすればよいですか?」これは、いくつかの最適化を行った別のバージョンのバイトコードです。

// i = 0
label: "forInit"
   push 0
   writeTo "i"

// while i < 100
label: "forStart"
   push "i"
   push 100
   jumpIfMoreThan "forEnd"

       // in = dataIn[i];
       push "i"
       push "dataIn"
       readProp
       saveTo "in"

       // if ((in % 5) == 0)
       push "in"
       push 5
       mod
       push 0
       jumpIfNotEquals "ifPart2"
       label: ifPart1
           // optimization: remove unnecessary /2
           // out = ((in / 2) >> 16) - 10;
           push "in"
           push 17
           rightshift
           push 10
           minus
           // optimization: don't need out var since value on stack
           // dataOut[i] = out;
           push "i"
           push "dataOut"
           writeProp
           // optimization: avoid branch to common loop end 
           // i++
           push "i"
           increment
           writeTo "i"
           goto "forStart"

       // else
       label: ifPart2
           // optimization: remove unnecessary /2
           // out = ((in << 5) / 2) * 50 + 10;
           push "in"
           push 4
           leftshift
           push 50
           multiply
           push 10
           add
           // optimization: don't need out var since value on stack
           // dataOut[i] = out;
           push "i"
           push "dataOut"
           writeProp
           // optimization: avoid branch to common loop end 
           // i++
           push "i"
           increment
           writeTo "i"
           goto "forStart"
label: "forEnd"
于 2012-06-17T15:57:47.760 に答える