ようこそ

これから、わいわいswiftc 番外編ワークショップ Vol.3 福岡のワークショップの問題を出していきます。問題はSILOptimizerのコンパイラのコードを理解できるようになるための初心者向けの問題で構成されています。また、各問題の前には必ず解説が入るので安心して進めてください。

わからなかったら？

おそらく、多くの人が初めてコンパイラのコードやC++のコードを触るのでちょっと戸惑うかもしれません。わからなかったら、ぜひ講師へ質問したり、同じチームの人と一緒に考えてみましょう。ポインタ型というよくわからない物を使いますが、テンプレで覚えられる文はテンプレみたいに成っているのでそれで覚えてください。

諸注意

※ から始まる文は基本的に余談ですので、特に見なくても大丈夫です。
このワークショップでは、初歩的なSILOptimiserの知識をなるべく網羅するために、一部問題では簡単なSwiftコードを最適化するようにしか考慮されていません。

1時間目: 簡単なPassを書いてみよう

先程解説したとおり、SILOptimizerはPassと呼ばれるモジュール群からなり、SILコードを操作して最適化をしたり、走査をして診断を行います。

この章は、Passを知るための基本的な知識を知るためのものです。

この章で学べること

SILOptimizerで扱う基本的なデータ構造を知ることができます
一番簡単な最適化PassであるAssume Single Threadedについて学べます

SILの構造について

SILは大きいものから、Module・Function・Basic Block・Instructionにわかれます。これは最適化前のraw SILも最適化後のcanonical SILも同様です。

例として、以下のソースで見てみましょう。

func zero() -> Int {
    return 0
}

これを、swiftcコマンドでraw SILに変換すると以下のようなコードに変換されます。

rawSILを出すコマンド.sh

$ swiftc -emit-silgen source1.swift -o source1.sil

source1.sil

import Builtin
import Swift
import SwiftShims

func zero() -> Int

// main
sil [ossa] @main : $@convention(c) (Int32, UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>) -> Int32 {
bb0(%0 : $Int32, %1 : $UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>):
  %2 = integer_literal $Builtin.Int32, 0          // user: %3
  %3 = struct $Int32 (%2 : $Builtin.Int32)        // user: %4
  return %3 : $Int32                              // id: %4
} // end sil function 'main'

// zero()
sil hidden [ossa] @$s4zeroAASiyF : $@convention(thin) () -> Int {
bb0:
  %0 = integer_literal $Builtin.IntLiteral, 0     // user: %3
  %1 = metatype $@thin Int.Type                   // user: %3
  // function_ref Int.init(_builtinIntegerLiteral:)
  %2 = function_ref @$sSi22_builtinIntegerLiteralSiBI_tcfC : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %3
  %3 = apply %2(%0, %1) : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %4
  return %3 : $Int                                // id: %4
} // end sil function '$s4zeroAASiyF'

// Int.init(_builtinIntegerLiteral:)
sil [transparent] [serialized] @$sSi22_builtinIntegerLiteralSiBI_tcfC : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int

では、どの部分がどれに当たるかを解説します。

Module

SILソースファイル全体です。import文、型の定義やFunctionなどから成っています。
今回は扱いませんが、Witness TableやV Tableといった関数テーブルの情報も乗ります。

Function

SILの関数です。Basic Blockから成っています。SwiftのFunctionから直接変換されたものだと考えてください。

以下はmain関数とzero関数の例です。

// main
sil [ossa] @main : $@convention(c) (Int32, UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>) -> Int32 {
bb0(%0 : $Int32, %1 : $UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>):
  %2 = integer_literal $Builtin.Int32, 0          // user: %3
  %3 = struct $Int32 (%2 : $Builtin.Int32)        // user: %4
  return %3 : $Int32                              // id: %4
} // end sil function 'main'

// zero()
sil hidden [ossa] @$s4zeroAASiyF : $@convention(thin) () -> Int {
bb0:
  %0 = integer_literal $Builtin.IntLiteral, 0     // user: %3
  %1 = metatype $@thin Int.Type                   // user: %3
  // function_ref Int.init(_builtinIntegerLiteral:)
  %2 = function_ref @$sSi22_builtinIntegerLiteralSiBI_tcfC : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %3
  %3 = apply %2(%0, %1) : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %4
  return %3 : $Int                                // id: %4
} // end sil function '$s4zeroAASiyF'

※ Swiftでは暗黙的にmain関数が生成されるので、mainという名前のFunctionが存在します。

Basic Block

SILの関数の中にあるブロックです。Instructionから成っています。
先頭にbb[数字]:というラベルがついています。

