2時間目: Dead Code Elimination

この問題で学べること

SILコードの構造であるSSA（Static Single Assignment）について理解し、それがどのように最適化を助けるかを知ることができます
特定のInstructionをFunctionから削除する方法を理解することができます
Dead Code Eliminationについて知って、簡単なDead Codeの削除ができるようになります

もう少し深くSILとPassを学ぶ

では、少々SILOptimizerのコードに慣れてきたと思うので、次はFunctionからInsturctionの削除をしてみたいと思います。
そこで、もう一つ必要になる知識がStatic Single Assignmentです。

Static Single Assignment(静的単一代入)

**Static Single Assignment(静的単一代入)**は、各変数が一度のみ代入できるようにする表現のことを指します。
そして、SILコードの構造がまさにSSAです。

では、次のようなコードをraw SILに変換して確かめましょう。

value.swift

func value() -> Int {
  var a = 10
  a += 5
  return a
}

value.swiftをrawSILにする.sh

$ swiftc -emit-silgen value.swift -o value.sil

このコードのrawSILは次のようになっています。

value.sil

// value()
sil hidden [ossa] @$s5neko25valueSiyF : $@convention(thin) () -> Int {
bb0:
  %0 = alloc_box ${ var Int }, var, name "a"      // users: %19, %1
  %1 = project_box %0 : ${ var Int }, 0           // users: %16, %12, %6
  %2 = integer_literal $Builtin.IntLiteral, 10    // user: %5
  %3 = metatype $@thin Int.Type                   // user: %5
  // function_ref Int.init(_builtinIntegerLiteral:)
  %4 = function_ref @$sSi22_builtinIntegerLiteralSiBI_tcfC : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %5
  %5 = apply %4(%2, %3) : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %6
  store %5 to [trivial] %1 : $*Int                // id: %6
  %7 = metatype $@thin Int.Type                   // user: %14
  %8 = integer_literal $Builtin.IntLiteral, 5     // user: %11
  %9 = metatype $@thin Int.Type                   // user: %11
  // function_ref Int.init(_builtinIntegerLiteral:)
  %10 = function_ref @$sSi22_builtinIntegerLiteralSiBI_tcfC : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %11
  %11 = apply %10(%8, %9) : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %14
  %12 = begin_access [modify] [unknown] %1 : $*Int // users: %15, %14
  // function_ref static Int.+= infix(_:_:)
  %13 = function_ref @$sSi2peoiyySiz_SitFZ : $@convention(method) (@inout Int, Int, @thin Int.Type) -> () // user: %14
  %14 = apply %13(%12, %11, %7) : $@convention(method) (@inout Int, Int, @thin Int.Type) -> ()
  end_access %12 : $*Int                          // id: %15
  %16 = begin_access [read] [unknown] %1 : $*Int  // users: %18, %17
  %17 = load [trivial] %16 : $*Int                // user: %20
  end_access %16 : $*Int                          // id: %18
  destroy_value %0 : ${ var Int }                 // id: %19
  return %17 : $Int                               // id: %20
} // end sil function '$s5neko25valueSiyF'

見にくいと思いますので、最初の数行をピックアップして解説します。

  %0 = alloc_box ${ var Int }, var, name "a"      // users: %19, %1
  %1 = project_box %0 : ${ var Int }, 0           // users: %16, %12, %6
  %2 = integer_literal $Builtin.IntLiteral, 10    // user: %5
  %3 = metatype $@thin Int.Type                   // user: %5
  // function_ref Int.init(_builtinIntegerLiteral:)
  %4 = function_ref @$sSi22_builtinIntegerLiteralSiBI_tcfC : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %5
  %5 = apply %4(%2, %3) : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %6
  store %5 to [trivial] %1 : $*Int                // id: %6

