研究速報
依存する関係）・データ依存関係（変数の定義–参照関

制限された動的情報を用いたブロック単位スライシン
グ手法の提案高田智規† ,††井上係）を表している．

Agrawal ら [1], [2] によって提案された 動的スライ
スは，注目した文中の変数の値に実際に影響を与えた克郎†（正員）

実行文の集合である．動的スライスは特定の入力デー

A Block Slicing Method Using Lightweight Dynamic Information
Tomonori TAKADA†,†† , Nonmember and Katsuro INOUE† , Member

タに基づいて導出されるため，ソースプログラムのう† 大阪大学大学院情報科学研究科，豊中市

ち実行されなかった部分は自動的に除かれる．このたGraduate School of Information Science and Technology, Osaka University, Toyonaka, 560-8531 Japan†† 日本電信電話株式会社，横須賀市

め，スライスサイズは静的スライスと比べ一般的に小さくなり，フォールト位置特定には好ましい．しかし，Nippon Telegraph and Telephone Corporation, Yokosuka, 239-0847 Japan

動的スライシングでは動的にプログラム文間の依存関係を追跡する必要があるため，多くのメモリや時間をあらまし必要とする．

静的な制御依存情報と動的なデータ依存情報を利用スライスを抽出するためには，実行前解析，実行時したスライシング手法である依存キャッシュスライシ

解析，スライス抽出の 3 段階の計算が必要となる．実

ングは動的スライシングと比べ，少ない実行時オーバ

行前解析時間はプログラムの長さとその構造に依存すヘッドでスライスを求めることが可能である．しかし，る．実行時解析時間は実行系列の長さに依存し，スラ実際のデバッグ段階で使用するためには，さらにオーイス抽出時間は，解析した依存関係の大きさに依存すバヘッドを削減することが求められている．本稿では，る．このため，繰り返し等が多用されるプログラムに依存キャッシュスライシングのオーバヘッドを削減さおいては，実行系列が大きくなり，実行時解析時間がせたブロック単位スライシングの提案を行う．また，非常に大きくなる．

実験を通じて，ブロック単位スライシングは依存キャッデバッグ作業においては，動的スライシングが適しシュスライシングに比べ約 50%実行時オーバヘッドをているが，上記の問題から，解析に必要な時間が非常削減可能であることを確認した．に大きくなる．

キーワード

準動的解析，依存キャッシュスライシ

この問題を解決するために，静的解析と動的解析を組み合わせた準動的解析手法が提案されている．依存

ング，ブロック単位スライシング

1. は じ め にキャッシュスライシング [6] は，このような準動的解析

プログラムスライシング技術を用いることでソース手法であり，簡単なキャッシュを用いることによって，プログラムのうちフォールトに関連する部分のみに注

動的スライシングと比べ実行時解析時間を短縮すると目することが可能である．プログラムスライス（スラともに，静的スライシングと比べスライスサイズを小イス）は関心のある文に含まれる変数に影響を与えるさくすることができる．しかし，その実行時間（実行文の集合を指す．スライスを利用することでデバッグ

時解析時間とプログラム自体の実行時間の和）は静的を効率的に行うことができる [3]．スライシング技術

スライシングの 3 倍〜10 倍程度であり，現実のデバッは大きく静的スライシングと動的スライシングの 2 つ

グ環境においては，さらなるオーバヘッドの削減が求に分類される．

められる．

Weiser [5] によって提案された静的スライス は，特そこで，依存キャッシュスライシングの基本的なア定のプログラム文中のある変数の値に影響を与えるイデアを基に，さらなる効率化を行った，ブロック単可能性のある文の集合である．静的スライスは一般に位スライシングの提案を行う．

サイズが大きく，極端な場合，ソースプログラム全体

2. ブロック単位スライシングがスライスとして抽出される．静的スライシングを

2. 1 概要計算するためには，プログラム依存グラフ（ProgramDependence Graph, PDG ）と呼ばれる有向グラフを用いる．PDG は文間の依存関係を表したグラフであり，を削減するために，複数の文をブロックとして扱い，その節点はプログラム中の文または条件式を，辺は制ブロック単位スライシングと呼ぶ．

