論 文
エイリアスフローグラフを用いた
オブジェクト指向プログラムのエイリアス解析手法
大畑 文明y近藤 和弘y井上 克郎y; yy

Alias Analysis Method for Object Oriented Programs Using Alias Flow Graphs
y

y

y; yy

Fumiaki OHATA , Kazuhiro KONDOU , and Katsuro INOUE

あらまし プログラムテキスト上の式（ または部分式）の対が同一のオブジェクト（ メモリ領域）を指す場合，
それらの式はエイリアス関係にあるという．これらは，引数の参照渡し ，参照変数，ポインタを介した間接参照などで生じる．既存のエイリアス解析手法は，解析結果の再利用が不十分で，オブジェクト指向プログラムの持つ再利用性がエイリアス解析に生かされていない．また，エイリアス解析手法の提案は今までいろいろなされているが，実用的なツールはあまり知られていない．本研究では，エイリアス解析結果の再利用およびモジュール化を考慮した，オブジェクト指向プログラムに対するエイリアス解析手法を提案する．本手法を実現したJava
エイリアス解析ツールは，JDK（ Java Developers's Kit ）附属クラスライブラリなど の大規模プログラムを実用的な時間で解析することができる．
キーワード

1.

エイリアス，モジュール化，オブジェクト指向プログラム，Java

新しい概念が導入されており，それらに対応したエイ

まえが き

リアス解析手法が提案されている [14]．

プログラムテキスト上の式（ または部分式）の対が

しかし ，既存のエイリアス解析手法は，解析手法を同一のオブジェクト（ メモリ領域）を指す場合，それオブジェクト指向言語に対応させたに過ぎず，解析結らの式はエイリアス関係（ Alias Relation ）にあると果そのものの再利用性，モジュール性は満たされていいう．エイリアス関係は，引数の参照渡し ，参照変数，

ない．プログラムの大規模化，プログラムの再利用へポインタを介した間接参照などによって生じ る．エイの関心が高まる現在，これらの特性を満たすエイリア

リアス関係は同値関係であり，その同値類をエイリア

ス解析手法が望まれる．

ス集合（ Alias Set ）と呼ぶ．また ，プ ログ ラムを静的に解析しエイリアス集合を求めることをエイリアス

本研究では，再利用性，モジュール性を考慮したエイリアスフローグラフによるエイリアス解析手法の提解析（ Alias Analysis ）といい，コンパイル時の最適案を行う．また，提案手法をJava エイリアス解析ツー

化 [1] や，プログラムスライス（ Prgram Slice ）[13] のルとして実装し その有効性を評価する．本ツールは，計算に欠くことのできないものである．

近年ソフト ウェア開発言語とし て多く利用されていまた，現在のプログラム開発環境において，C など

るJava を対象としており，JDK（ Java Developers'sの手続き型言語だけでなく，Java [7]，C++ [3] 等いKit ）附属クラスライブラリなど の大規模プ ログラム

わゆるオブジェクト 指向言語の利用が 高まっている．

に対しても実用的な時間で解析することができる．

オブジェクト指向言語には，従来の手続き型言語にはないクラス，継承，動的束縛，ポリモルフィズムなど

y 大阪大学大学院 基礎工学研究科，豊中市

Graduate School of Engineering Science, Osaka University,
Toyonaka-shi, 560-8531 Japanyy 奈良先端科学技術大学院大学 情報科学研究科, 生駒市
Graduate School of Information Science, Nara Institute of
Science and Technology, Ikoma-shi, 630-0101 Japan
電子情報通信学会論文誌

X

