LLVMの解析と変換パス¶

はじめに ¶

警告

このドキュメントは頻繁に更新されません。パスの一覧は、おそらく不完全です。opt -print-passesを使用して、optツールが認識するパスを一覧表示できます。

このドキュメントは、LLVMが提供する最適化機能の概要を示しています。最適化は、プログラムの一部をトラバースして情報を収集するか、プログラムを変換するパスとして実装されています。以下の表では、LLVMが提供するパスを3つのカテゴリに分類しています。解析パスは、他のパスが使用できる情報、またはデバッグやプログラムの可視化の目的で情報を計算します。変換パスは、解析パスを使用するか（または無効にする）ことができます。変換パスはすべて、何らかの方法でプログラムを変更します。ユーティリティパスは、いくつかのユーティリティを提供しますが、それ以外の分類には当てはまりません。たとえば、関数をビットコードに抽出したり、モジュールをビットコードに書き込むパスは、解析パスでも変換パスでもありません。上記の目次には、各パスの簡単な概要と、ドキュメントの後半にあるより完全なパスの説明へのリンクが記載されています。

解析パス ¶

このセクションでは、LLVM解析パスについて説明します。

`aa-eval`: 包括的なエイリアス解析精度評価器 ¶

これは、単純なN^2エイリアス解析精度評価器です。基本的に、プログラム内の各関数について、エイリアス解析の実装が、関数内の各ポインターペア間のエイリアス問い合わせにどのように答えるかを問い合わせるだけです。

これは、Naveen Neelakantam、Francesco Spadini、およびWojciech Stryjewskiによるコードに触発され、適応されています。

`basic-aa`: 基本エイリアス解析（ステートレスAA実装）¶

同一性（異なるグローバル変数はエイリアスにならないなど）を実装する基本的なエイリアス解析パスですが、状態を保持する解析は行いません。

`basiccg`: 基本コールグラフ構築 ¶

未実装です。

`da`: 依存関係解析 ¶

メモリアクセスにおける依存関係を検出するために使用される依存関係解析フレームワークです。

`domfrontier`: 支配フロンティア構築 ¶

このパスは、前方支配フロンティアを見つけるための単純な支配者構築アルゴリズムです。

`domtree`: 支配木構築 ¶

このパスは、前方支配者を見つけるための単純な支配者構築アルゴリズムです。

`dot-callgraph`: コールグラフを「dot」ファイルに出力 ¶

optでのみ使用可能なこのパスは、コールグラフを.dotグラフに出力します。このグラフは、「dot」ツールで処理して、PostScriptまたはその他の適切な形式に変換できます。

`dot-cfg`: 関数のCFGを「dot」ファイルに出力 ¶

optでのみ使用可能なこのパスは、制御フローグラフを.dotグラフに出力します。このグラフは、dotツールで処理して、PostScriptまたはその他の適切な形式に変換できます。さらに、-cfg-func-name=<substring>オプションを使用して、出力する関数をフィルタリングできます。指定された部分文字列を含むすべての関数が印刷されます。

`dot-cfg-only`: 関数のCFGを「dot」ファイルに出力（関数本体なし）¶

optでのみ使用可能なこのパスは、関数本体を除いて、制御フローグラフを.dotグラフに出力します。このグラフは、dotツールで処理して、PostScriptまたはその他の適切な形式に変換できます。さらに、-cfg-func-name=<substring>オプションを使用して、出力する関数をフィルタリングできます。指定された部分文字列を含むすべての関数が印刷されます。

`dot-dom`: 関数の支配木を「dot」ファイルに出力 ¶

optでのみ使用可能なこのパスは、支配木を.dotグラフに出力します。このグラフは、dotツールで処理して、PostScriptまたはその他の適切な形式に変換できます。

`dot-dom-only`: 関数の支配木を「dot」ファイルに出力（関数本体なし）¶

optでのみ使用可能なこのパスは、関数本体を除いて、支配木を.dotグラフに出力します。このグラフは、dotツールで処理して、PostScriptまたはその他の適切な形式に変換できます。

`dot-post-dom`: 関数の後方支配木を「dot」ファイルに出力 ¶

optでのみ使用可能なこのパスは、後方支配木を.dotグラフに出力します。このグラフは、dotツールで処理して、PostScriptまたはその他の適切な形式に変換できます。

`dot-post-dom-only`: 関数の後方支配木を「dot」ファイルに出力（関数本体なし）¶

optでのみ使用可能なこのパスは、関数本体を除いて、後方支配木を.dotグラフに出力します。このグラフは、dotツールで処理して、PostScriptまたはその他の適切な形式に変換できます。