以下はzero関数のbb0の例です。

bb0:
  %0 = integer_literal $Builtin.IntLiteral, 0     // user: %3
  %1 = metatype $@thin Int.Type                   // user: %3
  // function_ref Int.init(_builtinIntegerLiteral:)
  %2 = function_ref @$sSi22_builtinIntegerLiteralSiBI_tcfC : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %3
  %3 = apply %2(%0, %1) : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %4
  return %3 : $Int                                // id: %4

Instruction

実際に値を操作したり、関数を呼び出したりする命令です。

文末にある%[数字]はidと呼ばれるもので、これに値が格納されることがあります。

読むポイントを解説すると、

returnのような値を格納しないInstructionは、右の方のコメントに // id: %4 のように振られたidがわかるようになっています。
// user: %3 はその行のInstructionをつかっているidの一覧になっています。

以下はzero関数のbb0のInstructionの例です。

  %0 = integer_literal $Builtin.IntLiteral, 0     // user: %3
  %1 = metatype $@thin Int.Type                   // user: %3
  // function_ref Int.init(_builtinIntegerLiteral:)
  %2 = function_ref @$sSi22_builtinIntegerLiteralSiBI_tcfC : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %3
  %3 = apply %2(%0, %1) : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %4
  return %3 : $Int                                // id: %4

Basic Blockには、最後にはかならずreturnなどのTerminatorと呼ばれるInstructionが必要になります。

※ https://github.com/apple/swift/blob/master/docs/SIL.rst#basic-blocks にBasic Blockの定義があります。

これらは、SILOptimizerのPassを書くときでも同様のデータ構造が使うことができます。

では次は実際にPassを見ていきましょう。

SILOptimizerのPassの構成

まず、準備したSwiftコンパイラのXcodeを開き、WaiWaiOptimiser.cppを開きましょう。
XcodeでCmd + Shift + oと押して、WaiWaiOptimizer.cppと入力するとすぐに開くことができます。

下記のようなコードが出てくると思います。

#include "swift/SILOptimizer/PassManager/Passes.h"
#include "swift/SIL/SILFunction.h"
#include "swift/SIL/SILInstruction.h"
#include "swift/SIL/SILModule.h"
#include "swift/SILOptimizer/Utils/Local.h"
#include "swift/SILOptimizer/PassManager/Transforms.h"
#include "llvm/Support/CommandLine.h"
#include <iostream>

using namespace swift;
using namespace std;

namespace {
class WaiWaiOptimizer : public SILFunctionTransform {
  /// The entry point to the transformation.
  void run() override {
    // [No.1]: Assume Single Threadedを書く
    // Hint: Referenceカウンタを操作するInstructionをすべてnon atomicにする
  }
};
}


SILTransform *swift::createWaiWaiOptimizer() {
  return new WaiWaiOptimizer();
}

各問題では、コメントで示された部分の中身を実際に実装していきます。

ここで、コードの各部分を解説をしましょう。

#include "swift/SILOptimizer/PassManager/Passes.h"
#include "swift/SIL/SILFunction.h"
#include "swift/SIL/SILInstruction.h"
#include "swift/SIL/SILModule.h"
#include "swift/SILOptimizer/Utils/Local.h"
#include "swift/SILOptimizer/PassManager/Transforms.h"
#include "llvm/Support/CommandLine.h"
#include <iostream>

using namespace swift;
using namespace std;

#include はSwiftでいうimportに近いものと覚えておいてください。

※ namespaceという概念がC++にはありますが、このusing namespace swift;は「swiftというネームスペース以下にあるものは、このソースではすべてswiftネームスペースなしに明示しなくても使えるようにする」という意味です。後々意味がわかります。

次に移りましょう。

namespace {
class WaiWaiOptimizer : public SILFunctionTransform {
  /// The entry point to the transformation.
  void run() override {
    // [No.1]: Assume Single Threadedを書く
    // Hint: Referenceカウンタを操作するInstructionをすべてnon atomicにする
  }
};
}

これが、今回各問題でアルゴリズムを書き込むPassであるWaiWaiOptimizerの本体です。Passはこのようにクラスとして実装されます。
よく見ると、WaiWaiOptimizerは、SILFunctionTransformというクラスを継承しています。

このクラスを継承することで、WaiWaiOptimizerはFunctionごとに呼ばれるPassとして取り扱われます。
他に、SILModuleTransformを継承すれば、ModuleごとによばれるPassとして取り扱われます。

