Modern Compiler Implementation in ML; 第 18 章
久野靖∗

1999.3.31

イントロ1• Tiger, Java, goto なしの C →縮約可能□ 関数型言語→再帰がループ→任意の再帰では縮約可能と□ プログラムはループで時間を食う→最適化の価値は限らない• でもループって何?

□ 縮約可能だと何がいい?→解析が効率よくなる。

• Webster: 「終了条件が成立するまで繰り返し実行される命令の列」→△□ ループの定義:• でも以下では縮約可能には限定しない。

ノードの集合 S 。ヘッダノード h を含み、以下の条件:

2• S 中のすべてのノードから h へのパスが存在。

支配節□ まずループを見つける必要→支配節について知っておく• h から S 中のすべてのノードへのパスが存在。とよい。

• S の外のノードから S の中のノードへの辺は h への辺のみ。

• ノード s0 :

開始ノード (先行節がない)。

• s0 から n までの経路に常に d が含まれる→ d が n□ 図 18.1。

を支配する• 入口ノード:• すべてのノードは自身を支配

先行ノードがループ外のノードであるようなノード。

• 出口ノード: 後続ノードがループ外のノードであるようなノード。

2.1

支配節発見アルゴリズム□ n の先行節が p1 …pk とする。

• 出口は複数でもよい。ループは入れ子になってもよい。

• d (≠ n) が n を支配⇔ d がすべての pi を支配□ n を支配する節の集合を D[n] と書くと、1.1

縮約可能□ 図 18.2a:D[s0 ] = {s0 }ループではない。

D[n] = {n} ∪ (∩ (p ∈ pred[n])D[p])□ 図 18.2c:

x が y の唯一の先行ノードであるとき (x, y)を併合→ 18.2a と同じに。

• s0 以外の D[n] は全ノードの集合であるように初期• 18.2a と同じになるようなグラフ→縮約可能でない。
• 18.2a と同じものを含まない→縮約可能→ヘッダ設定。

• 反復法で解ける。トポロジカルソートしておけば効率よく解ける。

ノードがある。

• 到達不可能なノードは別扱いすべし。

□ if-then(-else), while, repeat, for, break のみ→縮約可能なグラフだけができる∗ 筑波大学大学院経営システム科学専攻

1

2.2

直接支配

□ 定理:

• ヘッダの支配関係に基づき h を木構造にする□ ループネスト木の葉→最内側ループ

連結グラフで ddomn、edomn → ndome またはedomn□ どのループにも含まれていない節を入れるため、ループ外の節は最外側の「仮想ループ」に含まれていることに□ →すべての n は idom(n)(直接支配節) をたかだか 1 つする。

持つ。

• idom(n) ≠ nプリヘッダ• idom(n)domn

2.6• idom(n) は他の d(n の支配節) を支配しない□ ループ最適化ではループの直前に何かを挿入したい→プ□ s0 以外の節はちょうど 1 つの直接支配節を持つ。

リヘッダ p を用意し、p から h への辺を作り、またループ外から h への辺はすべて p への辺につけかえる。

2.3

支配木

3

□ 直接支配関係のみを辺として持つ木→支配木。

ループ不変式□ ループ内で値が変わらない式は外に出したい (ホイスティ• 支配木の辺はグラフの辺と対応しないものも。

ング)□ hdomn であるような n から h へのグラフの辺→帰辺• 例によって控え目な見積りが必要• 帰辺 1 つにつきループが 1 つある。

□ d : t ← a1 opa2 がループ L について不変であるとは、各ai について

2.4

ループ

• ai が定数であるか、□ n → h が帰辺であるような自然ループとは、hdomx かつ• d に到達する ai の定義がすべてループ外にあるか、x から n への h を通らないパスがあるような x の集合• d に到達する ai の定義が 1 つだけでありかつループ不変のとき• h は 1 つ以上の自然ループのヘッダであることも。
• 自然ループでなくても最適化はできる。

□ これも反復解法で解ける。

