9 分で読了 #compilers #最適化
このページの目次

古典的最適化

最適化パイプラインで必ず行うべき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 = すべての命令
各命令について:
    命令が生成する値に使用者(useリストが空)がなく、かつ命令に副作用がない場合 (store/call/IO以外):
        死んでいる(marked dead)としてマークする
        命令の各オペランドについて: 定義元を確認し、使用者を失ったことで死んでいる可能性があれば処理する
不動点に達するまで反復する

除去できない場合の硬制的な制約: 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;
}                                  }

実装にはループ検出⁠(自然ループの検出——header blockがすべてのbody blockを支配し、back edgeがheaderに戻っている)に依存します。

ループ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