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

# ようこそ
これから、わいわいswiftc 番外編ワークショップ Vol.3 福岡のワークショップの問題を出していきます。問題はSILOptimizerのコンパイラのコードを理解できるようになるための初心者向けの問題で構成されています。また、各問題の前には必ず解説が入るので安心して進めてください。

# わからなかったら？
おそらく、多くの人が初めてコンパイラのコードやC++のコードを触るのでちょっと戸惑うかもしれません。わからなかったら、ぜひ講師へ質問したり、同じチームの人と一緒に考えてみましょう。ポインタ型というよくわからない物を使いますが、テンプレで覚えられる文はテンプレみたいに成っているのでそれで覚えてください。

# 諸注意
- ※ から始まる文は基本的に余談ですので、特に見なくても大丈夫です。
- このワークショップでは、初歩的なSILOptimiserの知識をなるべく網羅するために、一部問題では簡単なSwiftコードを最適化するようにしか考慮されていません。

# 1時間目: 簡単なPassを書いてみよう

先程解説したとおり、SILOptimizerは**Pass**と呼ばれるモジュール群からなり、SILコードを操作して最適化をしたり、走査をして診断を行います。

この章は、Passを知るための基本的な知識を知るためのものです。

## この章で学べること
- SILOptimizerで扱う基本的なデータ構造を知ることができます
- 一番簡単な最適化PassであるAssume Single Threadedについて学べます


## SILの構造について
SILは大きいものから、**Module**・**Function**・**Basic Block**・**Instruction**にわかれます。これは最適化前のraw SILも最適化後のcanonical SILも同様です。

例として、以下のソースで見てみましょう。

```swift
func zero() -> Int {
    return 0
}
```

これを、`swiftc`コマンドでraw SILに変換すると以下のようなコードに変換されます。

```shell:rawSILを出すコマンド.sh
$ swiftc -emit-silgen source1.swift -o source1.sil
```

```swift:source1.sil
import Builtin
import Swift
import SwiftShims

func zero() -> Int

// main
sil [ossa] @main : $@convention(c) (Int32, UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>) -> Int32 {
bb0(%0 : $Int32, %1 : $UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>):
  %2 = integer_literal $Builtin.Int32, 0          // user: %3
  %3 = struct $Int32 (%2 : $Builtin.Int32)        // user: %4
  return %3 : $Int32                              // id: %4
} // end sil function 'main'

// zero()
sil hidden [ossa] @$s4zeroAASiyF : $@convention(thin) () -> Int {
bb0:
  %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
} // end sil function '$s4zeroAASiyF'

// Int.init(_builtinIntegerLiteral:)
sil [transparent] [serialized] @$sSi22_builtinIntegerLiteralSiBI_tcfC : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int
```

では、どの部分がどれに当たるかを解説します。

### Module
SILソースファイル全体です。import文、型の定義やFunctionなどから成っています。
今回は扱いませんが、Witness TableやV Tableといった関数テーブルの情報も乗ります。


### Function
SILの関数です。Basic Blockから成っています。SwiftのFunctionから直接変換されたものだと考えてください。

以下は`main`関数と`zero`関数の例です。

```swift
// main
sil [ossa] @main : $@convention(c) (Int32, UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>) -> Int32 {
bb0(%0 : $Int32, %1 : $UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>):
  %2 = integer_literal $Builtin.Int32, 0          // user: %3
  %3 = struct $Int32 (%2 : $Builtin.Int32)        // user: %4
  return %3 : $Int32                              // id: %4
} // end sil function 'main'

// zero()
sil hidden [ossa] @$s4zeroAASiyF : $@convention(thin) () -> Int {
bb0:
  %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
} // end sil function '$s4zeroAASiyF'
```

> ※ Swiftでは暗黙的に`main`関数が生成されるので、`main`という名前のFunctionが存在します。

### Basic Block
SILの関数の中にあるブロックです。Instructionから成っています。
先頭に`bb[数字]:`というラベルがついています。


以下はzero関数の`bb0`の例です。

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

### Instruction
実際に値を操作したり、関数を呼び出したりする命令です。 

文末にある`%[数字]`は**id**と呼ばれるもので、これに値が格納されることがあります。

読むポイントを解説すると、

