Modern Compiler Implementation in C 19章後半(451ページから） 早稲田大学 理工学部 情報学科 上田研究室 高木祐介 1999年7月12日

19章後半 概要 19.3 SSAを利用する最適化アルゴリズム 19.4 配列、ポインタ、メモリ 19.5 制御依存グラフ 19.7 関数型中間表現

19.3節「SSAを利用する最適化 アルゴリズム」 死亡コード除去 単純な定数伝播 条件付き定数伝播 支配性を保つ

SSAグラフを表現するオブジェクト（451ページ） 文 ブロック、直前・直後の文、定義・使用する変数の5属性を持つ。 代入、φ関数、フェッチ、ストア、分岐の5種類。 変数 定義された場所、使用される場所のリスト ブロック 文のリスト、直前ブロックの順序付きリスト、直後ブロック

死亡コード除去（451-452ページ） SSAを使うと死亡コード解析が簡単。 変数の定義が死亡しているのは、使用リストが空のときだけ。 変数の定義は、その変数の全使用を支配する。 非SSAでは、使用リストが空でなくても死亡の場合があった。（同じ変数の、別の定義を使用する場合）

アルゴリズム19.12（452ページ） ＳＳＡを利用した死亡コード除去 W ← SSAプログラム中の全変数のリスト while Wが空でない Wから変数vを除去する if vの使用リストが空である Sは、vを定義する文であるとする if Sは、vに代入する以外の副作用がない プログラムからSを除去する for Sで使用されていた各変数x_i x_iの使用リストからSを除去する W ← W ∪ {x_i}

アルゴリズム19.12の時間コスト（451ページ） （プログラムの大きさ ＋ 除去された変数の個数）に比例した時間 変数の個数がプログラムの大きさを超えることはない。 →一般に線形時間 x_iの使用リスト（長いかも）からSを除去する時間は？ →使用リストを二重リンクリストで管理し、各使用（文？）に自分のノードを指すポインタを持たせれば、定数時間で済む。

図19.3b（435ページ）での 死亡コード除去（452ページ） a1,a2,a3,b0,b2,c0,c1,c2は使用されている。 b1の使用リストは空なので、ブロック2の文S： b1←φ(b0,b2) を除去する。 b0,b2の使用リストからSを除去する。 b0の使用リストが空だが、定義文がない。 b2はS以外でも使用されている。

単純な定数伝播（452-453ページ） v←c （cは定数）という文があったら、vの使用は、cの使用に置換できる。 v←φ(c1,c2,…,c_n) という文があって、c1=c2=…=c_n なら、この文を v←c に置換できる。

単純定数伝播のアルゴリズム(452ページ） W ← SSAプログラム中の全文のリスト while Wが空でない Wから文Sを除去する if Sは v←φ(c,c,...,c) ただしcは定数 Sを v←c に置換する if Sは v←c ただしcは定数 プログラムからSを除去する for vを使用する各文T T中のvをcに置換する W ← W ∪ {T}

図19.4g（437ページ）での 単純定数伝播（453ページ） 全引数が等価なφ関数はない。 i1←1 を除去して、 j3←i1 を j3←1 に置換。 j1←1 を除去して、 j2←φ( j4,1) k1←0 を除去して、 k2←φ(k4,0) j3←1 を除去して、 j4←φ(1, j5)

他の作業リストアルゴリズム（453ページ） コピー伝播 定数畳み込み 定数条件 到達不可能コード x←φ(y) や x←y を除去、xの使用をyに置換。 定数畳み込み x←a・b （a,bは定数）という文は、翻訳時に c←a・b を評価して、 x←c に置換。 定数条件 到達不可能コード

定数条件(453ページ） ブロックL中に if a<b goto L1 else L2 という文があり、aとbが定数なら、翻訳時に a<bを評価し、その値によって goto L1 か goto L2 に置換する。 LからL2（またはL1）への制御フロー枝を除去する。 L2（L1）の直前ブロックのリストと、L2（L1）中のφ関数の引数と から、Lを除去する。

到達不可能コード（453ページ） 定数条件で直前ブロックを除去した結果、ブロックL2が到達不可能になった場合、L2中の全文を除去する。

条件付き定数伝播 （453-456ページ） 単純定数伝播が実行可能と見なすブロックの集合は、不動点だが最小ではない。 条件付き定数伝播は最小不動点を見つける。 証拠がない限り、 ブロックは実行不可能と見なす。 変数は定数値を取ると見なす。

変数vの値（454ページ） V[v]=⊥ （初期値） V[v]=4 V[v]=T 実行可能な代入が見つかってない。 複数の実行可能な代入が見つかった。 翻訳時に値の分からない実行可能な代入が見つかった。

ブロックBの実行可能性 （454ページ） E[B]=false （初期値） E[B]=true

初期設定と、ブロックに対する 条件（454ページ） 1. SSA中で定義されない変数vは、プログラムに対する入力か、手続きの形式引数か、初期化し忘れの変数なので、V[v]←T とする。 2. 最初のブロックB1は実行可能。E[B1]←true 3. 実行可能なブロックBの直後ブロックがCのみなら、E[C]←true

実行可能な代入と分岐に対する条件（455ページ） 実行可能な代入 v←x・y について、 4. V[x]=c1 かつ V[y]=c2 なら、V[v]←c1・c2（定数畳み込み） 5. V[x]=T または V[y]=T なら、V[v]←T その他の代入 7. v←MEM( ) または v←CALL( ) なら、V[v]←T 実行可能な分岐 if x<y goto L1 else L2 について、 10. V[x]=T または V[y]=T なら、E[L1]←true かつ E[L2]←true 11. V[x]=c1 かつ V[y]=c2 なら、c1<c2 の値に応じて E[L1]←true または E[L2]←true（定数条件）

実行可能なφ関数に対する 条件（455ページ） v←φ(x1,...,x_n) について、 6. V[x_i]=c1,V[x_j]=c2,c1≠c2,i番目とj番目の直前ブロックが実行可能なら、V[v]←T 8. V[x_i]=T かつ i番目の直前ブロックが実行可能なら、V[v]←T 9. V[x_i]=c1 かつ i番目の直前ブロックが実行可能なとき、全てのjについて (V[x_j]=⊥ または V[x_j]=c1 または j番目の直前ブロックが実行不可能)なら、V[v]←c1

変数とブロックの解析 （455ページ） 変数用の作業リストWvから変数xを選び、xを使用する各文について条件4-9に従う。 ブロック用の作業リストWbからブロックBを選んで条件3を考え、B中の各文について条件4-9に従う。 ブロックBが新しく実行可能と見なされたら、Bと、実行可能な直後ブロックをWbに加える。 変数vが、⊥からc、cからTへ格上げされたら、vをWvに加える。 WvとWbが空になったら終わり。

条件付き定数伝播の アルゴリズム（455ページ） 解析は速く終わる。なぜなら、 変数は2回しか格上げされない。 ブロックは1回しか実行可能にならない。 解析が終わったら、 E[B]=false であるようなブロックBを除去する。 V[x]=c であるような変数xをcに置換し、xへの代入を除去する。

図19.4gでの条件付き定数伝播（456ページ図19.13） ブロック1、2は実行可能。（条件2、3） V[i1] ←1、V[ j1]←1、V[k1]←0。 V[ j2]←1、V[k2]←0。（条件9） ブロック3、5、7（、2）は実行可能。（条件11、3） V[ j3]←1。 V[k3]←1。（条件4） V[ j4]←1、V[k4]←1。（条件9） V[ j2]←1、V[k2]←T。（条件9、6） ブロック（3、）4は実行可能。（条件10） V[k3]←T、V[k4]←T。（条件5、8）

支配性を保つ（456-457ページ） 支配性とは、変数の定義が、その変数の使用を支配すること。 支配性を保たない最適化は避けるべき。 SSAから干渉グラフを作るアルゴリズム19.17など、支配性に依存する最適化アルゴリズムがある。 SSAの定義も支配性に依存している。

19.4節「配列、ポインタ、メモリ」 4種の依存関係 メモリ上での依存

4種の依存関係（457ページ） 書いてから読む。（SSAに明示される） 書いてから書く。（SSAにはない） 文Aが変数vを定義し、文Bがvを使用する。 書いてから書く。（SSAにはない） Aがvを定義した後、Bがvを定義する。 読んでから書く。（SSAにはない） Aがvを使用した後、Bがvを定義する。 制御する。 Bが実行されるかどうかをAが制御する。

メモリ上での依存（458ページ） これまでは、ロード・ストアを無視してきた。 メモリに対するSSAを得るには、各メモリワードに一度しか書き込まなければよい。 これは、純関数型言語がしていることと同じ（15章）。 実際には、裏でごみ集めによって物理メモリを使い回す。 手続き型言語では難しい。

単純だが現実的な解決 （459ページ） ストア命令は生存していると見なす。 ストアに対して死亡コード除去を行わない。 ロードとストアや、ストア2つを入れ替えない。 到達不可能なストアは除去してよい。 19章にある最適化アルゴリズムは、この単純なロード・ストアモデルを使っている。 命令を並べ替えない。 メモリを通じてデータフロー情報を伝播しない。

19.5節「制御依存グラフ」 制御依存グラフを作る 強力な死亡コード除去 制御依存グラフを使うアルゴリズムである。

用語（459-460ページ） 制御フローグラフ（CFG)には出口ノード1つ。 ノードyがxに制御依存するとは、 制御依存グラフ（CDG）は、 複数のreturn文を持つ関数のCFGは、各returnから、CFGの本当の出口ノードへの枝があると見なす。 ノードyがxに制御依存するとは、 xからuとvへの分岐があり、uから出口へyを通らないパスがあり、vから出口へyを通らないパスがないこと。 制御依存グラフ（CDG）は、 yがxに制御依存するとき、xからyへの枝を持つ。 yがvを逆支配するとは、 vから出口へyを通らないパスがないこと。

G（CFG)の CDGを作る （460ページ） 1. Gに入口ノードrを加え、 2. Gの枝の向きを逆にしてG’（逆CFG)を作る。 4. G’の支配前線DF_G’を計算する。 5. CDGは、x∈DF_G’[y]のとき、xからyへの枝を持つ。