• しかし最内側のループから最適化したい。
• ヘッダが共有されているとどっちが内側かわからない。

3.1• よくある解法は、ヘッダを共有するループを併合す□ ホイスティングでプログラムは早くなるが、「正しくなホイスティングい」変形をしてはいけない→図 18.6

ること (結果は自然ループではなくなるかも)。

□ d : t ← a1 opa2 をプリヘッダへ移動してもよい条件:

2.5

入れ子のループ• d がループの全出口を支配するか、ループ出口で生きていない□ A、B がループでヘッダが a、b のとき、adomb であれ
ば B の要素は A の要素に完全に含まれる (B は A の内側• かつ、t の定義がループ内で 1 箇所ループ)• かつ、t がループプリヘッダの出口で生きていない□ 入れ子関係を表すためループネスト木を作る。

□ 暗黙の副作用:演算が例外などを出す場合は手当必要(練習 18.7)。

• G の支配木を作る□ while を repeat-untli に:• すべての自然ループとそのヘッダ h を見つける

上記の 1 番目の条件のため、while ループには適用できないことが→ while を if

• ヘッダ h に対して loop[h] を定める (ヘッダ共有ルー+ repeat-until に変形すれば避けられる。

プの併合)

2

4

帰納変数

• これで乗算がプリヘッダに移せるが、乗算の遅延を動的隠蔽できるマシンだとあんまり効果がない場□ i がループ周回ごとに一定数増減し、j = i・c + d、とい合も。

うのはよくある。その場合、j も一定数増減に書き換え□ 例:られる。

• 帰納変数解析→一定増減の変数を見つける。強さ軽4.3減→乗算を加減算に置き換える。

• i は基本帰納変数。j などは i の派生帰納変数。1 つのものから派生した仲間→ファミリ

帰納変数の削除□ 強さ軽減の結果、いくつかの帰納変数が使われなくなることも。またループ終了判定にのみ使われることも。

□ (i, a, b) 記法…j = a + i・b のときこう書く。

□ いずれも削除できる。

□ 帰納変数が常に一定数増減→リニア帰納変数。18.9a のi はリニアではない。また j も一時的に取り残されるこ4.4とが。

判定の書き換え□ k が「ほとんど不要」とは、その変数がループ不変式に4.1対する比較のためのみに使われ、同じファミリの不要で帰納変数の定義□ 基本帰納変数:ない変数がある場合。
□ そのときは比較を適宜書き換えれば不要にできる。

ループ L 内での定義が i ← i+c、i ← i−c(c はループ不変) であるような変数。
□ 派生帰納変数:□ 制約:

k が L 内で派生帰納変数とは:変形時にきっちり割り切れないことも。またループ不変式の符号が不明で比較方向が分からないことも。

• L 中の k の定義が 1 つだけで k ← j・c、k ← j + d、c、d はループ不変、j は帰納変数であるとき。
• かつ、j が i の派生帰納変数であるなら、

□ 例:

5

• (a)k の定義に到達する j の定義はループ中にあるものだけで、配列の範囲検査□ うーん…

• (b) かつ、j の定義から k の定義までの間のいかなるパスにも i の定義がないとき。

6□ j が (i, a, b) なら k は (i, a, b・c) または (i, a + d, c)。

□ 本体が小さく、ループ制御の比率が高い場合に。

• 引くときは c をマイナスとして扱う (時として問題があることが…)□ 帰納変数を毎回増やさずまとめて扱うことも。
□ 半端な周回は出口で処理する。

□ 除算も 1/c 倍と考えてよい。ただし誤差の問題も。整数除算はどうしょうもない。

4.2

ループ展開

演算強さの軽減□ 多くのマシンで乗算は加減算より遅い。
□ j が (i, a, b) のとき、i ← i + c の直後に j ′ ← j ′ + c・b を入れ、j の定義を j ← j ′ にする。c・b がループ定数ならプリヘッダで計算できる。j ′ の初期設定も必要。

• j を j ′ で置き換えるのは、標準のコピー伝播によればよい。

3