s1,s2,s5,s6,s7

コンパイラ演習
第8回
(2011/12/01)
中村晃一野瀬貴史前田俊行
秋山茂樹池尻拓朗
鈴木友博渡邊裕貴
潮田資秀
小酒井隆広
山下諒蔵佐藤春旗
大山恵弘佐藤秀明
住井英二郎
今回の内容
• データフロー解析とそれに基づく最適化手法
マシン依存性による最適化の分類
• マシン非依存
– 静的に評価出来る部分をコンパイル時に計算
– 無駄な評価・計算を減らす
• マシン依存
– パイプライン効率を上げる
– キャッシュ効率を上げる
• 両者に関係
– 並列度を上げる
– オーバヘッド除去
局所性による最適化の分類
• 局所的最適化
– Peephole 最適化
– 基本ブロック内最適化
• 大域的最適化
– 基本ブロック間最適化
– 関数間最適化
– プログラム間最適化
今回のターゲット
– マシン非依存
– 基本ブロック間
• の
– データフロー解析法
– 最適化手法
• を扱います。
今回説明する基本ブロック間最適化
1.
2.
3.
4.
5.
•
コピー伝播
定数畳みこみ
共通部分式除去
値番号付け
部分冗長性除去
今回は到達定義解析・定義使用解析
に基づくアルゴリズムを紹介します。
基本ブロック間最適化の手順
1. 制御フローグラフを構築
2. データフロー解析をする
3. 最適化を行う
•
以上を個々の関数毎に行う
基本ブロックとは
• 入ってから出るまで一直線な
プログラム片
１．途中での合流が無く、
２．途中からの脱出が無い
• 途中に関数呼び出しを含む
ブロックを許すか否かは
最適化の種類による
基本ブロック
let x = f() in
if x > 0
then
let y = - x in
…
else
let y = x in
…
準備：ループの検出
• MinCaml には明示的なループが存在しない
→ そのままでは関数間解析をしないと
高度な最適化が難しい。
• 単純な方法
– 自己末尾再帰呼び出しを while 型ループへ
n=0
let rec f n =
if n < 10
then (…; f (n+1))
else ()
in f 0
if n < 10
…
n=n+1
準備：代入構文の用意
• ループ作成によって必要になる
変数の更新を表現
let rec f n =
if n < 10
then (…; f (n+1))
else ()
in f 0
if n < 10
…
nn+1
変数の
更新
• 左の様な let 文も右のように変換
let x = if ... then e1 else e2
n=0
if ...
x  e1
x e2
制御フローグラフ
• 関数 body を基本ブロックを頂点、
制御移行を辺として
entry
グラフを作る
• 空の entry,exit ブロックを用意
– 入口・出口を用意しておくと
あとあと楽
exit
データフロー解析 (前方解析)
•
プログラムポイントの集合を P、データの集合を D として以下を定義
–
–
–
–
•
In[p] : D
Out[p]: D
pred: P2P
f p: DD
(ポイント p の入口でのデータ)
(ポイント p の出口でのデータ)
(ポイント p の一つ前のポイントの集合を得る関数)
(ポイント p における伝達関数)
すべてのポイント p について In[p], Out[p] を求める
p1
p2
Out[p1]
Out[p2]
In[p3]
p3
データフロー解析 (後方解析)
•
プログラムポイントの集合を P、データの集合を D として以下を定義
–
–
–
–
•
In[p] : D
Out[p]: D
succ: P2P
f p: DD
(ポイント p の入口でのデータ)
(ポイント p の出口でのデータ)
(ポイント p の一つ後のポイントの集合を得る関数)
(ポイント p における伝達関数)
すべてのポイント p について In[p], Out[p] を求める
p1
Out[p1]
In[p2]
p2
In[p3]
p3
基本となるデータフロー解析
• 到達定義解析
– ある場所で使用される物(変数、式など)が
どこで定義されたか?
⇒ 前方解析
• 定義使用解析
– ある場所で定義された変数が
どこで使用されるか？
⇒ 後方解析
一方から容易に他方を求める事が出来る。
今回は到達定義解析の結果から定義使用解析を行う
到達定義解析
• データフロー解析の一種
• 使用される変数や式が
どこで定義されているかを調べる
• 流れ
– まずプログラムポイントを基本ブロックとして解析
– 続いて基本ブロック毎に、
プログラムポイントを
その中のステートメントとして解析
ブロック単位の到達定義解析：
reach 集合
• reach[B]: 基本ブロック B の入り口に到達する
定義文の集合
reach[B1] = Φ
reach[B2] = {s1, s2, s5, s6, s7}
reach[B3] = {s1, s2, s5, s6, s7}
B1
s1: i = 0
s2: s = 0
B2 s3: if i < 100
– これを計算する事が
解析の目標
s4: t = i
B3 s5: t = 2*t
s6: i = i + 1
s7: s = s + t
ブロック単位の到達定義解析：
def 集合
• def[B]: 基本ブロック B の中の定義文で
B の出口で有効なものの集合
def[B1] = {s1, s2}
def[B2] = Φ
def[B3] = {s5, s6, s7}
B1
s1: i = 0
s2: s = 0
B2 s3: if i < 100
s4: t = i
B3 s5: t = 2*t
s6: i = i + 1
s7: s = s + t
ブロック単位の到達定義解析：
kill 集合
• kill[B]: B の出口で無効化される定義文の集合
– 制御フローは考慮しなくてよい
B 内の文によって無効化され得る全ての定義文を集める。
kill[B1] = {s6, s7}
kill[B2] = Φ
kill[B3] = {s1, s2}
B1
s1: i = 0
s2: s = 0
B2 s3: if i < 100
s4: t = i
B3 s5: t = 2*t
s6: i = i + 1
s7: s = s + t
到達定義解析のデータフロー方程式
X
Ｂ
fB(X)
• とすれば以下を得る。
到達定義解析のアルゴリズム
全ての基本ブロック B について def[B] と kill[B] を計算し、
reach[B] := Φとする
reach[entry] := {arguments, global variables, ・・・}
do {
old_reach := reach
# 集合としてコピー
全ての基本ブロック B について {
全ての基本ブロック b ∈ pred(B) について {
reach[B] := reach[B] ∪ def[b] ∪ (reach[b] ＼ kill[b])
}
}
} while (old_reach != reach) # 集合として比較
到達定義解析の具体例
reach[B1] = Φ
reach[B2] = Φ
reach[B3] = Φ
B1
s1: i = 0
s2: s = 0
B2 s3: if i < 100
def[B1] = {s1, s2}
def[B2] = Φ
def[B3] = {s5, s6, s7}
kill[B1] = {s6, s7}
kill[B2] = Φ
kill[B3] = {s1, s2}
s4: t = i
B3 s5: t = 2*t
s6: i = i + 1
s7: s = s + t
※ここでは entry, exit を省略している
到達定義解析の具体例
reach[B1] = Φ
reach[B2] = {s1,s2}
reach[B3] = Φ
B1∈pred(B2) の def
B1
s1: i = 0
s2: s = 0
B2 s3: if i < 100
def[B1] = {s1, s2}
def[B2] = Φ
def[B3] = {s5, s6, s7}
kill[B1] = {s6, s7}
kill[B2] = Φ
kill[B3] = {s1, s2}
s4: t = i
B3 s5: t = 2*t
s6: i = i + 1
s7: s = s + t
※ここでは entry, exit を省略している
到達定義解析の具体例
B3∈pred(B2) の def
reach[B1] = Φ
reach[B2] = {s1,s2,s5,s6,s7}
reach[B3] = Φ
B1
s1: i = 0
s2: s = 0
B2 s3: if i < 100
def[B1] = {s1, s2}
def[B2] = Φ
def[B3] = {s5, s6, s7}
kill[B1] = {s6, s7}
kill[B2] = Φ
kill[B3] = {s1, s2}
s4: t = i
B3 s5: t = 2*t
s6: i = i + 1
s7: s = s + t
※ここでは entry, exit を省略している
到達定義解析の具体例
reach[B1] = Φ
reach[B2] = {s1,s2,s5,s6,s7}
reach[B3] = {s1,s2,s5,s6,s7}
B2∈pred(B3) の
reach＼kill
def[B1] = {s1, s2}
def[B2] = Φ
def[B3] = {s5, s6, s7}
kill[B1] = {s6, s7}
kill[B2] = Φ
kill[B3] = {s1, s2}
B1
s1: i = 0
s2: s = 0
B2 s3: if i < 100
s4: t = i
B3 s5: t = 2*t
s6: i = i + 1
s7: s = s + t
※ここでは entry, exit を省略している
到達定義解析の具体例
reach[B1] = Φ
reach[B2] = {s1,s2,s5,s6,s7}
reach[B3] = {s1,s2,s5,s6,s7}
変化なし
変化なし
B1
s1: i = 0
s2: s = 0
B2 s3: if i < 100
def[B1] = {s1, s2}
def[B2] = Φ
def[B3] = {s5, s6, s7}
kill[B1] = {s6, s7}
kill[B2] = Φ
kill[B3] = {s1, s2}
s4: t = i
B3 s5: t = 2*t
s6: i = i + 1
s7: s = s + t
※ここでは entry, exit を省略している
ステートメント単位の到達定義解析
• 変数の到達定義解析の場合以下を計算
– reach[s, x] : ステートメント s で使用されている変数 x
を定義している文集合
• s をブロック B の文とすると、reach[s,x] は
– B 内の s の先行命令が x を定義していれば
それのみ
– そうでなければ、reach[B] に含まれる x
を定義している文集合
• として計算できる
ステートメント単位の到達定義解析の例
• 例えば reach[s6,i] についてみてみる
– B3 の先行命令(S4,s5)は I を定義しないので
reach[B] を見る。
s1: i = 0
– reach[B] 内で i を定義している文は
B1 s2: s = 0
s1 と s6
reach[B3] = {s1,s2,s5,s6,s7}
B2 s3: if i < 100
– 従って
reach[s6,i] = {s1, s6}
B3
s4: t = i
s5: t = 2*t
s6: i = i + 1
s7: s = s + t
ステートメント単位の到達定義解析の例
• 最終結果
reach[s3, i] = {s1, s6}
reach[s4, i] = {s1, s6}
reach[s5,t] = {s4}
reach[s6,i] = {s1, s6}
reach[s7,s] = {s2, s7}
reach[s7,t] = {s5}
s1: i = 0
B1 s2: s = 0
B2 s3: if i < 100
B3
s4: t = i
s5: t = 2*t
s6: i = i + 1
s7: s = s + t
定義使用解析
• 以下を計算する
– use[s] : ステートメント s で定義されている変数 x
を使用している文集合
• 計算方法
– use[s] = { t | s ∈ reach[t, x], x は s が定義する変数}
定義使用解析の例
use[s1] = {s3, s4, s6}
use[s2] = {s7}
use[s4] = {s5}
use[s5] = {s7}
use[s6] = {s3, s4, s6}
use[s7] = {s7}
reach[s3, i] = {s1, s6}
reach[s4, i] = {s1, s6}
reach[s5,t] = {s4}
reach[s6,i] = {s1, s6}
reach[s7,s] = {s2, s7}
reach[s7,t] = {s5}
s1: i = 0
s2: s = 0
s3: if i < 100
s4: t = i
s5: t = 2*t
s6: i = i + 1
s7: s = s + t
実際の最適化の例: コピー伝播
• 変数の到達定義解析・定義使用解析を利用
copyprop(prog) {
worklist := (let x = v(変数)の形の文)
while (worklist != Φ) {
s := worklist.pop
foreach(t in use[s]) {
x := s が定義する変数
if (|reach[t,x]| == 1) {
# t に到達する変数が 1 つしかない
t 内の x の使用を v に置換
worklist.add(t) if t が let x’ = v’ の形で worklist に存在しない
}
}
}
}
実際の最適化の例: 定数畳みこみ
• 変数の到達定義解析・定義使用解析を利用
constfold(prog) {
worklist := 定数定義文
while (worklist != Φ) {
s := worklist.pop
foreach(t in use[s]) {
x := s が定義する変数
x を定数値に置換 if reach[t,x] の全てが同じ値を定義
静的に t を評価 if t の全引数が定数
worklist.add(t) if t の計算結果が定数
}
}
}
実際の最適化の例: 共通部分式除去
• 「利用可能な式」の到達定義解析を行う
• ここでは基本ブロック単位の解析を説明する
– Eavail[B]:
– Ekill[B]:
ブロック B の入口で利用可能な式集合
ブロック B 内でオペランドが
上書きされる式集合
– Edef[B]:
ブロックB内にある式で
出口で利用可能な式集合
• として以下を解く (∪でなく∩となる点に注意)
• その後ステートメント単位での解析をする
共通部分式除去の例
x=i*4
y=a+x
reach = {i * 4, a + x}
p = load y
x=i*4
y=b+x
q = load y
reach = {i * 4}
p=i*4
z=a+x
i * 4が共通部分式になっている
※右のパスで x が上書きされるので
a + x はここに到達しない。
共通部分式除去の例
x=i*4
t=x
y=a+x
i * 4 の為の一時変数を作って…
reach = {i * 4, a + x}
p = load y
x=i*4
y=b+x
q = load y
reach = {i * 4}
p=i*4
z=a+x
共通部分式除去の例
x=i*4
t=x
y=a+x
reach = {i * 4, a + x}
p = load y
x=t
y=b+x
q = load y
reach = {i * 4}
p=t
z=a+x
共通部分式を除去
実際の最適化の例: 値番号付け
• 先ほどのアルゴリズムでは
例えば下の様なものが解決出来ない
a=1
b=1
c=a+2
d=b+2
a=b+c
d=b
e=d+c
同じ値を持つが共通部分式じゃない
同じ値を持つが共通部分式じゃない
実際の最適化の例: 値番号付け
• 式の「値」を「番号」で識別して
共通な値を見つける
a=1
b=1
c=a+2
d=b+2
a=①
b=①
c=②
d=②
(②＝①＋２)
a=b+c
d=b
e=d+c
b=①
c=②
a=③
d=①
e=③
（③=①+②)
実際の最適化の例: 部分冗長性除去
• 値番号付けでも
部分冗長なケースは
解決できない
x=a+b
このパスでだけ
a + b が冗長
y=a+b
部分冗長性除去: 簡単なアイデア
• 式を挿入して全冗長にする
z=a+b
x=a+b
z=a+b
y=a+b
部分冗長性除去
• 手順
–
–
–
–
–
共通部分式の除去
危険辺の除去
入口計算・出口計算・挿入点を検査
上安全性・下安全性の検査
挿入点を求める
• 今回はせわしいコード移動 (busy-code-motion) という方法を紹介
– 式をできるだけ前方へ挿入する
• 以下 a + b という形の一つの式に注目する
危険辺の除去
• ２つ以上の後続ブロックを持つブロックから、
２つ以上の先行ブロックを持つブロックへの辺を
新たにブロックを挿入して除去
y=a+b
y=a+b
ここに a + b を挿入すると
後続のパスに影響
ここなら a + b を挿入しても
大丈夫
入口計算・出口計算
• ブロック B 内に a, b への代入文がある場合、
その最後の代入文の直後で分割
– 入口計算: 入口部分にあり、かつ a, b の代入より前にある a + b
– 出口計算: 出口部分にある a + b
x =a+b
a=2
b=x+b
y=a+b
• ブロックの集合をBとして
– NCompa+b: BBoolean
– XCompa+b: BBoolean
– Transpa+b: BBoolean
x =a+b
a=2
b=x+b
y=a+b
入口計算
出口計算
(ブロック B が入口計算を持つ)
(ブロック B が出口計算を持つ )
(ブロック B 内に a, b への代入文がない)
挿入点
• 以下の 2 つのプログラムポイントを「挿入点」と呼ぶ
– 入口挿入点
• 入口計算の直前 (入口計算がなければ基本ブロックの先頭)
– 出口挿入点
• 出口計算の直前 (出口計算がなければ基本ブロックの最後)
x =a+b
a=2
b=x+b
y=a+b
x =a+b
a=2
b=x+b
y=a+b
入口挿入点
入口計算
出口挿入点
出口計算
上安全性・下安全性
• ある挿入点に a + b を代入しても安全かどうか
• 上安全性
– entryからその点までの
どのパスにも a + b があり全部同じ値
• 下安全性
– その点から exit まで
どのパスにも a + b があり全部同じ値
•
•
•
•
NuSafea+b[B] : Boolean
XuSafea+b[B] : Boolean
NdSafea+b[B] : Boolean
XdSafea+b[B] : Boolean
(B の入口挿入点で上安全)
(B の出口挿入点で上安全)
(B の入口挿入点で下安全)
(B の出口挿入点で下安全)
上安全性・下安全性の解析
• NdSafe, XdSafe は以下の方程式で計算できる
• NuSafe, XuSafe も同様
せわしいコード移動
• 下安全で出来るだけ前方の挿入点に
t = a + b を挿入
• NEarlist[B] = trueである B の入口挿入点,
XEarliest[B] = trueである B の出口挿入点に
t = a + b を挿入
• すべての入口計算・出口計算を t に置換
その他最適化のヒント:
Do-All 型ループの検出
• 後の回やる並列化・キャッシュ最適化等に
欠かせない作業
• Do-All 型ループとは
– i = a,a+d,a+2d,…,a+(k-1)d と順番に回すループ
for (i = a; i < n; i += d) {
…
}
• while ループには既に直してあるのだから
インデックス変数 i を見つけてやればよい
Do-All 型ループの検出:
帰納的変数検出
• Do-All 型ループのインデックスは
帰納的変数になっている
– i0 = a
– in+1 = in + d
– ループ脱出条件により
i の上限 (下限) が決定出来る
• 到達定義解析の結果から
右のようなパターンを
見つければよい
i=a
if ループ脱出条件
i=i+d
帰納的変数の検出(例)
s1: i = 0
s2: s = 0
s3: if i < 100
s4: t = i
s5: t = 2*t
s6: i = i + 1
s7: s = s + t
s=0
for (i=0;i < 100; i++)
t=i
t = 2*t
s=s+t
共通課題
• 二つの共通課題のうち
一つ以上を解いてください
課題1
• MinCamlに到達定義解析を実装し
それを用いた最適化 (最低1つ) を実装せよ。
– 第2回で扱った到達定義解析に寄らない最適化
と比較し評価せよ。
課題2
• 今回紹介した単純な部分冗長性除去では
上手く冗長性が除去出来ないプログラムや
遅くなってしまうプログラムがある
• その例を挙げ、改善する方法を考えよ
– 参考文献
• Knoop, J., Ruthing, O., and Steffen, B. Lazy Code Motion. ACM
SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI.
• VanDrunen, T., and Hosking, A.L. Value-Based Partial Redundancy
Elimination, Lecture Notes in Computer Science Vol. 2985/2004,
pp. 167 - 184, 2004.
• Kennedy, R., Chan, S., Liu, S.M., Lo, R., Peng, T., and Chow, F. Partial
Redundancy Elimination in SSA Form. ACM Transactions on
Programming Languages Vol. 21, Num. 3, pp. 627-676, 1999.
コンパイラ係用課題
• 関数間解析・エイリアス解析など
さらに高度な解析と
それを用いた最適化を実装せよ
課題の提出先と締め切り
• 提出先: [email protected]
• 締め切り: 2 週間後 (12/15) の午後 1 時
– コンパイラ係用課題の締め切り: 2012 年 2月 27日
• Subject: Report 8 <学籍番号: 5 桁>
半角スペース 1 個ずつ
– 例： Report 8 11099
• 本文にも氏名と学籍番号を明記のこと
 質問は [email protected] まで

Download Report