利用可能な式

共通部分式の削除
•
•
•
•
中田育男著
コンパイラの構成と最適化
朝倉書店, 1999年
第１２章第２節４
利用可能な式のデータフロー解析
• E_GEN(B) = {op(x,y) | p(op(x,y))∈Bで、かつ、
pの後にはp’(def(x))∈Bまたは
p’(def(y))∈Bとなるp’はない}
• E_KILL(B) = {op(x,y) | p(def(x))∈Bまたは
p(def(y))∈Bなるpがある}
– p(def(x)): xが定義される点p
– p(op(x,y)): op(x,y)が計算される点p
利用可能な式のデータフロー解析
• AVAIL(B) = {op(x,y) | プログラムの入口点から
Bに達するどに路にも
op(x,y)があり、それらの最後の
op(x,y)からBまでの間に
p(def(x))もp(def(y))もない}
• AVAIL(B) =
∩ [E_GEN(P)∪{AVAIL(P)-E_KILL(P)}]
P∈pred(B)
AVAILを求めるアルゴリズム
AVAIL(B0) = φ;
for each block B (B≠B0)
AVAIL(B) = U
do {
changed = false;
for each block B {
NEWAVAIL =∩[E_GEN(P)∪{AVAIL(P)-E_KILL(P)}]
P∈pred(B)
if (NEWAVAIL ≠ AVAIL(B)) {
changed = true;
AVAIL(B) = NEWAVAIL;
}
} while (changed);
共通部分式の削除
• p(op(x,y))∈Bかつop(x,y)∈AVAIL(B)で、
Bの中にpの前にxまたはyの定義がなければ、
pでの計算は削除できる。
(a) Bの入り口で利用可能である式op(x,y)の計算を
しているq(z=op(x,y))のすべてについて、
qの直後に
T = z;
を追加する。Tは新しい名前とする。
(b) 上記p(v=op(x,y))をp(v=T)で置き換える。
qの計算
• E_GEN’(B) = {p(op(x,y)) | p(op(x,y))∈Bで、かつ、
pの後にはp’(def(x))∈Bまたは
p’(def(y))∈Bとなるp’はない}
• E_KILL’(B) = {p(op(x,y)) | p’(def(x))∈Bまたは
p’(def(y))∈Bなるpがある}
qの計算
• AVAIL’(B) = {p(op(x,y)) |
op(x,y) ∈AVAIL(B)で、
pはBに到達するop(x,y)を
計算する点}
• AVAIL’(B) =
∪ [E_GEN’(P)∪{AVAIL’(P)-E_KILL’(P)}]
P∈pred(B)
• AVAIL’の初期値は空集合。

Download Report