LoginSignup
175
142

More than 3 years have passed since last update.

@omochimetaru(metaru omochi)inQoncept, Inc.

Swiftのジェネリックなプロトコルの変数はなぜ作れないのか、コンパイル後の中間言語を見て考えた

Last updated at Posted at 2016-03-10

導入

Swiftでは通常のプロトコルは変数の型として使用することができますが、
型パラメータ(associated type)を持つジェネリックなプロトコルの変数は作れません。

非ジェネリックな例

protocol Hogeable {
    func hoge() -> Int
}
struct HogeCat: Hogeable {
    func hoge() -> Int { return 1111 }
}
let cat = HogeCat()
let hogeable: Hogeable = cat
// コンパイルOK

ジェネリックな例

protocol Fugable {
    typealias Element
    func fug() -> Element
}
struct FugaDog: Fugable {
    func fuga() -> Int { return 2222 }
}
let dog = FugaDog()
let fugable: Fugable = dog 
// コンパイルエラー
// protocol 'Fugable' can only be used as a generic constraint because it has Self or associated type requirements

これはJavaの感覚からすると不便です。
なぜこれができないのか考えを深めるために、
コンパイラの生成する中間コードを見て調べてみました。

結論

わかったことからの推測になりますが、
最適化しやすいコードが自然と多く生成されるように、
あえてそれを阻害するこの機能を言語仕様に含めていない
のだと思いました。

環境

Apple Swift version 2.1.1 (swiftlang-700.1.101.15 clang-700.1.81)

関連テクニック

そもそもこのようなケースに対して、
いくつかの妥協案が存在するので先に紹介します。

Type Erasure

try! Swiftではこのようなケースに対して、
下記のようにType Erasureを作るワークアラウンドが紹介されていました。

Type Erasureの例

struct AnyFugable<T>: Fugable {
    typealias Element = T
    private let fuga_: () -> T
    init<F: Fugable where F.Element == T>(inner: F) {
        fuga_ = { inner.fuga() }
    }
    func fuga() -> T { return fuga_() }
}
let dog = FugaDog()
let fugable: AnyFugable = AnyFugable(inner: dog)

Swiftの標準ライブラリでもSequenceTypeに対してAnySequenceが実装されているなど、
このパターンが使用されています。

このパターンの問題点として、
AnyFugableの中に入れたinnerが、
動的型判定やキャストによって取り出す事ができないというものがあります。
これにより、包んだところで内部の値がもっている他のプロトコルも失われることになります。

ただ、SequenceTypeのように、値的に扱える型であればそれで困る事はありません。

これらをJavaのinterfaceと比べると、
Javaでは型判定とダウンキャストをすることができてSwiftは不便になっています。

それと、実装が面倒くさいです。

そもそもClassを使う

そもそもプロトコルではなくClassを使って、
オーバライドによるポリモーフィズムで設計すれば型パラを含む参照型の変数を定義できます。
これで済む場合もあります。

しかし、クラスだと多重継承できないなどの問題があります。

特定のStructに変換する

例えばSequenceTypeの場合は、Array<T>に変換してしまえば保持できます。
これで済む場合もあります。

しかしこの場合、一度Arrayにするために要素のコピーが必要で、処理コストがかかります。
また、もともとのSequenceTypeが持っていたデータ構造とは関係なくなるため、
メソッドに対してオブジェクトごとにふるまいを変える事ができません。

JavaだとListインターフェースに対して、
ArrayListを入れたりLinkedListを入れたりするパターンが基本ですが、
それができません。

AnySequenceでは元のオブジェクトを保持しているので、
ふるまいは保持されます。

変数は作れないが、ジェネリックな関数は作れる

let fugable: Fugableを定義することはできません。
つまり、型パラを特殊化した型として変数を定義して値を保持する事はできません。
ですが、型パラを特殊化した型に値を与える事はできます。
ジェネリック関数です。

func callIntFugableFuga<F: Fugable where F.Element == Int>(fugable: F) -> Int {
    return fugable.fuga()
}
let dog = FugaDog()
callIntFugableFuga(dog)

上記のコードはコンパイルできて動きます。
callIntFugableFugaの引数fugableの型は、
型パラメータElementがIntに制約されたFugableです。

本来、値を変数へ代入する場合と、
値を関数の引数へ渡す場合の、
型システムとしてのルールは同じですが、
変数に定義する事はできなくても、
関数の仮引数として定義した変数に束縛する事は可能なのです。

これを軸に調査を進めました。

プロトコルによる動的ディスパッチの実装 (SIL)

そもそも、プロトコルとして値を扱うというのはどういう事なのでしょうか。
例えば、同じFugableプロトコルを満たしているstruct FugaDogと、struct FugaElephantがあった時、
なぜどちらも同じようにFugable型の変数に代入できるのでしょう。

両方とも値型で、異なるフィールド、メソッド定義を持つのに、
なぜ互換性のあるオブジェクトとして扱え、
メソッドを呼び分ける事ができるのでしょうか。

実際にその変換が行われるところを中間コードで見てみれば、
より内部の理解ができると思われます。

まず下記のようなコードを用意します。

// 1.swift
protocol Hogeable {
    func hoge() -> Int
}
struct HogeCat: Hogeable {
    func hoge() -> Int { return 1111 }
}

func callHogeableHoge(hogeable: Hogeable) -> Int {
    return hogeable.hoge()
}
func callCatHoge(cat: HogeCat) -> Int {
    return callHogeableHoge(cat)
}

print(callCatHoge(HogeCat()))

callHogeableHogeはHogeableの引数を取ります。
callCatHogeはHogeCatの引数を取り、callHogeableHogeに渡します。

なので、callCatHogeの内部で、HogeCatからHogeableへの変換が起こります。
この部分の生成コードを特に調べてみましょう。

SILについて

なお、Swiftのコンパイルは、まずSILという中間コードを生成し、
そこからLLVM IRという中間コードを生成し、
最後にネイティブバイナリを生成します。

SILは型システムとしてはSwiftレベルのものを持っていますが、
メソッド定義などは関数定義に書き下され、
制御構文はアセンブリ的なラベルジャンプになっています。

SILにはraw SILとcanonical SILがあり、
rawからcanonicalへの変換時にいくつかの最適化が行われます。

今回はまず、Swiftからなるべく近い、最適化無しのraw SILを調べてみます。

なお、SILのコードを読むときは、このドキュメントを参照すると良いです。

SILコードを読む

下記コマンドでコンパイラでSILコードを生成します。
最適化をしないように指定します。

swiftc -emit-silgen -Onone 1.swift > 1-rawsil.sil

出力結果から余計なものを削除して部分引用します。

// main.HogeCat.hoge (main.HogeCat)() -> Swift.Int
sil hidden @_TFV4main7HogeCat4hogefS0_FT_Si : $@convention(method) (HogeCat) -> Int {
    ...
}
// protocol witness for main.Hogeable.hoge <A where A: main.Hogeable> (A)() -> Swift.Int in conformance main.HogeCat : main.Hogeable in main
sil hidden [transparent] [thunk] @_TTWV4main7HogeCatS_8HogeableS_FS1_4hogeuRq_S1__fq_FT_Si : $@convention(witness_method) (@in_guaranteed HogeCat) -> Int {
    ...
}
// main.callHogeableHoge (main.Hogeable) -> Swift.Int
sil hidden @_TF4main16callHogeableHogeFPS_8Hogeable_Si : $@convention(thin) (@in Hogeable) -> Int {
    ...
}
// main.callCatHoge (main.HogeCat) -> Swift.Int
sil hidden @_TF4main11callCatHogeFVS_7HogeCatSi : $@convention(thin) (HogeCat) -> Int {
    ...
}
sil_witness_table hidden HogeCat: Hogeable module main {
    ...
}

silで始まっているところが関数定義です。
いま、4つの関数定義がありますが、一番気になるcallCatHogeの実装を見てみましょう。

