わいわいSwiftc 番外編ワークショップ vol.3 福岡 2時間目

# 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に変換して確かめましょう。

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

```shell:value.swiftをrawSILにする.sh
$ swiftc -emit-silgen value.swift -o value.sil
```

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

```swift: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'
```

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

```swift
  %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
```

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

```swift
  // 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`の参照先に入れているので、

```swift
  %1 = %5
```

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

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

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

が挙げられます。

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

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

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

```swift
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から利用されることができません。**

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

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

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

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

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

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

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

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

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

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

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

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

```cpp
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を削除しようとするとエラーになります。

```swift
  %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()`を使ったら、

```swift
  %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を削除するときは以下のポイントに気をつけましょう。

```cpp
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`を取得するのは簡単ですね。

```cpp

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

```

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

```cpp

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を取ることができます。

```cpp

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を使うことがあります。

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

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

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

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

```cpp
o.get()->getDefiningInstruction();
```

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


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

```cpp
SmallSetVector<SILInstruction*, 32> Instructions;
```

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

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

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

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

```cpp
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の条件としては

1. `return`や`noreturn`といったInsturction。副作用のある可能性があるInsturction
2. `Useful`なInstructionに依存しているInstructionを見つけ出してMarkする(使っているInsturctionと、使われているInsturction)
3. `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コードは、こんなかんじです。

```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成功です。

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