Skip to content

Instantly share code, notes, and snippets.

@omochi

omochi/wwswc-ort-impl.md

Created May 24, 2019 10:22
Show Gist options
  • Save omochi/42435836e4ac9a1a4e017414c00f8764 to your computer and use it in GitHub Desktop.
Save omochi/42435836e4ac9a1a4e017414c00f8764 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
wwswc-ort-impl.md

slidenumber: true autoscale: true

Opaque Result Typeの実装

omochimetaru

わいわいswiftc #11

疑問

ORTによる抽象化

後から真の型を変更可能 リコンパイルせずに変更可能

どのように実現するのか？

真の型による特殊化

真の型がわかるときは、その型で特殊化して取り扱う

どのように実現するのか？

答え

抽象化の方法

  • ORTのアイデンティティに対応するOpaque Type Descriptor(OTD)が作られる
  • OTDからはランタイム関数を介してMetatypeとProtocol Witness Tableが取得できる
  • もちろん、MetatypeからはValue Witness Tableが取得できる

特殊化の方法

  • 呼び出し側でポインタをキャストする

実験

protocol P { func print() }
extension Int : P {}

func f() -> some P { return Int(3) }

func callF() {
    let p1 = f() // ORTを返す関数の呼び出し
    let p2 = p1 // ORT型同士のコピー
    p2.print() // プロトコルメソッドの呼び出し
}

callee SIL

// f()
sil hidden @$s1a1fQryF : $@convention(thin) () 
  -> @out @_opaqueReturnTypeOf("$s1a1fQryF", 0) 🦸 {
// %0                                             // user: %1
bb0(%0 : $*@_opaqueReturnTypeOf("$s1a1fQryF", 0) 🦸):
  %1 = unchecked_addr_cast %0 : 
    $*@_opaqueReturnTypeOf("$s1a1fQryF", 0) 🦸 to $*Int // user: %4
  %2 = integer_literal $Builtin.Int64, 3          // user: %3
  %3 = struct $Int (%2 : $Builtin.Int64)          // user: %4
  store %3 to %1 : $*Int                          // id: %4
  %5 = tuple ()                                   // user: %6
  return %5 : $()                                 // id: %6
} // end sil function '$s1a1fQryF'

  • 返り値の型の表現は @_opaqueReturnTypeOf("$s1a1fQryF", 0) 型名に関数名が埋め込まれている

  • @outがついているので、ポインタによる間接返し

  • bb0の引数の型を見てもポインタだとわかる

  • unchecked_addr_castでIntのポインタにキャスト

  • storeでそのポインタに結果を書き込む

🦸

// lib/AST/ASTPrinter.cpp
      Printer << "@_opaqueReturnTypeOf(";
      OpaqueTypeDecl *decl = T->getDecl();
      
      Printer.printEscapedStringLiteral(
            decl->getOpaqueReturnTypeIdentifier().str());
      
      Printer << ", " << T->getInterfaceType()
                          ->castTo<GenericTypeParamType>()
                          ->getIndex();
      
      Printer << u8") \U0001F9B8";
      printGenericArgs(T->getSubstitutions().getReplacementTypes());

謎

caller SIL

