大阪大学 大学院基礎工学研究科 情報数理系専攻 ソフトウェア科学分野 高田 智規 プログラム解析の効率化 に関する研究 大阪大学 大学院基礎工学研究科 情報数理系専攻 ソフトウェア科学分野 高田 智規

略歴 平成9年3月 大阪大学大学院基礎工学研究科 物理系専攻 情報工学分野 博士前期課程修了 在学中はプログラムスライシングに関する研究に従事 平成9年4月 日本電信電話株式会社 入社 平成9年8月 ヒューマンインタフェース研究所に配属 ビデオサーバの負荷分散技術の研究・開発に従事 平成12年4月 西日本電信電話株式会社 大阪支店に異動 中規模ERPパッケージのSI業務 平成13年10月 大阪大学大学院基礎工学研究科 情報数理系専攻 博士後期課程入学 プログラムスライシングに関する研究に従事 平成14年5月 日本電信電話株式会社 サイバーソリューション研究所に異動 ディジタルコンテンツの著作権管理に関する研究・開発に従事

論文一覧 プログラム依存グラフの効率的な更新手法 電子情報通信学会論文誌 (1998) ⇒ 2章 プログラム依存グラフの効率的な更新手法 電子情報通信学会論文誌 (1998) ⇒ 2章 制限された動的情報を用いたプログラムスライシング手法の提案 電子情報通信学会論文誌(2002) ⇒ 3章 制限された動的情報を用いたブロック単位スライシング手法の提案 電子情報通信学会論文誌(投稿中) ⇒ 4章 ソースコード解析ツール開発支援システムの試用 電子情報通信学会論文誌(1997) Dependence-Cache Slicing: A Program Slicing Method Using Lightweight Dynamic Information, 10th IEEE International Workshop on Program Comprehension (2002/6発表予定)

発表内容 プログラム解析概要 プログラム依存グラフの効率的な更新手法 準動的解析を用いたスライシング手法 プログラムが変更された場合に、プログラム依存グラフを再計算することなく、部分的に更新する手法 準動的解析を用いたスライシング手法 静的解析情報と動的解析情報を組み合わせた効率的なスライシング手法

プログラム解析概要

デバッグ作業におけるプログラム解析 ソフトウェア開発において、デバッグ・テスト・保守フェーズにおける比重はソフトウェアの大規模化に伴い増加している デバッグ効率向上へのアプローチ 文間の依存関係解析によって特定の文に関連のある文を抽出 依存関係解析はオーバヘッドが大きい ↓ 解析の効率化が重要

プログラムスライス 注目した文に影響を与える（受ける）文の集合 プログラム開発における様々なフェーズで利用可能 ⇒ 特にデバッグフェーズ 開発作業の効率化を実現 1 program Square_Cube(input, output); 2 var a, b, c, d : integer; 3 function Square(x : integer) : integer; 4 begin 5 Square := x * x 6 end; 7 function Cube(x : integer) : integer; 8 begin 9 Cube := x * x * x 10 end; 11 begin 12 writeln(``Squared Value ?''); 13 readln(a); 14 writeln(``Cubed Value ?''); 15 readln(b); 16 writeln(``Select Feature! Square: 0 Cube: 1''); 17 readln(c); 18 if c = 0 then 19 d := Square(a) 20 else 21 d := Cube(b); 22 if d < 0 then 23 d := -1 * d; 24 writeln(d) 25 end. 1 program Square_Cube(input, output); 2 var a, b, c, d : integer; 3 function Square(x : integer) : integer; 4 begin 5 Square := x * x 6 end; 7 function Cube(x : integer) : integer; 8 begin 9 Cube := x * x * x 10 end; 11 begin 12 writeln(``Squared Value ?''); 13 readln(a); 14 writeln(``Cubed Value ?''); 15 readln(b); 16 writeln(``Select Feature! Square: 0 Cube: 1''); 17 readln(c); 18 if c = 0 then 19 d := Square(a) 20 else 21 d := Cube(b); 22 if d < 0 then 23 d := -1 * d; 24 writeln(d) 25 end.