強力な死亡コード除去 （461ページ） 強力でない死亡コード除去では、実質的な計算結果に役立っていない文も生存すると見なしていた。 強力な死亡コード除去では、プログラムの実質的な結果に役立つという証拠がなければ、文は死亡していると見なす。

強力な死亡コード除去の アルゴリズム（461ページ） 以下の文は生存と印付ける。 1. 入出力、ストア、関数からのreturn、副作用のあるかもしれない関数呼び出し。 2. 他の生存する文で使われる変数vの定義。 3. 他の生存する文が制御依存する条件分岐。 その後、印付いてない文を除去する。

図19.13dでの強力な死亡コード 除去（462ページ図19.16） ブロック4は、return文なので生存。（条件1） ブロック4が使用する変数はない。（条件2） ブロック4が制御依存する条件分岐はない。（条件3） 生存しているのはブロック4のみ。

強力な死亡コード除去で 注意すること（461ページ） 強力な死亡コード除去は、出力のない無限ループを除去する。 何もしない（止まらない）はずのプログラムが、出力して止まるプログラムになるかも。 並列化コンパイラではよく使われる。 無限ループと、ループ後の文を並列化すれば、無限ループを除去するのと同様の結果になるだろう。

19.6節「SSAからの逆変換」 SSAにおける生存解析

