ポインタ解析とエイリアス解析

エイリアス解析が答える問い

コンパイラが *p = 1; x = *q; *p = 2; という列を見たとき、x = *q を上の代入の前へ動かせるか、あるいは二度目の *p = 2 を一度目に統合できるかは、p と q が同じメモリを指すかに懸かっています。指しうるなら（エイリアス関係にあるなら）*q の読みは *p の書きに依存し、並べ替えも統合も許されません。この「どのポインタが同じ記憶域を指しうるか」を静的に推定するのが**エイリアス解析（alias analysis）であり、その土台となるのが各ポインタの指し先集合を求めるポインタ解析（pointer analysis）**です。

ポインタ解析は、各ポインタ変数 p に対し「p が指しうる抽象オブジェクトの集合」——points-to集合——を計算します。抽象オブジェクトとは、各 malloc 呼び出し地点や各局所変数のアドレスといった、無限にありうる実行時アドレスを有限個に丸めた代表です。二つのポインタの points-to集合が交われば「エイリアスしうる（may-alias）」、必ず同一の単一オブジェクトだけを指すなら「必ずエイリアスする（must-alias）」と判定します。最適化に直接効くのは多くの場合 may-alias が空かどうか、すなわち「絶対に重ならない」と言い切れるかです。

points-to集合を制約として解く

ポインタ解析の主流は、プログラムから制約を抽出して解く定式化です。ポインタが絡む文を、左辺の指し先集合と右辺の指し先集合の関係に翻訳します。代表的な四種を pts(x) を「x の points-to集合」として書くと次のようになります。

ここで p = q の制約 pts(q) ⊆ pts(p) は包含であって等値ではない点が肝心です。コピーは右から左へ一方向にしか指し先を流さないので、pts(p) が pts(q) より大きくても矛盾しません。ロードとストアは「q が何を指すか」が確定してからでないと展開できないため、解は一度では決まらず、集合が増えるたびに制約を再評価する固定点反復で求めます。集合の和集合を取りながら変化がなくなるまで回す構造は、データフロー解析の単調反復と同じ骨格です。

Andersen 流と Steensgaard 流

包含制約 ⊆ をそのまま解くのが **Andersen 流（包含ベース）**です。制約をノードが points-to集合、辺が包含を表すグラフとみなし、ロード／ストアで動的に辺を追加しながら和集合を伝播させます。精密ですが、最悪計算量はポインタ数 n に対して O(n³) で、大規模プログラムでは重くなります。

これに対し Steensgaard 流（等価ベース）は、包含 ⊆ を等値 = に粗く近似します。p = q を見たら pts(p) と pts(q) を即座に同一集合へ併合（unify）してしまうのです。指し先が連鎖的に併合されるため、各変数はちょうど一つの「指し先クラス」を持ち、解析はUnion-Findでほぼ線形時間 O(n·α(n)) に収まります。代償は精度です。一方向で十分な箇所まで双方向に等値化するため、本来は片方しか指さないポインタ同士まで「同じものを指す」とまとめてしまいます。

両者は精度と速度の両極であり、近年は中間として、初手で安価に併合してから一部だけ包含で精緻化するハイブリッドや、後述のオフライン最適化で Andersen 流を高速化する手法が用いられます。

フロー感度とコンテキスト感度

points-to集合をどれだけ細かく文脈分けするかで、精度と計算量がさらに変わります。二つの「感度（sensitivity）」軸が中心です。

**フロー感度（flow sensitivity）**は、文の実行順序を区別するかどうかです。フロー鈍感（flow-insensitive）な解析は、関数内のすべての文をいわば順不同に扱い、各ポインタに単一の points-to集合を割り当てます。p = &a; の後に p = &b; が来ても、pts(p) は両方を含む {a, b} のままです。Andersen / Steensgaard の素朴な定式化はフロー鈍感で、だからこそ高速です。対してフロー敏感（flow-sensitive）な解析はプログラム点ごとに points-to集合を持ち、強い更新（strong update）——*p = q で p が唯一のオブジェクトを指すと分かれば、そのオブジェクトの古い指し先を上書き消去する——が可能になり、SSA形式とも噛み合います。精度は上がりますが、点ごとに状態を持つぶん重くなります。

コンテキスト感度（context sensitivity）は、関数呼び出しの呼び出し元を区別するかどうかです。コンテキスト鈍感な解析は、id(x){return x;} のような関数を全呼び出しでまとめて扱うため、ある呼び出しの実引数が別の呼び出しの仮引数へ漏れる偽の流れを生みます。コンテキスト敏感な解析は呼び出し文脈ごとに解析を分け、これを防ぎます。文脈の表し方には、呼び出し地点の列で区別する call-site 感度（k-CFA） と、レシーバオブジェクトで区別する object 感度 があり、後者はオブジェクト指向コードで有効とされます。

最適化への含意

エイリアス情報の最終的な価値は、それが許す（あるいは禁じる）変換にあります。コンパイラがメモリ参照を扱うほぼすべての最適化が、その裏でエイリアス解析を参照しています。

• 冗長ロードの除去とレジスタ昇格：x = *p; ...; y = *p; の間に *p を変えうるストアが無いと示せれば、二度目のロードを省き値を再利用できます。ストアと p が may-alias なら省けません。値をレジスタに保持し続けられるかも、同じ判定に依存します。
• 命令の並べ替え：*p = a; b = *q; を入れ替えてよいのは p と q が no-alias のときだけです。エイリアスしうるなら、書きと読みの間にメモリ依存が立ち、スケジューラは順序を保たねばなりません。
• デッドストア除去：*p = 1; *p = 2; で、間に p 経由でない読みが無くかつ両者が must-alias なら、最初のストアは死んでいます。

C と C++ で最適化が効きにくいと言われる一因は、ポインタ演算と型変換により may-alias 集合がすぐ膨らみ、解析が保守化することにあります。これを補う言語側の仕組みが、「このポインタはこの区間で他とエイリアスしない」とプログラマが宣言する restrict（C99）や、型が違えばエイリアスしないと仮定する**厳密エイリアス規則（strict aliasing）**です。対照的に Rust の所有権と借用は、可変参照の排他性を型システムで保証することで「&mut T は他とエイリアスしない」をコンパイラに無償で与え、エイリアス解析に頼らずアグレッシブな最適化を可能にします。

まとめ

ポインタ解析は各ポインタの points-to集合を求め、それを基にエイリアス解析が「同じメモリを指しうるか」を健全に判定します。包含制約を解く Andersen 流は精密だが立方時間、等値併合する Steensgaard 流は粗いがほぼ線形時間で、両極の間にトレードオフが広がります。フロー感度・コンテキスト感度を上げれば精度は増すものの状態空間が爆発するため、実務は感度を有限に切り詰めて妥協点を探ります。そして解析が保守化してエイリアスの可能性が残るほど、冗長ロード除去・命令並べ替え・デッドストア除去といった最適化は抑制されます。restrict や Rust の所有権は、この may-alias の膨張を言語側で抑え込み、最適化の余地を取り戻すための装置です。