エイリアス解析

エイリアス解析では、プログラムのメモリ領域を「エイリアスクラス」(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}$ であればエイリアスとならない、という有用な特性を得ることができる。

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

出典は列挙するだけでなく、脚注などを用いてどの記述の情報源であるかを明記してください。 記事の信頼性向上にご協力をお願いいたします。（2023年3月）

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

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