Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

はじめに

今回は、Reaching DefinitionAvailable expressionsに引き続き、データフロー解析の一つであるLiveness analysisの話をしようかと思います。
これによって、Dead Code Elimination(DCE)ができるようになります。

Liveness analysis

そのまま日本語に訳すと、生存解析。ある変数の定義がプログラムのどこで使われるのか解析する手法です。

概要

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

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}

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

1行目:何らかの計算をして、tに代入する場合。
2行目:aの場所のメモリの値を、tにロードする場合。
3行目:aの場所のメモリに、bの値をストアする場合。
4行目:何らかの条件を判定して、指定した場所へジャンプする条件分岐。
5行目:関数f()を、引数 a と b で呼び出す場合。
6行目:関数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の変化がなくなるまで繰り返します。以下に、疑似コードを示します。

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

sample
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してみると以下のようになります。

sample2.c
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除算も例外が発生する場合がありますね。
そういった命令を安易に削除してしまうと、プログラムの意味が変わってしまう場合があります。最適化は、プログラムの意味を変えない範囲で行われるべきであるので、こういった場合は注意が必要です。

おわりに

今回は、コンパイラの最適化の一種であるLiveness analysisについて書きました。
次は、CFGのことや、スピードアップのことについて書こうかなと思います。
LCMやSSAのことについてもそのうち。

関連記事---Reaching Definition, Available expressions, データフロー解析高速化テクニック

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away