- `return`のような値を格納しないInstructionは、**右の方のコメントに `// id: %4` のように振られたidがわかるようになっています。**
- `// user: %3` は**その行のInstructionをつかっているidの一覧になっています。**

以下はzero関数の`bb0`の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
```

Basic Blockには、最後にはかならず`return`などのTerminatorと呼ばれるInstructionが必要になります。
> ※ https://github.com/apple/swift/blob/master/docs/SIL.rst#basic-blocks にBasic Blockの定義があります。

これらは、SILOptimizerのPassを書くときでも同様のデータ構造が使うことができます。

では次は実際にPassを見ていきましょう。


## SILOptimizerのPassの構成
まず、準備したSwiftコンパイラのXcodeを開き、`WaiWaiOptimiser.cpp`を開きましょう。
Xcodeで`Cmd + Shift + o`と押して、`WaiWaiOptimizer.cpp`と入力するとすぐに開くことができます。

下記のようなコードが出てくると思います。

```cpp
#include "swift/SILOptimizer/PassManager/Passes.h"
#include "swift/SIL/SILFunction.h"
#include "swift/SIL/SILInstruction.h"
#include "swift/SIL/SILModule.h"
#include "swift/SILOptimizer/Utils/Local.h"
#include "swift/SILOptimizer/PassManager/Transforms.h"
#include "llvm/Support/CommandLine.h"
#include <iostream>

using namespace swift;
using namespace std;

namespace {
class WaiWaiOptimizer : public SILFunctionTransform {
  /// The entry point to the transformation.
  void run() override {
    // [No.1]: Assume Single Threadedを書く
    // Hint: Referenceカウンタを操作するInstructionをすべてnon atomicにする
  }
};
}


SILTransform *swift::createWaiWaiOptimizer() {
  return new WaiWaiOptimizer();
}
```

各問題では、コメントで示された部分の中身を実際に実装していきます。

ここで、コードの各部分を解説をしましょう。

```cpp
#include "swift/SILOptimizer/PassManager/Passes.h"
#include "swift/SIL/SILFunction.h"
#include "swift/SIL/SILInstruction.h"
#include "swift/SIL/SILModule.h"
#include "swift/SILOptimizer/Utils/Local.h"
#include "swift/SILOptimizer/PassManager/Transforms.h"
#include "llvm/Support/CommandLine.h"
#include <iostream>

using namespace swift;
using namespace std;
```

`#include` はSwiftでいう`import`に近いものと覚えておいてください。  


> ※ namespaceという概念がC++にはありますが、この`using namespace swift;`は「`swift`というネームスペース以下にあるものは、このソースではすべて`swift`ネームスペースなしに明示しなくても使えるようにする」という意味です。後々意味がわかります。

次に移りましょう。

```cpp
namespace {
class WaiWaiOptimizer : public SILFunctionTransform {
  /// The entry point to the transformation.
  void run() override {
    // [No.1]: Assume Single Threadedを書く
    // Hint: Referenceカウンタを操作するInstructionをすべてnon atomicにする
  }
};
}
```

これが、今回各問題でアルゴリズムを書き込むPassである`WaiWaiOptimizer`の本体です。Passはこのようにクラスとして実装されます。  
よく見ると、`WaiWaiOptimizer`は、`SILFunctionTransform`というクラスを継承しています。

**このクラスを継承することで、`WaiWaiOptimizer`はFunctionごとに呼ばれるPassとして取り扱われます。**
**他に、`SILModuleTransform`を継承すれば、ModuleごとによばれるPassとして取り扱われます。**

> ※ 事前課題をやった人はもうおわかりと思いますが、`WaiWaiOptimizer`をsil-optで呼び出したときに`Hello, Optimizer!`がたくさん出力されましたね？ `WaiWaiOptimizer`は`SILFunctionTransform`を継承しているので、つまりはFunctionごとに`Hello, Optimizer!`が出力されたことになります

> ※ 先程、`using namespace swift;`の話をしましたが、実はここで効果を発揮しています。`SILFunctionTransform`は`swift`というネームスペースにあるので、`swift::SILFunctionTransform`と書かないといけないのですが、`using namespace swift;`で書かないで良いようになっています。

