CFG，トポロジカルソート，Bit Vector，ワークリストアルゴリズム

はじめに

この記事は，以前に私がQiitaに投稿した記事である． ふと，はてなブログにも残しておきたいと思ったので，移植する．

Control Flow Graph(CFG)

CFGとは、基本ブロック(basic block)をノードとするグラフのこと。 まず、基本ブロックとは何かというところから説明したいと思います。

基本ブロック(basic block)

ある命令 n が唯一の先行節 p を持ち、また p の唯一の後続節が n であるとき、p と n の gen、kill、in、out を合わせて考えることができ、p と n を一つのノードにまとめることができます。 これが、基本ブロックの根底にある考え方です。基本ブロックは、次の定義を満たします。

1. 基本ブロック内の最初の命令は、ラベル付きである。
2. 基本ブロック内の最後の命令は、無条件ジャンプ、または条件付きジャンプである。
3. 基本ブロック内のその他の命令は、ラベル付き、無条件ジャンプ、条件付きジャンプのどれでもない。

つまり、基本ブロックの途中では、どこかに分岐することもなく、どこかから合流することもないということです。また、この定義より、基本ブロック内の最初と最後の命令以外は、常に唯一の先行節と唯一の後続節を持ちます。よって、基本ブロックを１単位として、gen、kill、in、out の計算をすることができます。 簡単な場合として、命令 n が唯一の先行節 p を持ち、p の唯一の後続節が n であるときを考えてみます。

上の図みたいなのを想像してください。 外側の赤い枠が、p と n を合わせてできた基本ブロックだとします。その基本ブロックの in と out を、in[pn]、out[pn] とします。すると、見てわかるように、in[pn] は in[p] と等しく、同様に、out[pn] は out[n] と等しくなります。また、p と n はお互いが唯一の先行節、後続節の関係なので、out[p] と in[n] も等しくなります。 ここで、Reaching Definitionのデータフロー方程式を考えてみましょう。out[n]は以下のように書けます。

out[n] = gen[n] \cup (in[n] - kill[n])

in[n] = out[p] より、

out[n] = gen[n] \cup ((gen[p] \cup (in[p] - kill[p])) - kill[n])

これを少し整理してみると、

out[n] = (gen[n] \cup (gen[p] - kill[n])) \cup (in[p] - (kill[p] \cup kill[n]))

このように書けます。 これはつまり、この p と n を合わせてできた基本ブロックの gen[pn] と kill[pn] が次のように書けることを意味しています。

gen[pn] = gen[n] \cup (gen[p] - kill[n]) 
kill[pn] = kill[p] \cup kill[n]

よって、out[n] = out[pn]、in[p] = in[pn] なので、次の式が得られます。

out[pn] = gen[pn] \cup (in[pn] - kill[pn])

この out[pn] が、 p と n を合わせてできた基本ブロックの out の値です。これで一つの命令単位でなく、一つの基本ブロック単位で in と out を計算することができます。 このようにして、基本ブロック単位でデータフロー方程式を解くことで、より高速に解を得ることができます。

基本ブロックのトポロジカルソート

トポロジカルソートとは、グラフ理論におけるノードの順序付け方法の一つです。 これをCFGに対して適用すると、あるノードが実行されるとき、そのノードのすべての先行節が実行されているように、ノードを順序付けすることができます。 例えば、次のようなCFGがあったとします。

各ブロックの左側の黒い数字は、このCFG内のそのブロックの固有の番号(basic block id)です。このCFGにトポロジカルソートを適用させると、ブロックを辿る順序は、各ブロックの右側の赤い数字の順番になります。上の図を見ると、あるブロックに到達したときには、そのブロックの全ての先行節がすでに訪問されている状態になっていることがわかると思います。 トポロジカルソートを求めるアルゴリズムは色々あるらしいですが、ここでは深さ優先探索(depth first search)を用いた方法を紹介します。

function DFS(n):
  if visited[n] = false
    visited[n] ← true;
    foreach s in succ[n]
      DFS(s);
    endfor;
    topo_sorted[N] ← n;
    N ← N - 1;
  endif;
endfunction;

procedure Topological_Sort:
  N ← the number of nodes
  foreach n : 0 to N
    visited[n] ← false;
  endfor;
  DFS(entry_node);
endprocedure

