Reaching Definition

はじめに

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

最適化とは

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

Reaching Definition

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

概要

例えば、以下のようなプログラム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の変化がなくなるまで繰り返します。以下に、疑似コードを示します。

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の場合で例を考えてみましょう。

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もありますね。これでは、コンパイル時にどちらの定義を選択すれば良いのかコンパイラは知ることができず、最適化できないということになります。

参考記事

Common Sub-expression Elimination
Dead Code Elimination
CFG，トポロジカルソート，Bit Vector，ワークリストアルゴリズム
Lazy Code Motion