最適化から見る、Swiftの / 2 と * 0.5

この記事は、CAM Advent Calendar 15日目の記事です:golf:
前回は @matsuhei さんによる、 [レガシーコードに対する解析ツール（重複コード編）](https://qiita.com/matsuhei/items/a0b73eca764be1ee383a)でした。

## 概要

以前、Swiftのコードを誰かに見せてたときに以下のように指摘されました。

> 誰か「ここ、 `/ 2` になっとるけど `* 0.5` のほうが速いで」
> 僕「あ、まぁ確かにそうですね（そんなに変わるかいな）」

確かに、基本的には割り算よりも掛け算のほうがパフォーマンスがいいです。直に頭で計算するとき、僕も掛け算のほうが計算しやすいです。計算理由にもよりますが、Swiftもその例から漏れないはずです。

ただ、iOSでは本番用のipaを作成するときにはリリースビルド（本番）が行われます。
速度ではなく、最適化の側面から見て、コードが一緒になってないかな？と思ったので、検証してみました。

## 検証環境

Apple Swift version 5.1.2 (swiftlang-1100.0.278 clang-1100.0.33.9)
Target: x86_64-apple-darwin19.0.0

## SIL
Swift Compiler は以下のようになっています。
<img width="968" alt="SS 2019-12-14 14.05.03.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/104868/bee565e2-3b0c-c64c-c95d-0c3cdfbc4312.png">

注目すべきはSILです。
SILは `Swift Intermediate Language` の略で、実行できるバイナリーに落とし込むために必要な中間言語です。
Swift CompilerはLLVM IRに落とし込む前にSILを生成します。
SILは主に２種類、 `raw SIL` と `canonical SIL` があります。
`raw SIL` は、AST(abstract syntax tree)から解析しやすいように変換された直後のものです。
`canonical SIL` は、 `raw SIL` を最適化された状態の SILです。

## 検証１

```sample1.swift
let aaa: Double = 200
let result: Double = aaa * 0.5
```

```sample2.swift
let aaa: Double = 200
let result: Double = aaa / 2
```

### 実行コード

```
$ swiftc -emit-sil -O sample1.swift > sample1.sil
$ swiftc -emit-sil -O sample2.swift > sample2.sil
```

`-emit-sil` で `canonical SIL` が生成されます。`raw SIL` を生成するには、 `-emit-silgen` と書けばよいです。
`-O` が付いていますが、これは canonical SIL からまた最適化が施された状態のものを生成するために必要なオプションで、ついてない場合は、 `-Onone` と同等です。

### 結果

```sample1.sil
sil_stage canonical

import Builtin
import Swift
import SwiftShims

@_hasStorage @_hasInitialValue let aaa: Double { get }

@_hasStorage @_hasInitialValue let result: Double { get }

// aaa
sil_global hidden [let] @$s7sample53aaaSdvp : $Double

// result
sil_global hidden [let] @$s7sample56resultSdvp : $Double

// main
sil @main : $@convention(c) (Int32, UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>) -> Int32 {
bb0(%0 : $Int32, %1 : $UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>):
  alloc_global @$s7sample53aaaSdvp                // id: %2
  %3 = global_addr @$s7sample53aaaSdvp : $*Double // user: %6
  %4 = float_literal $Builtin.FPIEEE64, 0x4069000000000000 // 200 // user: %5
  %5 = struct $Double (%4 : $Builtin.FPIEEE64)    // user: %6
  store %5 to %3 : $*Double                       // id: %6
  alloc_global @$s7sample56resultSdvp             // id: %7
  %8 = global_addr @$s7sample56resultSdvp : $*Double // user: %11
  %9 = float_literal $Builtin.FPIEEE64, 0x4059000000000000 // 100 // user: %10
  %10 = struct $Double (%9 : $Builtin.FPIEEE64)   // user: %11
  store %10 to %8 : $*Double                      // id: %11
  %12 = integer_literal $Builtin.Int32, 0         // user: %13
  %13 = struct $Int32 (%12 : $Builtin.Int32)      // user: %14
  return %13 : $Int32                             // id: %14
} // end sil function 'main'
```

```sample2.sil
sil_stage canonical

import Builtin
import Swift
import SwiftShims

@_hasStorage @_hasInitialValue let aaa: Double { get }

@_hasStorage @_hasInitialValue let result: Double { get }

// aaa
sil_global hidden [let] @$s7sample63aaaSdvp : $Double

// result
sil_global hidden [let] @$s7sample66resultSdvp : $Double

// main
sil @main : $@convention(c) (Int32, UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>) -> Int32 {
bb0(%0 : $Int32, %1 : $UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>):
  alloc_global @$s7sample63aaaSdvp                // id: %2
  %3 = global_addr @$s7sample63aaaSdvp : $*Double // user: %6
  %4 = float_literal $Builtin.FPIEEE64, 0x4069000000000000 // 200 // user: %5
  %5 = struct $Double (%4 : $Builtin.FPIEEE64)    // user: %6
  store %5 to %3 : $*Double                       // id: %6
  alloc_global @$s7sample66resultSdvp             // id: %7
  %8 = global_addr @$s7sample66resultSdvp : $*Double // user: %11
  %9 = float_literal $Builtin.FPIEEE64, 0x4059000000000000 // 100 // user: %10
  %10 = struct $Double (%9 : $Builtin.FPIEEE64)   // user: %11
  store %10 to %8 : $*Double                      // id: %11
  %12 = integer_literal $Builtin.Int32, 0         // user: %13
  %13 = struct $Int32 (%12 : $Builtin.Int32)      // user: %14
  return %13 : $Int32                             // id: %14
} // end sil function 'main'
```

### Diff

```diff
@@ -9,21 +9,21 @@
 @_hasStorage @_hasInitialValue let result: Double { get }
 
 // aaa
-sil_global hidden [let] @$s7sample53aaaSdvp : $Double
+sil_global hidden [let] @$s7sample63aaaSdvp : $Double
 
 // result
-sil_global hidden [let] @$s7sample56resultSdvp : $Double
+sil_global hidden [let] @$s7sample66resultSdvp : $Double
 
 // main
 sil @main : $@convention(c) (Int32, UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>) -> Int32 {
 bb0(%0 : $Int32, %1 : $UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>):
-  alloc_global @$s7sample53aaaSdvp                // id: %2
-  %3 = global_addr @$s7sample53aaaSdvp : $*Double // user: %6
+  alloc_global @$s7sample63aaaSdvp                // id: %2
+  %3 = global_addr @$s7sample63aaaSdvp : $*Double // user: %6
   %4 = float_literal $Builtin.FPIEEE64, 0x4069000000000000 // 200 // user: %5
   %5 = struct $Double (%4 : $Builtin.FPIEEE64)    // user: %6
   store %5 to %3 : $*Double                       // id: %6
-  alloc_global @$s7sample56resultSdvp             // id: %7
-  %8 = global_addr @$s7sample56resultSdvp : $*Double // user: %11
+  alloc_global @$s7sample66resultSdvp             // id: %7
+  %8 = global_addr @$s7sample66resultSdvp : $*Double // user: %11
   %9 = float_literal $Builtin.FPIEEE64, 0x4059000000000000 // 100 // user: %10
   %10 = struct $Double (%9 : $Builtin.FPIEEE64)   // user: %11
   store %10 to %8 : $*Double                      // id: %11
```

`float_literal $Builtin.FPIEEE64, 0x4059000000000000 // 100`
これ、 `200 / 2` した `100` を直接 result に突っ込んでますね……。
最適化された結果、SIL時点で実行時に計算されるのではなく結果のみを返されるようになりました。
リテラル値で計算されるから良いように最適化されたのかなと思ったので、検証コードを変更してみます。

## 検証２
```sample3.swift
func test(_ value: Double) -> Double {
  return value * 0.5
}
let result: Double = test(200.0)
```

```sample4.swift
func test(_ value: Double) -> Double {
  return value / 2
}
let result: Double = test(200.0)
```

### 結果

```sample3.sil
sil_stage canonical

import Builtin
import Swift
import SwiftShims

func test(_ value: Double) -> Double

@_hasStorage @_hasInitialValue let result: Double { get }

// result
sil_global hidden [let] @$s7sample36resultSdvp : $Double

// main
sil @main : $@convention(c) (Int32, UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>) -> Int32 {
bb0(%0 : $Int32, %1 : $UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>):
  alloc_global @$s7sample36resultSdvp             // id: %2
  %3 = global_addr @$s7sample36resultSdvp : $*Double // user: %6
  %4 = float_literal $Builtin.FPIEEE64, 0x4059000000000000 // 100 // user: %5
  %5 = struct $Double (%4 : $Builtin.FPIEEE64)    // user: %6
  store %5 to %3 : $*Double                       // 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'

// test(_:)
sil hidden @$s7sample34testyS2dF : $@convention(thin) (Double) -> Double {
// %0                                             // users: %3, %1
bb0(%0 : $Double):
  debug_value %0 : $Double, let, name "value", argno 1 // id: %1
  %2 = float_literal $Builtin.FPIEEE64, 0x3FE0000000000000 // 0.5 // user: %4
  %3 = struct_extract %0 : $Double, #Double._value // user: %4
  %4 = builtin "fmul_FPIEEE64"(%3 : $Builtin.FPIEEE64, %2 : $Builtin.FPIEEE64) : $Builtin.FPIEEE64 // user: %5
  %5 = struct $Double (%4 : $Builtin.FPIEEE64)    // user: %6
  return %5 : $Double                             // id: %6
} // end sil function '$s7sample34testyS2dF'
```

```sample4.sil
sil_stage canonical

import Builtin
import Swift
import SwiftShims

func test(_ value: Double) -> Double

@_hasStorage @_hasInitialValue let result: Double { get }

// result
sil_global hidden [let] @$s7sample46resultSdvp : $Double

// main
sil @main : $@convention(c) (Int32, UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>) -> Int32 {
bb0(%0 : $Int32, %1 : $UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>):
  alloc_global @$s7sample46resultSdvp             // id: %2
  %3 = global_addr @$s7sample46resultSdvp : $*Double // user: %6
  %4 = float_literal $Builtin.FPIEEE64, 0x4059000000000000 // 100 // user: %5
  %5 = struct $Double (%4 : $Builtin.FPIEEE64)    // user: %6
  store %5 to %3 : $*Double                       // 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'

// test(_:)
sil hidden @$s7sample44testyS2dF : $@convention(thin) (Double) -> Double {
// %0                                             // users: %3, %1
bb0(%0 : $Double):
  debug_value %0 : $Double, let, name "value", argno 1 // id: %1
  %2 = float_literal $Builtin.FPIEEE64, 0x4000000000000000 // 2 // user: %4
  %3 = struct_extract %0 : $Double, #Double._value // user: %4
  %4 = builtin "fdiv_FPIEEE64"(%3 : $Builtin.FPIEEE64, %2 : $Builtin.FPIEEE64) : $Builtin.FPIEEE64 // user: %5
  %5 = struct $Double (%4 : $Builtin.FPIEEE64)    // user: %6
  return %5 : $Double                             // id: %6
} // end sil function '$s7sample44testyS2dF'
```

### Diff

```diff
@@ -9,13 +9,13 @@
 @_hasStorage @_hasInitialValue let result: Double { get }
 
 // result
-sil_global hidden [let] @$s7sample36resultSdvp : $Double
+sil_global hidden [let] @$s7sample46resultSdvp : $Double
 
 // main
 sil @main : $@convention(c) (Int32, UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>) -> Int32 {
 bb0(%0 : $Int32, %1 : $UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>):
-  alloc_global @$s7sample36resultSdvp             // id: %2
-  %3 = global_addr @$s7sample36resultSdvp : $*Double // user: %6
+  alloc_global @$s7sample46resultSdvp             // id: %2
+  %3 = global_addr @$s7sample46resultSdvp : $*Double // user: %6
   %4 = float_literal $Builtin.FPIEEE64, 0x4059000000000000 // 100 // user: %5
   %5 = struct $Double (%4 : $Builtin.FPIEEE64)    // user: %6
   store %5 to %3 : $*Double                       // id: %6
@@ -25,16 +25,16 @@
 } // end sil function 'main'
 
 // test(_:)
-sil hidden @$s7sample34testyS2dF : $@convention(thin) (Double) -> Double {
+sil hidden @$s7sample44testyS2dF : $@convention(thin) (Double) -> Double {
 // %0                                             // users: %3, %1
 bb0(%0 : $Double):
   debug_value %0 : $Double, let, name "value", argno 1 // id: %1
-  %2 = float_literal $Builtin.FPIEEE64, 0x3FE0000000000000 // 0.5 // user: %4
+  %2 = float_literal $Builtin.FPIEEE64, 0x4000000000000000 // 2 // user: %4
   %3 = struct_extract %0 : $Double, #Double._value // user: %4
-  %4 = builtin "fmul_FPIEEE64"(%3 : $Builtin.FPIEEE64, %2 : $Builtin.FPIEEE64) : $Builtin.FPIEEE64 // user: %5
+  %4 = builtin "fdiv_FPIEEE64"(%3 : $Builtin.FPIEEE64, %2 : $Builtin.FPIEEE64) : $Builtin.FPIEEE64 // user: %5
   %5 = struct $Double (%4 : $Builtin.FPIEEE64)    // user: %6
   return %5 : $Double                             // id: %6
-} // end sil function '$s7sample34testyS2dF'
+} // end sil function '$s7sample44testyS2dF'
```

```
%4 = builtin "fmul_FPIEEE64"(%3 : $Builtin.FPIEEE64, %2 : $Builtin.FPIEEE64) : $Builtin.FPIEEE64 // user: %5
%4 = builtin "fdiv_FPIEEE64"(%3 : $Builtin.FPIEEE64, %2 : $Builtin.FPIEEE64) : $Builtin.FPIEEE64 // user: %5
```

割り算と掛け算がちゃんと別れています。
`/ 2` を自動的に `* 0.5` に変換される、なんてことはないようです。
ちなみに、`test(:)` に `@inlinable` を追加したら、検証１と同じ計算した結果の100の値保持されました。展開されて、最適化が施されたようです。

## まとめ

- リテラル値同士の計算は 最適化されて計算した結果のみ保持する

これを色々調べて思ったのは、ただ早いから `* 0.5` を選ぶのは軽率かなと思いました。可読性の問題もあったり、上の最適化されて結果同じ場合もあったりするので、そこらへんを正しく見極めて書いていくことが大事だと感じました。

次は16日目、@keitatata による [redis レプリケーションとシャーディング](https://qiita.com/keitatata/items/44678ad472e61a4606c5) です。お楽しみに。

## 追記

@pelican さんからご指摘を頂き、 `LLVM IR` での最適化後だと * 0.5 に変換されてるそうです。
sample3.swift, sample4.swift を再度検証しました。

### 実行コード

```
$ swiftc -emit-ir -O sample3.swift > sample3.ll
$ swiftc -emit-ir -O sample4.swift > sample4.ll
```

### 結果

```sample3.ll
; ModuleID = '-'
source_filename = "-"
target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-apple-macosx10.15.0"

%TSd = type <{ double }>

@"$s7sample36resultSdvp" = hidden local_unnamed_addr global %TSd zeroinitializer, align 8
@__swift_reflection_version = linkonce_odr hidden constant i16 3
@llvm.used = appending global [1 x i8*] [i8* bitcast (i16* @__swift_reflection_version to i8*)], section "llvm.metadata"

; Function Attrs: norecurse nounwind writeonly
define i32 @main(i32, i8** nocapture readnone) local_unnamed_addr #0 {
entry:
  store double 1.000000e+02, double* getelementptr inbounds (%TSd, %TSd* @"$s7sample36resultSdvp", i64 0, i32 0), align 8
  ret i32 0
}

; Function Attrs: norecurse nounwind readnone
define hidden swiftcc double @"$s7sample34testyS2dF"(double) local_unnamed_addr #1 {
entry:
  %1 = fmul double %0, 5.000000e-01
  ret double %1
}

attributes #0 = { norecurse nounwind writeonly "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "target-cpu"="penryn" "target-features"="+cx16,+fxsr,+mmx,+sahf,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" }
attributes #1 = { norecurse nounwind readnone "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "target-cpu"="penryn" "target-features"="+cx16,+fxsr,+mmx,+sahf,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" }

!llvm.module.flags = !{!0, !1, !2, !3, !4, !5, !6, !7, !8}
!swift.module.flags = !{!9}
!llvm.linker.options = !{!10, !11}
!llvm.asan.globals = !{!12}

!0 = !{i32 2, !"SDK Version", [2 x i32] [i32 10, i32 15]}
!1 = !{i32 1, !"Objective-C Version", i32 2}
!2 = !{i32 1, !"Objective-C Image Info Version", i32 0}
!3 = !{i32 1, !"Objective-C Image Info Section", !"__DATA,__objc_imageinfo,regular,no_dead_strip"}
!4 = !{i32 4, !"Objective-C Garbage Collection", i32 83953408}
!5 = !{i32 1, !"Objective-C Class Properties", i32 64}
!6 = !{i32 1, !"wchar_size", i32 4}
!7 = !{i32 7, !"PIC Level", i32 2}
!8 = !{i32 1, !"Swift Version", i32 7}
!9 = !{!"standard-library", i1 false}
!10 = !{!"-lswiftCore"}
!11 = !{!"-lobjc"}
!12 = distinct !{null, null, null, i1 false, i1 true}
```

```sample4.ll
; ModuleID = '-'
source_filename = "-"
target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-apple-macosx10.15.0"

%TSd = type <{ double }>

@"$s7sample46resultSdvp" = hidden local_unnamed_addr global %TSd zeroinitializer, align 8
@__swift_reflection_version = linkonce_odr hidden constant i16 3
@llvm.used = appending global [1 x i8*] [i8* bitcast (i16* @__swift_reflection_version to i8*)], section "llvm.metadata"

; Function Attrs: norecurse nounwind writeonly
define i32 @main(i32, i8** nocapture readnone) local_unnamed_addr #0 {
entry:
  store double 1.000000e+02, double* getelementptr inbounds (%TSd, %TSd* @"$s7sample46resultSdvp", i64 0, i32 0), align 8
  ret i32 0
}

; Function Attrs: norecurse nounwind readnone
define hidden swiftcc double @"$s7sample44testyS2dF"(double) local_unnamed_addr #1 {
entry:
  %1 = fmul double %0, 5.000000e-01
  ret double %1
}

attributes #0 = { norecurse nounwind writeonly "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "target-cpu"="penryn" "target-features"="+cx16,+fxsr,+mmx,+sahf,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" }
attributes #1 = { norecurse nounwind readnone "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "target-cpu"="penryn" "target-features"="+cx16,+fxsr,+mmx,+sahf,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" }

!llvm.module.flags = !{!0, !1, !2, !3, !4, !5, !6, !7, !8}
!swift.module.flags = !{!9}
!llvm.linker.options = !{!10, !11}
!llvm.asan.globals = !{!12}

!0 = !{i32 2, !"SDK Version", [2 x i32] [i32 10, i32 15]}
!1 = !{i32 1, !"Objective-C Version", i32 2}
!2 = !{i32 1, !"Objective-C Image Info Version", i32 0}
!3 = !{i32 1, !"Objective-C Image Info Section", !"__DATA,__objc_imageinfo,regular,no_dead_strip"}
!4 = !{i32 4, !"Objective-C Garbage Collection", i32 83953408}
!5 = !{i32 1, !"Objective-C Class Properties", i32 64}
!6 = !{i32 1, !"wchar_size", i32 4}
!7 = !{i32 7, !"PIC Level", i32 2}
!8 = !{i32 1, !"Swift Version", i32 7}
!9 = !{!"standard-library", i1 false}
!10 = !{!"-lswiftCore"}
!11 = !{!"-lobjc"}
!12 = distinct !{null, null, null, i1 false, i1 true}
```

### Diff

```diff
@@ -5,19 +5,19 @@
 
 %TSd = type <{ double }>
 
-@"$s7sample36resultSdvp" = hidden local_unnamed_addr global %TSd zeroinitializer, align 8
+@"$s7sample46resultSdvp" = hidden local_unnamed_addr global %TSd zeroinitializer, align 8
 @__swift_reflection_version = linkonce_odr hidden constant i16 3
 @llvm.used = appending global [1 x i8*] [i8* bitcast (i16* @__swift_reflection_version to i8*)], section "llvm.metadata"
 
 ; Function Attrs: norecurse nounwind writeonly
 define i32 @main(i32, i8** nocapture readnone) local_unnamed_addr #0 {
 entry:
-  store double 1.000000e+02, double* getelementptr inbounds (%TSd, %TSd* @"$s7sample36resultSdvp", i64 0, i32 0), align 8
+  store double 1.000000e+02, double* getelementptr inbounds (%TSd, %TSd* @"$s7sample46resultSdvp", i64 0, i32 0), align 8
   ret i32 0
 }
 
 ; Function Attrs: norecurse nounwind readnone
-define hidden swiftcc double @"$s7sample34testyS2dF"(double) local_unnamed_addr #1 {
+define hidden swiftcc double @"$s7sample44testyS2dF"(double) local_unnamed_addr #1 {
 entry:
   %1 = fmul double %0, 5.000000e-01
   ret double %1
```

```
%1 = fmul double %0, 5.000000e-01
```
ご指摘の通り、どちらのコードも * 0.5 になってます。

### 追記のまとめ

結果として、以下のことがわかりました。

* `/ 2` は `* 0.5` に変換される
* `SIL` と `LLVM IR` の最適化の内容が違う → 詳しく調べる

Swift Compilerは正しく最適化していました。
ただ、だから `* 0.5` しか使わないというわけではなく、文脈（％の計算なのか・半分にしたいのか）に応じて使い分けを行いリーダビリティを優先すべきと思いました。

## 参考資料
以下の資料は今回の記事を書く上で非常に参考になりました。ありがとうございます。

http://llvm.org/devmtg/2015-10/slides/GroffLattner-SILHighLevelIR.pdf
https://blog.waft.me/2018/01/09/swift-sil-1/
https://github.com/apple/swift/blob/master/docs/SIL.rst
https://qiita.com/Kuniwak/items/cbf6b88db249838895b5