そして、`WaiWaiOptimizer`は`run`関数をオーバーライド（実装の上書き）しています。**この`run`関数の中で実際に最適化のアルゴリズムを実装します。**

最後のコードに移りますが、これはPipelineなどからPassを要求された際、オブジェクトを渡す関数です。

```cpp
SILTransform *swift::createWaiWaiOptimizer() {
  return new WaiWaiOptimizer();
}
```

> ※ Pass.defというものにPassの情報を登録しないといけないですが、登録した際にはこの関数の定義が自動生成されるので、その実装しなければなりません。定義とか実装とかナンノコッチャと思う人はC++のヘッダーまわり勉強すると理解できます。


### `SILFunctionTransform`のAPIについて

さて、基本的なPassの構造はわかりましたね。
しかし、最適化アルゴリズムを実装するには、いま見ているFunctionのBasic BlockやInstructionを手に入れないと何もできません。
`SILFunctionTransform`は以下のような機能を提供しているので、Basic BlockやInstructionの情報を簡単に手に入れることができます。

- `getFunction()` 関数
  - 現在見ているFunctionのポインタ型を手に入れることができる。帰ってくる型は`SILFunction*` 型

試しに`getFunction()` 関数を使ってみましょう。`run()` の中に試しに次のように書いてみましょう。

```cpp
// autoはC++の型推論キーワード。
// 本当はC++では`auto`のところにはSILFunction* と書かないといけないですが、C++には一応型推論が実装されています。
auto currentFunction = getFunction(); // C++は文の最後にはセミコロンが必要です
```

これで、現在Passが見ているFunctionの情報を手に入れました。これで第一段階クリアです。
では、Basic Blockを手に入れましょう。**実は、`SILFunction`型はBasic Blockのコレクション型のようなものです。**

コレクション型ということは、`for`文でFunction内の各BasicBlockの情報を取ることができます。つまり、次のように書くことができます。

```cpp
auto currentFunction = getFunction();
for(auto &bb: *currentFunction) {
    
}
```

`getFunction` 関数はポインタ型を返します。なので、`*currentFunction`のように返されたものは先頭に`*`がないと、実態を取り扱うことができません。

ただし、ポインタ型について詳しく説明するとこんがらがるので、今日はFunctionからBasic Blockを取り出すコードは↑のような書き方になるとだけ覚えておいてください。

`for`の中身で`bb`という変数がBasic Blockの情報をもっています。これは`SILBasicBlock`という型です。感のいい人ならわかると思いますが、**この型はInstructionのコレクション型のようなものです。**

つまりは、このように書けます。

```cpp
auto currentFunction = getFunction();
for(auto &bb: *currentFunction) {
    for(auto &i: bb) {
            
    }  
}
```
`bb` ポインタ型ではないので、`*currentFunction`のように先頭に`*`がなくて大丈夫です。
一番深いネストの部分の`i`がInstructionを示しています。型は`SILInstruction`です。

さて、Instructionまでたどり着きました。次が最後のステップです。
次は、今見ているInstructionが何のInstructionなのかを特定しないといけません。**SILOptimizerのPassではInstructionの特定にはダウンキャストを使っています。**

