SILOptimizerに軽く入門する

# SILOptimizerに軽く入門する
こんにちは、[freddi](https://twitter.com/___freddi___)です。Swiftを初めて１年位経ちましたが、今までの登壇内容などのせいか一部の人から「[リテラル](https://qiita.com/freddi_/items/044bdf6defbbe434a8e2)[おじさん](https://www.tryswift.co/events/2019/tokyo/jp/#literal)」と呼ばれるなど、リテラルハラスメントを受けています。
  
この記事は「[Swift Advent Calendar 2019](https://qiita.com/advent-calendar/2019/swift)」の15日目の記事です。皆さんが簡単に、Swiftコンパイラの最適化フェーズであるSILOptimizerを学べるようになるための、準備になる知識の内容を書いています。少々長いですが、ゆっくりお付き合いください。

## なぜSILOptimizerに入門すべきなのか？（ポエム）
さて、なぜ私たちは貴重なSwift Advent Calendarの一枠を使ってまで、SILOptimizer入門にすべきなのでしょうか？
あるとしたら、Swiftのコードの「理不尽な動かない」に対しての、理解や考察の糧をある程度持ってもらいたいからです。

詳しくはこのあと話しますが、SILOptimizerでは最適化オプションによっては特定のコードを削除したりします。また、iOSアプリケーション開発でも`Debug`と`Release`では最適化オプションも違います。
  
つまり、コードによってはiOSアプリで`Debug`と`Release`で挙動が違ってくるかもしれません。それは一概に最適化のせい、とは言えません。しかし、例えば最適化によってコードが消えた結果、`Debug`と`Release`では全然挙動は違うということは無きにしもあらずです。私もプロダクト開発では何度か出くわしました。

それを「勝手に挙動が変わった」と思うのと「最適化に問題があるな」と思うのでは、全然視点とモチベーションが違います。「理不尽な動かない」に直面したとき、SILOptimizerなどの最適化の知識を一つの考察の糧にすると、もしかしたら「勝手に挙動が変わった」と思う世界線の自分とは違った、またスマートで面白い打開策を見つけられるかもしれません。

今回の解説記事だけではそこまでのレベルに達するのは難しいですが、他の資料などを見るときなどにの補助になる知識になると思います。

## Swiftコンパイラのコンパイルの流れ
まずはじめに、事前知識としてSwiftコンパイラのコンパイルのフローを復習します。知っている人は飛ばしても構いません。

私達が書いたSwiftコードはSwiftコンパイラにコンパイルされ、目的の成果物になります。それは、アプリになったり、frameworkだったり、オブジェクトファイル[^objectfile]だったり。

さて、私達のSwiftコードは、目的の成果物になるまでは、コンパイラの中ではいくつかのフェーズを経ています。
Swiftコンパイラのフロー図を利用して紹介します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/152231/af6bdf5f-5f69-46d7-9fa6-10dfdc37362c.png)
(引用元: https://www.slideshare.net/kitasuke/sil-for-first-time-leaners/1 by kitasuke)

まず、Swiftのコードは**Parse**のフェーズで**抽象構文木(AST)**になり、**Sema**のフェーズでその抽象構文木に**型(Type)情報**が付きます。
その後、型情報付きのASTは**SILGen**で中間言語である**Swift Intermediate Language(SIL)**のコードになり、ここで**SILOptimizer**によって最適化が入ります。
最後に、最適化されたSILは**IRGen**によって**LLVM IR**のコードになった後、目的の成果物になります。

## Swiftコンパイラの最適化のフェーズ SILOptimizer
SwiftコンパイラはSILGenのフェーズで、Swift Intermediate Language(以下SIL)と呼ばれる中間言語に変換して、LLVM IRに変換します。
その、LLVM IRに変換する前に、そのSILを最適化を行うフェーズがあります。それが今回話す**SILOptimizer**[^genoptimizer]です。

## SILOptimizerの役割
Optimizerとの名のある通り、SILOptimizerは**Swiftのプログラムの最適化**[^program]を行います。

どのような最適化を行うか、簡単な例を少しだけ出すと、

- 不必要なコードの削除[^elimination]
  - 使われていない変数・定数を見つけ出して削除し、メモリに不必要なものが乗らないようにする
- できる限りHeapをStackにする[^stackheap]
  - プログラムの中でStackで確保できそうなところはすべてStackに変えて、プログラムのパフォーマンスを上げる

このように、私達のSwiftのプログラムをより良くするために、**中間言語であるSILのコードをSILOptimizerは最適化してくれています。**

## SILの最適化
ここからは最適化対象である、SILについてフォーカスしたお話をします。

実は、SILといえども、２種類のSILが存在しています。おおまかに、**SILOptimizerから出たか（最適化された）** or **出てないか**[^generaloptimization]、で分けられています。

### raw SIL
まず、SILGenから出たばかりの最適化がされていないSILは、**raw SIL**と呼ばれています。

では、試しに次のコードのraw SILをみてみましょう。

```swift:value.swift
let value = 10
```

raw SILは`swiftc`の`-emit-silgen`オプションで見ることができます。

```sh
swiftc value.swift -emit-silgen > value.sil
```

<details><summary>そして出力されたraw SILのコードがこちらです。(クリックで展開)</summary><div>
※ 無理やりSwiftのSyntaxハイライトを入れています。

```swift:value.sil
sil_stage raw

import Builtin
import Swift
import SwiftShims

@_hasStorage @_hasInitialValue let value: Int { get }

// value
sil_global hidden [let] @$s5valueAASivp : $Int

// main
sil [ossa] @main : $@convention(c) (Int32, UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>) -> Int32 {
bb0(%0 : $Int32, %1 : $UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>):
  alloc_global @$s5valueAASivp                    // id: %2
  %3 = global_addr @$s5valueAASivp : $*Int        // user: %8
  %4 = integer_literal $Builtin.IntLiteral, 10    // user: %7
  %5 = metatype $@thin Int.Type                   // user: %7
  // function_ref Int.init(_builtinIntegerLiteral:)
  %6 = function_ref @$sSi22_builtinIntegerLiteralSiBI_tcfC : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %7
  %7 = apply %6(%4, %5) : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %8
  store %7 to [trivial] %3 : $*Int                // id: %8
  %9 = integer_literal $Builtin.Int32, 0          // user: %10
  %10 = struct $Int32 (%9 : $Builtin.Int32)       // user: %11
  return %10 : $Int32                             // id: %11
} // end sil function 'main'

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

初見だと、もとのSwiftのコードより非常に複雑だと思ってしまうようなコードが出てきましたね。

### canonical SIL
SILOptimizerから出て最適化がされたSILは、**canonical SIL**と呼ばれています。

では、最適化されたcanonical SILのコードを見たいと思います。raw SILをcanonical SILにするのは簡単で、`swiftc`の`-emit-sil`オプションを指定して、先程出力した`value.sil`を渡せばよいです。

```sh
swiftc value.sil -emit-sil > value-canonical.sil
```

swiftコードから直接canonical SILを出すこともできます。

```sh
swiftc value.swift -emit-sil > value-canonical.sil
```

<details><summary>そして出力されたcanonical SILのコードがこちらです。(クリックで展開)</summary><div>
※ 無理やりSwiftのSyntaxハイライトを入れています。

```swift:value-canonical.sil
sil_stage canonical

import Builtin
import Swift
import SwiftShims

@_hasStorage @_hasInitialValue let value: Int { get }

// value
sil_global hidden [let] @$s5valueAASivp : $Int

// main
sil @main : $@convention(c) (Int32, UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>) -> Int32 {
bb0(%0 : $Int32, %1 : $UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>):
  alloc_global @$s5valueAASivp                    // id: %2
  %3 = global_addr @$s5valueAASivp : $*Int        // user: %6
  %4 = integer_literal $Builtin.Int64, 10         // user: %5
  %5 = struct $Int (%4 : $Builtin.Int64)          // user: %6
  store %5 to %3 : $*Int                          // id: %6
  %7 = integer_literal $Builtin.Int32, 0          // user: %8
  %8 = struct $Int32 (%7 : $Builtin.Int32)        // user: %9
  return %8 : $Int32                              // id: %9
} // end sil function 'main'

// Int.init(_builtinIntegerLiteral:)
sil public_external [transparent] [serialized] @$sSi22_builtinIntegerLiteralSiBI_tcfC : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int {
// %0                                             // user: %2
bb0(%0 : $Builtin.IntLiteral, %1 : $@thin Int.Type):
  %2 = builtin "s_to_s_checked_trunc_IntLiteral_Int64"(%0 : $Builtin.IntLiteral) : $(Builtin.Int64, Builtin.Int1) // user: %3
  %3 = tuple_extract %2 : $(Builtin.Int64, Builtin.Int1), 0 // user: %4
  %4 = struct $Int (%3 : $Builtin.Int64)          // user: %5
  return %4 : $Int                                // id: %5
} // end sil function '$sSi22_builtinIntegerLiteralSiBI_tcfC'
```
</div></details>

なんかところどころ違いますが、もとのSwiftのコードより複雑なのは変わりないですね。

### raw SILとcanonical SILの違いを見る
さて、raw SILとcanonical SILの違いは一体何でしょうか？
気づいた人もいるかも知れませんが、まず一行目が違います。

```swift:value.sil
// 1行目
sil_stage raw
```

```swift:value-canonical.sil
// 1行目
sil_stage canonical
```

みたとおりなのですが、SILのコードは一行目でこのSILがraw SILかcanonical SILを示しています。
さて、それだけでしょうか？

実は、`Int`の定数`value`を宣言して、`10`を代入している部分も大きく違います。

```swift:value.sil
// 15行目以降
  alloc_global @$s5valueAASivp                    // id: %2
  %3 = global_addr @$s5valueAASivp : $*Int        // user: %8
  %4 = integer_literal $Builtin.IntLiteral, 10    // user: %7
  %5 = metatype $@thin Int.Type                   // user: %7
  // function_ref Int.init(_builtinIntegerLiteral:)
  %6 = function_ref @$sSi22_builtinIntegerLiteralSiBI_tcfC : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %7
  %7 = apply %6(%4, %5) : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %8
  store %7 to [trivial] %3 : $*Int                // id: %8
```

```swift:value-canonical.sil
// 15行目以降
  alloc_global @$s5valueAASivp                    // id: %2
  %3 = global_addr @$s5valueAASivp : $*Int        // user: %6
  %4 = integer_literal $Builtin.Int64, 10         // user: %5
  %5 = struct $Int (%4 : $Builtin.Int64)          // user: %6
  store %5 to %3 : $*Int                          // id: %6
```

明らかに、canonical SILのほうが、raw SILよりも行数も少ないですね。**これはraw SILから不必要なコードが削除されたり、別のコードに交換されたりしたことを示しており、これはSILOptimizerが行っています。**

## 最適化のPassとPipeLine

さて、ここからはSILOptimizerについてフォーカスしたお話をします

### Passとは？
SILOptimizerという一つの大きなモジュールが、すべての最適化を担っているわけではありません。
SILOptimizerは、**Pass**[^llvmpass]という細かいモジュールが多数存在しており、そのPass達がそれぞれの役割の最適化を行っています。

例えば、先程話した「できる限りHeapをStackにする」のも実は**AllocBoxToStack**と呼ばれるPassが行っています。

### オプションとPass
Swiftコードをコンパイルするときに、**SILOptimizerは必ず呼び出され、その中のいくつかのPassも必ず呼ばれます**。
例えば、先程話したAllocBoxToStackは必ず呼ばれます。

しかし、「いくつかのPassも必ず呼ばれます」と言ったとおり、**SILOptimizerの中のすべてのPassが、意思表示もなしに必ず呼ばれるわけではないです**。  
わかり易い例として、`assert`と`precondition`が**最適化オプション次第で消えるという**ものがあります。**これはSILOptimizerのあるPassが該当のコードを削除しているから**です。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/152231/d91873fc-5553-5207-b823-5044d9aa776f.png)
(引用元: http://safx-dev.blogspot.com/2015/02/swift-assert-precondition-and-fatalerror.html by Safx)


つまり、最適化オプションだけが、Passを呼ぶか呼ばないかの判断になっているのでしょうか？
皆さんは馴染みがないと思いますが、たとえばswiftcに`-assume-single-threaded`というオプションを付けると、Single Thread向けの成果物を出力します。

```sh
swiftc -assume-single-threaded value.swift
```

これは、Single Thread向けに最適化するPassである**AssumeSingleThreaded**[^assumesinglethreaded]を呼び出すオプションでもあります。

つまり、

- SILOptimizerのPassは、**最適化オプションによっては呼ばれるものと呼ばれないものがある**
- AssumeSingleThreadedのような、**オプションで呼び出すPassもある**

という事がわかります。

実際にはどうやっているかと言うと、Swiftコンパイラは、オプションなどの状況からPassの通り道である**Pipeline**というものを作り上げます。
このPipelineにどのPassが通るかを設定し、raw SILはPipelineどおりに最適化されます。

ここまでまとめると、SILOptimizerのオーバービューはこんな感じになります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/152231/3b16dafb-7bcd-3928-c34b-834b828fb180.png)
(引用元: https://www.slideshare.net/YukiAki/tutorial-for-developing-siloptimizer-pass by freddi)

## SILOptimizerはコードの「診断」もやっている
さて、ここまでSILOptimizerの最適化の話をしてきましたが、実はSILOptimizerはコードの**「診断(Diagnostic)」**を行うPassもあります。
代表的なものとして、数値系のオーバーフローのチェックをするPassがあります。このPassは、数値系のオーバーフローがあったらその場でエラーを出します。

ここで、皆さんに宿題を出します。

```swift:overflow.swift
let value = 100000000000000000000 //コンパイルできない
```

この、overflow.swiftは普通にコンパイルしようとすると、

```sh
$ swiftc overflow.swift
value.swift:1:13: error: integer literal '100000000000000000000' overflows when stored into 'Int'
let value = 100000000000000000000 //コンパイルできない
```

とコンパイルエラーになります。これは`100000000000000000000`が`Int`だとオーバーフローするから当然ですね。

では、`-emit-silgen`と`-emit-sil`のオプションをつけたときに、それぞれどのようにエラーが変化するでしょうか？

実際にこのことをご自身の手を動かしてみて確かめてみてください。Swiftコンパイラのフローの中にあるSILOptimierについて、実際に体感することができます。[^option]


## もっと学びたい人向けに
ここからSILOptimizerが興味がある人向けに、勉強になるマテリアルをいくつか紹介します。
これらのSILOptimizerに関する資料は、だいたいSwiftコンパイラのコードをリーディングしたりいじったりするものなので、これらをこなすと更に深くSILOptimizerについて勉強することができます。

### SIL入門
近年はSILの解説資料が多くなってきており、よりSILに入門しやすくなりました。

#### SIL for First Time Learners(SIL入門)
- https://www.youtube.com/watch?v=sT0SNp-Tw-8
- 書き起こし: http://niwatako.hatenablog.jp/entry/2018/03/01/104747

#### Swiftの中間言語SILを読む シリーズ
https://blog.waft.me/2018/01/09/swift-sil-1/

#### SILを読もう
https://www.youtube.com/watch?v=jih0ljNpODs

### Swift Compilerの最適化入門 - AllocBoxToStack編
この文章の中で何回か言及したAllocBoxToStackに関して、この動画では詳しい解説をしています。
https://www.youtube.com/watch?v=hsO3PWH9Rcw

また、発表者のkitasukeさんんはAllocBoxToStack編に関する書籍も販売しているのでぜひ読んでみてください。
https://kitasuke.booth.pm/items/1034691


### SILOptimizerを自分で作って遊んで見る
SILOptimizerのPassを自分で作って遊んでみようという題材の発表です。SILOptimizerが何をやっているのか、SILOptimizerのコードを読み歩き方などを解説しています。
https://www.youtube.com/watch?v=QBXcCTfwyZ8

また、SIL以外にもSwiftコンパイラのディープな話題に興味が出てきた方は、ぜひ、わいわいswiftc[^waiwai]という勉強会に参加するといいかもしれません。

## まとめ
SILOptimizerのPassなどを含んだ簡単なオーバービューや、SILOptimizerがどのような最適化を行っているかについて話しました。
冒頭にも言ったとおり、これはベースになる知識のみの解説記事なので、もし興味が出たら「もっと学びたい人向けに」にある資料などをみて勉強してみてください。

ご精読（？）ありがとうございました。明日の16日目の[homunuz](https://qiita.com/homunuz)さんのネタに期待しています！

[^generaloptimization]: General Optimizationとよばれる、canonical SILをさらにOptimizeするフェーズがあるのですが、今回は割愛しています。詳しくは https://blog.waft.me/2018/01/09/swift-sil-1/

[^stackheap]: StackとHeapには利点と不利な点があります。しかし、StackのほうがHeapよりも好まれている、と言われてピンとこない方は https://keens.github.io/blog/2017/04/30/memoritosutakkutohi_puto/ あたりを見ると良いかもしれません。https://developer.apple.com/videos/play/wwdc2016/416/ ではSwiftにフォーカスした話が聞けます。

[^program]: ここでSwiftコードと書かなかった理由は、**あくまでSILOptimizerはraw SILを最適化しているのであり、Swiftコードを直接最適化しているわけではない**からです。

[^genoptimizer]: SILOptimizerは、フロー図のようにSILGenとひとくくりにされていることがあります。

[^objectfile]: オブジェクトファイルってなんぞや、って思う人がいるかも知れませんが、その人はオブジェクトファイルというものから知るよりも、基本的にプログラミング言語のコンパイラがやっていることから知るのがいいかもしれません。こちらにC言語のコンパイルの解説がありますのでご参照ください。http://aoking.hatenablog.jp/entry/20121109/1352457273

[^llvmpass]: SILGenの後のフェーズのLLVMの最適化のモジュールもPassと呼ばれるものです。https://www.ibm.com/developerworks/jp/opensource/library/os-createcompilerllvm2/index.html

[^elimination]: 英語だと、**Code Elimination**と言います。たとえば、機能していないコードを最適化で消すことを**Dead Code Elimination(DCE)**といいます。DCEと言う略し方はSwiftコンパイラのコードでもよく使われており、単語として覚えていて損はありません。https://github.com/apple/swift/blob/62ccf81f7748e3e2c8626354d1ecb3adbd26b063/lib/SILOptimizer/SILCombiner/SILCombine.cpp#L51 こんなとことか。

[^assumesinglethreaded]: 昔私が少々解説した資料があるので、ご興味があればご参照ください。https://www.slideshare.net/YukiAki/siloptimizercode-reading

[^option]: もっと知りたい人は、これでコンパイルしてみてください → `swiftc -Xllvm -sil-print-pass-name overflow.swift`。「SILOptimizerを自分で作って遊んで見る」という動画でも詳しく説明していますが、SILが通ったPassを見ることができます。

[^waiwai]: connpassはこちら → https://iosdiscord.connpass.com/ 。中継もやっており、私はたまにそちらで見ています。また、いままでの中継はアーカイブとして残っています。https://www.youtube.com/results?search_query=%E3%82%8F%E3%81%84%E3%82%8F%E3%81%84swiftc