SSAからの逆変換 （462-463ページ） y←φ(x_1,…,x_n)を含むブロックの、i番目の直前ブロックの最後に y←x_i を加える。 枝分割SSAでないと、無駄な代入が入る。 逆変換の後、レジスタ割り当てを行う。 元のプログラムで同一の変数xから派生したx1とx2は、最適化（定数伝播、コピー伝播）によって干渉しているかもしれない。 派生元は無視。合体（コピー伝播）に任せる。

SSAにおける生存解析 （463-464ページ） φ関数を代入命令に変換する前に、SSAから干渉グラフを作れる。 アルゴリズム19.17は、各変数の生存範囲を計算し、干渉グラフを作る。 変数が生存しているブロックをたどって、その範囲で定義される他の変数との干渉を計算。 時間コストは、干渉グラフの大きさに比例。 末尾再帰で効率的。

アルゴリズム19.17（463ページ） LivenessAnalysis() = for 各変数v M←{} %すでにたどったブロックを覚えておく for vの各使用場所s if sは、vをi番目の引数に持つφ関数である LiveOutAtBlock(sを含むブロックのi番目の直前ブロック, v) else LiveInAtStatement(s, v) LiveOutAtBlock(n, v) = %変数vは、ブロックnから生存して出ているか if n∈M then すでにたどったブロックにたどり着いたので終わり M ← M∪{n} LiveOutAtStatement(nの最後の文, v)

アルゴリズム19.17（463ページ） LiveInAtStatement(s, v) = %変数vは、文sに生存して入っているか if sは、ブロックnの最初の文である then for nの各直前ブロックp LiveOutAtBlock(p, v) else LiveOutAtStatement(s’, v) LiveOutAtStatement(s, v) = %変数vは、文sから生存して出ているか for vを除く、文sで定義される各変数w 干渉グラフに (v, w) を加える if vがsで定義されている then vの定義にたどり着いたので終わり LiveInAtStatement(s, v)