`globals-aa`: グローバル変数に対する単純なmod/ref解析 ¶

この単純なパスは、アドレスが取得されていないグローバル値に対するエイリアスおよびmod/ref情報を提供し、関数がメモリを読み書きするかどうか（「pure」かどうか）を追跡します。この単純な（しかし非常に一般的な）ケースでは、非常に正確で有用な情報を提供できます。

`instcount`: 各種`Instruction`の数をカウント ¶

このパスは、すべての命令の数を収集して報告します。

`iv-users`: 誘導変数のユーザー ¶

誘導変数から計算された式の「興味深い」ユーザーの記録管理を行います。

`lazy-value-info`: 遅延値情報解析 ¶

値制約情報の遅延計算のためのインターフェースです。

`lint`: LLVM IRの静的lintチェック ¶

このパスは、LLVM IRで未定義の動作または意図しない可能性のある動作を生成する一般的で容易に特定できる構成要素を静的にチェックします。

これは、2つの点で正確性の保証ではありません。まず、包括的ではありません。静的に実行できるチェックがまだ実装されていないものがあります。これらのいくつかはTODOコメントで示されていますが、それらも包括的ではありません。第二に、多くの条件は静的にチェックできません。このパスは動的なインストルメンテーションを行わないため、考えられるすべての問題をチェックすることはできません。

もう1つの制限として、すべてのコードが実行されると仮定している点が挙げられます。到達不可能な基本ブロック内のnullポインタを介したストアは無害ですが、このパスはそれでも警告を発します。

最適化パスによって、このパスがチェックする条件がより明白になったり、より明白でなくなったりすることがあります。最適化パスが警告を生成しているように見える場合は、最適化パスがコード内の既存の条件を明らかにしているにすぎない可能性があります。

このコードは、instcombineの前に実行される場合があります。多くの場合、instcombineは同じ種類のものをチェックし、未定義の動作を含む命令を到達不可能（または同等）なものに変換します。このため、このパスはビットキャストなどを調べる努力をしています。

`loops`: 自然ループ情報 ¶

この解析は、自然ループを特定し、CFGのさまざまなノードのループ深度を決定するために使用されます。特定されたループは、実際には同じヘッダーノードを共有する複数の自然ループである可能性があり、単一の自然ループだけではないことに注意してください。

`memdep`: メモリ依存関係解析 ¶

指定されたメモリ操作について、それが依存する先行するメモリ操作を決定する解析です。エイリアス解析情報に基づいて構築され、一般的なエイリアス情報クエリの種類に対する遅延キャッシングインターフェースを提供しようとします。

`print<module-debuginfo>`: モジュールレベルのデバッグ情報のデコード ¶

このパスは、モジュール内のデバッグ情報メタデータをデコードし、(十分に準備された)人間が読める形式で標準出力に出力します。

`postdomtree`: 後方支配木構築 ¶

このパスは、後方支配者を見つけるための単純な後方支配者構築アルゴリズムです。

`print-alias-sets`: エイリアスセットプリンター ¶

未実装です。

`print-callgraph`: コールグラフを出力 ¶

opt でのみ使用可能なこのパスは、コールグラフを人間が読み取れる形式で標準エラー出力に出力します。

`print-callgraph-sccs`: コールグラフの強連結成分を出力 ¶

opt でのみ使用可能なこのパスは、コールグラフの強連結成分を人間が読み取れる形式で標準エラー出力に出力します。

`print-cfg-sccs`: 各関数のCFGの強連結成分を出力 ¶

opt でのみ使用可能なこのパスは、各関数のCFGの強連結成分を人間が読み取れる形式で標準エラー出力に出力します。

`function(print)`: 関数を標準エラー出力に出力 ¶

PrintFunctionPass クラスは、他の FunctionPasses とパイプライン処理するように設計されており、モジュールの関数を処理順に出力します。

`module(print)`: モジュールを標準エラー出力に出力 ¶

このパスは、実行時にモジュール全体を単純に出力します。

`regions`: 単一エントリ単一出口領域の検出 ¶

RegionInfo パスは、関数内の単一エントリ単一出口領域を検出します。領域は、残りのグラフに2箇所のみ接続されている任意の部分グラフとして定義されます。さらに、階層的な領域ツリーが構築されます。

`scalar-evolution`: スカラー進化解析 ¶

ScalarEvolution 解析は、ループ内のスカラー式を解析および分類するために使用できます。これは、一般的な誘導変数の認識に特化しており、抽象的で不透明な SCEV クラスでそれらを表現します。この解析により、ループの反復回数やその他の重要なプロパティを取得できます。

この解析は、主に誘導変数の置換と強度削減に役立ちます。

`scev-aa`: ScalarEvolutionベースのエイリアス解析 ¶

ScalarEvolution クエリに基づいて実装された単純なエイリアス解析です。

これは、異なる反復間の依存関係ではなく、ループの単一反復内の依存関係をテストするという点で、従来のループ依存関係解析とは異なります。

ScalarEvolution は、BasicAliasAnalysis のアドホックな解析のコレクションよりも、ポインタ演算のより完全な理解を持っています。

`stack-safety`: スタックセーフティ解析 ¶

StackSafety 解析は、スタックに割り当てられた変数をメモリアクセスのバグから安全と見なせるかどうかを判断するために使用できます。

この解析の主な目的は、サニタイザが安全な変数の不要なインストルメンテーションを回避するために使用することです。

変換パス ¶

このセクションでは、LLVM変換パスについて説明します。

`adce`: アグレッシブなデッドコード除去 ¶

ADCEは、コードを積極的に除去しようとします。このパスは DCE と似ていますが、値はそうでないことが証明されるまでデッドと仮定します。これは SCCP と似ていますが、値の存続期間に適用されます。

`always-inline`: `always_inline` 関数のインライナー ¶

「always inline」としてマークされている関数のみを処理するカスタムインライナーです。

`argpromotion`: 「参照による」引数をスカラーに昇格 ¶

このパスは、「参照による」引数を「値による」引数に昇格させます。実際には、ポインタ引数を持つ内部関数を検索することを意味します。エイリアス解析を使用して、引数が*読み取り専用*であることを証明できれば、値のアドレスではなく値を関数に渡すことができます。これにより、コードの再帰的な簡素化が発生し、allocaの除去につながります（特にSTLのようなC++テンプレートコードで）。

このパスは、関数に渡される集約引数も処理し、集約の要素が読み取り専用の場合にそれらをスカラー化します。集約のスカラー化により、関数に3つ以上のオペランドを渡す必要がある場合、このパスはスカラー化を拒否することに注意してください。これは、大きな配列や構造体に対して何千ものオペランドを渡すことは非効率的だからです！

この変換は、書き込み専用である引数（代わりに値を返す）に対しても行うことができますが、現在は行っていません。このケースは、LLVMが関数の複数の戻り値をサポートし始めた場合に最適に処理されます。

`block-placement`: プロファイルガイド付き基本ブロック配置 ¶

このパスは、非常に単純なプロファイルガイド付き基本ブロック配置アルゴリズムです。その考え方は、頻繁に実行されるブロックを関数の先頭に配置し、フォールスルー条件分岐の数を増やすことです。特定の関数のプロファイル情報がない場合、このパスは基本的に深さ優先順にブロックを順序付けます。

`break-crit-edges`: CFG内のクリティカルエッジを分割 ¶

ダミーの基本ブロックを挿入することで、CFG内のすべてのクリティカルエッジを分割します。クリティカルエッジを処理できないパスで「必須」になる場合があります。この変換は明らかにCFGを無効にしますが、前方支配者（集合、直接支配者、ツリー、および境界）情報を更新できます。

`codegenprepare`: コード生成のための最適化 ¶

このパスは、入力関数のコードを調整して、SelectionDAGベースのコード生成をより適切に準備します。これは、その基本ブロック単位のアプローチの制限を回避します。最終的には削除されるはずです。

`constmerge`: 重複するグローバル定数のマージ ¶

重複するグローバル定数を、共有される単一の定数にマージします。これは、一部のパス（例：TraceValues）が、既存の文字列が使用可能かどうかとは関係なく、プログラムに多くの文字列定数を挿入するため、役立ちます。

`dce`: デッドコード除去 ¶

デッドコード除去はデッド命令除去に似ていますが、削除された命令で使用されていた命令を再確認して、新しくデッドになったかどうかを確認します。

`deadargelim`: デッド引数除去 ¶

このパスは、内部関数からデッド引数を削除します。デッド引数除去は、直接デッドである引数と、他の関数のデッド引数として関数呼び出しに渡されるだけの引数を削除します。このパスも同様の方法でデッド引数を削除します。

このパスは、可能性のあるデッド引数を追加するアグレッシブなプロシージャ間パスの後に実行するクリーンアップパスとして、しばしば役立ちます。

`dse`: デッドストア除去 ¶

基本ブロックローカルな冗長ストアのみを考慮する、単純なデッドストア除去です。

`function-attrs`: 関数属性の推論 ¶

コールグラフを巡回し、非ローカルメモリにアクセスしない、または読み取りのみを行う関数を探し、それらにreadnone/readonlyマークを付ける単純なプロシージャ間パスです。さらに、関数の呼び出しによって、呼び出しを生き残るポインタ値のコピーが作成されない場合、（ポインタ型の）関数引数に「nocapture」マークを付けます。これは、ポインタが参照解除されるだけで、関数から返されたり、グローバルに保存されたりしないことをほぼ意味します。このパスは、コールグラフの下位から上位への巡回として実装されています。

`globaldce`: デッドグローバル除去 ¶

この変換は、プログラムから到達不可能な内部グローバル変数を除去するように設計されています。アグレッシブなアルゴリズムを使用して、確実に有効なグローバル変数を検索します。必要なグローバル変数をすべて検出した後、残りを削除します。これにより、到達不可能なプログラムの再帰的なチャンクを削除できます。

`globalopt`: グローバル変数オプティマイザ ¶

このパスは、アドレスが取得されたことがない単純なグローバル変数を変換します。明らかに真である場合、読み取り/書き込みグローバル変数を定数としてマークし、ストアのみが行われた変数を削除するなどします。

`gvn`: グローバル値ナンバリング ¶

このパスは、グローバル値ナンバリングを実行して、完全に冗長な命令と部分的に冗長な命令を除去します。また、冗長なロードの除去も行います。

`indvars`: 誘導変数の正規化 ¶

この変換は、誘導変数（およびそれから派生した計算）を分析および変換し、後続の分析および変換に適したより単純な形式にします。

この変換は、識別可能な誘導変数を持つ各ループに対して以下の変更を加えます。

すべてのループは、0から始まり1ずつステップする単一の正規化された誘導変数を持つように変換されます。
正規化された誘導変数は、ループヘッダーブロックの最初のPHIノードであることが保証されます。
ポインタ演算の再帰は、配列添え字を使用するように昇格されます。

ループのトリップ回数が計算可能な場合、このパスは次の変更も行います。

ループの終了条件は、誘導変数の値と終了値を比較するように正規化されます。これは、次のようなループになります。
```
for (i = 7; i*i < 1000; ++i)

into
```
```
for (i = 0; i != 25; ++i)
```
ループ外のindvarから派生した式の使用は、ループの外で派生値を計算するように変更され、誘導変数の終了値への依存関係が排除されます。ループの唯一の目的が、ある派生式の終了値を計算することである場合、この変換によってループはデッドになります。

この変換の後には、目的のループ変換がすべて実行された後に強度削減を行う必要があります。さらに、それが有利なターゲットでは、ループを0にカウントダウンするように変換できます（「doループ」最適化）。

`inline`: 関数の統合/インライン化 ¶

関数の下位から上位へのインライン化。

`instcombine`: 冗長な命令の結合 ¶

より少なく、単純な命令を形成するように命令を結合します。このパスはCFGを変更しません。このパスでは、代数的な簡素化が行われます。

このパスは、次のようなものを結合します。

%Y = add i32 %X, 1
%Z = add i32 %Y, 1

次のように

%Z = add i32 %X, 2

これは、ワークリスト駆動型の単純なアルゴリズムです。

このパスは、プログラムに対して次の正規化が実行されることを保証します。

二項演算子が定数オペランドを持つ場合、右側に移動されます。
定数オペランドを持つビット単位演算子は、常にシフトが最初に実行され、次にor、次にand、次にxorとなるようにグループ化されます。
比較命令は、可能であれば<、>、≤、または≥から=または≠に変換されます。
ブール値に関するすべてのcmp命令は、論理演算に置き換えられます。
add X, Xはmul X, 2 ⇒ shl X, 1として表現されます。
定数2のべき乗の引数を持つ乗算は、シフトに変換されます。
…など。

このパスは、特定のよく知られた関数呼び出し（例：ランタイムライブラリ関数）への呼び出しも簡素化できます。たとえば、main()関数内にあるexit(3)の呼び出しは、単にreturn 3に変換できます。ライブラリ呼び出しを簡素化するかどうかは、-function-attrsパスと、異なるターゲットでのライブラリ呼び出しに関するLLVMの知識によって制御されます。

`aggressive-instcombine`: 式パターンの結合 ¶

より少なく、単純な命令を持つ式を形成するように式パターンを結合します。

たとえば、このパスは、適用可能な場合、TruncInstによってポスト支配される式の幅をより小さい幅に削減します。

これは、CFGを変更でき、O(1)よりも高い複雑さを必要とするパターン最適化を含むため、instcombineパスとは異なります。したがって、instcombineパスよりも少ない回数実行する必要があります。

`internalize`: グローバルシンボルの内部化 ¶

このパスは、入力モジュール内のすべての関数をループ処理し、メイン関数を探します。メイン関数が見つかった場合、他のすべての関数と初期化子を持つすべてのグローバル変数は内部としてマークされます。

`ipsccp`: プロシージャ間スパース条件付き定数伝播 ¶

スパース条件付き定数伝播のプロシージャ間バリアントです。

`jump-threading`: ジャンプスレッディング ¶

ジャンプスレッディングは、基本ブロックを流れる異なる制御フローのスレッドを見つけようとします。このパスは、複数の先行要素と複数の後続要素を持つブロックを調べます。ブロックの1つ以上の先行要素が、常に後続要素の1つへのジャンプを引き起こすと証明できる場合、このブロックの内容を複製することにより、先行要素から後続要素へのエッジを転送します。

これが発生する可能性のある例を以下に示します。

if () { ...
  X = 4;
}
if (X < 3) {

この場合、最初のifの最後にある無条件分岐は、2番目のifのfalse側にリベクトル化できます。

`lcssa`: ループクローズドSSA形式パス ¶

このパスは、ループ境界を越えて有効なすべての値に対して、ループの最後にphiノードを配置することにより、ループを変換します。たとえば、左側のコードを右側のコードに変換します。

for (...)                for (...)
    if (c)                   if (c)
        X1 = ...                 X1 = ...
    else                     else
        X2 = ...                 X2 = ...
    X3 = phi(X1, X2)         X3 = phi(X1, X2)
... = X3 + 4              X4 = phi(X3)
                            ... = X4 + 4

これはまだ有効なLLVMです。追加のphiノードは純粋に冗長であり、InstCombineによって簡単に削除されます。この変換の主な利点は、LoopUnswitchingなど、他の多くのループ最適化を簡素化することです。LCSSA形式のループ用語セクションで詳細を読むことができます。

`licm`: ループ不変コード移動 ¶

このパスは、ループ不変コード移動を実行し、可能な限り多くのコードをループの本体から削除しようとします。これは、コードをプリヘッダーブロックにホイスティングするか、安全であれば終了ブロックにシンクすることにより行われます。このパスはまた、ループ内の必須エイリアスのメモリ位置をレジスタに配置することで、 "不変" ロードとストアのホイスティングとシンクも行います。

ループから操作をホイスティングすることは、正規化変換です。ミドルエンドでの後続の最適化を有効にし、簡素化します。レジスタ圧力を軽減するためのホイスティングされた命令の再マテリアライゼーションは、レジスタ圧力に関するより正確な情報を持っており、ライブレンジを増やすLICM以外の最適化も処理するバックエンドの責任です。

このパスは、2つの目的でエイリアス分析を使用します。

ループ不変のロードと呼び出しをループの外に移動します。ループ内のロードまたは呼び出しが、ストアされたものとエイリアスにならないと判断できる場合、他の命令と同様にホイスティングまたはシンクできます。
メモリのスカラープロモーション。ループ内にストア命令がある場合、ループ内ではなくループの後にストアが行われるように移動しようとします。これは、いくつかの条件が真である場合にのみ発生します。
1. ストアされたポインタはループ不変です。
2. ループ内に、ポインタと可能性のあるエイリアスを持つストアやロードはありません。ループ内に、ポインタをmod/refする呼び出しはありません。
これらの条件が真の場合、ポインタのループ内のロードとストアを一時的なalloca’d変数を使用するようにプロモーションできます。次に、mem2reg機能を使用して、変数に適切なSSA形式を構築します。

`loop-deletion`: デッドループの削除 ¶

このファイルは、デッドループ削除パスを実装しています。このパスは、無限でない計算可能なトリップ回数を持ち、副作用や揮発性命令がなく、関数の戻り値の計算に寄与しないループを除去する役割を担っています。

`loop-extract`: ループを新しい関数に抽出 ¶

スカラー変換 ExtractLoop() をラップするパスで、最上位の各ループをそれぞれ新しい関数に抽出します。ループが特定の関数内の *唯一の* ループである場合、変更されません。これは、bugpoint を使用したデバッグに最も役立つパスです。

`loop-reduce`: ループ強度削減 ¶

このパスは、1つ以上のコンポーネントにループ誘導変数を含むループ内の配列参照に対して強度削減を実行します。これは、最初の反復の配列アクセスの初期値を保持する新しい値を作成し、次にループ内で新しいGEP命令を作成して値を適切な量だけ増分することにより実現されます。

`loop-rotate`: ループの回転 ¶

単純なループ回転変換です。概要は回転ループのループ用語にあります。

`loop-simplify`: 自然ループの正規化 ¶

このパスは、自然ループをより単純な形式に変換するためのいくつかの変換を実行します。これにより、後続の解析と変換がより簡単で効果的になります。概要はループ用語、ループ簡略化形式にあります。

ループプリヘッダーの挿入により、ループの外側からループヘッダーへの単一の非クリティカルなエッジが保証されます。LICMなどの多くの解析と変換が簡素化されます。

ループ出口ブロックの挿入により、ループからのすべての出口ブロック（ループの内側に先行ブロックを持つループの外側のブロック）は、ループの内側からのみ先行ブロックを持つことが保証されます（したがって、ループヘッダーによって支配されます）。これにより、LICMに組み込まれているストア・シンキングなどの変換が簡素化されます。

このパスは、ループに正確に1つのバックエッジがあることも保証します。

simplifycfgパスは、分割されたが不要になったブロックをクリーンアップするため、このパスの使用によって生成されたコードのパフォーマンスが低下することはありません。

このパスは明らかにCFGを変更しますが、ループ情報と支配情報も更新します。

`loop-unroll`: ループの展開 ¶

このパスは、単純なループ展開を実装します。indvarsパスによってループが正規化されている場合に最適に機能し、ループの繰り返し回数を簡単に判断できます。

`loop-unroll-and-jam`: ループの展開とジャム ¶

このパスは、単純な展開とジャムの古典的なループ最適化パスを実装します。ループを変換します

for i.. i+= 1              for i.. i+= 4
  for j..                    for j..
    code(i, j)                 code(i, j)
                               code(i+1, j)
                               code(i+2, j)
                               code(i+3, j)
                           remainder loop

これは、外部ループを展開し、内部ループを1つに「ジャム」（融合）したものと見なすことができます。新しい内部ループで変数またはロードを共有できる場合、これによりパフォーマンスが大幅に向上する可能性があります。依存関係分析を使用して、変換が安全であることを証明します。

`lower-global-dtors`: グローバルデストラクタのローワー化 ¶

このパスは、グローバルモジュールデストラクタ（llvm.global_dtors）を、llvm.global_ctorsにグローバルコンストラクタとして登録され、デストラクタ関数を登録するための__cxa_atexitへの呼び出しを含むラッパー関数を生成することにより、ローワー化します。

`lower-atomic`: 原子組み込み関数を非原子形式にローワー化 ¶

このパスは、既知の非プリエンプティブな環境で使用するために、原子組み込み関数を非原子形式にローワー化します。

このパスは、環境が非プリエンプティブであることを検証しません（一般的に、これには、ビットコード形式では利用できない可能性のあるライブラリを含む、プログラムの全体のコールグラフに関する知識が必要です）。単にすべての原子組み込み関数をローワー化します。

`lower-invoke`: アンワインドレスコードジェネレーター向けにinvokeをcallにローワー化 ¶

この変換は、スタックアンワインドをまだサポートしていないコードジェネレーターで使用することを目的としています。このパスは、invoke命令をcall命令に変換するため、例外処理landingpadブロックはデッドコードになります（その後-simplifycfgパスを実行して削除できます）。

`lower-switch`: `SwitchInst`をブランチにローワー化 ¶

一連のブランチでswitch命令を書き換えます。これにより、ターゲットは、都合がよくなるまでswitch命令を実装しなくても済みます。

`mem2reg`: メモリからレジスタへの昇格 ¶

このファイルは、メモリ参照をレジスタ参照に昇格させます。ロードとストアのみを使用するalloca命令を昇格させます。支配フロンティアを使用してphiノードを配置し、関数を深さ優先順にトラバースして、ロードとストアを適切に書き換えることで、allocaを変換します。これは、「刈り込まれた」SSA形式を構築するための標準的なSSA構築アルゴリズムです。

`memcpyopt`: memcpy最適化 ¶

このパスは、memcpy呼び出しの削除、またはストアのセットをmemsetに変換することに関連するさまざまな変換を実行します。

`mergefunc`: 関数のマージ ¶

このパスは、マージ可能な同等の関数を探して折りたたみます。

関数セット間に全順序が導入されます。2つの関数のうちどちらが大きいかを答える比較を定義します。これにより、関数を二分木に配置できます。

新しい関数ごとに、ツリー内の同等性をチェックします。

同等物が存在する場合は、そのような関数を折りたたみます。両方の関数がオーバーライド可能である場合、機能を新しい内部関数に移動し、それに対する2つのオーバーライド可能なthunkを残します。

同等物が存在しない場合は、この関数をツリーに追加します。

ルックアップルーチンはO(log(n))の複雑さを持つのに対し、マージプロセス全体はO(n*log(n))の複雑さを持っています。

詳細については、この記事をお読みください。

`mergereturn`: 関数の終了ノードの統一 ¶

関数内にret命令が1つ以下しかないことを保証します。さらに、CFGの新しい終了ノードがどれであるかを追跡します。

`partial-inliner`: 部分インライナー ¶

このパスは、通常、関数の本体を囲むif文をインライン化することにより、部分インライン化を実行します。

`reassociate`: 式の再関連付け ¶

このパスは、より良い定数伝播、GCSE、LICM、PREなどを促進するように設計された順序で、交換可能な式を再関連付けします。

例：4 + (x + 5) ⇒ x + (4 + 5)

このアルゴリズムの実装では、定数にrank = 0、関数引数にrank = 1が割り当てられ、他の値には現在の関数の逆ポストオーダートラバーサルに対応するrankが割り当てられます（2から開始）。これにより、ループ内の深い値にはループ外の値よりも高いrankが効果的に与えられます。

`rel-lookup-table-converter`: 相対ルックアップテーブルコンバーター ¶

このパスは、ルックアップテーブルをPICフレンドリーな相対ルックアップテーブルに変換します。

`reg2mem`: すべての値をスタックのスロットに格下げ ¶

このファイルは、すべてのレジスタをメモリ参照に格下げします。mem2regの逆になることを意図しています。load命令に変換することにより、基本ブロック全体で有効な値はalloca命令とphiノードの前にあるload命令のみになります。これにより、CFGのハッキングがはるかに簡単になることを意図しています。後のハッキングを容易にするために、エントリブロックは2つに分割され、導入されたalloca命令（およびそれ以外何もない）がエントリブロックに含まれます。

`sroa`: 集約のスケーラスイッチング ¶

よく知られた集約のスケーラスイッチング変換です。この変換は、可能な場合、集約型（構造体または配列）のalloca命令を、各メンバーの個々のalloca命令に分割します。次に、可能な場合、個々のalloca命令を、きれいなスカラーSSA形式に変換します。

`sccp`: スパース条件付き定数伝播 ¶

スパース条件付き定数伝播とマージは、次のように要約できます。

値は、それ以外が証明されない限り一定であると仮定します。
BasicBlockは、それ以外が証明されない限りデッドであると仮定します。
値が定数であることを証明し、定数で置き換えます。
条件分岐が無条件分岐であることを証明します。

このパスは、定義をデッドにする傾向があります。DCEパスをこのパス実行後のある時点で実行することをお勧めします。

`simplifycfg`: CFGの簡素化 ¶

デッドコードの削除と基本ブロックのマージを実行します。具体的には

先行ノードのない基本ブロックを削除します。
先行ノードが1つだけで、その先行ノードが1つの後続ノードしか持たない場合、基本ブロックをその先行ノードにマージします。
単一の前身ノードを持つ基本ブロックのPHIノードを削除します。
無条件分岐のみを含む基本ブロックを削除します。

`sink`: コードシンク ¶

このパスは、可能であれば命令を後続ブロックに移動するため、結果が不要なパスでは実行されません。

`simple-loop-unswitch`: ループのアンスイッチ ¶

このパスは、ループ不変条件の分岐を含むループを複数のループに変換します。例えば、左のコードを右のコードに変換します。

for (...)                  if (lic)
    A                          for (...)
    if (lic)                       A; B; C
        B                  else
    C                          for (...)
                                   A; C

これにより、コードサイズが指数関数的に増加する可能性があるため（ループがアンスイッチされるたびに倍増）、結果のコードが閾値よりも小さくなる場合のみアンスイッチします。

このパスは、ループ不変条件をループの外に持ち上げるために、事前にLICMを実行する必要があります。これにより、アンスイッチの機会が明らかになります。

`strip`: モジュールからすべてのシンボルを削除する ¶

コードのストリップを実行します。この変換によって削除されるもの：

仮想レジスタの名前
内部グローバル変数と関数のシンボル
デバッグ情報

この変換によりコードの可読性が大幅に低下するため、コードサイズを削減したり、コードのリバースエンジニアリングを困難にするなど、stripユーティリティを使用する場合にのみ使用してください。

`strip-dead-debug-info`: 使用されていないシンボルのデバッグ情報を削除する ¶

コードのストリップを実行します。「strip」と似ていますが、使用されていないシンボルのデバッグ情報のみを削除します。

`strip-dead-prototypes`: 使用されていない関数プロトタイプを削除する ¶

このパスは、入力モジュールのすべての関数をループ処理し、デッド宣言を見つけて削除します。デッド宣言とは、実装がない関数の宣言です（つまり、使用されていないライブラリ関数の宣言）。

strip-debug-declare: すべてのllvm.dbg.declareイントリンシックと#dbg_declareレコードを削除します。 ——————————————————————-

コードのストリップを実行します。「strip」と似ていますが、llvm.dbg.declareイントリンシックのみを削除します。

`strip-nondebug`: dbgシンボルを除くすべてのシンボルをモジュールから削除する ¶

コードのストリップを実行します。「strip」と似ていますが、dbg情報は保持されます。

`tailcallelim`: テールコールの削除 ¶

このファイルは、現在の関数の呼び出し（自己再帰）に続いて、関数のエントリへの分岐を持つreturn命令を変換し、ループを作成します。このパスは、基本アルゴリズムに以下の拡張機能も実装しています。

呼び出しとreturnの間にある些細な命令は、変換を妨げません。ただし、現在、分析では本当に役に立つ命令（デッドな命令のみ）を移動することはできません。
このパスは、結合式によってテール再帰を妨げられている関数を、累算変数を使用するように変換します。これにより、典型的なナイーブな階乗またはフィボナッチの実装を効率的なコードにコンパイルします。
関数がvoidを返す場合、returnが呼び出しによって返された結果を返す場合、または関数が関数のすべての出口で実行時定数を返す場合、TREが実行されます。returnが何か他のもの（定数0など）を返し、それでもTREできる可能性はありますが、ありそうではありません。関数の*他のすべての*return命令がまったく同じ値を返す場合、TREできます。
呼び出し元が呼び出し元のスタックフレームにアクセスしないことを証明できれば、（コードジェネレータによって）テールコールの削除の対象としてマークされます。

ユーティリティパス ¶

このセクションでは、LLVMユーティリティパスについて説明します。

`deadarghaX0r`: デッド引数のハッキング（BUGPOINT専用。使用しないでください）¶

デッド引数の削除と同じですが、外部の関数への引数を削除します。bugpointでのみ使用してください。

`extract-blocks`: モジュールから基本ブロックを抽出する（bugpoint用）¶

このパスは、bugpointによってモジュールからすべてのブロックを独自の関数に抽出するために使用されます。

`instnamer`: 匿名命令に名前を付ける ¶

これは、命令に名前を与える小さなユーティリティパスです。これは、最適化の効果を比較する場合に非常に役立ちます。名前のない命令を削除すると、他のすべての命令の番号が変更され、差分が非常にノイズが多くなる可能性があるためです。

`verify`: モジュール検証器 ¶

LLVM IRコードを検証します。これは、テスト中の最適化の後で実行すると便利です。llvm-asは、ビットコードを出力する前にその入力を検証し、また、不正なビットコードはLLVMをクラッシュさせる可能性があることに注意してください。したがって、すべての言語フロントエンドは、最適化変換を実行する前に、その出力を検証することをお勧めします。

二項演算子の両方のパラメータは、同じ型です。
メモリアクセス命令のインデックスが他のオペランドと一致することを検証します。
算術演算などが、ファーストクラス型に対してのみ実行されることを検証します。シフトや論理演算が整数型に対してのみ行われることを検証します。
switch文内のすべての定数は、正しい型です。
コードは有効なSSA形式です。
ラベルを他の型（構造体など）に入れることや、ラベルを返すことはできません。
自己参照できるのはPHIノードのみです。%x = add i32 %x、%xは無効です。
PHIノードは、各先行ノードのエントリを、余分なものなしで持つ必要があります。
PHIノードは、基本ブロックの最初の要素で、すべてまとめてグループ化されている必要があります。
PHIノードは、少なくとも1つのエントリを持つ必要があります。
すべての基本ブロックは、終端命令のみで終わる必要があり、終端命令を含んではいけません。
関数のエントリノードは、先行ノードを持つことができません。
すべての命令は、基本ブロックに埋め込まれている必要があります。
関数は、void型の引数をとることができません。
関数の引数リストが、宣言された型と一致することを検証します。
void値の名前を指定することはできません。
初期化子が無い内部グローバル値を持つことはできません。
ret命令が、関数戻り値の型と一致しない値を返すことはできません。
関数呼び出しの引数の型は、関数プロトタイプと一致します。
コード全体に散らばっているアサートによってテストされる他のすべてのもの。

これは完全なセキュリティ検証（Javaなど）を提供するものではなく、コードが整形式であることを確認するだけです。