御依存関係（ある文の実行有無が条件式の実行結果に
電子情報通信学会論文誌

X

Vol. Jxx–X

依存キャッシュスライシングの実行時オーバヘッド
ブロック単位でデータ依存関係を求める．この手法を以下に，ブロック単位スライシングの計算手順を
No. xx pp. 1–4

xxxx 年 xx 月

1

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

示す．

STEP1 実行前解析 (ブロック化・静的制御依存解析)
ソースプログラムから，以下の手順により，制御依存辺のみを持ちデータ依存辺を持たない PDG の部分
グラフ P DGBL を静的に生成する．
まず，2. 2 節に述べるブロック化アルゴリズムに従い，文の集合とブロックとの対応関係を得る．
次に，ブロックに対応する節点を用意し，ブロック間に制御依存関係が存在すれば，対応する節点間に制御依存辺を引く．ただし，データ依存辺は加えない．
次に，静的スライシングで利用する PDG と同様，文または制御文に対応する節点を用意する．そして，文間に制御依存関係が存在すれば，対応する節点間に制御依存辺を引く．ただし，データ依存辺は加えない．

STEP2 実行時解析 (動的データ依存関係解析)

入力

P : ソースプログラム (文 s1 , s2 , · · · , s n が含まれているものとする)
N : ユーザによって指定されたブロック化因子
出力BS: ブロックの集合
アルゴリズム本体（ 1 ） BS := ⊥，i = 1（ 2 ） i < n である限り，次を実行（ a ） si , · · · , s i+N−1 が同じ制御ブロックに含まれる場
合，または制御文を含むがその配下の文が全てこれらの文集合に含まれる場合 Bj := {si , · · · , s i+N−1 }，i := i + N(ただし，関数境界は越えないものとする)（ b ） si , · · · , s i+N−1 が上記以外の場合 (制御ブロックの境界を越える場合)，ブロック境界を越えないような文をsk とすると，Bj := {si , · · · , s k }，i := k + 1（ c ） BS := BS ∪ Bj

対象プログラムをある入力データで実行する．

図 1 ブロック化アルゴリズム
Fig. 1 Algorithm for creating blocks

実行の際，2. 3 節で示すデータ依存関係抽出アルゴリ
ズムに基き，動的なデータ依存関係を計算し，PDGBLにデータ依存辺を追加する．プログラム実行が終了した時点で，PDGBL の完成となる．

STEP3 スライス計算
PDGBL を用いて，静的スライシングと同様の方法でスライス計算を行う．
例えば，スライシング基準 (sc , v) に関するスライスを抽出する場合，まず，sc に対応する節点から制御依存辺および v に関するデータ依存辺を逆向きに辿るこ入力

P DGBL : 部分的に生成されブロック化された PDG
P : 対象プログラム
I: P への入力
作業変数

P 中の各変数 v に対する依存キャッシュC(v)
出力

OU T : 入力 I に対するプログラム P の実行の出力
P DGBL : 完成した PDGとで到達可能な節点集合を導出する．そして，この節点集合に対応する文が求めるスライスとなる．

2. 2 ブロック化アルゴリズム
2. 1 節の Step 1 で使われるブロック化アルゴリズムを図 1 に示す．
このアルゴリズムでは，ブロック化因子 N に基づき，N 個の文を 1 つのブロックとしてブロック化を行う．ブロック化因子 N はユーザによって指定可能であり，N の値を変化させることにより，ユーザは任意の粒度でのブロック化が可能である．

