netail.net

_ タイムゾーン的には ▲

日本時間とずれているのを忘れて昨日書いてしまったので直しました．とりあえずカナダ時間で書くことにします．

_ [論文][ツール] ポインタ解析アルゴリズムのためのデータベースbddbddb ▲

John Whaley, Monica S. Lam: Cloning-Based Context-Sensitive Pointer Alias Analysis Using Binary Decision Diagrams.

Proceedings of PLDI 2004, pp. , Washington, DC, USA, June 2004.

いわゆるポインタ解析アルゴリズム(Points-To Set Analysis)の提案論文．

最初に，recursive call がある部分はループになっている部分(Strongly Connected Components)を１ノードに置換することでaccyclic graphへ変換する．

次に，呼び出し場所が違う場合，メソッドのグラフを呼び出し箇所ごとに丸ごとコピーする（"Cloning-Based"と言っているのはそのため）．

これらの作業の結果，Call Path ごとに完全に独立したグラフが出来上がる．この上で context-insensitive 解析を実行すれば，context-sensitive な結果が得られることになる．

ただし，普通にコピー操作を実行してしまうと必要な記憶容量が膨大になってしまうので，BDD-Based Deductive DataBase（略して bddbddb）を使ってデータを保存し，その上で論理型言語のDatalogを使ってデータ操作することを提案している．Datalogのプログラムのうち，特定のサブセットだけを扱うことでパフォーマンス向上している様子．

論文は，上記のアイディアと，Datalog言語で定義された解析アルゴリズムを解説している．，基本の代入関係から Points-To 解析をすることで型の到達可能性をちゃんと考慮したコールグラフを作成し，そこから必要なコピー操作を行ってグラフを call path 単位に分解し，その上で context-insensitive な points-to 解析を行う．

アプローチとしては，context-sensitive にしようとしたときのデータ量の爆発を BDD によって抑えようというものだと考えられる．Datalog はリレーショナル代数の処理を書きやすく，リレーションをBDD上で表現して，DatalogをBDD上の操作にマップするというところが工夫で，しかもDatalogを使ってアルゴリズムが比較的簡潔に示されている点はけっこうえらい（AからBに代入があって，BからCに代入があるときAからCに代入があると考える，といったようなルールをDatalogは簡潔に記述できる）．

bddbddb 自体は，β版という位置づけだが，sourceforge で公開されている．使い方については，ドキュメントがあまりちゃんと用意されてないので，ちょっと調査中．正直，パフォーマンス上の工夫が凝らされた解析ツールは貴重な存在なので，今回は少しまじめに調べている．