7.2 生存変数解析モジュール

データフロー解析手法を実際のOCamlプログラムとして実装するための素材として，簡単なデータフロー解析を行うモジュールが配布コード中に含まれている．cfg.ml，dfa.mlには汎用的なデータフロー解析モジュール（前者は制御フローグラフ関連，後者は解析本体）が定義されており，また，live.mlはそれらを使って生存変数解析を行うモジュールである．なお，配布コード中では，仮想機械コード中の各地点（命令の前後）におけるデータフロー値の集合をプロパティ(property)と呼ぶ．

生存変数解析モジュールを試しに使ってみよう．minimlcコマンドに-Gオプションをつけて：

$ ./minimlc -G
# 1+2*3;;
  ...
#

のように実行すると，次のような制御フローグラフ (control-flow graph)が画面に表示されるはずである．

制御フローグラフ中の<BEGIN: 関数名>と<END: 関数名>は，それぞれプログラムの先頭と末尾に追加したダミーの文である．制御フローグラフの入口と出口のノードをこのように単一のノードにまとめ，入口ノードへ入ってくるエッジや出口ノードから出ていくエッジをなくすことで，データフロー解析が簡単になることが多い．

生存変数解析を行うには，minimlcコマンドに最適化オプション-Oを同時につける．

$ ./minimlc -O -G
# 1+2*3;;
  ...
#

のように実行すると，解析結果の埋め込まれた次のようなグラフが画面に表示されるはずである．

各文の前後に埋め込まれている「{...}」が，そのプログラム地点におけるプロパティ（生存変数の集合）を示している．たとえば，「ret t0」の直前では，返り値の入っている局所変数t0は生きている．そのt0は一つ前の「add t0, 1, t1」で局所変数t1の値を使って定義されているので，その直前ではt0は死んでおり，t1は生きている．

もう少し複雑なプログラムを解析してみよう．ループ構文をつかって掛け算を行なう次のコード：

let e = 8 in
let mult8 = fun x ->
  loop c = (x, 0) in
    if 0 < c.1 then
      recur (c.1 + (-1), c.2 + e)
    else c.2 in
mult8 9;;

の制御フローグラフ（解析結果ありとなし）を，それぞれ以下に示す．なお，配布コード中のデータフロー解析モジュールは関数単位でしか解析を行なわないため，関数_toplevelと関数_b__f0の2つのグラフに分かれている．関数_toplevelのグラフ中のcall命令と，<BEGIN: _b__f0>と<END: _b__f0>を結んでやると関数呼出し間のプロパティの伝搬を考慮した，より正確な解析が可能だが，この実験では扱わないことにする．