2. 3 データ依存関係収集アルゴリズム
図 2 に 2. 1 節の Step 2 で使われるデータ依存関係抽出アルゴリズムを示す．まず，プログラム中で用いアルゴリズム本体（ 1 ） P 中の各静的変数 v に対し, C(v) := ⊥{ 各キャッシュの未代入マークによる初期化．
(注) 動的に割当てられる変数は割当てられた時点でキャッシュを用意し，⊥ を代入する． }（ 2 ） P が停止するまで以下を繰り返し実行する{ P を入力 I で最初から停止するまで文ごとに実行 }（ a ） I に関して，P の次の一文 s を実行（ b ） s で 使 用 (参 照) さ れ る 各 変 数 u に つ い て ，uC(u) = ⊥ かつ ，デー タ依存辺 C(u) - B(s) が存
uB(s) を追加する．
在しなければ PDGBL に C(u)ここで，B(s) は s を含むブロックを表す．
（ c ） s で定義される各変数 w について，C(w) := B(s)図 2 データ依存関係収集アルゴリズム
Fig. 2 Algorithm for computing data dependence relations

られる全ての変数 v に対して，キャッシュ（C(v) と記す）を用意する．
プログラムの各実行時点において，C(v) は最も新
しく v を定義した文に対応する節点の属するブロックを保持し，文 s において v が使用（参照）された際，2C(v) が保持する節点から s の属するブロックに対応する節点 (B(s)) に対してデータ依存辺を (すでに存在しなければ) 追加する．一方，s で v が定義された際，C(v) は B(s) に対応する節点に更新する．これらを全レ

ターての変数に対して行う．
配列変数や構造体については，依存キャッシュスライシングと同様，全ての要素に対してキャッシュを用う．プログラム P 2 はクイックソートを行うプログラムであり，キーとデータの 2 つの構成要素を持つ構造体の配列に対し，キーを基に整列を行う．

P 1 に対して 10,000 の要素，P 2 に対して 100,000意する．

3. ブロック単位スライシングの拡張の要素のソートを行う処理について，元プログラム

ブロック単位スライシングの実行時効率および利便（実行時解析を行わない．静的スライシングの場合も性を向上させるため，以下を考える．

含む），依存キャッシュスライシング，ブロック単位ス• スカラ型変数の静的解析

ライシング の実行時解析時間を複数測定し，その平均配列やポインタ型の変数のデータ依存関係を静的に時間を求めた．なお，ブロック単位スライシングにつ解析することは非常に困難であるが，スカラ型変数にいては，3. 節で示した拡張を取り入れたアルゴリズム

ついては比較的容易に解析することが可能である．そを使用した．

こで，PDGBL 作成時に，スカラ型変数のデータ依存

この実験の結果を表 1 に示す

関係についても解析し，実行時にはポインタ・配列・

表 1 平均実行時間 (秒)Table 1 Average Execution Time (Sec.)構造体などの変数についてのみ依存関係を解析することで，実行時オーバヘッドを削減できる．

• ブロック内局所変数の解析省略
ブロック内でのみ使用される変数 (関数の局所変数など) は，ブロック外へ依存関係が伝播することは無P1
P2
元プログラム0.017 0.266
依存キャッシュスライシング 0.141 2.692
ブロック単位スライシング
0.058 1.413(M-PentiumIII 600MHz CPU with 256MB Memory)

い．そこで，このような変数についてはキャッシュの作成・データ依存辺の追加を共に省略することにより，実行時間・消費メモリを削減することができる．

• 基本ブロック (basic block) 単位のブロック化
ブロック化因子の特別な場合として，基本ブロックを一つのブロックとして計算すれば，ユーザが特にブロック化因子を指定する必要の無い場合に有用である．
また，制御構造の境界を越えることが無くなり，無駄なブロックが少なくなると考えられる．ここで，基本ブロックとは，連続する分岐のない文の列のうち，可能な限り大きいものを指す．

4. 実

験

4. 1 概要

ブロック単位スライシングの有効性を確認するため実行時間の測定を行った．依存キャッシュスライシン

4. 2 考察

表 1 より，依存キャッシュスライシングでは元プログラム（静的スライシング）の約 9〜10 倍程度の実行時間となっているのに対し，ブロック単位スライシン
グでは約 3〜6 倍程度となっている．また，ブロック単位スライシングは依存キャッシュスライシングの実行時間は約 1/2 に短縮できていることが分かる．
この理由について以下に簡単な考察を行う．
ブロック単位スライシングでは，ブロック化を行うことにより PDG の節点数を減らすことができる．そのため，実行時に追加するデータ依存辺は依存キャッシュスライシングに比べ少なくなり，また，依存辺の追加に関するオーバヘッドも少なくなる．PDG の節点数を表 2 に示す．

