オブジェクト指向プログラムにおけるエイリアス解析について
大畑文明 y井上克郎 yz

y 大阪大学大学院基礎工学研究科〒 560-8531 大阪府豊中市待兼山町 1-3
z 奈良先端科学技術大学院大学情報科学研究科〒 630-0101 奈良県生駒市高山町 8916-5

エイリアスとは，引数の参照渡し・参照変数・ポインタを介した間接参照などで生じ る，識別子が異なるが同じ メモリ領域を指す可能性のある変数および式の集合である．しかし，既存のエイリアス解析手法は，解析結果の再利用を考慮しておらず，オブジェクト指向プログラムの持つ再利用性がエイリアス解析に生かされていない．本研究では，エイリアス解析結果の再利用・モジュール化を考慮した，オブジェクト指向プ
ログラムに対するエイリアス解析手法を提案する．

Alias analysis for object-oriented programs

Fumiaki Ohatay and Katsuro Inoueyz
y Graduate School of Engineering Science, Osaka University

1-3 Machikaneyama, Toyonaka,
Osaka 560-8531, Japanz Nara Institute of Science and Technology Department of Informatio Science8916-5 Takayama-cho, Ikoma-City,
Nara 630-0101, Japan

In this paper, we propose an alias analysis method for object-oriented programs, which takes reusability
and modularity of its results into account.

Alias is a set of variables and expressions which possiblyrefer to the same location during execution.

Since existing alias analysis methods do not reuse own

results, we can not make use of reusability of object-oriented programs on alias analyses.

-1-

1

まえがき

プログラムのデバッグ支援に有効な方法としてプログラムスライス (Prgram Slice) [1] がある．プ
ログラムスライスとは，プログラム P 中のある文
s に対して，s で参照しているある変数 v の内容に影響を与えうる文の集合 Q のことである．現在では , デバッグ支援だけでなくテスト，保守，プログ
ラム合成，プログラム理解などにも利用されている. このプログラムスライスの計算は，Phase 1: データ依存解析
Phase 2: 制御依存解析
Phase 3: プログラム依存グラフ (PDG) の構築
Phase 4: PDG を利用し スライスを計算という過程 [12] をたど るが，Phase 1: データ依
存解析においては，各文でどの変数が定義・使用されているかが判明していなければならない．そのため，ポインタ (参照) が存在するプログラミン
グ言語のデータ依存解析では，エイリアスの解析が前提となっている．
また，現在のプログラム開発環境において，Cなどの手続き型言語だけでなく，Java[8]・C++[9]等いわゆるオブジェクト指向言語の利用が高まっている．その理由としては，オブジェクト指向モデルが持つ，拡張容易性・抽象化・カプセル化・モ
ジュール性・再利用性・階層などが挙げられる．オ
ブジェクト指向言語には，従来の手続き型言語にはないクラス・継承・動的束縛・ポリモルフィズ
ムなど 新しい概念が導入されており，それらに対応したエイリアス解析手法がいくつか提案されている [7]．
しかし ，既存のエイリアス解析手法は，解析ア
ルゴ リズムをオブジェクト指向言語に対応させたに過ぎず，解析結果そのものの再利用性・モジュー
ル性は満たされていない．プログラムの大規模化・プログラムの再利用への感心が高まる現在，これらの特性を満たすエイリアス解析手法が望まれる．
本研究では，再利用性・モジュール性を考慮したエイリアスフローグラフによるオブジェクト指
向プログラムに対するエイリアス解析手法の提案
を行う．
以降，2 ではエイリアスについて簡単に紹介する．3 ではオブジェクト指向言語およびそれに対するエイリアス解析について紹介する．4 ではエ
イリアスフローグラフによるエイリアス解析手法の提案を行い，5 でまとめと今後の課題について
述べる．

2

エイリアス

FS エイリアス解析 (Flow-Sensitive Alias Analysis) (以降，FS 解析と略す) の 2 つに分けることができる．以下，FS 解析・FI 解析を簡単に説明する．
FS エイリアス解析

