Dead Code Elimination(無用コード除去, DCE)

はじめに

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

Liveness analysis

そのまま日本語に訳すと、生存解析。ある変数の定義がプログラムのどこで使われるのか解析する手法です。 これによって、無用コード除去(Dead Code Elimination, DCE)ができるようになります。

概要

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

void main(int v){
  int a,b,x;
  a = 1;
  b = 2;

  if(v < a){
    x = a + b;
  } else {
    a = 10;
    b = 5;
  }
  a = 100;
  x = a * b;
  b = 20;
}

このような場合は、if文のfalse側の a = 10; で格納された a の値は使われないです。また、最後の b = 20; の b の値もその後使われません。 そのような使われない値はレジスタに保存しておくのも無駄であるので、命令を削除してしまおうというのがDead Code Eliminationです。

アルゴリズム

それでは、アルゴリズムの説明に入ります。 genとkillの計算表は以下のようになってます。

Statement s	gen[s]	kill[s]
t ← a ⊕ b	{a, b}	{t}
t ← Mem[a]	{a}	{t}
Mem[a] ← b	{b}	{}
if a < b goto L1 else goto L2	{a, b}	{}
f(a,b)	{a, b}	{}
t ← f(a,b)	{a, b}	{t}

これは、それぞれ以下のような場合です。

１行目：何らかの計算をして、tに代入する場合。 ２行目：aの場所のメモリの値を、tにロードする場合。 ３行目：aの場所のメモリに、bの値をストアする場合。 ４行目：何らかの条件を判定して、指定した場所へジャンプする条件分岐。 ５行目：関数f()を、引数 a と b で呼び出す場合。 ６行目：関数f()を引数 a と b で呼び出し、その返り値をtに代入する場合。

次に、inとoutの計算式を示します。

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

ここで、succ[n]はnの後続節を表します。このLiveness analysisは、Reaching DefinitionやAvailable expressionsと違い、プログラムの実行順とは逆順でデータフロー解析をしていきます。この逆順の解析をbackward dataflow analysisと言います。 上記の式を、すべての命令についてinとoutの変化がなくなるまで繰り返します。以下に、疑似コードを示します。

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

まず、inとoutは空集合で初期化します。そのあと、データフロー方程式に沿って各inとoutを計算していきます。ここで、気を付けなければならないのが、バックワード解析では、outの方から計算します。また、union関数は引数の和集合を計算する関数です。 では、先のsample.cで例を考えてみましょう。

1: a ← 1
2: b ← 2
3: if v < a goto L1 else goto L2
4: L1: x ← a + b
5 goto L3
6: L2: a ← 10
7: b ← 5
8: goto L3
9: L3: a ← 100
10: x ← a * b
11: b ← 20

次に、gen、kill、in、outを計算すると以下のようになります。

n	gen[n]	kill[n]	in[n]	out[n]
1		{a}	{v}	{a, v}
2		{b}	{a, v}	{a, b, v}
3	{a, v}		{a, b, v}	{a, b}
4	{a, b}	{x}	{a, b}	{b}
5			{b}	{b}
6		{a}
7		{b}		{b}
8			{b}	{b}
9		{a}	{b}	{a, b}
10	{a, b}	{x}	{a, b}
11		{b}

バックワード解析なので、11番のノードのoutから計算していきます。 ここで、注目すべきなのは、6番のノードのoutです。6番のノードでは、a ← 10 という操作をしていますが、out[6]に a がないので、その値は今後使われないということがわかります。同様に、11番のノードにも注目してみると、out[11]には b が含まれないので、この b の値は今後使われないということがわかります。 使われないなら無駄なので削除してしまいましょうということで、sample.cをDCEしてみると以下のようになります。

void main(int v){
  int a,b,x;
  a = 1;
  b = 2;

  if(v < a){
    x = a + b;
  } else {
    b = 5;
  }
  a = 100;
  x = a * b;

sample2.cでは、無駄な命令が省かれて最適化されました。

DCEの注意点

sample.cは簡単なプログラムだったので、この値は使われない ⇒ よし、消してしまおう！ というようにできたのですが、いつでもこのようにできるとは限りません。 DCEで考慮しなければならない場合は、例外処理を発生させる可能性のある命令がある場合です。 普通の計算でもオーバーフローすると例外が発生する場合がありますし、0除算も例外が発生する場合がありますね。 そういった命令を安易に削除してしまうと、プログラムの意味が変わってしまう場合があります。最適化は、プログラムの意味を変えない範囲で行われるべきであるので、こういった場合は注意が必要です。

参考記事

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