エイリアス解析のソースを表示

{{複数の問題
|出典の明記=2023-09
|独自研究=2023-09
|脚注の不足=2023-09
}}
'''エイリアス解析'''（エイリアスかいせき、{{lang-en-short|alias analysis}}）は、[[コンパイラ]]理論における手法の1つで、ある記憶域が複数の箇所からアクセスされるかどうかを判定する方法である。2つの[[ポインタ (プログラミング)|ポインタ]]（あるいは参照）が同じ記憶域を参照している場合、「[[:en:Aliasing (computing)|エイリアス]]されている」({{lang|en|aliased}}) とみなされる。日本語では「（同じ実体に対する）別名となっている」とも訳せる。

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

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

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

*p = 1;
*q = 2;
i = *p + 3;
</syntaxhighlight>
<!--
翻訳元の英語版では、対象言語を名言せず、またメンバー変数fooを持つ謎の構造体を仮定して、p.fooやq.fooで唐突に使用するコード例が書かれてあったが、そのような不明瞭で中途半端に抽象化したまわりくどいことをせずとも、Cの組み込み型とポインタだけでエイリアスの説明はできる。
ちなみにCには参照はなく、エイリアスはポインタ経由もしくは共用体でのみ生成されうる。ポインタでない構造体変数pとqは異なるオブジェクトであり、互いにエイリアスではない。
言語に関する最低限の知識もなく、内容をロクに理解せずに表面的に翻訳してしまうと、翻訳元のひどさに気づかない。
-->
ここで、エイリアスに3つの場合がありうる。

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

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

==エイリアス解析を行う==
{{独自研究範囲|date=2023-09|エイリアス解析では、プログラムのメモリ領域を「エイリアスクラス」(alias class) に分割する。
エイリアスクラスは互いに交わらない位置の集合であり、互いを指し示すことはない。議論のため、最適化をプログラムの低レベルな[[中間表現]]上で行うものとする。すなわち、プログラムはバイナリ操作、ジャンプ、レジスタ間のデータ転送、レジスタとメモリ間のデータ転送、分岐、[[サブルーチン]]の呼び出しと復帰の命令にコンパイルされるものとする。}}<!-- 翻訳元の英語版 (oldid=282236521) からのコピーらしいが、C/C++の「記憶域クラス」(storage class) からのアナロジーとして勝手にでっち上げた造語なのでは？　出典もまったくないし、少なくとも最新の英語版 (oldid=1133707419) では跡形もなくゴッソリ削除されている。出典に基づかない独自研究は許されない。[[Wikipedia:独自研究は載せない]], [[Wikipedia:出典を明記する]] -->

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

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

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

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

==参考文献==
{{参照方法|section=1|date=2023-03}}
{{cite book |author=Appel, Andrew W. |title=Modern Compiler Implementation in ML |publisher=Cambridge University Press |location=Cambridge, UK |year=1998 |pages= |isbn=0 521 60764 7 |oclc= |doi=}}

==関連項目==
* [[エスケープ解析]]
* [[ポインタ解析]]
* [[シェープ解析]]

[[Category:コンパイラ|えいりあすかいせき]]