※ 事前課題をやった人はもうおわかりと思いますが、WaiWaiOptimizerをsil-optで呼び出したときにHello, Optimizer!がたくさん出力されましたね？ WaiWaiOptimizerはSILFunctionTransformを継承しているので、つまりはFunctionごとにHello, Optimizer!が出力されたことになります

※ 先程、using namespace swift;の話をしましたが、実はここで効果を発揮しています。SILFunctionTransformはswiftというネームスペースにあるので、swift::SILFunctionTransformと書かないといけないのですが、using namespace swift;で書かないで良いようになっています。

そして、WaiWaiOptimizerはrun関数をオーバーライド（実装の上書き）しています。このrun関数の中で実際に最適化のアルゴリズムを実装します。

最後のコードに移りますが、これはPipelineなどからPassを要求された際、オブジェクトを渡す関数です。

SILTransform *swift::createWaiWaiOptimizer() {
  return new WaiWaiOptimizer();
}

※ Pass.defというものにPassの情報を登録しないといけないですが、登録した際にはこの関数の定義が自動生成されるので、その実装しなければなりません。定義とか実装とかナンノコッチャと思う人はC++のヘッダーまわり勉強すると理解できます。

`SILFunctionTransform`のAPIについて

さて、基本的なPassの構造はわかりましたね。
しかし、最適化アルゴリズムを実装するには、いま見ているFunctionのBasic BlockやInstructionを手に入れないと何もできません。
SILFunctionTransformは以下のような機能を提供しているので、Basic BlockやInstructionの情報を簡単に手に入れることができます。

getFunction() 関数
- 現在見ているFunctionのポインタ型を手に入れることができる。帰ってくる型はSILFunction* 型

試しにgetFunction() 関数を使ってみましょう。run() の中に試しに次のように書いてみましょう。

// autoはC++の型推論キーワード。
// 本当はC++では`auto`のところにはSILFunction* と書かないといけないですが、C++には一応型推論が実装されています。
auto currentFunction = getFunction(); // C++は文の最後にはセミコロンが必要です

これで、現在Passが見ているFunctionの情報を手に入れました。これで第一段階クリアです。
では、Basic Blockを手に入れましょう。実は、SILFunction型はBasic Blockのコレクション型のようなものです。

コレクション型ということは、for文でFunction内の各BasicBlockの情報を取ることができます。つまり、次のように書くことができます。

auto currentFunction = getFunction();
for(auto &bb: *currentFunction) {
    
}

getFunction 関数はポインタ型を返します。なので、*currentFunctionのように返されたものは先頭に*がないと、実態を取り扱うことができません。

ただし、ポインタ型について詳しく説明するとこんがらがるので、今日はFunctionからBasic Blockを取り出すコードは↑のような書き方になるとだけ覚えておいてください。

forの中身でbbという変数がBasic Blockの情報をもっています。これはSILBasicBlockという型です。感のいい人ならわかると思いますが、この型はInstructionのコレクション型のようなものです。

つまりは、このように書けます。

auto currentFunction = getFunction();
for(auto &bb: *currentFunction) {
    for(auto &i: bb) {
            
    }  
}

bb ポインタ型ではないので、*currentFunctionのように先頭に*がなくて大丈夫です。
一番深いネストの部分のiがInstructionを示しています。型はSILInstructionです。

さて、Instructionまでたどり着きました。次が最後のステップです。
次は、今見ているInstructionが何のInstructionなのかを特定しないといけません。SILOptimizerのPassではInstructionの特定にはダウンキャストを使っています。

まず、先程の例のInstructionのコードを出します。

  %0 = integer_literal $Builtin.IntLiteral, 0     // user: %3
  %1 = metatype $@thin Int.Type                   // user: %3
  // function_ref Int.init(_builtinIntegerLiteral:)
  %2 = function_ref @$sSi22_builtinIntegerLiteralSiBI_tcfC : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %3
  %3 = apply %2(%0, %1) : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %4
  return %3 : $Int                                // id: %4

例えば、1行目のinteger_literalは、PassではIntegerLiteralInstというSILInstructionを継承した型で表現されています。2行目のmetatypeはMetatypeInst・・・。

では、すべてのInstructionは型で扱えるとして、今のiがどのInstructionなのかを調べたいですね。その時は、dyn_castというキャストの関数を使います。

dyn_cast関数では、<>の中にキャストしたい型、引数にチェックしたいInstructionのポインタを入れます。普通の型をポインタ型に変換したいときは、変数の先頭に&をつけてください。

auto currentFunction = getFunction();
for(auto &bb: *currentFunction) {
    for(auto &i: bb) {
        if(auto integerI = dyn_cast<IntegerLiteralInst>(&i)) {
                
        }
    }  
}

