ループ • • • • 中田育男著コンパイラの構成と最適化朝倉書店, 1999年第１２章第２節５支配関係 B1 • 二つのブロックB1、B2について、プログラムの入口からB2に到達するどの路も必ずB1を通るとき、 B2 B1はB2を支配（dominate）するという。 • B1はB2の支配ブロックである、という。 • B1はB2の支配ブロックであり、かつ B2の後続ブロックでもあれば、ループが形成される。 • B2からB1への辺は戻り辺(back edge)と呼ぶ。支配関係の計算 • DOM(B): ブロックBの支配ブロックの集合 • DOM(B) = {B} ∪ ∩DOM(P) P∈pred(B) • DOM(B)の初期値 – DOM(B0) = {B0} – DOM(B) = ブロック全体 (B≠B0) ループ • DOM(B)∋D • succ(B)∋D • LOOP(D,B) = {D} ∪ {C | CからDを通らずに Bに達する路がある} • Dは頭部（header）という。 • 頭部はループのすべてのブロックを支配する。 • 共通の頭部を持つ異なるループは、１つのループにまとめておく。ループの外への移動 • 移動先 – ループの入口の直前に新設する入口ブロック – 前頭部・前ヘッダ（preheader） • z = x op y : ループ不変な式… xもyも次のどれかに該当する – 定数である。 – この使用に到達する定義はすべてループの外にある。 – この使用に到達する定義はただ１つで、その定義には不変のしるしが付いている。ループの外への移動 • 文「z=x op y」の式「x op y」がループ不変であれば、変数Tを導入して、 T = x op y を入口ブロックに入れ、もとの文を、 z=T とすればよい。ループの外への移動 • 以下の条件が満足されていれば、 Tを使わずにもとの文全体を入口ブロックに移すことができる。 – この文はループのすべての出口のブロックを支配するブロックにある。 – このループの中でzが定義されるのはこの文だけである。 – ループの入口からこの文に達するまでの間に zの使用はない。