グのオーバヘッドはコンパイラ型言語の場合に特に大きくなる [6] ため，C 言語で記述されたサンプルプログラムを対象とし，動的データ依存収集の動作を追加した．
サンプルプログラムとして，多様なプログラムで用表 2 PDG 節点数
Table 2 The number of nodes in PDG
ブロック化前ブロック化後P12720

P24534

いられるソートプログラムを対象とし，P 1,P 2 の 2 つのプログラムを用いた．対象プログラムとしては，プ

また，関数内局所変数については，依存キャッシュログラム長に対し実行系列が大きくなるもの，つまりスライシングではキャッシュを作成し，そのデータ依繰り返しを多く含むものとするため，ソートプログラ存辺をも追加しているが，ブロック単位スライシングムを選んだ．プログラム P 1 はマージソートを行うプ

ではその局所変数が単一ブロックの中でしか使用されログラムであり，配列に格納されたデータの整列を行無い場合，解析を行わない．これは，頻繁に呼びださ
3電子情報通信学会論文誌 ’xx/xx Vol. Jxx–X No. xx

れ制御構造が単純な小さな関数などについて非常に有効であると考えられる．本実験では，P 2 において，関数内局所変数に関するキャッシュの参照数を平均約1,600,000 回省略することが可能であった．
スカラ型変数の解析については，ブロック単位スライシングでは実行前解析において解析しているため実行時に解析する必要がない．表 3 に，実行時に解析した定義-参照関係の数について示す．スカラ型変数の実行前解析により，大幅に実行時解析のコストを抑えることが可能であることがわかる．
表 3 実行時に解析した定義-参照関係数
Table 3 The number of analysed Def-Use relation during executing sample programs
P1
P2
依存キャッシュスライシング 2,300,000 20,000,000
ブロック単位スライシング
380,000
6,450,000

5. ま と め
一般に，配列やポインタなどを含んだプログラムのデータ依存関係を静的に解析するのは非常に困難であり，また，動的に解析するのは非常に実行時オーバヘッドが必要となる．本稿では，ブロック単位スライシングというアルゴリズムを提案した．この方式では，複数の文をブロックとして扱い，ブロック単位で動的にデータ依存関係を求めることで，実行時オーバヘッドを大幅に削減できる．
今後は，ブロック単位スライシングの正確性について実験を行うとともに，4. 2 節で示したブロック内静的依存解析についても検討，および，ブロック化因子を様々な数値に変動させた場合の，実行時間と正確性についての考察をも行う．また，静的・動的・依存キャッシュスライシング等の機能を実装したデバッグシステ
ム [4] への実装を行い，実ユーザによるデバッグ実験などの検証も行う予定である．

文

献[1] Agrawal, H. and Horgan, J. : “Dynamic Program Slicing”, SIGPLAN Notices, Vol.25, No.6, pp. 246–256, 1990.
[2] Korel, B., and Laski, J. : “Dynamic Program Slicing”, Information Processing Letters, Vol.29, No,10, pp. 155–163 (1988).
[3]

西松 顕, 楠本 真二, 井上 克郎: “フォールト位置特定にお[4]けるプログラムスライスの実験的評価”, 信学技報 SS98-3,
pp.17-24, Mar 1998
佐藤 慎一, 飯田 元, 井上 克郎: “プログラムの依存関係解析に基づくデバッグ支援ツ−ルの試作”, 情処論 Vol.37, No.4,
pp.536-545, Apr 1996
[5] Weiser, M.: “Program Slicing”, Proceedings of the Fifth Interna-4tional Conference on Software Engineering, pp. 439–449 (1981).
[6]高田 智規, 井上 克郎, 芦田 佳行, 大畑 文明: “制限された動的情報を用いたプログラムスライシング手法の提案”，電子情報通信学会論文誌 D-I, Vol. J85-D-I, No. 2, pp. 228-235,(2002).
（平成年月日受付，月日再受付）