freddi-kit/How to develop SIL Optimizer in Swift Language.md

## How to develop SIL Optimizer in Swift Language.md

      
    Raw
  

              How to develop SIL Optimizer in Swift Language.md
            
          
    slidenumbers: true
autoscale: true
How to develop SIL Optimizer in Swift Language

わいわいswiftc #29 30th/July/2021

@___freddi___


本日の話


おもちさんの話の続き
SIL Optimizer の Pass が Swift で書けるようになったという話


ちょっと復習 ~ SIL


Swift Intermediate Language の略
Swift のソースコードをコンパイルするときに経る中間言語
ここでSwiftコンパイラによる(特有の)最適化が走る

![inline fit](compile flow.png)

ちょっと復習 ~ SIL


print("Hello World!") の SIL (最適化後) の文字列リテラルを String のイニシャライザにぶっこむコードのみを抜粋

  %8 = string_literal utf8 "Hello, World!"        // user: %13
  %9 = integer_literal $Builtin.Word, 13          // user: %13
  %10 = integer_literal $Builtin.Int1, -1         // user: %13
  %11 = metatype $@thin String.Type               // user: %13
  // function_ref String.init(_builtinStringLiteral:utf8CodeUnitCount:isASCII:)
  %12 = function_ref @$sSS21_builtinStringLiteral ... -> @owned String // user: %13
  %13 = apply %12(%8, %9, %10, %11) : ... -> @owned String // user: %15
  %14 = init_existential_addr %7 : $*Any, $String // user: %15
  store %13 to %14 : $*String                     // id: %15

ちょっと復習 ~ SIL の構造(1)


まず、SIL は大きいものから以下の構造に分けられる

SIL Module
SIL Function
SIL Basic Block
SIL Instruction


今回は小さい方から見ていく


ちょっと復習 ~ SIL の構造(2) SIL Instruction


SIL Instruction

直訳すると "SIL命令" で、スコープ中の一行一行のコードを表す
殆どが %(id) = (instruction) というフォーマット

変数名の代わりに id というものを使う


  // 変数 %8 に 文字列リテラルを入れる
  %8 = string_literal utf8 "Hello, World!" // user: %13

コメントの // user: %(id) とはそのinstructionを利用するidを表してくれる

使っているものがない・前述のフォーマットに従ってないなら // id: %(id) とその instruction の id を表してくれる


ちょっと復習 ~ SIL の構造(3) SIL Basic Block


SIL Basic Block

bb(番号): というフォーマットから始まる instruction の塊を示す
スコープ ({ } に囲まれたコード) と考えると良い


// 0番 basic block
bb0:
  ...
  %8 = string_literal utf8 "Hello, World!" // user: %13
  ...

SIL Basic Block は instruction のコレクションと思うと今後の話がわかりやすい


ちょっと復習 ~ SIL の構造(4) SIL Function


SIL Function

言わずもがな関数
１つ以上の basic block から構成される
１つのSwiftの関数は １つのSIL Function に変換される