// main.callCatHoge (main.HogeCat) -> Swift.Int
sil hidden @_TF4main11callCatHogeFVS_7HogeCatSi : $@convention(thin) (HogeCat) -> Int {
bb0(%0 : $HogeCat):
  debug_value %0 : $HogeCat  // let cat           // id: %1
  // function_ref main.callHogeableHoge (main.Hogeable) -> Swift.Int
  %2 = function_ref @_TF4main16callHogeableHogeFPS_8Hogeable_Si : $@convention(thin) (@in Hogeable) -> Int // user: %6
  %3 = alloc_stack $Hogeable                      // users: %4, %6, %7
  %4 = init_existential_addr %3#1 : $*Hogeable, $HogeCat // user: %5
  store %0 to %4 : $*HogeCat                      // id: %5
  %6 = apply %2(%3#1) : $@convention(thin) (@in Hogeable) -> Int // user: %8
  dealloc_stack %3#0 : $*@local_storage Hogeable  // id: %7
  return %6 : $Int                                // id: %8
}

この行で、引数として受けたHogeCat型の変数を、%0と名前付けしています。

bb0(%0 : $HogeCat):

この行で、関数@_TF4main16callHogeableHogeFPS_8Hogeable_Siを%2に代入しています。
この関数は、最初に引用したとおり、callHogeableHogeがコンパイルされたものです。

%2 = function_ref @_TF4main16callHogeableHogeFPS_8Hogeable_Si : $@convention(thin) (@in Hogeable) -> Int // user: %6

次の行で、スタックメモリに$Hogeable型のサイズの領域を確保し、そのポインタを%3としています。
その次で、その領域(%3)をHogeCat用のHogeable領域として初期化し、
その次で、その領域(%4)に引数で受けたcat(%0)をコピーしています。
(%3の後ろに付いている#1の意味はわからなかったので、スルーします。)

  %3 = alloc_stack $Hogeable                      // users: %4, %6, %7
  %4 = init_existential_addr %3#1 : $*Hogeable, $HogeCat // user: %5
  store %0 to %4 : $*HogeCat                      // id: %5

最後に、%2に用意した関数を、catから作った$Hogeableへのポインタ%3を渡して呼び出します。

  %6 = apply %2(%3#1) : $@convention(thin) (@in Hogeable) -> Int // user: %8

つまり、ここまでの内容により、
HogeCatをHogeableとして渡すときには、
HogeCatのアドレスをそのまま渡しているわけではなく、
いったんアクセスを仲介するための$Hogeable型のオブジェクトを作り、
HogeableからHogeCatを間接的に参照させる形を作って呼び出していた事がわかりました。

さて、後ろの方に関数定義とは別の次のようなコードがあります。

sil_witness_table hidden HogeCat: Hogeable module main {
  method #Hogeable.hoge!1: @_TTWV4main7HogeCatS_8HogeableS_FS1_4hogeuRq_S1__fq_FT_Si    // protocol witness for main.Hogeable.hoge <A where A: main.Hogeable> (A)() -> Swift.Int in conformance main.HogeCat : main.Hogeable in main
}

これはwitnessテーブルを定義しているコードです。

witnessテーブルというものについて調べた結果、
これは雑に言うと仮想関数テーブルのプロトコル版のようなものです。

ここで生成されているのはHogeCatがHogeableとして振る舞う時のオブジェクトが使うための、
ディスパッチテーブルです。

Hogeableにはメソッドhogeが一つだけ定義されているため、
それに対応してこのテーブルにも、メソッド#Hogeable.hoge!1として、
関数@_TTWV4main7HogeCatS_8HogeableS_FS1_4hogeuRq_S1__fq_FT_Siが登録されています。

これの定義を見てみます。

// protocol witness for main.Hogeable.hoge <A where A: main.Hogeable> (A)() -> Swift.Int in conformance main.HogeCat : main.Hogeable in main
sil hidden [transparent] [thunk] @_TTWV4main7HogeCatS_8HogeableS_FS1_4hogeuRq_S1__fq_FT_Si : $@convention(witness_method) (@in_guaranteed HogeCat) -> Int {
bb0(%0 : $*HogeCat):
  %1 = alloc_stack $HogeCat                       // users: %2, %3, %6
  copy_addr %0 to [initialization] %1#1 : $*HogeCat // id: %2
  %3 = load %1#1 : $*HogeCat                      // user: %5
  // function_ref main.HogeCat.hoge (main.HogeCat)() -> Swift.Int
  %4 = function_ref @_TFV4main7HogeCat4hogefS0_FT_Si : $@convention(method) (HogeCat) -> Int // user: %5
  %5 = apply %4(%3) : $@convention(method) (HogeCat) -> Int // user: %7
  dealloc_stack %1#0 : $*@local_storage HogeCat   // id: %6
  return %5 : $Int                                // id: %7
}

ざっくり読むと、関数の引数として$HogeCatへのポインタを受け取り、
その受け取ったオブジェクトを、
関数@_TFV4main7HogeCat4hogefS0_FT_Siに渡して呼び出す、
という形をしています。

関数@_TFV4main7HogeCat4hogefS0_FT_SiはHogeCatのhogeメソッドがコンパイルされたもので、
引数として$HogeCatを受け取り、その処理を実行する、というものです。

つまり、witnessテーブルに登録されている関数は、
HogeCatという実際の型がHogeableというプロトコルとして使われている時のための、
HogeCatの本当のメソッドを呼び出すグルーコードが書かれたもの、
という事がわかります。

最後に、callHogeableHogeのSILコードを見てみます。

// main.callHogeableHoge (main.Hogeable) -> Swift.Int
sil hidden @_TF4main16callHogeableHogeFPS_8Hogeable_Si : $@convention(thin) (@in Hogeable) -> Int {
bb0(%0 : $*Hogeable):
  debug_value_addr %0 : $*Hogeable  // let hogeable // id: %1
  %2 = open_existential_addr %0 : $*Hogeable to $*@opened("0EAE1E88-E6A6-11E5-97B8-A8667F09828A") Hogeable // users: %3, %4
  %3 = witness_method $@opened("0EAE1E88-E6A6-11E5-97B8-A8667F09828A") Hogeable, #Hogeable.hoge!1, %2 : $*@opened("0EAE1E88-E6A6-11E5-97B8-A8667F09828A") Hogeable : $@convention(witness_method) <τ_0_0 where τ_0_0 : Hogeable> (@in_guaranteed τ_0_0) -> Int // user: %4
  %4 = apply %3<@opened("0EAE1E88-E6A6-11E5-97B8-A8667F09828A") Hogeable>(%2) : $@convention(witness_method) <τ_0_0 where τ_0_0 : Hogeable> (@in_guaranteed τ_0_0) -> Int // user: %6
  destroy_addr %0 : $*Hogeable                    // id: %5
  return %4 : $Int                                // id: %6
}

なんだかよくわからないUUIDが出てきて読みづらいですが、
ざっくりと構造を読み取ると、
引数で受け取った$Hogeableへのポインタ%0が、
%2を経由して、witness_method命令に渡され、
取得した関数%3を、これまで同様applyで呼び出す、という形をしています。

ここまでのコードでは、関数を参照するところは、
function_ref命令を使っていました。
この命令は、引数として@から始まる関数名だけを用いて、関数を取得していました。

しかしここでは、witness_method命令を使っています。
これは、
Hogeableという型名、
#Hogeable.hoge!1というメソッド名、
メソッドを呼び出すオブジェクト(%2)の3つの引数を用いて関数を取得しています。

この部分にて、
先ほど見たwitnessテーブルのエントリが取り出され、
Hogeableとして扱われている実際の型に応じた関数が呼び出される、
という動的ディスパッチが行われている事がわかります。

動作のまとめ

ここまでの結果をまとめると、HogeCatがHogeableとしてアップキャストされ、
そのhogeメソッドが呼ばれる過程は次のようになります。
(callHogeableHogeを介す部分を省略します。)

  1. Hogeable型のオブジェクトを作る。
  2. これをHogeCat用に初期化し、HogeCatの値をコピーする。
  3. 作ったHogeableのポインタを、アップキャストされた値として扱う。
  4. Hogeableのポインタから、その値用のwitnessテーブルを参照し、 メソッドとなる関数を呼び出して呼び出す。
  5. witnessテーブルに登録されていた関数は、 witnessテーブル用のグルーコードになっている。 引数で渡されたアドレスはHogeCatのポインタとなっている。 これを用いて、HogeCatのメソッド本体を呼び出す。
  6. HogeCatのメソッド本体が呼び出される。

これでなぜ、structがプロトコルとして扱え、
メソッド呼び出しが動的ディスパッチできるかわかりました。

最適化について

なお、上記の結果は結構ややこしい過程を経ていますが、
実際にはコンパイラによってここから最適化がかかります。

下記のコマンドで、最適化ありのcanonical SILコードを見てみます。

swiftc -emit-sil -O 1.swift > 1-canosil-o.sil

下記が出力です。

// main.HogeCat.hoge (main.HogeCat)() -> Swift.Int
sil hidden @_TFV4main7HogeCat4hogefS0_FT_Si : $@convention(method) (HogeCat) -> Int {
bb0(%0 : $HogeCat):
  %1 = integer_literal $Builtin.Int64, 1111       // user: %2
  %2 = struct $Int (%1 : $Builtin.Int64)          // user: %3
  return %2 : $Int                                // id: %3
}

// protocol witness for main.Hogeable.hoge <A where A: main.Hogeable> (A)() -> Swift.Int in conformance main.HogeCat : main.Hogeable in main
sil hidden [transparent] [thunk] @_TTWV4main7HogeCatS_8HogeableS_FS1_4hogeuRq_S1__fq_FT_Si : $@convention(witness_method) (@in_guaranteed HogeCat) -> Int {
bb0(%0 : $*HogeCat):
  %1 = integer_literal $Builtin.Int64, 1111       // user: %2
  %2 = struct $Int (%1 : $Builtin.Int64)          // user: %3
  return %2 : $Int                                // id: %3
}

// main.callHogeableHoge (main.Hogeable) -> Swift.Int
sil hidden @_TF4main16callHogeableHogeFPS_8Hogeable_Si : $@convention(thin) (@in Hogeable) -> Int {
bb0(%0 : $*Hogeable):
  debug_value_addr %0 : $*Hogeable  // let hogeable // id: %1
  %2 = open_existential_addr %0 : $*Hogeable to $*@opened("3CD6449A-E6AE-11E5-A7DB-A8667F09828A") Hogeable // users: %3, %4
  %3 = witness_method $@opened("3CD6449A-E6AE-11E5-A7DB-A8667F09828A") Hogeable, #Hogeable.hoge!1, %2 : $*@opened("3CD6449A-E6AE-11E5-A7DB-A8667F09828A") Hogeable : $@convention(witness_method) <τ_0_0 where τ_0_0 : Hogeable> (@in_guaranteed τ_0_0) -> Int // user: %4
  %4 = apply %3<@opened("3CD6449A-E6AE-11E5-A7DB-A8667F09828A") Hogeable>(%2) : $@convention(witness_method) <τ_0_0 where τ_0_0 : Hogeable> (@in_guaranteed τ_0_0) -> Int // user: %6
  destroy_addr %0 : $*Hogeable                    // id: %5
  return %4 : $Int                                // id: %6
}

プロトコルのメソッドを呼び出す部分が、
witness_method命令を使用しているのは変わりませんが、
HogeCatのhogeメソッドの実体@_TFV4main7HogeCat4hogefS0_FT_Siと、
HogeCatのwitnessメソッド@_TTWV4main7HogeCatS_8HogeableS_FS1_4hogeuRq_S1__fq_FT_Siが、
それぞれインライン展開され、同じ内容になっています。
witnessメソッドはもはやグルーコードではなく、独自に実装を持っています。

プロトコルによる動的ディスパッチの実装 (LLVM IR)

しかし、witnessテーブルとかwitness_method命令とか、
ここらへんの挙動は謎のままです。
そこで、SILからさらにコンパイルを進めて、LLVM IRを見てみます。

LLVM IRについて

LLVM IRは、コンパイラ基盤LLVMで使われている中間言語です。
この言語は、Swiftとは独立したもので、
clangでC++などをコンパイルする際も、LLVM IRが経由されます。

Swiftとは独立しているので、
型システムはSwiftと関係なく、
witnessテーブルといった概念もなく、
それらのメモリ上での表現が直接コードされます。

アセンブリに近いような言語仕様ですが、
処理系に近いプリミティブ型、構造体、ポインタなどの型修飾、関数定義、
といった機能があるので、
生のアセンブリよりもだいぶ構造化されています。

C言語とアセンブリの間ぐらいにあるような言語です。

LLVM IRを読むときは、この資料を参照すると良いです。

ここでは、callCatHoge, callHogeableHogeの実装と、
witnessテーブルまわりの実装を見ていきます。

LLVM IRを得るには次のようにします。
ここでも最適化を切っておきます。

swiftc -emit-ir -Onone 1.swift > 1-ir.ll

ただ、ちょっと最適化が効いてしまって説明に都合がわるかったので、
swiftコードをちょっと修正します。

struct HogeCat: Hogeable {
    var a: Int = 1111
    func hoge() -> Int { return a }
}

HogeCatはフィールドaの値を返すようにしておきます。

LLVM IRを読む

生成されたコードはSILのようにコメントがあまり無く、
行数も多いのですが、SILで生成された関数名と同じ名前で関数が定義されるので、
それらを起点に辿ることができます。

まずは、HogeCatの実体を見てみましょう。
SILではwitnessメソッドはHogeCatのポインタを取るようになっていました。
その関数は@_TTWV4main7HogeCatS_8HogeableS_FS1_4hogeuRq_S1__fq_FT_Siでした。
IRで同じ名前を見つけることができます。

define hidden i64 @_TTWV4main7HogeCatS_8HogeableS_FS1_4hogeuRq_S1__fq_FT_Si(%V4main7HogeCat* noalias nocapture dereferenceable(8), %swift.type* %Self) #0 {
entry:
  %.a = getelementptr inbounds %V4main7HogeCat* %0, i32 0, i32 0
  %.a.value = getelementptr inbounds %Si* %.a, i32 0, i32 0
  %1 = load i64* %.a.value, align 8
  %2 = call i64 @_TFV4main7HogeCat4hogefS0_FT_Si(i64 %1) #3
  ret i64 %2
}

第1引数が型%V4main7HogeCatへのポインタ、第2引数が%swift.typeへのポインタとなっています。
元のSILの関数とくらべて、第2引数が増えていますね。

さて、この第1引数の型の定義を探すと下記が見つかります。

%Si = type <{ i64 }>
%V4main7HogeCat = type <{ %Si }>

HogeCatという型が、整数型一つと定義され、
整数型が64bit整数として定義されている事がわかります。

またこの関数の内部で、HogeCatのhogeメソッドの実体、
@_TFV4main7HogeCat4hogefS0_FT_Siが呼び出されています。

引数はi64 %1となっているので、64bit整数一つを渡しています。
HogeCatは2階層の構造体ですが、結局i64フィールド1つしかもたないため、
i64がHogeCatの直接表現として使われています。

witness関数はSILと同様である事が確認できたので、
次にwitness関数を呼び出している部分、callHogeableHogeを見てみます。

define hidden i64 @_TF4main16callHogeableHogeFPS_8Hogeable_Si(%P4main8Hogeable_* noalias nocapture dereferenceable(40)) #0 {
entry:
  %.metadata1 = alloca %swift.type*, align 8
  %1 = getelementptr inbounds %P4main8Hogeable_* %0, i32 0, i32 1
  %.metadata = load %swift.type** %1, align 8
  %2 = getelementptr inbounds %P4main8Hogeable_* %0, i32 0, i32 0
  %3 = bitcast %swift.type* %.metadata to i8***
  %4 = getelementptr inbounds i8*** %3, i64 -1
  %.metadata.valueWitnesses = load i8*** %4, align 8, !invariant.load !12, !dereferenceable !13
  %5 = getelementptr inbounds i8** %.metadata.valueWitnesses, i32 2
  %6 = load i8** %5, align 8, !invariant.load !12
  %projectBuffer = bitcast i8* %6 to %swift.opaque* ([24 x i8]*, %swift.type*)*
  %7 = call %swift.opaque* %projectBuffer([24 x i8]* %2, %swift.type* %.metadata) #2
  %8 = getelementptr inbounds %P4main8Hogeable_* %0, i32 0, i32 2
  %witness-table = load i8*** %8, align 8
  store %swift.type* %.metadata, %swift.type** %.metadata1, align 8
  %9 = load i8** %witness-table, align 8, !invariant.load !12
  %10 = bitcast i8* %9 to i64 (%swift.opaque*, %swift.type*)*
  %11 = call i64 %10(%swift.opaque* noalias nocapture %7, %swift.type* %.metadata)
  %12 = getelementptr inbounds %P4main8Hogeable_* %0, i32 0, i32 1
  %.metadata2 = load %swift.type** %12, align 8
  %13 = getelementptr inbounds %P4main8Hogeable_* %0, i32 0, i32 0
  %14 = bitcast %swift.type* %.metadata2 to i8***
  %15 = getelementptr inbounds i8*** %14, i64 -1
  %.metadata2.valueWitnesses = load i8*** %15, align 8, !invariant.load !12, !dereferenceable !13
  %16 = load i8** %.metadata2.valueWitnesses, align 8, !invariant.load !12
  %destroyBuffer = bitcast i8* %16 to void ([24 x i8]*, %swift.type*)*
  call void %destroyBuffer([24 x i8]* %13, %swift.type* %.metadata2) #2
  ret i64 %11
}

まず引数の型は%P4main8Hogeable_*となっています。
これはSILではHogeableのポインタでした。
定義を見てみます。

%swift.type = type { i64 }
%P4main8Hogeable_ = type { [24 x i8], %swift.type*, i8** }

このように定義されています。
24バイトの領域、型を表す型(%swift.type)へのポインタ、バイト領域へのダブルポインタの3つのフィールドになっています。
ここが見られるのが、SILとIRの違いの一つですね。

スタックに型の型のポインタを確保し、そのアドレスを%.metadata1とします。

  %.metadata1 = alloca %swift.type*, align 8

%P4main8Hogeable_のポインタ%0から、0番目の要素の、第2フィールドのアドレスを%1に代入します。
これはさっき見た定義の通り第2フィールドの型は%swift.type*だったので、
%1の型は%swift.type**となります。
(以降、ポインタのオフセット数や配列の要素数は0番目から、フィールドは1番目から、関数の引数は1番目からと数えます。)

なお、getelementptr命令の詳細はこちらで見れます。

  %1 = getelementptr inbounds %P4main8Hogeable_* %0, i32 0, i32 1

%1の示す先を変数に取り出します。
%.metadataの型は%swift.type*となります。
ようするに、Hogeableの第2フィールドを取り出したことになります。

  %.metadata = load %swift.type** %1, align 8

今度は%0から0番目のフィールドのアドレスを取ります。%2: [24 x i8]*です。

  %2 = getelementptr inbounds %P4main8Hogeable_* %0, i32 0, i32 0

%swift.type*型の%.metadataをi8***にキャストして%3に入れます。
そして、%3の-1番目の要素のアドレスを%4に入れます。
つまり%swift.type*が指し示すメモリ領域、つまり%swift.typeの領域の、ポインタ1つ分手前のメモリ領域には、
i8**が入っているということでしょう。

  %3 = bitcast %swift.type* %.metadata to i8***
  %4 = getelementptr inbounds i8*** %3, i64 -1

%.metadata.valueWitnessesとして、%4が指す値がロードされます。型はi8**ですね。

  %.metadata.valueWitnesses = load i8*** %4, align 8, !invariant.load !12, !dereferenceable !13

%.metadata.valueWitnessesが示すポインタの2つめの要素のポインタを取り、
その値を%6にロードします。%6の型はi8*ですね。

  %5 = getelementptr inbounds i8** %.metadata.valueWitnesses, i32 2
  %6 = load i8** %5, align 8, !invariant.load !12

このポインタを、
[24 x i8]*を第1引数,
%swift.type*を第2引数,
返り値の型が%swift.opaqueへのポインタである関数ポインタとしてキャストし、%projectBufferとします。
2つの引数は、Hogeableの第1, 2番目のフィールドと同じ型ですね。

そしてその関数ポインタを呼び出します。
第1引数が%2、第2引数が%.metadataですので、
結局のところ%0のHogeableの第1, 第2フィールドを渡して呼び出しています。
その結果が%7に保持されます。

  %projectBuffer = bitcast i8* %6 to %swift.opaque* ([24 x i8]*, %swift.type*)*
  %7 = call %swift.opaque* %projectBuffer([24 x i8]* %2, %swift.type* %.metadata) #2

%0の第3フィールドのアドレスを%8に入れます。i8***ですね。

  %8 = getelementptr inbounds %P4main8Hogeable_* %0, i32 0, i32 2

%8の参照先を%witness-tableとして代入します。
ついにwitnessテーブルがi8**型の値として登場しました。
Hogeableの第3フィールドはwitnessテーブルだった事がわかります。

  %witness-table = load i8*** %8, align 8

%.metadataの中身を%.metadata1が示す領域にコピーします。
この領域の型はスタックに確保した%swift.type*でした。

  store %swift.type* %.metadata, %swift.type** %.metadata1, align 8

%witness-tableの示す値を%9にコピーします。%9はi8*です。
つまりこれは、i8**をポインタの配列と考えた時に、第0要素のポインタを取り出しています。

  %9 = load i8** %witness-table, align 8, !invariant.load !12

%9を、第1引数%swift.opaque*、第2引数%swift.type*、返り値i64の関数ポインタにキャストして%10に入れます。

  %10 = bitcast i8* %9 to i64 (%swift.opaque*, %swift.type*)*

%10に、%7と%.metadataを与えて呼び出します。
%7は%projectBuffer関数の返り値でした。%.metadataは%0の返り値です。

  %11 = call i64 %10(%swift.opaque* noalias nocapture %7, %swift.type* %.metadata)

さてここで、%11に結果を入れていますが、最後のところでこれをreturnしています。

  ret i64 %11

ということは、%11を返したcall命令がwitnessメソッドの呼び出しです。
なのでこの間のコードは無視します。

さて、必要な部分を見終わったので整理します。

%0はHogeable*でした。

Hogeableは3つのフィールドを持っていて、
第1フィールドが謎の24バイト、
第2フィールドが型情報(metadata)へのポインタ、
第3フィールドがwitnessテーブルへのポインタでした。

型情報のすぐ上には、valueWitnessesというi8**がありました。
つまり、ポインタの配列です。
この配列の2番目の要素(インデックス2)の要素を関数ポインタ%projectBufferとして取り出しました。

%projectBufferに、
第1フィールドの謎の24バイトを指すポインタと、
第2フィールドの型情報へのポインタを与えると返ってくるのが、
HogeCatへのポインタ(%7)です。

第3フィールドがwitnessテーブルで、ポインタの配列です。
この配列の0番目の要素が、HogeCatのhogeのwitness関数です。

このwitness関数に、%projectBufferにより取り出したHogeCatへのポインタと、
第2フィールドの型情報を渡して呼び出すのが、
witness関数の呼び出しの流れです。

図にするとこのような感じです。

witness-table.jpeg

次はさらに、Hogeableの値領域が実際にどのようなメモリになっているのかを、
IRから確認してみます。

SILでは、callCatHogeの内部でHogeCatからHogeableへのアップキャストがされるときに、
Hogeableの実体をスタックメモリに作っていました。
なのでcallCatHogeを見ればHogeableの構築部分があるはずです。

define hidden i64 @_TF4main11callCatHogeFVS_7HogeCatSi(i64) #0 {
entry:
  %1 = alloca %P4main8Hogeable_, align 8
  %2 = getelementptr inbounds %P4main8Hogeable_* %1, i32 0, i32 1
  store %swift.type* bitcast (i64* getelementptr inbounds ({ i8**, i64, { i64, i8*, i32, i32, i8*, %swift.type** (%swift.type*)*, %swift.type_pattern*, i32, i32, i32 }*, %swift.type*, i64 }* @_TMfV4main7HogeCat, i32 0, i32 1) to %swift.type*), %swift.type** %2, align 8
  %3 = getelementptr inbounds %P4main8Hogeable_* %1, i32 0, i32 2
  store i8** getelementptr inbounds ([1 x i8*]* @_TWPV4main7HogeCatS_8HogeableS_, i32 0, i32 0), i8*** %3, align 8
  %4 = getelementptr inbounds %P4main8Hogeable_* %1, i32 0, i32 0
  %object = bitcast [24 x i8]* %4 to %V4main7HogeCat*
  %object.a = getelementptr inbounds %V4main7HogeCat* %object, i32 0, i32 0
  %object.a.value = getelementptr inbounds %Si* %object.a, i32 0, i32 0
  store i64 %0, i64* %object.a.value, align 8
  %5 = call i64 @_TF4main16callHogeableHogeFPS_8Hogeable_Si(%P4main8Hogeable_* noalias nocapture dereferenceable(40) %1)
  ret i64 %5
}

