はじめに
今回は、データフロー解析において基本的な知識であるControl Flow Graph(CFG)やBit Vector、CFGのノードの辿り方などを書いていきたいと思います。
データフロー解析の具体的な手法については、以下の記事を参考にしてみてください。
Reaching Definition
Available expressions
Liveness analysis
Control Flow Graph(CFG)
CFGとは、基本ブロック(basic block)をノードとするグラフのことで、少し計算機科学の分野をかじったことがある人なら聞いたことがあると思います。
まず、基本ブロックとは何かというところから説明したいと思います。
基本ブロック(basic block)
ある命令 n が唯一の先行節 p を持ち、また p の唯一の後続節が n であるとき、p と n の gen、kill、in、out を合わせて考えることができ、p と n を一つのノードにまとめることができます。
これが、基本ブロックの根底にある考え方です。基本ブロックは、次の定義を満たします。
- 基本ブロック内の最初の命令は、ラベル付きである。
- 基本ブロック内の最後の命令は、無条件ジャンプ、または条件付きジャンプである。
- 基本ブロック内のその他の命令は、ラベル付き、無条件ジャンプ、条件付きジャンプのどれでもない。
つまり、基本ブロックの途中では、どこかに分岐することもなく、どこかから合流することもないということです。また、この定義より、基本ブロック内の最初と最後の命令以外は、常に唯一の先行節と唯一の後続節を持ちます。よって、基本ブロックを１単位として、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ならトポロジカルソート順に基本ブロックを訪問すれば、全ブロックの計算は２回で済みますが、ほとんどのプログラムはループを含んでいます。ループがあると、全ブロックの再計算が何回も行われることもあり、非効率的です。しかし、このワークリストアルゴリズムでは、再計算はループの中だけに留まるので、より効率的にデータフロー方程式の解を得ることができます。
おわりに
今回は、データフロー解析を行う上で基本的事項である各種テクニックについて書きました。
近年では、CPU一つ当たりの性能は頭打ちになってきましたが、GPUを用いた高速計算はまだまだ発展途上で、様々な分野に応用されている途中です。なので、コンパイラの最適化技術というのは、今後さらに需要が高まります。こういう記事を読んで、少しでもコンパイラの最適化について興味を持ってもらえたら嬉しいです。
逆に、最近工学的な発展がめざましい機械学習、人工知能の分野は、実は理学的な研究ではすでにほぼ終わっていると言われています。ハードウェアが進化してきたので、それに前からあった理学の知識を乗っけたのです。今は、人工知能ブームなので人工知能を学ぶのもいいと思いますが、コンパイラの分野にも興味を持ってもらえたらなと思います。
今後も、LCMやSSAなどコンパイラの最適化手法についてそのうち書こうと思います。