// main関数
sil @main : $@convention(c) (Int32, ...) -> Int32 {
  bb0:
    ...
    %8 = string_literal utf8 "Hello, World!" // user: %13
    ...

SIL Function は basic block のコレクションと思うと今後の話がわかりやすい


ちょっと復習 ~ SIL の構造(5) main関数


補足として、たとえ swiftファイルに関数にを書いてなくてもコンパイル時必ず生成される function　がある
生成されるのは main 関数

C言語 の main関数と機能も同じ。プログラムのエントリポイント


swiftファイルに直接書いたコードが main関数に囲われて呼ばれる

// main関数
sil @main : $@convention(c) (Int32, ...) -> Int32 {
  ...

ちょっと復習 ~ SIL の構造(6) SIL Module


コンパイルされたSILファイル全体
グローバル変数やimportされたモジュール、struct・classの定義、function などが現れる

// sil_stage　正体は次のページ見るとわかるけど
// このSILは canonical SIL だよって意味
sil_stage canonical 

import Builtin
...

sil @main : $@convention(c) (Int32, ...) -> Int32 {
  bb0:
    ...
    %8 = string_literal utf8 "Hello, World!" // user: %13
    ...

ちょっと復習 ~ SIL Optimizer (1)


SILを最適化するコンパイラの最適化フェーズ
SIL Optimizerの中にある Pass というモジュールがそれぞれ最適化の役割を持っている
その Pass の適用の順番を組み立てて（Pass Pipeline）実際にSILを最適化するフェーズ
raw SIL が最適化前のSILで canonical SIL が最適化後

![inline 60%](flow of optimizer.png)

上の図で言えば、緑の矢印が Pipeline と考えてもらえると
最適化PassはC++で書かれている（いた）


ちょっと復習 ~ SIL Optimizer (2) Pass の種類


Pass には2種類ある

Module Pass
Function Pass
どちらも勝手に僕が呼んでるだけなので注意


Module or Functionごとに発動するPassか、という違いのみ


ちょっと復習 ~ SIL Optimizer (3) C++ の Pass を読む


実際にどういう Pass があるか読んでみよう


ちょっと復習 ~ SIL Optimizer (4) C++ の Pass を読む


AssumeSingleThreaded

知ってる限り最小で読みやすい Pass


ちょっと復習 ~ SIL Optimizer (5) C++ の Pass を読む

class AssumeSingleThreaded : public swift::SILFunctionTransform {
  /// The entry point to the transformation.
  void run() override {
    if (!getOptions().AssumeSingleThreaded)
      return;
    for (auto &BB : *getFunction()) {
      for (auto &I : BB) {
        if (auto RCInst = dyn_cast<RefCountingInst>(&I))
          RCInst->setNonAtomic();
      }
    }
    invalidateAnalysis(SILAnalysis::InvalidationKind::Instructions);
  }
};

from: lib/SILOptimizer/Transforms/AssumeSingleThreaded.cpp


ちょっと復習 ~ SIL Optimizer (6) C++ の Pass を読む


順に見ていく
SILFunctionTransform に準拠しているが、これでこの Pass は function ごとに発動される

SILModuleTransform にすると Module ごとに発動される


エントリポイントである run 関数をオーバーライドして動作を記述していく

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

ちょっと復習 ~ SIL Optimizer (7) C++ の Pass を読む


getOptions で -assume-single-threaded �オプションが付いてるか見る

ついてなかったら、最適化をしない


  ...
  /// The entry point to the transformation.
  void run() override {
    if (!getOptions().AssumeSingleThreaded)
      return;
  ...

ちょっと復習 ~ SIL Optimizer (8) C++ の Pass を読む


ここが心臓部分

まず、getFunction で SILFunction 型のオブジェクトを取る
SILFunction 型のオブジェクト は SILBasicBlock のコレクションなのでそれを forでぶん回して各 basic block を見る

BB は basic block のこと


  ...
    for (auto &BB : *getFunction()) { // ココの説明
      for (auto &I : BB) {
        if (auto RCInst = dyn_cast<RefCountingInst>(&I))
          RCInst->setNonAtomic();
      }
    }
    invalidateAnalysis(SILAnalysis::InvalidationKind::Instructions);
  ...

ちょっと復習 ~ SIL Optimizer (9) C++ の Pass を読む


また、SILBasicBlock 型のオブジェクト は SILInstruction のコレクションなのでそれを for でぶん回して各 instruction を見る

  ...
    for (auto &BB : *getFunction()) {
      for (auto &I : BB) { // ココの説明
        if (auto RCInst = dyn_cast<RefCountingInst>(&I))
          RCInst->setNonAtomic();
      }
    }
    invalidateAnalysis(SILAnalysis::InvalidationKind::Instructions);
  ...

ちょっと復習 ~ SIL Optimizer (10) C++ の Pass を読む


今見てる SILInstruction がどんな instruction かはダウンキャストすればわかる
ここでは、リファレンスカウント関係の instruction かどうかをチェックしている

RefCountingInst へのキャストチェック。instruction の種類は 型で表現
dyn_cast という特殊な関数を使う


  ...
    for (auto &BB : *getFunction()) {
      for (auto &I : BB) { 
        if (auto RCInst = dyn_cast<RefCountingInst>(&I)) // ココの説明
          RCInst->setNonAtomic();
      }
    }
    invalidateAnalysis(SILAnalysis::InvalidationKind::Instructions);
  ...

ちょっと復習 ~ SIL Optimizer (11) C++ の Pass を読む


キャストチェックが通ったら、その insturcion を non atomic にする
そして invalidateAnalysis を読んでPassのマネージャに変更があったことを知らせる

  ...
    for (auto &BB : *getFunction()) {
      for (auto &I : BB) { 
        if (auto RCInst = dyn_cast<RefCountingInst>(&I)) 
          RCInst->setNonAtomic(); // ココの説明
      }
    }
    invalidateAnalysis(SILAnalysis::InvalidationKind::Instructions); // ココの説明
  ...

ちょっと復習 ~ SIL Optimizer (12) C++ の Pass を読む


この Pass を適用するとこんな感じになる
前

strong_release %4 : $Neko

後

strong_release [nonatomic] %4 : $Neko

なぜリファレンスカウントだけなのか不明


ちょっと復習 ~ SIL Optimizer (13) Pass の登録方法


自前でcppファイルを用意したなら lib/SILOptimizer/Transforms/CMakeLists.txt に記載
include/swift/SILOptimizer/PassManager/Passes.def に ↓ みたいな記述を書く

PASS({C++のPassのクラス名}, "sil-{C++のPassのクラス名}", "なんか適当な説明")

↑ によって create{C++のPassのクラス名} という関数の実装を要求されるので、実装する

作ったPassクラスのオブジェクトを返せば良い


lib/SILOptimizer/PassManager/PassPipeline.cpp でそのPassが呼ばれるようにソースを書き換える

Passes.def への↑の書き換えによって、add{C++のPassのクラス名} という名前の関数が SILPassPipelinePlan 型に生えるのでそれを使う


ちょっと復習 ~ もっと復習したい人は


僕のNSSpainで話した内容を見てください。(英語)


Swift Optimizing (at Compiler World)


あと Swiftckaigi の登壇も参考になります


SILOptimizerを自分で作って遊んで見る @freddi-kit


やっと本題


Pass が Swift でも書けるようになりました


libswift という Swiftコンパイラのソースに存在する Swift Package を利用して開発できるようになりました
該当PR: #37398


AssumeSingleThreaded を Swift 移植しよう


試しに AssumeSingleThreaded を Swift に移植してみる


まずはじめに (1) swiftのビルド


swift コンパイラを clone して build する
apple/swift
ドキュメントによると、 libswiftを使うには、ビルドオプションに --libswift が必要


まずはじめに (2) swiftのビルド


以下でやってみる（xcodeproj の生成を行う）

$ utils/build-script --xcode --release --skip-build-benchmarks \
                     --skip-ios --skip-watchos --skip-tvos --swift-darwin-supported-archs x86_64 \
                     --sccache --libswift

まずはじめに (3) swiftのビルド


エラー発生...

CMake Error in libswift/CMakeLists.txt:
  The custom command generating

    /Users/freddi/swift-source/build/Xcode-ReleaseAssert/swift-macosx-x86_64/libswift/SIL.o

  is attached to multiple targets:

    libswift
    libswift-SIL.o

  but none of these is a common dependency of the other(s).  This is not
  allowed by the Xcode "new build system".


まずはじめに (4) swiftのビルド


ninja でやってみる

$ utils/build-script --release --skip-build-benchmarks \ # さっきと比較してココの --xcode が消えてる
                     --skip-ios --skip-watchos --skip-tvos --swift-darwin-supported-archs x86_64 \
                     --sccache --libswift

これはいけた


libswift/Package.swift を開く


libswift は Package.swift が用意されていて、これを開くと Xcode が開く

libswift/Package.swift


Xcode で開発できます
(多分) swift ビルドしなくても Xcode上では build はできると思う

![inline fit](first spm libswift.png)

Source/FunctionPasses に AssumeSingleThreadedSwift.swift を追加


AssumeSingleThreadedSwift.swift を Source/FunctionPasses 以下に追加する
現時点で何も書かれていない


AssumeSingleThreadedSwift.swift に空の Pass を追加


オリジナルの AssumeSingleThreaded は SILFunctionTransform を継承している
なので、まずは同じ働きをする FunctionPass で空のPassを作る
クロージャ内に最適化のアルゴリズムを書く

import SIL
import SILBridging

let assumeSingleThreadedSwift = FunctionPass(name: "sil-assume-single-threaded-swift") { function, context in
}

再掲 AssumeSingleThreaded.cpp

class AssumeSingleThreaded : public swift::SILFunctionTransform {
  /// The entry point to the transformation.
  void run() override {
    if (!getOptions().AssumeSingleThreaded)
      return;
    for (auto &BB : *getFunction()) {
      for (auto &I : BB) {
        if (auto RCInst = dyn_cast<RefCountingInst>(&I))
          RCInst->setNonAtomic();
      }
    }
    invalidateAnalysis(SILAnalysis::InvalidationKind::Instructions);
  }
};

移植 (1) Option のチェック

...
if (!getOptions().AssumeSingleThreaded)
  return;
...
まずはこれからやってみる

移植 (1) Option のチェック


実はこの時点でoptionを確認する方法はない
引数にある context からも現時点ではアクセスできない

import SIL
import SILBridging

let assumeSingleThreadedSwift = FunctionPass(name: "sil-assume-single-threaded-swift") { function, context in
}

移植 (1) FunctionPassContext によるBrigde


このような場合、クロージャの context を通じて必要な関数等にBrigdeする
context は FunctionPassContext 型

let assumeSingleThreadedSwift = ... { function, context in
...

移植 (1) FunctionPassContext によるBrigde


FunctionPassContext の実装を覗いてみる

struct FunctionPassContext {
  ...
  
  func erase(instruction: Instruction) {
    PassContext_eraseInstruction(passContext, instruction.bridged)
  }

  ...


どうやらこの erase は Brigde されている
PassContext_eraseInstruction は C++ のコードに実装と定義がある

定義は include/swift/SIL/SILBridging.h にある
実装は lib/SILOptimizer/PassManager/PassManager.cpp にある


移植 (1) PassContext_eraseInstruction


FunctionPassContext の実装を覗いてみる（C++）

  void PassContext_eraseInstruction(BridgedPassContext passContext,
                                     BridgedInstruction inst) {
    castToPassInvocation(passContext)->eraseInstruction(castToInst(inst));
  }

BridgedPassContext は libswift(Swift) の FunctionPassContext、BridgedInstruction は Instruction
castToPassInvocation を利用して、context を LibswiftPassInvocation に変更し C++ の Pass の関数をコールする
Instruction は SILInstruction として利用するには、castToInst に渡さなければならない


移植 (1) 参考に Option のチェックを作ってみる(libswift)


FunctionPassContext に isAssumeSingleThreadedEnabled の 実装を追加

  var isAssumeSingleThreadedEnabled: Bool {
    return !(PassContext_isAssumeSingleThreadedEnabled(passContext) == 0)
  }

次に PassContext_isAssumeSingleThreadedEnabled の実装と定義をC++側で行う


移植 (1) 参考に Option のチェックを作ってみる(定義)


PassContext_isAssumeSingleThreadedEnabled を定義 include/swift/SIL/SILBridging.h に入れる

SwiftInt PassContext_isAssumeSingleThreadedEnabled(BridgedPassContext context);

Swift の Int を返したいときは、SwiftInt を返すようにする
Bool はなかった...


移植 (1) 参考に Option のチェックを作ってみる(実装)


PassContext_isAssumeSingleThreadedEnabled を lib/SILOptimizer/PassManager/PassManager.cpp で実装する

SwiftInt PassContext_isAssumeSingleThreadedEnabled(BridgedPassContext context) {
    SILPassManager *pm = castToPassInvocation(context)->getPassManager();
    return pm->getOptions().AssumeSingleThreaded;
}

context を castToPassInvocation したものから getPassManager して PassManager の object を手に入れる
これから オリジナルの実装のように getOptions がコールできる
option  は Swift の 型として Brigde できないので現状このような実装になった


移植 (1) Option のチェック


context.isAssumeSingleThreadedEnabled をコールして完成

import SIL
import SILBridging

let assumeSingleThreadedSwift = FunctionPass(name: "sil-assume-single-threaded-swift") { function, context in
    if !context.isAssumeSingleThreadedEnabled {
        return
    }
}

移植 (2) instruction の走査


再びオリジナル実装
次はココを実装してみる

...
for (auto &BB : *getFunction()) {
  for (auto &I : BB) {
    if (auto RCInst = dyn_cast<RefCountingInst>(&I))
      RCInst->setNonAtomic();
  }
}
...

移植 (2) instruction の走査


クロージャの引数 funcion は C++実装の getFunction と同じ
cast も dyn_cast ではなく Swift のキャストで問題なし
Swift らしく書ける

    ...
    for block in funcion.blocks {
        for instruction in block.instructions {
            if let rcInst = instruction as? RefCountingInst {
               ...
            }
        }
    }
    ...

移植 (2) instruction の走査


問題は C++ の RCInst->setNonAtomic();
これは libswift にはないので Brigde が必要
要領はさっきと同じ


移植 (2) setNonAtomic の実装 (libswift)


RefCountingInst に setNonAtomic の 実装を追加

public class RefCountingInst : Instruction {
  final public var reference: Value { operands[0].value }

  public func setNonAtomic() {
      RefCountingInst_setNonAtomic(bridged)
  }
}

次に RefCountingInst_setNonAtomic の実装と定義をC++側で行う


移植 (2) setNonAtomic の実装 (定義)


RefCountingInst_setNonAtomic を定義 include/swift/SIL/SILBridging.h に入れる

void RefCountingInst_setNonAtomic(BridgedInstruction inst);

次に RefCountingInst_setNonAtomic の実装と定義をC++側で行う


移植 (2) setNonAtomic の実装　(実装)


RefCountingInst_setNonAtomic を lib/SILOptimizer/PassManager/PassManager.cpp で実装する

void RefCountingInst_setNonAtomic(BridgedInstruction inst) {
    castToInst<RefCountingInst>(inst)->setNonAtomic();
}

inst を castToInst して、オリジナル実装通り setNonAtomic をコールする


移植 (2) instruction の走査


あとは rcInst.setNonAtomic() をSwift実装でコール

    ...
    for block in funcion.blocks {
        for instruction in block.instructions {
            if let rcInst = instruction as? RefCountingInst {
                rcInst.setNonAtomic()
            }
        }
    }
    ...

だいたいできた

import SIL
import SILBridging

let assumeSingleThreadedSwift = FunctionPass(name: "sil-assume-single-threaded-swift") { function, context in
    if !context.isAssumeSingleThreadedEnabled {
        return
    }

    for block in funcion.blocks {
        for instruction in block.instructions {
            if let rcInst = instruction as? RefCountingInst {
                rcInst.setNonAtomic()
            }
        }
    }
}

残りの作業


同じ階層にある CMakeList.txt に AssumeSingleThreadedSwift.swift を追記しておく
PassManager/PassRegistration.swift) でこの Pass を追記する

private func registerSwiftPasses() {
  registerPass(silPrinterPass, { silPrinterPass.run($0) })
  registerPass(mergeCondFailsPass, { mergeCondFailsPass.run($0) })
  registerPass(simplifyGlobalValuePass, { simplifyGlobalValuePass.run($0) })
  registerPass(assumeSingleThreadedSwift, { assumeSingleThreadedSwift.run($0) }) // これ
}

後は Pass を PassPipeline で呼ばれるようにすればいい


再掲: Pass の登録方法


include/swift/SILOptimizer/PassManager/Passes.def に ↓ みたいな記述を書く

PASS({C++のPassのクラス名}, "sil-{C++のPassのクラス名}", "なんか適当な説明")

↑ によって create{C++のPassのクラス名} という関数の実装を要求されるので、実装する

作ったPassクラスのオブジェクトを返せば良い


lib/SILOptimizer/PassManager/PassPipeline.cpp でそのPassが呼ばれるようにソースを書き換える

Passes.def への↑の書き換えによって、add{C++のPassのクラス名} という名前の関数が SILPassPipelinePlan 型に生えるのでそれを使う


Pass の登録方法 Ver: libswift (1)


include/swift/SILOptimizer/PassManager/Passes.def に ↓ みたいな記述を書く

SWIFT_FUNCTION_PASS({Pass名}, "{name: 引数に渡した string}", "なんか適当な説明")

↑ によって create{Pass名} という関数が生成される（実装は必要ない）
もし C++ と libswift 実装両方あるなら、SWIFT_FUNCTION_PASS_WITH_LEGACY という物もある

libswift に実装がないなら C++ の方を呼ぶ、みたいなことができる
同様の条件で、SWIFT_FUNCTION_PASS にするとランタイムエラーになるので注意


Pass の登録方法 Ver: libswift (2)


SWIFT_FUNCTION_PASS_WITH_LEGACY の場合、 createLegacy{Pass名} という関数の実装がC++側のPassに要求される

実装しないと swift がビルドエラーになる


lib/SILOptimizer/PassManager/PassPipeline.cpp でそのPassが呼ばれるようにソースを書き換える

Passes.def への↑の書き換えによって、add{Pass名} という名前の関数が SILPassPipelinePlan 型に生えるのでそれを使う

legacy の場合は、勝手にコンパイラ側がハンドリングしてくれる


再度 Build して Test してみる


再度ビルドコマンドでビルドする
以下のコマンドを実行してTest

$ {ビルド成果物のあるフォルダ}/swiftc test.swift \ 
                                 -emit-sil -assume-single-threaded \
                                 -o result.sil -Xllvm -sil-print-pass-name

-Xllvm -sil-print-pass-name で 呼ばれた Pass をチェックできる


呼ばれた！！！

...
Start function passes at stage: Rest of Onone
  Run #22, stage Rest of Onone, pass 1: AssumeSingleThreadedSwift (sil-assume-single-threaded-swift), Function: $s4test2OBCACycfc # ここ
  Run #23, stage Rest of Onone, pass 2: OnonePrespecializations (onone-prespecializer), Function: $s4test2OBCACycfc
  Run #24, stage Rest of Onone, pass 1: AssumeSingleThreadedSwift (sil-assume-single-threaded-swift), Function: $s4test2OBCACycfC
  Run #25, stage Rest of Onone, pass 2: OnonePrespecializations (onone-prespecializer), Function: $s4test2OBCACycfC
  Run #26, stage Rest of Onone, pass 1: AssumeSingleThreadedSwift (sil-assume-single-threaded-swift), Function: $s4test2OBCfd
  Run #27, stage Rest of Onone, pass 2: OnonePrespecializations (onone-prespecializer), Function: $s4test2OBCfd
  Run #28, stage Rest of Onone, pass 1: AssumeSingleThreadedSwift (sil-assume-single-threaded-swift), Function: $s4test2OBCfD
  Run #29, stage Rest of Onone, pass 2: OnonePrespecializations (onone-prespecializer), Function: $s4test2OBCfD
  Run #30, stage Rest of Onone, pass 1: AssumeSingleThreadedSwift (sil-assume-single-threaded-swift), Function: main
  Run #31, stage Rest of Onone, pass 2: OnonePrespecializations (onone-prespecializer), Function: main
  Run module pass #32, stage Rest of Onone, pass 3: SILDebugInfoGenerator (sil-debuginfo-gen)
...

※ ちゃんと non-atomic になっているのも確認


現時点でぶつかっている壁


AssumeSingleThreadedSwift.swift の実装を変えて再ビルドしても反映されない

--clean でビルドし直さないといけないかも？


それ以外は今の所なし


わかったことや補足など


libswift で SILOptimizer の Pass を Swift で開発できるようになったのは確か
おおまかなこと（走査など）は 現状の libswift で用意された実装のみで可能
細かいことをやろうとすると context による Brigde が必要
公式ドキュメントには様々な制約が書いてある

Mandatory Pass は現時点で実装できない、など


参考文献


libswift/README.md