19.7節「関数型中間表現」 スコープ SSAから関数型中間表現への変換 関数型プログラムから関数型中間表現への変換

関数型中間表現の特徴 （464ページ） 関数型言語の関数型中間表現と、手続き型言語のSSAは、関係が近い。 関数型中間表現（465ページ図19.18）では、 式の評価順序は決まっている。 中間結果は名前付きの一時変数に収められる。 組み込み演算や関数の実引数は、変数か定数。 変数への束縛は一度だけ。等式による推論ができる。 変数の使用は、その変数の束縛スコープ中にある。 スコープは文法上の表記。支配ノードの計算は不要。

関数型中間表現の式 （465ページ図19.18） atom → c 整定数 atom → s 文字列定数 atom → v 変数 exp → let fundefs in exp 関数宣言 exp → let v = atom in exp コピー exp → let v = binop(atom,atom) in exp 算術演算 exp → let v = M[atom] in exp メモリからフェッチ exp → M[atom] := atom; exp メモリにストア exp → if atom relop atom then exp else exp 条件分岐 exp → atom(args) 末尾呼び出し exp → let v = atom(args) in exp 非末尾呼び出し exp → return atom リターン

関数型中間表現の構文（式以外） （465ページ図19.18） args → args → atom args fundefs → fundefs → fundefs function v(formals) = exp formals → formals → v formals binop → plus | minus | mul | … relop → eq | ne | lt | ...

スコープ（465-466ページ） let v = … in exp let function f1(…) = exp1 … 束縛変数vのスコープは、exp。 let function f1(…) = exp1 … function f_k(…) = exp_k in exp 束縛変数f_iのスコープは、expとexp_j全て。（再帰を許す。） function f(…, v, ...) = exp 束縛変数vのスコープは、exp（関数本体）。

関数型中間表現の利点 （466ページ） インライン展開ができる。 インライン展開が簡単。 中間表現木（7章）では、関数の出入口が機種依存なので、関数を扱うのが難しい。 インライン展開が簡単。 （15章328ページ、アルゴリズム15.8） 実引数は変数か定数のみ。 その他の式の場合を考えなくてよい。

SSAから関数型中間表現へ の変換(466-467ページ） 複数の直前ブロックを持つCFGノードは、関数に変換。 引数は、ノード中のφ関数で定義される変数。 ノードへの枝は、jumpではなく、関数呼び出し。 ノードfがgを支配しているなら、関数gを、fにネストする。

アルゴリズム19.20（467ページ）ノードの変換 Translate(node) = nodeが支配するノードのうち、複数の直前ブロックを持つp_iは “function Fi()=Translate(p_i)” に変換。引数は、p_i中のφ関数で定義される変数 Fi を並べて F とする return Statements(node, 1, F)

アルゴリズム19.20（467ページ）文の変換 Statements(node, j, F) = %node中のj番目以降の文を変換 if node中の文を変換し終わった if 直後ブロックsの直前ブロックが1個だけ then Statements(s, 1, F) else 複数の直前ブロックを持つsへの枝は関数呼び出しに変換 else if nodeのj番目の文がφ関数 then Statements(node, j+1, F) else if j番目の文が “return a” then “let F in return a” else if move命令の場合 then “let move命令 in Statements(node, j+1, F)” else if “if a<b goto s1 else s2”の場合 then “let F in if a<b then Translate(s1) else Translate(s2)”

図19.4g（437ページ）を関数型中間表現に変換（466ページ、プログラム19.19） Translate(ノード1) F = “function f2(j2,k2) = Translate(ノード2)” “let i1=1…k1=0 in let F in f2(j1,k1)” Translate(ノード2) “(let in) if k2<100 then Translate(3) else Translate(4)” Translate(3) F = “function f7(j4,k4) = Translate(7)” “let F in if j2<20 then Translate(5) else Translate(6)” Translate(7) “(let in) f2(j4,k4)”

関数型プログラムから関数型 中間表現への変換（468ページ） （純）関数型プログラムは、 すでにスコープルールに従っている。 実引数は原子式（変数や定数）でないかも。 同名の変数があるかも。（?? variables are not unique） 関数型中間表現への変換 式の中間結果を一時変数に収めるのは簡単。 支配ノードとSSAの計算は不要。

関数型中間表現の最適化 （468ページ） SSAでの最適化は、関数型中間表現でも使える。 関数型プログラムでの最適化（15章）は、関数型中間表現でも使える。 明示多相型と型検査と型再構成（16章）に対応させることができる。 関数型中間表現は、お勧め。