// callF()
sil hidden @$s1a5callFyyF : $@convention(thin) () -> () {
bb0:
  %0 = alloc_stack $@_opaqueReturnTypeOf("$s1a1fQryF", 0) 🦸, 
    let, name "p1" // users: %10, %9, %4, %2
  // function_ref f()
  %1 = function_ref @$s1a1fQryF : 
    $@convention(thin) () 
    -> @out @_opaqueReturnTypeOf("$s1a1fQryF", 0) 🦸 // user: %2
  %2 = apply %1(%0) : $@convention(thin) ()
    -> @out @_opaqueReturnTypeOf("$s1a1fQryF", 0) 🦸
  %3 = alloc_stack $@_opaqueReturnTypeOf("$s1a1fQryF", 0) 🦸,
    let, name "p2" // users: %8, %7, %6, %4
  copy_addr %0 to [initialization] %3 :
    $*@_opaqueReturnTypeOf("$s1a1fQryF", 0) 🦸 // id: %4
  %5 = witness_method $@_opaqueReturnTypeOf("$s1a1fQryF", 0) 🦸, #P.print!1 : 
    <Self where Self : P> (Self) -> () -> () : 
    $@convention(witness_method: P) <τ_0_0 where τ_0_0 : P> 
    (@in_guaranteed τ_0_0) -> () // user: %6
  %6 = apply %5<@_opaqueReturnTypeOf("$s1a1fQryF", 0) 🦸>(%3) : 
    $@convention(witness_method: P) <τ_0_0 where τ_0_0 : P> 
    (@in_guaranteed τ_0_0) -> ()
  destroy_addr %3 : $*@_opaqueReturnTypeOf("$s1a1fQryF", 0) 🦸 // id: %7
  dealloc_stack %3 : $*@_opaqueReturnTypeOf("$s1a1fQryF", 0) 🦸 // id: %8
  destroy_addr %0 : $*@_opaqueReturnTypeOf("$s1a1fQryF", 0) 🦸 // id: %9
  dealloc_stack %0 : $*@_opaqueReturnTypeOf("$s1a1fQryF", 0) 🦸 // id: %10
  %11 = tuple ()                                  // user: %12
  return %11 : $()                                // id: %12
} // end sil function '$s1a5callFyyF'

  • $@_opaqueReturnTypeOf("$s1a1fQryF", 0)型 でalloc_stackして、 結果を受け取る変数をスタックに確保 そのアドレスを%0に代入

  • function_ref,applyでfを呼び出す 引数に確保したメモリ領域を渡す

  • 呼び出し後は%0に結果が入っている

  • コピー先変数を同様に作成、 %3でアドレスを保持

  • copy_addrで%0から%3にコピー

  • witness_methodで、 $@_opaqueReturnTypeOf("$s1a1fQryF", 0)型 のP.printメソッドを取得

  • applyで呼び出す

  • destroy_addrで%3の中身を破棄
  • dealloc_stackで%3のメモリを解放
  • destroy_addrで%0の中身を破棄
  • dealloc_stackで%0のメモリを解放

  • 関数名を埋め込んだ型名、 $@_opaqueReturnTypeOf("$s1a1fQryF", 0) で表現

  • calleeは真の型をキャストして書き込み

  • callerは型名以外普通

callee LLVM-IR

define hidden swiftcc void @"$s1a1fQryF"
  (%swift.opaque* noalias nocapture sret) #0 {
entry:
  %1 = bitcast %swift.opaque* %0 to %TSi*
  %._value = getelementptr inbounds %TSi, %TSi* %1, i32 0, i32 0
  store i64 3, i64* %._value, align 1
  ret void
}
  • 型名は消えている
  • 引数でopaqueポインタを受け取る
  • それをIntのポインタにキャスト
  • storeで書き込み

caller LLVM-IR