FS エイリアス解析 [2, 3] とは，プログラム文の実行順を考慮したエイリアス解析手法をいう．一般に到達エイリアス集合 (Reaching Alias Set) を利用して解析を行う．図 1 に変数 c(太枠部) の FS
エイリアス (網掛部) とその計算に用いた到達エイ
リアス集合を示す．到達エイリアス集合は，エイリアス関係の成り立つ組の集合であり，文を解析するたびに更新される．各エイリアス組の要素は(文, オブジェクトへの参照) で構成されており，例
えば文 2: a = new Integer(1) により，エイリア
ス組 f(2, a), (2, new Integer(1))g が生成される．
また，文 6: c = a により，エイリアス組 f(4, c),(3, b), (3, new Integer(2))g が f(6, c), (2, a), (2,new Integer(1))g 変更されているのが分かる．文
7 の変数 c に関するエイリアスを求める場合，文 7における到達定義集合から識別子 c を含むエイリ
アス組を探す．変数 c は f(6, c), (2, a), (2, newInteger(1))g に含まれており，網掛部が求めるエイ
リアスとなる．

1: DInteger
a,DDDb,DDc;DDDDDDDD
2: DaDDDD = DDDDnew
DDDDDInteger
DDDDDDDD (1);3: b = new Integer(2);4: c = b;
5: DSystem.out.println(c);6: DcDDDD = DDaDDDD;
7: System.out.println(DDDDcDD);(a) プログラム

文

1
2
3
4
5
6
7



到達エイリアス集合

(2, a), (2, new Integer(1))(2, a), (2, new Integer(1)) ,(3, b), (3, new Integer(2))(2, a), (2, new Integer(1)) ,(4, c), (3, b), (3, new Integer(2))
〃(6, c), (2, a), (2, new Integer(1)) ,(3, b), (3, new Integer(2))

f

g

f

g

f

g

f

g

f

g

f

g

f

g

〃

(b) 到達エイリアス集合

図 1: FS エイリアス解析
FI エイリアス解析

FI エイリアス解析 [4, 5] とは，プログラム文の実行順を考慮しないエイリアス解析手法をいう．一
般にエイリアス (または，Point-to) グラフを利用して解析を行う．図 2 に変数 c(太枠部) の FI エイ
リアス (網掛部) およびエイリアスグラフを示す．
エイリアスグラフの節点はメモリ領域を指し うる変数および 式 (動的・静的いずれも含む) である．
辺はエイリアス関係を表現している．また，複数辺による経路は節点間の間接のエイリアス関係を表わしている．例えば，文 4: c = b・文 6: c = a により，c〜b 間・c〜a 間に辺が引かれるため，a〜b 間

エイリアス (Alias) とは，引数の参照渡し・参照
変数・ポインタを介した間接参照などで生じる，識別子が異なるが同じ メモリ領域 (オブジェクト ) を指す可能性のある変数および 式の集合 (以降，単にエイリアス集合 (Alias Set) と略す) である．本
研究では，同一識別子で同じ メモリ領域を指す変数・式もエイリアス集合に含めるとする．
エイリアス集合を導き出すエイリアス解析 (Alias
Analysis) は，大きく FI エイリアス解析 (FlowInsensitive Alias Analysis) (以降，FI 解析と略す)・-2-class Employee f
String name; int salary; Employee boss;
Employee(String n, int s) f
name = n; salary = s; boss = null;に経路が生じるため，fa, b, cg はエイリアス組と解釈される．c からの到達可能な節点が，文 7 の変数 c に関するエイリアスである．エイリアスグラ
フより，fa, b, new Integer(1), new Integer(2))gが求めるエイリアスとなる．
D
DDDD, DDb
DDDD, DDDc
1: Integer
Da
DDD;
DDDDDInteger
DDDDDDDD
2: DDDaDDDDDD = DDDDDDnew
DDDDDDDDDDDDD(1);DDDDDInteger
DDDDDDDD
3: DDbDDDD = DDDDnew
DDDDDDDDDDDDD(2);4: DDcD = DbDDD;
DDDc
5: System.out.println(
DDD );
6: DDDDcDD = DDaDDDD;
7: System.out.println(DDcDDDD);(a) プログラム

gvoid add salary(int n) fsalary += n; gvoid set boss(Employee e) f boss = e; gvoid print() fg

System.out.println(name + " Salary:" + salary);ga

new Integer(1)bnew Integer(2)class Manager extends Employee fManager(String n, int s)DfDsuper(n, s);gvoid manage(Employee DeDDD) fce .set boss(this); DDeDDDD.add salary(50);

DDD
DDD

(b) エイリアスグラ

g

フ

g

図 2: FI エイリアス解析

class OÆce fpublic static void main(String args[]) f
DDDDDDDDDDDDDDDDDDDDDDDDD700)
DDDD
Employee DDADDDD = Dnew
DDDDDDEmployee("Mr.A",
DDDDDDDDDDDDDDDDDDDDDDDD;Manager B = new Manager("Mr.B", 850);

FS 解析と FI 解析の比較

正確性: FS 解析はプログラム文の実行順を考慮しているため，FI 解析よりも正確性は高い

gB.manage(DDADDDD); DDADDDD.print(); B.print();g% java OÆceMr.A Salary: 800
Mr.B Salary: 850

正確性 (accuracy) とは，「 少なくとも
実在するエイリアス集合は含まれているとして，どれだけ実在しないエ
イリアス集合を取り除くことができるかの程度」を表す．

図 3: Java プログラム

コスト : FS 解析は FI 解析よりも時間計算量・空間計算量を必要とする
文献 [6] において，両者の詳細な比較がなされて
いる．

3.2

オブジェクト 指向言語におけるエイリアス
解析
既存のオブジェクト指向プログラムにおけるエイリアス解析は，表 1 に挙げた概念変更を含め，既に提案されている手続き型言語のエイリアス解析
手法の拡張の形態となっている．以降，既存のエ
表 1: オブジェクト指向言語への拡張

Java とエイリアス

オブジェクト指向言語の 1 つであるJava は C++とは異なり，ポインタはなく参照変数のみ存在す
る．そのため解析結果が直接プログラム理解に結びつきやすく，プログラムスライスやコンパイラ
最適化のためだけでなく，デバッグや保守においてもエイリアス解析の利用が期待できる．
図 3 に Java プログラムとその実行結果を示す．
ユーザは文 A.print() の出力異常を認識し，参照変
数 A に関するエイリアスを抽出を試みる．網掛部
が文 A.print() の A に関するエイリアス，下線部がそのエイリアスが呼び出したメソッド である．この場合，文 e.add salary(50) を add salary(50) に変更することで期待動作を行うようになる．

3

オブジェクト 指向プログラムにおけるエイリアス解析3.1

オブジェクト 指向言語

手続き型言語構造体
構造体の要素関数 手続きポインタ変数()

オブジェクト指向言語
クラス
属性
メソッド
オブジェクトへの参照

イリアス解析手法に関して，いくつかの視点から考察を行う．
■ FS 解析の問題 手続き (関数) が存在するプログラムの場合，到達エイリアス集合を用いた FS 解
析 [7] では，すべての実行 (手続き呼び出し ) 経路をたど りながら到達エイリアス集合を計算する．その際には，呼び出し 側でのエイリアス集合を，手続き側で解釈可能なように識別子の付け換え (参照渡しの場合，エイリアス組に属する実引数を仮引数に置き換えるのもその 1 つである) をその都度行わねばならない．また，再帰呼び出しが存在する場合，エイリアス集合が収束するまで再帰経路を解析し続ける必要がある．これは，解析結果がエイリアス組の形式で保持されていることに起因している．つまり，ある時点でエイリアス組に変化が起ったとき，その変化の影響を受ける到達
エイリアス集合を持つ文すべてにその変化を伝播

オブジェクト 指向 (Object-Oriented) プログラミ
ングでは，プログラムはオブジェクトの協調し合う集りとして構成され，そのオブジェクトはそれぞれ何らかのクラスのインスタンスであり，そのクラスは継承関係でまとめられたクラス階層の要素となる [10]．

-3-させ，到達エイリアス集合を更新しなければならないためである．
■解析結果の再利用 ある文 s の到達エイリアス
集合は，その文が含まれるプログラム全体の解析により導出されたものであるため，他の文 t が変更されたとき，文 s も再解析しなければならない
場合が多く存在する．これは，エイリアス解析結果のモジュール性・独立性が満されていないことに起因する．解析結果のモジュール化による再利
用は，頻繁に変更されるプログラムや再利用の可能性の低い単一プログラムでは直接の効果が現れにくく，更新頻度の少なく再利用性の高いライブ
ラリに対する解析にのみ有効であると考えていた．
しかし ，このライブラリが持つ特性はオブジェク
ト指向プログラムにも共通している．オブジェク
ト指向プログラムでは，継承機能など ，言語自身が再利用を考慮したものとなっているため，記述されたクラスの利用範囲が特定のプログラムにとど まらない．また，クラス階層の上位に存在するクラスは属性・メソッドが汎化されているため一度定義されると変更されることは少ない．そのため，クラスやメソッド 単位で解析結果をモジュール化することにより，再計算コストの削減が期待できる．
■同一クラスの異なるインスタンス属性の取り扱
い オブジェクト指向プログラムでは，異なるオ
ブジェクト間での状態 (属性) と振舞い ( メソッド )は独立であるため，図 4 の例では fx.s, A::sg，fy.s,
A::sg はエイリアス組と言えるが，同一クラスのイン スタン スがその内部情報を共有する (具体的には，fx.s, y.s, A::sg がエイリアス組となる) ことは
正確性の低下につながる．このため，インスタン...
x = new A;
yDD=DDDnew A;
DDx.s
DDD = .. .;DDDDy.s
DDDDDD = .. .;...

算時に逐次導出する手法が考えられる．
3.3 提案する手法
そこで本研究では，先に述べた
 再解析コストの軽減 エイリアス解析結果のモジュール化 および それに伴う再利用性向上
 内部エイリアス関係の表現を目的とする， FS 解析に基づくエイリアスフローグラフ (AFG)
 AFG を用いたエイリアス計算の提案を行う．クラス・メソッド 単位で到達エイ
リアス集合によるエイリアス解析を行い，クラス
AFG・メソッド AFG をそれぞれ構築する．各 AFGは独立したモジュールとして存在し ，対応するク
ラス・メソッドが更新されない限り不変であり，二次媒体への記憶およびその再利用が 可能である．
AFG はクラス・メソッド 内部のエイリアスに関する情報のみを保持しており，インスタンス独自のエイリアス関係やインスタンス間をまたぐ エイリ
アス関係はユーザからの要求があった時点で逐次
解析する．

4

エイリアスフローグラフ (AFG)

エイリアスフローグラフ (Alias Flow Graph，
AFG) は，FS エイリアス関係を無向グラフで表現したものであり，FS エイリアス計算をグラフの到達問題に置き換える．AFG によるエイリアス解
析手法は，大きく以下の 5 段階で構成させる．
Phase 1: オブジェクトへの参照の抽出(AFG 節点の生成)

Phase 2: 到達エイリアス集合を利用し，直接のエイリアス関係の抽出(AFG 辺の生成)
Phase 3: AFG 構築
Phase 4: メソッド 呼び出しグラフ (MFG) 構築
Phase 5: AFG によるエイリアス計算

class A f

Integer s;.. .(. ..)DDD. ..= DDsD;. ..

本節では，AFG 構築・MFG 構築・AFG によるエイリアス計算に分け，それぞれ説明する．今回
提案するアルゴ リズムは Java の参照変数によるエイリアスを対象としているが，ポインタ変数によるエイリアスにも適応可能であり，本節の最後で簡単に述べる．
D
D
DD
DD
DD
DD
DInteger
DD
DD
DD
DD
DD
DD
DD
D(0);
1: Integer a = DDDDnewf

図 4: オブジェクト指向プログラム
スごとにクラス内部のエイリアス情報を持たせる手法が考えられるが，単純にインスタンスの数だ
けエイリアス情報を生成すると，多大な空間コストを要する．そこで，存在するエイリアス関係を 外部からの影響を受けないもの . . . 内部エイリ
アス関係 (Inner Alias Relation)

2: Integerb, c;
3: DDbDDDD = a;4: c = b;

図 5: サンプルプログラム

内部エイリアス関係は，例として，手続き型言語の手続き・関数，オブジェ
クト指向言語のメソッド・クラス内で成立する．

Phase 1: AFG 節点の生成
AFG 標準節点
AFG 節点 (AFG Node) は，文とオブジェクトへの参照の組である．ここでいうオブジェクト への参照は，(1) インスタンス生成式(2) 参照変数 外部からの影響を受けるもの . . . 外部エイリア
ス関係 (Outer Alias Relation)に分け，内部エイリアス関係のみ前もって解析し情報を蓄え，外部エイリアス関係はエイリアス計-4-

(3) ポインタ変数による間接参照式のいずれかである．ただし (3) は，C や C++など
ポインタを有する言語で用いる．また，これらの節点を特に標準節点 (Normal Node) と呼ぶ．
図 5 にサンプルプ(1,a)DDDDDDDDDDDDDD
ログ ラムを，図 6 にDD(1,DDDDDDDDnew
Integer)
DDDDDDDDDDDDDD
図 5 の AFG 節点を示
(3,
a)DD
D(3,
DDDb)
す．文 3: b = a におDDDDDD(4, b)
いて，b は参照変数で(4, c)
ありオブジェクトへの参照に該当する．よっ
図 6: AFG 節点て，AFG 節点 (3, b)が 生成され る．同様に，文 1: Integer a = new Integer(0) においても，
new Integer はインスタンス生成式であり，AFG
節点 (1, new Integer) が生成される．
AFG 特殊節点

手続きの存在しない単一プログラムにおいては，

AFG 標準節点のみ用いることで AFG を構築することができる．しかし ，オブジェクト指向プログ
ラムではメソッド ・属性が存在するため，
 引数渡しによる，メソッド〜メソッド 呼び出し元
 メソッド の戻り値による，メソッド 〜メソッド
呼び出し元 属性による，同一クラス ( イン スタン ス) の メ
ソッド 〜メソッド
でのエイリアスの受け渡しを考慮しなければならな
い．そのため．表 2 に挙げる AFG 特殊節点 (AFG
Special Node) を新たに追加する．
Phase 2: AFG 辺の生成
AFG 辺 (AFG Edge) は，2 つの AFG 節点間の，同一変数参照，代入文やパラメータの対応による
直接のエ イリアス関係を表す．複数の AFG 辺で構成された経路は，2 節点間の，推移的に成り立
つ間接のエイリアス関係を表す．AFG 辺は到達エ
イリアス集合を利用して引かれる．
到達エイリアス集合
本手法で用いる到達エイリアス集合は，2 節のFS エイリアス解析で用いた到達エイリアス集合とは以下の点で異なる．
 要素は，エイリアス組ではなく AFG 節点である．本手法では，エイリアス関係を AFG 辺 お
よび AFG 経路で表現するため，到達エイリア
ス集合内でエイリアス組を保持する必要はなく，後述する AFG 節点でよい 到達エイリアス集合は各文で保持されるのではなく，AFG 辺を引くためにのみ使われる
到達エイリアス集合の計算は 2 節の FS エイリ
アスの抽出アルゴ リズムを基本とし ，分岐文・繰
り返し文・連続文など それぞれアルゴ リズムを定義した．
図 7 に，図 5((1, new Integer), (1, a))のAFG 辺を示((1, a), (3, a))す．AFG 辺は先
((3,
a),
(3,
b))
DD((3,
DDDDDDDDb),
DDDDDDDD(4,DDDDDDb))
DDDDDDに述べた到達エ((4, b), (4, c))
イリアス集合を図 7: AFG 辺-5-public class Calc f

Integer i;public Calc()
i = new Integer(0);public void inc()i = new Integer(i.intValue() + 1);
public void add(int c)
i = new Integer(i.intValue() + c);
public Integer result()
return(i);fgfclass Test f

Calc a, b;
Integer c;Test()
a = new Calc();b = new Calc();a.inc();
b.add(1);c = b.result();

g

f

f

g

f

g

g
g

g

図 8: サンプルプログラム
用いて引かれる．
例えば 文 4: c
= b においては，
到達エイリアス集合は f(1, a), (3, b)g となっており．AFG 節点 (3, b)〜 (4, b) 間に AFG 辺が引かれる．文 4 の解析後，到達エイリアス集合が更新され，新たに AFG 節点 (4, c) が追加され，f(1, a),(3, b), (4, c)g となる．
インスタンス属性・インスタンスメソッド の表現
オブ ジェクト 指向プ ログ ラムでは ，イン スタ
ン ス属性や イン スタン ス メソッド を表現するため「 a.b.c 」「 d.e() 」といった表記がなされ る．このため，AFG 節点の拡張が 必要となる．そのため，Method 節点・標準節点に，親節点・子節点に関する情報を追加する．具体的な例は図 9 に示す．
Phase 3: AFG の構築
AFG は，Phase 1:・Phase 2:で生成され る
AFG 節点・AFG 辺を用い，メソッド ・クラスごとに構築される．各メソッド を解析して構築されるメソッド AFG(Method AFG) は，メソッドが定義されたクラスのクラス AFG(Class AFG) に属する．図 8 にサンプルプログラムを，図 9 にそのAFG を示す．実線の無向辺は 2 節点間のエイリア
ス関係を，破線の有向辺は節点の親子関係 (has-a
関係) を表している．
Phase 4: メソッド 呼び出しグラフの構築
メソッド 呼び出しグラフ (Method Flow Graph，
MFG) とは，クラス中に存在する (同一インスタン ス) メソッド 間の呼び出し 関係を有向グラフで表現したものである．MFG 節点 (MFG Node) はメソッドを表し，メソッド A が メソッド B を呼ぶ
場合，MFG 辺 (MFG Edge) を節点 A から節点 Bに引く．図 10 にプログラムおよびその MFG を示
す．B クラスではメソッド p は定義されておらず，
親クラス A のメソッド p が利用される．B クラスの MFG 構築の際には，B クラスが継承したメソッ
ド A::p はメソッド q を呼び出しているが，それはメソッド B::q でありメソッド A::q ではないことに注意しなければならない．

表 2: 特殊節点

特殊節点

Actual-Alias-in(AA-in)
Formal-Alias-in(FA-in)
Actual-Alias-out(AA-out)
Formal-Alias-out(FA-out)
Method-Alias-out(MA-out)
MethodInstance-Alias-in(IA-in)
Instance-Alias-out(IA-out)

AA-in(out) 節点から AFG 辺をたど る
Step 1: オブジェクトへの参照 x に対応する AFG

public class Calc
Integer i;public Calc ( )public void inc ( )IA-out [ i ]IA-in [ i ] IA-out [ i ]i = new Integer ( 0 );i = new Integer ( i . intValue() + c );public void add ( int c )節点を X とする
X を始点とし，新たな到達可能節点が見つからなくなるまで AFG 辺を推移的にたどる．
その際，到達節点 C の種類に応じ ，存在する
AFG 辺をたど る以外に，以下のような処理を行う
親節点 P を持つ標準 (インスタンス属性) 節点:

Step 2:

public Integer result ( )IA-in [ i ] IA-out [ i ]IA-in [ i ] MA-out

i = new Integer ( i . intValue( ) + 1 );return ( i );(1) 節点 C に対応する属性を c とする(2) 節点 P のエ イリアス計算 (その結果を，P とする)(3) P に存在するイン スタン ス生成式から，

class Test
Calc a;Calc b;Integer c;Test()

P の型を類推a = new Calc ( ); b = new Calc ( );a . inc ( );(4) Object-Context(P ) の計算
Object-Context(P ) とは，P が子節点として持つ Method 節点の存

b . add ( 1 ); c = b . result ( );IA-out [ a ] IA-out [ b ]在により導出される，P が直接もしくは間接的に呼び出す可能性のあるメソッド 集合である．
直接呼び 出され るメソッド とは，Method 節点に対応するメソッドを指す (P の類推型が複数クラスになる場合，対応するメソッド も複数になる可能性がある)．
間接的に呼び出されるメソッドとは，直接呼び出されるメソッドが内部で呼び出す同一インスタンスのメソッドのことを指し，MFG を用いて導出する．
(5) Object-Context(P ) に属するメソッド の各メソッド AFG 内の IA-in[c]・IA-out[c]節点から AFG 辺をたど る(6) P の子節点のうち，識別子 c の標準節点から AFG 辺をたど る
親節点 P を持つ Method 節点:(1) 節点 C に対応するメソッド を c とする(2) 節点 P のエイリアス計算(3) P に存在するイン スタン ス生成式から，P の型を類推(4) Object-Context(P ) の計算(5) P の類推型が持つメソッド c に対応するメソッド AFG の MA-out 節点から AFG
辺をたど るIA-in(out) 節点:(1) 節点 C に対応する属性を c とする(2) Object-Context(this) に属するメソッド

IA-out [ c ]図 9: 図 8 の AFG
Phase 5: AFG を用いたエイリアス計算

AFG によるエイリアス計算は，AFG のグラフ到達問題に置き換えられる．ある オブジェクトへの参照 x のエイリアスを抽出する手順を基本方針とともに以下に示す．
基本方針 1: 親節点を持つ節点のエイリアスを導出する場合，まずその親節点のエイリアス計算
問題を解決させる (これにより，エイリアス解
析対象が特定インスタンスに限定される)基本方針 2: MA-out や FA-in(out) 節点など ，メ
ソッド 間をまたぐエイリアス関係の導出の際には，MFG を用いて対象 (呼び 出し 先・呼び 出し 元) メソッド を探索し ，対応する Method やclass A f
public void p() f q(); gpublic void q() f r(); gpublic void r() f g
gclass B extends Afpublic void q() f s(); gpublic void s() f gg

概要(実引数により，メソッドに渡されるエイリアス)(仮引数により，メソッドに渡されるエイリアス)(実引数により，メソッド 呼び出し元に渡されるエイリアス)(仮引数により，メソッド 呼び出し元に渡されるエイリアス)(戻り値により，メソッド 呼び出し元に渡されるエイリアス)(メソッド の戻り値により，メソッド 呼び出し元に渡されるエイリアス，
AA-in(out) 節点の親節点)
エイリアス属性 (属性により，メソッド 内に渡されるエイリアス)
エイリアス属性 (属性により，メソッド 外に渡されるエイリアス)
実エイリアス引数
仮エイリアス引数
実エイリアス引数
仮エイリアス引数
戻りエイリアス値
メソッド 呼び出し

A::p
A::q

A::p
A::r

Class A

B::q
B::s

Class B

図 10: メソッド 呼び出しグラフ (MFG)-6-

の メソッド AFG が持つ IA-out(in)[c] 節
点から AFG 辺をたど る
AA-in(out) 節点:(1) 節点 C の親節点である，Method 節点に対応するメソッド を PA とする(2) PA に対応するメソッド AFG を GA とする
(3) GA の該当する FA-in(out) 節点から AFG
辺をたど るFA-in(out) 節点:(1) 節点 C を持つメソッド AFG を GB ，GBに対応するメソッド を PB とする(2) Object-Context(this) に 含まれ ており，
かつ PB を呼び出す メソッド PA を MFGから抽出(3) PA に対応するメソッド AFG を GA とする
(4) GA の 該 当 す る AA-in(out) 節 点か ら
AFG 辺をたど る
MA-out 節点:(1) 節点 C を持つメソッド AFG を GB ，GBに対応するメソッド を PB とする(2) PB を呼び出すメソッド PA を MFG から抽出(3) PA に対応するメソッド AFG を GA とする
(4) GA が持つ ( メソッド PB を呼ぶ) メソッ
ド 節点から AFG 辺をたど る
Method 節点:(1) 節点 C に対応するメソッド PA のメソッ
ド AFG を GA とする(2) GA が持つ MA-out 節点から AFG 辺を
たど る
Step 3: 到達可能な AFG 節点集合に対応するオ
ブジェクトへの参照が，求める x のエイリアス
4.1 エイリアス計算例
エイリアス計算の例として，図 8 の参照変数 c(太枠部) のエイリアスの抽出手順を説明する．
(1) 参照変数 c に対応する AFG 節点から AFG 辺
をたど り，Method 節点 result() に到達(2) Method 節点 result() は親節点 b を持つため，
親節点 b のエイリアス計算を行い，Method 節
点のエイリアス計算に関与するインスタンスを特定する(1) 節点 b のエイリアス B を計算 (図 11)(2) B に存在するインスタン ス生成式から節点b の型を類推 [Calc クラス]
(3) Object-Context(B ) を計算 [fCalc::Calc()，
Calc::add(int c)，Calc::result()g](4) 節点 b の 型類推より，節点 b は Calc クラスの イン スタン スへの 参照であ ることから ，Calc::result() の MA-out 節点から AFG 辺をたど る (図 12)(1) AFG 辺をたど り，IA-in[i] に到達(2) 属性 i のエ イリア スに影響を 与え うる メ
ソッド，すなわ ち Object-Context(this)(=Object-Context(B )) の IA-out[i] 節点からエイリアス計算 (Object-Context(B ) に含まれ-7-class Test
Calc a;Calc b;Integer c;Test()
a = new Calc ( ); b = new Calc ( );a . inc ( );b . add ( 1 ); c = b . result ( );IA-out [ a ] IA-out [ b ]IA-out [ c ]図 11: 図 8 の b に関するエイリアス (網掛部)public class Calc
Integer i;public Calc ( )public void inc ( )IA-out [ i ]IA-in [ i ] IA-out [ i ]i = new Integer ( 0 );i = new Integer ( i . intValue() + c );public void add ( int c )public Integer result ( )IA-in [ i ] IA-out [ i ]IA-in [ i ] MA-out

i = new Integer ( i . intValue( ) + 1 );return ( i );図 12: 図 8 の b.result() に関するエイリアス (網掛部)ない Calc::inc() は対象から除外される)
図 13 に，c のエイリアス (網掛部) および ObjectContext(B )(下線部) を示す．
4.2

ポインタ変数を持つ言語でのエイリアス解析
これまで，参照変数を仮定したアルゴ リズムを記述したが，C・C++などポインタ変数を持つ言
語では，ポインタ (特に n 階 (n  2) ポインタ) による間接参照を考慮する必要がある．引数としてn 階ポインタ変数を使用することで，たとえ値渡しであっても，手続き内で呼び出し元のエイリア
ス関係を変更可能であるためである．
そこで，参照変数では 1 変数あたり 1 個のエイ
リアス情報であったが ，n 階ポ インタ変数では 1
変数あたり n 個のエイリアス情報を用意する．図14 は，C 言語で記述されたプログラムおよびそこから抽出されたエイリアス辺の集合を示している．
手続き assign(char **y, char *x) は 2 階のポイン
タ変数 y を使用しており，実引数である&b について&b および b に関するエイリアス情報が AA-in
として，仮引数 y について y および *y に関するエ
イリアス情報が FA-in として，手続き main()・手続き assign(char **y, char *x) にそれぞれ用意されている．また，b(*y) に関するエイリアス情報を呼び出し先に反映するため，AA-out(FA-out) が追加されている．

5

まとめと今後の課題

本研究では，オブジェクト指向言語に対する，再利用性・モジュール性を考慮したエイリアスフロー
グラフによるエイリアス解析手法 の提案を行った．
また，今回紹介できなかったが，提案手法を Javapublic class Calc f

Integer DDDDi DD;
public Calc()
DDi D
DDDDDDDInteger
DDDDDDD
DDD = Dnew
DDDDDDDDDDDDD(0);public void inc()i = new Integer(i.intValue() + 1);
public void add(int c)
DDi D
DDDDDDDInteger
DDDDDDD
DDD = Dnew
DDDDDDDDDDDDD
D
D
D(DDi D.intValue() + c);
public Integer result()
return(DDDDi DD);gramming Language Design and Implementation, pp.1{12, 1995.

f[4] B. Steensgaard, \Points-to analysis inalmost linear time." in 23rd Annual
ACM SIGACT-SIGPLAN Symposium on
the Principles of Programming Languages,
pp.32-41, 1996.

g

fclass Test f

Calc a, b;
Integer c;Test()
a = new Calc();b = new Calc();a.inc();
b.add(1);DDDDDDDDD
DDcD
DDDDDDDD();
DDD = Db.resultgf[5] M. Shapiro, and S. Horwitz, \Fast andaccurate ow-insensitive point-to analysis,"in 24th Annual ACM SIGACT-SIGPLAN
Symposium on the Principles of Programming Languages, 1997.

f

g

f

g

g

[6] M. Hind, and A. Pioli, \An Empritical
Comparison of Interprocedural Pointer Alias
Analysis," in IBM Research Report #21058,
1997.

g

g

図 13: 図 8 の c に関するエイリアス (網掛部)void main()
1: char *a, *b;
2: char c = ' ';3: a = &c;
4: assign(&b, a);5: putc(*b);
fg

6: void assign(
char **y,char *x)
7: *y = x;gf((3, &c), (3, a))((3, a), (4, a))((1, b), (4, b))((4, &b), (4, AA-in[y]))((4, b), (4, AA-in[*y]))((4, a), (4, AA-in[x]))((4, AA-out[*y]), (4, b))((4, b), (5, b))[7] P. Tonella, G. Antoniol, R. Fiutem, and E.
Merlo, \Flow Insensitive C++ Pointers andPolymorphism Analysis and its Application
to Slicing," in Proceedings of the 19th International Conference on Software Engineeringm, pp.433-443, 1997.
[8] J. Gosling, B. Joy, and G. Steele, 村上 雅章[訳], \The Java 言語仕様"((6, FA-in[y]), (7, y))((6, FA-in[*y]), (7, *y))((6, FA-in[x]), (7, x))((7, x), (7, *y))((7, *y), (6, FA-out[*y]))[9] B. Stroustrup, \The C++ Programming
Language(Third edition)," Addison-Wesley,1997.

図 14: ポインタ変数を持つ言語 (C) での解析

[10] G. Booch, \Object-Oriented Design with
Application," The Benjamin/Cummings
Pubrishinh Company, Inc, 1991.

を対象としたエイリアス解析ツールとして実装を行った．今後の課題としては，
 AFG データベースの構築 例外処理・スレッド への対応などが挙げられる．また，エイリアス解析ツール
による本手法の評価も行いたいと考えている．

[11] 片山, 土居, 鳥居 [監訳], \ソフトウェア工学大事典," 朝倉書店.
[12] S. Horwitz, and T. Reps, \The Use of Program Dependence Graphs in Software Engineering," In Proceedings of the 14th International Conference on Software Engineering,
pp 392{411, 1992.

謝辞 本研究は , 栢森情報科学振興財団の補助を受
けている.

参考文献
[1] M. Weiser, \Program Slicing," in Proceedings of the 5th International Conference on
Software Engineering, pp.439{449, 1981.
[2] M. Enami, R. Ghiya, and L. J. Hendren,\Context-sensitive interprocedural points-to
analysis int the presence of function pointers." in SIGPLAN'94 Conference on Programming Language Design and Implementation, pp.242{256, 1994.
[3] R. P. Wilson, and M. S. Lam, \EÆcient
context-sensitive pointer analysis for C Programs," in SIGPLAN'95 Conference on Pro-8-c