ポインタ解析アルゴリズム - MIUSE

修士論文
静的単一代入形式を用いた
ポインタ解析アルゴリズム
平成 2
2年 度 修 了
三重大学大学院工学研究科
博士前期課程情報工学専攻
計算機ソフトウェア研究室
田中雄一
三重大学大学院
工学研究科
概要
ポインタ解析は多くのプログラム解析にとって必須であり，その解析情報はプログラムの最適化や
信頼性の向上に役立つ.しかし，プログラムの実行前に行うポインタ解析では，完全な解析情報
を求めることは一般に不可能である.そのため近似的な解析情報を求めるアルゴ、リズムの研究が
さかんに行われ，これまでに計算量と正確さのトレードオフを考慮した様々な近似アルゴリズム
が報告されている.このトレードオフに影響を与える 1つの指針としてフロー依存性がある.フ
ロー依存解析は正確だが実行効率が悪いのに対して，フロー非依存解析は実行効率は良いが正確
さで劣る.
このフロー非依存ポインタ解析の不正確さを改善するために， H
a
s
t
iら (
1
9
9
8
)は静的単一代入
形式 C
S
t
a
t
i
cS
i
n
g
l
eAssignmentFormう以下回A形式)を用いたブロ←非依存ポインタ解析アル
ゴリズムを提案し，その有用性老示した.また， I
そのアルゴリズムがフロー依存ポインタ解析アル
ゴリズムと同等の解析能力を有するか否か Jを未解決問題として提起した. H
ardekopfら (
2
0
0
9
)
は両者の解析能力が同等ではないと予想し， SSA形式と通常のフロー依存解析を組み合わせたア
ルゴリズムを提案した.
本稿ではこの未解決問題について考察し， H
ardekopfらの予想、に反して， 2つのアルゴ、リズムが
同等の解析能力を有することを示すとともに， H
a
s
t
iらのアルゴリズムを改善した新しいアルゴリ
ズムを提案する.
三重大学大学院
工学研究科
目次
ti--
第 1章
はじめに
ポインタ解析
i
唱
L q d q d q d s吐
内
1
.
1
.1 フロー依存性 (
F
l
o
w
s
e
n
s
i
t
i
v
i
t
y
) ...
1
.
1
.2 文脈依存性 (
C
o
n
t
e
x
t
s
e
n
s
i
t
i
v
i
t
y
)
1
.
1
.3 mayポインタ解析， mustポインタ解析.
1
.2 静的単一代入形式 (SSA形式)
1
.3 ポインタ解析と SSA形式の組合せ. .
1
.3
.
1 H
a
s
t
iらのアルゴリズム
GU ￡ U E U 円i
第 2章 準備
2
.
1 対象のプログラミング言語. • • • • • • • • • • •
2
.
2 デリファレンスの置き換え. • • • • .
2
.
3 諸定義.• •
第 3章 未解決問題の証明と提案手法
9
1
1
唱
4vbvhuvhuvhリ
ム
第 4章 提案手法の考察
4
.
1 H
a
s
t
iらの手法との比較
4
.1
.1 同等性. • • • • • • • • • • • • • •
4
.1
.2 解析の効率
tu
titi--11
4
.1
.3 インクリメンタルな手法. • • • • • •
4
.
2 提案手法の拡張.
i
噌 t i - -
a 円i n y Q U Q U
町
凸
可
i
唱 t i - -
第 5章 手続き間解析への拡張
5
.
1 s
u
p
e
r
g
r
a
p
h
.1 関数ポインタ
5
.1
5
.
2 手続き間解析を行う提案手法. • • •
5
.
2
.
1 構文の拡張
U
5
.
2
.
2 s
u
p
e
r
g
r
a
p
hを用いた解析. • •
q
h
a
22
“
ヮ2
qd
第 6章 実験評価
6
.
1 実 装 .• • • • • • •
6
.
2 実験結果と考察.
第 7章
関連研究
26
第 8章
おわりに
27
謝辞
28
三重大学大学院
工学研究科
付 録 B 提案手法のインクリメンタルな手法への変更
付 録 C 再帰呼び出しを含む supergraph
付 録 D supergraphの構築例
1
1
三京大学大学院
工学研究科
9aqaqdqdqu
付録AH
astiらの手法 [HH98]の実行例
81345
参考文献
第 1章 は じ め に
現在ソフトウェアはあらゆる分野で使用され，またその複雑さと規模はますます増大し続けて
いる.そのためソフトウェアの実行効率や信頼性の向上が強く求められ，それらを実現するため
のプログラム解析に関する研究がさかんに行われている.ポインタ解析は多くのプログラム解析
にとって必須であり，その解析情報はプログラムの最適化や信頼性の向上に役立つ.しかし，プ
ログラムの実行前に行うポインタ解析では，完全な解析情報を求めることは一般に不可能である
[
R
a
m
9
4
]
. そのため近似的な解析情報を求めるアルゴ、リズムの研究がさかんに行われ，これまでに
計質量と正確さのトレードオフを考慮した様々な近似アルゴリズムが報告されている [
H
i
n
O
l
]
.こ
のトレードオフに影響を与える 1つの指針としてフロ←依存性がある.一般に，文の実行順序を
考慮するフロー依存解析は文の実行順序を考慮しないフロー非依存解析より正確である.しかし
フロー依存解析はフロー非依存解析と比べて実行効率が悪い.
フロー非依存ポインタ解析の不正確さを改善するために， H
a
s
t
iら [
H
H
9
8
]は静的単一代入形式
(
S
t
a
t
i
cS
i
n
g
l
eAssignmentForm
， 以下 SSA形式)[CFR+91 AHOO].
を用いたフロー非依存ポイン
タ解析アルゴリズムを提案し，その有用性老示した.また， I
そのアルゴリズムがフロー依存ポイン
タ解析アルゴリズムと同等の解析能力を有するか否か」を未解決問題として提起した. Hardekopf
ら[
H
L
0
9
]は両者の解析能力が同等ではないと予想し， SSA形式と通常のフロー依存解析を組み合
わせたアルゴリズムを提案した.
本稿ではこの未解決問題を考察し， Hardekopfらの予想に反して， 2つのアルゴリズムが同等の
解析能力を有することを示すとともに H
a
s
t
iらのアルゴリズム老改善した新しいアルゴ、リズムを
提案する.
ぅ
1
.1 ポインタ解析
ポインタの存在するプログラムを解析するためには，まず最初にプログラムの各点におけるポ
インタ変数の指しうる対象の集合を求めるポインタ解析が行われなければならない.そして，ポ
インタ解析の結果の正確さは，到達定義解析のようなポインタ解析の結果を必要とする解析の正
確さと効率に影響を与える [SH97b，H
P
O
O
]
.
ポインタ解析には動的な解析と静的な解析があり，前者はプログラムの実行中に行うものであ
り，後者はフ。ログ、ラムの実行に先立つて行うものである.特に，後者はプログラムの実行中のオー
バーヘッドが生じないという利点があり，これまでさかんに研究が行われてきた.ポインタ解析
には，その解析の正確さと計算量のトレードオフに影響老与えるいくつかの指針があり，フロー
依存性と文脈依存性によって大きく分類される.
1
.
1
.1 フロー依存性 (Flow-sensitivity)
フロー依存性とはプログラムの文の実行順序を考虐するか否かである.文の実行順序を考慮す
るフロー依存 (
F
l
o
w
s
e
n
s
i
t
i
v
e
)解析は得られる解析情報が正確であるが，実行効率が悪い.一方，
1
三重大学大学院
工学研究科
(
1
)a= &w;
a
l= &wo;
P
l= &
a
l
;
b1=&xo;
i
f
(・
..
)
(
2
)P=&
a
;
(
3
)b= &x;
i
f
(・
・
・
)
(
4
) b=&y;
b
2=&
y
o
;
b
3=ゆ (
b
bl
)
;
2，
P2 = &b
3;
(
5
)P= &b;
(
6
)
図1.2
:図1.1を SSA形式に変換した例
図1.1
:通常のプログラム
文の実行順序を考慮しないフロー非依存 (
F
l
o
w
-i
n
s
e
n
s
i
t
i
v
e
)解析は実行効率は良いが，正確さで劣
る.従来は計算量やメモリ使用量の観点からフロー非依存の手法 [
And94ぅ HH98，HL07aぅ HL07b
う
HBCC99，SH97a，S
t
e
9
6ぅ田中 1
0
]について多く研究されてきたが，近年ではメモリ使用量や計算
量を抑えたフロー依存の手法も提案されている [EGH94，HL09 HBCC99 N
L
0
9
]
.
フロー依存解析は実行される文の順序を考慮するため，文単位で解析結果を求める.従来のフ
ロー依存ポインタ解析はデータフロー解析の枠組みを使用しているが，近年では最適化の手法を導
入することでスケーラピリティを改良した新しいフロー依存ポインタ解析も提案されている [
H
L
0
9
]
.
フロー非依存解析では，実行される文の順序を考慮しないため，プログラム全体で 1つの解析結
果を求める.フロー非依存ポインタ解析には ，i
n
c
l
u
s
i
o
n
b
αs
e
d
[
A
n
d
9
4
]と e
q
u
a
l
i
t
y
b
αs
e
d
[
S
t
e
9
6
]の 2
つの考え方 1がある. i
n
c
l
u
s
i
o
n
b
a
s
e
dポインタ解析はフ。ログ、ラムから制約を作成し，制約グラフを構
築する.ポインタ情報はこのグラフの推移閉包を求めることで得られるため，時間計費量は O
(
η
3
)
である.またこの i
n
c
l
u
s
i
o
n
b
a
s
e
dポインタ解析に対して，解析結果に影響を与えることなしに入
力サイズ nを減らすことで，スケーラピリティを向上させる研究もなされている [HL07b H
L
0
7
a
]
.
n
i
o
n
f
i
n
d
e
q
u
a
l
i
t
y
b
a
s
e
dポインタ解析は型推論を用い，推論規則から変数に割り当てられた型を u
テ、ータ構造を使って統合していく.そのため S
t
e
e
n
s
g
a
a
r
d
[
S
t
e
9
6
]のアルゴリズムは O(n
α
(
η，
n
)
)
2、
で
ある.
図1.1に対するフロー依存ポインタ解析とフロー非依存ポインタ解析の結果を表1.1に示す.こ
こで， p→ aは pが aを指す， p→ a，
bは pが aか bを指すことを表す.フロ←依存ポインタ解
析で得られるポインタ情報はその行番号の直前までに得られているものであり，フロー非依存ポ
インタ解析ではプログラム全体の情報となる.このようにフロー非依存ポインタ解析で得られる
ポインタ情報は，フロー依存ポインタ解析の各行における情報と比べて，不正確であることが分
かる.
ぅ
ヲ
ぅ
1
.
1
.2 文 脈 依 存 性 (Context-sensitivity)
文脈依存牲とは関数呼び出しを個別に扱うか否かである.関数呼び出しを区別して扱う文脈依
存解析は，呼び出す際の引数と返却値の関係を考慮した解析である [
EGH94]. 一方，文脈非依存
1i
n
c
l
u
s
i
o
n
b
a
s
e
dポインタ解析は A
n
d
e
r
s
e
n
s
t
y
l
eポインタ解析， e
q
u
a
l
i
t
y
b
a
s
e
dポインタ解析は S
t
e
e
n
s
g
a
a
r
d
s
t
y
l
e
ポインタ解析とも呼ばれる.
2
a
(
nη
)はアッカーマン関数の逆関数であり，非常にゆっくり増加する関数である(現実的なサイズ nでは定数 4以
下と見なせる).
ヲ
2
三重大学大学院
工学研究科
表1.1
: 図1.1のプログラムに対するポインタ解析の結果
フロー依存ポインタ解析
フロー非依存ポインタ解析
(
2
)
α →ω
(
3
)
α → ω，
p→ α
ポインタ情報 I
(
4
)
α → ω J→ Z P→ α
(
5
)
α → ω b→ {
x，
y
} P→ α
(
6
)
α → ω b→ {
x，
y
}，
p→ b
ぅ
ぅ
う
α→w
b→ {xぅy
}
p→ α
{，
b
}
う
解析は同じ関数の呼び出し式をまとめて扱う，すなわち関連する関数呼び出しのすべての引数の値
S
H
9
7
a，H
L
0
9
]
.
はまとめられ，その結果として得られる返却値がすべての呼び出し元に返される [
1
.
1
.3 mayポインタ解析， mustポインタ解析
ポインタ解析には m仰 と m
ustの 2種類がある. mayポインタ解析はプログラムのある実行中
に生じる結果を求める.一方， mustポインタ解析はプログラムのすべての実行の中に生じる結果
を求める.本稿において，ポインタ解析といえば mayポインタ解析を表す.
1
.2 静的単一代入形式 (
SSA形式)
SSA形式 [CFR+91，AHOO]とは，コンパイラ最適化などに使われる中間表現の lつで以下のよ
うな特徴がある.
1.各変数は l度だけ定義されるように添字が付けられる
i
i
. 1つの変数に対する定義が複数到達する箇所にゆ関数3を挿入する
SSA形式の例として，図1.1を SSA形式に変換したものを図1.2に示す.同じ変数に対して，代
f文の後には変数 bに対す
入文で定義される度に新しい添字が付けられているのが分かる.また i
る定義が複数 (blとb2)到達するので，ゆ関数が挿入されている.
SSA形式はその特徴からプログラムのフローを考慮した形となっている.そのためデータフロー
解析で得ていた情報は添字付き変数によって容易に得ることができる.この点から近年，定数伝
播や共通部分式の除去といったコンパイラの最適化フェーズや，大規模なソフトウェアの解析に
広く用いられるようになっている.
1
.3 ポインタ解析と
SSA形式の組合せ
SSA形式はその特徴から，フロー非依存ポインタ解析の精度を改善させることができる.たと
えば，図1.2に対してフロー非依存ポインタ解析を行った結果は表1.2のようになる.この結果
は図1.1に対するフロー依存ポインタ解析の結果と同等であり，フロー非依存ポインタ解析の結
果を改善したものとなっている.
3制御の流れによって，右辺のどれかの変数を返す仮想的な関数
3
三京大学大学院
工学研究科
表1.2
: 図1.2に対するフロー非依存ポインタ解析の結果
α1一
→
ポインタ情報
I
b
l→ X
o
ぅ
P
l→
(
1
)
(
2
)
(
3
)
(
4
)
(
5
)
(
6
)
Wo
b
2→ y
o，b
3→ {
X
O，
Y
o
}
α1 ぅ P
2→
a=&w;
p= &a;
a =&x;
c= *
p
;
*p= &y;
b
3
a
l= &wO;
P
l= &
a
l
;
a
2= &
x
O
;
C
l= *
P
l
;
*
P
l= &yO;
d
l= a
2
;
d= a
;
(
a
)通常のプログラム
(
b
)SSA形式プログラム
図1.3
: デリファレンスを含むプログラムの SSA形式への変換例
しかし，ポインタ解析と SSA形式は単純には組み合わせられず，いくつかの間題点がある.そ
の問題とは，プログラム中にアドレス演算子 (
&
x
)やデリファレンス (
*
p
)が現れる場合に，うまく
SSA形式に変換できないということである.その例を図1.3に示す.
この図1.3の例では問題点が 2つある.まず図1.3
(
b
)の (
4
)に問題がある.叩 1の値は (
2
)よ
りa
lである.しかし実際には， (
3
)で定義された a
2でなければならない.これは aの添字付きの
変数のアドレス老値として持ったため，その後 (
3
)で aが再定義されたことを反映されていないた
めに起こっている. 2つ目は (
6
)の a
2についてである. (
5
)は実際には aの定義文であるので， a
3
を=の左辺に持つ定義文にする必要がある.したがって (
6
)の aの添字を 3にする必要がある.こ
れはデリファレンス (
*
P
l
)により，プログラム中に aが現れていないため，添字の更新が行われな
いことが原因である.
1
.3
.
1 Hastiらのアルゴリズム
H
a
s
t
iら [HH98]は，このデリファレンスの問題を克服し，フロー非依存ポインタ解析と SSA形
式を組み合わせたアルゴリスムを提案した (Algorithm1
)
. Algorithm1において， CFGは制
御フローグラフ，注釈はデリファレンス (
*
p
)の変数 pがとりうる値の集合，中間形式はデリファ
レンスを注釈を用いて置き換えて得られるプログラムである.デリファレンスの置き換えは，デ
リファレンスの変数 pのとりうる値の集合の要素数によって以下の 2通りがある.
; a =b; とする.
1.変数 pが値&aのみをとるときは叩= b;を
l
l
.
変数 pが値を複数とるときは元の代入文を分岐に置き換え，各分岐先で各要素に対して (
i
)
を行う.たとえば ，P→ α
{ うりのとき，代入文句= x
;は 2つの分岐に置き換えられ，それ
ぞれの分岐に代入文 a = x
; とb = x
;をおく.
2でフロー非依存ポインタ解析を行い，それによって得られる
このアルゴリズムでは，まず 1
ポインタ情報を各デリファレンスに与える.そして 3
8の繰返しでは， 4でプログラム中のデリ
4
三重大学大学院
_[学研究科
A19orithm1H
a
s
t
iら [
H
H
9
8
]のアルゴリズム
Require: 制御フローグラフ CFG
1
: CFGに対してフロー非依存ポインタ解析を行う
2
: CFGの中のデリファレンスに注釈を付ける
3
:r
epeat
4
:
CFGから中間形式 (
1
M
)老作る
5
: 1Mを SSA形式に変換する (
I
M
s
s
a
)
6
: I
M
s
s
aに対してフロー非依存ポインタ解析を行う
7
:
I
M
s
s
aと解析結果を用いて CFGの注釈を更新する
8
:u
n
t
i
l注釈に変化がない
ファレンスを注釈を用いて置き換える.これにより，プログラムにデリファレンスがなくなり図
1
.3(b)のような問題点を生ずることなく SSA形式に変換できる (
5
)
.6
7では， SSA形式に変換
したプログラムに対してフロー非依存ポインタ解析を行い，その解析結果を注釈に反映させる.こ
のとき注釈に変化があれば，この一連の処理を繰り返す.このアルゴリズムが不動点に達したと
き，つまり注釈に変化が生じなくなったとき，その時点で得られているポインタ情報を最終的な
結果とする.またこのアルゴリズムは，不動点に達する前に繰返しを止めることで，解析精度が
低くなるが解析コストを抑えることが可能である. Algorithm1のアルゴ、リズムの実行例を付録
Aに示す.
H
a
s
t
iらは，この最終的な結果が元のプログラムに対するフロー依存ポインタ解析によって得ら
れる結果と等しいかどうか，つまりこの H
a
s
t
iらのアルゴリズム(または H
a
s
t
iらが提案したポイ
ンタ解析手法を用いたあるアルゴリスム)がフロー依存ポインタ解析のアルゴ、リズムと同等の能力
を有するか否かを未解決問題として提起した.
本稿の構成は次のようになっている.第 2章では本稿で使用する語句の定義を示す.第 3章で
は，未解決問題について 2つのアルゴリズムが同等の解析能力を有することを証明するとともに，
その結果として得られる新しい SSA形式を用いたフロー非依存ポインタ解析のアルゴ、リズムを提
案する.第 4章ではその提案手法について考察を行う.第 5章では， 2つのアルゴ、リズムが関数呼
び出しを考慮しでも同等の解析結果をもたらすことを示し，提案手法を手続き間解析に拡張する.
第 6章では，本研究の提案手法と H
a
s
t
iらの手法の評価を行う.第 7章では，関連研究を紹介し，
最後に第 8章で本研究の結論と今後の課題を述べる.なお，付録 A として， H
a
s
t
iらの手法の実
行例，付録 B として， H
a
s
t
iらのインクリメンタルな手法に対応するように変更した提案手法，付
録 Cに，再帰関数に対する s
u
p
e
r
g
r
a
p
hの例，そして付録 D として s
u
p
e
r
g
r
a
p
hを用いた解析の実
行例をそれぞれ示した.
5
三京大学大学院
工学研究科
第 2章 準 備
この章では，本研究で使用する構文規則と定義を示す.
2
.
1 対象のプログラミング言語
対象とするプログラミング言語は i
f文
， w
h
i
l
e文
， c
h
o
i
c
e文 (
2
.
2節)，そして以下の形を持つ代
入文から構成されるものとする 1
n重ポインタ変数
η，重ポインタ変数;
(
2
.
1
)
n重ポインタ変数
&(n-1重ポインタ変数);
(
2
.
2
)
*
(
n+1重ポインタ変数);
(
2
.
3
)
n重ポインタ変数;
(
2.
4
)
η
重ポインタ変数
*(η+1重ポインタ変数)
であるポインタ変数のことである.たとえば int *
*pなら
ば pは 2重ポインタ変数である.またこの*の数を多重度と呼び， pの多重度は 2である.プログ
ラム内の変数の多重度の最大値が m であるとき，そのプログラムを最大多重度 m のプログラムと
いう.
η 重ポインタ変数とは，型の*の数が η
2
.
2 デリファレンスの置き換え
文献 [
H
H
9
8
]で述べられている，デリファレンス(日)を xの値で置き換える処理は，
る値の個数によって次のようになされる.
X のとりう
• xのとりうる値が 1つに定まる場合
置き換えたものは通常の代入文として処理する.
・
xのとりうる値が複数個である場合
それらのうちのどれかをとることを表す c
h
o
i
c
e文を挿入する.挿入した c
h
o
i
c
e文は以下の
ように取り扱う.
h
o
i
c
e文も dとして扱う.
一元の代入文を dとすると，それを置き換えてできた c
- SSA形式に変換されるとき， c
h
o
i
c
e文の後ろにはの関数が挿入される.
&b}であるならば， y = {a，
b};である.
たとえば， y =町;で xのとりうる値の集合が {&a，
h
o
i
c
e文の記法とする.
この例のように{-• .}を含む代入文を本稿での c
1代入文には x = *
*
p
;のような形も存在するが，とれは一時的な変数 (
t
m
p
)を導入することにより， tmp= *
p
;x
*
t
m
p
;のように変形することができる.したがって，このような代入文の形も (
2
.
3
)の代入文の形に変形することが
;のような形も同様に (
2.4)の代入文の形に変形可能である.一般的な C フ。ログ、ラムへの
可能である.代入文*句= p
.
2節で述べる.
適用については 4
=
6
三重大学大学院
工学研究科
2
.
3 諸定義
変数 X の左辺値を &xと書く.これ以降，代入文と等式を混同しやすい箇所では，それらを明確
に区別するために，代入には"="，等式には"三"を用いる.
定義 1 (変数の定義文).ある代入文 dが変数 Z の定義文であるとは，その代入文 dが x =ピ;の形
を持っときであるか，または争 =ε うであり ，pが dの直前で、&xを値として持っときである.
h
o
i
c
e文であるとき，たとえばいうy}=ぜ;のとき， dは変数 xおよび yの定義文と
代入文 dが c
考える.
'が代入文 dに到達可能とは ， d
'から dに至るあるイ長さが
定義 2 (代入文の到達可能).代入文 d
正のj路が存在して，その途中に d
'と同じ変数の定義文が存在しないときである.
代入文の左辺値がその代入文の左辺式の左辺値を去すとする.また同様に，代入文の右辺値が
その代入文の右辺式の右辺値を表すとする.
定義 3(代入文の右辺値).代入文 d:eニピ;の右辺値 r
(
d
)が&
α をとりうるとは，次の (
1
)， (
2
)，
(
3
)のうちのどれか老満たすときである.
'三 &
α
(
1
)e
(
2
)e
'三 Uかつある代入文 d
'が存在して ，&yを d
'の左辺値， &
α を dタの右辺値として持ち ，d
'
が dに到達可能
(
3
)e
'三 かつある代入文 d
'が存在して ，&zを d
'の左辺値， &
υをd
'の右辺値として持ち ，d
'
が dに到達可能かつある代入文 d"が存在して ，&yを d"の左辺値， &
α を d"の右辺値と
して持ち ，d
"が dに到達可能.すなわち，次のような代入文の列が存在する.
d
うう :
g= g
'
;(
l
(
d
")三 &yぅr
(
d
"
)三 &α)
d
' :f=f
'
;(
l
(
d
'
)三&ム r
(
d
'
)三 &
y)
d :ε=*
z
;
定義 4(代入文の左辺値).代入文 d:ε=ε うの左辺値 l
(
d
)が&yをとりうるとは，次の (
1
)，(
2
)の
うちのどれかを満たすときである.
(
1
)
ε
三
u
(
2
) e三勺かつある代入文 d
'が存在して ，&xを d
'の左辺値， &
νをd
'の右辺値として持ち ，d
に到達可能
定義 3，4は c
h
o
i
c
e文を含むプログラムに容易に拡張できる.すなわち， c
h
o
i
c
e文 d:{xy
}=
{a，
b
}
;のときは， d:x=a
;，d:x=b
;，d:y=a
;，d:y=b
;のいずれかが実行されると考える
ことにより，同様に定義可能である.
代入文 dにおける変数 xのとりうる値の集合を次のように定義する.ここで代入文の集合を D，
変数の集合を Varとする.
ぅ
7
三主主大学大学院
工学研究科
定義 5(変数のとりうる値の集合). d d
'εD， x，yεVαTが与えられたとき，代入文 dにおける
変数 zのとりうる値の集合を次のように定義する.
タ
V(dぅ
X
)= {&ν￨ある代入文 d
'が存在して ，d
'が dに到達可能かつ l
(
d
'
)三 &X，r
(
d
'
)三 &ν}
なお， V(dス)は dの実行直前にとりうる xの値の集合である.また変数 xが最大多重度のポイ
ンタ変数であるとき， V(dス)の定義は以下のようになる.
V(dぅ
X
)= {&ν￨ある代入文 d
'
:X= e
'
;が存在して ，d
'が dに到達可能かつ r
(
d
'
)=&ν}
ポインタ解析は各代入文 dεDに対し， dの実行直前における各変数 xの指し先の集合を求める
ものである.したがって，フロー依存ポインタ解析アルゴ、リズムは V(dス)を正しく求めるアルゴ、
リズムであるということができる.
SSA形式上での変数のとりうる値の集合を定義するために，まず通常のプログラムと SSA形式
のプログラムの対応関係，。関数を含む代入文，通常のプログラムにおける到達可能の定義を SSA
形式に適用することで得られる到達可能を定義する.
定義 6(SSA形式の代入文の集合).通常のプログラムの代入文 dモDを SSA形式に変換したも
のを d
s
s
aとする.
s
sα とする.そして，その SSA形式の代入文の集合を D
定義 7(ゆ関数の扱い). i
t関数を右辺に含む代入文均二 i
t(...);の左辺値は&九右辺イ直はゆ関数
の引数の右辺値の集合である.
ι
定義 8(SSA形式における代入文の到達可能). SSA形式において代入文 s
a:X
i= e
;が代入文
に到達可能であるとは
d
，d~sα から dssa 1
こ至るある f
長さが正のj路が存在して，その途中に
α
s
s
&
X
j
(
j
チりを左辺値として持つ代入文が存在しないときである.
定義 6，7，8を用いて ，ds
sα における変数町のとりうる値の集合を以下のように定義する.
定義 9(SSA形式における変数のとりうる値の集合). d
'
s
s
α ED
s
sαが与えられたとき，代入
s
sα，d
文 ds
s
α における変数的のとりうる値の集合を次のように定義する.
V
ss
α(
d
町)= {&ν|
αぅ
s
s
ある代入文 d~sα が存在して ， d~sα が dssa 1こ到達可能かっ
l(d~sα) 三 &Xi ， r(d~sα) 三均}
なお， SSA形式のプログラムにおいては ，Vs
d
α(
s
s
sα?町)弁。となる変数 xの添字 iはたかだか l
つのみ存在する.以降，ゆ関数を右辺に含む代入文をの関数代入文，それ以外在通常の代入文と
呼ぶ.
以上より，未解決問題「フロー依存ポインタ解析と SSA形式上のフロー非依存ポインタ解析が
同等の解析能力を有する」を示すことは，すべての代入文 dεDとすべての変数 zεVαrに対し
て，ある添字 iが存在して ，V(dぅ
X
)=V
ss
α(
d
X
i
)を示すことと等しいといえる.
α，
s
s
8
三重大学大学院
工学研究科
第 3章未解決問題の証明と提案手法
この章では 2
.
1節で定義した構文規則を満たすプログラムについて，フロー依存ポインタ解析と
SSA形式上のフロー非依存ポインタ解析が同等の解析能力を有することを示す.
補題1.最大多重度のポインタ変数への代入文は次の 1
，2の形式を持つ.
1
. n重ポインタ変数 = n重ポインタ変数;
2
. n重ポインタ変数 = &(n-1重ポインタ変数);
証明.最大多重度を n とすると，最大多重度が n十 1のポインタ変数は存在しないので明らか. 口
補題 1から最大多重度の変数はそれより下の多重度の変数の影響を受けないことが分かる.こ
の性質を用いて，最大多重度の変数に対して，両者の解析結果が等しいことを示す.以下では，最
大多重度の変数のみを SSA形式に変換したと考え，その代入文の集合を百ssaとする.
補題 2. d E D，xε 防 r
(
xは最大多重度の変数jとし， dssa E Dssa，均は ds
sα に到達する zの添
字付き変数であるとする.このとき ，V(d
，
x
)= 九sa(dssa ，
勾jが成立する.
，i
iを示す.
証明.次の i
.
iV
(dぅx
):
2Vssα (
dssα
，
X
i
)
dssα ，X
i
)とする.このとき，ある η+1個の最大多重度の変数 z
f
)，z
f
)，
・1
&yεVssα (
三均と代入文
句;が存在して，次の条件 (
1
)，(
2
)，(
3
)を満たす
d
4
4
=
4
)
(
1
)e
o=
=&y
(
2
)匂 主 z
j:J)oret=ゆ
(
ぅ
z
j
:
J
)
う
)
，
1壬i壬n
(
3
) diは di十1に到達可能，1
:
:
:
;i三n+1
(ただし ，d
α
)
1三 d
n+
s
s
これを図示すると次のようになる.
do :北)_匂;
dl:dJ)=41);ord)=ゆ(点)?);
dn
:
タ)=4:ゴ
);ord=φ(
ぅ
4ロ)ぅ);
ds
sα
この代入文の列において，各 di(
0:
:
;i三 n
)の右辺値は &yを含む.元のプログラムにおい
て，ゆ関数代入文 d
k:zf)=ゆ( zjU)
;に対応するフ。ログラムの位置に代入文 d
k
:
z=
z
;を挿入する.代入文 d
k
:
z= z
;を挿入しても，元のプログラムと同じ計賓が行われることか
i
(
O:
:
;i三n
)の右辺値として &yを含む.すなわち &yξV(dス)が成立する.
ら，各代入文 d
ぅ
う
)
9
三重大学大学院
工学研究科
&a;
x= &a;
y=&b;
X
i
f
(・
・
・
)
P
l= &X;
i
f
(
・
・)
*p= &
c
;
e
l
s
e
*
P
l= &
C
;
e
l
s
e
P= &X;
i
f
(・
・
・
)
x= &
C
;
e
l
s
e
p= &y;
P2= &y;
P= &y;
*
p
;
P
l，
P
2
)
;
P3=ゆ (
z= *
P
3
;
x= &a;
y=&b;
p=&x;
Z
二
(
a
)通常のブログラ
二
y=&b;
(
b
)最大多重度の変
数
J
i
:SSA形式に変換
ム
x= &a;
y= &b;
i
f
(・
・
)
x= &
C
;
z= {
X，
y
}
;
z= {X，
y
}
;
(
c
)デリファレン
スを置き換えた
プログラム
(
d
)(
c
)から最大
多重度の文を除去
したプログラム
図3
.
1
:デリファレンスの置き換え
i
i
. V(d，
x
)cVssα (
ds
i
)
sα ぅ X
&yεV(dぅx
)とすると， V(d，
x
)の定義より dに到達可能なある代入文ぽ :e=ぜ;が存在して，
l
(
dう
)=
=&x，r(dう
)=
=&yを満たす. xは最大多重度の変数であることから， e= xが成立す
'老 SSA形式に変換した ds
'
s
sα について， dう
s
s
α とd
る. dと d
sα と d
s
sα の聞には複数個の Xj
=ゆ(・ー);の形のの関数代入文が存在する.これらのゆ関数代入文はすべて定義 7より右辺
値に &yを含む.したがって， &yEV
s
s
a
(
d
s
sα ぅ X
i
)である.
口
元のプログラムを P，最大多重度の変数のデリファレンスを補題 2で得られる結果を用いて置き
換えたプログラムを Pうとする.プログラム Pうに対する定義 5の関数 V を V'，代入文の集合を D'
と書くことにする.また代入文 dうε Dう
は P における代入文 dと対応している.デリファレンス
の置き換えによるプログラムの変化の例を図 3
.
1に示す .Pを図 3
.
1
(
a
)とすると，最大多重度の
) を置き換えたプログラム pうは図 3
.
1
(
c
)から pの定義文を取り除いたプロ
変数(ここでは変数 P
.
1
(
d
)となる.また pうは最大多重度の変数 pの定義文を消去したものであるので，最
グラム図 3
大多重度1を最大多重度としたプログラムと考えることができる.新しい最大多重度は補題 1が
成立する.
この P と Pうにおける代入文の到達可能について，次の補題が成立する.
補題 3
. 最大多重度 -1の変数 zの定義文 d
oε Dに対して ，d
oが dED に到達可能であるなら
ば，P' の対応する代入文 d~ E D'は P
'において d
'εD'に到達可能である.逆もまた成立する.
，iを示す.
証明.次の i
i
.d
oが dに到達可能=今 d
oう
は dうに到達可能
定義より d
oと dの聞に変数 xの定義文が存在しない.そして定義文の定義より，その間に
;の左辺のデリファレンス (
*
p
)は&x以外の値になっている.したがって，
ある代入文 *p=e
デリファレンスの置き換え後のプログラム Pうにおける代入文 do
'も dうに到達可能である.
1
0
三重大学大学院
工学研究科
i
i
. dOう
が dうに到達可能=今 dOは dに到達可能
dOが dに到達可能でないとする.そのとき dOから dヘ至るすべての路に xの定義文が存在
が dうに到達可能であることに矛盾する. したがって ，dOう
がd
する.このことは dOう
'に到達
可能であれば， dOは dに到達可能である.
口
最大多重度 -1の変数について，次の補題が成立する.
4
.dεD，xεVαr(x:最大多重度 -1の変数)， d
'εD
'であるとする.このとき ， V
(
d
，
x
)
=V
'
(
d
'
，
x
)である.
補題
証明.最大多重度 -1の変数について，次の i
，i
iを示す.
i
. V(dス
)cV (
d
'，
x
)
(
l
)は最大多重度
p
(
O
)，p
う
1の変数， q
(
O
)，q(1)は最大多重度の変数であるとし， size(&yE
V(dぅx
)
)を代入文 dの直前で，変数 X に&yを代入するために実際に行われた代入文の回数
i
z
eに関する帰納法で証明する.
とする.この s
&yE V(dス)とするとき，すなわちある代入文 d
O
:eニザ;のとき， d
Oが dに到達可能かっ
l
(dO)三&九 r(do)三 &yである.このとき e三 x または e三 河 (0)の場合とぜ三 &yまたは
ぜ三 p
(
l
) またはぜ三 *q(1)の場合がある.
(
a
)s
i
z
e=1，すなわち e三 xかつぜ三 &yのとき，定義より代入文 dO:x=&y;が存在
が dうに到達可能
し
， dOが dに到達可能である.このとき補題 3より Pうにおいても dOう
である.よって &yεVう
(
d
'，
x
)である.
(
b
)s
i
z
e=たのとき成り立っと仮定し， s
i
z
e= k+1を証明する.次の 4つの場合に分けて
考える.
(
1
) e三 *
q
(
O
)かつぜ三 &y，すなわち dO:*
q
(
O
)= &yうのとき， &xEV(do，
q
(
O
)
)が成
う
が dうに到達
立する.帰納法の仮定より， &xεVう
(
d
o
'，
q
(
O
)
)，そして補題 3より dO
可能なので &yεVう
(
d
'，
x
)が成り立つ.
(
2
) e三 x か つ ぜ 三 p
(
l
)，すなわち dO:x = p(1);のとき， &yεV(d
(
l
)
)が成立す
oぅp
う
が dうに到達可
る.帰納法の仮定より， &yεVう
(
d
O
'，
p
(
l
)
)，そして補題 3より， dO
(
d
'，
x
)である.
能なので &yεVう
(
3
) e三 x かつぜ三 *q(
1
)，すなわち d
O
:x= *
q
(
l
)
;のとき， &zεV(dO，
q
(
l
)
)かつ &y
εV(doぅz
)が成立する.帰納法の仮定より， &zεVう
(
do'
，
q(
1
)
)
， &yεVヲ(
d
o
'，
z
)が
いえる.そして dOが dに到達可能であるため，補題 3より， &yEVう
(
dうバ)が成立
する.
(
4
) e三 *
q
(
O
) かつ eう
さ p
(
l
)，すなわち d
O
:*
q
(
O
)= p
(
l
)
;のとき， &xεV(do，
q
(
O
)
)
う
かつ &yεV(do，
p(1))が成立する.帰納法の仮定より， &xE Vう
(
do，
q
(
O
)
)，&yE
Vう
(
d
O
'，
p
(
l
)
)がいえる.そして dOが dに到達可能であるので，&yεVう
(
d
'，
x
)が成
立する.
よって， V(dス)三 Vう
(
d
'，
x
)が成立する.
i
i
. V(dス
):
2V'(d'，
x
)
p
(
O
)，p
(
l
)は最大多重度一 1の変数， q
(
O
)，q(1)は最大多重度の変数であるとし， size(&yε
1
1
三重大学大学院
工学研究科
Vう
(
d
'，
x
)
)を代入文 dうの直前で，変数 X に&yを代入するために実際に行われた代入文の回数
とする. (
i
)と同様に，この s
i
z
eに閣する帰納法で証明する.
&yεV'(d'，
x
)とするとき，定義よりある代入文 d
Oうe=ぜ;が存在して， d
Oう
が dうに到達可
う
)
三 &x，r
能かつ l
(
do
(
d
ザ)三 &yである.このとき eについて， e三 x，e三{-•，'x，
.
.
.
}
の
場合があり，またぜについて， e
'三 &y，e
う
三p
(
l
)，ぜ三{-..
， p(
1
)，...}の場合がある.
(
a
)s
i
z
e= 1
(
1
) e=xか つ ぜ =&yのとき，すなわち代入文 d
o:
うx= &
y;のとき， d
oう
が dうに到
うに対応する代入文 doが dに到達可能であることが
達可能である.補題 3より do
いえる .&yεV(dス)である.
(
2
) e三{..'
， x，...}かつぜ三 &y，すなわち d
o:
う{
.，'x，
.
.
.
}= &
y;のとき，代入文 do
:
う
が dう
*
q
(
O
)= &y;である. 補題 2より， &xεV(do，
q
(
O
)
)が成立する.そして do
に到達可能であるから，補題 3より d
oが dに到達可能である.よって &yεV(dス)
が成り立つ.
(
b
)s
i
z
e= kのとき成り立っと仮定し， s
i
z
e= k十 1を証明する.次の 3つの場合に分けて
考える.
(
1
) e三 X かつぜ三 p
(
l
)，すなわち d
o
'
:x= p
(
l
)
;のとき， &yεV'(do'，
p(1))が成立す
る.帰納法の仮定より， &yE V(do♂ (
1
)
)，そして d
oう
が dうに到達可能であるから，
d
oが dに到達可能なので、 &yEV(dx
)が成り立つ.またこのとき d
o
:x= *
q
(
l
)
;の
場合があるが，補題 2より V(d
，
q
(
l
)
)
=
{
&
p
(1)}がいえるため成立する.
O
う
:x= {
(
2
) e三 xかつぜ三{...
，p
(
l
)，
.
..}，すなわち do
・ 1p(IL--};のとき， &yε
Vう
(
d
O
'，
p
(
l
)
)が成立する.ぜが c
h
o
i
c
e文なので，代入文 d
oは x=*q(1);であり，補
，
q(1))である.また帰納法の仮定より， &yEV(do
1
)
)，そ
題 2より &p(l)εV(do
♂(
oう
がd
'に到達可能であるから， d
oが dに到達可能なので， &yεV(d，
x
)が
して d
ぅ
成り立つ.
(
3
) e三{..，'x，...}かつぜ三 p
(
l
)，すなわち d
o:
う{
.
.，'Xγ ・
・
}= p(1);のとき， &yE
Vう
(
d
'
，
p(1))が成立する.また代入文 do
:*
q
(
O
)=p(1);と補題 2より， &xεV(do，
q
(
O
)
)
o
う
が成立する.帰納法の仮定 (&yεVう
(
d
'
，
p(
1
)
)
)
よ
り
， &yεV(do
，
p(1))，そして do
o
が dうに到達可能であるから ，d
oが dに到達可能なので &yεV(d，
x
)が成り立つ.
(
d
'，
x
)
.
よって V(dス)三 Vう
以上より， V(dス)= V
う
(
d
'，
x
)である.
口
系 l
. dεD，xεVαr
(
x
:最大多重度 -1以下の変数)， d
'εD
'は P'において dに対応する代入
文であるとする.このとき ， V
(d
，
x
)=V
'
(
d
'
，
りである.
証明.補題 4より最大多重度 -1の変数に対して，各変数がとりうる値が等しいことが言える.ま
た最大多重度 -1を新しく最大多重度と考えると，補題 4を用いることで， 1つ下の多重度につい
ても同じ集合を得ることができる.したがって，元の最大多重度 -2の変数に対しても V(dス)=
Vう
(
d
ううx
)がいえる.以上のことを繰り返し用いることで，最大多重度1以下のすべての変数に対
x
)= Vう
(
d
'，
x
)がいえる.
口
して， V(d，
補題 1，2，系 1を考慮した SSA形式上のフロー非依存解析アルゴリズムを Algorithm2に示
す.このアルゴ、リズムの基礎となる考えは最大多重度の変数はそれより下の多重度の変数の影響
を受けないということである.
1
2
三重大学大学院
工学研究科
A19orithm2提案手法
Require:制御フローグラフ CFG
f
o
rn =最大多重度 t
o1do
CFGの n重ポインタ変数老 SSA形式に変換する (SSA
)
n
SSAnに対してフロー非依存ポインタ解析を行う
SSAnの n重ポインタ変数のデリファレンスを解析結果を用いて置き換える
endf
o
r
多重度
フロー依存ポインタ解析
SSA形式+フロー非依存ポインタ解析
補題 2
max
Vssα
V
系l
補題 2
1
Vう
max1
・
系l
max-2
1
Vう
s
sα
補題 2
V"
系l
s
sα
Vう
1
図3
.
2
:定理 1の証明の概略
このアルゴリズムを用いて，以下の定理を示す.
定理1. 2
.
1節で定義した構文規則を満たすプログラムにおいて ， v
を求めるフロー依存ポインタ
解析と Algorithm2のアルゴリズムの結果は等しい.
.
2に証明の概略を示す.
証明.最大多重度 η に関する帰納法で証明を行う.また図 3
.
i n= 1のとき補題 2より多重度 1の変数 X について， V(dス
)= V (
d
回品)である.
s
制
i
i
. n =kのとき成り立つとし ，n =k+1を考える.多重度 k+1の変数 xに対して補題 2よ
x
)= V
s
s
a
(
d
s
s
a，
X
i
)である.また補題 4より，多重度 kの変数どについて V(dう
ど
)=
りV(d，
Vう
(
d
'，
xう)であり，仮定から最大多重度が kの場合は成り立つ.以上より最大多重度が k+1
のときも成り立つ.
したがって，すべての多重度の変数に対して， V(dx
)= V (
d
部加 X
i
)がいえる.
ぅ
制
口
提案手法と H
a
s
t
iらの手法の解析能力が等しいことは第 4章で述べる.したがって，この同等
性より次の定理老得る.
定理 2
.H
a
s
t
iらのアルゴリズムおよび提案手法がフロー依存ポインタ解析と同等の解析能力を有
する.
定理 1
，2より，本稿において H
a
s
t
iらの提起した未解決問題老 2
.
1節で定義した構文規則を満
たすプログラムに対して解決した.
1
3
三重大学大学院
工学研究科
第 4章 提 案 手 法 の 考 察
この章では，第 3章で示した提案手法について述べ，次に1.3節で説明した H
a
s
t
iらの手法との
比較を行う.そして最後に本手法を 2
.
1節の構文規則の範囲に入らないような構文要素を含む一般
的なプログラムに対して，どのように適用するかを示す.
提案手法は多重度の概念を用いて，最大多重度の変数から順に SSA形式への変換，フロー非依
存ポインタ解析，デリファレンスの置き換えを行う (Algorithm2
)
. また定理 1より，その解析
結果はフロー依存ポインタ解析と同等のものとなる.提案手法の実行例を図 4
.
1に，得られるポ
インタ情報を表 4
.
1に示す.フロー依存解析で得られる情報はその文の直前までに得られるもの
である.
(
1
)
(
2
)
(
3
)
a= 0
;
b= 1
;
p= &a;
q= &b;
t= &p;
a= 0
;
b= 1
;
p= &a;
q= &b;
t
l= &p;
a= 0
;
b= 1
;
p= &a;
q=&b;
h = &p;
a= 0
;
b= 1
;
P
l= &
a
;
q
l= &b;
h = &p;
a= 0
;
b= 1
;
P
l= &a;
q
l= &b;
t
l= &p;
i
f
(・
・
・
)
i
f
(・
・
・
)
i
f
(・
・
・
)
i
f
(・
・
)
i
f
(・
・
・
)
*
t= &b;
(
4
) *p= 2
;
t= &q;
*
t
l= &b;
*p= 2
;
t
2= &q;
p=&b;
*p= 2
;
t
2= &q;
P
2= &b;
P
2= &b;
)
;
3=φ(p2，
pl
P
3=ゆ (
P
2，
P
l
)
; P
*P3=2;
{
a，
b}= 2
;
t
2= &q;
t
2= &q;
(
5
)
(
a
)
(
b
)
(
c
)
(
d
)
(
e
)
図4
.
1
:提案手法の実行例
表4
.
1
:図 4
.
1のプログラムに対する各ポインタ解析の結果
フロー依存ポインタ解析
SSA形式+フロー非依存ポインタ解析
(
1
)P→ α
(
2
)P→ α q→ b
2→ q
t
l→ P t
(
3
)P→ α ，
q→ b t→ p
P
l→ α P
2→ b P3→ α
{ b
}
(
4
)P→ α
{，
b
}，
q→ b t→ p ql→ b
(
5
)P→ α
{，
b
}，
q→ b t→ q
う
ポインタ情報
ぅ
う
ぅ
う
う
う
う
図4
.
1
(
a
)の最大多重度の変数は tであるため，まず tを SSA形式に変換する(図 4
.
1
(
b
)
)
.次
1
4
三噴大学大学院
工学研究科
に図 4
.
1
(
b
)の最大多重度の変数に対してフロー非依存ポインタ解析を行う.そして解析結果の tl
→ p， 七2→ qを用いて *tlを指し先 pで置き換える(図 4
.
1
(
c
)
)
. これで最大多重度に関する処理
が終了する.同様のことを最大多重度 -1の変数に対して行う(図 4
.
1
(d
)，図 4
.
1
(e
)
)
.図4
.
1
(
e
)
の代入文 {a，
b} = 2
;が c
h
o
i
c
e文である.
4
.
1 Hastiらの手法との比較
4
.1
.1 同等性
提案手法と H
a
s
t
iらの手法の同等性については，次に述べる性質より容易に証明可能である.最
大多重度はそれ以下の多重度の変数の影響を受けないため，すべての変数に対して繰り返し解析
を行う H
a
s
t
iらの手法と，最大多重度の変数のみを解析する提案手法は最大多重度の変数に対し
て等しい解析結呆を得る.これは， H
a
s
t
iらの手法では無駄な計算をしているが，最大多重度の変
数に対しては無害であること老示している.このことを最大多重度 1
，最大多重度 -2，・・・と順
に考えることで同等性がいえる.
4
.1
.2 解析の効率
H
a
s
t
iらのアルゴリズム [
H
H
9
8
]と本研究の提案手法 (AIgorithm2
)の実行効率を比較する.
H
a
s
t
iらのアルゴリズムは多重度を考慮していないため，プログラム全体を不動点に到達するまで
繰り返し解析を行っている.つまり各繰返しの中でゆ関数の挿入と変数の名前付けをすべての変
数に対して行っている.一方，提案手法では多重度を考慮したアルゴリズムとなっており，その
結果各変数について l度だけゆ関数の挿入と名前付けを行えばよい.その点から無駄な計算を除
いた提案手法は H
a
s
t
iらの手法より実行効率の良いものとなっている.なお，本研究の結果より
H
a
s
t
iらのアルゴリズムは，最悪の場合，最大多重度 +1回の繰返しで不動点を求められることが
わかっている.
4
.1
.3 インクリメンタルな手法
H
a
s
t
iらの手法はインクリメンタルな手法，すなわち繰返しを途中で止めることで，解析精度は
低くなるが，解析コストを抑えることが可能である.本手法はその点で異なり，すべての変数を
解析するまで繰返しを止めることはできない.しかし，次に示すように同等の結果を得られるア
ルゴリズムは本手法を用いても実現可能である.
H
a
s
t
iらの手法を k回繰り返したときに得られる結果の説明のために，次の定義を必要とする.
α を与える
定義 10(極大なポインタ変数).多重度 nのポインタ変数 zが極大であるとは， xfこ&
代入文の列 1があり，それらの代入文の両辺に多重度 n+1以上のポインタ変数が出現しないとき
である.
H
a
s
t
iらの手法をた回繰り返して得られる結果のうち，フロー依存ポインタ解析と同等の結果と
なる変数は次のものとなる.
・極大なポインタ変数
たとえば， z=&aiY =zぅ X
1
=Yiのような代入文の列である.
1
5
三重大学大学院
工学研究科
s
t
r
町 tS
{
i
n
t;
i
i
n
tj
;
}
;
(乱)構造体
s
t
r
u
c
tSs
，t *
p
; s
t
r
u
c
tSs
，t
，*
p
;
;
i
n
ts
_
i
う
えj
ヲ
t
_
i
う
t
_
j
う*p
う
i
_ *
p
_
j
;
s=t
p= &
s
;
s
_
i= t
_
i
;
s
_
j=L
j
;
i
;
p
_
i=&s_
p
_
j= &
s
_
j
;
う
(
b
)プログラム
(
c
)変換例
図4
.
2
:構造体型変数の基本型の変数への置き換え例
-繰返しによって新たに得られる極大なポインタ変数
(n
これは多重度 n
mω -k <n 三 叫nax)の変数を含む.これ以外の変数についてはフロー依存ポ
インタ解析の結果と同等であることは保証されない.すなわち，フロー依存ポインタ解析を部分
的に行い，かつフロー非依存ポインタ解析を行った近似的な値となる.以上のことを考慮するこ
とにより，本手法を用いた同等の解析手法が得られる(付録 B参照).
4
.
2 提案手法の拡張
本手法は， C言語で記述された一般的なプログラムのポインタに関係する文を抜き出して，そ
れが本稿で定義した構文規則を満たしていれば適用することができる.また構文規則を満たして
いない場合でも，料xを含むような代入文においては一時変数を導入すれば，規則を満たす代入文
に変形することが可能である.さらに本稿で定義した構文規則の範囲内には入らない構成要素に
関しては，次のように扱うことで適用できる.
-配列
配列の要素への参照はその配列全体への参照として扱う.たとえば，配列 aに関係した代入
a
[
i
]
;や p=a
+
i
;老単に代入文 p=&a;と近似することによって解析司能になる.
文 p=&
・構造体，共用体
構造体名ーメンバ名で lつの変数と見なすことで対応できる.構造体のコピー文はそれぞれ
に対応するメンバの代入文として扱う.例を図 4.2に示す.ただし，構造体のメンバに構造
体へのポインタを含む場合に，同様の変換を行うためには，さらなる解析を必要とする.共
用体についても同様に扱う.
m
a
l
l
o
cなど)
・動的メモリ確保 (
m
a
l
l
o
c
(・
…
);のような代入文は，動的メモリ確保関数を変数として考え，そのアドレス
を xに代入する文であるとする.これらの関数は呼び出しごとに異なる変数であるとする.
繰返し中は同ーの変数を表すとする.
X
二
関数呼び出しについては第 5章で述べる.このように構文要素を扱うことで，本稿で定義した構
文規則に基づいた本手法を一般的なプログラムに適用できる.
1
6
三重大学大学院
工学研究科
第 5章手続き間解析への拡張
第 3章で証明した未解決問題は手続き内解析，つまり関数呼び出しの無いプログラムに対する
ものであった.この章では，本稿で定義した構文規則に関数呼び出しを加えたとしても，フロー依
存ポインタ解析と SSA形式を用いたフロー非依存ポインタ解析の結果が等しいことを示す.まず，
手続き間解析の実現方法の 1つである s
u
p
e
r
g
r
a
p
hについて説明する.次に. s
u
p
e
r
g
r
a
p
hを用いた
手続き間フロー依存ポインタ解析アルゴリズムを示し，そのアルゴリズムと SSA形式を用いたフ
ロー非依存ポインタ解析の解析結果が等しいことを証明する.そして，提案手法 (Algorithm2
)
を関数呼び出しを考慮したアルゴ、リズムに拡張する.
5
.
1 supergraph
手続き間解析では，呼び出される関数に，実引数とグ、ローバル変数，そしてそれらの変数から
参照可能な変数の値が渡される.そして，その値を用いて関数内を解析した結果が呼び出しもと
に返される .supergraphとは各関数に対する制御フローグラフに次のようなノードと辺を加える
ことで，関数聞をつないだフローグラフである [ALSU07ぅ HH98，LR91，Mye81j
1
.
・各呼び出し点(関数呼び出しの文)に対して c
a
l
lノードと returnノードを作る.
• c
a
l
lノードに入る辺は呼び出し点に入る辺であり. r
e
t
u
r
nノードから出る辺は呼び出し点か
ら出る辺である.
a
l
lノードから呼び出される関数の e
n
t
r
yノードへの辺と，呼び出される関数の e
x
i
tノード
・c
e
t
u
r
nノードへの辺を追加する.
から r
さらに，引数がある場合は，仮引数に実引数の値を代入するための文をまとめた新しいノードを
c
a
l
lノードと e
n
t
r
yノードの聞に加え，もし x= f
(・・・);であれば，返却値を受け取る変数 X への代
入文を持つ新しいノードを e
x
i
tノードと r
e
t
u
r
nノードの聞に加える.これにより，引数の値の伝
u
p
e
r
g
r
a
p
hは 1つの制御フローグラフと見なせるので. s
u
p
e
r
g
r
a
p
hに対し
播が実現される.この s
u
p
e
r
g
r
a
p
hの例を図 5
.
1に示す.
て手続き内解析を行うことで，手続き間解析の結果を得られる. s
s
u
p
e
r
g
r
a
p
hを用いた場合の文脈依存性老考えたとき，図 5
.
1
(
b
)のように単純に関数聞に辺を
追加した場合は，呼び出される関数への各入力がまとめられ，その出力がすべての呼び出し点に
戻されることになるので，文脈非依存の手続き間解析となる. s
u
p
e
r
g
r
a
p
hで文脈依存解析を実現
する方法の 1つとしては，関数の複製がある(図 5
.
1
(
c
)
)
. すなわち，関数 fを呼び出す各点から
関数 fの制御フローグ、ラフヘ辺をつなぐのではなく，各呼び出し点に対して関数 fの制御フローグ
ラフを複製し，その複製に対して辺の追加を行う.こうすることで，呼び出し点と関数が 1対 1に
対応するので，呼び出しを区別した文脈依存の解析が行える.ただし再帰がある場合には，複製
が無限に行われるので，この方法を用いることができない.再帰を構成する関数に対しては複製
を行わず，従来の方法で呼び出し 点と呼び出される関数を結ぶ.そして再帰に関する結果は一般
J
1L
andiら
[
L
R
9
1
]は，i
n
t
e
r
p
r
o
c
e
d
u
r
a
lc
o
n
t
r
o
lf
i
o
wgraph(ICFG)という言葉を使っている.
17
三重大学大学院
工学研究科
i
(
ρ
1
)
*
n= 1
;
;
r
e
t
u
r
nn
;
i
n
tmai
叫void){
c
;
i
n
t*a *b *
i
n
tx，
y
;
う
う
x=y=2
0
;
a= &x;
b= f
(
a
)
;
(
2
)
c= &y;
b=f
(
c
)
;
(
3
)
r
e
t
u
r
n0
;
}
(
b
)s
u
p
e
r
g
r
a
p
h
(
a
)プログラム
(
c
) 複製を利用した s
u
p
c
r
g
r
a
p
h
図5
.
1
:(
a
)のプログラムに対する supergraph
に不動点を求めることによって得られる [EGH94 ALSUO
可.再帰老含む s
upergraphの例を付録
Cに示す.
ぅ
表5
.
1
:図 5
.
1
(
a
)に対するポインタ解析の結果
文脈非依存(図 5.1(b))
(
1
)n→ {
x，
y
}，a→ x，b→ {xぅy
}う
c→ {NULL，
y
}
ポインタ
情報
(
2
)n→ {
x，
y
} a→ X b→ {
x，
y
}
c→ {NULLy
}
(
3
)n→ {x，
y
}，a→ x，b→ {x，
y
}
c→ {NULL，
y
}
ぅ
う
う
文脈依存(図 5
.
1
(
c
)
)
(
1
) n→ 丸 a→ x
(
1
)
'n→ ぁ a→
(
2
) n→ X a→
ぅ
x，
c→ y
Xぅ b→ x
Xぅ b→
ぅ
ぅ
(
3
) n→ ぁ a→ x，
b→ y C → y
ぅ
図 5.1(a)のプログラムに対して， supergraphを用いた文脈非依存フロー依存ポインタ解析と文
.
1に示す.文脈依存解析において関数 fは区別される
脈依存フロー依存ポインタ解析の結果を表 5
1
)，2回目の呼び出しに対する結果を (
1
)うに示す.ポイ
ので， 1回目の呼び出しに対する結果を (
ンタ変数が指す変数が不定であることを NULLを用いて表す.
1
8
三重大学大学院
工学研究科
.
う・
件
1
﹃︿t
IMFi
剖
1
)
d
)コ I
V
ハ
印刷
司・
ゆ副
， I
d
・
1;
v
o
i
dfO{
、‘.，，ノ
94
(
rJ1t ・ ?
、サハリ
〆
t
ン
中
tFJ
、
LrJ
}fp=g;
rib
、
、
，- ]
EA
lノ
(ー
、
，
f4t.
i
十
P
4
F
、
e
l
s
e
{
jjハリ
、
Jtt
ip
-P +)
i
f
(・・・){
f
p= f
;
v
o
i
dgO{
f
p
O
; ・
・ (
*
)
図5
.
2
:関数ポインタの例
5
.1
.1 関数ポインタ
関数ポインタが存在する場合，関数ポインタのとりうる値が分からなければ， s
u
p
e
r
g
r
a
p
hを構
築することができない.したがって， s
u
p
e
r
g
r
a
p
hを構築するためには，まず関数ポインタに関す
るポインタ解析を行い，それらの値を得る必要がある.
また，グローバルな関数ポインタによって呼び出される関数 fを解析するとき，関数 f内でその
関数ポインタの初期値が fであると考えなければならない [EGH94]. これについて，図 5
.
2を用
いて説明する. (*)で関数ポインタによる関数呼び出しが行われる.この点において，グ、ローパル
変数 fpのポインタ情報は fp→ {
f，
g
}である.イ直 fを用いて関数呼び出しを行うとき，呼び出さ
れる関数 fの中では fpの値は fであり，決して (
1
)の点において，関数 gを呼び出すことはない.
同様に関数 gにおいても関数 fを呼び出すことはない.これは，呼び出す関数に対する引数の代
入文を加えたノードに代入文(この例では， fp = f
;や fp = g
;
)を追加することで， s
u
p
e
r
g
r
a
p
h
上で実現できる.
5
.
2 手続き間解析を行う提案手法
5
.
2
.
1 構文の拡張
関数呼び出しとして，以下の構文を考える.
f
(・・・);
x=f
(
.
..
)
;
fは関数名または関数ポインタであり 2，X は η 重ポインタ変数か *
(
n+1重ポインタ変数)である.
5
.
2
.
2 supergraphを用いた解析
s
u
p
e
r
g
r
a
p
hを用いた手続き間フロー依存ポインタ解析は Algorithm3によって行われる.ま
ず
， 1において通常の関数呼び出しに対して s
u
p
e
r
g
r
a
p
hを構築する.このとき，関数ポインタを用
2C言語ではやを関数ポインタとした場合， f
p
(・
・
・
)
と (
*
f
p
)
(・ー)のどちらでも記述できるので，ここでは区別しな
し¥
1
9
三重大学大学院
工学研究科
A19orithm3sup町 graphを用いたフロー依存ポインタ解析アルゴリズム
1
:s
u
p
e
r
g
r
a
p
hSを構築する
2
:r
epeat
3
: r
epeat
4
:
f
o
ra
l
lsεSの代入文の集合 do
5
:
データフロー方程式を計算する
6
:
endf
o
r
7
:
u
n
t
i
l解析結果に変化がない
8
: 計算された値をもとに Sを更新する
9
:u
n
t
i
lSに変化がない
5で
いた関数呼び出しは，その関数ポインタの値が不定であるのでそのままプログラムに残る. 3
はプログラムの各点での各変数のとりうる値を計算する.そして 6で，関数ポインタを用いた関数
呼び出しに対して，その値に応じて辺を追加し supergraphを更新する.この処理は， supergraph
に更新がなくなるまで繰り返す (
2
7
)
. Algorithm3を適用した例を付録 D に示す.
この supergraphを用いた手続き間解析について，次の定理が成り立つ.
.2
.
1節の構文規則を満たす代入文と 5
.
2
.
1節の関数呼び出しの列からなる関数を考える.こ
補題 5
れらの関数から複製を利用して構築された supergraphは 2
.
1節の構文規則を満たしている.
証明. supergraphは関数呼び出しをその関数の本体で置き換えたものである.また関数ポインタ
f文として見ることができ
の値によって，複数の呼び出し先を持つ可能性があるが，そのときは i
る.よって得られた supergraphは 2
.
1節の構文規則を満たしている.
口
定理 3
.2
.
1節と 5
.
2
.
1節で定義した構文規則を満たすプログラムにおいて， Algorithm 3と
Algorithm3のデータフロー方程式を SSA形式上のフロ←非依存ポインタ解析に置き換えたア
ルゴ、リズムの解析結果は等しい.
証明.定理 2より，データフロー方程式と SSA形式を用いたフロー非依存ポインタ解析の結果は
口
等しくなる.
supergraphを用いた解析において，全ての変数の値を正しく求めるためには， s
u
p
e
r
g
r
a
p
hに更
新が無い状態，つまり関数呼び出しが適切に呼び出し先の関数とつながっている状態である必要
がある.また，関数ポインタについては，その値が通常のポインタ変数の値に依存しないことか
ら，関数ポインタだけを事前に解析することができる.これを考慮したアルゴリズム老手続き間
解析を行う提案手法として， Algorithm4に示す.さらに，このアルゴリズムについて，次の定
理が得られる.
定理 4
.2
.
1節と 5
.
2
.
1節で定義した構文規則を満たすプログラムにおいて， Algorithm 3と
Algorithm4は同等の解析能力を有する.
証明.定理 3より，両者の解析において不動点に達したときに得られている supergraphは等しい.
そして，補題 5と定理 2より，その supergraphに対するそれぞれの解析は等しい解析結果を得る.
したがって， Algorithm3と関数ポインタを事前に解析する Algorithm4は同等の解析能力老
口
有する.
2
0
三重大学大学院
工学研究科
A19orithm4関数呼び出しを考慮したポインタ解析アルゴリズム
Require:制御フローグラフ (CFG)のリスト L
通常の関数呼び出しを考慮した s
u
p
e
r
g
r
a
p
hSを構築する
repeat
Sの中の関数ポインタ変数を SSA形式に変換する (SSAf)
SSA
fに対してフロー非依存ポインタ解析を行う
解析結果を用いて Sを更新する
u
n
t
i
lSに変化がない
f
o
rn= 最大多重度 t
o1do
Sの中の n重ポインタ変数を SSA形式に変換する (SSA
)
n
SSAnに対してフロー非依存ポインタ解析を行う
SSAnのデリファレンスを解析結果を用いて置き換える
endf
o
r
2
1
三重大学大学院
工学研究科
第 6章 実 験 評 価
この章では，本研究の提案手法と H
a
s
t
iらの手法 [
H
H
9
8
]を用いた解析結果を示し， 2つの手法
.
1の 1
0個の Cプログラムを用
の実行効率(解析にかかる時間)について考察を行う.実験には表 6
.
cファイルと .
hファイルを wcコマン
いた.プログラムの行数 (LOC)は(ライブラリ関数を除く )
ドを用いて得られた値で，コメントも含む.代入文は解析対象の代入文の数を示し，多重度 1の
変数に関する代入文の数を多重度 1として表している.
表6
.
1
:ベンチマークの特徴
代入文
a
l
l
r
o
o
t
s
q
u
e
e
n
s
自x
o
u
t
p
u
t
g
e
n
e
t
i
c
anagram
c
o
m
p
r
e
s
s
mway
a
n
s
i
t
a
p
e
c
o
m
p
i
l
e
r
f
o
o
t
b
a
l
l
。
。
。
。
。
。
。
。
。 。
。
。
LOC 多重度 1 多重度 2 多重度 3 関数呼び出し
2
0
5
1
1
37
1
3
1
2
8
3
6
3
4
5
6
7
9
4
4
3
5
0
9
2
8
647
3
9
1
4
4
4
1
0
1
4
9
7
5
1
8
3
9
6
9
0
5
4
1
1
0
1
7
4
4
2
1
5
3
97
G
2
2
3
6
8
4
9
377
2
2
6
1
2
2
5
1
3
2
8
6
.
1 実装
本研究では 4つの手法，すなわち提案手法(手続き内解析 AIgorithm2，手続き間解析 Alg
o
rithm4
)と H
a
s
t
iらの手法(手続き内解析 Algorithm1と手続き間解析 [
H
H
9
8
]
)老実装した.こ
れらの解析は文脈非依存の解析を行う.各手法で用いられるフロー非依存ポインタ解析には [
A
n
d
9
4
]
を，制御フローグラフの支配木を求めるアルゴリズムには [
L
T
7
9
];
を
， SSA形式への変換アルゴ、リ
ズムには [CFR
十9
1
]をそれぞれ用いている.
それらの解析手法の実装は COINS[Pro]内に組み込む形で、行った. COINSは入力プログラムに
H
I
R
)と機械語に近い表現形式の低水準中間表現 (
L
I
R
)を核とし
近い表現形式の高水準中間表現 (
て，それらを扱う様々なモジュールからなっている.本研究では，入力プログラムに近い形式であ
り，かつポインタの型情報などが保持されている HIR上で、実装を行った.つまり， COINSによっ
て生成される HIRの制御フローグラフを解析手法の入力として受け取り，それに対して解析を行
う形となる.
2
2
三重大学大学院
工学研究科
表6
.
2
:各解析手法の解析時間 (
m
s
)
. 比率は "H剖 t
iらの解析時間/提案手法の解析時間"で求めた
ものである.
手続き間
提案手法
a
l
l
r
o
o
t
s
q
u
e
e
n
s
f
i
x
o
u
t
p
u
t
g
e
n
e
t
i
c
anagram
c
o
m
p
r
e
s
s
mway
a
n
s
i
t
a
p
e
c
o
m
p
i
l
e
r
f
o
o
t
b
a
l
l
9
.
6
1
5
.
6
1
3
.
0
3
2
.
2
7
1
.
6
9
5
.
2
9
3
.
8
1
1
7
.
2
4
2
5
0.
2
4
2
.
8
手続き内
H
a
s
t
iら 比率 提案手法
1
7
.
2
1
.7
9
7
.
0
9
.
2
2
0
.
8
1
.3
3
2
3
.
8
1
.8
3
8
.
8
1
.7
1
1
3
.
2
5
5
.
2
1
8
1
.
8 2
.
5
4
6
5
.
0
1
7
3
.
8 1
.8
3
6
4
.
0
.9
2
1
8
0
.
0 1
5
9
.
0
3
5
7
.
8 3
9
9
.
2
.
0
5
5
2
9
.
4 2
9
2
.
2
.
1
1
4
6
1
0
.
2 2
.
5
1
1
7
2.
H
a
s
t
iら
1
2.
4
1
0
.
6
1
4
.
8
3
6.
4
1
5
7
.
6
1
1
7
.
2
1
4
3
.
6
3
1
3
.
2
1
5
9
.
0
2
6
7
.
6
比率
1
.7
7
1
.1
5
1
.6
8
2
.
7
6
42
2.
1
.8
3
2.
4
3
3
.
1
6
1
.7
2
1
.5
5
6
.
2 実験結果と考察
実験結果を表 6
.
2に，その結果を手続き間解析と手続き内解析に分けて図示したものを図 6
.
1と
図6
.
2に示す.手続き間解析の解析時聞は，制御フローグラフのリストを受け取ってから最終的な
u
p
e
r
g
r
a
p
hを前もって構築し，
ポインタ情報を得るまでの時間であり，手続き内解析の解析時間は s
それを入力として受け取ってからポインタ情報を得るまでの時間である.各々の解析時聞は 5回
の平均によるもので，比率は "
H
a
s
t
iらの解析時間/提案手法の解析時間"で計算したものである.
.
2より，手続き間，手続き内のそれぞれの解析において，提案手法は H
a
s
t
iらの手法より解
表6
析時聞が短いことが分かる.よって，提案手法は H
a
s
t
iらの手法と比べて効率的であるといえる.
また，この解析時間の違いには H
a
s
t
iらの手法の繰り返し回数が大きく関係していると考えられ
る.図 6
.
3，図 6
.
4は表 6
.
2の比率と H
a
s
t
iらの手法の繰り返し回数をまとめたものである.これ
らの図を見ると，若干の誤差は見られるが，比率と繰り返し回数のグラフが似た形になっている
ことが分かる.このことは繰り返しの回数だけ，解析時聞が増えていることを表している.実際，
提案手法は"プログラム全体を SSA形式に変換し，ポインタ解析を行うううことを l度だけ行うのに
a
s
t
iらの手法は"プログラム全体を SSA形式に変換し，ポインタ解析を行う"ことを何度
対し， H
も繰り返す.よって，この結果は両者のアルゴリズムの遣いを表していると考えられる.
H
a
s
t
iらの手法の不動点を求めるための繰り返し回数について考える.本研究ではその繰り返し
回数が，最悪の場合，最大多重度 +1になると示した.実験結果を見ると，繰り返し回数は 2か 3
であり，最大多重度 +1に収まっている.しかし，多重度は大きくても 3であり， 1重ポインタ変
数までしか含まないプログラムも多数見られた.よって，少数の実験結果ではあるが，一般的な
プログラムに対する不動点計算の繰り返し回数は，最悪の場合は最大多重度の数 +1となるが，実
際にはそれほど大きくならない (
2，3回程度)と推測できる.ただし，この繰り返し回数は関数ポ
インタを含まないプログラムに対してのものである.関数ポインタがある場合には，さらに回数
が増えると予想される.
以上のことから，提案手法が H
a
s
t
iらの手法と比べて効率的であり，かつ繰り返し回数が解析時
間に大きく影響していることが分かる.
2
3
三重大学大学院
工学研究科
700
600
500
(帥
ε)E世事睦
400
・
-提案手法
300
H
a
s
t
iら
200
.
.
.
・
100
。.
・
ー・
圃
queens
genetic
compress
ansitape
f
o
o
t
b
a
l
l
a
l
l
r
o
o
t
s
行xoutput
anagram
mway
compiler
図 6.
1
:手続き閥解析の解析時間
350
300
250
(
E)E世喜雄
200
﹄
・
-提案手法
H
a
s
t
iら
150
100
50
』
.
・
.
・
・
。
queens
genetic
compress
ansitape
f
o
o
t
b
a
l
l
a
l
l
r
o
o
t
s
自x
output
anagram
mway
compiler
図6
.
2
:手続き内解析の解析時間
24
三重大学大学院
工学研究科
3.
5
3
2
.
5
2
ー比率
1
.
5
申 繰り返し回数
0
.
5
。
queens
g
e
n
e
t
i
c
comp
r
e
s
s
a
n
s
i
t
a
p
e
f
o
o
t
b
a
l
l
a
l
l
r
o
o
t
s
f
i
x
o
u
t
p
u
t
anagram
mway
c
o
m
p
i
l
e
r
図 6.
3
: 手続き間解析における，提案手法に対する H
a
s
t
iらの手法の解析時間の比率と
Hastiらの手法の繰り返し回数
3
.
5
3
2
.
5
2
ー比率
1
.
5
申 繰り返し回数
0
.
5
oqueens
g
e
n
e
t
i
c
compress
a
n
s
i
t
a
p
e
f
o
o
t
b
a
l
l
a
l
l
r
o
o
t
s
f
i
x
o
u
t
p
u
t
anagram
mway
c
o
m
p
i
l
e
r
図 6.4:手続き内解析における，提案手法に対する Hastiらの手法の解析時間の比率と
Hastiらの手法の繰り返し回数
2
5
三重大学大学院
工学研究科
第 7章 関 連 研 究
H
a
s
t
iら [
H
H
9
8
]は本研究の動機となった未解決問題， I
フロー依存ポインタ解析と SSA形式を用
いたフロー非依存ポインタ解析が同等の解析能力老有するか否か」を提起した.本研究はその未
解決問題を考察し，解決した.そして， H
a
s
t
iらの手法のように，全ての変数を繰り返し解析する
J
固に解析を行うことで，実行効率を改善できることを示した.
のではなく，多重度の概念を用いてI
Lapkowskiら [
L
H
9
8
]はポインタを持つ言語に対する SSA形式の問題(本稿でも述べたデリファ
レンスの問題など)について議論している.彼らは各ポインタ変数 pに対して， pの値を表す添
字とうの値を去す添字という 2つの添字を与えることで，問題の解決をはかった.しかし彼らの
εndSSANumberingと呼ばれる方法によって変換されたプログラムは，。関数を持たないた
Ext
め，各変数の使用に対して一意に定義が定まるという SSA形式の性質を満たしていない形式となっ
ている.
Hardekopfら [
H
L
0
9
]は SSA形式とフロー依存ポインタ解析を組み合わせた手法を提案した.彼
o
p
l
e
v
e
l変数(アドレス演算子&を用いてそのアドレスが他の変
らの手法は変数を 2つのクラス ，t
d
r
e
s
s
t
αk
en変数(アドレスが他の変数にわたり，ポインタによって間
数に渡されない変数)と αd
接的に参照される変数)に分類し， t
o
p
l
e
v
e
l変数を SSA形式に変換したあとフロー依存ポインタ
解析を行う. t
o
p
l
e
v
e
l変数は SSA形式なので，それらのポインタ変数の指し先情報はプログラム
全体で 1つのみ保持すればいい.よって各文が保持するポインタ変数の指し先情報を減らすこと
ができ，解析の効率の向上につながる. Hardekopfらの手法は t
o
p
l
e
v
e
l変数に対する結果のみを
グローバルに保持するのに対し，本手法は，繰返しの中で a
d
d
r
e
s
s
t
a
k
e
n変数を t
o
p
l
e
v
e
l変数の
性質を持つように置き換え，最終的に全てのポインタ変数の指し先情報をプログラム全体で 1つ
保持するものである. Hardekopfらは，未解決問題に対して，両者の解析能力が同等ではないと
予想していたが，本研究では予想に反して，同等の解析能力を有することを示した.
田中[田中 1
0
]は i
n
c
l
u
s
i
o
n
b
a
s
e
dポインタ解析における制約グラフの動的推移閉包の問題に対し
て，多重度の概念を導入することで，計算量を抑えたアルゴリズムを提案した.本研究ではその
多重度の概念老 SSA形式に適用した新しいアルゴ、リズムを提案し，従来手法より実行効率の良い
ことを確認した.
2
6
三重大学大学院
工学研究科
第 8章 お わ り に
本稿では，まず H
a
s
t
iら [
H
H
9
8
]が提起した SSA形式を用いたフロー非依存ポインタ解析に関
する未解決問題を，限定的なプログラムにおいて解決した.すなわち本稿で定義した構文規則を
満たすプログラムにおいては， H
a
s
t
iらのアルゴリズムがフロー依存ポインタ解析と同等の解析能
力を有することを示した.次に，構文規則を関数呼び出し，配列などを含むように拡張しでも，同
等の解析能力を有することも確認した.このことから，一般的なプログラムに対して，フロー依
存ポインタ解析と同等の結果を SSA形式を用いたフロー非依存ポインタ解析でも得られると考え
ている.さらに H
a
s
t
iらのアルゴリズムと同等の解析能力を持ち，より実行効率の良い新しいア
ルゴ、リズムを提案し，実験によりその提案手法の有用性老示した.
今後の課題としては，手続き間解析と構造体の扱いについてが挙げられる. s
u
p
e
r
g
r
a
p
h老用い
た手続き間解析を行う提案手法は，確かにフロー依存ポインタ解析と同等の解析能力を持つ.し
かし，複製老利用した s
u
p
e
r
g
r
a
p
hの構築は呼び出される関数のインライン展開(再帰を除く)と
同様であると考えられ，プログラムのサイズが指数的に増加してしまうおそれがある.よって，手
続き間解析を行う提案手法は，メモリ使用量や実行効率の点で，さらなる考察が必要となる.
構造体のメンバに構造体へのポインタがある場合は，それに対して第 4章で示した適用方法を
用いることができない.それを解決する lつの方法は手続き内解析の直前に構造体へのポインタ
型の変数に対してポインタ解析を行うことである.その解析結果を利用し，構造体へのポインタ
型の変数を置き換えることで，第 4章の方法を適用できるようになると考えている.その構造体
へのポインタ型の変数の値を求める解析には，多重度の概念を適用できないので，不動点を求め
る解析が必要になると考えている.
27
三重大学大学院
工学研究科
謝辞
本研究を述べるにあたり，日頃丁寧にご指導いただき，度々研究の議論の時聞を設けていただ
いた大山口通夫教授に心より感謝いたします.また，講義等を通してご指導いただいた山田俊行
講師，研究に関して様々なご指摘をいただいた三橋一郎助教，ならびに何かとお世話になりまし
た落合美子事務職員に深く感謝いたします.
そして，研究や講義に関して，熱心に議論していただき，様々な指摘をしていただいた属苅直
人氏に深く感謝いたします.さらに，研究に関する情報提供や指摘をしてくださった研究室の学
生諸氏に感謝いたします.
2
8
三重大学大学院
工学研究科
参考文献
[
A
H
O
O
]
JohnAycockandN
i
g
e
lHorspoo
l
.S
i
m
p
l
eG
e
n
e
r
a
t
i
o
no
fS
t
a
t
i
cS
i
n
g
l
e
A
s
s
i
g
n
m
e
n
t
e
c
t
u
r
eNotesi
nComputerS
c
i
e
n
c
e pp.110-124 2
0
0
0
.
F
o
r
m
.L
ぅ
う
町10nicaS
. Lam，R
a
v
iS
e
t
h
i andJ
e
f
f
r
e
yD
.U
l
l
m
a
n
. Compilers
[ALSU07] A
l
f
r
e
dV
. Aho，
e
c
h
n
i
q
u
e
s，α
ndT
o
o
l
sSecondE
d
i
t
i
o
n
.P
e
a
r
s
o
n
/A
d
d
i
s
o
n
-Wesley 2
0
0
7
.
P
r
i
n
c
i
p
l
e
s，T
ぅ
う
[
A
n
d
9
4
]
r
s
e
n
. ProgramA
n
a
l
y
s
i
sα
ndS
p
e
c
i
a
l
i
z
αt
i
o
nf
o
rt
h
e C Programming
L
a
r
sO
l
eA吋 e
L
αnguα
g
e
.PhDt
h
e
s
i
s Un
i
v
e
r
s
i
t
yo
fCopenhagen May1
9
9
4
.
ヲ
う
JeanneF
e
r
r
a
n
t
e，
BarryK
.Rosen，
MarkN
.Wegman andF
.Kenneth
[CFR+91] RonCytron，
.E
f
f
i
c
i
e
n
t
l
yComputingS
t
a
t
i
cS
i
n
g
l
eAssignmentFormandt
h
eC
o
n
t
r
o
lDeZadeck
干α
n
sαc
t
i
o
nonProgrammingLα
nguα
g
eα
ndSystemsVo
.
l1
3
pendenceG
r
a
p
h
.ACM1
N
o
.4，
p
p
.451-490，
October1
9
91
.
ぅ
う
う
[EGH94] MaryamEmami，
RakeshGhiya andLa凶 eJ
.H
e
n
d
r
e
n
.C
o
n
t
e
x
t
S
e
n
s
i
t
i
v
eI
n
t
e
r
p
rか
c
e
d
u
r
a
lP
o
i
n
t
s
t
oA
n
a
l
y
s
i
si
nt
h
eP
r
e
s
e
n
c
eo
fF
u
n
c
t
i
o
nP
o
i
n
t
e
r
s
.I
nP
r
o
c
e
e
d
i
n
g
so
f
t
h
eACMSIGPLAN1
9
9
4C
o
n
f
e
r
e
n
c
eonProgrammingLα
ngu
αg
eDesignα
ndI
m
p
l
e
ment
αt
i
o仏 p
p
.2
4
2
2
5
6
.ACM 1
9
9
4
.
ぅ
う
M
i
c
h
a
e
lBurke，
P
a
u
lC
a
r
i
n
i andJong-DeokC
h
o
i
.I
n
t
e
r
p
r
o
c
e
d
u
r
a
l
[HBCC99] M
i
c
h
a
e
lHind，
αnsαc
t
i
o
ηsonProgrammingLαnguα
g
e
sα
ndSystems，
P
o
i
n
t
e
rA
l
i
a
sA
n
a
l
y
s
i
s
.ACMTr
Vo.
l2
1 No.4 p
p
.848-894 1
9
9
9
.
ぅ
ラ
う
ヲ
[HH98
剖
]
RebeccaH剖
a
s
抗
副
t
iandSusanHぽ
o
r
w
i
比
t
z
.Us
討i
n
gS
t
a
t
i
cS
i
n
g
l
eAss
泊i
gnme
凶
n
此
l
tFormt
ω
o
I
m
戸
p
1
F
l
o
w
I
n
百s
e
n
お
回
s
討
i
比
耐
t
i
討
v
eP凶
O
i
凶
n
式
1t
e
目rA
n
a
l
y
s
i
s
.I
nP
r
o
c
e
e
d
i
n
g
so
ft
h
eACMSIGPLAN'
9
8Conngu
αg
eDesignα
ndImplement
αt
i
o凡 p
p
.9
7
1
0
5，
June
f
e
r
e
n
c
e onProgrammingLα
1
9
9
8
.
[
H
i
n
0
1
]
凶: H
aventWeS
o
l
v
e
dThisProblemY
e
t
? I
nP
r
o
M
i
c
h
a
e
lH
i
n
d
.P
o
i
n
t
e
rAnalys
a
l
y
s
i
sf
o
r
c
e
e
d
i
n
g
so
ft
h
e2001ACMSIGPLAN-SIGSOFTworkshoponProgramαn
8
0
f
t
ω
αr
et
o
o
l
sande
n
g
i
n
e
e
r
i
n
g pp.54
-61 2
0
01
.
“
う
う
う
[
H
L
0
7
a
]
BenHardekopfandC
a
l
v
i
nL
i
孔
E
x
p
l
o
i
t
i
n
gP
o
i
n
t
e
randL
o
c
a
t
i
o
nE
q
u
i
v
a
l
e
n
c
et
o
t
αt
i
cα
η
αl
y
s
i
s
:1
4t
hi
n
t
e
r
nα
t
i
o
n
αlSympos叩 m，SAS
O
p
t
i
m
i
z
eP
o
i
n
t
e
rA
n
a
l
y
s
i
s
.I
nS
，p
p
.2
6
5
2
8
0，
2
0
0
7
.
2007
[
H
L
0
7
b
]
BenHardekopfandC
a
l
v
i
nL
i
n
. TheAntandt
h
eG
r
a
s
s
h
o
p
p
e
r
:F
a
s
tandA
c
c
u
r
o
c
e
e
d
i
n
g
so
ft
h
e2007
r
a
t
eP
o
i
n
t
e
rA
n
a
l
y
s
i
sf
o
rM
i
l
l
i
o
n
so
fL
i
n
e
so
fC
o
d
e
. I
nP
ACMSIGPLANc
o
n
f
e
r
e
n
c
eonProgrammingl
a
n
g
uα
g
ed
e
s
i
g
nα
ndimplement
αt
i
o
n
p
p
.2
9
0
2
9
9
.ACM，
2
0
0
7
.
ぅ
2
9
三重大学大学院
工学研究科
[HL0到
9
]
BenHa
紅r
d
e
k
o
p
fandC
a
l
v
i
nL
i
n
.S
e
臼m
昨
1
P
r
o
c
白ε
e
d
i
n
伊
g
so
ft
h
e3
6
t
仇
hACMSIGPLAN-SIGACTSym
η~pos幻t叩
um
g
r
ammz
α
肌n
gLαng
仰u
α
句g
e
叫
，
s
兵p
p
.226-238 Januar
可
y2
却0
0
ω
9
.
0η P
r
門'
in
c
i
伊
p
l
ε
so
fP
r
o
-
う
ハ
リ
ハU
P
H
M
i
c
h
a
e
lHindandAnthonyP
i
o
l
i
. WhichP
o
i
n
t
e
rA
n
a
l
y
s
i
sS
h
o
u
l
d1Use? I
nP
r
o
c
e
e
d
i
n
g
so
ft
h
e2000AC MSIGSOFTI
n
t
e
r
n
a
t
i
o
nαlSymposiumonS
o
f
t
ω
αr
eT
e
s
t
i
n
g
α
η dAn
αl
y
s
i
sぅ pp・1
1
3
1
2
3
.ACM 2
0
0
0
.
う
[
L
H
9
8
]
ト
C
h
r
i
s
t
o
p
h
e
rLapkowskiandL
a
u
r
i
eJ
.Hendren. ExtendedSSANumbering: I
n
t
r
c
d
u
c
i
n
gSSAP
r
o
p
e
r
t
i
e
st
oLanguageswithMultiL
e
v
e
lP
o
i
n
t
e
r
s
.L
e
c
t
u
r
eN
o
t
e
si
n
ComputerS
c
i
e
n
c
e，
Vol
.1
3
8
3ぅ p
p
.128-143 1
9
9
8
.
司
ヲ
[
L
R
9
1
]
WilliamLandiandBarbaraG
.Ryde
r
.P
o
i
n
t
e
r
I
n
d
u
c
e
dA
l
i
a
s
i
n
g
:A ProblemC
l
a
s
s
i
o
n
f
e
r
e
n
c
eR
e
c
o
r
do
ft
h
eE
i
g
h
t
e
e
n
t
hAnnualACMSymposiumonP
r
i
n
f
i
c
a
t
i
o
n
.I
nC
c
伊l
e
so
fProgrammingLα
ηg
u
α
g
e
s
ぅ p
p
.93-103 1
9
91
.
う
[
L
T
7
9
]
ThomasLe時 a
u
e
randRobertEndreT
a
r
j
a
n
.A F
a
s
tAlgorithmf
o
rF
i
n
d
i
n
gDominat
o
r
si
naF
l
o
w
g
r
a
p
h
. ACMT
r
αn
s
αc
t
i
o
n
sonProgrammingLαngu
αg
e
sαndS
y
s
t
e
m
sぅ
Vol
.1，
No.1
，pp.121-141 1979.
う
[
M
y
e
8
1
]
EugeneW.M
y
e
r
s
. AP
r
e
c
i
s
eI
n
t
e
r
P
r
o
c
e
d
u
r
a
lDataFlowA
l
g
o
r
i
t
h
m
.I
nP
r
o
c
e
e
d
i
n
g
so
ft
h
e8
t
hACMSIGPLAN-SIGACTSymposiumonP
r
i
n
c
i
p
l
e
so
fProgramming
L
αnguα
.
ge
sぅ p
p
.2
1
9
2
3
0
.ACM，
1
9
81
.
[
N
L
0
9
]
NomairA.NaeemandO
n
d
f
e
jL
h
o
t
a
k
.E
f
f
i
c
i
e
n
tA
l
i
a
sS
e
tA
n
a
l
y
s
i
sUsingSSAForm.
I
nP
r
o
c
e
e
d
i
n
g
so
ft
h
e2009I
n
t
e
r
n
αt
i
o
n
a
lSymposiumonMemoryManα
gement p
p
.
79-88 2
0
0
9
.
う
ヲ
[
P
r
o
]
t
t
p
:
jj
w
w
w
.
c
o
i
n
s
p
r
o
j
e
c
t
.
o
r
gj
.
COINSP
r
o
j
e
c
t
. COINSP
r
o
j
e
c
thomepage. h
[Ram94] Ga
町 s
anRamalinga
乱
TheUndecidab
i
1
i
t
yo
fA
l
i
a
s
i
n
g
. ACMTn
αmαc
t
i
o
n
sonP
r
o
grammingLαngu
αg
e
sαndS
y
s
t
e
m
s
うVo
l
.1
6うN
o
.5，
p
p
.1467-1471う1
9
9
4
.
[
S
H
9
7
a
]
MarcS
h
a
p
i
r
oandSusanH
o
r
w
i
t
z
. F
a
s
tandAccurateF
l
o
w
I
n
s
e
n
s
i
t
i
v
eP
o
i
n
t
s
T
o
A
n
a
l
y
s
i
s
.I
n The2
4
t
hACMSIGPLANSIGACTSymposiumonP
r
i
n
c
i
p
l
e
so
fP
r
o
grammingLαngu
αg
e
s，
p
p
.1
1
4 January1
9
9
7
.
倫
う
[
S
H
9
7
b
]
MarcS
h
a
p
i
r
oandSusanH
o
r
w
i
t
z
. TheE百e
c
t
so
ft
h
eP
r
e
c
i
s
i
o
no
fP
o
i
n
t
e
rA
n
a
l
y
s
i
s
.
L
e
c
t
u
r
eN
o
t
e
si
nComputerS
c
i
e
n
c
e，
Vo
l
.1
302，
p
p
.16-34 1
9
9
7
.
う
[
S
t
e
9
6
]
BjarneS
t
e
e
n
s
g
a
a
r
d
.P
o
i
n
t
s
t
oA
n
a
l
y
s
i
si
nAlmostL
i
n
e
a
rTime. I
nThe2
3
r
dACM
SIGPLAN-SIGACTSymposiumonP
r
i
n
c
i
p
l
e
so
fProgrammingLαngu
αg
e
s
ぅ p
p
.3
2
4
1，
January1
9
9
6
.
←
[田中 1
0
] 田中友幸.プログラムの参照先解析に関する研究. M
a
s
t
e
r
'
st
h
e
s
i
sぅ三重大学大学院工
学研究科う March2
0
1
0
.
3
0
三重大学大学院
工学研究科
付 録A
H
a
s
t
iらの手法 [HH98]の実行例
図 A.1，
図 A.2に図 A.1(a)のプログラムに対する H
a
s
t
iらの手法の実行例を示す.
前処理
図 A.1(a)に対してフロー非依存ポインタ解析を行い，解析結果として次の結果を得る.
t→
{
s
}S → {
pq
}
ぅ
ぅ
この結果をデリファレンス (
*
t，
*
s
)に注釈として付与する.
繰返し (
1回目)
1.デリファレンスの注釈に基づいて，図 A.1(b)の中間形式に変換する.このとき変数 s
は 2つの指し先の候補を持っているため， branchノードを用いて分岐の形に置き換え
る.そして，このフ。ログラムを SSA形式に変換する(図 A.1(c
)
)
.
1
1
.
図 A.1(c)に対してフロー非依存ポインタ解析を行い，次のような解析結果を得る.
t
1→ {
s
}，S
1→ {
p
}，S
2→ {
q
}
これを用いて図 A.1(a)の注釈を更新する.このとき， *
tはもしそのまま現れていたと
1
となっていたため，ポインタ情報
t
1
→
{
s
}
を用いて更新する.同様に
*
sは
すると吋
もし branchノードに現れていたとすると *
S
2となっているため， S
2→ {
q
}を用いる.
l
l
l
.
この更新により句の注釈に変化が生じたため，もう l度処理を繰り返す(図 A
.
2
)
.
繰返し (
2回目)
1回目の繰返しと同様の処理を行ったあと，図 A.2(c)に対してフロー非依存ポインタ解析
を行うと，次の結果が得られる.
七1→
{
S
}，S
1→ {
p
}，S
2→ {
q
}
この解析結果は 1回目の解析結果と同等であり，各デリファレンスの注釈も変化がないため，
この結果が最終的なポインタ情報となる.
3
1
三重大学大学院
工学研究科
t.
.{s}
5 .
.{
P.q}
(
a
)CFG (注釈付き)
(
b
)中間形式
(
c
)SSA形式
図A
.
l
:H
a
s
t
iら [
H
H
9
8
]の実行例(1回目)
t~ {5}
5.
. {q}
(
a
)CFG (注釈付き〉
(
b
)中間形式
図A
.
2
:H
a
s
t
iら [
H
H
9
8
]の実行例(2回目)
32
三重大学大学院
工学研究科
(
c
)SSA形式
付 録B
提案手法のインクリメンタルな手法への
変更
H
a
s
t
iらの手法である途中で止めることで得られる解析結果と同等の結果を得る手法を AIgorithm5に示す.なお，極大なポインタ変数を求める方法としては， SSA形式に変換して極大な
ポインタ変数を求めることが効率よく計算できる方法の lつである. AIgorithm5の手法では，
極大なポインタ変数は l度だけ解析され，それ以降の解析では不必要となり除去されるのに対し，
H
a
s
t
iらの手法は何度も繰り返し解析を行われる.この点が大きな違いである.
A19orithm5提案手法 (
H
a
s
t
iらのインクリメンタルな手法に対応)
Require: 制御フローグラフ CFG ，多重度 i(l 三 i~max)
f
o
rn=maxt
oido
)
極大なポインタ変数を SSA形式に変換する (SSA
n
SSAnに対してフロー非依存ポインタ解析を行う
SSAnの極大なポインタ変数のデリファレンスを解析結果を用いて置き換える
endf
o
r
i
fi>0then
フロー非依存ポインタ解析を行う
SSAj)
デリファレンスを置き換え， SSA形式に変換する (
SSAjに対してフロー非依存ポインタ解析を行う
endi
f
3
3
三重大学大学院
工学研究科
付 録C
再帰呼び出しを含む supergraph
再帰呼び出しを含むとき. supergraphは図 C.lのようになる.なお，このプログラムに対する
supergraphは，複製を用いるか否かに関わらず，図 C.l(b)の形となる.
v
o
i
df
O{
ノ
E
J--y
A
/l¥
l
，
，
‘
、，
，
(
、
、i
-f
ρ+
・
・
1
•
i
n
tm
a
i
n
(
v
o
i
d
)
{
-う
p?i
、
、
‘
‘
，
，
，
〆
(
r
e
t
u
r
n0
;
(
b
)s
u
p
e
r
g
r
a
p
h
(
a
)プログラム
図C
.
l
:再帰関数を含む supergraph
34
三重大学大学院
工学研究科
付 録D
supergraphの構築例
図 D.l(a)のプログラムに対する， Algorithm3の適用例を示す.この例では複製を用いた
s
u
p
e
r
g
r
a
p
hを構築する.
.
l
(
b
)
)
.こ
まず関数ポインタによらない関数呼び出しを考慮した supergraphを構築する(図 D
のとき， 2つの関数呼び出し(吋 p)O;は処理しない.
)0;で f
p→
次にその supergraphに対してフロー依存ポインタ解析を行う.その結果，各(*fp
gというポインタ情報が得られる.これらの情報を用いて s
u
p
e
r
g
r
a
p
hを更新したものが図 D.l(c)
となる.
s
u
p
e
r
g
r
a
p
hに変化があったので，図 D.l(c)に対してフロー依存ポインタ解析を行う.この解
p
)0;には， f
p→ g，2つ目のい f
p
)0;には， f
p→ fというポインタ情報
析では， 1つ目のい f
が与えられる.この情報から， supergraphは図 D.l(d)のように更新される.
s
u
p
e
r
g
r
a
p
hが更新されたので，さらにフロー依存解析を行う.この結果は前回の結果と変わら
u
p
e
r
g
r
a
p
hの構築に
ない.よって supergraphの変化も無いため，解析が終了する.この例では s
焦点を当てたが，実際には，関数ポインタだけでなく，通常のポインタ変数に対する解析も同時
に行われている.
3
5
三重大学大学院
工学研究科
v
o
i
d(
*
f
p
)0
;
v
o
i
df
O
{
v
o
i
dg
O{
f
p= f
;
i
n
tm
a
i
n
(
v
o
i
d
)
{
f
p= g
;
f
O
う
(
*
f
p
)
O
;
(
*
f
p
)
O
;
r
e
t
u
r
n0
;
(
a
)フ。ログラム
(
b
)通常の関数呼び出しを考
慮した s
u
p
e
r
g
r
a
p
h
れ
ら
得
IU
で
返
工学研究科
m
v
三重大学大学院
繰出
の叫
QU
3
6
目
、、﹄ノ
図D
.
l
:supergraph
回開
2u
似る
(
c
)1回目の繰返しで得られ
るs
u
p
e
r
g
r
a
p
h