---
title: データフロー解析
url: https://doc.liz6.com/ja/compilers/05-optimization/01-data-flow-analysis
locale: ja
area: compilers
tags:
- data flow analysis
- gen/kill
- meet operator
- forward/backward
- may/must
- reaching definitions
- liveness
- available expressions
- fixed-point iteration
- worklist algorithm
- lattice
- monotonicity
- MOP
- MFP
- distributive function
- sparse analysis
- SSA
- compilers
- optimization
date: 2026-06-30
modified: 2026-07-19
description: コンパイラ最適化の前処理層:制御フローグラフ上でデータフローの事実を収束するまで反復伝播する。gen/kill/meet/worklist の同一フレームワークを使い、方向と meet 演算を変えるだけで、liveness、reaching defs、available expressions の3つの異なる問題を解くことができる。
---

# データフロー解析

> コンパイラ最適化の前処理層:制御フローグラフ上でデータフローの事実を収束するまで反復伝播する。gen/kill/meet/worklist の同一フレームワークを使い、方向と meet 演算を変えるだけで、liveness、reaching defs、available expressions の3つの異なる問題を解くことができる。

## 概要

コンパイラは「プログラムの各地点で、どの変数が使用されており、どの定義がそこに到達し、どの式がすでに計算済みなのか」を知る必要がある——これらの情報は単一の命令からは得られず、制御フロー全体にわたって伝播されなければならない。**データフロー解析(data flow analysis)** とは、プログラムの制御フローグラフ(CFG)上でデータフローの事実を反復伝播させ、すべての地点で収束するまで処理を続ける手法である。

このプロセスを**統一フレームワーク**(Kildall, 1973)として抽象化することで、同じ反復アルゴリズムの「方向」「meet 演算」「伝達関数」を変更するだけで、多様な解析問題を解くことができる。ここではこの統一フレームワークについて解説し、その後に最も重要な3つの実例である reaching definitions、liveness、available expressions について詳しく述べる——これらは [古典的最適化](/compilers/05-optimization/02-classic-optimizations.md) の直接的な前提知識でもある。

## 統一フレームワーク

データフロー解析の4つの構成要素:

| 構成要素 | 意味 | 例 (reaching defs) |
|------|------|-------------------|
| **方向** | forward(エントリからアウトプットへ) または backward(アウトプットからエントリへ) | forward |
| **meet 演算** | 経路が合流する際の事実の結合方法: ∪(may) または ∩(must) | ∪(may) |
| **伝達関数** | 1つの命令が入ってきた事実をどのように変更し、その命令の出力事実を生成するか | `out = gen ∪ (in - kill)` |
| **初期値** | 各ノードの初期推定値 (通常は top または bottom) | in[entry]=∅, out[B]=∅ |

- **may 解析**(∪): 「どのような可能性があるか」を問う——過剰近似であり、過剰検出を許容し見落としを避ける。reaching definitions は may 解析である:ある定義がその地点に「到達する可能性がある」。
- **must 解析**(∩): 「どのようなことが確実か」を問う——不足近似であり、誤検出を避けて見逃しを許容する。available expressions は must 解析である:ある式が「すでに計算済みであることが確実」。

伝達関数は通常、次のように表記される:`out[B] = gen[B] ∪ (in[B] - kill[B])`(または meet によって ∪ の代わりに ∩ を用いる)。ここで gen はそのブロック内で「生成」される新しい事実、kill はそのブロック内で「無効化」される古い事実を指す。

### 反復求解: worklist アルゴリズム

CFG 全体を安定(不動点)に達するまで繰り返しスキャンする:

```
for each block B: out[B] = ∅ (または top)
worklist = all blocks
while worklist not empty:
    B = worklist.pop()
    in[B] = meet(out[predecessors of B])
    old_out = out[B]
    out[B] = gen[B] ∪ (in[B] - kill[B])     ← 伝達関数
    if out[B] changed:
        worklist.push(successors of B)        ← 変更された部分のみ伝播
```

終端性は2つの条件によって保証される:**格(lattice)の高さが有限**(事実集合に最大要素が存在する)であり、**伝達関数が単調**(新しい in → 新しい out は古い値より小さくならない)——不動点定理による。実用的な CFG においては、収束は非常に速い(通常 3〜5 回の反復で完了する)。

worklist のソート順序は収束速度に影響する——前駆ノードがすでに更新されたノードを先に処理する(CFG のトポロジカル順序で近似する)方が、ランダムに処理するよりも効率的である。

