コンパイラバックエンド処理 データフロー解析 : Reaching Definition

はじめに

Qiitaでは、コンパイラの最適化の話が少ないな～と思ったので、コンパイラのバックエンドの話をしようかと思います。
自分はCOINS(コンパイラ共通インフラストラクチャ)や、Ocelotで実装したことがあります。COINSはJavaで、OcelotはC++です。
まぁ、もちろん自作したコンパイラ上に実装しても良いと思いますが、今の時代に一人で現実的なコンパイラを作るのはナンセンスですからね。素直に共通インフラストラクチャとか使うのが良いと思います。

最適化とは

コンパイラは、フロントエンドで字句解析、構文解析などをして、バックエンドでCFG(Control Flow Graph、制御フローグラフ)作成、各種最適化、レジスタ割り付け、実行可能コードの出力などの処理を行います。
今回は、そのうちの最適化の話です。最適化とは、簡単に言ってしまえば、より早く、より効率的にプログラムが動作するように、しかも、プログラムの意味を変えずに、プログラムを変形しようということです。今までに、様々な最適化アルゴリズムが考案されています。

Reaching Definition

今回は、タイトルにもあるようにReaching Definitionの話をします。
これは、ある変数の定義がどこまで到達するのかといった情報をデータフローする解析手法です。

概要

例えば、以下のようなプログラムsample.cがあったとします。

sample.c

void main(int x){
  int a,b,c,d;
  a = 1;
  b = 2;
  if(x < 10){
    a = 5;
  } else {
    b = 3;
    c = a + b;
  }
  d = a + b;
  return;
}

このような場合は、まず、c の値はコンパイル時に判明します。
なぜかというと、c = a + b;の命令には、aについては a = 1; だけ、bについては b = 3; だけの定義が到達するからです。よって、c の値は 1 + 3 だと判明します。
一方、d の値はコンパイル時にはわかりません。
それは、d = a + b; の命令には a,b についての定義が２つ以上到達するからです。
if文のtrue側が実行されたとすると、a = 5; b = 2; が到達し、false側が実行されたとすると、a = 1; b = 3; が到達します。
このように定義がどこにどれくらい到達するのか解析するのがReaching Definitionです。
さらに、上記の c の値のように、定義が一つだけ到達すると分かった時には、そこに値を伝播させることができます。これをConstant propagationと言います。

アルゴリズム

それでは、アルゴリズムの説明に入ります。
まず、CFGの各命令について、以下の表のようにgenとkillの計算をします。

Statement s	gen[s]	kill[s]
d1 : t ← a⊕b	{d1}	def(t) - {d1}
d2 : t ← Mem[x]	{d2}	def(t) - {d2}
d3 : t ← f()	{d3}	def(t) - {d3}

1行目は、何らかの計算をしてtに代入する場合、2行目はメモリからtに値をロードする場合、3行目は関数f()の返り値をtに代入する場合です。２列目は、命令sがあったとき、gen[s]に追加すべき要素です。ここで、d1やd2というのは、各命令につけた番号です。３列目は、命令sがあったとき、kill[s]に追加すべき要素です。ここで、def(t)とは、変数tを定義する全ての命令を表します。
表中にないようなメモリへのストア命令や条件分岐文などはgenとkillの計算には関与しません。

次に、inとoutの計算をします。ある命令nについてのinとoutは以下の数式で計算します。

in[n] = \cup_{p \in pred[n]}out[p] \\
out[n] = gen[n] \cup (in[n]-kill[n])

ここで、pred[n]はnの先行節を表します。上記の式を、すべての命令についてinとoutの変化がなくなるまで繰り返します。以下に、疑似コードを示します。

pseudoCode

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は空集合で初期化します。また、union()関数は引数の和集合を計算する関数です。
これだけだと分かりずらいと思うので、先ほどのsample.cの場合で例を考えてみましょう。

sample

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

まぁ、こんな感じに書けると思います。次に、gen、kill、in、outを計算すると以下のようになります。

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

表中の数字は、各命令の数字に対応しています。
ここで注目すべきなのは、n = 7 のときの in です。in[7] = {1,6}なので、１番と６番の定義が到達しているということです。つまり、7: c ← a + bは7: c ← 1 + 3と置き換えられるということになります。
さらに、定数畳み込み(Constant folding)を適用させれば、7: c ← 4となります。
一方、n = 9 のときに注目すると、９番の命令には定数伝播できないことがわかります。見てわかるように、in[9]には、aについての定義である1と4があり、bについての定義である2と6もありますね。これでは、コンパイル時にどちらの定義を選択すれば良いのかコンパイラは知ることができず、最適化できないということになります。

おわりに

今回は、コンパイラの最適化の一種であるReaching Definitionについて書きました。
今後も、available expressionやliveness analysisについて書こうかと思います。

追記

Available expressionsについて書きました。---Available expressions
Liveness analysisについて書きました。---Liveness analysis
高速化テクニックについて書きました。---データフロー解析高速化テクニック