フォールト位置特定におけるプログラムスライス 実験１ スライス利用 スライスなし 被験者 A1 A2 A3 B1 B2 B3 デバッグ時間（分） 119 128 120 154 175 122.3 149.7 実験２ スライスなし スライス利用 被験者 A1 A2 A3 B1 B2 B3 デバッグ時間（分） 118 126 155 131 92 120 133.0 114.3 西松 顕, 西江 圭介, 楠本 真二, 井上 克郎: ``フォールト位置特定における プログラムスライスの実験的評価'', 電子情報通信学会論文誌, Vol.J82-D-I, No.11, pp. 1336--1344 (1999).

スライスの応用 フォールト位置特定 プログラム再利用 プログラム理解 プログラム合成 プログラム編集 プログラム簡素化 など

スライスの分類 静的スライシング プログラムを静的に（実行なしに）解析 動的スライシング 特定の入力に基づき解析

静的スライシング プログラムを静的に（実行なしに）解析 全ての入力データを仮定 依存関係を基にプログラム依存グラフ(Program Dependence Graph, PDG)を構築 PDG辺を辿ることによりスライスを計算

依存関係 制御依存関係 データ依存関係 ある文の実行有無が他の条件式の判定結果に依存 変数の定義-参照関係 s1: if a=0 then s2: b :=1; s1 s2 s3: a := 1; s4: writeln(a); s3 s4 a

プログラム依存グラフ 依存関係を表したグラフ 節点 文を表す 辺 文間の依存関係を表す 文 条件式 特殊節点 （関数境界解析等） 節点 文を表す 文 条件式 特殊節点 （関数境界解析等） 辺 文間の依存関係を表す データ依存辺 制御依存辺

