Elimination(以下DCE)という最適化を書いてみた。今回はその実装の過程で調べたことなどをメモ。Elimination日本語だとそのまま「デッドコード除去」や「無用コード除去」などと訳されることが多そう。名前の通り使われていないコードを削除する最適化で、SILでいうと1つの関数(SILFunction)を単位として、その中で使われていない変数や文、引数をなどを消す。swift/DeadCodeElimination.cpp(誰にも使われていない関数を消す最適化ではない点に注意。Eliminationという名前で別に存在する。$Int32}これを最適化するとreturnだけのスッキリしたコードになる。$Int32}「使われないものを消す」という意味ではわかりやすくイメージしやすい最適化だが、どうやって「使われていない」ということを調べるのだろうか?というのが今回のメインの話。復習DCEの解説をする前にSILについての用語の説明をしておく。Block(基本ブロック、BBなどと略す)からなる。{基本ブロック基本ブロック...}BBはラベル、引数、いくつかの命令を含んだ文(ドキュメントにはsil-instruction-defなどと書かれている)と1つのTerminator(例えばreturnなど)からなる。terminator一般的なDCEのアルゴリズムDCEはコンパイラの書籍などにもよく載っている一般的な最適化方式であり、SILに限らずSSA形式のプログラムの最適化に使われている。DCEのアルゴリズムは簡単にいうと「生きている(live)文に印をつけて、印がついていないものを削除」である。2まではシンプルなのだが、3がなかなか難しいところで、この「制御依存」している箇所を見つけるのに何段階もプログラムを解析していく必要がある。以下PDT)を作成するPDTを作成するために今回作成したプログラムではLengauer-Tarjanアルゴリズムを採用した。Dominator(直接支配節)を計算する必要がある。CDGあたりを簡単にメモしておく。Graph(制御フローグラフ)プログラムの流れをそのままグラフにしたもの。SILにおいてはBBを一つの単位としてCFGが作られている。nodeと呼ばれる出口となるBBを1つ持つ。cond_brなど他のBBに分岐・ジャンプするものであればそこを繋いでできたグラフがCFGになる。nodeからある基本ブロックBへの経路で必ずある基本ブロックAを通らないと行けないとき、AをBのDominator(支配節)と呼ぶ。Dominator(後支配節)と呼ぶ。どちらの場合もすべてのノードは自分自身を(後)支配する。自分自身の支配を除いて支配関係をグラフにすると木構造になる。PDTはCFGをごにょごにょしていくと計算できる。Dependent(制御依存)とは、簡単に言うと「あるBBを通るかどうかは、ある他のBBの分岐次第で決まる」ということである。わかりやすいところでいえばif文の分岐の中はifの条件式に依存していて、3の条件は例えば「else節がliveならifの条件もlive」のように考えられる。Frontier(支配辺境)と呼ばれる「最初に後支配から外れる」ノードを見つける必要がある。dominatorにはならない、みたいなことを考えるとこれを求めることで制御依存しているノードを見つけられることがなんとなく見えてきそう。実はSwiftの実装ではPDTまでは計算するものの、CDGは完全には計算しない実装になっている。読んでないけどコード中に貼られていた論文を参照。depth)を計算するあるノードからCFGのpredecessorを辿っていって支配から外れたノードとそのlevelを保持するその中でlevelが最小のものがControl-dependentなノードになる。結局支配辺境を計算している?DCEの実装ここまでで必要な用語は定義し終えたので、実際の実装をみていく。条件1に当てはまるものをmarkするまず1の条件「副作用のある文、関数からの戻り」などをliveにする。Swiftの実装ではSILInstruction::mayHaveSideEffectsがtrueの命令unreachableそのreturnなど一部のterminatorがliveとなっている。unreachableのみをこの条件に引っ掛けることにした。条件2に当てはまるものをmarkする1の条件にひっかかったものがあった場合そこから他の文にliveをpropagateさせていく。パターンとしては主に2つあって、その変数を定義している文があるときはそれをliveにする。1でここがliveになるその変数がBBの引数ならばCFGにおけるそのBBのpredecessor(つまりBBにジャンプしているBB)を取得して、そのterminatorをliveにする。%1を定義しているのでlive。ここでbb2にジャンプしているのでlive。1でここがliveになるこれを繰り返していく。条件3に当てはまるものをmarkするSILの実装でいうと、制御依存しているBBのterminatorをliveとしてmarkしていく。ここでbb3にジャンプしているのでlive。ここまでがメインのDCEの実装。あとは自分で実装したもの・していないもの含め実際のSwiftコンパイラにはいくつか細かい対応が入っているのでそれも確認しておく。cond_brをbrに置き換えるmarkしていった結果、cond_br命令がdead判定された場合わざわざconditionを判定するまでもない。そのため分岐先を辿っていて適当なliveなblockをみつけた後、ただそこにジャンプするように書き換える。使われていない引数をundefに置き換えるBBで使われていない引数がある場合、そのBBを呼び出すbr命令などの引数にはundefが渡される。DCEとも呼ばれ、そのまま実装をすると無限ループするブロックも削除してしまい、意味が変わってしまうことがある。bb1Swiftの実装ではこのようなループは削除しないように予め関数が無限ループするかをhasInfiniteLoopsという関数で確認している。dependency文同士の依存関係を逆にする命令がいくつかある。普通の命令は%2の文が生きている場合%1がliveになる。%1しかし例えばデバッグ用の命令は、%1がliveなときに限り%2もliveになる。%1今回自分の実装では依存が逆になる命令を実装していなかったのでこれはスキップした。まとめSwiftのDCEはだいたい大まかにセオリー通り実装されているが、CDGを計算していなかったり、無限ループは削除しないようになっていたり細かい工夫が見られる。今回自分で実装したものはこちら。