IRでも、はじめにallocaでスタック上にHogeableを確保し、そのアドレスを%1に入れています。
その後、%2に第2フィールド、%3に第3フィールド、%4に第1フィールドのアドレスを入れています。

swift.type*である%2の第2フィールドへは、下記のように値を書き込んでいます。

  store %swift.type* bitcast (
    i64* getelementptr inbounds (
        {
             i8**, 
             i64, 
             {
                i64, i8*, i32, i32, i8*, 
                %swift.type** (%swift.type*)*, 
                %swift.type_pattern*, 
                i32, i32, i32 
             }*,
             %swift.type*,
             i64 
        }* @_TMfV4main7HogeCat,
        i32 0, 
        i32 1
    ) to %swift.type*
  ),
  %swift.type** %2,
  align 8

これは、5つのフィールドを持つ構造体へのポインタである@_TMfV4main7HogeCatの0番オフセットの、
第2フィールドのアドレスを取るので、このi64となっているフィールドのアドレスを取り、
それを%swift.type*としてキャストしています。
つまりこの%swift.typeはi64だったので、綺麗ですね。

コード中を探すと、@_TMfV4main7HogeCatの定義があります。

@_TMfV4main7HogeCat = internal constant { 
    i8**, 
    i64, 
    { 
        i64, i8*, i32, i32, i8*, 
        %swift.type** (%swift.type*)*, 
        %swift.type_pattern*, 
        i32, i32, i32 
    }*, 
    %swift.type*, 
    i64 
} 
{ 
    i8** getelementptr inbounds (
        [20 x i8*]* @_TWVV4main7HogeCat, i32 0, i32 0
    ), 
    i64 1, 
    { 
        i64, i8*, i32, i32, i8*, 
        %swift.type** (%swift.type*)*,
        %swift.type_pattern*, 
        i32, i32, i32 
    }* @_TMnV4main7HogeCat, 
    %swift.type* null, 
    i64 0 
}

