9 分で読了
このページの目次

古典的最適化

最適化パイプラインで必ず行うべき7つの古典的最適化——定数畳み込みからループ不変量外だし、SROAまで。各手法がデータフロー解析を用いて最適化の機会をどのように見つけるか、そして副作用、volatile、非正規化制御フローなどのハードリミットがある場合に何故できないか。

概要

データフロー解析は、「ある地点で、どの式が既に計算済みか、どの変数が生きているか」という情報を提供します。ここでは、その情報を使って何を行うかについて解説します。産業用コンパイラが必ず行う7つの最適化、各手法がデータフロー解析の結果を用いて最適化の機会をどのように見つけるか、そしていつ実行できないか（想定以上に多くの制約条件があります）。これらの最適化はLLVMでは異なるpassに対応しており、コンパイラパイプライン内で繰り返し実行されます。あるpassの最適化が、次のpassの最適化の機会を創出します。

すべての最適化の前提条件は、SSA形式で行うことです。SSAにおけるdef-useチェーンにより、各最適化はO(n)またはO(n log n)のスパース操作となります。

1. 定数畳み込みと定数伝播

定数畳み込み(constant folding): コンパイル時に定数式を計算します。

x = 2 + 3    →  x = 5
y = a * 0    →  y = 0

定数伝播(constant propagation): 定数定義を使用しているすべての箇所を定数に置換します。

x = 5
y = x + 1    →  y = 6

これらは通常、同じpassで実行されます（伝播と畳み込みを交互に行い、飽和するまで再帰）。SSA形式では、def-useチェーンに沿って置換するだけでよく、データフロー解析は不要です。SSAでは各変数の定義箇所が一意であるためです。

条件付き定数伝播はさらに強力です。if (false) { ... } のような定数条件を用いて、実行不可能な分岐を除去し、分岐内のコードがコンパイルされないようにします。これはWegman-Zadeckアルゴリズムの中核であり、SSAに基づくスパース条件付き定数伝播(SCCP)に基づいています。

2. CSE（共通部分式除去）

問題⁠: a = b + c; ... ; d = b + c において、中間で b と c が変更されていない場合、2回目の b + c は共通部分式であり、直接 a の値を使用できます。

実装は利用可能式(available expressions)（データフロー解析由来）に依存します。

各式 e = x op y について:
  利用可能式の情報で確認: e は現在地点で「まだ有効」か
  有効であれば: 既存の結果を使用し、現在の計算を削除
  それ以外: 現在の計算を保持し、e を「ここで利用可能」とマーク

LLVMはCSEの一般化としてGVN(Global Value Numbering)⁠を使用します。これは「同一式の2つの出現」だけでなく、各値に番号を割り当てます。異なる式でも値が等しい場合（例: x+1 と 1+x、交換法則が成り立つ場合）、同じ値番号を共有します。

3. DCE（デッドコード除去）

問題⁠: 命令が生成する値が一度も使用されていない場合、その命令は削除できます。

SSA形式におけるDCEは非常に単純です。def-useチェーンを辿ります。

worklist = すべての命令
各命令について:
    if 命令が生成する値に使用者がいない (useリストが空) かつ 命令に副作用がない (store/call/IOではない):
        デッドとしてマーク
        命令の各オペランドについて: 定義元を確認し、使用者を失うことでデッドになる可能性を調べる
不動点に達するまで反復

除去できないハードリミットがいくつかあります。store（メモリを変更し、他の場所からloadされる可能性がある）、call（副作用があるため、戻り値が使用されていても削除不可）、volatile load/store（明示的に保持するよう要求）。副作用を持つ命令は、コンパイラがその副作用の値も観察されないことを証明した場合のみ削除可能です。これにはより重い解析（MemorySSAなど、後述）が必要です。

4. Inlining（インライン展開）

問題⁠: call @f により、f の関数本体を呼び出し元に直接コピーし、関数呼び出しのオーバーヘッド（引数渡しのためのスタック操作、ジャンプ、リターン）を削除します。これにより、後続の最適化の文脈が露出します（特定の引数値において、関数本体内で新しい定数畳み込み/CSE/DCEのトリガーとなる可能性があるため）。

インライン展開のトレードオフは「行うか行わないか」ではなく、⁠いつ行うかです。