まず、先程の例の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
```

例えば、1行目の`integer_literal`は、Passでは`IntegerLiteralInst`という`SILInstruction`を継承した型で表現されています。2行目の`metatype`は`MetatypeInst`・・・。

では、すべてのInstructionは型で扱えるとして、今の`i`がどのInstructionなのかを調べたいですね。その時は、`dyn_cast`というキャストの関数を使います。

`dyn_cast`関数では、`<>`の中にキャストしたい型、引数にチェックしたいInstructionのポインタを入れます。普通の型をポインタ型に変換したいときは、変数の先頭に`&`をつけてください。

```cpp
auto currentFunction = getFunction();
for(auto &bb: *currentFunction) {
    for(auto &i: bb) {
        if(auto integerI = dyn_cast<IntegerLiteralInst>(&i)) {
                
        }
    }  
}
```

このC++書き方は**Swiftの`as?`による`nil`チェックに似ています。**
もし`dyn_cast`によるキャストが成功した場合、`if`の中で`integerI`は`IntegerLiteralInst`として取り扱われます。そうでなければ、`if`には入りません。

ここまで、このソースコードが何をやっているかをコメントで解説すると、

```cpp
// 今Passが見ているFunctionの情報をもらう
auto currentFunction = getFunction();
// Functionを構成してる各Basic Blockを見る
for(auto &bb: *currentFunction) {
    // Basic Blockを構成してる各Instructionを見る
    for(auto &i: bb) {
        // 今見ているInstructionが`integer_literal`なら・・・？
        if(auto integerI = dyn_cast<IntegerLiteralInst>(&i)) {
                
        }
    }  
}
```
こんなかんじです。

最後に、一つ重要な関数を紹介します。なにかしら、SILコードに変更があったときは、`run`関数の最後で`invalidateAnalysis`関数を最後に呼ばなければなりません。

```cpp
invalidateAnalysis(SILAnalysis::InvalidationKind::Instructions);
```

これは、Moduleに何かしらの変更をした際は必ず呼ばないといけない関数です。ここでは、Instructionを変更したことを引数に渡しています。
Analysisとは直訳すると解析ですが、たとえばclassの継承関係などの情報はAnalysisからもらうことがあります。

### C++を書く上での注意事項

C++を書く上での注意事項ですが、先程も言ったとおり**ポインタ型というものがあります。**
`int`を使った例を以下に載せます。

```cpp
// a は intの変数
int a = 10;

// b は int*(intのアドレス) の変数
int *b;

// &a はaのアドレスを表す
// bにaのアドレスを渡す
b = &a;

// ポインタ型に*をつけると、そのアドレスの参照先（実体）を示す
// ここではbにはaのアドレスが入っているので、cには10が入る。
int c = *b;
```

ほかにも`&`をつかう例として参照渡しや右辺値参照というものがありますが、C++の話は沼になるので省略します。

ポインタ型の関数や変数を呼び出すときは、`.`ではなく、`->`を使ってください。
たとえば、上の例だと、もし`integerI`の`getValue()`を呼びたいときは、

```cpp
if(auto integerI = dyn_cast<IntegerLiteralInst>(&i)) {
    // integerIはIntegerLiteralInstのポインタ型。
    // getValue()関数を呼びたいなら、-> を使う
    integerI->getValue(); // C++は文の最後にはセミコロンが必要です（２回め）
}
```

`auto`でとってきた変数がポインタ型かそうでないか迷ったときは、自動補完をしてくれるIDEの力に頼ってください。

## Passのデバックについて
たとえば、`SILBasicBlock`や`SILInstruction`には`dump`という関数があり、その変数がSILコード上のどのBasic Block（やInstruction)を表すかを出力させることができます。

また、`getFunction()->getName().str()` と書くことでマングルされた関数名を`string`で受け取ることができますし、`cout`を使ってそれを出力させることができます。

# 問題1: 簡単なPassを書いてみよう
## 問題

Swiftプログラムをシングルスレッド向けに最適化するPassであるAssume Single Threadedを作りましょう。このPassは、

- Reference Count関係のInstructionを`non-atomic`にする。

ということをやっています。
ここで補足しないといけないのは、Reference Count関係のInstructionは`RefCountingInst`型で表現されます。
`RefCountingInst`型には、そのInstructionを`non-atomic`にするメンバ関数があるので、探してみてください！

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


## 問題が終わったら？
問題をテストしてください。この問題のテストファイルは`swift`ディレクトリから見て`waiwai-test/question01.sil`です。

このテストの起動方法は、

```shell
# swiftディレクトリにいる想定
$ ../build/Xcode-DebugAssert/swift-macosx-x86_64/Debug/bin/sil-opt -wai-wai-optimizer waiwai-test/question01.sil | ../build/Xcode-DebugAssert/llvm-macosx-x86_64/Debug/bin/FileCheck waiwai-test/question01.sil
```

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

もし、TestだけでなくOptimizeされたsilを見たいのであれば、

```shell
# swiftディレクトリにいる想定
$ ../build/Xcode-DebugAssert/swift-macosx-x86_64/Debug/bin/sil-opt -wai-wai-optimizer waiwai-test/question01.sil -o waiwai-test/optimized-question-01.sil
```
を叩いて、`waiwai-test/optimized-question-01.sil`を見てみてください。成功していればちゃんと変更されてます。

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