エイリアス解析

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

エイリアス解析: Alias analysis)は、コンパイラ理論における手法の一つで、ある記憶域が複数の箇所からアクセスされるかどうかを判定する方法である。二つのポインタが同じ記憶域を参照している場合、「エイリアスしている」とみなされる。

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

エイリアス解析の行うこと[編集]

一般的には、エイリアス解析はあるメモリ参照が同じメモリ領域を示すかどうかを判定する。 これによって、コンパイラは、ある文によりプログラム中のどの変数が影響を受けるかを知ることができる。たとえば、下のような構造体のメンバーにアクセスするコードを考える。 ...; p.foo = 1; q.foo = 2; i = p.foo + 3; ... ここで、エイリアスに3つの場合がありうる。

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

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

エイリアス解析を行う[編集]

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

型に基づくエイリアス解析[編集]

プログラミング言語が型安全にコンパイルされ、コンパイラの型チェックが正しく、さらにローカル変数を参照することができない(MLや Haskell, Java など)とすると、有益な最適化を行うことが可能である。二つのメモリ位置が異なるエイリアス領域内にあることが既知である状況は多数ある。

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

コードに対してエイリアス解析を行う際、メモリへの各ロードとストアは領域ごとにラベル付けされる必要がある。すると、与えられたメモリ領域に対して重要な特性 A_i B_j すなわちエイリアス領域 i,j を得る。i=j ならば、A_iB_j にエイリアスする可能性があり、i \neq j であればエイリアスしない。

フローに基づくエイリアス解析[編集]

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

参考文献[編集]

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

関連項目[編集]