Topological_Sort手続きが終わったときに、topo_sorted配列に格納されているのがトポロジカルソートされたブロックの順序です。 Reaching DefinitionやAvailable expressionsなどは、先行節のoutの情報を用いてinを計算するforward analysisなので、全ての先行節がすでに訪問され、outが計算されていれば、効率よくデータフロー解析を行うことができます。なので、forward analysisでは、このトポロジカルソートした順序でブロックを訪問します。 また、Liveness analysisなどのbackward analysisは、逆に後続節のinの情報を用いてoutを計算するので、トポロジカルソートの逆順でブロックを辿る必要があります。逆トポロジカルソートは、上記のアルゴリズムで、entry_nodeではなくexit_nodeからDFSを適用し、DFS関数内で後続節の代わりに先行節へのエッジを辿ることで得られます。

Bit Vector

データフロー解析では、フローされているデータは何らかの集合です。それは、一つの命令だったり、変数だったりしますが、そのような有限集合は、Bit Vectorで表すことができます。 Bit Vectorで表すと何がうれしいかというと、集合のAND演算やOR演算を高速に処理することができるようになります。

Reaching Definitionでの例を考えてみます。

1: a ← 1
2: b ← 2
3: if x < 10 goto L1 else goto L2
4: L1: a ← 5
5: goto L3
6: L2: b ← 3
7: c ← a + b
8: goto L3
9: L3: d ← a + b

n	gen[n]	kill[n]	in[n]	out[n]
1	1	4		1
2	2	6	1	1,2
3			1,2	1,2
4	4	1	1,2	2,4
5			2,4	2,4
6	6	2	1,2	1,6
7	7		1,6	1,6,7
8			1,6,7	1,6,7
9	9		1,2,4,6,7	1,2,4,6,7,9

このような例を考えてみたとき、例えば、９番のノードの in は、５と８番のノードの out の和集合で表されます。これをBit Vectorで表してみると、

	1	2	4	6	7
out[5]	0	1	1	0	0
out[8]	1	0	0	1	1
in[9]	1	1	1	1	1

このようになります。out[5]は２と４番の命令に対してビットが立っていることを表し、同様にout[8]は１と６と７番の命令に対してビットが立っていることを表しています。

in[9] = out[5] \cup out[8]

であるので、上の表を見ても分かるように、ビットのOR演算をした結果が、in[9]に格納されます。 逆に、積集合を計算したいときは、ビットのAND演算をすれば良いのです。 このように集合をビット演算で計算できるので、より高速にデータフロー解析をすることができるようになります。

ワークリストアルゴリズム

これは、データフロー方程式を再計算しなければならないところだけ、再計算するというアルゴリズムです。例えば、Reaching Definitionのアルゴリズムはこのように書けるのでした。

foreach n
  in[n] ← {}; 
  out[n] ← {}; 
endfor; 
do 
  foreach n 
    in2[n] ← in[n]; 
    out2[n] ← out[n]; 
    foreach p in pred[n]
      in[n] ← union(in[n],out[p]);
    endfor;
    out[n] ← union(gen[n],in[n]-kill[n]);
  endfor;
while in[n] = in2[n] and out[n] = out2[n] for all n;

このアルゴリズムでは、いずれかのin,out集合が変更されると、また全ての命令についてループを回し、再計算していました。これだと、再計算する必要のないところまで再計算していて、非効率です。そこで、再計算されるべきところだけワークリストに保存して、再計算するというのがこのアルゴリズムです。 Reaching Definitionのワークリストアルゴリズムは、以下のように書くことができます。

worklist ← set of all nodes;
while worklist ≠ empty
  pop n from worklist;
  old_out ← out[n];
  foreach p in pred[n]
      in ← union(in,out[p]);
  endfor;
  out[n] ← union(gen[n],in-kill[n]);
  if old_out ≠ out[n]
    foreach s in succ[n]
      if s ∉ worklist
        push s into worklist;
      endif;
    endfor;
  endif;
endwhile;

ループのないCFGならトポロジカルソート順に基本ブロックを訪問すれば、全ブロックの計算は２回で済みますが、ほとんどのプログラムはループを含んでいます。ループがあると、全ブロックの再計算が何回も行われることもあり、非効率的です。しかし、このワークリストアルゴリズムでは、再計算はループの中だけに留まるので、より効率的にデータフロー方程式の解を得ることができます。

参考記事

Reaching Definition
Common Sub-expression Elimination
Dead Code Elimination

Lazy Code Motion