define hidden swiftcc void @"$s1a5callFyyF"() #0 {
entry:
  %p2.debug = alloca i8*, align 8
  %0 = bitcast i8** %p2.debug to i8*
  call void @llvm.memset.p0i8.i64(i8* align 8 %0, i8 0, i64 8, i1 false)
  %p1.debug = alloca i8*, align 8
  %1 = bitcast i8** %p1.debug to i8*
  call void @llvm.memset.p0i8.i64(i8* align 8 %1, i8 0, i64 8, i1 false)
  %2 = call swiftcc %swift.metadata_response
    @swift_getOpaqueTypeMetadata(
      i64 0, i8* undef, 
      %swift.type_descriptor* bitcast (
        <{ i32, i32, i16, i16, i16, i16, i8, i8, i8, i8, i32, i32, i32, i32, i32 }>* 
        @"$s1a1fQryFQOMQ" 
        to %swift.type_descriptor*
      ), i64 0
    ) #5
  %3 = extractvalue %swift.metadata_response %2, 0
  %4 = bitcast %swift.type* %3 to i8***
  %5 = getelementptr inbounds i8**, i8*** %4, i64 -1
  %.valueWitnesses = load i8**, i8*** %5, align 8, !invariant.load !42, !dereferenceable !43
  %6 = bitcast i8** %.valueWitnesses to %swift.vwtable*
  %7 = getelementptr inbounds %swift.vwtable, %swift.vwtable* %6, i32 0, i32 8
  %size = load i64, i64* %7, align 8, !invariant.load !42
  %p2 = alloca i8, i64 %size, align 16
  call void @llvm.lifetime.start.p0i8(i64 -1, i8* %p2)
  %8 = bitcast i8* %p2 to %swift.opaque*
  store i8* %p2, i8** %p2.debug, align 8
  %p1 = alloca i8, i64 %size, align 16
  call void @llvm.lifetime.start.p0i8(i64 -1, i8* %p1)
  %9 = bitcast i8* %p1 to %swift.opaque*
  store i8* %p1, i8** %p1.debug, align 8
  call swiftcc void @"$s1a1fQryF"(%swift.opaque* noalias nocapture sret %9)
  %10 = getelementptr inbounds i8*, i8** %.valueWitnesses, i32 2
  %11 = load i8*, i8** %10, align 8, !invariant.load !42
  %initializeWithCopy = bitcast i8* %11 to %swift.opaque* (%swift.opaque*, %swift.opaque*, %swift.type*)*
  %12 = call %swift.opaque* %initializeWithCopy(%swift.opaque* noalias %8, %swift.opaque* noalias %9, %swift.type* %3) #3
  %13 = call swiftcc i8**
    @swift_getOpaqueTypeConformance(
      i8* undef, 
      %swift.type_descriptor* bitcast (
        <{ i32, i32, i16, i16, i16, i16, i8, i8, i8, i8, i32, i32, i32, i32, i32 }>*
        @"$s1a1fQryFQOMQ"
        to %swift.type_descriptor*
      ), i64 1
    ) #5
  %14 = getelementptr inbounds i8*, i8** %13, i32 1
  %15 = load i8*, i8** %14, align 8, !invariant.load !42
  %16 = bitcast i8* %15 to void (%swift.opaque*, %swift.type*, i8**)*
  call swiftcc void %16(%swift.opaque* noalias nocapture swiftself %8, %swift.type* %3, i8** %13)
  %17 = getelementptr inbounds i8*, i8** %.valueWitnesses, i32 1
  %18 = load i8*, i8** %17, align 8, !invariant.load !42
  %destroy = bitcast i8* %18 to void (%swift.opaque*, %swift.type*)*
  call void %destroy(%swift.opaque* noalias %8, %swift.type* %3) #3
  call void %destroy(%swift.opaque* noalias %9, %swift.type* %3) #3
  %19 = bitcast %swift.opaque* %9 to i8*
  call void @llvm.lifetime.end.p0i8(i64 -1, i8* %19)
  %20 = bitcast %swift.opaque* %8 to i8*
  call void @llvm.lifetime.end.p0i8(i64 -1, i8* %20)
  ret void
}

  • swift_getOpaqueTypeMetadataというランタイム関数に、 $s1a1fQryFQOMQを渡している

  • $s1a1fQryFQOMQは opaque type descriptor for <<opaque return type of a.f() -> some>>

  • これで%3にMetatypeが取り出される 実際には真の型であるIntのMetatypeが得られる

  • getelementptrの-1で%5にValue Witness Tableを取り出す

  • getelementptrの8で%7に型のメモリサイズを取り出す

  • このサイズを使って、allocaでメモリ確保して、 %p1と%p2にアドレスを代入

  • bitcastで%p1をopaqueポインタにキャスト

  • callでfを呼び出し、そのポインタを引数に渡す

  • さっき取り出したVWTからgetelementptrの2で initializeWithCopyを取り出す

  • callでそれを呼び出してコピーを実行

  • swift_getOpaqueTypeConformanceというランタイム関数に、 OTDと1を渡している。 この1はこの型が準拠するプロトコルリストからPを指定する番号

  • これによって%13にProtocol Witness Tableが取り出せる 実際には真の型であるIntのPのPWT

  • getelementptrの1でPWTからメソッドを%14に取り出す

  • callでプロトコルメソッドの呼び出し

  • getelementptrの1でVWTからdestroyを取り出す

  • callでそれを呼び出してp1とp2を破棄

  • メモリ解放はallocaなのでコード無し

  • Opaque Type Descriptorがfのコンパイル時に一緒に生成されているので、fの返す真の型が変更されたときには、OTDの中身も一緒に変更される。

  • caller側では、OTDをランタイム関数に渡して、Metatype, VWT, PWTなどを取得して動作するので、OTDの中身が変わっても互換性を維持できる。

特殊化の実験

最適化でfの呼び出しが消去されないように、 fに@inline(never)を付ける。

callee SIL