これのやっていることを一行づつ説明するためにコメントを入れます。

  // alloc_boxで変数名 "a" の変数をヒープに確保する
  %0 = alloc_box ${ var Int }, var, name "a"      // users: %19, %1
  // project_boxで%1 に "a" の参照をもたせるようにする
  %1 = project_box %0 : ${ var Int }, 0           // users: %16, %12, %6
  // integer_literalは整数リテラルを示す。これは、コード上にあった10から生成された
  %2 = integer_literal $Builtin.IntLiteral, 10    // user: %5
  // metatypeはその後に書かれたmetatype objectへの参照。今回はInt型のmetatype objectの参照を%3に持たせている
  // 今回はあまり深入りしないで大丈夫です
  %3 = metatype $@thin Int.Type                   // user: %5
  // function_ref は関数の参照。整数リテラルを受け取るIntのイニシャライザを呼ぶために%4に関数の参照を格納している
  // function_ref Int.init(_builtinIntegerLiteral:)
  %4 = function_ref @$sSi22_builtinIntegerLiteralSiBI_tcfC : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %5
  // applyをつかって、関数%4に%2と%3を引数で渡して結果を%5に格納している。つまりInt型のオブジェクトが作られる。
  %5 = apply %4(%2, %3) : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %6
  // %5を%1の参照先に格納する。
  store %5 to [trivial] %1 : $*Int                // id: %6

まず、このコードはSSAのフォーマットですね。最後の「%5を%1の参照先に格納」しているところはSSAと違うじゃん！と思うかもしれません。
しかし、あくまでこれはstoreで%5を%1の参照先に入れているので、

  %1 = %5

のような = を使うような再代入に当たるものではないです。
感のいい人はおわかりともいますが、この部分のコードは元のSwiftコードのvar a = 10にあたります。

SSAのメリット

SSAのメリットは、いくつかの最適化が可能になったり、通常のコードの表現よりも圧倒的に楽に最適化できることです。代表として、

定数畳み込みと定数伝播
Dead Code Elimination

が挙げられます。

定数畳み込みに関しては、例えば、リテラル同士の計算は事前に省略できるので、最適化時に計算したものとすり替えたりします。

var a = 5 + 10
// ↓ 最適化後
var a = 15

定数伝播は式内に定数への参照が含まれていた場合に、それを定数の中身にすり替えるというものです。

var a = 5
var b = a + 10
// ↓ 最適化後
var a = 15
var b = 5 + 15 // a が 5にすり替わった

これに似たようなものはArrayCountPropagationというPassが実装しています。

Dead Code Eliminationに関しては、その名の通り使われていないコードの削除を指します。
ですが、Codeの削除では、そのコードが実際に他から使われてないかをしっかり走査することが大事です。

そのときにSSAを利用するとコード(Instruction)同士の関係が単純になり、それらの走査が非常に楽になります。
何が単純かと言うと、SSAはその特性上、前のInstructionから利用されることができません。

わかり易い例といえば、次のようなコードはありえますが、

%0 = ... // user: %1
%1 = ... // user: %2
... // id: %2

次のようなコードはありえません。%0 と %1が循環して依存していますが、%0の時点で%1は何か不明なのでSSAに反しています。

%0 = ... // user: %1
%1 = ... // user: %0, %2
... // id: %2

Dead Code EliminationはSwiftコンパイラのコードでは頭文字をとってDCEと略されることが多いです。なので、この文章でも省略してDCEと書きます。

では、簡単なDCEであるminDCEを実装しましょう。その前に必要知識の準備をします。

Instructionの削除について

SILInsturctionは、SILInstruction型が提供しているeraseFromParent()関数で行えます。
ですが、これは使うにはいくつか守らなければなりません。

forでBasic Blockを回しているときに注意

たとえば、次のようなコードはセグフォを起こします。

