Modern Compiler Implementation in C by Andrew W. Appel 章19 静的単一代入形 451ページ **************************************************************** 節19.3 SSAを利用する最適化アルゴリズム **************************************************************** SSA形の主な利点は、重要なデータフロー情報に素早くアクセスできることなので、 SSAグラフのデータ構造の表現に気をつけるべきである。 関心があるのは、文、基本ブロック、変数の三つである。 文 関心ある属性は、その文が含まれるブロック、ブロック中の直前直後の文、変数の定義と使用の五つである。 各文は、通常の代入、φ関数、フェッチ、ストア、分岐の五つのうちどれかである。 変数 定義された場所（文）、使用される場所のリストの二属性。 ブロック 文のリスト、直前ブロックの順序付きリスト、直後ブロック（ブロックの終わりが条件分岐文なら複数）の三属性。 直前ブロックの順序は重要で、それによってブロック中の φ(v1,v2,v3) の意味が決まる。 ================================================================ 死亡コードの除去 ================================================================ SSAデータ構造を使うと、死亡コード解析は特に素早く簡単に行える。 ある変数が定義場所で生存しているのは、その変数の使用リストが空でない場合である。 なぜなら、（単一代入形では）同一の変数を複数定義することはなく、 変数の定義は、その変数の全使用を支配するからである。 （定義から使用へ至るパスが存在しなければならない。注1） 注1 普通、接続グラフのみを考える。 このことから、死亡コードを除去する以下の反復アルゴリズムが出てくる。 while 使用されない変数vがある and vを定義する文は他に副作用がない do vを定義する文を除去する 文 v ← x・y または v←φ(x,y) を除去するとき、 xとyの使用リストから、その文を除去することに注意。 除去された文が使用リストに載る唯一の文なら、xやyが死亡変数になる。 これを効率的にするため、 アルゴリズム19.12は変数の作業リストWを作り替えながら使う。 アルゴリズム19.12はプログラムの大きさに加え、 除去された変数の個数に比例した時間がかかる。 変数の個数はプログラムの大きさを超えることがないので、 一般にはプログラムの大きさに比例した線形時間かかる。 ただ疑問なのは、 （潜在的に長くなりうる）x_iの使用リストからSを除去するのにかかる時間である。 x_iの使用リストを二重リンクリストで管理し、x_iの各使用文にノード自身を指すポインタを持たせれば、 定数時間でSを除去できる。 452ページ アルゴリズム19.12 SSA形を利用した死亡コード除去 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} end for end if end if end while 図19.3bのプログラムに、このアルゴリズムを適用すると、 文 b1←φ(b0,b2) を除去できる。 もっと強力な死亡コード除去アルゴリズムでは、死亡の定義が異なる。 461ページで述べる。 ================================================================ 単純な定数伝播 ================================================================ v←c の形の文があり、cが定数なら、 vの使用は全てcの使用に置換できる。 v←φ(c1,c2,...,c_n) の形のφ関数があり、c_iが全て等しい定数なら、 このφ関数は、v←c に置換できる。 以上の条件は、SSAデータ構造を使って簡単に検出、実現でき、 単純な作業リストアルゴリズムで定数伝播できる。 W ← SSAプログラム中の全文のリスト while Wが空でない Wから文Sを除去する if Sは v←φ(c,c,...,c) ただしcは定数 Sを v←c に置換する end if if Sは v←c ただしcは定数 プログラムからSを除去する for vを使用する各文T T中のvをcに置換する W ← W ∪ {T} end for end if end while 453ページ 図19.4gのSSAプログラムにこのアルゴリズムを適用すると、 代入 j3←i は j3←1 に置換され、i1←1 は除去される。 変数j1とk1の使用も定数に置換される。 以下の諸変形は全て、この作業リストアルゴリズムに含めることができ、 線形時間でこれら全ての最適化を一度に行える。 コピー伝播 一引数φ関数 x←φ(y) やコピー代入 x←y は除去できる。 xの全使用をyに置換すればよい。 定数畳み込み 文 x←a・b があり、aとbが定数なら、 翻訳時に c←a・b を評価し、この文を x←c に置換することができる。 定数条件 ブロックL中の条件分岐 if a2 と 1--M1->3 が作られる。 この二つの定義使用枝は、SSAの定義使用関係と同様に 二枝の合流点でφ関数を作ることになる。 しかし、2から3への枝がないのに、 コンパイラが以下のように文を並べ替える障害となるのは何か？ 1 M1←store(M0, i,4) 3 M2←store(M1, k,j) 4 x ← load(M1, j) 459ページ 関数型の依存は正しいままである。 M1を文1実行後のメモリのスナップショットと見なせば、 文4は、そのスナップショットのアドレスjからのロードで正しいままである。 しかし、コンピュータに複数のメモリコピーを持たせるのは、控えめに言っても非効率的である。 読んでから書く依存 2→3 があるせいで、 M1の全使用が実行される前に、コンパイラがM2を作ることができないと言いたい。 しかし、メモリについて正確な依存情報を計算するのはこの章の範囲を超えている。 ---------------------------------------------------------------- 単純だが現実的な解 読んでから書く依存と書いてから書く依存の情報がなく、 ストア命令は必ず生存していると見なすとしか言えない。 ストアについて死亡コード除去は行わない。 ロードとストア、または二つのストアを入れ替えるような変形は行わない。 しかし、ストア命令は到達不可能かもしれず、 到達不可能なストア命令は除去できる。 この章に示された最適化アルゴリズムは、命令を並べ替えず、 メモリを通じてデータフロー情報を伝播しようともしないので、 陰にこの単純なロードストアモデルを使っている。 **************************************************************** 節19.5 制御依存グラフ **************************************************************** ノードxは、ノードyが実行されるかを直接制御できるだろうか？ この疑問の答えは、プログラムの変形と最適化の助けとなる。 フローグラフには出口ノードがなければならない。 制御フローグラフが一個の関数を表しているなら、 出口ノードは、その関数のreturn文である。 return文が複数あるなら、実際には 各々からそのCFGの正規出口ノードへ制御フロー枝が通っていると見なす。 ノードyがxに制御依存しているとは、 xからuとvへの分岐があり、uから出口へyを通らないパスがあり、vから出口へのパスが必ずyを通ることを言う。 460ページ 制御依存グラフ（CDG）は、yがxに制御依存しているとき、xからyへの枝を持つ。 yがvを逆支配するとは、 vから出口へのパスが必ずyを通る（つまり、逆制御フローグラフ上でyがvを支配する）ことを言う。 ---------------------------------------------------------------- 制御依存グラフの作成 制御フローグラフGのCDGを作るには、 1. Gに新しい入口ノードrを付ける。 rからGの最初のノードsへ枝を通す（外のプログラムからGに入れることを示す)。 rからGの出口ノードexitへ枝を通す（外のプログラムがGを実行できないことを示す）。？？？ 2. G'を逆制御フローグラフとする（Gの枝を逆向きにしたものである)。 G'の最初のノードはGの出口ノードに当たる。 3. G'の支配ノード木を作る（根はGの出口ノードに当たる)。 4. G'のノードの支配前線DF_G'を計算する。 5. CDGは、x∈DF_G'[y]ならxからyへの枝を持つ。 つまり、yが実行されるかをxが直接制御するとは、 逆制御フローグラフ上でxがyの支配前線に含まれることである。 図19.4のプログラムのCDGを、図19.15に示す。 図19.15 制御依存グラフの作成 (a) CFG（図19.4bから） (b) 逆CFG (c) 逆支配ノード (d) 逆支配前線 (e) CDG SSAグラフと制御依存グラフを使って、 「AはBより前に実行されるか？」という疑問に答えられる。 SSAの使用定義枝とCDG枝を通ってAからBへ至るパスがあるなら、 データ・制御依存があるので、AはBより前に実行される必要がある。 461ページ ================================================================ 強力な死亡コード除去 ================================================================ 制御依存グラフの面白い使い方が死亡コード除去にある。 図19.13dのような状況を考えよう。 これまでの死亡コード除去の判断は（節17.3やアルゴリズム19.12で述べたように）、 ・k3の定義で使用されるのでk2は生存している。 ・k2の定義で使用されるのでk3は生存している。 しかし、どちらの変数も計算の実質的な結果には役立っていない。 条件付き定数伝播では、実行されるという証拠が見つからなければブロックは到達不可能と見なしたが、 同様に強力な死亡コード除去では、 プログラムの実質的な結果に役立つ証拠がなければ文は死亡していると見なす。 ---------------------------------------------------------------- アルゴリズム 以下の文に生存と印付ける。 1. 入出力、メモリへのストア、関数からのリターン、その他副作用があるかもしれない関数呼び出し。 2. 他の生存する文で使用される変数の定義。 3. 他の生存する文が制御依存している条件分岐。 その後、印付けられていない文を除去する。 反復（または作業リストアルゴリズム）で実現できる。 図19.13dのプログラムにこのアルゴリズムを適用した楽しい結果を、図19.16に示す。 全体のループが除去され、すごく効率的なプログラムになった！ ---------------------------------------------------------------- 注意 強力な死亡コード除去アルゴリズムでは出力のない無限ループを除去するので、 プログラムの意味が変わってしまう。 何もしないのではなく、そのプログラムはループの後に出力文を実行するかもしれない。 多くの環境ではこれは認められないと思われる。 しかし一方、制御依存グラフは並列化コンパイラでよく使われる。 制御依存もデータ依存もない二つの文は並列に実行できる。 並列化コンパイラでは無意味な無限ループを除去しなくても、 ループ後の文（ループに制御依存しない）と並列にループを実行できる。 無限ループを除去するのとだいたい同じ効果が得られる。 462ページ 図19.16 強力な死亡コード除去 (a) SSAプログラム (b) 逆支配ノード (c) 逆支配前線 (d) 制御依存グラフ (e) 生存する文を見つける ブロック4はリターンなので生存。 ブロック2に制御依存する生存ブロックはないし、 k2やk3にデータ依存する生存代入もないので、 他に生存する文はない。 (f) 死亡文除去後 **************************************************************** 節19.6 SSA形からの逆変換 **************************************************************** プログラムを変形や最適化した後、 静的単一代入形のプログラムをφ関数のない実行可能な表現に変換しなければならない。 定義 y←φ(x1,x2,x3) を変換すると、 直前ブロック枝1から来たなら y←x1、 直前ブロック枝2から来たなら y←x2、 直前ブロック枝3から来たなら y←x3 となる。 この定義を枝分割SSA形で実現するには、 φ関数を含むブロックのi番目の直前ブロックの最後に y←x_i を加えればよい。 「直前ブロックか直後ブロックが一つ」の性質のおかげで、 無駄な代入が加えられることはない。 図19.2b（この性質がない）では、ブロック2に a3←a1 を加える必要があるが、 then分岐が取られたら無駄になる。 しかし、図19.2cでは、a3←a1 はブロック5に加えればよく、 無駄に実行されることはない。 これで、プログラムにレジスタ割り当てを行うことができる。 レジスタ割り当ては章11で述べた。 元のプログラムで同一の変数xから派生したx1とx2を、 単に同一のレジスタに割り当ようとしても、 SSA形のプログラム変形によって変数の生存範囲が干渉しているかもしれない（演習19.11を見よ）。 よって、異なるSSA変数の派生元は無視し、 463ページ レジスタ割り当てで合体（コピー伝播）を行うことによって ほとんど全ての代入命令を除去させることにする。 ================================================================ SSAのための生存解析 ================================================================ アルゴリズム19.17 SSA形での生存範囲を計算し、干渉グラフを作る。 グラフをたどるアルゴリズムは、 LiveOutAtBlock、LiveInAtStatement、LiveOutAtStatement間の相互再帰で表される。 再帰が終わるのは、 LiveOutAtBlockですでにたどったブロックにたどり着いたときか、 LiveOutAtStatementでvの定義にたどり着いたときかである。 LivenessAnalysis() = for 各変数v M ← {} for vの各使用場所s if sは、vをi番目の引数に持つφ関数である pは、sを含むブロックのi番目の直前ブロックであるとする LiveOutAtBlock(p,v) else LiveInAtStatement(s,v) end if end for end for end LivenessAnalysis LiveOutAtBlock(n,v) = vは、nから生存して出ているか if not n∈M M ← M∪{n} sは、nの最後の文であるとする LiveOutAtStatement(s,v) end if end LiveOutAtBlock LiveInAtStatement(s,v) = vは、sに生存して入っているか if sは、どれかのブロックnの最初の文である vは、nに生存して入っているか for nの各直前ブロックp LiveOutAtBlock(p,v) end for else s'は、sの直前の文であるとする LiveOutAtStatement(s',v) end if end LiveInAtStatement LiveOutAtStatement(s,v) = vは、sから生存して出ているか Wは、sで定義される変数の集合であるとする for 各変数w ∈ (W - {v}) 干渉グラフに (v,w) を加える end for if not v∈W LiveInAtStatement(s,v) end if end LiveOutAtStatement φ関数を代入命令に変換する前に、 SSAプログラムから干渉グラフを効率的に作ることができる。 アルゴリズム19.17では、各変数vの各使用から逆にグラフをたどり、vの定義にたどり着くと止まる。 SSA形の支配性によって、vの定義によって支配された領域からアルゴリズムが外れないことが保証されている。 多くの変数では、この領域は小さなものである。 図19.14（非SSAプログラム）の場合と比較せよ。 図19.14の変数x1に、このアルゴリズムを適用すると、 1から3への枝をさかのぼり、全プログラムをたどる。 このプログラムは、vが生存しているブロックのみを処理するので、 実行時間は、作り出した干渉グラフの大きさに比例する（演習19.12を見よ）。 464ページ アルゴリズム19.17で示したが、 再帰（LiveInAtStatementがLiveOutAtBlockを呼ぶとき）と末尾再帰 （LiveInAtStatementがLiveOutAtStatementを呼ぶとき、 LiveOutAtStatementがLiveInAtStatementを呼ぶとき、 LiveOutAtBlockがLiveOutAtStatementを呼ぶとき）を使っている。 プログラミング言語やコンパイラによっては、 末尾再帰はgotoとしてすごく効率的にコンパイルできる。 節15.6を見よ。 しかし、効率的な末尾再帰をサポートしないコンパイラでこのアルゴリズムを実現するときは、 末尾再帰の代わりに、gotoを明示的に使うか、LiveOutAtStatementとLiveInAtStatementで作業リストを使うほうが良いだろう。 **************************************************************** 節19.7 関数型の中間形 **************************************************************** 関数型プログラミング言語では、 （章15で述べたように）実行が進むにつれて変数が値に束縛され、 一度初期設定した変数の値が変わることはない。 このため、等式による推論を行うことができ、 プログラマの役に立つものとなっている。 しかし、等式による推論はコンパイラにとってもっと役に立つものでもある。 コンパイラによる多くの最適化は、遅いプログラムを もっと速い等価なプログラムに書き換えるものである。 xの今の値と後での値が違うかもしれないとコンパイラが心配する必要がなければ、 この変形は簡単に表せる。 この単一代入性は、関数型プログラミングとSSA形両方の心臓部である。 関数型言語のコンパイラで使う関数型中間表現と 手続き型言語のコンパイラで使うSSA形とは密接な関係にある。 図19.18に、現代的な関数型言語のコンパイラで使われる種類の中間表現を抽象文法で示す。 四つ組とSSA形とラムダ計算の最良の性質を目指している。 四つ組表記と同様に、 式は組み込み演算に分割され、評価の順序が決まっていて、 全ての中間結果は明に名付けられたtemporaryであり、 演算や関数の実引数は原子式（変数か定数）である。 SSA形とラムダ計算と同様に、 全ての変数は単一代入（束縛）され、 変数の全使用は束縛スコープ中にある。 ラムダ計算と同様に、 スコープは文法上の表記で済み、支配ノードの計算は必要ない。 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 リターン args → args → atom args fundefs → fundefs → fundefs function _v(formals) = exp formals → formals → _v formals binop → plus | minus | mul | ... relop → eq | ne | lt | ... ---------------------------------------------------------------- スコープ 変数名を複数回束縛に使うことはできない。 変数の束縛にはスコープがあり、その変数の全使用はスコープ中に現れなければならない。 let v=... in exp で束縛された変数vのスコープは単にexpである。 let function f1(...) = exp1 : function f_k(...) = exp_k in exp で束縛された関数変数f_iのスコープは、 expだけでなくexp_j全てを含む（相互再帰関数を許している）。 関数の形式引数に束縛された変数のスコープは、関数の本体である。 466ページ こういうスコープルールによって多くの最適化の理屈付けが簡単になる。 関数のインライン展開を例に取ろう。 節15.4で述べたように、 定義 f(x)=E と使用 f(z) があるとき、 中のxをzに置換したEのコピーで、使用を置換することができる。 章7の木言語には関数がないので、 インライン関数を表現するのは難しい。 章15の関数表記では、zが非原子式の場合、 （アルゴリズム15.8bで示したように）置換が複雑になる。 しかし、図19.18の関数型中間形では、全ての実引数は原子式なので、 アルゴリズム15.8aで示したようにインライン展開は非常に簡単になる。 ---------------------------------------------------------------- SSAを関数形に変換する SSAプログラムは、アルゴリズム19.20に示すように関数形に変換できる。 複数の直前ブロックを持つ制御フローノードは関数になる。 この関数の実引数は、ノード中のφ関数で定義される変数である。 ノードfがノードgを支配しているなら、 関数gは、関数fの本体中にネストされる。 φ関数を含むノードへの制御フロー枝は、ノードへのジャンプではなく、関数呼び出しで表される。 プログラム19.19に、変換後のプログラムがどのようになるかを示す。 プログラム19.19 図19.4gのSSAプログラムを関数型中間形に変換 467ページ アルゴリズム19.20 SSAを関数型中間形に変換する Translate(node) = Cは、支配ノード木においてnodeの子供全ての集合であるとする p1,...,p_nは、Cのノードのうち複数の直前ブロックを持つものとする for i ← 1 to n a1,...,a_kは、p_i中のφ関数で定義される変数とする（k=0かもしれない） Si = Translate(p_i) とする Fi = "function f_p_i(a1,...,a_k) = Si" とする end for F = F1 F2 ... Fn とする return Statements(node,1,F) end Translate Statements(node,j,F) = if node中にj個以上の文がない then sは、nodeの直後ブロックであるとする if sの直前ブロックはnodeのみ then return Statements(s,1,F) else sはm個の直前ブロックを持つ nodeは、sのi番目の直前ブロックとする s中のφ関数は以下のようなものとする a1 ← φ(a11,...,a1m) a_k ← φ(a_k1,...,a_km) return "let F in f_s(a1i,...,a_ki)" end if elsif nodeのj番目の文はφ関数 then return Statements(node, j+1, F) elsif nodeのj番目の文は "return a" then return "let F in return a" elsif nodeのj番目の文は a ← b・c then % a←b、a←M[b]、M[a]←b の場合も同様 S = Statements(node, j+1, F) とする return "let a = b・c in S" elsif nodeのj番目の文は "if a