このC++書き方はSwiftのas?によるnilチェックに似ています。
もしdyn_castによるキャストが成功した場合、ifの中でintegerIはIntegerLiteralInstとして取り扱われます。そうでなければ、ifには入りません。

ここまで、このソースコードが何をやっているかをコメントで解説すると、

// 今Passが見ているFunctionの情報をもらう
auto currentFunction = getFunction();
// Functionを構成してる各Basic Blockを見る
for(auto &bb: *currentFunction) {
    // Basic Blockを構成してる各Instructionを見る
    for(auto &i: bb) {
        // 今見ているInstructionが`integer_literal`なら・・・？
        if(auto integerI = dyn_cast<IntegerLiteralInst>(&i)) {
                
        }
    }  
}

こんなかんじです。

最後に、一つ重要な関数を紹介します。なにかしら、SILコードに変更があったときは、run関数の最後でinvalidateAnalysis関数を最後に呼ばなければなりません。

invalidateAnalysis(SILAnalysis::InvalidationKind::Instructions);

これは、Moduleに何かしらの変更をした際は必ず呼ばないといけない関数です。ここでは、Instructionを変更したことを引数に渡しています。
Analysisとは直訳すると解析ですが、たとえばclassの継承関係などの情報はAnalysisからもらうことがあります。

C++を書く上での注意事項

C++を書く上での注意事項ですが、先程も言ったとおりポインタ型というものがあります。
intを使った例を以下に載せます。

// a は intの変数
int a = 10;

// b は int*(intのアドレス) の変数
int *b;

// &a はaのアドレスを表す
// bにaのアドレスを渡す
b = &a;

// ポインタ型に*をつけると、そのアドレスの参照先（実体）を示す
// ここではbにはaのアドレスが入っているので、cには10が入る。
int c = *b;

ほかにも&をつかう例として参照渡しや右辺値参照というものがありますが、C++の話は沼になるので省略します。

ポインタ型の関数や変数を呼び出すときは、.ではなく、->を使ってください。
たとえば、上の例だと、もしintegerIのgetValue()を呼びたいときは、

if(auto integerI = dyn_cast<IntegerLiteralInst>(&i)) {
    // integerIはIntegerLiteralInstのポインタ型。
    // getValue()関数を呼びたいなら、-> を使う
    integerI->getValue(); // C++は文の最後にはセミコロンが必要です（２回め）
}

autoでとってきた変数がポインタ型かそうでないか迷ったときは、自動補完をしてくれるIDEの力に頼ってください。

Passのデバックについて

たとえば、SILBasicBlockやSILInstructionにはdumpという関数があり、その変数がSILコード上のどのBasic Block（やInstruction)を表すかを出力させることができます。

また、getFunction()->getName().str() と書くことでマングルされた関数名をstringで受け取ることができますし、coutを使ってそれを出力させることができます。

問題1: 簡単なPassを書いてみよう

問題

Swiftプログラムをシングルスレッド向けに最適化するPassであるAssume Single Threadedを作りましょう。このPassは、

Reference Count関係のInstructionをnon-atomicにする。

ということをやっています。
ここで補足しないといけないのは、Reference Count関係のInstructionはRefCountingInst型で表現されます。
RefCountingInst型には、そのInstructionをnon-atomicにするメンバ関数があるので、探してみてください！

まず、gitでwaiwai-question01ブランチから、waiwai-question01-{あなたの名前}という名前のbranchを切ってください。
回答のコードは、WaiWaiOptimizer.cppで指定してあるところ(run関数内)に書き込みます。

問題が終わったら？

問題をテストしてください。この問題のテストファイルはswiftディレクトリから見てwaiwai-test/question01.silです。

このテストの起動方法は、

# swiftディレクトリにいる想定
$ ../build/Xcode-DebugAssert/swift-macosx-x86_64/Debug/bin/sil-opt -wai-wai-optimizer waiwai-test/question01.sil | ../build/Xcode-DebugAssert/llvm-macosx-x86_64/Debug/bin/FileCheck waiwai-test/question01.sil

を叩くとTestが走ります。何も表示されなければTest成功です。

もし、TestだけでなくOptimizeされたsilを見たいのであれば、

# swiftディレクトリにいる想定
$ ../build/Xcode-DebugAssert/swift-macosx-x86_64/Debug/bin/sil-opt -wai-wai-optimizer waiwai-test/question01.sil -o waiwai-test/optimized-question-01.sil

を叩いて、waiwai-test/optimized-question-01.silを見てみてください。成功していればちゃんと変更されてます。

テストが終わったら、講師がチェックしに行くので手を上げて教えて下さい！