PDGの例 Main Square Cube 1 program Square_Cube(input, output); 2 var a, b, c, d : integer; 3 function Square(x : integer) : integer; 4 begin 5 Square := x * x 6 end; 7 function Cube(x : integer) : integer; 8 begin 9 Cube := x * x * x 10 end; 11 begin 12 writeln(``Squared Value ?''); 13 readln(a); 14 writeln(``Cubed Value ?''); 15 readln(b); 16 writeln(``Select Feature! Square: 0 Cube: 1''); 17 readln(c); 18 if c = 0 then 19 d := Square(a) 20 else 21 d := Cube(b); 22 if d < 0 then 23 d := -1 * d; 24 writeln(d) 25 end. x-para Square-exit Cube-exit d := Square(a) d := Cube(b) d := -1 * d Square := x * x Cube := x*x*x readln(a) readln(b) readln(c) writeln(“Sq.. writeln(“Cu.. writeln(“Sel.. writeln(d) if d<0 if c=0 Square Cube Main x a b d c d

静的スライスの例 スライシング基準 Main Square Cube 1 program Square_Cube(input, output); 2 var a, b, c, d : integer; 3 function Square(x : integer) : integer; 4 begin 5 Square := x * x 6 end; 7 function Cube(x : integer) : integer; 8 begin 9 Cube := x * x * x 10 end; 11 begin 12 writeln(``Squared Value ?''); 13 readln(a); 14 writeln(``Cubed Value ?''); 15 readln(b); 16 writeln(``Select Feature! Square: 0 Cube: 1''); 17 readln(c); 18 if c = 0 then 19 d := Square(a) 20 else 21 d := Cube(b); 22 if d < 0 then 23 d := -1 * d; 24 writeln(d) 25 end. Main Square writeln(“Sq.. readln(a) x-para writeln(“Cu.. readln(b) x a Square := x * x writeln(“Sel.. a readln(c) Square Square-exit if c=0 Square c b d := Square(a) Cube d d := Cube(b) x-para b x d if d<0 d := -1 * d Cube := x*x*x d d Cube Cube writeln(d) Cube-exit d スライシング基準

動的スライシング プログラムをある入力データで実行する 注目した文に実際に影響を与えた文の集合 プログラムの実行系列を基に動的依存グラフ(Dynamic Dependence Graph, DDG)を作成し、グラフの辺を辿ることにより抽出

動的スライスの例 入力 a=2, b=1, c=0 の場合 Main Square Cube 1 program Square_Cube(input, output); 2 var a, b, c, d : integer; 3 function Square(x : integer) : integer; 4 begin 5 Square := x * x 6 end; 7 function Cube(x : integer) : integer; 8 begin 9 Cube := x * x * x 10 end; 11 begin 12 writeln(``Squared Value ?''); 13 readln(a); 14 writeln(``Cubed Value ?''); 15 readln(b); 16 writeln(``Select Feature! Square: 0 Cube: 1''); 17 readln(c); 18 if c = 0 then 19 d := Square(a) 20 else 21 d := Cube(b); 22 if d < 0 then 23 d := -1 * d; 24 writeln(d) 25 end. Main Square writeln(“Sq.. readln(a) x-para writeln(“Cu.. readln(b) x a Square := x * x writeln(“Sel.. a readln(c) Square Square-exit if c=0 Square c d := Square(a) Cube d if d<0 d writeln(d) 入力 a=2, b=1, c=0 の場合

静的・動的スライシングの特徴 静的スライシング プログラムの実行を伴わない 動的スライシング プログラムの実行が必須 長所 短所 長所 短所 有効な入力データが無い場合でも解析可能 短所 全ての入力データを仮定した安全な近似が必要 配列変数・ポインタ等の正確な解析ができない 動的スライシング プログラムの実行が必須 長所 配列・ポインタ等も正確に解析可能 短所 実行時オーバヘッドが大きい 実行時間、メモリ空間etc.

プログラム依存グラフの 効率的な更新手法

デバッグフェーズにおけるスライス利用 ソース変更 実行 デバッグ終了 解析(PDG計算) 大規模プログラムにおいては解析のオーバーヘッドが大きい スライス計算 プログラムに変更が加えられた際に、プログラム全体を再解析することなしにPDGを更新する手法が必要。 フォールト位置特定

提案手法 PDG中の依存辺を基に変数の定義情報を復元し、変更後の依存関係を計算することで、変更の影響を受ける部分のみを更新 制御依存辺更新 関数内データ依存辺更新 関数間影響解析

諸定義 対象言語 PDG スカラ型のみからなる手続き型言語（Pascalサブセット）

基本方針 制御依存関係は構文解析から更新 PDGのDD辺は解析時に変数の定義情報を基にして引かれている． ⇒ 変更前のPDG中のDD辺から，変数の定義情報の一部を復元することが可能． これを利用し、変更後のデータ依存関係を求め依存辺を更新 v r s 到達定義<r,v>

提案するアルゴリズム 関数内解析アルゴリズム 関数間解析アルゴリズム 文の削除 文の追加 文の修正 （基本的には削除＋追加） 他関数に与える影響を解析

削除アルゴリズム アルゴリズムDeleteVertex 入力: 削除する節点s 出力: 更新されたPDG sで定義されている各変数vについて DD ← DD ∪ {r v t | r ∈ PreDef(s,v), t ∈ target(s,v)} DD ← DD – {r v s | r ∈ source(s,v)} – {s v t | t ∈ target(s,v)} FLOW ← FLOW ∪ { p → n | p ∈ prev(s), n ∈ next(s) } – { r → s | r ∈ prev(s) } – { s → t | t ∈ target(s) } 節点s自身を削除

共通アルゴリズム アルゴリズムFindPreDef （前定義節点の発見） 入力: 節点s , 変数v c ∈ prev(s) なる各cに対して以下を順に実行 cにおいてvが定義されていれば PreDef(s,v) ← PreDef(s,v) ∪ c cにおいてvが参照されていれば PreDef(s,v) ← PreDef(s,v) ∪ source(c,v) cにおいてvが定義・参照ともにされていなければ、c←prev(c)として2a.以下を実行

定義 文sから文tへの変数vに関するデータ依存辺 s v t 文sから文tへのフロー辺 s → t 文sからフロー辺を逆方向に辿った節点集合 prev(s) 文sからフロー辺を順方向に辿った節点集合 next(s) 文sから変数vに関してデータ依存辺を逆方向に辿った節点集合 source(s,v) 文sから変数vに関してデータ依存辺を順方向に辿った節点集合 target(s,v)

削除アルゴリズム s1: readln(x,y); s2: max := x; s3: if x>y then max := y writeln(max) readln(x,y) x y max s1 s2 s3 s4 s5 s6 if x>y DD CD Flow s1 readln(x,y) s1: readln(x,y); s2: max := x; s3: if x>y then s4: max := x else s5: max := y; s6: writeln(max); y x x y s2 max := x r s t max max x s3 if x>y s4 s5 直前にmaxを定義している文r、sからDDを辿った文tを発見 rからtへDDを追加 直前の文と直後の文間にフロー辺を追加 sおよび関連する文を削除 max := x max := y s6 max max writeln(max) DD CD Flow

挿入アルゴリズム アルゴリズムInsertVertex 入力: 挿入する節点s, prev(s), next(s) 出力: 更新されたPDG FLOW ← FLOW ∪ { p → s | p ∈ prev(s) } ∪ { s → n | n ∈ next(s) } – { p → n | p ∈ prev(s), n ∈ next(s) } sで定義している各変数vすべてについて以下を実行 各r∈PreDef(s,v), t∈target(r,v)に対して、vを定義しないようなパス s, … , t が存在すれば、以下を実行 DD ← DD ∪ { s v t } 任意のr ∈ PreDef(s,v)に対してvを定義しないようなパスr, …, tが存在しなければ、 DD ← DD – { r v t | r ∈ PreDef(s,v)} sで参照している各変数uすべてについて、 DD ← DD ∪ { r u s | r ∈ PreDef(s,v) }

挿入アルゴリズム s1: readln(x,y); s2: max := x; s3: if x>y then else max := y writeln(max) readln(x,y) x y max s1 s2 s3 s5 s6 if x>y s1 readln(x,y) s1: readln(x,y); s2: max := x; s3: if x>y then else s5: max := y; s6: writeln(max); x y x x y s2 max := x max := x s3 if x>y max max := x s5 挿入する節点およびCDを作成 フロー辺引きなおし maxを参照する文を探索しDDを追加 挿入により不要となるDD削除 参照する変数のDD追加 max := y max s6 max writeln(max) DD CD Flow

修正アルゴリズム アルゴリズムModifyVertex 入力: 節点s, 変更後の定義変数集合V’, 変更後の参照変数集合U’ 出力: 更新されたPDG FLOW ← FLOW v ∈ V – V’ に対して、 DD ← DD ∪ { r v t | r ∈ PreDef(s,v), t ∈ target(s,v) } – { s v t | t ∈ target(s,v) } v’ ∈ V’ – V に対して、 各r∈PreDef(s,v’), t∈target(r,v’)に対して、vを定義しないようなパスr,…,tが存在すれば以下を実行 DD ← DD ∪ { s v’ t } 任意のr∈PreDef(s,v’)に対して、v’を定義しないようなパスr,…,tが存在しなければ、 DD ← DD – { r v’ t | t ∈ PreDef(s,v) } u ∈ U – U’ に対して、 DD ← DD – { r u s | r∈PreDef(s,u) } u’ ∈ U’ – U に対して、 DD ← DD ∪ { r u’ s | r∈PreDef(s,u’)}

関数間解析 関数内変更を実行 変更した関数内で「必ず定義される」「定義される可能性がある」「参照される可能性がある」変数の集合を計算 他の関数に与える影響を計算し、変化があれば依存辺を追加・削除（各関数の値が収束するまで繰り返す）

実験 Pascalスライシングシステムに実装 実行結果 単位:秒 SparcStation20上 削除 約1060行 挿入 約570行 50行 100行 250行 430行 PDG再計算 0.08 0.35 1.42 16.61 削除 <0.01 0.01 0.07 挿入・変更 0.05 単一関数 複数関数

まとめ プログラムが変更された際に、プログラム全体を再解析することなく、PDGを更新する手法を提案

準動的情報を用いたプログラムスライシング手法

静的スライシングと動的スライシング 解析コスト 静的 ＜ 動的 スライスサイズ 静的 ＞ 動的 実行系列の保存 : 高コスト（実行時） 解析コスト 静的 ＜ 動的 実行系列の保存 : 高コスト（実行時） 実行系列の解析 : 高コスト（解析時） スライスサイズ 静的 ＞ 動的 静的スライシングでは全ての入力値を仮定 動的スライシングでは１種類のトレースを対象 実際の実行データを収集できるため、配列添字やポインタ解析も可能

静的情報と動的情報の結合 静的解析情報 準動的解析 ＋ 動的解析情報 効率的かつ効果的な解析

準動的解析 準動的解析のアプローチ 動的に 経路情報 を収集 動的に データ依存関係 を収集 コールマークスライシング （既存手法） 依存キャッシュスライシング

コールマークスライシング 依存関係 実行時、関数呼び出し文が実行されたかどうか（コールマーク）をセット 制御依存関係 データ依存関係 実行依存関係 ED（Execution Dependence） ある文が実行されなければ、別の文は決して実行されない 実行時、関数呼び出し文が実行されたかどうか（コールマーク）をセット コールマークとEDを基に、実行されなかった文をPDGから除外

コールマークスライシングの特長 実行されない文がスライスから除外される ⇒ 静的スライスより小さな（正確な）スライス 簡単なフラグと容易に計算できるCEDで実現可能 ⇒ 実装が容易 実行時に収集する情報は呼び出し文が実行されたかどうかのみ ⇒ 実行時オーバヘッドの増加が少ない

コールマークスライシングの限界 配列・ポインタ・構造体変数の正確性は静的スライシングと同等 1: a[0]:=0; 2: a[1]:=3; 3: readln(b); 4: a[b]:=2; 5: c:=a[0]+4; 6: writeln(c); ? ? ?

依存キャッシュスライシング データ依存関係に着目した準動的スライシング手法 制御依存関係 データ依存関係 構文解析で容易に解析可能 ⇒ 静的に解析 データ依存関係 静的に正確な解析は困難 ⇒ 簡単なキャッシュを用い、動的に解析

依存キャッシュスライスの計算 実行前解析: 節点と制御依存辺のみからなるPDGのサブセットPDGDSを構築。変数にキャッシュを用意 実行時解析: 変数が定義されれば、キャッシュに文を設定。変数が参照されれば、キャッシュに保持されている文からデータ依存辺を追加 実行後解析: なし スライス計算: PDGDSの辺を辿りスライスを抽出

アルゴリズムの概要 静的制御依存関係解析 PDGの部分グラフPDGDSを静的に生成する． まず，静的スライシングで利用するPDGと同様，文または制御文に対応する節点を用意する．そして，文間に制御依存関係が存在すれば，対応する節点間に制御依存辺を引く．ただし，PDGDSにデータ依存辺は加えない． 動的データ依存関係解析 対象プログラムをある入力データで実行する． 実行の際，次節で示すデータ依存関係抽出アルゴリズムに基き，動的なデータ依存関係を計算し，PDGDSにデータ依存辺を追加する．プログラム実行が終了した時点で，PDGDSの完成となる． PDGDSによるスライス計算 PDGDSを用いて，静的スライシングと同様の方法でスライス計算を行う． 例えば，スライシング基準(sc, v)に関する依存キャッシュを抽出する場合，まず，scに対応する節点から制御依存辺およびvに関するデータ依存辺を逆向きに辿ることで到達可能な節点集合を導出する．そして，この節点集合に対応する文が求めるスライスとなる．

動的データ依存関係抽出アルゴリズム 入力 PDGBL: 部分的に生成されブロック化されたPDG P: 対象プログラム I: Pへの入力 作業変数 P中の各変数vに対する依存キャッシュC(v) 出力 OUT: 入力Iに対するプログラムPの実行の出力 PDGBL: 完成したPDG アルゴリズム本体 1. P中の各静的変数vに対し, C(v) := Φ 2. Pが停止するまで以下を繰り返し実行する { Pを入力Iで最初から停止するまで文ごとに実行 } a) Iに関して，Pの次の一文sを実行 b) sで使用(参照)される各変数uについて， C(u) ≠Φかつ，データ依存辺 C(u) u sが存在しなければPDGBL にC(u) u sを追加する． c) sで定義される各変数wについて，C(w) := s

データ依存関係収集 1: a[0]:=0; 1: a[0]:=0; 2: a[1]:=3; 3: readln(b); キャッシュ内容 Input: b=0 a[0] a[1] b c 1: a[0]:=0; 1: a[0]:=0; 2: a[1]:=3; 3: readln(b); 4: a[b]:=2; 5: c:=a[0]+4; 6: writeln(c); s1 s4 s2 s3 s1 s2 s4 s2 s3 s5 s4 s2 s3 s5 s1 s2 s3 2: a[1]:=3; 3: readln(b); b 4: a[b]:=2; a[0] 5: c:=a[0]+4; c 6: writeln(c);

データ依存関係収集(2) 1: a[0]:=0; 1: a[0]:=0; 2: a[1]:=3; 3: readln(b); キャッシュ内容 Input: b=1 a[0] a[1] b c 1: a[0]:=0; 1: a[0]:=0; 2: a[1]:=3; 3: readln(b); 4: a[b]:=2; 5: c:=a[0]+4; 6: writeln(c); s1 s2 s1 s1 s2 s3 s1 s4 s3 s1 s4 s3 s5 a[0] 2: a[1]:=3; 3: readln(b); b 4: a[b]:=2; 5: c:=a[0]+4; c 6: writeln(c);

依存キャッシュスライスの特長 簡単なキャッシュを用いることで、動的なデータ依存関係を収集 ⇒ 効率的かつ効果的なスライス 既存環境にキャッシュおよびDD辺構築機能を追加することで実装可能 ⇒ 実装が容易

実験 ３つのプログラム について、 を計算 P1: カレンダー P2：酒屋問題 P3：酒屋問題（拡張版） 静的スライス コールマークスライス 依存キャッシュスライス 動的スライス を計算

実験結果～スライスサイズ 静的 ＞ CM ＞＞ DC ＞ 動的 P2・P3では配列変数を使用しているため顕著 行 187 182 166 200 static 182 166 180 call-mark 162 160 dependence-cache 140 dynamic 120 100 80 61 60 40 21 17 15 16 20 5 5 8 P1 P2 P3 静的 ＞ CM ＞＞ DC ＞ 動的 P2・P3では配列変数を使用しているため顕著

実験結果～実行時解析時間 静的 ≒ CM ≒ DC ＜＜ 動的 DCは僅かな実行時オーバヘッド増加で解析可能 時間 (ms) 206464 6000 static call-mark dependence-cache dynamic 4731 5000 4834 4700 4540 4000 3000 2000 1000 47 47 51 174 43 43 45 P1 P2 P3 静的 ≒ CM ≒ DC ＜＜ 動的 DCは僅かな実行時オーバヘッド増加で解析可能

まとめ 準動的手法を用いたスライシング手法 「依存キャッシュスライシング」 を提案 スライスサイズは静的スライシングより小さく、動的スライシングより大きい 僅かな実行時オーバヘッドで、配列・ポインタ等を正確に解析可能

むすび

まとめ プログラム中の文間の依存関係解析に関して，解析を効率化するための手法を提案した． 提案手法についてそれぞれの有効性を確認 ↓ プログラムに変更が加えられた際の再解析を効率化し，インタラクティブなデバッグ作業を実現するプログラム依存グラフの効率的な更新手法 静的解析情報と動的解析情報を組み合わせた準動的解析手法を用いることにより，現実的な実行時オーバヘッドで高精度のプログラムスライスを抽出できる依存キャッシュスライシング手法 提案手法についてそれぞれの有効性を確認 ↓ デバッグ作業の効率化、ソフトウェア開発の生産性向上

今後の研究方針 作業者によるデバッグ作業における実験を通した評価 実プログラムへの適用 オブジェクト指向プログラムへの適用 PDG更新 … エイリアス解析等への対応 依存キャッシュスライシング … 他言語への実装 オブジェクト指向プログラムへの適用 継承・動的束縛などオブジェクト指向独自の概念への対応