概要
これまで見てきた最適化技法のほとんどは一つの関数（プロシージャ）内で実行される**プロシージャ内分析**（intraprocedural analysis）でした。しかし実際のプログラムは多くの関数呼び出しで構成されているため、関数境界を越えた**プロシージャ間分析**（interprocedural analysis）が必要です。
この記事ではプロシージャ間分析の核心概念と最も重要な応用であるポインタ分析を扱います。
1. プロシージャ間分析の必要性
1.1 関数呼び出しが最適化を妨げる例
void init(int* arr, int n) {
for (int i = 0; i < n; i++)
arr[i] = 0;
}
void process() {
int a[100];
init(a, 100);
int x = a[0]; // x = 0か？
}
`init`関数の内部を分析しなければ `a[0]` の値を知ることができません。保守的に `a[0]` がどんな値でもあり得ると仮定する必要があり、定数伝播ができません。
1.2 プロシージャ間分析で必要な情報
| 情報 | 必要な理由 |
| ---------------------------- | ------------------------------------ |
| 関数の副作用（side effects） | どのグローバル変数を修正するか |
| パラメータの別名（aliasing） | 2つのパラメータが同じメモリを指すか |
| 戻り値の範囲 | 関数の戻り値が定数か |
| 呼び出し先 | 関数ポインタによる間接呼び出しの対象 |
1.3 保守的仮定 vs プロシージャ間分析
// 保守的仮定（プロシージャ間分析なし）：
// - 関数呼び出しがすべてのグローバル変数を修正し得る
// - ポインタパラメータを通じてアクセス可能なすべてのメモリを修正し得る
// - 戻り値について何も分からない
// プロシージャ間分析後：
// - init()はarrが指す配列のみ修正
// - init()はグローバル変数を修正しない
// - init()後arr[0..n-1]はすべて0
2. 呼び出しグラフ（Call Graph）
2.1 定義
**呼び出しグラフ**はプログラムの関数をノードとし、呼び出し関係を辺として表現したグラフです。
// プログラム：
// main() -> foo() -> bar()
// -> baz() -> bar()
// -> qux()
// 呼び出しグラフ：
// main -> foo -> bar
// -> baz -> bar
// -> qux
2.2 間接呼び出しの問題
関数ポインタによる間接呼び出しは呼び出し先を静的に知ることが難しいです。
typedef int (*FuncPtr)(int);
int add1(int x) { return x + 1; }
int mul2(int x) { return x * 2; }
void apply(FuncPtr f, int x) {
int result = f(x); // fがadd1かmul2か分からない
}
この場合ポインタ分析を通じて `f` が指し得る関数の集合を推定します。
2.3 呼び出しグラフの構成方法
**Class Hierarchy Analysis（CHA）**：オブジェクト指向言語でクラス階層を基に可能な呼び出し先を決定
// Javaの例：
// Animal.speak()が呼び出されると
// Dog.speak()、Cat.speak()などすべてのサブクラスのメソッドが可能な対象
// CHA：Animalのすべてのサブクラスのspeak()を候補に含む
// RTA（Rapid Type Analysis）：実際に生成された型のみ考慮
// VTA（Variable Type Analysis）：変数の実際の型を追跡
3. 文脈感度（Context Sensitivity）
3.1 文脈非感度分析
関数が呼び出される文脈を区別せず、すべての呼び出し地点の情報を合わせて分析します。
// 関数identity：
int identity(int x) { return x; }
// 呼び出し地点：
a = identity(1); // 呼び出し1
b = identity(2); // 呼び出し2
// 文脈非感度分析：
// identityのx = {1, 2}（すべての呼び出しの引数を統合）
// identityの戻り値 = {1, 2}
// -> a = {1, 2}, b = {1, 2}（不正確！）
3.2 文脈感度分析
各呼び出し地点を個別に分析します。
// 文脈感度分析：
// 呼び出し1の文脈：identity(1) -> 戻り値 = 1 -> a = 1
// 呼び出し2の文脈：identity(2) -> 戻り値 = 2 -> b = 2
// 正確な結果！
3.3 文脈の表現方法
**呼び出し文字列（Call String）**：呼び出しスタックを文脈として使用
// main -> foo -> identity（文脈：[main, foo]）
// main -> bar -> identity（文脈：[main, bar]）
// k制限呼び出し文字列：最近k個の呼び出しのみ考慮
// k=1：[foo], [bar]
// k=2：[main,foo], [main,bar]
**関数要約（Summary）**：関数の入出力関係を要約
// identity関数の要約：
// 入力x -> 出力x（恒等関数）
// 各呼び出し地点で要約を適用：
// identity(1) -> 1
// identity(2) -> 2
4. ポインタ分析（Pointer Analysis）
4.1 ポインタ分析とは
プログラムの各地点でポインタが指し得るメモリ位置の集合を決定する分析です。
// ポインタ分析の質問：
// ポインタpが指し得る対象は？
int a, b;
int *p;
if (cond)
p = &a;
else
p = &b;
// この地点でpのpoints-to集合：pts(p) = {a, b}
4.2 ポイント・ツー関係の種類
// アドレス取得：p = &x -> pがxを指す
// コピー： p = q -> pがqが指すものを指す
// ロード： p = *q -> pがqが指すものが指すものを指す
// ストア： *p = q -> pが指すものがqが指すものを指す
4.3 Andersenの分析
**包含ベース（inclusion-based）**分析とも呼ばれます。各ポインタ変数に対して別個のpoints-to集合を維持します。
アルゴリズム：Andersen分析
入力：ポインタ代入文の集合
出力：各変数のpoints-to集合
規則：
p = &x -> {x}をpts(p)に追加
p = q -> pts(q)をpts(p)に追加
p = *q -> pts(q)の各要素rに対して、pts(r)をpts(p)に追加
*p = q -> pts(p)の各要素rに対して、pts(q)をpts(r)に追加
反復：変化がなくなるまで
例：
// プログラム：
p = &a; // pts(p) = {a}
q = &b; // pts(q) = {b}
p = q; // pts(p) = {a, b}（pts(q)をpts(p)に追加）
r = &p; // pts(r) = {p}
s = *r; // rがpを指すので、pts(p) = {a, b}をpts(s)に追加
// pts(s) = {a, b}
複雑度：O(n^3) - nはポインタ変数の数
4.4 Steensgaardの分析
**統合ベース（unification-based）**分析です。同じ対象を指し得るポインタを一つの等価クラスに統合します。
アルゴリズム：Steensgaard分析
規則：
p = &x -> pの型がxを指すよう設定
p = q -> pとqのpoints-to集合を統合（union）
p = *q -> 適切な統合を実行
*p = q -> 適切な統合を実行
Union-Findデータ構造を使用
例：
// プログラム：
p = &a; // pts(p) = {a}
q = &b; // pts(q) = {b}
p = q; // pとqを統合 -> pts(p) = pts(q) = {a, b}
// Andersenと同じ結果
// しかし：
r = &c; // pts(r) = {c}
p = r; // Andersen：pts(p) = {a, b, c}, pts(r) = {c}
// Steensgaard：p,q,rすべて統合 -> pts = {a, b, c}
// Steensgaardの方が不正確（rは実際にはa,bを指さない）
複雑度：O(n \* alpha(n)) - ほぼ線形、alphaは逆アッカーマン関数
4.5 比較
| 特性 | Andersen | Steensgaard |
| ---------- | ------------ | -------------------------- |
| 精度 | 高い | 低い |
| 複雑度 | O(n^3) | ほぼO(n) |
| 方式 | 包含ベース | 統合ベース |
| 適した用途 | 精密な最適化 | 大規模プログラムの高速分析 |
5. 別名分析（Alias Analysis）
5.1 定義
2つの式が同じメモリ位置を参照するかを判別する分析です。
// 別名関係：
// *pとaは別名か？ -> pがaを指していれば別名
// 別名の3つの答え：
// Must-alias：常に同じ位置を指す
// May-alias：同じ位置を指す可能性がある
// No-alias：絶対に同じ位置を指さない
5.2 別名分析と最適化
void foo(int *p, int *q) {
*p = 10;
*q = 20;
int x = *p; // x = 10？それとも20？
}
別名分析の結果に応じて：
- pとqが**no-alias**なら：x = 10（定数伝播可能）
- pとqが**may-alias**なら：xの値は不明（保守的）
- pとqが**must-alias**なら：x = 20
5.3 型ベース別名分析（TBAA）
C/C++の厳密な別名規則（strict aliasing rule）を利用します。
// Cでは異なる型のポインタは別名でないと仮定可能
int *pi;
float *pf;
// piとpfはno-alias（型が異なる）
// 例外：char*はすべての型と別名可能
// 例外：unionのメンバー
5.4 restrictキーワード
C99の `restrict` キーワードはポインタが指すメモリへの唯一のアクセス手段であることをプログラマが保証します。
// restrictがなければa、b、cが別名の可能性
void add(int *a, int *b, int *c, int n) {
for (int i = 0; i < n; i++)
a[i] = b[i] + c[i];
}
// restrict使用：別名なしを保証
void add(int * restrict a, int * restrict b, int * restrict c, int n) {
for (int i = 0; i < n; i++)
a[i] = b[i] + c[i]; // ベクトル化可能！
}
6. フロー感度 vs フロー非感度分析
6.1 フロー非感度（Flow-Insensitive）
プログラムの実行順序を無視し、すべての文を同時に考慮します。
// フロー非感度分析：
p = &a; // 文1
p = &b; // 文2
x = *p; // 文3
// 結果：pts(p) = {a, b}（すべての地点で同じ）
// 文1の後でもpts(p) = {a, b}
利点：速くて簡単
欠点：不正確（文1直後はpはaのみを指す）
6.2 フロー感度（Flow-Sensitive）
プログラムの実行順序を考慮し、各プログラム地点で別個の情報を維持します。
// フロー感度分析：
p = &a; // この地点以後：pts(p) = {a}
p = &b; // この地点以後：pts(p) = {b}（以前の値を上書き）
x = *p; // この地点で：pts(p) = {b}
// -> xはbのみを指し得る（より正確！）
利点：正確
欠点：遅くメモリ消費が大きい
6.3 実用的な選択
// 一般的なコンパイラの選択：
// - プロシージャ内分析：フロー感度（精度重要、規模が小さい）
// - プロシージャ間分析：フロー非感度（拡張性重要、規模が大きい）
// - ポインタ分析：ほとんどフロー非感度（規模の問題）
7. プロシージャ間データフロー分析
7.1 MOD/REF分析
各関数がどの変数を修正（MOD）し参照（REF）するかを分析します。
// MOD(f)：関数fが修正し得る変数の集合
// REF(f)：関数fが参照し得る変数の集合
void foo() {
x = 1; // MOD(foo) = {x, ...}
y = x + z; // REF(foo) = {x, z, ...}
bar(); // barのMOD/REFも伝播
}
// MOD(foo) = {x} U MOD(bar)（barが修正するものも含む）
// REF(foo) = {x, z} U REF(bar)
7.2 関数インライニング（Function Inlining）
プロシージャ間分析の最も簡単な代替手段は関数を呼び出し地点にインライニングすることです。
// 元：
int square(int x) { return x * x; }
int result = square(5);
// インライニング後：
int result = 5 * 5; // -> 定数畳み込み可能 -> result = 25
インライニングの利点：
- 関数呼び出しオーバーヘッドの除去
- プロシージャ内最適化がより多くのコードを見られる
インライニングの欠点：
- コードサイズの増加（命令キャッシュに悪影響）
- 再帰関数はインライニング不可
- 過度なインライニングはむしろ性能低下
7.3 部分インライニングとクローニング
// 部分インライニング：ホットパスのみインライニング
void foo(int x) {
if (x > 0) { // 90%の確率
// 簡単なコード -> インライニング
} else {
// 複雑なコード -> 関数呼び出し維持
}
}
// 関数クローニング：呼び出し文脈に応じた特化バージョンを生成
void foo_const5() { // x=5の時に特化
// x=5で定数伝播されたコード
}
まとめ
| 概念 | 説明 |
| ------------------ | -------------------------------------- |
| プロシージャ間分析 | 関数境界を越えたプログラム分析 |
| 呼び出しグラフ | 関数間の呼び出し関係を表すグラフ |
| 文脈感度 | 呼び出し文脈に応じて分析結果を区別 |
| Andersen分析 | 包含ベースポインタ分析、O(n^3) |
| Steensgaard分析 | 統合ベースポインタ分析、ほぼO(n) |
| 別名分析 | 2つの式が同じメモリを参照するか判別 |
| フロー感度分析 | プログラム実行順序を考慮した分析 |
| フロー非感度分析 | 実行順序を無視した分析（速いが不正確） |
| MOD/REF分析 | 関数が修正/参照する変数の集合を分析 |
プロシージャ間分析とポインタ分析はプログラム全体最適化の基盤です。特にポインタが頻繁に使用されるC/C++プログラムでは、正確なポインタ分析なしには効果的な最適化が困難です。AndersenとSteensgaardの分析は精度と効率のトレードオフを代表する2つのアプローチです。次の記事では現代コンパイラの核心的な中間表現であるSSA形式を扱います。
현재 단락 (1/238)
これまで見てきた最適化技法のほとんどは一つの関数（プロシージャ）内で実行される**プロシージャ内分析**（intraprocedural analysis）でした。しかし実際のプログラムは多くの関数呼...