netail.net

_ 論文 ▲

David Binkley and Mark Harman. Results From a Large-Scale Study of PerformanceOptimization Techniques for Source Code Analyses Based on Graph Reachability Algorithms. 3rd IEEE International Workshop on Source Code Analysis and Manipulation (SCAM 2003). 27th September 2003, Amsterdam, Netherlands. pages 203-212.

大規模 C プログラムに対するスライス計算をするときに，グラフを事前にどういじったらどのくらい高速化したか，という最適化の実験の話．

Strongly Connected Components の接続の１頂点化，SCC に対するデータ構造的なサポート導入，頂点のトポロジカルソート導入，推移的な辺の除去，というようにだんだん最適化している．

実験の適用対象はけっこう大規模で（というか他の論文と同じだが）100万行分くらい．とはいえ，全部で100万行なので，この書き方は誤解を招きそう．平均的には，３倍くらいの高速化をしている．

例によって，評価している時間はスライス計算の時間のみでグラフ構築時間を見ていない．実はグラフ構築に激しく時間かかってたりしないよなぁ，とちょっと邪推したくなるのだが．CodeSurfer を使ってる人たちで，SDG (System Dependence Graph) 構築時間について言及している人を，あまり見たことがない．昔はとても遅かったらしいが，今はどうなんだろう．

_ 論文 ▲

Laura K. Dillon, R.E.Kurt Stirewalt:Lightweight Analysis of Operational SpecificationsUsing Inference Graphs.

Operational Specifications というのはLOTOS などの形式言語のことらしく，色々な言語に対応するために式評価を Inference Graph としてアーキテクチャ構築で使うコンポーネント図みたいな部品を合成したデータフローグラフとして表現すれば，入力値が要らないものから順番に評価していけば結果が取れますね，という感じ．

何が lightweight なのかはよく分からないが，ルールベースで自動生成するところなのだろうか．inference graph の有用性はいまひとつ分からない．

_ 論文 ▲

David Binkley and Mark Harman. An Empirical Study of Predicate Dependence Levels and Trends 25th IEEE/ACM International Conference on Software Engineering (ICSE 2003). 3-10 May, 2003. Portland, Oregon, USA, Pages 330-339.

プログラムの中に登場する predicate から参照できる Formal parameters の数と，predicate で実際に使われるパラメータの数に関する統計を取ってみた，という論文．predicate の定義が曖昧だが，たぶん if など制御文などで使われる変数式全般．

対象のプログラムは20個の C プログラムで，最大で160KLOCくらい．Predicates per KLOC はどのプログラムでも変わらなかったらしい．

で，結果としては，使えるパラメータ数が増えていくに従って，だんだん参照可能なパラメータは増えていくが，実際に使われるパラメータはあまり増えないので，コンテキストへの依存度（使われる率）は下がっていくらしい．ただし，グローバル変数に関してはそういう関係がなく，グローバル変数が増えるほど使われる傾向にあったらしい．

で，依存度が低ければスライスサイズなども小さくなるので人間の労力を大きく削減できるだろう，ということになる．参照可能な Parameter の数さえ数えればだいたいの傾向がわかって，しかもそんなに計算コストは高くないので便利そう？これ単体で，どうこうできるものではないような気もするが．

_ 論文 ▲

David Binkley, Mark Harman:A Large-Scale Empirical Study of Forward and Backward Static Slice Size and Context Sensitivity.19th IEEE International Conference on Software Maintenance (ICSM 2003). Amsterdam, The Netherlands, 22-26 September 2003. Pages 44-53.

プログラムスライスを全部のスライス基点から計算することで統計的に比較をしている論文．実験時のスライス基点については，基点の選び方が効いてくるので，とりあえず全部計算するのがいい，と思っている様子．

対象プログラムは C で書かれた43プログラム，合計100万行ばかり．静的スライスの計算は CodeSurfer で計算されたもの．グラフ中でループになっているようなStrongly Connected Components (SCC) を１頂点として集約して，手続き内頂点はトポロジカルソートしてから，計算している．

グラフ構築は置いておいて，計算そのものは平均 3000KLOC/sec くらいのペースで処理が進んだらしい．(大きいものほど遅くて，100KLOC/sec を切るものもいくつか)

スライスサイズは，プログラム全体の７％~６０％程度．また，context-sensitive （ある手続きに複数の呼び出し文があるときにそれらを区別する）を省略すると，スライスサイズが sensitive なときの50％増しくらい（物によっては数倍）になったらしい．

ちなみに，forward slice と backward slice とを比べるとforward slice のほうがサイズが小さくなるらしい．何となく正しいような気はするけど．

context-sensitivity に関しては色々研究があるらしくて，呼び出し列を call string という文脈自由文法扱いにしてスライスサイズを減らすための情報に使うらしい．引用されているのは次の二つ．

Krinke, J.: Evaluation context-sensitive slicing and chopping. ICSM 2002, pp.22-31.

Agrawal, G. and Guo, L.: Evaluating explicitly context-sensitive program slicing. Workshop on Program Analysis for Software Tools and Engineering, pp.6-12, 2001.