## 3つの古典的解析

### Reaching Definitions (前方, may, ∪)

**問題**: プログラムの地点 p において、後続の代入によって上書きされずに p に到達する可能性のある代入(definition)は何か？

```
gen[B]:  本ブロック内で最後に変数 x に代入を行う文 (それより前の代入は後続の代入によって上書きされる)
kill[B]: 本ブロック内の新しい代入によって「殺される」、他の場所での x へのすべての代入
```

use-def チェーンの構築の基礎となる——[SSA 形式](/compilers/04-intermediate-representation/01-ssa-form.md) が登場した後、reaching definitions は SSA IR 上では疎になり、反復求解は不要となるが、通常の IR 上では依然として必須である。

### Liveness (後方, may, ∪)

**問題**: プログラムの地点 p において、変数 x の値は将来使用されるか(次回の代入前に使用されるか)？

```
方向を backward に変更:アウトプットから前駆ノードへ伝播
gen[B]:  本ブロック内で「使用」されるが、本ブロック内で「再定義」される前に使用される変数
kill[B]: 本ブロック内で「再定義」されるが、その定義前に本ブロック内で「使用」されない変数 (新しい値が古い値を上書きする)
```

活度解析(liveness analysis)はレジスタ割り当てを直接決定する:**2つの変数が同時にアクティブでなければ、同じレジスタを共有できる**( [レジスタ割り当て](/compilers/05-optimization/03-register-allocation.md) を参照)。これはコンパイラ最適化において最も頻繁に行われる解析である。

### Available Expressions (前方, must, ∩)

**問題**: プログラムの地点 p において、式 `x + y` はすでに計算済みであり、かつ x と y のいずれも再代入されていないか？

```
gen[B]:  本ブロック内で計算された式 (かつその後 x/y が再定義されていない)
kill[B]: 本ブロック内で x または y への代入が行われた後、x または y を含むすべての式は無効化される
meet:   ∩ (must)——エントリ地点の利用可能式 = すべての前駆ノードのアウトプット地点の共通部分
```

available expressions の情報は **CSE(共通部分式除去)** に直接利用される——もし `x + y` が現在の地点で利用可能であれば、再計算せずに以前の結果を使用する。

## MOP vs MFP: 理想解と不動点解の間のギャップ

- **MOP(Meet Over all Paths)**: プログラムの地点 p に対して、「p に到達するすべての可能な経路が運ぶ事実」を集め、それらの事実に対して meet を実行する。これが理想解である。
- **MFP(Maximal Fixed Point)**: 反復不動点アルゴリズムによって得られる解。**MFP ≤ MOP**(格の順序において、MFP はより保守的になり得る)。

**分配可能(distributive)な伝達関数**——つまり `f(a meet b) == f(a) meet f(b)` を満たす関数——の場合、MFP = MOP となり、不動点が理想解となる。reaching definitions と liveness の伝達関数は分配可能であるが、constant propagation の伝達関数は分配可能ではないため、MFP は MOP よりも保守的になる。

## SSA における疎データフロー

[SSA 形式](/compilers/04-intermediate-representation/01-ssa-form.md) において、全体の反復不動点フレームワークは大幅に簡素化される:

- 各変数は1回だけ定義される → reaching definition は「この使用に対応する定義はどこか」(直接的な def-use チェーンであり、解析不要) に退化する。
- liveness は def-use グラフ上で実行できる——各定義地点から到達可能なすべての使用地点がその live range であり、CFG 全体で反復する必要はない。
- 「CFG 全体に事実を伝播する」多くの pass は、SSA では「dominator tree 上での単一パス伝播」に退化する。

これが SSA が「疎解析(sparse analysis)」と呼ばれる理由である——データフローの事実は CFG のすべての辺ではなく、def と use の地点にのみ付随する。

## 参考文献

- **Kildall (1973)**: "A Unified Approach to Global Program Optimization" — データフロー解析の統一フレームワーク
- **Dragon Book**: Chapter 9, Machine-Independent Optimizations — gen/kill テーブルと不動点アルゴリズムの完全な解説を含む
- **Cooper/Torczon**: "Engineering a Compiler", Chapters 8–10

*Keywords: data flow analysis, gen/kill, meet operator, forward/backward, may/must, reaching definitions, liveness, available expressions, fixed-point iteration, worklist algorithm, lattice, monotonicity, MOP, MFP, distributive function, sparse analysis, SSA*