エイリアス解析

エイリアス解析（エイリアスかいせき、英: alias analysis）は、コンパイラ理論における手法の1つで、ある記憶域が複数の箇所からアクセスされるかどうかを判定する方法である。2つのポインタ（あるいは参照）が同じ記憶域を参照している場合、「エイリアスされている」(aliased) とみなされる。日本語では「（同じ実体に対する）別名となっている」とも訳せる。

エイリアス解析は通例制御フロー認識とコンテキスト認識に分類される。 エイリアスする可能性があるものと、確実にエイリアスしているものを特定することができる。 エイリアス解析という用語はポインタ解析と同義で用いられることもある。

エイリアス解析の行うこと

一般的には、エイリアス解析はあるメモリ参照が同じメモリ領域を示すかどうかを判定する。 これによって、コンパイラは、ある文によりプログラム中のどの変数が影響を受けるかを知ることができる。たとえば、以下のようなintへのポインタ経由でアクセスするC言語のコードを考える。

int* p;
int* q;
int i;

/* この時点でポインタ p と q は NULL でも不定値でもなく、何か有効なアドレスを指しているものとする */

*p = 1;
*q = 2;
i = *p + 3;

ここで、エイリアスに3つの場合がありうる。

1. 変数 p と q はエイリアスしない。
2. 変数 p と q は確実にエイリアスする。
3. コンパイル時には、変数 p と q がエイリアスするかどうかは決定論的に判断できない。

p と q がエイリアスしないのであれば、i = *p + 3; は　i = 4 に置き換えることができる。p と q が確実にエイリアスするのであれば、i = *p + 3; は i = 5 に置き換えることができる。いずれの場合も、エイリアスによる情報を元に最適化を施すことができる。一方、p と q がエイリアスするかどうか判断できない場合には、最適化を施すことができず、結果はコード全体を実行するまで得ることができない。2つのメモリ参照のエイリアスが不明の場合、「エイリアスする可能性がある」関係と呼ぶことができる。

エイリアス解析を行う

エイリアス解析では、プログラムのメモリ領域を「エイリアスクラス」(alias class) に分割する。 エイリアスクラスは互いに交わらない位置の集合であり、互いを指し示すことはない。議論のため、最適化をプログラムの低レベルな中間表現上で行うものとする。すなわち、プログラムはバイナリ操作、ジャンプ、レジスタ間のデータ転送、レジスタとメモリ間のデータ転送、分岐、サブルーチンの呼び出しと復帰の命令にコンパイルされるものとする。^[独自研究?]

型に基づくエイリアス解析

もしコンパイルされる言語が型安全であり、コンパイラの型チェックが正しく、さらにローカル変数を参照するポインタを生成する能力を持たない言語（ML、Haskell、Javaなど）だとすると、有益な最適化を行うことが可能である。2つのメモリ位置が確実に異なるエイリアスクラス内にあることが既知である状況は多数ある。

1. 異なる型を持つ2つの変数は同じエイリアスクラスにない。異なる型を持つ2つの変数は、同時に同じメモリ位置を共有することができない、ということは、強い型付けがされていて、メモリへの参照がない（メモリ位置への参照を直接変更することができない）言語の特性だからである。
2. 現在のスタックフレームに局所的な変数の割り当ては、別のスタックフレームからの以前の割り当てと同じエイリアスクラスに存在しない。これは、新しいメモリの割り当ては、他のすべてのメモリ割り当てと領域が交わらないためである。
3. レコード型（構造体）の各フィールドは、自身のエイリアスクラスを持つ。一般的には、型付けの原則として、同じレコード型を持つ変数のみがエイリアスとなりうるからである。あるレコード型のすべての変数はメモリ内で同一の形式であるから、そのフィールドは自分自身に対してのみエイリアスとなりうる。
4. 同様に、ある型の配列は自身のエイリアスクラスを持つ。

コードに対してエイリアス解析を行う際、メモリへのロードとストアごとにクラスでラベル付けされる必要がある。すると、エイリアスクラス ${\displaystyle i,j}$ を持つ、与えられたメモリ位置 ${\displaystyle A_{i}}$ と ${\displaystyle B_{j}}$ に対して、${\displaystyle i=j}$ であれば ${\displaystyle A_{i}}$ は ${\displaystyle B_{j}}$ のエイリアスとなる可能性があり、${\displaystyle i\neq j}$ であればエイリアスとならない、という有用な特性を得ることができる。

フローに基づくエイリアス解析

フローに基づく解析は、型に基づいた解析とは異なり、参照や型のキャストがある言語でも適用することができる。フローに基づく解析は、型に基づいた解析を代替したり、補ったりする形で用いることができる。フローに基づく解析では、新たなエイリアスクラスがメモリの割り当てごとに作成されたり、アドレスが使用されているグローバル変数およびグローバル変数ごとに作成されたりする。参照は時間が経過すると別の領域を指す可能性もあり、複数のエイリアスクラスにまたがる可能性がある。これは、各メモリ位置が単一のエイリアスクラスではなく複数のエイリアスクラスの集合を持つことを意味する。

参考文献

Appel, Andrew W. (1998). Modern Compiler Implementation in ML. Cambridge, UK: Cambridge University Press. ISBN 0 521 60764 7 

関連項目

• エスケープ解析
• ポインタ解析
• シェープ解析