はじめに
今回は、前回のReaching Definitionに引き続き、データフロー解析の一つであるAvailable expressionsの話をしようかと思います。
Available expressionsによって、Common Sub-expression Elimination(共通部分式削除、CSE)ができるようになります。
Available expressions
日本語に訳すと、利用可能な式。つまり、プログラム中のあるポイントで利用可能である式があるかどうか解析する手法です。
概要
例えば、以下のようなプログラムsample.cがあったとします。
void main(int a, int b){
int x,y,z;
x = a + b;
if(a < 5){
y = a + b;
} else {
a = 10;
x = a - b;
}
z = a + b;
return;
}
このような場合は、見てわかるように、a + b の値が２回計算されてしまっていて無駄です。
if文のtrue側のy = a + b; の命令を実行するときには、すでに a + b の値を一回計算していて、しかもその値をそのまま使えるので、使ってしまったほうが計算回数が少なくすみます。
しかし、if文を抜けたあとの z = a + b; では、以前に計算した a + b の値は利用することができません。これは、if文のfalse側で、a の値を変更しているからです。
Available expressionsでは、一時変数 t1,t2 を導入して、次のように変形します。
void main(int a, int b){
int x,y,z;
int t1,t2;
t1 = a + b;
x = t1;
if(a < 5){
t1 = a + b;
y = t1;
} else {
a = 10;
t2 = a - b;
x = t2;
}
t1 = a + b;
z = t1;
return;
}
t1はa + bについての一時変数で、t2はa - bについての一時変数です。
Available expressionsでは、まず最初に、
d ← a + b
という計算があったら、a + b用の一時変数tを導入し、
t ← a + b \\
d ← t
という変換をします。このように変換しておけば、データフロー解析後にa + b の値が使えるとわかったら、t ← a + b の命令を消せばいいだけなので、後々楽です。
アルゴリズム
それでは、アルゴリズムの説明に入ります。
Reaching Definitionと同じように、以下の表のようにgenとkillの計算をします。
| Statement s | gen[s] | kill[s] |
|---|---|---|
| t ← a ⊕ b | {a ⊕ b} - kill[s] | expressions containing t |
| t ← Mem[a] | {Mem[a]} - kill[s] | expressions containing t |
| Mem[a] ← b | {} | expressions of the form Mem[x] |
| f(a,b) | {} | expressions of the form Mem[x] |
| t ← f(a,b) | {} | expressions containing t and expressions of the form Mem[x] |
これは、それぞれ以下のような意味です。
１行目：何らかの計算をして、tに代入する場合。
２行目：aの場所のメモリの値を、tにロードする場合。
３行目：aの場所のメモリに、bの値をストアする場合。
４行目：関数f()を呼び出す場合。
５行目：関数f()を呼び出し、その返り値をtに代入する場合。
kill[s]にある、expressions containing t とは、t を含む式のことです。つまり、t の値は変更されたので、t をオペランドに持つような式(t + x など)は利用可能でないからkillするということです。
また、expressions of the form Mem[x]とは、Mem[x]の式(任意の x の値について)をキルするということです。メモリアクセスについては、プログラムのどの場所で、メモリのどの位置にアクセスするかといったことを正確に解析するのが難しいです。なので、メモリに値をストアする可能性がある場合は、Mem[x]形式の式はすべてキルします。
また、表中にないような条件分岐文などは、genとkillの計算には関与しません。
次に、inとoutの計算をします。ある命令nについてのinとoutは以下の数式で計算します。
in[n] = \cap_{p \in pred[n]}out[p] \\
out[n] = gen[n] \cup (in[n] - kill[n])
ここで、pred[n]はnの先行節を表します。上記の式を、すべての命令についてinとoutの変化がなくなるまで繰り返します。以下に、疑似コードを示します。
in[entry_node] ← {};
out[entry_node] ← {all expressions};
foreach n
if n is not entry_node then
in[n] ← {all expressions};
out[n] ← {all expressions};
endif;
endfor;
do
foreach n
in2[n] ← in[n];
out2[n] ← out[n];
foreach p in pred[n]
in[n] ← intersection(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()関数は引数の和集合を計算する関数で、intersection()関数は引数の積集合を計算する関数です。
では、先ほどのsample2.cの場合で、例を考えてみます。
1: t1 ← a + b
1*: x ← t1
2: if a < 5 goto L1 else goto L2
3: L1: t1 ← a + b
3*: y ← t1
4: goto L3
5: L2: a ← 10
6: t2 ← a - b
6*: x ← t2
7: goto L3
8: L3: t1 ← a + b
8*: z ← t1
一時変数を導入してみると、このように書けると思います。
次に、gen、kill、in、outを計算すると以下のようになります。
| n | gen[n] | kill[n] | in[n] | out[n] |
|---|---|---|---|---|
| 1 | {a + b} | {a + b} | ||
| 2 | {a + b} | {a + b} | ||
| 3 | {a + b} | {a + b} | {a + b} | |
| 4 | {a + b} | {a + b} | ||
| 5 | {a + b, a - b} | {a + b} | ||
| 6 | {a - b} | {a - b} | ||
| 7 | {a - b} | {a - b} | ||
| 8 | {a + b} | {a + b} |
a + b を計算している1,3,8番のノードでは、{a + b}をgen[n]に加えています。また、a - b を計算している6番のノードでは、{a - b}をgen[n]に加えています。
5番のノードではaの値を変更しているので、a + b と a - b はキルされます。
8番のノードには、4番のノードから{a + b}が、7番のノードから{a - b}がデータフローされてきますが、それらの積集合を取ると空集合となるので、8番のノードのin[n]は空集合です。
ここで、3番のノードのinに注目してみると、a + b があります。つまり、3番のノードの入口でa + b が利用可能であるので、3番のノードは消去することができます。この操作のことをCommon Sub-expression Elimination(共通部分式削除、CSE)と言います。
つまり、sample2.cをCSEすると、以下のようになります。
void main(int a, int b){
int x,y,z;
int t1,t2;
t1 = a + b;
x = t1;
if(a < 5){
y = t1;
} else {
a = 10;
t2 = a - b;
x = t2;
}
t1 = a + b;
z = t1;
return;
}
上記のsample3.cを見るとわかるように、無駄な計算が省かれ最適化されました。
おわりに
今回は、コンパイラの最適化の一種であるAvailable expressionsについて書きました。
そのうち、Liveness analysisとか書こうと思います。
LCMやSSAのこともそのうち書けたらいいかな～と思います。
関連記事 --- Reaching Definition
追記
Liveness analysisについて書きました。---Liveness analysis
高速化テクニックについて書きました。---データフロー解析高速化テクニック