Swiftの中間言語SILを読む その5 - Dead Code Elimination

February 19, 2018

最近SILの最適化を自分で書き始めてみていて、その第一弾として概念的にわかりやすそうなDead Code Elimination(以下DCE)という最適化を書いてみた。今回はその実装の過程で調べたことなどをメモ。

レポジトリはこちら。

Dead Code Elimination

日本語だとそのまま「デッドコード除去」や「無用コード除去」などと訳されることが多そう。名前の通り使われていないコードを削除する最適化で、SILでいうと1つの関数(SILFunction)を単位として、その中で使われていない変数や文、引数をなどを消す。

(誰にも使われていない関数を消す最適化ではない点に注意。それはDead Function Eliminationという名前で別に存在する。)

例えば以下のSILでは最終的にreturn %0 : $Int32 をしており%3 ~ %8 は使われていない。

sil @dead1 : $@convention(thin) (Int32, Int32) -> Int32 {
bb0(%0 : $Int32, %1 : $Int32):
  %3 = struct_extract %0 : $Int32, #Int32._value
  %4 = struct_extract %1 : $Int32, #Int32._value
  %5 = integer_literal $Builtin.Int1, -1
  %6 = builtin "sadd_with_overflow_Int32"(%3 : $Builtin.Int32, %4 : $Builtin.Int32, %5 : $Builtin.Int1) : $(Builtin.Int32, Builtin.Int1)
  %7 = tuple_extract %6 : $(Builtin.Int32, Builtin.Int1), 0
  %8 = struct $Int32 (%7 : $Builtin.Int32)
  return %0 : $Int32
}

これを最適化するとreturnだけのスッキリしたコードになる。

sil @dead1 : $@convention(thin) (Int32, Int32) -> Int32 {
bb0(%0 : $Int32, %1 : $Int32):
  return %0 : $Int32
}

「使われないものを消す」という意味ではわかりやすくイメージしやすい最適化だが、どうやって「使われていない」ということを調べるのだろうか?というのが今回のメインの話。

SILの関数とBasicBlockの構造 復習

DCEの解説をする前にSILについての用語の説明をしておく。

SILの関数は、関数名、型、いくつかのBasic Block(基本ブロック、BBなどと略す)からなる。

sil 関数名 :  {
基本ブロック
基本ブロック
...
}

BBはラベル、引数、いくつかの命令を含んだ文(ドキュメントにはsil-instruction-defなどと書かれている)と1つのTerminator(例えばreturnなど)からなる。

ラベル(引数):
  %1 = ... // instruction def
  %2 = ... // instruction def
  return %2 // terminator

一般的なDCEのアルゴリズム

DCEはコンパイラの書籍などにもよく載っている一般的な最適化方式であり、SILに限らずSSA形式のプログラムの最適化に使われている。

DCEのアルゴリズムは簡単にいうと「生きている(live)文に印をつけて、印がついていないものを削除」である。

生きている文の定義をModern Compiler Implementation in MLから引用すると、

  1. 関数からの戻り、副作用を生じる可能性がある文
  2. 他のliveな文で使われている変数を定義する文
  3. 他の生きている文がControl-Dependent(制御依存)している条件分岐

1, 2まではシンプルなのだが、3がなかなか難しいところで、この「制御依存」している箇所を見つけるのに何段階もプログラムを解析していく必要がある。

手順を具体的に書くと

  1. 関数のControl Flow Graph(制御フローグラフ, 以下CFG)を作成する
  2. CFGからPost-dominant Tree(後支配木. 以下PDT)を作成する
    • PDTを作成するために今回作成したプログラムではLengauer-Tarjanアルゴリズムを採用した。そこではPDTを求めるためにCFGからDepth-first Spanning Tree(深さ優先全域木)Semidominator Tree(半支配木)Immediate Dominator(直接支配節)を計算する必要がある。
  3. PDTからDominance Frontier(支配辺境)を計算する
  4. Dominance FrontierからControl Dependent Graph(制御依存グラフ)を作る

全部の解説をしていると長くなってしまうので、Swiftコンパイラのコードリーディングする上でもよく出てくるCFG, PDT, CDGあたりを簡単にメモしておく。

Control Flow Graph(制御フローグラフ)

プログラムの流れをそのままグラフにしたもの。SILにおいてはBBを一つの単位としてCFGが作られている。 例えば以下のSILっぽいコードのCFGを書いてみると、

sil @hogehoge : $@convention(thin) () -> () {
bb0:
  br bb1
bb1:
  cond_br %0, bb2, bb3
bb2:
  br bb1
bb3:
  return %1
}

こんな感じ。

bb0 -> bb1
bb1 -> bb2
bb1 -> bb3
bb2 -> bb1

CFGはentry nodeと呼ばれる入り口となるBBと、canonical exit nodeと呼ばれる出口となるBBを1つ持つ。

SILの関数からの変換は特に難しくなく、BBのterminatorがbr, cond_brなど他のBBに分岐・ジャンプするものであればそこを繋いでできたグラフがCFGになる。

Post Dominator Tree(後支配木)

CFGにおいて、entry nodeからある基本ブロックBへの経路で必ずある基本ブロックAを通らないと行けないとき、AをBのDominator(支配節)と呼ぶ。

逆に、ある基本ブロックCからexit nodeへの経路で必ずDを通らないといけないとき、DをCのPost Dominator(後支配節)と呼ぶ。

どちらの場合もすべてのノードは自分自身を(後)支配する。 自分自身の支配を除いて支配関係をグラフにすると木構造になる。特にPost Dominatorの関係でできた木をPost Dominator Treeと呼ぶ。

PDTはCFGをごにょごにょしていくと計算できる。 今回採用したアルゴリズムと実装↓

