Swiftの中間言語SILを読む その2 - box-to-stack optimization

January 11, 2018

どういう進め方をしようか少し迷ったけれど、SILのSyntaxなどはすっ飛ばしてまず最適化を1つ読んでみることにした。Syntaxはわからなければそのたびにドキュメント見ればだいたいわかりそうなのと記事にしたとしてもドキュメントの焼き直しくらいにしかならなさそうなので、進めながらわからなかったところ・知らなかったところをメモする程度にして、このシリーズでは主に最適化を順番に読んでいくことにした。

まずは練習がてら、前回紹介した この動画でも少し触れられているbox-to-stack optimizationを読んでみる。

box-to-stack optimization 概要

ファイルとしてはlib/SILOptimizer/AllocBoxToStack.cppbox-to-stack optimization とか alloc_box Promotion とかいう名前で呼ばれている通り、SILのalloc_box命令をalloc_stack命令に変える(つまりアロケート先をヒープからスタックにPromoteする)最適化のこと。

box-to-stack optimizationはGuaranteed Optimizationである。

なぜ必要なのか?

Swiftでは関数内で宣言した変数が必ずしもスタックに載せることができて、関数のスコープを抜けたタイミングで破棄できるとは限らない。

なぜかというとSwiftはClosureをサポートしており、変数がClosureによってキャプチャされ、変数のライフタイムが関数のスコープより長くなる(escapeする)可能性があるからである。

func myFunction() -> Int {
   var x = 1
   runClosure { x = 2 }
   return x
}

(ちなみにスタックに載せられる・載せられないをstack disciplineに従うとかいうみたいなのだが、いまだになんて訳すべきなのかはわからない)

このためSwiftとしてはSILGenの時点(つまりraw SIL)では全ての変数は一旦alloc_box命令によってヒープにアロケートすることにして、使われ方を確認したのち本当にローカルな変数なのであれば最適化によってスタックへのアロケートに変更するという動きをする。

最適化の動きをみてみる

func myFunction() -> Int {
  var a = 1
  return a
}

このシンプルなコードを例に -sil-print-allで最適化の過程をのぞいてみる。

$ swiftc -Onone -Xllvm -sil-print-all -Xllvm -sil-print-only-functions=myFunctionSiy bts.swift &> bts.sil

するとStack Promotion of Box Objects という名前のPassの前後でalloc_box から alloc_stackに変わっていることが確認できる。

// myFunction()
sil hidden @_T03bts10myFunctionSiyF : $@convention(thin) () -> Int {
bb0:
  %0 = alloc_box ${ var Int }, var, name "a"      // users: %10, %1
  %1 = project_box %0 : ${ var Int }, 0           // users: %7, %6
  // function_ref Int.init(_builtinIntegerLiteral:)
  %2 = function_ref @_T0S2iBi2048_22_builtinIntegerLiteral_tcfC : $@convention(method) (Builtin.Int2048, @thin Int.Type) -> Int // user: %5
  %3 = metatype $@thin Int.Type                   // user: %5
  %4 = integer_literal $Builtin.Int2048, 1        // user: %5
  %5 = apply %2(%4, %3) : $@convention(method) (Builtin.Int2048, @thin Int.Type) -> Int // user: %6
  store %5 to [trivial] %1 : $*Int                // id: %6
  %7 = begin_access [read] [static] %1 : $*Int    // users: %9, %8
  %8 = load [trivial] %7 : $*Int                  // user: %11
  end_access %7 : $*Int                           // id: %9
  destroy_value %0 : ${ var Int }                 // id: %10
  return %8 : $Int                                // id: %11
} // end sil function '_T03bts10myFunctionSiyF'

*** SIL function after Guaranteed Passes "Stack Promotion of Box Objects" (1) ***
// myFunction()
sil hidden @_T03bts10myFunctionSiyF : $@convention(thin) () -> Int {
bb0:
  %0 = alloc_stack $Int, var, name "a"            // users: %9, %5, %6
  // function_ref Int.init(_builtinIntegerLiteral:)
  %1 = function_ref @_T0S2iBi2048_22_builtinIntegerLiteral_tcfC : $@convention(method) (Builtin.Int2048, @thin Int.Type) -> Int // user: %4
  %2 = metatype $@thin Int.Type                   // user: %4
  %3 = integer_literal $Builtin.Int2048, 1        // user: %4
  %4 = apply %1(%3, %2) : $@convention(method) (Builtin.Int2048, @thin Int.Type) -> Int // user: %5
  store %4 to [trivial] %0 : $*Int                // id: %5
  %6 = begin_access [read] [static] %0 : $*Int    // users: %8, %7
  %7 = load [trivial] %6 : $*Int                  // user: %10
  end_access %6 : $*Int                           // id: %8
  dealloc_stack %0 : $*Int                        // id: %9
  return %7 : $Int                                // id: %10
} // end sil function '_T03bts10myFunctionSiyF'