意思決定要因:
  - 関数本体のサイズ（小規模関数はインライン展開、大規模関数は展開しない場合あり -- 閾値は調整可能）
  - 呼び出し回数（1回しか呼び出されない関数は、インライン展開後、元の関数本体を直接削除可能）
  - ループ内の呼び出し（ループ本体内の呼び出しは、インライン展開後にループ最適化をトリガーできるため、より多くインライン展開される）
  - 再帰関数は最初のN層のみインライン展開（無限展開を防ぐため）

LLVMのインラインpassはコストモデルに基づいています。各call siteについて、インライン展開後のサイズ変化と性能収益を見積もり、個別に決定します。

5. LICM（ループ不変量外だし）

問題⁠: ループ本体内で各イテレーションごとに同じ値を計算する式を、ループの外に移動し、1回だけ計算するようにします。

while (i < n) {                    t = a + b          ← ループ前に移動
    x = a + b;        →           while (i < n) {
    i = i + 1;                         i = i + 1;
}                                  }

実装はループ検出⁠（自然ループの検出——すべてのbody blockを支配するheader blockを持ち、header blockに戻るback edgeが1つある）に依存します。

ループ L 内の各命令 instr について:
    if instr のオペランドがループ内で不変である (ループ定数の定義、またはループ外から来る場合):
        if instr がそれ到達するすべてのパスで、同じ命令によって支配されている (特定のパパスでスキップされない場合):
            if instr に副作用がない:
                instr をループ前置ブロック(preheader)に移動 → 元の位置から削除

最初の2つの条件は「外だししても意味が変わらない」ことを保証し、3つ目の条件はループ依存関係を持つ命令を除外します。

6. Loop Unrolling（ループ展開）

ループ本体をN回コピーし、分岐/バックエッジ/帰納変数更新のオーバーヘッドを削減します。

for i in 0..4:                     a[0] = b[0] + c[0]
    a[i] = b[i] + c[i]      →     a[1] = b[1] + c[1]
                                   a[2] = b[2] + c[2]
                                   a[3] = b[3] + c[3]

LLVMではデフォルトで2〜4回展開され、ループの境界がコンパイル時定数の場合のみ完全展開されます。展開後、CSEやベクトル化(SLP)がトリガーされることがよくあります。隣接する2つのloadが1回のSIMD loadにまとまります。

7. SROA（Aggregateのスカラ置換）

「構造体の alloca + フィールドごとの load/store」を「各フィールドの独立した変数」に置換します。

元:                              SROA後:
%struct = alloca {i32, float}      ; (allocaは分解される)
%f0 = gep %struct, 0, 0           %x = ...
store i32 %x, ptr %f0             %y = ...
%f1 = gep %struct, 0, 1           %add = add i32 %x, ...
store float %y, ptr %f1
%r = load i32, ptr %f0            → 各フィールドが独立したSSA仮想レジスタになる
%add = add i32 %r, 1              mem2reg が load/store の昇格をさらに続ける

SROAはmem2regの前処理です。Aggregateをフィールドに分解することで、mem2regが各フィールドを個別にSSAに昇格させることができます。両者を組み合わせた処理は、LLVM最適化パイプラインの起動時に最初に実行されるpassグループの一つです。

最適化の順序と繰り返し実行

最適化passは1回実行するだけでは不十分です。A passの最適化がB passの新しい機会を創出し、B passの最適化がA passの新しい機会を創出します。LLVMのpassパイプラインは複数回繰り返し実行されます（インライン→CSE→DCE→LICM→...）。各ラウンドで前ラウンドの残滓をクリーンアップします。ループ最適化(LICM + Unrolling)は、大規模なループ変換を集中的に行うために別段階に配置され、その後、新しいスカラ最適化のラウンドが続きます。

参考文献

  • Dragon Book: 第9章〜第10章 — マシン非依存最適化の完全な分類
  • Cooper/Torczon: "Engineering a Compiler", 第8章〜第10章 — 各最適化のアルゴリズムと擬似コード
  • LLVM: lib/Transforms/Scalar/ (スカラpass)、lib/Transforms/IPO/(インタープロシージャールpass)、lib/Analysis/ (データフロー解析)

Keywords: constant folding, constant propagation, SCCP, CSE, common subexpression elimination, GVN, global value numbering, DCE, dead code elimination, inlining, cost model, LICM, loop invariant code motion, loop unrolling, SROA, scalar replacement, mem2reg, pass pipeline, phase ordering

関連ページ

© 2026 liz's doc