sil hidden [noinline] @$s1b1fQryF : $@convention(thin) () 
  -> @out @_opaqueReturnTypeOf("$s1b1fQryF", 0) 🦸 {
// %0                                             // user: %1
bb0(%0 : $*@_opaqueReturnTypeOf("$s1b1fQryF", 0) 🦸):
  %1 = unchecked_addr_cast %0 : 
    $*@_opaqueReturnTypeOf("$s1b1fQryF", 0) 🦸 to $*Int // user: %4
  %2 = integer_literal $Builtin.Int64, 3          // user: %3
  %3 = struct $Int (%2 : $Builtin.Int64)          // user: %4
  store %3 to %1 : $*Int                          // id: %4
  %5 = tuple ()                                   // user: %6
  return %5 : $()                                 // id: %6
} // end sil function '$s1b1fQryF'
  • 最適化前と変化無し！

caller SIL

// callF()
sil hidden @$s1b5callFyyF : $@convention(thin) () -> () {
bb0:
  %0 = alloc_stack $Int                           // users: %2, %7, %4
  // function_ref f()
  %1 = function_ref @$s1b1fQryF : 
    $@convention(thin) () 
    -> @out @_opaqueReturnTypeOf("$s1b1fQryF", 0) 🦸 // user: %3
  %2 = unchecked_addr_cast %0 : 
    $*Int to $*@_opaqueReturnTypeOf("$s1b1fQryF", 0) 🦸 // user: %3
  %3 = apply %1(%2) : 
    $@convention(thin) () 
    -> @out @_opaqueReturnTypeOf("$s1b1fQryF", 0) 🦸
  %4 = load %0 : $*Int                            // user: %6
  // function_ref Int.print()
  %5 = function_ref @$sSi1bE5printyyF : 
    $@convention(method) (Int) -> () // user: %6
  %6 = apply %5(%4) : $@convention(method) (Int) -> ()
  dealloc_stack %0 : $*Int                        // id: %7
  %8 = tuple ()                                   // user: %9
  return %8 : $()                                 // id: %9
} // end sil function '$s1b5callFyyF'

  • 真の型Intでalloc_stackして、アドレスを%0に代入

  • それを@_opaqueReturnTypeOf("$s1b1fQryF", 0)型のポインタにキャストして、 fの呼び出しに渡している

  • Intのprintメソッド$sSi1bE5printyyFを直接呼び出し

  • dealloc_stackでメモリ解放

  • ORT型での操作がなくなり、Intを直接扱っている

  • fを呼び出す時に、IntへのポインタをORT型へのポインタにキャストしただけ

caller LLVM-IR

; Function Attrs: noinline norecurse nounwind writeonly
define hidden swiftcc void @"$s1b1fQryF"
  (%swift.opaque* noalias nocapture sret) local_unnamed_addr #5 {
entry:
  %._value = bitcast %swift.opaque* %0 to i64*
  store i64 3, i64* %._value, align 1
  ret void
}
  • ほぼ変化無し！

callee LLVM-IR

define hidden swiftcc void @"$s1b5callFyyF"() local_unnamed_addr #1 {
entry:
  %0 = alloca %TSi, align 8
  %1 = bitcast %TSi* %0 to i8*
  call void @llvm.lifetime.start.p0i8(i64 8, i8* nonnull %1)
  %2 = bitcast %TSi* %0 to %swift.opaque*
  call swiftcc void @"$s1b1fQryF"(%swift.opaque* noalias nocapture nonnull sret %2)
  %._value = getelementptr inbounds %TSi, %TSi* %0, i64 0, i32 0
  %3 = load i64, i64* %._value, align 8
  tail call swiftcc void @"$sSi1bE5printyyF"(i64 %3)
  call void @llvm.lifetime.end.p0i8(i64 8, i8* nonnull %1)
  ret void
}
  • allocaでInt型の変数を確保
  • そのアドレスを%swift.opaque*にキャスト
  • それを引数に渡してfを呼び出す
  • Intのprintメソッド$sSi1bE5printyyFを呼び出し
  • 返り値がopaque pointerでの間接返しになっている事以外は、普通にIntを扱うコードと同じ。
  • 最適化により、OTDとランタイム関数の使用が消去されている。
  • 抽象化によるパフォーマンスのロスが無い事がわかる。
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment