大阪大学 大学院基礎工学研究科 情報数理系専攻 ソフトウェア科学分野 高田 智規

Slides:



Advertisements
Similar presentations
©2008 Ikuo Tahara探索 状態空間と探索木 基本的な探索アルゴリズム 横形探索と縦形探索 評価関数を利用した探索アルゴリズム 分岐限定法 山登り法 最良優先探索 A ( A* )アルゴリズム.
Advertisements

シーケンス図の生成のための実行履歴圧縮手法
背景 ソフトウェアの大規模化・複雑化 生産性と品質の向上 ↓ オブジェクト指向分析設計の適用 開発ツールの投入.
XHTML構文検証手法における スクリプト要素の静的解析アルゴリズム
プログラミング言語論 第4回 手続きの引数機構 変数の有効範囲
プログラムの動作を理解するための技術として
F11: Analysis III (このセッションは論文2本です)
MATLAB測位プログラミングの 基礎とGT (1)
リファクタリングのための 変更波及解析を利用した テスト支援ツールの提案
ML 演習 第 7 回 新井淳也、中村宇佑、前田俊行 2011/05/31.
動的スライスを用いたバグ修正前後の実行系列の差分検出手法の提案
プログラム静的解析手法の効率化と 解析フレームワークの構築に関する研究
プログラム実行履歴を用いたトランザクションファンクション抽出手法
プログラム実行時情報を用いたトランザクションファンクション抽出手法
ソースコードの変更履歴における メトリクス値の変化を用いた ソフトウェアの特性分析
静的情報と動的情報を用いた プログラムスライス計算法
プログラム依存グラフを利用した 情報漏洩解析手法の提案と実現
動的スライスを用いた バグ修正前後の実行系列の比較
プログラミング言語論 第9回 Hoare論理の練習問題 手続きの引数機構 変数の有効範囲
動的依存グラフの3-gramを用いた 実行トレースの比較手法
オブジェクト指向プログラムにおける エイリアス解析手法の提案と実現
オブジェクト指向プログラムにおける エイリアス解析について
インラインスクリプトに対するデータフロー 解析を用いた XHTML 文書の構文検証
動的スライスを用いたバグ修正前後の実行系列の差分検出手法
利用関係に基づく類似度を用いたJavaコンポーネント分類ツールの作成
Javaプログラムの変更を支援する 影響波及解析システム
社会シミュレーションのための モデル作成環境
コードクローン検出ツールを用いた ソースコード分析システムの試作と プログラミング演習への適用
通信機構合わせた最適化をおこなう並列化ンパイラ
動的データ依存関係解析を用いた Javaプログラムスライス手法
ソースコードの特徴量を用いた機械学習による メソッド抽出リファクタリング推薦手法
オブジェクト指向プログラムにおける エイリアス解析・視覚化ツールの試作
オープンソース開発支援のための リビジョン情報と電子メールの検索システム
コードクローンの動作を比較するためのコードクローン周辺コードの解析
Javaバイトコードの 動的依存解析情報を用いた スライシングシステムの実現
プログラム理解におけるThin sliceの 統計的調査による有用性評価
バイトコードを単位とするJavaスライスシステムの試作
プログラミング言語論 第5回 手続きの引数機構 変数の有効範囲
オブジェクト指向プログラミングと開発環境
○ 後藤 祥1,吉田 則裕2 ,井岡 正和1 ,井上 克郎1 1大阪大学 2奈良先端科学技術大学院大学
セキュリティ解析アルゴリズムの実現と オブジェクト指向言語への適用に関する一考察
コードクローン分類の詳細化に基づく 集約パターンの提案と評価
Javaバーチャルマシンを利用した 動的依存関係解析手法の提案
コーディングパターンの あいまい検索の提案と実装
JAVAバイトコードにおける データ依存解析手法の提案と実装
インスタンスの型を考慮したJavaプログラムの実行経路の列挙手法の提案
JavaScriptを含んだHTML文書に対する データフロー解析を用いた構文検証手法の提案
復習 2次元配列 4列 j = 0 j = 1 j = 2 j = 3 i = 0 i = 1 i = 2 3行
オブジェクトの協調動作を用いた オブジェクト指向プログラム実行履歴分割手法
静的情報と動的情報を用いた Javaプログラムスライス計算法
プログラムスライスを用いた凝集度メトリクスに基づく 類似メソッド集約候補の順位付け手法
設計情報の再利用を目的とした UML図の自動推薦ツール
依存関係の局所性を利用した プログラム依存グラフの 効率的な構築法
保守請負時を対象とした 労力見積のためのメトリクスの提案
クローン検出ツールを用いた ソフトウェアシステムの類似度調査
メソッドの同時更新履歴を用いたクラスの機能別分類法
開発作業の形式化に基づく プロセス評価 松下誠 大阪大学.
アスペクト指向プログラミングの 動的プログラムスライスへの応用
蓄積されたオブジェクトの動作履歴を用いた 実行履歴削減手法の提案
欠陥検出を目的とした類似コード検索法 吉田則裕,石尾隆,松下誠,井上克郎 大阪大学 大学院情報科学研究科
エイリアス関係を考慮した Javaプログラム用静的スライシングツール
プログラムの一時停止時に 将来の実行情報を提供するデバッガ
動的スライスを用いたバグ修正前後の実行系列の差分検出手法の提案
動的スライスを用いたバグ修正前後の実行系列の差分検出手法の提案
回帰テストにおける実行系列の差分の効率的な検出手法
オブジェクト指向言語における セキュリティ解析アルゴリズムの提案と実現
識別子の読解を目的とした名詞辞書の作成方法の一試案
オブジェクト指向メトリクスを用いた 開発支援に関する研究 --- VC++とMFCを用いた開発を対象として ---
オブジェクト指向言語論 第六回 知能情報学部 新田直也.
Presentation transcript:

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

略歴 平成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.

フォールト位置特定におけるプログラムスライス 実験1 スライス利用 スライスなし 被験者 A1 A2 A3 B1 B2 B3 デバッグ時間(分) 119 128 120 154 175 122.3 149.7 実験2 スライスなし スライス利用 被験者 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を更新する手法を提案

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

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

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

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

コールマークスライシング 依存関係 実行時、関数呼び出し文が実行されたかどうか(コールマーク)をセット 制御依存関係 データ依存関係 実行依存関係 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辺構築機能を追加することで実装可能 ⇒ 実装が容易

実験 3つのプログラム について、 を計算 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更新 … エイリアス解析等への対応 依存キャッシュスライシング … 他言語への実装 オブジェクト指向プログラムへの適用 継承・動的束縛などオブジェクト指向独自の概念への対応