for(auto& BB: *getFunction()) {
    for(auto &i: BB) {
        // ループが壊れるのでセグフォが出る。
        i.eraseFromParent();

for(auto 変数名: 変数名)の形式の繰り返し処理はBasic Blockの情報を参照しながら行います。
ループの途中でいきなりBasic BlockからInstructionが消えたらループ処理が壊れます。

これを解決する方法の一つとして、アドレスを使って手動でループ回す方法があります。

for(auto& BB: *getFunction()) {
    // beginがInstructionの最初のアドレス。endが最後のアドレス。++で次のInstuctionにシフトできる
    for (auto i = BB.begin(), E = BB.end(); i != E;) {
        // アドレスからInstructionを取る。&や*がよくわからないと思うので、テンプレとしてみたほうが良い。
        auto *inst = &*i;
        i++;
        inst.eraseFromParent();

削除しようとしてるInstructionを参照しているInstructionがあると強制終了

削除しようとしているInstructionが他から参照されているとき、Passが落ちます。

たとえば、下のコードの%0 = ...のInstructionを削除しようとするとエラーになります。

  %0 = integer_literal $Builtin.IntLiteral, 0     // user: %3
  %1 = metatype $@thin Int.Type                   // user: %3
  // function_ref Int.init(_builtinIntegerLiteral:)
  %2 = function_ref @$sSi22_builtinIntegerLiteralSiBI_tcfC : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %3
  %3 = apply %2(%0, %1) : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %4
  return %3 : $Int                                // id: %4

%3は%0のuserなので"Uses of SILInstruction remain at deletion."というメッセージとともに強制終了なります。

解決策として、Instructionの関数であるreplaceAllUsesOfAllResultsWithUndef()を使えば良いです。
replaceAllUsesOfAllResultsWithUndef()は、そのInstructionが参照されている部分をundefに変更します。

例えば、↑の%0 = ...でreplaceAllUsesOfAllResultsWithUndef()を使ったら、

  %0 = integer_literal $Builtin.IntLiteral, 0
  %1 = metatype $@thin Int.Type                   // user: %3
  // function_ref Int.init(_builtinIntegerLiteral:)
  %2 = function_ref @$sSi22_builtinIntegerLiteralSiBI_tcfC : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %3
  %3 = apply %2(undef, %1) : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %4
  return %3 : $Int                                // id: %4

のように%3 = ...の%0がundefになり、かつ%0 = ...の// user: %3というコメントが消えます。

結論

↑を踏まえて、Basic BlockからInstructionを削除するときは以下のポイントに気をつけましょう。

for(auto& bb: *getFunction()) {
    // ポイント: Instructionの削除前提でforを回すときはアドレスで回す
    for (auto i = bb.begin(), E = bb.end(); i != E;) {
        auto *inst = &*i;
        // ポイント: 他のInstructionが参照している部分をundefに変えてから削除
        i++;
        inst->replaceAllUsesOfAllResultsWithUndef();
        inst->eraseFromParent();

SIL Value

SILの構造として、SIL Valueにというものがありますが、これはいわゆる定数と考えてください。
https://github.com/apple/swift/blob/master/docs/SIL.rst#values-and-operands に定義がありますが、%0といった%から始まる値や、先程出てきたundefがSIL Valueに当たります。

そのInstructionを使っているInsructionを取得する

いくつかのInstructionの文末の// user: %...コメントにあるとおり、Instructionで生成された値はどこかのInstructionで使われている可能性があります。

この使っているInstructionが生成したSILValueはUserと呼びましょう。

Userは簡単に全て取得することができます。ではすべてのUserを試しにとってみましょう。

一つの値を生成する (%0 = ... みたいになっている) Instructionは、PassではSingleValueInstruction型で表現されています。まず、Basic Block全体からSingleValueInstructionを取得するのは簡単ですね。


for(auto i: bb)
  if(auto valueI = dyn_cast<SingleValueInstruction>(&i)) {

UserのコレクションはSingleValueInstructionのgetUsesという関数で取れます。これは、Operandという型のポインタのコレクションを返します。


for(auto i: bb)
  if(auto valueI = dyn_cast<SingleValueInstruction>(&i)) {
    for(auto useO: valueI->getUses())

このOperandのgetUser()を使えば、そのUserを生成しているInstructionを簡単に取得できます。
要は、// user: %m %nの%mとか%nのUserを生成しているInstructionを取ることができます。


for(auto i: bb)
  if(auto valueI = dyn_cast<SingleValueInstruction>(&i)) {
    for(auto useO: ValueI->getUses())
      if(auto UseI = useO->getUser())

そのInstructionが使っているInsructionを取得する

たとえば、return Instructionは一つのSILValueを返したり、ほかのInstructionも複数SILValueを使うことがあります。

  return %15 : $Int // id: %19

この使われているSILValueは簡単に取得できます。
SILInstructionのgetAllOperands関数を使うと、↑とは違ってポインタじゃないOperand型のコレクションを取得できます。

for(auto inst: bb)
   for(auto& o: inst->getAllOperands())

ここでポイントですが、このOperandから今回の目的のInstructionを取る場合は、次のようにしなければ取得できません。

o.get()->getDefiningInstruction();

get()はOperandからSILValue（ただし、ポインタ型）をとり、SILValueからさらにそのSILValueを定義しているInstructionをとるには、getDefiningInstruction関数を呼びます。

SmallSetVectorについて

SmallSetVectorはLLVMのライブラリの型で、SwiftでいうSet型に近いものです。よく、一時的に複数のSILInsructionなどのSILの情報を保存する際などに利用されます。

SmallSetVector<SILInstruction*, 32> Instructions;

Genericsのようなものが見えますが、左には格納したい型、右にはunsigned intで初期サイズを入れます。
初期サイズを超えても自動的に追加でサイズは確保されますが、用途にあったサイズを入れるのが安全です。

要素を入れるときは、insert関数を使います。

SmallSetVector<SILInstruction*, 32> Instructions;
...
for(auto i: BB) {
  Instructions.insert(&i);

また、SmallSetVectorの中に対象のオブジェクトがあるかどうかは、count関数で調べられます。
countはint(該当する要素の数)を返します。C++では1以上の数はtrueとして取り扱われるので、ifの条件式に書いても構いません。

SmallSetVector<SILInstruction*, 32> Instructions;
...
for(auto i: BB) {
  if(Instructions.count(&i)) {
    ...

Passのリフレッシュ

PassのオブジェクトはPipeLineから呼ばれて作られますが、Passのオブジェクトは使い回されます(たとえばSILFunctionTransformは他のFunctionの最適化でも使い回される)。

なので、目的に応じてメンバとして使っているSmallVectorやSmallPtrSetなどは、runの最後などでclearを呼び出して空にしたほうが良いです。

問題2: minDCEをつくる

というわけで、ここまでの説明で簡単なDCEを作ることができるようになりました。
本家DCEのアルゴリズムは少々ワークショップでやるには、ちょっとむずかしいので縮小版であるのminDCEを作ります。

本家では、削除対象ではないInstructionを**Useful(使える)**InsturctionとしてMarkしていき、そのMarkした情報を元に削除できそうなInsturctionをFunctionから取り除きます。

UsefulなInsturctionの条件としては

returnやnoreturnといったInsturction。副作用のある可能性があるInsturction
UsefulなInstructionに依存しているInstructionを見つけ出してMarkする(使っているInsturctionと、使われているInsturction)
UsefulなInsturctionが制御依存している条件分岐（複数のBasic Blockの間の走査）

が挙げれますが、このInsturctionをうまく走査してUsefulなのをすべてMarkすればよいです。十分に走査した後、MarkされなかったInsturctionを削除します。
今回は、1. 2. 3. をすべてワークショップの短い時間でこなすのは骨が折れるので、問題・テストでは少々条件を優しくしています。

問題

minDCEを実装して使われていないInstructionをFunctionから削除しましょう。

今回のminDCEのポリシーを次のように定義します。このポリシーはすでに実装されています。

Basic Blockが1つだけで、最後のInstructionがreturnなFunctionのみ最適化する。
- Basic Blockが２つ以上あるFunctionをつかうと、条件3. が必要になるため(問題の簡略化)
最初の条件1.はreturnのみUsefulなInstrucitonとして扱う
- 本当は副作用のあるInstructionなどを考慮に入れないといけないが、問題の簡略化のため
// user: ... をみるのはSingle Value Instructionだけでいい

まず、gitでwaiwai-question02ブランチから、waiwai-question02-{あなたの名前}という名前のbranchを切ってください。
回答のコードは、WaiWaiOptimizer.cppで指定してあるところ(run関数やほかのメンバ関数内)に書き込みます。

テスト対象の元のSwiftコードは、こんなかんじです。

func value() -> Int {
  let a = 10;
  let b = 10;
  return a
}

ここでは、b は使われていないのでDCEの削除対象になります。

Hint

MarkされたInstructionを表現するのに困ったら、先程のSmallPtrSetを使ってみるのも良いかもしれません。
走査が終わったと思っても、走査で新しくUsefulとMarkされたInstructionをチェックするのを忘れているかもしれません。
Deleteの方法は間違ってませんか？

問題が終わったら？

問題をテストしてください。この問題のテストファイルはswiftディレクトリから見てwaiwai-test/question02.silです。

../build/Xcode-DebugAssert/swift-macosx-x86_64/Debug/bin/sil-opt -wai-wai-optimizer waiwai-test/question02.sil | ../build/Xcode-DebugAssert/llvm-macosx-x86_64/Debug/bin/FileCheck waiwai-test/question02.sil

を叩くとTestが走ります。何も表示されなければTest成功です。

テストが終わったら、講師がチェックしに行くので手を上げて教えて下さい！