Swiftの中間言語SILを読む その3 - class_methodのDevirtualization

January 31, 2018

最近は別のことをやっていてあまりSwiftに触ってなかったのだけど、気分転換に最適化を1つ読んでみる。

SwiftにおけるDevirtualizeの実装

Devirtualizeはvtableやwitness tableを使ったメソッドディスパッチを、staticなディスパッチ(つまりただの関数呼び出し)に変換する最適化である。

SwiftにおいてはDevirtualizeはGuaranteedなOptimizationではなく、Generic Performance Optimizationである。つまり-Oオプションをつけた場合のみ有効になる。

Devirtualizerと名のつく最適化Passは実はいくつかあり、そのため共通的な処理はlib/SILOptimizer/Utils/Devirtulizer.cppにまとめられていて、それを各Passが使っている形になる。

今回読むのはclass_method / super_method / witness_method命令についてのPassでlib/SILOptimizer/Transforms/Devirtualizer.cppにある。

最適化の出力を見るときにはIndirect Call Devirtualizationなどで探すと良い。

PASS(Devirtualizer, "devirtualizer",
     "Indirect Call Devirtualization")

大まかにはtryDevirtualizeApplyをエントリポイントとして、そこから形に応じてtryDevirtualizeWitnessMethod, tryDevirtualizeClassMethodを呼び出す。

今回は特にclass_methodの最適化について見ていく。

DevirtualizeのキーになるstripUpCasts関数

swift/InstructionUtils.cpp at master · apple/swift · GitHub

Devirtualizeをするには「その変数のDynamicTypeがなにであるか」をOptimize時に知る必要がある。例えば以下のようなケースの場合は代入を辿っていけばanimal.bark()animalのDynamicTypeはDogになることがわかり、Dogbark()メソッドを直接呼び出せるか検討できる。

let animal: Animal = Dog()
// ...
animal.bark()

SILレベルではlet animal: Animal = Dog()はこんな感じで、Dog型の値を作ったあとにupcast命令でAnimalにしていることがわかる。

%4 = alloc_ref $Dog
%5 = upcast %4 : $Dog to $Animal
store %5 to %3 : $*Animal

stripUpCasts関数はまさにこのupcastを辿っていってDynamicTypeを見つけ出すのに使われる。

class_methodに関するDevirtualize 2パターン

class_method命令について、最適化が適用できる可能性があるのは大きく分けて以下の2パターン。

1. 実質的にfinalなメソッドの場合

isEffectivelyFinalMethodという関数でtrueが返ってくる場合がそれに該当する。

swift/Devirtualize.cpp at master · apple/swift · GitHub

「実質final」は明示的に指定したケースも含めてこの3パターンのみ。

  • そのclassもしくはメソッドにに明示的にfinalが指定されている場合
class Animal { ... }

// classにfinal
final class Dog: Animal { ... }

// methodにfinal
class Cat: Animal {
  final func bark() { ... }
}
  • メソッドが最初に実装されたクラス以降誰にもoverrideされていない場合
class Animal {
  func bark() { ... }
}

// すべてのサブクラスがbark()をoverrideしていない 
// => Dog, Catのbark()は実質final
class Dog: Animal { }
class Cat: Animal { }
  • メソッドがoverrideされているが、そのクラスのサブクラスでは誰もoverrideしていない場合
class Animal { 
  func bark() { ... }
}

// overrideしているが、そのサブクラスでは誰もoverrideしていない
// => Dogのbark()は実質final
class Dog: Animal {
  override func bark() { ... }
}

class ShibaKen: Dog { }

2. DynamicTypeが静的に分かる場合

その変数が初期化されたところまでstripUpCastsで辿っていくと実体がわかることがある。

class Animal {
  func bark() { }
}

class Dog: Animal {
  // subclassでoverrideされているので実質finalには当てはまらない
  override func bark() { }
}

class ShibaKen: Dog {
  override func bark() { }
}

// しかしstripUpcastによってDynamicTypeがわかる。
let animal: Animal = Dog()
animal.bark()

読んでわからなかったところ その1 - getExactDynamicType

class_methodの「DynamicTypeが静的に分かる場合」に関して実はもう1つパターンがある。それがgetExactDynamicTypeによって「実際のインスタンスはわからないけど、DynamicTypeは静的にわかる」ケースである。

テストでいうとこの部分が該当することから分かる通り、本来は以下のようなケースで最適化されることを期待しているように見える。

func hogehoge(b: Bool) {
  let animal: Animal
  if b {
    animal = Dog(name: "pochi")
  } else {
    animal = Dog(name: "taro")
  }
  animal.bark()
}

bは実行時にしか決まらないので当然ifのどっちに入ってくるかはわからないためどのどっちで作られたインスタンスを使うかは決められない。が分岐のすべてのケースで実体はDogなためanimalのDynamicTypeはDogに決まる。

それに基づいて最適化をするのだろうが、半日考えてこれに該当させられるケースを見つけられなかった。試しに該当部分の最適化をコメントアウトしてビルドしてみた結果、案の定該当テスト部分のみfailしたので、消しても大きな影響はもしかしたらないのかもしれない。p-rチャンス?

読んでわからなかったところ その2 - super_method命令

Classに関するdevirtualizeにおいてはもう一つsuper_method命令に関する最適化があるはずなのだが、これもそもそもsuper_methodを吐くようなswiftコードを書くことができなかった。

該当部分のコミットを見るとこんなコードがテストケースとして書かれているのだが、このコードを-emit-silgenしてもsuper_methodはSILに現れなかった。

class Parent {
  @inline(never)
  class func onlyInParent() {}
  @inline(never)
  final class func finalOnlyInParent() {}
  @inline(never)
  class func foo() {}
}

class Child : Parent {}

class Grandchild : Child {
  class func onlyInGrandchild() {
    super.onlyInParent()
    super.finalOnlyInParent()
  }

  override class func foo() {
    super.foo()
  }
}

SILGenモジュールでsuper_methodを吐くコードを探してみたがどうやらisForeignというものがfalseじゃないとダメらしい。今回はなにかはわからなかった。

if (!constant.isForeign) {
  superMethod = SGF.B.createSuperMethod(loc, castValue, constant,
                                            functionTy);
}

まとめ

class_method(とsuper_method)について最適化がされる代表的なケースをコードから読み解いてみた。(たぶんこれ以外にもあるだろうけれど….)

次回はもう一つwitness_method命令、つまりprotocol witness tableを引く場合のdevirtualizeについて見てみる。

このエントリーをはてなブックマークに追加