Vol. Jxx{X

以降，2. ではエイリアス解析およびオブジェクト指

向プログラムに対する解析について説明する．3. で手法の提案を行う．4. で Java エイリアス解析ツールによる手法の実験的評価を行い，5. で考察する．最後に

6. でまとめと今後の課題について述べる．

No. xxpp. 1{11xxxx

年 xx 月1

電子情報通信学会論文誌 'xx/xx Vol. Jxx{X No. xx

2.

2. 1

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

エイリアス解析は，大きくFI エイリアス解析（ Flow（以降，FI 解析と略す），
Insensitive Alias Analysis ）FS エイリアス解析（ Flow-Sensitive Alias Analysis ）2. 2

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

既存のオブジェクト指向プログラムにおけるエイリ
アス解析手法は，既に提案されている手続き型言語のエイリアス解析手法をオブジェクト指向言語に拡張したものとなっているが，それらに関していくつかの視点から考察を行う．

（以降，FS 解析と略す）の 2 つに分けることができる．

FS 解析の問題

Flow-Insensitive（ FI ）エイリアス解析

リアス集合を用いた FS 解析では，すべての実行（ 手以下，それぞれを図 1 を用いて簡単に説明する．

FI エイリアス解析 [2], [12] とは，各プログラム文の実行順を考慮しないエイリアス解析手法をいい，エイリアスグラフを利用する．図 1(a) に変数 c（ 太枠部）の FI エイリアス（ 網掛部）を，図 1(c) にその計算に用いたエイリアスグラフを示す．エイリアスグラフは無向グラフであり，節点はメモリ領域を指し うる変数
および式を，辺は（代入や引数の参照渡しなどにより）節点間に直接のエイリアス関係があることを表す．文

7 の変数 c に関するエイリアスを求める場合，エイリ
fa, b,
new Integer(1), new Integer(2))g であり，網掛部がアスグラフの変数 c 節点から到達可能な節点は求めるエイリアスとなる．
Flow-Sensitive（ FS ）エイリアス解析

FS エ イリアス解析 [9], [16] とは，プ ログラム文の手続きを含むプログラムを解析する場合，到達エイ
続き呼び出し ）経路をたど りながら到達エイリアス集合を計算しなければならない．また，再帰呼び出しが存在する場合，エイリアス集合が収束するまで再帰経路を解析し続ける必要がある．これは，解析結果がエ
イリアス集合の形で保持されていることに起因し ている．つまり，ある時点でエイリアス集合に変化が起こったとき，その変化の影響を受ける可能性のある到達エイリアス集合を持つ文すべてにその変化を伝播させ，各文の到達エイリアス集合を再計算しなければならないためである．

解析結果の再利用
到達エイリアス集合 RA(s) は文 s が存在するプログラム全体を解析することにより導出されたものであるため，別の文 t が変更されたとき，RA(s) を再計算しなければならない場合が多く存在する．これは，エ

実行順を考慮したエイリアス解析手法をいい，到達エ

イリアス解析結果のモジュール性，独立性が満されてイリアス集合（ Reaching Alias Set ）を利用する．図いないことに起因する．オブジェクト指向プログラム

1(b) に変数 c（ 太枠部 ）の FS エ イリアス（ 網掛部 ）を，図 1(d) にその計算に用いた到達エイリアス集合
を示す．到達エイリアス集合 RA(s) の要素は 文 s の実行直前において成立し かつ 文 s において識別子を介して参照可能なエイリアス集合であり，その集合の各要素は (文番号，式) の組で表わされ る．文 7 の変数 c に関するエイリアスを求める場合，RA(7) から識別子 c を含むエイリアス集合を探索する．変数 c は集合f(6, c), (2, a), (6, a), (2, new Integer(1))g に含

まれており，網掛部が求めるエイリアスとなる．
FI エイリアス解析と FS エイリアス解析

FS 解析はプログラム文の実行順を考慮しているため，FI 解析と比較し時間計算量，空間計算量を必要とするが，解析の精度は高く，実際に図 1 においてもその差は顕著である．両者の詳細な比較は [11] でなされでは，継承機能など ，言語自身が再利用を考慮したものとなっているため，記述されたクラスの利用範囲が特定のプログラムにとど まらない．また，上位クラスであるほど その属性やメソッド は汎化されたものとなり，一度定義されると変更されることは少ない．そのため，解析結果のクラスやメソッド 単位でのモジュー
ル化は ，再計算コストの削減に有効であると考えている．

同一クラスの異なるインスタンス属性の取り扱い
オブジェクト指向プログラムでは，異なるオブジェ
クト間での状態（ 属性）と振舞い（ メソッド ）は独立であるため，図 2 の例では

fx.s, A::sg，fy.s, A::sg がそれぞれエイリアス集合といえるが，同一クラスのイf

ンスタンスがその内部情報を共有する場合， x.s, y.s,

A::sg がエイリアス集合とみなされるため，解析精度ており，本研究では解析精度を重視していることからの低下につながる．このため，インスタンスごとにク

FS 解析に着目する．

ラス内部のエイリアス情報を持たせる手法が考えられ

2

論文／エイリアスフローグラフを用いたオブジェクト指向プログラムのエイリアス解析手法

1: Integer a, b, c;
2: a = new Integer(1);3: b = new Integer(2);4: c = b;
5: System.out.println(c);6: c = a;
7: System.out.println(c);1: Integer a, b, c;
2: a = new Integer(1);3: b = new Integer(2);4: c = b;
5: System.out.println(c);6: c = a;
7: System.out.println(c);(a) FI エイリアス解析(b) FS エイリアス解析

new Integer(1)

a

c

b

new Integer(2)到達エイリアス集合 (RA(s))

文 (s)




1
2
3
4

f(2, a), (2, new Integer(1))gf(2, a), (2, new Integer(1))g,f(3, b), (3, new Integer(2))gf(2, a), (2, new Integer(1))g,f(4, c), (3, b), (4，b), (3, new Integer(2))gf(2, a), (2, new Integer(1))g,f(4, c), (5, c), (3, b), (4，b),(3, new Integer(2))gf (6, c), (2, a), (6, a), (2, new Integer(1)) g,f(3, b), (4, b), (3, new Integer(2))g(d) 到達エイリアス集合

567(c) エイリアスグラフ

図 1 FI エイリアス解析 と FS エイリアス解析
Fig. 1 FI alias analysis and FS alias analysis

x = new A;
y = new A;
x.s = . . . ;y.s = . . . ;class A f
Integer s;. . . (. . . ) f. . . = s;

図 2 オブジェクト指向プログラム（ Java ）1: Integer a =new Integer(0);2: Integer b, c;
3: b = a;4: c = b;生成すると多大な空間コストを要する．そこで，存在するエイリアス関係を

内部エイリアス関係（ Inner Alias Relation ） 同 一
クラスのインスタンス間で共通なエイリアス関係

外部エイリアス関係（ Outer Alias Relation ） 同一
クラスのインスタンス間で独立なエイリアス関係に分け，内部エイリアス関係のみ前もって解析し ，外部エイリアス関係は必要に応じて逐次導出する手法が考えられる．

Integer b, c;
c = b;

b = a;

図 3 サンプルプログラム および その AFG

Fig. 2 Object oriented program(Java)

るが，単純にインスタンスの数だけエイリアス情報をInteger a = new Integer(0);Fig. 3 Sample program and its AFGズで構成される．

Phase 1:
Phase 2:Phase 3:Phase 4:

AFG 節点（オブジェクトへの参照）の抽出
AFG 辺（ 直接のエイリアス関係）の抽出
メソッド 呼び出しグラフの構築
エイリアス計算クラス，メソッド 単位で FS エ イリアス解析を到達
エ イリアス集合によって行い，クラス AFG（ Class
AFG ），メソッド AFG（ Method AFG ）をそれぞれ構築する（ Phase 1 { 2 ）．各 AFG は独立したモジュー
ルとして存在し ，対応するクラス，メソッドが更新さ

エイリアスフローグラフ（ AFG ）を用いたエイリアス解析手法

れない限り不変であり，二次媒体への記憶およびその本研究では，前節で述べた再解析コストの軽減，エみ保持しており，外部エイリアス関係はユーザからの3.

イリアス解析結果のモジュール化，内部エイリアス関係および外部エイリアス関係の抽出のための，（ 1 ） エイリアスフローグラフ（ AFG ）構築法

（ 2 ） AFG によるエイリアス計算手法

再利用が可能である．AFG は内部エイリアス関係の要求があったとき逐次解析する（ Phase 4 ）．

以降，メソッド のない単一プ ログ ラム（ 図 3 ），複数メソッド で構成されたプログラム（ 図 8 ）を例に用いながら各フェーズを順に説明する．

の提案を行う．エイリアスフローグラフ（ Alias Flow

3. 1

Graph，AFG ）は，FS エイリアス関係を無向グラフ

AFG 節点（ AFG Node ）は，文番号とオブジェク

Phase 1: AFG 節点の抽出で表現したものであり，FS エ イリアスの計算をグラトへの参照式の組である．ここでいうオブジェクト へ

フの到達問題に置き換える．本節で述べるアルゴ リズの参照式とは，参照型の式を指し，参照変数および イムはJava を前提に，参照型の式（ 参照変数，インス

ンスタンス生成式もこれに含まれる．また，これらのタンス生成式など ）によるエイリアスを対象としてい節点を特にAFG 標準節点（ AFG Normal Node ）とるが，ポインタ変数の間接参照によるエイリアスにも呼ぶ．

拡張可能であり，5. 2 で簡単に述べる．

AFG によるエイリアス解析手法は以下 4 つのフェー

図 3 の 文番号 3 の b は 参照変数であるためオブジェクトへの参照式に該当し ，AFG 節点 (3, b) が生
3

電子情報通信学会論文誌 'xx/xx Vol. Jxx{X No. xx

成される（ 注 1 ）．同様に，文番号 1 のnew Integer(0) はインスタン ス生成式であるため，AFG 節点 (1, newInteger(0)) が生成される．

メソッド のない単一プ ログ ラムにおいては ，AFG

標準節点のみ用いることで AFG を構築できる．一方，通常オブジェクト指向プログラムではメソッド 引数やclass A f
void p() fq();gvoid q() fr();gvoid r() fg

class B extends Af
void q() fs();gvoid s() fgg

A::p()

A::q()(a) Class A

インスタンス（ クラス）属性が存在するため，これらA::r()g
A::p()

B::q()

B::s()(b) Class B

A::q()

図 4 サンプルプログラム および その MFGを介したエイリアスの受け渡しを考慮しなければなら

Fig. 4 Sample program and its MFG

ない．そのため．表 1 に挙げるAFG 特殊節点（ AFG
Special Node ）を追加する．

3. 2

Phase 2: AFG 辺の抽出

AFG 標準辺（ AFG Normal Edge ）は，2 つの AFG

節点間で，同一変数の参照や代入文，パラメータの対応などによる直接のエイリアス関係が存在するとき引かれる．複数の AFG 辺で構成された経路は，2 節点間'(x): 式 x から AFG 節点 X への射影
X : X のエイリアス（ X は AFG 節点の集合）
NP (X ): X の親節点(m): メソッド m からメソッド AFGM への射影
e =id e0 : 式 e と式 e0 が同じ 識別子であるとき真，さもなくば 偽図6 定義Fig. 6 De nitionsの（推移的に成り立つ）間接のエイリアス関係を表す．
また，AFG をオブジェクト指向プ ログラムに適応する際，a:b や c:d() のようなイン スタン ス属性やイン スタン スメソッド を表現するために ，イン スタン
ス および 属性（ メソッド ）を表す AFG 節点間に親子関係を定義する．例えば a:b に関し て，a，b に対応する AFG 節点をそれぞれ Na ，Nb とすると，Naは Nb の 親節点（ Parent Node ），Nb は Na の 子節点（ Child Node ）となり，Na から Nb に対し有向辺が引かれる（このような辺をAFG 特殊辺（ AFG Spetial
Edge ）と呼ぶ ）．図 9 にその具体例（ 破線の有向辺）を示す．この関係はエイリアス計算時（ Phase 4 ）にの MFG 構築の際には，B クラスが継承したメソッド

A::p() はシグニチャq() のメソッド を呼び出しているが，それは B::q() でありメソッド A::q() ではないことに留意する必要がある．
3. 4

Phase 4: エイリアス計算

AFG によるエイリアス計算は以下の方針に基づく．

（ 1 ） 親節点 P を持つ節点 C のエイリアスを導出する場合，まず P のエ イリアス計算問題を解決させ（ これにより，エ イリアス解析対象が特定インスタン

スに限定され，P の型および 後述するオブジェクトコ

利用される．このような節点間の親子関係は Method

ンテキストが導出される），その結果を元に C のエイしても同様に AFG 特殊辺を引く．

リアス計算を行う

節点と AA-in（ out ）節点間にも存在し ，これらに対
3. 3

Phase 3: メソッド 呼び出しグラフの構築

メソッド 呼び 出し グ ラフ（ Method Flow Graph，
MFG ）とは，クラス中に存在する（ 同一イン スタンス）メソッド 間の呼び出し関係を有向グラフで表現したものである．MFG の各節点を MFG 節点（ MFG

Node ）と呼び，メソッド を表す．メソッド A がメソッ

ド B を呼ぶ場合，A，B に対応する MFG 節点をそれぞれ MA ，MB とすると，有向辺であるMFG 辺（ MFG Edge ）が節点 MA から節点 MB に引かれる．

図 4 にサンプルプログラムおよびその MFG を示す．

B クラスではメソッド p は定義されておらず，シグニ

チャp() に対するメソッド は A::p() となる．B クラス

1

AFG

AFG

（注 ）
：本論文に図示されているに関して，節点のラベルには文番号が省略されているが，分りやすいようプログラムテキストの文字列をグラフ上に補助的に記している．

4（ 2 ） MA-out や FA-in（ out ）節点など ，メソッド間をまたぐ エイリアス関係の導出の際には，MFG を用いて呼び 出し 先（ 呼び 出し 元 ）メソッド を探索し ，対応する Method 節点や AA-in（ out ）節点から AFG
辺をたど るアルゴ リズムの詳細は図 5 に，またその中で利用する式の定義を図 6 に示す．

オブジェクト コンテキスト

AFG を用いて 導出されたエ イリアス集合 P に 関するオブジェクト コンテキスト（ Object Context ）とP に属する節点の子節点として存在する Method
P が 直接もし くは間接的に呼は，節点から導出され る，

び 出す可能性のある メソッド 集合を指し ，Object-

P

Context( ) と表す．

直接呼び出されるメソッド とは，Method 節点に対

論文／エイリアスフローグラフを用いたオブジェクト指向プログラムのエイリアス解析手法
表1 特殊節点
Table 1 AFG special node
特殊節点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 ）節点の親節点）
エイリアス属性（ 属性により，メソッド 内に渡されるエイリアス）
エイリアス属性（ 属性により，メソッド 外に渡されるエイリアス）

Step 1: E := '(e)Step 2: E を始点とし ，新たな到達可能節点が見つからなくなるまで AFG 辺を推移的にたど る

加えて，到達節点 C の種類に応じて以下のような処理も行う[Cond.1] 親節点を持つ標準（ インスタンス属性）節点:（ 1 ） c := ' 1 (C )，P := NP (C )1 (G )（ 2 ） GMM Object-Context( ) に含まれる IA-in（ out ）[c] 節点から AFG 辺をたど る
N NP (N )&& ' 1 (N ) =id c から AFG 辺をたど る[Cond.2] 親節点を持つ Method 節点:（ 1 ） c := ' 1 (C )，P := NP (C )1 (M )（2） M
Object-Context( ) に含まれる MA-out 節点から AFG 辺をたど る[Cond.3] IA-in（ out ）節点:1
（ 1 ） c := ' (C )1 (M )（2） M
Object-Context(this) に含まれる IA-out（ in ）[c] 節点から AFG 辺をたど る[Cond.4] AA-in（ out ）節点:
（ 1 ） Method 節点 NP (C ) が呼ぶメソッド m を計算（ 2 ） (m) に含まれる FA-in（ out ）節点から AFG 辺をたど る[Cond.5] FA-in（ out ）節点:
（ 1 ） MB := M C
M , mB := 1 (MB )（ 2 ） mA := m m Object-Context(this) && m が mB を呼ぶ （ MFG より），MA := (mA )（ 3 ） MA に含まれる AA-in（ out ）節点から AFG 辺をたど る[Cond.6] MA-out 節点:（ 1 ） MB := M C
M ，mB := 1 (MB )（ 2 ） mA := m m が mB を呼ぶ （ MFG より），MA := (mA )（ 3 ） MA に含まれる（ mB を呼ぶ）Method 節点から AFG 辺をたど る[Cond.7] Method 節点:（ 1 ） 節点 C に対応するメソッド 呼び出し文から呼ばれるメソッドを mA とする（ 2 ） MA := (mA )（ 3 ） MA に含まれる MA-out 節点から AFG 辺をたど る
Step 3: 到達可能な AFG 節点集合に対応するオブジェクトへの参照式が，求める e のエイリアス

f j
f j

2P

f j

2

f j

2

2

Pg
g

Pg

g

f j 2 gf j 2

g

f j 2 gf j

g

図 5 エイリアス計算アルゴ リズム
Fig. 5 Alias calculation algorithm

応するメソッド を指す（ 注 2 ）．間接的に呼び 出されるメ

トより正確なエイリアス情報を抽出することができる．

オブジェクト コンテキスト（ Flow Insensitive Object

例として，図 7 において Calc::Calc()， Calc::add()，
Calc::result() が順に呼ばれたときのreturn(i) に関す
るエ イリアス計算を挙げ る．図 7(b) は メソッド 実行
順を考慮しているため，図 7(a) と比較してそのエ イ
リアス集合は小さく，Calc::Calc() メソッド 内の 2 式
i，new Integer が除外されているのが分かる．メソッ

Context ）に分けられる．前者は メソッド の実行順を

ド 実行順を考慮するには解析コストの増加は避けられ考慮するが，後者は考慮しない．そのため，FS オブず，これらはトレード オフの関係となる．なお，本論

ソッド とは，直接呼び出されるメソッドが内部で呼び出す可能性のある同一インスタンスのメソッド を指し，MFG を用いて導出する．
またオブジェクトコンテキストは，FS オブジェクト

コンテキスト（ Flow Sensitive Object Context ），FI

ジェクトコンテキストは FI オブジェクトコンテキス

文では FI オブジェクトコンテキストを採用している．
3. 5

2

P

（注 ）
：メソッド のオーバーライドが行われた場合， の型が唯一に特定できなければ同一シグニチャに対してメソッドが複数存在する可能性がある

エイリアス計算例

エイリアス計算の例として，図 8 の参照変数 c（ 太枠網掛部）のエイリアスの抽出手順を説明する．
5

電子情報通信学会論文誌 'xx/xx Vol. Jxx{X No. xx

public class Calc f
Integer i;public Calc() fi = new Integer(0);g
public void inc() fi = new Integer(i.intValue() + 1);g
public void add(int c) f
i = new Integer(i.intValue() + c);

public class Calc f
Integer i;public Calc() fi = new Integer(0);gpublic void inc() fi = new Integer(i.intValue() + 1);gg

public Integer result() freturn(i);ggpublic void add(int c) f
i = new Integer(i.intValue() + c);(a) FI オブジェクトコンテキスト
public class Calc f
Integer i;public Calc() fi = new Integer(0);g
public void inc() fi = new Integer(i.intValue() + 1);g
public void add(int c) f
i = new Integer(i.intValue() + c);gg

public Integer result() freturn(i);g(b) FS オブジェクトコンテキスト
図 7 オブジェクトコンテキスト

Fig. 7 Object context

gpublic Integer result() f
return(i);ggresult() のエイリアス計算に関与するインスタンスを特定する（ a ） 節点 b のエイリアス（b）

B を計算（ 図 9 ）

B に存在するインスタンス生成式から節点 bの型を特定 [Calc クラス]（ c ） Object-Context(B) を 計 算 [fCalc::Calc()，
Calc::add(int c)，Calc::result()g]（ 3 ） 節点 b は Calc クラスのインスタンスへの参照であることから，Calc::result() の MA-out 節点から AFG 辺をたど る（ 図 10 ）（ a ） AFG 辺をたど り，IA-in[i] に到達（ b ） 属 性 i の エ イ リア スに 影 響 を 与え うる メ
ソッド，すなわち Object-Context(this) = ObjectContext(B) の IA-out[i] 節点から AFG 辺をたど る（ Calc::Calc()， Calc::add() も同様）
図 8 に，c のエイリアス（ 網掛部）および Object-

Context(B)（下線部）を示す．Object-Context(B) に含まれない Calc::inc() はエ イリアス計算対象から除外されているのが分かる．
4.

実

験

提案手法を Java を対象言語とするエイリアス解析
6gFig. 8 Alias set for c at c = b.result()(Masked)

Class Test
Calc a; Calc b; Integer c;Test() IA-in[a]辺をたどり，Method 節点 result() に到達（ 図 9 ）め，親節点 b のエイリアス計算を行い，Method 節点g

図 8 文 c = b.result() の c に関するエイリアス（網掛部）（ 1 ） 参照変数 c に対応する AFG 節点から AFG（ 2 ） Method 節点 result() は 親節点 b を持つた

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

IA-in[c]a = new Calc();b = new Calc();a.inc();

b.add(1);IA-out[a]図9IA-in[b]IA-out[b]c = b.result();

IA-out[c]図 8 の文 c = b.result() の b に関するエイリアス（ 網掛部）

Fig. 9 Alias set for b at c = b.result() inFig.8(Masked)
public Class Calc
Integer i;public Calc() IA-in[i]public void inc() IA-in[i]i = new Integer(0);i = new Integer(i.intValue() + 1);

IA-out[i]IA-out[i]public void add(int c) IA-in[i]i = new Integer(i.intValue() + c);
IA-out[i]public Integer result() IA-in[i]return(i);MA-out

図 10 図 8 の文 c = b.result() の b.result() に関するエイリアス（ 網掛部）

Fig. 10 Alias set for b.result() at c = b.result() inFig.8(Masked)

ツールとして実装し，本手法の有効性を評価した．解析アルゴ リズムとして，FI オブジェクトコンテキストを採用している．
4. 1

Java エイリアス解析ツール

ツールは解析部（ Java エイリアス解析ライブラリ）論文／エイリアスフローグラフを用いたオブジェクト指向プログラムのエイリアス解析手法とユーザーインタフェース部（ Java エ イリアス表示

SourceFile

ParseTree SemanticTree

MFG AFGツール ）で構成されており，その構成を図 11(a) に示

す．以降，解析部およびユーザーインターフェース部

libANTLR

をそれぞれ簡単に説明する．

libjavammlibAFG
Answer

Query

UI

User

解析部
解析部は C++で記述されており，libANTLR（ 字(a) ツール構成

句解析 ，構文解析 ）（注 3 ），libjavamm（ 意味解析 ），libAFG（エイリアス解析）の 3 つのライブ ラリで構成されている．これらのライブ ラリにより，各Java

ソースプ ログ ラムに対して構文解析木，意味解析木，

MFG および AFG がそれぞれ構築される．
ユーザーインターフェース部
ユーザーインターフェース部は，C++で記述されており Gtk[6] ツールキットを使用している．その機能には，テキストウインド ウ（ 図 11(b) ）およびエ
イリアスツリーウインド ウ（ 図 11(c) ）によるエイリ

アス表示，プログラム編集がある．ユーザがあるオブ
ジェクトへの参照式に関するエイリアスの抽出を指示(b) テキストウィンド ウ

すると，ツールはテキストウィンド ウおよびエイリア
スツリーウィンド ウ上にその解析結果を表示する．
エイリアス集合の導出により，プログラムテキスト
はエ イリアス集合に含まれ るエイリアス部分（ Alias
part ）と，エイリアス集合に含まれない非エイリアス

部分（ Non-alias part ）に区分される．テキストウィ
ンド ウでは，ユーザの視点をエイリアス部分に着目させなければならないが，エイリアス部分 と 非エイリ
アス部分の差別化の手段はユーザの目的によって様々(c) エイリアスツリーウィンド ウである．とりわけ，エイリアスの性質上ソースコード

図 11 Java エイリアス解析ツール

Fig. 11 Java alias analysis tool

中に占める割合は非エイリアス部分が圧倒的に多く，その視覚化に重点を置く必要がある．本ツールでは目的に応じた 3 つの視覚化手法を実現し，その一つとして，図 11(b) ではエイリアス部分を背景色の変更により，非エイリアス部分を線分化により差別化を行っている．
また，エイリアス部分は複数メソッドにわたって点在することが多く，複数のファイルにおよぶことも少なくない．エイリアスツリーウィンド ウは，テキスト
ウィンド ウでは困難なエイリアス部分全体の把握を支援する．エイリアスツリーの各節点は，クラス名，メ
ソッド 名，オブジェクトへの参照式を表わす．図 11(c)では，2 つのエイリアス集合（ ALIAS[0]，ALIAS[1] ）のエイリアスツリーが示されており，ツリーの各節点

3 ANTLR [5]

L

L

L

（注 ）
：
は，言語 の文法 を与えることでの字句解
析，構文解析ルーチンをもし くは Java で生成するツールである．

C++を選択することで対応する要素の名前，型，位置などの情報を得ることができる．
4. 2

計測方法

対象プログラムの概要を表 2 に示す．ここでは，対象プログラム自身を新規モジュール，対象プログラムが利用する JDK 1.2 附属クラスライブ ラリを 再利用可能モジュールとみなし，以下の 3 点について検証を行った．
（ 1 ） 解析結果のモジュール化による効率化
新規モジュールおよび 再利用可能モジュールのエ イリアス解析（ Phase 1 { 3 ）時間の比較（ 表 3 ）．

（ 2 ） AFG によるエイリアス計算時間7電子情報通信学会論文誌 'xx/xx Vol. Jxx{X No. xx
表 2 対象プログラム
Table 2 Target programs
プログラム

[概要]
WeirdX[X サーバ]
ANTLR[構文解析生成]
DynamicJava[インタプ リタ]

新規
ファ イル
行

47

16,703とそのモジュールが利用する他のモジュールも再解析

再利用可能（ JDK ）ファ イル
行

815 115,977(5.5%) (12.6%) (94.5%) (87.4%)
129 18,775
267 33,847(32.6%) (35.7%) (67.4%) (64.3%)
242 32,037
825 119,564(22.7%) (21.1%) (77.3%) (78.9%)

表 3 エイリアス解析時間（ Phase 1 { 3 ）[ms]Table 3 Alias analysis time(Phase 1 { 3)[ms]
プログラム

新規

再利用可能

WeirdX
com.jcraft.weirdx.Client
ANTLR
antlr.MakeGrammar
DynamicJava koala.dynamicjava.
interpreter.TypeChecker

計算対象クラス

られる．
到達エイリアス集合のみによるエイリアス解析では，
解析終了時点ですべてのエイリアス集合が抽出されている．提案手法のエイリアス解析過程は，AFG 構築（ Phase 1 { 3 ） および AFG によるエイリアス計算

AFG 構築時間と比較した場合，エイリアス計算に要ものに限られている場合やユーザとの対話形式でエイ

計算時間

0.29
0.17
0.07

リアスを求める解析ツールの実現においては，実用に十分に足るものであると考えている（ 表 4 ）．
また本手法では，同一クラスのインスタンスに共通するエイリアス関係のみ AFG に保持し ，インスタン
ス独自のエイリアス関係はエイリアス計算時に導出す
る．本手法の適応により，同一クラスの異なるインス

Table 5 Size of alias set

WeirdX
com.jcraft.weirdx.Client
ANTLR
antlr.MakeGrammar
DynamicJava koala.dynamicjava.
interpreter.TypeChecker

ジュールのみ解析すればよく，解析コストの削減が得する時間コストは小さく，求めるエイリアスが特定の表 5 エイリアス集合の要素数
プログラム

AFG を構築しておくことで，ユーザは新規・更新モ

するにはエ イリアス計算を行う必要がある．しかし ，

表 4 エイリアス計算時間（ Phase 4 ）[ms]Table 4 Alias calculation time(Phase 4)[ms]
計算対象クラス

加えられず繰り返し再利用されるモジュールを解析し（ Phase 4 ）に区分されており，エイリアス集合を導出

WeirdX
14,220100,540
ANTLR
12,83023,480
DynamicJava 56,260
110,150
PentiumIII-667MHz-512MB(Linux)

プログラムの対象にせざ るを得ない．本手法では，新たな変更が

非共有

共有

15.37 24.54
5.94 18.77
9.16 17.19

対象ファイルに存在する全ての AFG 標準節

点からの平均エイリアス計算（ Phase 4 ）時間（ 表 4 ）．

タンスのエイリアス情報を個別に取り扱うことで精度の向上が得られている（ 表 5 ）．
5. 2

ポインタ変数を持つ言語でのエイリアス解析

3. で述べたアルゴ リズムは Java の持つ参照型の式によるエイリアスを仮定したものであったが，C，C++などポインタ変数を持つ言語ではポインタ（ 特に高階
ポインタ）による間接参照を考慮する必要がある．こ 2) ポインタ変数を使用す（ 3 ） 同一クラスの異なるインスタンスの属性を区れは，引数として n 階 (n別することによる解析精度への影響ることで，たとえ値渡しであっても，手続き内で呼びインスタンス属性に関するエイリアス情報に関し，提案手法をポインタに適用するため Phase 1，2，4

 インスタンスごとに区別しない（共有） インスタンスごとに区別する（非共有）を拡張する．以下にその拡張に関して簡潔に述べる．

の 2 つの手法を用いて（ 2 ）と同様のエ イリの抽出

アス計算を行い，導出されたエイリアス集合

あったが，n 階ポインタ変数では 1 変数あたり n 個のの平均要素数を比較（ 表 5 ）．
5.

考

察

5. 1

実験データの解釈

解析結果のモジュール化による効率化（ 表 3 ）に関して，到達エイリアス集合のみによるエイリアス解析
では，モジュール単位でエイリアス解析結果を保持することができないため，あるモジュールが変更される
8

出し元のエイリアス関係を変更可能であることによる．

| Phase 1: AFG 節点の抽出，Phase 2: AFG 辺
参照変数では 1 変数あたり 1 つのエイリアス情報でエイリアス情報を用意する．図 12 は，C 言語で記述されたプログラムおよびそこから抽出された直接のエイリアス関係の集合を示している．手続き assign(char**y, char *x) は 2 階のポインタ変数 y を使用しており，実引数である&b について &b および b に関するエイリアス情報が AA-in 節点として，仮引数 y について y および *y に関するエイリアス情報が FA-in 節

点として，手続き main()，手続き assign(char **y,

論文／エイリアスフローグラフを用いたオブジェクト指向プログラムのエイリアス解析手法

1:
2:
3:
4:
5:

void main() fchar *a, *b;char c = ' ';a = &c;assign(&b, a);putc(*b);g((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))

されることを意味する．この時，( ,) を ( , Æ ) に対する制約条件という．この制約条件は，本論文でいう間接的なエイリアス関係の成立条件に対応する．
しかし ，これらの手法はエイリアス解析のモジュール化（ 呼び出し側モジュールの解析結果に依存しない
エイリアス解析）を実現するため，各モジュール内で((6, FA-in[y]), (7, y))((6, FA-in[*y]), (7, *y))((6, FA-in[x]), (7, x))((7, x), (7, *y))g((7, *y), (6, FA-out[*y]))
図 12 ポインタ変数を持つ言語（ C ）でのエイリアス解析
Fig. 12 Alias analysis for languages with pointervariables like Cのエイリアス解析時に，対象モジュールから参照可能

Step 2: E を始点とし ，新たな到達可能節点が見つからなくなるまで AFG 辺を推移的にたど るて，モジュール内のエイリアス解析時（ Phase 1 { 2 ）6: void assign(char **y,char *x) f
7: *y = x;な外部変数（ 大域変数や仮引数など ）のすべての組み合わせを ( ,) として与え，そのとき成立するエ イ

リアス組 ( , Æ ) を抽出する必要がある．

我々の手法は直接的なエ イリアス関係のみを AFG辺で表現し ，間接的なエイリアス関係は AFG 上での到達可能性を調べることで得るようにしている．従っ加えて，到達節点 C の種類に応じて以下のような処理も行う[Cond.1] 親節点を持つ標準（ インスタンス属性）節点:
[Cond.8] '' 演算子を持つ AFG 標準節点（ x = ' 1 (C ) ）:（ 1 ） X := '(x)（ 2 ） f'(y ) j '(&y ) 2 Xg から AFG 辺をたど る
f'(y) j '(y) 2 Xg から AFG 辺をたど る[Cond.9] '&' 演算子を持つ AFG 標準節点
（ &x = ' 1 (C ) ）:（ 1 ） X := '(x)（ 2 ） f'(y ) j '(y ) 2 Xg から AFG 辺をたど る
f'(&y) j '(y) 2 Xg から AFG 辺をたど る

図 13 エイリアス計算アルゴ リズム（ポインタ）
Fig. 13 Alias computation algorithm(for pointers)

char *x) にそれぞれ用意されている．また，b，*y に関するエ イリアス情報を呼び 出し 先に反映するため，

AA-out，FA-out 節点がそれぞれ追加されている．
| Phase 4: エイリアス計算
ポインタに関する演算子としては，間接演算子'' お
よびアドレス演算子'&' がある．x は x が指す記憶領域の内容を，&x は x の記憶領域の位置を表す．エイ
リアス計算アルゴ リズムをこれらの演算子に対応させるため，図 5 の Step 2 を拡張する．詳細は，図 13 に
示す．
5. 3

には ，外部変数すべての組み合わせを想定する必要はなく，直接的なエ イリアス関係を満たす節点間にAFG 辺を引くだけでよい．モジュールにまたが る解析（ Phase 4 ）の時，外部変数間のエ イリアス関係は到達可能な AFG として与えられる．モジュール内解析ではエイリアスとして導出されなかった 2 つの式が（ 外部からの影響により ）間接的なエ イリアス関係を満たすかど うかは，与えられた外部からの AFG を経
由することで到達可能となるかを調べればよい．
また，[10] は手続き型言語に関してのみ論じられて
おり，オブジェクト指向言語特有の問題，例えば本稿で扱うオブジェクトコンテキストなどは考慮されていない．[15] は参照変数への代入により発生するエイリ
アスを求める方法を提案しており，ポインタ変数によるエイリアスには触れられていない．また，いずれの研究もプロトタイプ実装を行っただけで，実用的なシステム構築には至っていない．
一方，今回我々は FI オブジェクトコンテキストを採用しており，メソッド の呼び出し順を考慮している
上記 2 手法と比較して解析精度が低下する場合がある．
精度とコストはトレード オフの関係にあるため一概に手法の優越を判断することは難しいが，今後 FS オブ
ジェクトコンテキストも加えた相互比較を行いたいと考えている．

関連研究

エイリアス解析のモジュール化に関する研究としては [10], [15] がある．前もってモジュール内のエイリア

6.

まとめと今後の課題

ス解析を行う点で我々と同じであるがその計算の手間本研究では，オブジェクト指向言語に対する，再利は大きくなる．これらの手法では各文の到達エイリア

用性，モジュール性を考慮したエイリアスフローグラ

ス集合の要素をエイリアス関係の成り立つ組 f( , ),( , Æ )g で表現している．これは， , がエイリアス
関係を満たすならば ，( , Æ ) がエイリアスとして導出

フによるエイリアス解析手法 の提案を行った．また，提案手法をJava エイリアス解析ツールとして実装を行い，その有効性を検証した．今後の課題としては，
9電子情報通信学会論文誌 'xx/xx Vol. Jxx{X No. xx

既存のエイリアス解析手法とのコストや精度に関する
比較，AFG データベースの構築，例外処理，スレッ
ド への対応などが挙げられる．

謝辞

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

（ 平成年月日受付，月日再受付）文

献[1] Aho, A.V., Sethi, R. and Ullman, J.D., \Compilers :Principles, Techniques, and Tools", Addison-Wesley,
1986.
[2] B. Steensgaard, \Points-to analysis in almost linear time." in 23rd Annual ACM SIGACT-SIGPLAN
Symposium on the Principles of Programming Languages, pp.32-41, 1996.
[3] B. Stroustrup, \The C++ Programming Language(Third edition)," Addison-Wesley, 1997.
[4] G. Booch, \Object-Oriented Design with Application," The Benjamin/Cummings Publishing Company, Inc, 1991.
[5] http://www.ANTLR.org/, \ANTLR Website."[6] http://gtkmm.sourceforge.net/, \Gtk ."[7] J. Gosling, B. Joy, and G. Steele, 村上 雅章 [訳], \TheJava 言語仕様"[8] 片山, 土居, 鳥居 [監訳], \ソフトウェア工学大事典," 朝倉書店.
[9] M. Enami, R. Ghiya, and L. J. Hendren, \Contextsensitive interprocedural points-to analysis in thepresence of function pointers." in SIGPLAN'94 Conference on Programming Language Design and Implementation, pp.242{256, 1994.
[10] M. J. Harrold and G. Rothermel, \Separate Computation of Alias Information for Reuse," in IEEE
Transactions on Software Engineering, Special section of best papers of the 1996 International Symposium on Software Testing and Analysis, vol.22, no.7,
pp.442{460, 1996.
[11] M. Hind, and A. Pioli, \An empirical comparison ofinterprocedural pointer alias analysis," in IBM Research Report #21058, 1997.
[12] M. Shapiro, and S. Horwitz, \Fast and accurate owinsensitive point-to analysis," in 24th Annual ACM
SIGACT-SIGPLAN Symposium on the Principles ofProgramming Languages, 1997.
[13] M. Weiser, \Program slicing," in Proceedings of the
5th International Conference on Software Engineering, pp.439{449, 1981.
[14] P. Tonella, G. Antoniol, R. Fiutem, and E. Merlo,\Flow insensitive C++ pointers and polymorphism
analysis and its application to slicing," in Proceedings of the 19th International Conference on Software
Engineering, pp.433-443, 1997.
[15] R. K. Chatterjee and B. G. Ryder, \Modular Con10

crete Type-Inference for Statically Typed ObjectOriented Programming Languages," Department ofComputer Science, Rutgers University, no.DCS-TR349, 1997.
[16] R. P. Wilson, and M. S. Lam, \EÆcient contextsensitive pointer analysis for C programs," in SIGPLAN'95 Conference on Programming Language Design and Implementation, pp.1{12, 1995.

大畑

文明

平 10 阪大・基礎工・情報中退．平 12 同大大学院修士課程了．現在同大学院博士課程在学中．プログラム構造解析の研究に
従事．

近藤

和弘

平 12 阪大・基礎工・情報卒．現在同大
学院修士課程在学中．プログラム構造解析の研究に従事．

井上克郎 （ 正員）

昭 54 阪大・基礎工・情報卒．昭 59 同大大学院博士課程了．同年同大・基礎工・情報・助手．昭 59〜昭 61 ハワイ大マノア
校・情報工学科・助教授．平 1 阪大・基礎

工・情報・講師．平 3 同学科・助教授．平7 同学科・教授．工博．ソフトウェア工学の研究に従事．

論文／エイリアスフローグラフを用いたオブジェクト指向プログラムのエイリアス解析手法

Fig.1
FI エイリアス解析 と FS エイリアス解析
FI alias analysis and FS alias analysis
Fig.2
オブジェクト指向プログラム（ Java ）Object oriented program(Java)
Fig.3
サンプルプログラム および その AFG
Sample program and its AFG
Fig.4
サンプルプログラム および その MFG
Sample program and its MFG
Fig.5

AFG special node
Table.2
対象プログラム

Target programs
Table.3

エイリアス解析時間（ Phase 1 { 3 ）[ms]Alias analysis time(Phase 1 { 3)[ms]Table.4
エイリアス計算時間（ Phase 4 ）[ms]Alias calculation time(Phase 4)[ms]Table.5
エイリアス集合の要素数

Size of alias set

エイリアス計算アルゴ リズム

Alias calculation algorithm
Fig.6
定義

De nitions
Fig.7
オブジェクトコンテキスト

Object context
Fig.8
文 c = b.result() の c に関するエイリアス（ 網掛部）
Alias set for c at c = b.result()(Masked)
Fig.9
図 8 の文 c = b.result() の b に関するエイリアス（網掛部）

Alias set for b at c = b.result() in Fig.8(Masked)
Fig.10
図 8 の文 c = b.result() の b.result() に関するエイリ
アス（ 網掛部）

Alias set for b.result() at c = b.result() inFig.8(Masked)
Fig.11Java エイリアス解析ツール
Java alias analysis toolFig.12
ポインタ変数を持つ言語（ C ）でのエイリアス解析
Alias analysis for languages with pointer variables
like C
Fig.13
エイリアス計算アルゴ リズム（ポインタ）

Alias computation algorithm(for pointers)
Table.1
特殊節点

11