Rogue Engineer's Diary / やさぐれ日記(2004-11-14)

2004-11-14

■ [Modern Compiler Implementation in ML] フローグラフを描いて遊ぶ

先週はフローグラフ生成部を組み上げるところまで進めたワケだが、結果が正しいことをどうやって確認しようかと、その後ずっと考え込んでいた。出てきたデータ構造を手作業で覗き込むのではあまりにも手間がかかりすぎる。フローグラフを相手にしているのだから図にして眺めるのが筋だと思うし、そっちの方が絶対面白いであろう、ということで、いろいろと方法を検討する。

フローグラフのデータ構造から、picみたいな描画言語を経由するとツールでうまいこと画像化出来るハズであると信じてGoogleで"graph drawing language"というキーワードで探したところ、Graphvizなるモノが見つかった。テキストファイルでノードの連結状態を記述してやれば、ノードの配置と連結状態を自動的に計算した上で画像化してくれるというツールらしい。まさに今回やろうとしているフローグラフの表示のために作られたかのようなプログラムである。

マニュアルを眺めながら、Graphviz向けにファイルを出力するためのプログラムを1日かけて書く。完成したプログラムにテストプログラムの一つ

/* a simple while */
let
  var x := 5
in
  while x < 10 do x := x + 1
end

を食わせると、こんなファイルが出てくるので、これをGraphvizにかけてやると…おっ、出た出た。

フローグラフの姿が一目瞭然である。右側はマージソートのプログラム（の一部）をグラフ化してみたもの。少々規模が大きくなってもちゃんと図にしてくれる。これは楽しい。

…と、こんなことをやっているうちに日が暮れてしまった。第10章ではフローグラフと共に、interference graphの生成もやらなければならないのだが、そちらの方はまったく手がつかないままになっている、ということで次回はそちらをやっつける予定。Graphvizの出番もまだまだありそう。

本日のツッコミ(全3件) [ツッコミを入れる]

# しゅどう (2004-11-17 00:05)

すばらしー＞Graphviz
K原研の(マクロ)フローグラフPostscript化ツールは、たしか、どなたか（名前失念！）が開発したものだったような。

# ささだ (2004-11-17 14:22)

基本ブロックを1ノードにするとかっこいいんじゃないでしょうか。

# 福盛 (2004-11-17 22:26)

昔のヒトはえらかったですよね（今のヒト達もえらいけど）＞しゅどう
確かに基本ブロックを1ノードにまとめるのはやっておきたいですねぇ。まだまだ遊べそうです＞ささだ

ツッコミ・コメントがあればどうぞ! E-mailアドレスは公開されません。

[TrackBack URL: http://fukumori.org/diary/tb.rb/20041114]

本日のリンク元