Control Dependent Graph (制御依存グラフ)

Control Dependent(制御依存)とは、簡単に言うと「あるBBを通るかどうかは、ある他のBBの分岐次第で決まる」ということである。

わかりやすいところでいえばif文の分岐の中はifの条件式に依存していて、3の条件は例えば「else節がliveならifの条件もlive」のように考えられる。

CDGを求めるにはPDTからDominance Frontier(支配辺境)と呼ばれる「最初に後支配から外れる」ノードを見つける必要がある。解説は省略するがif Cond then A else Bみたいなコードで言えばCondからBに迂回する経路があるのでAはCondのpost dominatorにはならない、みたいなことを考えるとこれを求めることで制御依存しているノードを見つけられることがなんとなく見えてきそう。実装はこちら

実はSwiftの実装ではPDTまでは計算するものの、CDGは完全には計算しない実装になっている。読んでないけどコード中に貼られていた論文を参照。

  • Pingali, Keshav, and Gianfranco Bilardi. “Optimal control dependence computation and the Roman chariots problem.” ACM Transactions on Programming Languages and Systems (TOPLAS) 19.3 (1997): 462-491.

ざっとコードを読んだ感じだと、

  • 各ノードのlevel(= depth)を計算する
  • あるノードからCFGのpredecessorを辿っていって支配から外れたノードとそのlevelを保持する
  • その中でlevelが最小のものがControl-dependentなノードになる。

ということらしい。結局支配辺境を計算している?

DCEの実装

ここまでで必要な用語は定義し終えたので、実際の実装をみていく。

条件1に当てはまるものをmarkする

まず1の条件「副作用のある文、関数からの戻り」などをliveにする。 Swiftの実装では

  • SILInstruction::mayHaveSideEffectsがtrueの命令
  • unreachable
  • そのreturnなど一部のterminator

がliveとなっている。 自分の実装ではまだSILの命令全てに対応しているわけではないので、return, throw, unreachableのみをこの条件に引っ掛けることにした。

条件2に当てはまるものをmarkする

1の条件にひっかかったものがあった場合そこから他の文にliveをpropagateさせていく。 パターンとしては主に2つあって、

  1. その変数を定義している文があるときはそれをliveにする。

     % 5 = ...       // ② %5を定義しているので2でここがliveになる 
     return %5 : $() // ① 1でここがliveになる
    
  2. その変数がBBの引数ならばCFGにおけるそのBBのpredecessor(つまりBBにジャンプしているBB)を取得して、そのterminatorをliveにする。

     bb1:
       %1 = ...          // ④ %1を定義しているのでlive。
       br bb2(%1 : $Int) // ③ ここでbb2にジャンプしているのでlive。
     bb2(%2 : $Int)      // ② %2は引数。bb2にジャンプしてくるBBを探す
       return %2 : $Int  // ① 1でここがliveになる
    

これを繰り返していく。

条件3に当てはまるものをmarkする

SILの実装でいうと、制御依存しているBBのterminatorをliveとしてmarkしていく。

sil @control_dependent : $() {
bb0:
  %0 = integer_literal $Int1, 1 // 当然ここも
  cond_br %0, bb1, bb2 // ④ bb0はbb1, bb2の制御依存なのでここもlive
bb1:
  %2 = integer_literal $Int, 3 // ここも③よりlive
  br bb3(%2 : $Int) // ③ ここでbb3にジャンプしているのでlive
bb2:
  %4 = integer_literal $Int, 3 // ここも③よりlive
  br bb3(%4 : $Int) // ③ ここでbb3にジャンプしているのでlive。
bb3(%6 : $Int):     // ② %6は引数。bb3にジャンプしてくるBBを探す
  return %6 : $Int  // ① 1でここがliveになる
}    

ここまでがメインのDCEの実装。 あとは自分で実装したもの・していないもの含め実際のSwiftコンパイラにはいくつか細かい対応が入っているのでそれも確認しておく。

cond_brをbrに置き換える

markしていった結果、cond_br命令がdead判定された場合わざわざconditionを判定するまでもない。そのため分岐先を辿っていて適当なliveなblockをみつけた後、ただそこにジャンプするように書き換える。

実装はこちら

使われていない引数をundefに置き換える

BBで使われていない引数がある場合、そのBBを呼び出すbr命令などの引数にはundefが渡される。

bb1(%1 : $Builtin.Int32, %2 : $Builtin.Int32): // bb1の引数はdead
  br bb3
bb2:
  br bb1(undef : $Builtin.Int32, undef : $Builtin.Int32) // その呼び出しの引数をundefにする

無限ループは除去しない

この記事で説明したDCEはAggressive DCEとも呼ばれ、そのまま実装をすると無限ループするブロックも削除してしまい、意味が変わってしまうことがある。

bb1:
  br bb1

Swiftの実装ではこのようなループは削除しないように予め関数が無限ループするかをhasInfiniteLoopsという関数で確認している。

Reverse dependency

文同士の依存関係を逆にする命令がいくつかある。 普通の命令は%2の文が生きている場合%1がliveになる。

%1 = ...
%2 = some_inst %1

しかし例えばデバッグ用の命令は、%1がliveなときに限り%2もliveになる。

%1 = ...
%2 = some_debug %1

今回自分の実装では依存が逆になる命令を実装していなかったのでこれはスキップした。

まとめ

SwiftのDCEはだいたい大まかにセオリー通り実装されているが、CDGを計算していなかったり、無限ループは削除しないようになっていたり細かい工夫が見られる。

今回自分で実装したものはこちら。実際のSwiftレポジトリにあるテストケースも3つパスした🎉

このエントリーをはてなブックマークに追加