[コンパイラ] 18. プロシージャ間分析とポインタ分析

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()はarrが指す配列のみ修正
// - init()はグローバル変数を修正しない
// - init()後arr[0..n-1]はすべて0

// プログラム：
// main() -> foo() -> bar()
//        -> baz() -> bar()
//                 -> qux()

// 呼び出しグラフ：
//   main -> foo -> bar
//        -> baz -> bar
//               -> qux

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か分からない
}

// Javaの例：
// Animal.speak()が呼び出されると
// Dog.speak()、Cat.speak()などすべてのサブクラスのメソッドが可能な対象

// CHA：Animalのすべてのサブクラスのspeak()を候補に含む
// RTA（Rapid Type Analysis）：実際に生成された型のみ考慮
// VTA（Variable Type Analysis）：変数の実際の型を追跡

// 関数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}（不正確！）

// 文脈感度分析：
// 呼び出し1の文脈：identity(1) -> 戻り値 = 1 -> a = 1
// 呼び出し2の文脈：identity(2) -> 戻り値 = 2 -> b = 2
// 正確な結果！

// main -> foo -> identity（文脈：[main, foo]）
// main -> bar -> identity（文脈：[main, bar]）

// k制限呼び出し文字列：最近k個の呼び出しのみ考慮
// k=1：[foo], [bar]
// k=2：[main,foo], [main,bar]

// identity関数の要約：
// 入力x -> 出力x（恒等関数）
// 各呼び出し地点で要約を適用：
// identity(1) -> 1
// identity(2) -> 2

// ポインタ分析の質問：
// ポインタpが指し得る対象は？

int a, b;
int *p;
if (cond)
    p = &a;
else
    p = &b;

// この地点でpのpoints-to集合：pts(p) = {a, b}

// アドレス取得：p = &x  -> pがxを指す
// コピー：     p = q    -> pがqが指すものを指す
// ロード：     p = *q   -> pがqが指すものが指すものを指す
// ストア：     *p = q   -> pが指すものがqが指すものを指す

アルゴリズム：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}

アルゴリズム：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を指さない）

// 別名関係：
// *pとaは別名か？ -> pがaを指していれば別名

// 別名の3つの答え：
// Must-alias：常に同じ位置を指す
// May-alias：同じ位置を指す可能性がある
// No-alias：絶対に同じ位置を指さない

void foo(int *p, int *q) {
    *p = 10;
    *q = 20;
    int x = *p;  // x = 10？それとも20？
}

// Cでは異なる型のポインタは別名でないと仮定可能
int *pi;
float *pf;
// piとpfはno-alias（型が異なる）

// 例外：char*はすべての型と別名可能
// 例外：unionのメンバー

// 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];  // ベクトル化可能！
}

// フロー非感度分析：
p = &a;     // 文1
p = &b;     // 文2
x = *p;     // 文3

// 結果：pts(p) = {a, b}（すべての地点で同じ）
// 文1の後でもpts(p) = {a, b}

// フロー感度分析：
p = &a;     // この地点以後：pts(p) = {a}
p = &b;     // この地点以後：pts(p) = {b}（以前の値を上書き）
x = *p;     // この地点で：pts(p) = {b}
            // -> xはbのみを指し得る（より正確！）

// 一般的なコンパイラの選択：
// - プロシージャ内分析：フロー感度（精度重要、規模が小さい）
// - プロシージャ間分析：フロー非感度（拡張性重要、規模が大きい）
// - ポインタ分析：ほとんどフロー非感度（規模の問題）

// 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)

// 元：
int square(int x) { return x * x; }
int result = square(5);

// インライニング後：
int result = 5 * 5;  // -> 定数畳み込み可能 -> result = 25

// 部分インライニング：ホットパスのみインライニング
void foo(int x) {
    if (x > 0) {     // 90%の確率
        // 簡単なコード  -> インライニング
    } else {
        // 複雑なコード  -> 関数呼び出し維持
    }
}

// 関数クローニング：呼び出し文脈に応じた特化バージョンを生成
void foo_const5() {   // x=5の時に特化
    // x=5で定数伝播されたコード
}