クロージャによってキャプチャされる場合は必ずpromoteされるかと言われるとそんなことはなくて、@escapingの有無によってpromoteされるかされないか決まる。

@escapingがない場合は最適化される。

func runClosure(_ f: () -> ()) {
  f()
}

func myFunction() -> Int {
  var x = 1
  runClosure { x = 2 }
  return x
}
%0 = alloc_stack $Int, var, name "x"

@escapingをつけるとこの最適化はされない。 (ちなみにどのalloc_boxも最適化ができない場合、-sil-print-allでの出力はスキップされる。)

func runClosure(_ f: @escaping () -> ()) {
  f()
}
%0 = alloc_box ${ var Int }, var, name "x"

動きはわかったので、次は実装であるAllocBoxToStack.cppを読んでみる。

メインのロジックをみてみる

最適化はrunという関数を持ったSILFunctionTransformを継承してつくられ、run内でSILを書き換えていくことで行われていく。このクラスがおそらくPassManager.cppによって管理されている?

class AllocBoxToStack : public SILFunctionTransform {
  /// The entry point to the transformation.
  void run() override { ... }
}

メインの実装はシンプルで、関数内のAllocBoxInst命令を探して、canPromoteAllocBox でチェックして、promoteできそうならPromotableに記録する。

for (auto &BB : *getFunction()) {
  for (auto &I : BB)
    if (auto *ABI = dyn_cast<AllocBoxInst>(&I))
      if (canPromoteAllocBox(ABI, PromotedOperands))
        Promotable.push_back(ABI);
}

そしてrewritePromotedBoxesで書き換える。

if (!Promotable.empty()) {
  bool CFGChanged = false;
  auto Count = rewritePromotedBoxes(Promotable, PromotedOperands,
                                    CFGChanged);

メインの流れはこんな感じなので、あとはそれぞれ

  • promoteできるかどうかの判断のロジック
  • 書き換えのロジック

を追ってみる。

Promoteできるかどうかの判断のロジック

canPromoteAllocBox / findUnexpectedBoxUse 辺りの関数によって行われている。

まず、SILモジュールの機能として、SILValue(%1 のようなやつ)が何かの命令(SILInstruction, alloc_boxなど) のオペランド(Operand)になっているかを取れ、どこで使われているかを確認できる。 ちなみにSIL上にもusers:で表示されている。

%0 = alloc_box ${ var Int }, var, name "x"      // users: %16, %9, %1

まずBoxであることに起因する命令、例えば参照カウントを増やす・減らすなどの命令は無視できる。

if (isa<StrongRetainInst>(User) || isa<StrongReleaseInst>(User) ||
    isa<ProjectBoxInst>(User) || isa<DestroyValueInst>(User) ||
    (!inAppliedFunction && isa<DeallocBoxInst>(User)))
  continue;

変数がコピーされている場合はその先も追っていく必要があるので、チェック用のリストに追加して再帰的にチェックする。

if (isa<MarkUninitializedInst>(User) || isa<CopyValueInst>(User)) {
  copy(cast<SingleValueInstruction>(User)->getUses(),
       std::back_inserter(Worklist));
  continue;
}

@escapingによってエスケープする場合はまずココに来る。クロージャを作る前にcopy_valueによって参照がコピーされ、partial_applyでクロージャを作る際のコンテキストとして渡される。

%9 = copy_value %0 : ${ var Int }               // user: %11
mark_function_escape %1 : $*Int                 // id: %10
%11 = partial_apply %8(%9) : $@convention(thin) (Bool, @owned { var Int }) -> () // user: %12

そこからは作ったクロージャ自体やその使われ方をチェックしていく。

checkPartialApplyBody はクロージャのBodyの中での変数の使われ方を見る。クロージャにはコンテキストとして変数が渡されることになるが、その変数について再度findUnexpectedBoxUseを呼び出して使われかたを確認している。

partialApplyEscapespartial_apply命令で作ったクロージャの使われ方を見る。そのクロージャが他の関数に渡されている場合はいくつかの例外を除きescapeされたとされる。

書き換えのロジックをみてみる

rewriteAllocBoxAsAllocStackが書き換え用の関数である。やっていることはシンプルでスタックへ書き換えて、要らないものを消す。

具体的には、

  • alloc_boxalloc_stackに変換する
  • project_box命令を消してalloc_stackでアロケートしたものを直接見るように書き換える。
  • 最後で使われたところにdealloc_stack命令を挿入する
  • 参照カウントの増減などの命令はそのまま消す

まとめ

まずは基本的な最適化をみてみた。まだSILモジュールでわからないところがちょいちょいあるので読むのにそこそこ時間がかかってしまったが、ある程度は読めたと思う。。

次はもう一つぐらい最適化を読んでみたい。

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