スタティックに初期化される値だとわかります。
第1フィールドのi8**は、
要素20個のポインタの配列へのポインタ、@_TWVV4main7HogeCatを、
ポインタ0オフセットの配列第0要素のアドレスを取ることで、
つまりi8**としてキャストしていますね。
第2フィールドの%swift.typeであるi64は1になっています。
第3フィールドの構造体ポインタには、@_TMnV4main7HogeCatが入っています。
第4はnull, 第5は0です。

戻って考えると、
スタティック定数@_TMfV4main7HogeCatの第2フィールドのアドレスを、
Hogeableの第2フィールドに入れていたのでした。

次に、Hogeableのwitnessテーブルである第3フィールドへの書き込みです。

  store i8** getelementptr inbounds (
    [1 x i8*]* @_TWPV4main7HogeCatS_8HogeableS_,
    i32 0, 
    i32 0
  ), 
  i8*** %3, 
  align 8

このように、要素が1つのポインタ配列へのポインタ@_TWPV4main7HogeCatS_8HogeableS_を、
先程と同様0, 0へのアドレスを取ることでi8**へとキャストします。

@_TWPV4main7HogeCatS_8HogeableS_の定義を見てみます。

@_TWPV4main7HogeCatS_8HogeableS_ = 
hidden constant [1 x i8*] 
[
    i8* bitcast (
        i64 (
            %V4main7HogeCat*, 
            %swift.type*
        )* @_TTWV4main7HogeCatS_8HogeableS_FS1_4hogeuRq_S1__fq_FT_Si 
        to i8*
    )
],
align 8

これはまさにwitnessテーブルですね。
一つ入っているエントリの@_TTWV4main7HogeCatS_8HogeableS_FS1_4hogeuRq_S1__fq_FT_Siは、
SILのwitnessテーブル定義に書いてあったものと同じで、
第1引数がHogeCat*、第2引数が%swift.type*です。

最後に、謎の24バイトの第1フィールド%4の初期化を見ます。

  %object = bitcast [24 x i8]* %4 to %V4main7HogeCat*
  %object.a = getelementptr inbounds %V4main7HogeCat* %object, i32 0, i32 0
  %object.a.value = getelementptr inbounds %Si* %object.a, i32 0, i32 0
  store i64 %0, i64* %object.a.value, align 8

まず、その24バイトの領域へのポインタを、HogeCatへのポインタと見なして%objectとしています。
その第1フィールドaのアドレスを%objectから取り出し%object.aとし、
さらにその第1フィールドvalueのアドレスを%object.aから取り出し%object.a.valueとしています。
そして最後にその領域を%0の指す値、つまりHogeCat全体で埋めています。
今メモリレイアウトとしては、HogeCatとHogeCat.a.valueが完全に重なっているからです。

つまり、Hogeableの第1フィールドの24バイトの先頭8バイトに、
HogeCatの値24バイトが直接埋め込まれているのです。

また、このHogeCatの3重のフィールド構造ですが、Swiftソースの下記に対応しています。

struct HogeCat: Hogeable {
    var a: Int
}
struct Int : SignedIntegerType, Comparable, Equatable {
    var value: Builtin.Int64
}

ちなみに、24バイトを超えるstructを作ってみたら、
mallocによるヒープ確保になり、Hogeableの先頭8バイトにそのポインタが入るように代わりました。

struct HogeDog: Hogeable {
    var a: Int = 2222
    var b: Int = 3333
    var c: Int = 4444
    var d: Int = 5555
    func hoge() -> Int { return a + b + c + d }
}
func callDogHoge(dog: HogeDog) -> Int {
    return callHogeableHoge(dog)
}

下記がコンパイル後です。
%10で24バイト領域をポインタの配列にキャストし、
その次のstoreでその配列の第0要素に%9を書き込みます。
%9は@swift_slowAllocの返り値のポインタです。

define hidden i64 @_TF4main11callDogHogeFVS_7HogeDogSi(%V4main7HogeDog* noalias nocapture dereferenceable(32)) #0 {
entry:
  %1 = alloca %P4main8Hogeable_, align 8
  %.a = getelementptr inbounds %V4main7HogeDog* %0, i32 0, i32 0
  %.a.value = getelementptr inbounds %Si* %.a, i32 0, i32 0
  %2 = load i64* %.a.value, align 8
  %.b = getelementptr inbounds %V4main7HogeDog* %0, i32 0, i32 1
  %.b.value = getelementptr inbounds %Si* %.b, i32 0, i32 0
  %3 = load i64* %.b.value, align 8
  %.c = getelementptr inbounds %V4main7HogeDog* %0, i32 0, i32 2
  %.c.value = getelementptr inbounds %Si* %.c, i32 0, i32 0
  %4 = load i64* %.c.value, align 8
  %.d = getelementptr inbounds %V4main7HogeDog* %0, i32 0, i32 3
  %.d.value = getelementptr inbounds %Si* %.d, i32 0, i32 0
  %5 = load i64* %.d.value, align 8
  %6 = getelementptr inbounds %P4main8Hogeable_* %1, i32 0, i32 1
  store %swift.type* bitcast (i64* getelementptr inbounds ({ i8**, i64, { i64, i8*, i32, i32, i8*, %swift.type** (%swift.type*)*, %swift.type_pattern*, i32, i32, i32 }*, %swift.type*, i64, i64, i64, i64 }* @_TMfV4main7HogeDog, i32 0, i32 1) to %swift.type*), %swift.type** %6, align 8
  %7 = getelementptr inbounds %P4main8Hogeable_* %1, i32 0, i32 2
  store i8** getelementptr inbounds ([1 x i8*]* @_TWPV4main7HogeDogS_8HogeableS_, i32 0, i32 0), i8*** %7, align 8
  %8 = getelementptr inbounds %P4main8Hogeable_* %1, i32 0, i32 0
  %9 = call noalias i8* @swift_slowAlloc(i64 32, i64 7) #4
  %10 = bitcast [24 x i8]* %8 to i8**
  store i8* %9, i8** %10, align 8
  %11 = bitcast i8* %9 to %V4main7HogeDog*
  %.a1 = getelementptr inbounds %V4main7HogeDog* %11, i32 0, i32 0
  %.a1.value = getelementptr inbounds %Si* %.a1, i32 0, i32 0
  store i64 %2, i64* %.a1.value, align 8
  %.b2 = getelementptr inbounds %V4main7HogeDog* %11, i32 0, i32 1
  %.b2.value = getelementptr inbounds %Si* %.b2, i32 0, i32 0
  store i64 %3, i64* %.b2.value, align 8
  %.c3 = getelementptr inbounds %V4main7HogeDog* %11, i32 0, i32 2
  %.c3.value = getelementptr inbounds %Si* %.c3, i32 0, i32 0
  store i64 %4, i64* %.c3.value, align 8
  %.d4 = getelementptr inbounds %V4main7HogeDog* %11, i32 0, i32 3
  %.d4.value = getelementptr inbounds %Si* %.d4, i32 0, i32 0
  store i64 %5, i64* %.d4.value, align 8
  %12 = call i64 @_TF4main16callHogeableHogeFPS_8Hogeable_Si(%P4main8Hogeable_* noalias nocapture dereferenceable(40) %1)
  ret i64 %12
}

さて、これでcallCatHogeの中で作ったHogeableのフィールド3つが埋まりました。
最後はそのHogeableのポインタをcallHogeableHogeに渡すだけです。

  %5 = call i64 @_TF4main16callHogeableHogeFPS_8Hogeable_Si(%P4main8Hogeable_* noalias nocapture dereferenceable(40) %1)
  ret i64 %5

これで、Hogeableへの値HogeCatの埋め込み、
metadata、witnessテーブルが確認できました。

もう1つここまでで出てきたものとして、%swift.typeの1つ前から、
valueWitnessテーブルが辿れるというものがありました。

これを確認してみます。

metadataが指しているのは、次の構造体のi64型の第2フィールドのアドレスです。

@_TMfV4main7HogeCat = internal constant { 
    i8**, 
    i64, 
    { 
        i64, i8*, i32, i32, i8*, 
        %swift.type** (%swift.type*)*, 
        %swift.type_pattern*, 
        i32, i32, i32 
    }*, 
    %swift.type*, 
    i64 
} 
{ 
    i8** getelementptr inbounds (
        [20 x i8*]* @_TWVV4main7HogeCat, i32 0, i32 0
    ), 
    i64 1, 
    { 
        i64, i8*, i32, i32, i8*, 
        %swift.type** (%swift.type*)*,
        %swift.type_pattern*, 
        i32, i32, i32 
    }* @_TMnV4main7HogeCat, 
    %swift.type* null, 
    i64 0 
}

先ほども見たとおり、そのi64の前にはi8**にキャストされた@_TWVV4main7HogeCatがあります。
これがHogeCatのvalueWitnessテーブルという事がわかります。

valueWitnessテーブルの第2要素の関数を使って、
Hogeable*からHogeCat*を取り出すのでした。
これを追いかけてみましょう。

@_TWVV4main7HogeCat = constant [20 x i8*] 
[
    i8* bitcast (void (i8*, %swift.type*)* @__swift_noop_void_return to i8*), 
    i8* bitcast (i8* (i8*, i8*, %swift.type*)* @__swift_memcpy8_8 to i8*), 
    i8* bitcast (i8* (i8*, %swift.type*)* @__swift_noop_self_return to i8*), 
    i8* bitcast (void (i8*, %swift.type*)* @__swift_noop_void_return to i8*), 
    i8* bitcast (void (i8*, %swift.type*)* @__swift_noop_void_return to i8*), 
    i8* bitcast (i8* (i8*, i8*, %swift.type*)* @__swift_memcpy8_8 to i8*), 
    i8* bitcast (i8* (i8*, i8*, %swift.type*)* @__swift_memcpy8_8 to i8*), 
    i8* bitcast (i8* (i8*, i8*, %swift.type*)* @__swift_memcpy8_8 to i8*), 
    i8* bitcast (i8* (i8*, i8*, %swift.type*)* @__swift_memcpy8_8 to i8*), 
    i8* bitcast (i8* (i8*, i8*, %swift.type*)* @__swift_memcpy8_8 to i8*), 
    i8* bitcast (i8* (i8*, i8*, %swift.type*)* @__swift_memcpy8_8 to i8*), 
    i8* bitcast (i8* (i8*, %swift.type*)* @__swift_noop_self_return to i8*), 
    i8* bitcast (i8* (i8*, i8*, %swift.type*)* @__swift_memcpy8_8 to i8*), 
    i8* bitcast (void (i8*, %swift.type*)* @__swift_noop_void_return to i8*), 
    i8* bitcast (i8* (i8*, i8*, i64, %swift.type*)* @__swift_memcpy_array8_8 to i8*), 
    i8* bitcast (i8* (i8*, i8*, i64, %swift.type*)* @__swift_memmove_array8_8 to i8*), 
    i8* bitcast (i8* (i8*, i8*, i64, %swift.type*)* @__swift_memmove_array8_8 to i8*), 
    i8* inttoptr (i64 8 to i8*), i8* inttoptr (i64 7 to i8*), i8* inttoptr (i64 8 to i8*)
]

たしかに第2要素が、i8*と%swift.type*を受け取る型の関数、@__swift_noop_self_returnになっています。

これも定義されています。

; Function Attrs: nounwind
define linkonce_odr hidden i8* @__swift_noop_self_return(i8*, %swift.type*) #2 {
entry:
  ret i8* %0
}

ちゃんと第1引数%0をそのままreturnする関数になっています。
HogeCatはHogeableの先頭24バイトの最初の8バイトに埋め込まれているので、
これでちゃんとHogeCat*が返るわけです。

これで、HogeCatをHogeableにアップキャストして呼び出す時、
どのようなメモリレイアウトと関数テーブルの参照が構築されるかがわかりました。
そして、SILで見た場合よりも具体的にわかりました。

ジェネリックなプロトコルの場合

ここまでの調査で、ジェネリックでないプロトコルとして、structをどうやってアップキャストしているかがわかりました。
そしてHogeableは関数を呼び出す前に生成されており、
これをフィールドとして使った場合は、このHogeable型が使われるのだろうとわかります。

では下記のようなジェネリックな関数callIntFugableFugaを呼び出すときは何が起きているのでしょうか。

func callIntFugableFuga<F: Fugable where F.Element == Int>(fugable: F) -> Int {
    return fugable.fuga()
}

callHogeableHogeの時は、Hogeable型の値を作ってからcallHogeableHogeにそのアドレスを渡していました。

同様に考えれば、callIntFugableFugaの引数として渡すための、
Element型パラメータがIntに束縛されている時のFugable型の値が作られ、
そのアドレスがcallIntFugableFugaに渡されるようになっているはずです。

ということは、Intに特殊化されたFugableの値型というものが存在することになり、
なぜプロパティに保持できないのか、という疑問が生まれます。

SILを見る

早速見ていきましょう。
元となるSwiftソースは下記になります。

protocol Fugable {
    typealias Element
    func fuga() -> Element
}
struct FugaDog: Fugable {
    var aaa: Int = 3333
    @inline(never) func fuga() -> Int {
        return aaa
    }
}
@inline(never) func callIntFugableFuga<F: Fugable where F.Element == Int>(fugable: F) -> Int {
    return fugable.fuga()
}
func callDogFuga(dog: FugaDog) -> Int {
    return callIntFugableFuga(dog)
}

print(callDogFuga(FugaDog()))

@inline(never)は後の説明の都合でついています。

さてこれをsilgenして、callDogFugaの部分を見てみます。

// main.callDogFuga (main.FugaDog) -> Swift.Int
sil hidden @_TF4main11callDogFugaFVS_7FugaDogSi : $@convention(thin) (FugaDog) -> Int {
bb0(%0 : $FugaDog):
  debug_value %0 : $FugaDog  // let dog           // id: %1
  // function_ref main.callIntFugableFuga <A where A: main.Fugable, A.Element == Swift.Int> (A) -> Swift.Int
  %2 = function_ref @_TF4main18callIntFugableFugauRq_S_7Fugablezqq_S0_7ElementSi_Fq_Si : $@convention(thin) <τ_0_0 where τ_0_0 : Fugable, τ_0_0.Element == Int> (@in τ_0_0) -> Int // user: %5
  %3 = alloc_stack $FugaDog                       // users: %4, %5, %6
  store %0 to %3#1 : $*FugaDog                    // id: %4
  %5 = apply %2<FugaDog>(%3#1) : $@convention(thin) <τ_0_0 where τ_0_0 : Fugable, τ_0_0.Element == Int> (@in τ_0_0) -> Int // user: %7
  dealloc_stack %3#0 : $*@local_storage FugaDog   // id: %6
  return %5 : $Int                                // id: %7
}

これにはちょっと驚きました。
function_ref命令で取り出した関数は、
型パラメータを含むジェネリックな型定義になっています。
そして、apply命令には、
その型パラメータを埋める<FugaDog>が書いてあります。

呼び出し先のcallIntFugableの定義も見てみましょう。

// main.callIntFugableFuga <A where A: main.Fugable, A.Element == Swift.Int> (A) -> Swift.Int
sil hidden [noinline] @_TF4main18callIntFugableFugauRq_S_7Fugablezqq_S0_7ElementSi_Fq_Si : $@convention(thin) <F where F : Fugable, F.Element == Int> (@in F) -> Int {
bb0(%0 : $*F):
  debug_value_addr %0 : $*F  // let fugable       // id: %1
  %2 = witness_method $F, #Fugable.fuga!1 : $@convention(witness_method) <τ_0_0 where τ_0_0 : Fugable> (@out τ_0_0.Element, @in_guaranteed τ_0_0) -> () // user: %4
  %3 = alloc_stack $Int                           // users: %4, %5, %6
  %4 = apply %2<F, Int>(%3#1, %0) : $@convention(witness_method) <τ_0_0 where τ_0_0 : Fugable> (@out τ_0_0.Element, @in_guaranteed τ_0_0) -> ()
  %5 = load %3#1 : $*Int                          // user: %8
  dealloc_stack %3#0 : $*@local_storage Int       // id: %6
  destroy_addr %0 : $*F                           // id: %7
  return %5 : $Int                                // id: %8
}

型パラメータ名Fが残ったジェネリック関数になっている事がわかります。
そして、Intに特殊化されたFugableのような型は出てきませんでした。
呼び出し側でapplyに渡しているのはFugaDogのポインタそのままです。

つまり、1つの答えとしては次のようになります。
SILのレベルでジェネリックプロトコルを保持する型が存在しないため、
そのようなプロパティは作ることができない。
一方ジェネリック関数に制約を与えた型を渡すことができるのは、
型パラメータの制約をSILのレベルで表現できるから。
という事です。

しかし、SILのレベルではそうであったとしても、
LLVM IRのレベルではそのような言語機能はありません。
実行できるということは、ジェネリックなFugableとしてポリモーフィズムするコードが、
生成されているはずです。

それを見ていきましょう。

LLVM IRを見る

呼び出し側は次のようになっています。

define hidden i64 @_TF4main11callDogFugaFVS_7FugaDogSi(i64) #0 {
entry:
  %1 = alloca %V4main7FugaDog, align 8
  %.aaa = getelementptr inbounds %V4main7FugaDog* %1, i32 0, i32 0
  %.aaa.value = getelementptr inbounds %Si* %.aaa, i32 0, i32 0
  store i64 %0, i64* %.aaa.value, align 8
  %2 = bitcast %V4main7FugaDog* %1 to %swift.opaque*
  %3 = call i64 @_TF4main18callIntFugableFugauRq_S_7Fugablezqq_S0_7ElementSi_Fq_Si(%swift.opaque* noalias nocapture %2, %swift.type* bitcast (i64* getelementptr inbounds ({ i8**, i64, { i64, i8*, i32, i32, i8*, %swift.type** (%swift.type*)*, %swift.type_pattern*, i32, i32, i32 }*, %swift.type*, i64 }* @_TMfV4main7FugaDog, i32 0, i32 1) to %swift.type*), i8** getelementptr inbounds ([2 x i8*]* @_TWPV4main7FugaDogS_7FugableS_, i32 0, i32 0))
  ret i64 %3
}

スタックにFugaDogを作り%1でアドレスを持ち、
引数%0のFugaDogをコピーして初期化しています。
%1のFugaDog*を%swift.opaque*にキャストして%2としています。
callで呼び出しているのはSILでジェネリックだったcallIntFugableFugaです。

  %3 = call i64 @_TF4main18callIntFugableFugauRq_S_7Fugablezqq_S0_7ElementSi_Fq_Si(
    %swift.opaque* noalias nocapture %2, 
    %swift.type* bitcast (
        i64* getelementptr inbounds (
            {
                i8**,
                i64, 
                {
                    i64, i8*, i32, i32, i8*, 
                    %swift.type** (%swift.type*)*, 
                    %swift.type_pattern*,
                    i32, i32, i32 
                }*, 
                %swift.type*, 
                i64 
            }* @_TMfV4main7FugaDog, 
            i32 0, 
            i32 1
        ) 
        to %swift.type*
    ), 
    i8** getelementptr inbounds (
        [2 x i8*]* @_TWPV4main7FugaDogS_7FugableS_,
        i32 0, 
        i32 0
    )
  )

callHogeableHogeの時はHogeable*だけが引数だったのに対し、
呼び出し引数が3つに増えています。

第1引数は%2の%swift.opaque*です。これは実際にはFugaDog*のキャストです。

第2引数は先程はHogeableの第2フィールドとして出てきた%swift.type*を、
同じようにstatic定数@_TMfV4main7FugaDogのi64のアドレスにしています。
その1つ前にはvalueWitnessTableがあるやつです。

第3引数もHogeableの第3フィールドのwitnessテーブルの初期化と同じやり方で、
@_TWPV4main7FugaDogS_7FugableS_のwitnessテーブルを渡しています。

全体として、さっきのHogeableをフィールドごとにバラして引数にしたような形ですね。

なお、witnessテーブルのエントリ数が1から2に変わっています。

@_TWPV4main7FugaDogS_7FugableS_ = hidden constant [2 x i8*] 
[
    i8* null, 
    i8* bitcast (
        void (%Si*, %V4main7FugaDog*, %swift.type*)* 
        @_TTWV4main7FugaDogS_7FugableS_FS1_4fugauRq_S1__fq_FT_qq_S1_7Element
        to i8*
    )
], align 8

第0要素がnullになり、第1要素にfugaのwitness関数が入っています。
そして、返り値がIntではなくvoidになり、
第1引数が%Si*とIntをポインタ経由で返すようになっています。
第2引数と第3引数については、Hogeableのwitness関数のときと同じ形です。
ジェネリックな動作にするため、返り値の返し型がポインタ渡しに変化したようですね。

さて、関数本体を見てみましょう。

; Function Attrs: noinline
define hidden i64 @_TF4main18callIntFugableFugauRq_S_7Fugablezqq_S0_7ElementSi_Fq_Si(%swift.opaque* noalias nocapture, %swift.type* %F, i8** %F.Fugable) #1 {
entry:
  %F1 = alloca %swift.type*, align 8
  %1 = alloca %Si, align 8
  store %swift.type* %F, %swift.type** %F1, align 8
  %2 = getelementptr inbounds i8** %F.Fugable, i32 1
  %3 = load i8** %2, align 8, !invariant.load !12
  %4 = bitcast i8* %3 to void (%swift.opaque*, %swift.opaque*, %swift.type*)*
  %5 = bitcast %Si* %1 to %swift.opaque*
  call void %4(%swift.opaque* noalias nocapture sret %5, %swift.opaque* noalias nocapture %0, %swift.type* %F)
  %.value = getelementptr inbounds %Si* %1, i32 0, i32 0
  %6 = load i64* %.value, align 8
  %7 = bitcast %swift.type* %F to i8***
  %8 = getelementptr inbounds i8*** %7, i64 -1
  %F.valueWitnesses = load i8*** %8, align 8, !invariant.load !12, !dereferenceable !13
  %9 = getelementptr inbounds i8** %F.valueWitnesses, i32 4
  %10 = load i8** %9, align 8, !invariant.load !12
  %destroy = bitcast i8* %10 to void (%swift.opaque*, %swift.type*)*
  call void %destroy(%swift.opaque* %0, %swift.type* %F) #2
  ret i64 %6
}

%1が確保され、%.valueで参照し、%6でそれをロードし、retしているので、
%1が関数から返り値を受け取るためのローカル変数です。

第2引数で渡された%F: %swift.type*はローカル変数%F1にコピーされます。

第3引数のwitnessテーブルの第1要素から関数を取り出し、%2,%3,%4と処理して関数ポインタとなります。
%1は%5で%swift.opaque*へキャストされます。

これでwitness関数とその引数3つが揃うので、callで呼び出されます。

結論として、ジェネリック関数の呼び出しでは、
値の型のポインタ、型情報、witnessテーブルの3つをプロトコル型の値の変わりに使うことで、
動的な値を実現しています。
ポインタの型はopaqueポインタとすることで消され、
返り値がジェネリックな場合は値の返却が引数のポインタ経由となり、
これもまたopaqueポインタとなります。

ここまでわかって、逆に疑問が生まれます。

値のポインタ、型情報、witnessテーブルの3つの値があれば、
型パラメータのあるプロトコルの値が取り扱えるという事がわかりました。
SIL上にはそのような機能はありませんでしたが、
LLVM IRでそのように扱えるのだから、
SIL側に対応する仕様が定義されたらそれで動くはずです。

3つの値を並べた値のメモリサイズも固定ですから、
こんな感じでIRの世界でも構造体として定義することができて、
そうしたらもう先ほどのHogeableとほぼ同じです。

%P4main7Fugable_ = type { %swift.opaque*, %swift.type*, i8** }

ということは、技術的な制約ではなく、
設計上の選択であろうと思われます。

SILと最適化

SILの仕様としてジェネリック関数が導入されている事と関連して、
raw SILからcanonical SILへの変換時の最適化として、
ジェネリック関数の特殊化があります。

ここまでの調査では最適化を抑制してきましたが、
ここで最適化ありのcanonical SILの出力を見てみます。

// generic specialization <main.FugaDog with main.FugaDog : main.Fugable in main> of main.callIntFugableFuga <A where A: main.Fugable, A.Element == Swift.Int> (A) -> Swift.Int
sil shared [noinline] @_TTSg5V4main7FugaDogS0_S_7FugableS____TF4main18callIntFugableFugauRq_S_7Fugablezqq_S0_7ElementSi_Fq_Si : $@convention(thin) (@in FugaDog) -> Int {
bb0(%0 : $*FugaDog):
  debug_value_addr %0 : $*FugaDog  // let fugable // id: %1
  %2 = load %0 : $*FugaDog                        // user: %4
  // function_ref main.FugaDog.fuga (main.FugaDog)() -> Swift.Int
  %3 = function_ref @_TFV4main7FugaDog4fugafS0_FT_Si : $@convention(method) (FugaDog) -> Int // user: %4
  %4 = apply %3(%2) : $@convention(method) (FugaDog) -> Int // user: %5
  return %4 : $Int                                // id: %5
}

// main.callIntFugableFuga <A where A: main.Fugable, A.Element == Swift.Int> (A) -> Swift.Int
sil hidden [noinline] @_TF4main18callIntFugableFugauRq_S_7Fugablezqq_S0_7ElementSi_Fq_Si : $@convention(thin) <F where F : Fugable, F.Element == Int> (@in F) -> Int {
bb0(%0 : $*F):
  debug_value_addr %0 : $*F  // let fugable       // id: %1
  %2 = witness_method $F, #Fugable.fuga!1 : $@convention(witness_method) <τ_0_0 where τ_0_0 : Fugable> (@out τ_0_0.Element, @in_guaranteed τ_0_0) -> () // user: %4
  %3 = alloc_stack $Int                           // users: %4, %5, %6
  %4 = apply %2<F, Int>(%3#1, %0) : $@convention(witness_method) <τ_0_0 where τ_0_0 : Fugable> (@out τ_0_0.Element, @in_guaranteed τ_0_0) -> ()
  %5 = load %3#1 : $*Int                          // user: %8
  dealloc_stack %3#0 : $*@local_storage Int       // id: %6
  destroy_addr %0 : $*F                           // id: %7
  return %5 : $Int                                // id: %8
}

なんと、FugaDogに特殊化されたcallIntFugableFugaと、
先ほどと同じジェネリックなcallIntFugableFugaの両方のコードが生成されました。

特殊化版は、その内部で、引数で受けたFugaDog*のfugaを呼び出す時も、
FugaDog.fugaの本体を値型で呼び出せています。

そして嬉しいことに、callDogFugaの中から呼び出されるケースでは、特殊化された版のcallIntFugableFugaが呼ばれています。

// main.callDogFuga (main.FugaDog) -> Swift.Int
sil hidden @_TF4main11callDogFugaFVS_7FugaDogSi : $@convention(thin) (FugaDog) -> Int {
bb0(%0 : $FugaDog):
  debug_value %0 : $FugaDog  // let dog           // id: %1
  %2 = alloc_stack $FugaDog                       // users: %3, %5, %6
  store %0 to %2#1 : $*FugaDog                    // id: %3
  // function_ref generic specialization <main.FugaDog with main.FugaDog : main.Fugable in main> of main.callIntFugableFuga <A where A: main.Fugable, A.Element == Swift.Int> (A) -> Swift.Int
  %4 = function_ref @_TTSg5V4main7FugaDogS0_S_7FugableS____TF4main18callIntFugableFugauRq_S_7Fugablezqq_S0_7ElementSi_Fq_Si : $@convention(thin) (@in FugaDog) -> Int // user: %5
  %5 = apply %4(%2#1) : $@convention(thin) (@in FugaDog) -> Int // user: %7
  dealloc_stack %2#0 : $*@local_storage FugaDog   // id: %6
  return %5 : $Int                                // id: %7
}

callDogFuga -> callIntFugableFuga -> DogFuga.fugaの呼び出しチェーンにおいて、
関数参照は全て静的なfunction_refになっており、
もはやwitnessテーブルの参照はありません。

もちろん、witnessテーブルにはジェネリック版が登録されています。

sil_witness_table hidden FugaDog: Fugable module main {
  associated_type Element: Int
  method #Fugable.fuga!1: @_TTWV4main7FugaDogS_7FugableS_FS1_4fugauRq_S1__fq_FT_qq_S1_7Element  // protocol witness for main.Fugable.fuga <A where A: main.Fugable> (A)() -> A.Element in conformance main.FugaDog : main.Fugable in main
}

そしてここまでinline化を抑制していましたが、これを外すとこうなります。

// main.callDogFuga (main.FugaDog) -> Swift.Int
sil hidden @_TF4main11callDogFugaFVS_7FugaDogSi : $@convention(thin) (FugaDog) -> Int {
bb0(%0 : $FugaDog):
  debug_value %0 : $FugaDog  // let dog           // id: %1
  %2 = struct_extract %0 : $FugaDog, #FugaDog.aaa // user: %3
  return %2 : $Int                                // id: %3
}

callDogFugaの中で、FugaDog型の値から直接フィールドの値を読んで返しています。
callIntFugableFugaと、その先のDogFuga.fugaの両方がインライン化された結果、
このようになりました。

このような最適化ができるのは、ジェネリック関数が制約の形で書かれていて、
呼び出しと対応して実際の型がコンパイル時に確定するからです。

考察

ここまで調べた上での僕の推測は、
ジェネリックなプロトコルのプロパティ(変数)を作れない仕様にしているのは、
もし作った場合には、それにはこの最適化が効かない事を嫌ったからだと思います。

Javaでよく知られたListインターフェースのスタイルがあるので、
おそらくそれができる言語仕様であれば、
とりあえず多くの人がそのようなジェネリックプロトコルで取り回すようになると思われます。

そして例えば、そのようなIntのSequenceなどでプロパティを受け取るクラスがあれば、
そのクラスからそのプロパティを参照して何かする別のクラスもSequenceで扱う、
というように型定義の伝搬が自然と起こり、
アプリケーションのほとんど全体でSequenceによって取り回す事になるでしょう。

一方、それを禁止した仕様にしておけば、
ほとんど全てのケースでプロトコルと型制約で実装された関数群は、
実際のstructの型で特殊化可能になり、
静的ディスパッチとなり、インライン化が可能となります。
そして、遅いジェネリックな動作となるのは、
ユーザーが自らType Erasureをせこせこ実装した場合ということです。

これは前者と比較すると結構なパフォーマンスの違いを生みそうに思います。
特に、ジェネリックな型で代表的なものはやはりコレクションで、
O(n)のオーダーを持つ処理と絡みやすいため、アプリの動作速度におけるウェイトが大きそうです。

Swiftは生成バイナリの動作が速い事も言語設計目標の1つにしています。
C++とJavaの間にこのテーマに関してはそれなりの性能差があるはずです。
C++ではテンプレートクラスはコンパイル時にソースレベルで展開されるため高速に動作します。
一方Javaではジェネリックなインターフェースは、
型パラTの型をもつ部分は全て参照型となり、
値型はBoxingされ、
メソッド呼び出しは常に仮想関数テーブルによる動的ディスパッチになります。
Swiftは動作速度において、C++並の性能がでるようにこのような選択をしたと思われます。

またC++のテンプレートクラスで、
SwiftのSequenceTypeのような事をしようとした場合を考えてみます。
C++のstd::vector<T>は実際の値型を定義するので、SwiftのArray<T>にあたります。
ここでSwiftでは、SequenceTypeというプロトコルを満たす型に対して、
ジェネリック関数の形で再利用可能な部品を実装できます。
C++でも確か同じようにstd::vectorでもstd::listでも渡して使える関数を定義可能ですが、
テンプレート構文を結構深く使いこなす必要があったと思います。
Swiftはそのようなコードがprotocol文だけで簡単に書けるようになっています。

この言語仕様にする問題点は、
元の値の振る舞いを保持したままインターフェースを扱いたい場合で、
かつ、複数のインターフェースを同時に満たすクラスを取り扱う事ができない事です。

1つめの条件を満たすためにType Erasureを作る必要がありますが、
プロトコルAのAnyA, プロトコルBのAnyBはそれぞれ元の値を隠蔽してしまうため、
どちらかに包んだ瞬間にもう片方のインターフェースは失われます。

やろうと思ったら、プロトコルAとプロトコルBの両方を満たしたType ErasureであるAnyAorBを実装する必要がありますが、
この組み合わせ方ごとにErasureの実装が必要なため非現実的です。

しかしなんとなく、そのような複雑な機能をもったオブジェクトを作ったことは、
あまりこれまでに無かったような気がします。

プロトコルはよくわからないコンパイルエラーが出て沼にはまりそうなのが心配で、
どの程度導入するべきか悩ましい状態が続いていたのですが、
今回自分なりにはいろいろクリアになってきたので、
今後はもっとstructとprotocolを活用していきたいと思います。

175
142
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
175
142