Skip to content

Instantly share code, notes, and snippets.

@freddi-kit
Last active May 22, 2020 06:54
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save freddi-kit/4cda6ed8f3abaa1e426852674bd359ce to your computer and use it in GitHub Desktop.
Save freddi-kit/4cda6ed8f3abaa1e426852674bd359ce to your computer and use it in GitHub Desktop.
mayHaveSideEffects.md

slidenumbers: true autoscale: true

mayHaveSideEffects

わいわいswiftc #20 22nd/May/2020

@___freddi___


本日の話の流れ・趣旨

  • わいわいswiftc 番外編ワークショップ #3 - 福岡 の復習
  • 「副作用がありそう」なコードをコンパイラが見つけ方を知る

わいわいswiftc 番外編ワークショップ #3 - 福岡

  • ご参加ありがとうございました
  • みんな一生懸命解いていて嬉しいです
    • C++ の部分が難しかったので解けなくても当然です

わいわいswiftc 番外編ワークショップ #3 - 福岡


ちょっと復習 ~ SILとは

  • Swiftの中間表現言語 (Swift Intermediate Language)
  • Swiftのコードをコンパイルしている途中で現れる
  • 最適化はSILのコードで行われる
  • 最適化前のSILがraw SIL、後がcanonical SIL

ちょっと復習 ~ SIL(例)

SILに変換前

var a = 10

ちょっと復習 ~ SIL(例)

SILに変換後

sil_stage canonical

import Builtin
import Swift
import SwiftShims

@_hasStorage @_hasInitialValue var a: Int { get set }

// a
sil_global hidden @$s5swift1aSivp : $Int

// main
sil @main : $@convention(c) (Int32, UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>) -> Int32 {
bb0(%0 : $Int32, %1 : $UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>):
  alloc_global @$s5swift1aSivp                    // id: %2
  %3 = global_addr @$s5swift1aSivp : $*Int        // user: %6
  %4 = integer_literal $Builtin.Int64, 10         // user: %5
  %5 = struct $Int (%4 : $Builtin.Int64)          // user: %6
  store %5 to %3 : $*Int                          // id: %6
  %7 = integer_literal $Builtin.Int32, 0          // user: %8
  %8 = struct $Int32 (%7 : $Builtin.Int32)        // user: %9
  return %8 : $Int32                              // id: %9
} // end sil function 'main'

// Int.init(_builtinIntegerLiteral:)
sil public_external [transparent] [serialized] @$sSi22_builtinIntegerLiteralSiBI_tcfC : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int {
// %0                                             // user: %2
bb0(%0 : $Builtin.IntLiteral, %1 : $@thin Int.Type):
  %2 = builtin "s_to_s_checked_trunc_IntLiteral_Int64"(%0 : $Builtin.IntLiteral) : $(Builtin.Int64, Builtin.Int1) // user: %3
  %3 = tuple_extract %2 : $(Builtin.Int64, Builtin.Int1), 0 // user: %4
  %4 = struct $Int (%3 : $Builtin.Int64)          // user: %5
  return %4 : $Int                                // id: %5
} // end sil function '$sSi22_builtinIntegerLiteralSiBI_tcfC'

ちょっと復習 ~ SILコードの構造

  • SILの構造は以下のざっと以下の通り(テーブルとか一部省略)
    • SIL Module (ソースファイル全体)
    • の中に、SIL Function (Swiftで作った関数から生成)
    • の中に、SIL Basic Block (条件分岐のスコープとか)
    • の中に、SIL Instruction (コードの一行一行)

ちょっと復習 ~ SILコードの構造(例)

// ファイル全体がSIL Module
sil_stage canonical

import Builtin
...

// SIL Function
// main
sil @main : $@convention(c) (Int32, ...) -> Int32 {
// bb から始まる SIL Basic Block
bb0(%0 : $Int32, %1 : $UnsafeMutablePointer<Optional ..
  // ここらから SIL Instruction
  alloc_global @$s5valueAASivp                    // id: %2
  ...
  return %8 : $Int32                              // id: %9
} // end sil function 'main'

以降、各単語の冒頭のSILは省略できそうなときは省略


ちょっと復習 ~ SILOptimizer

  • SIL を最適化するコンパイラのモジュール
  • それぞれの最適化の役割を持つ Pass というモジュールからなる
  • Module 全体を見る Pass と Function を見る Pass がある

Dead Code Elimination

  • 使われていないコードを削除する最適化Pass
    • 使われていないコード == "死んでるコード" == Dead Code
  • 大体の場面で DCE と略されている
    • コンパイラのコードとか
  • ワークショップの課題で作らされた Pass
    • ワークショップのは削除の条件が厳しくないminDCE

Dead Code Eliminationの仕組み

  1. 削除しない条件に当てはまる Instruction を Live Insturction としてMark
  2. Markされていない Insturction を Function から取り除く
  3. Function からいらないコードが消えている
  4. (゚д゚)ウマー

Dead Code Eliminationの仕組み

  • 本家での Live Insturction のだいたいの条件
    • returnnoreturn といった Insturction。
      • ワークショップでは return のみ
    • ❌ 副作用のある可能性がある Insturction
    • ⭕ Live Instruction に依存している Instruction
    • ❌ Live Insturction が 制御依存 している条件分岐 - 複数の Basic Block の間の走査
  • ワークショップで実装した minDCE は⭕がついた条件だけを利用

Dead Code Eliminationの仕組み 余談


return や noreturn といった Insturction

  • Basic Block のルール
    • Terminator と呼ばれる Instruction で終わらないといけない
      • return
        • noreturn
        • unreachable (FatalErrorのあとに付いたりする)
        • throw ...

ワークショップでreturnされた値をusefulとして扱った

理由

  • 例えば下のSILコード
  store %5 to %3 : $*Int                          // id: %6
  %7 = integer_literal $Builtin.Int32, 0          // user: %8
  %8 = struct $Int32 (%7 : $Builtin.Int32)        // user: %9
  return %8 : $Int32                              // id: %9

ワークショップでreturnされた値をusefulとして扱った

理由

  • このコードは 最後に return %8 してる(id: %9
    • id: %9return (Terminator) => Live
  • %8 の値を生成している Instruction は 依存 している => Live
    • %8 を返している Instruction は id: %8 の Inscructionと呼ぶ
  • id: %8 が利用している %7id: %7)も依存 => Live
  • %7 からも 依存を芋づる式に走査して Live としてMarkといけない

ワークショップでreturnされた値をusefulとして扱った

理由

  • 例えば下のSILコードは id: %6 が消えるかもしれない
    • return に依存していないInstruction
    • %7, %8, %9 に依存していないから
  store %5 to %3 : $*Int                          // id: %6
  %7 = integer_literal $Builtin.Int32, 0          // user: %8
  %8 = struct $Int32 (%7 : $Builtin.Int32)        // user: %9
  return %8 : $Int32                              // id: %9

ワークショップでreturnされた値をusefulとして扱った

理由

  • minDCE には問題点
    • noreturn の時とか無条件ですべてのコードを消すのでは
    • その時は Instructionに 副作用があるかどうか を調べる
    • ワークショップでは時間が足りんので省略
      • 今日の話題はコレ
      • 「Instructionに 副作用があるかどうか を調べる」関数の話

seemsUseful

  • 以下は、本家 DCE にある seemsUseful という関数の一部
    • 名前の通り「UsefulなInstruction」かを true/false で返す
      • Live と Useful は同じ意味と思って良い 
    • 先ほど紹介した Terminator のチェックもここで判断してる
    • Instruction の依存の走査はまた別の場所
static bool seemsUseful(SILInstruction *I) {
  if (I->mayHaveSideEffects())
    return true;

  ...

seemsUseful

  • Function 中の Instruction を Mark する markLive 関数で利用
    • seemUseful の結果が trueならば
      • InstructionmarkValueLiveする
      • 厳密には Insctruction 中の SIL Value をMark

mayHaveSideEffects

  • seemsUseful でUsefulかどうかの判断に使われている関数
  • これで「副作用があるかどうか」を判断してるらしい
    • 条件によっては副作用を発生しないこともあるので may

mayHaveSideEffects への疑問

  • mayHaveSideEffects は、 何を「副作用」としているのか?
  • 内部実装を見て確かめてみたい

mayHaveSideEffects の内部実装

  • こんなかんじ
bool SILInstruction::mayHaveSideEffects() const {
  // If this instruction traps then it must have side effects.
  if (mayTrap())
    return true;

  MemoryBehavior B = getMemoryBehavior();
  return B == MemoryBehavior::MayWrite ||
    B == MemoryBehavior::MayReadWrite ||
    B == MemoryBehavior::MayHaveSideEffects;
}

mayHaveSideEffects の内部実装の見るポイント?

  • この2つをフォーカスすれば、謎を解明できそう!
    • mayTrap
    • MemoryBehavior

mayTrap

  • // If this instruction traps then it must have side effects.
  • 直訳: この命令がトラップする場合、副作用があるはず
  • trap == プログラムの異常終了

mayTrap の内部実装をとりあえず覗く

  • 割とシンプルでやさしい
bool SILInstruction::mayTrap() const {
  switch(getKind()) {
  case SILInstructionKind::CondFailInst:
  case SILInstructionKind::UnconditionalCheckedCastInst:
  case SILInstructionKind::UnconditionalCheckedCastAddrInst:
    return true;
  default:
    return false;
  }
}

dyn_cast<I>isa<T>

  • Passでは、コード中で見るInsctructionはSILInstruction
  • 具体的なInstructionの種類を知るには?
  • dyn_cast<I>isa<T> (キャスト)を使って確認できる

dyn_cast<I>isa<T> サンプルコード

  • 今見ているInstructionがInterger Literal Instructionか見ている

    // Instが Interger Literal Instructionかしらべる
    // $0 = integer_literal $Builtin.Int64, 100
    if (auto *BI = dyn_cast<IntegerLiteralInst>(Inst)) {

dyn_cast<I>isa<T>

  • それぞれのInstructionは、SILInstruction 型を継承した型で表される
    • SILInstruction 型は、コンパイラ上で SIL Instruction を表現している
  • 目的のInstruction型へのダウンキャストが成功すれば良い

getKind

  • getKind はキャストを使わない方法
    • enumを返していて、switchとか使えて良い
  • SILInstructionKind は、enumの値でInstructionがどの種類のものかを表す
switch(I->getKind()) {
case SILInstructionKind::IntegerLiteralInst: ...
case SILInstructionKind:: ReturnLiteralInst: ...

mayTrap の内部実装をとりあえず覗く (再掲)

bool SILInstruction::mayTrap() const {
  switch(getKind()) {
  case SILInstructionKind::CondFailInst:
  case SILInstructionKind::UnconditionalCheckedCastInst:
  case SILInstructionKind::UnconditionalCheckedCastAddrInst:
    return true;
  default:
    return false;
  }
}

つまり?

  • この3つのInstructionはtrapなのでUsefulになっている
    • CondFailInst
    • UnconditionalCheckedCastInst
    • UnconditionalCheckedCastAddrInst

わからないことはSIL.rstで調べよう

  • SIL.rstにはだいたいのInstructionの情報が乗っています

SIL.rstでInstructionを調べるコツ

  • キャムルケースになってるのをスネークケースに分解してCtrl+F
    • cond_fail
    • unconditional_checked_cast
    • unconditional_checked_cast_addr
  • 全部ヒットします

cond_fail

// BNF
sil-instruction ::= 'cond_fail' sil-operand, string-literal
  • もしオペランドが 1 のときRuntime Failure
    • オペランド == 引数と考えるとわかりやすい
    • sil-operand がオペランド
cond_fail %0 : $Builtin.Int1, "failure reason"
// %0 must be of type $Builtin.Int1

unconditional_checked_cast

// BNF
sil-instruction ::= 'unconditional_checked_cast' sil-operand 'to' sil-type
  • キャストできるかを確かめる
  • オペランドのオブジェクトがキャスト不可の場合Runtime Failure
  • as! のようなもの
%1 = unconditional_checked_cast %0 : $A to $B
%1 = unconditional_checked_cast %0 : $*A to $*B
// $A and $B must be both objects or both addresses
// %1 will be of type $B or $*B

unconditional_checked_cast_addr

// BNF
sil-instruction ::= 'unconditional_checked_cast_addr'
                     sil-type 'in' sil-operand 'to'
                     sil-type 'in' sil-operand
  • キャスト
  • 最初のオペランドが、最後のオペランドの型にがキャスト不可の場合Runtime Failure

unconditional_checked_cast_addr

  • unconditional_checked_cast と同じように見えるけど
    • どうやらキャスト元のオブジェクトは破棄されるらしい
unconditional_checked_cast_addr $A in %0 : $*@thick A to $B in $*@thick B
// $A and $B must be both addresses
// %1 will be of type $*B
// $A is destroyed during the conversion. There is no implicit copy.

unconditional_checked_cast_value はどうなの?

  • mayTrap に入ってない unconditional_checked 系統のInstruction
  • 入れ忘れか、そうでないか不明 🤔 🤔 🤔 🤔 🤔
    • Runtime Failure するのに ....

mayHaveSideEffects の内部実装(再掲)

bool SILInstruction::mayHaveSideEffects() const {
  // If this instruction traps then it must have side effects.
  if (mayTrap())
    return true;

  MemoryBehavior B = getMemoryBehavior();
  return B == MemoryBehavior::MayWrite ||
    B == MemoryBehavior::MayReadWrite ||
    B == MemoryBehavior::MayHaveSideEffects;
}
  • つまり、プログラムが**条件によっては異常終了するなら「副作用あり」**と捉える
  • つぎは Memory Behavior!

getMemoryBehavior とは

  • その SIL Instruction がメモリ上でどう振る舞うかを調べる
  • 読み解くには、わりとLLVMの知識が必要

getMemoryBehavior の実装

SILInstruction::MemoryBehavior SILInstruction::getMemoryBehavior() const {

  if (auto *BI = dyn_cast<BuiltinInst>(this)) {
    // Handle Swift builtin functions.
    const BuiltinInfo &BInfo = BI->getBuiltinInfo();
    if (BInfo.ID != BuiltinValueKind::None)
      return BInfo.isReadNone() ? MemoryBehavior::None
                                : MemoryBehavior::MayHaveSideEffects;

    // Handle LLVM intrinsic functions.
    const IntrinsicInfo &IInfo = BI->getIntrinsicInfo();
    if (IInfo.ID != llvm::Intrinsic::not_intrinsic) {
      // Read-only.
      if (IInfo.hasAttribute(llvm::Attribute::ReadOnly) &&
          IInfo.hasAttribute(llvm::Attribute::NoUnwind))
        return MemoryBehavior::MayRead;
      // Read-none?
      return IInfo.hasAttribute(llvm::Attribute::ReadNone) &&
                     IInfo.hasAttribute(llvm::Attribute::NoUnwind)
                 ? MemoryBehavior::None
                 : MemoryBehavior::MayHaveSideEffects;
    }
  }

  // Handle full apply sites that have a resolvable callee function with an
  // effects attribute.
  if (isa<FullApplySite>(this)) {
    FullApplySite Site(const_cast<SILInstruction *>(this));
    if (auto *F = Site.getCalleeFunction()) {
      return F->getEffectsKind() == EffectsKind::ReadNone
                 ? MemoryBehavior::None
                 : MemoryBehavior::MayHaveSideEffects;
    }
  }

  switch (getKind()) {
#define FULL_INST(CLASS, TEXTUALNAME, PARENT, MEMBEHAVIOR, RELEASINGBEHAVIOR)  \
  case SILInstructionKind::CLASS:                                              \
    return MemoryBehavior::MEMBEHAVIOR;
#include "swift/SIL/SILNodes.def"
  }
  llvm_unreachable("We've just exhausted the switch.");
}

getMemoryBehavior

  • 長い;;
  • まずは戻り値の enum から見ていく

SILInstruction::MemoryBehavior

  • メモリ上の振る舞いを定義する enum
    • 以下の5つが定義されている
      • None
      • MayRead
      • MayWrite
      • MayReadWrite
      • MayHaveSideEffects

SILInstruction::MemoryBehavior::None

  • 何もしないやつ

SILInstruction::MemoryBehavior::MayRead

  • The instruction may read memory.
  • 直訳) メモリを読むかもしれない

SILInstruction::MemoryBehavior::MayWrite

  • The instruction may write to memory.
  • 直訳) メモリに書き込むかもしれない

...::MemoryBehavior::MayReadWrite

  • The instruction may read or write memory.
  • 直訳) 読むか書き込むかもしれない(またはその両方?)

...::MemoryBehavior::MayHaveSideEffects

  • The instruction may have side effects not captured solely by its users. Specifically, it can return, release memory, or store. Note, alloc is not considered to have side effects because its result/users represent its effect.
  • 直訳) Instructionは、その利用者だけでは捉えられない副作用を持つことがあります。具体的には、リターン、メモリ解放、ストアなどです。注意:allocは、その結果/利用者がその作用を表すので、副作用があるとは考えられません。
  • 意訳)なにかしら、のちのち副作用がある

MemoryBehavior ?

  • つまりは、そのInstructionが、どのようにメモリ上で振る舞うか を表す
  • 見た感じだと、次のメモリ上の振る舞いが「副作用」として該当するようにしている
    • MayWrite (書き)
    • MayReadWrite (読み書き)
    • MayHaveSideEffects (副作用あり)
  • seemUseful は、今見ているInscructionに副作用があるか調べている

getMemoryBehaviorの実装を見る

最初の if にフォーカスを当てる

  if (auto *BI = dyn_cast<BuiltinInst>(this)) {
    // Handle Swift builtin functions.
    const BuiltinInfo &BInfo = BI->getBuiltinInfo();
    if (BInfo.ID != BuiltinValueKind::None)
      return BInfo.isReadNone() ? MemoryBehavior::None
                                : MemoryBehavior::MayHaveSideEffects;

    // Handle LLVM intrinsic functions.
    const IntrinsicInfo &IInfo = BI->getIntrinsicInfo();
    if (IInfo.ID != llvm::Intrinsic::not_intrinsic) {
      // Read-only.
      if (IInfo.hasAttribute(llvm::Attribute::ReadOnly) &&
          IInfo.hasAttribute(llvm::Attribute::NoUnwind))
        return MemoryBehavior::MayRead;
      // Read-none?
      return IInfo.hasAttribute(llvm::Attribute::ReadNone) &&
                     IInfo.hasAttribute(llvm::Attribute::NoUnwind)
                 ? MemoryBehavior::None
                 : MemoryBehavior::MayHaveSideEffects;
    }
  }

getMemoryBehaviorの実装を見る

  • キャストでInstructionが BuiltinInst なのかを調べてる
  if (auto *BI = dyn_cast<BuiltinInst>(this)) {
     ...

BuiltinInst とは?

  • Represents an invocation of builtin functionality provided by the code generator.
  • 直訳) コード・ジェネレータが提供する組み込み機能の呼び出しを表します。
  • 🤔 🤔 🤔 🤔 🤔

BuiltinInst とは?

  • SIL.rst にあった
  • https://github.com/apple/swift/blob/master/docs/SIL.rst#builtin
  • Invokes functionality built into the backend code generator, such as LLVM- level instructions and intrinsics.
  • SIL Instruction の冒頭に builtin とついているのがポイント
  • 直訳) LLVMレベルの命令や組み込み関数など、バックエンドコードジェネレーターに組み込まれた機能を呼び出します。  
// Example
%1 = builtin "foo"(%1 : $T, %2 : $U) : $V

BuiltinInst とは?

  • BuiltinInst には以下の2つの種類がある
    • Swift builtin function
    • LLVM intrinsic function

BuiltinInst とは? Swift builtin function

  • Swift(SIL)のコードレベルで表現できない処理 の呼び出し

    • LLVMの処理に書き換わるべき場所
  • 例) Int(64)同士の比較演算

    // SIL
    %5 = builtin "cmp_eq_Int64"(%3 : $Builtin.Int64, %4 : $Builtin.Int64) ...

    ↓ LLVM IRだとこうなる

    // LLVM IR
    %10 = icmp eq i64 %8, 10

BuiltinInst とは? Swift builtin function

  • Builtins.def にbuiltin functionの一覧あり
    • ちなみに先程の cmp_eq_Int64 は、Builtins.def では cmp_eq としてリストされている

BuiltinInstとは? LLVM intrinsic functions

  • LLVMに、既にある関数を読み込む コード

getMemoryBehaviorの実装を見る

Swift builtin functions

  • 見た感じ、その2つで条件を分けている
  • Swift builtin functions へのアプローチをまずは見てみる
  if (auto *BI = dyn_cast<BuiltinInst>(this)) {
    // Handle Swift builtin functions.
    const BuiltinInfo &BInfo = BI->getBuiltinInfo();
    ...

    // Handle LLVM intrinsic functions.
    const IntrinsicInfo &IInfo = BI->getIntrinsicInfo();
    ...
  }

getMemoryBehaviorの実装を見る

Swift builtin functions

  if (auto *BI = dyn_cast<BuiltinInst>(this)) {
    // Handle Swift builtin functions.
    const BuiltinInfo &BInfo = BI->getBuiltinInfo();
    if (BInfo.ID != BuiltinValueKind::None)
      return BInfo.isReadNone() ? MemoryBehavior::None
                                : MemoryBehavior::MayHaveSideEffects;
  • どうやらこのbuiltinのfunctionの情報をとって、以下の情報をもとにMemory Behaviorを判断
    • BInfo.ID
    • BInfo.isReadNone()

BInfo.ID

  • BInfo.ID とは?
    • 戻り値になってるのは、BuiltinValueKind
    • 型の詳細を見てみる

BInfo.ID

  • 見た感じ BuiltinValueKindenum
/// BuiltinValueKind - The set of (possibly overloaded) builtin functions.
enum class BuiltinValueKind {
  None = 0,
#define BUILTIN(Id, Name, Attrs) Id,
#include "swift/AST/Builtins.def"
};
  • どうやら先程言及した Builtins.def から、なんか取っている?

BInfo.ID

  • Builtins.def を覗く
  • さっき言及した cmp_eq_Int64 周辺の部分を見てみる
...
#ifndef BUILTIN_BINARY_PREDICATE
#define BUILTIN_BINARY_PREDICATE(Id, Name, Attrs, Overload) \
          BUILTIN(Id, Name, Attrs)
#endif
BUILTIN_BINARY_PREDICATE(ICMP_EQ,  "cmp_eq",   "n", IntegerOrRawPointerOrVector)
BUILTIN_BINARY_PREDICATE(ICMP_NE,  "cmp_ne",   "n", IntegerOrRawPointerOrVector)
BUILTIN_BINARY_PREDICATE(ICMP_SLE, "cmp_sle",  "n", IntegerOrVector)
...

BInfo.ID

BUILTIN_BINARY_PREDICATEというものが定義されている

// マクロ
BUILTIN_BINARY_PREDICATE(ICMP_EQ,  "cmp_eq",   "n", IntegerOrRawPointerOrVector)

ICMP_EQがさっき例で載っていた cmp_eq のId

以下でBUILTINに変換できるようになっている

// マクロ
#define BUILTIN_BINARY_PREDICATE(Id, Name, Attrs, Overload) \
          BUILTIN(Id, Name, Attrs)

BInfo.ID

/// BuiltinValueKind - The set of (possibly overloaded) builtin functions.
enum class BuiltinValueKind {
  None = 0,
#define BUILTIN(Id, Name, Attrs) Id,
#include "swift/AST/Builtins.def"
};
  • つまり、BInfo.ID は�Builtns.defで定義された、builtin functionのID
    • Builtins.defの内部のマクロで BUILTIN(Id, Name, Attrs) にかえて、
    • そのBUILTIN - Idenumの値にしている

getMemoryBehaviorの実装を見る

Swift builtin functions

  • if (BInfo.ID != BuiltinValueKind::None)
  • false ならLLVM intrinsic function として次のパートでハンドリング
  if (auto *BI = dyn_cast<BuiltinInst>(this)) {
    // Handle Swift builtin functions.
    const BuiltinInfo &BInfo = BI->getBuiltinInfo();
    if (BInfo.ID != BuiltinValueKind::None)
      return BInfo.isReadNone() ? MemoryBehavior::None
                                : MemoryBehavior::MayHaveSideEffects;
  • 次は isReadNone。だけどだいたい同じメカニズムなのでサッと紹介

isReadNone

  • builtin functionが メモリアクセスを許可されているかを調べる
    • LLVM IRでは関数に 属性(Attribute) がつけられる
      • どういう振る舞いを行うか?が属性から読み取れる
    • readnone 属性がついていると、メモリアクセスが許可されない
    • 逆に言えば、readnoneがついてなければ、なにかメモリでやるかもしれないということになる

isReadNone

// Builtins.def からまた抜粋
#ifndef BUILTIN_BINARY_PREDICATE
#define BUILTIN_BINARY_PREDICATE(Id, Name, Attrs, Overload) \
          BUILTIN(Id, Name, Attrs)
#endif
BUILTIN_BINARY_PREDICATE(ICMP_EQ,  "cmp_eq",   "n", IntegerOrRawPointerOrVector)
  • BUILTIN(Id, Name, Attrs) のなかで Attrs="n" だったら readnone
    • メモリアクセスができない処理に変換されるということ
  • bultin functions は Bultins.def で 属性を一つ一つ ラベリングしてる
    • 変換先は、属性がつけれない Instruction 単体だから?

getMemoryBehavior の実装を見る

Swift builtin functions

  if (auto *BI = dyn_cast<BuiltinInst>(this)) {
    // Handle Swift builtin functions.
    const BuiltinInfo &BInfo = BI->getBuiltinInfo();
    if (BInfo.ID != BuiltinValueKind::None)
      return BInfo.isReadNone() ? MemoryBehavior::None
                                : MemoryBehavior::MayHaveSideEffects;
  • つまり↑は 以下のように読み取れる
    • Insructionの情報から、builtin function の属性を見る
    • もし、readnone (メモリアクセスが許可されてない)なら副作用は当然なし
    • そうでないなら、副作用は何らかの形であるかもしれない

getMemoryBehaviorの実装を見る

Swift builtin functions

  • このまでのノリがわかると後半もわかる
  • 次は、LLVM intrinsic functionsのハンドリング
    • こっちも属性を見てるのがノリでわかる
    // Handle LLVM intrinsic functions.
    const IntrinsicInfo &IInfo = BI->getIntrinsicInfo();
    if (IInfo.ID != llvm::Intrinsic::not_intrinsic) {
      // Read-only.
      if (IInfo.hasAttribute(llvm::Attribute::ReadOnly) &&
          IInfo.hasAttribute(llvm::Attribute::NoUnwind))
        return MemoryBehavior::MayRead;
      // Read-none?
      return IInfo.hasAttribute(llvm::Attribute::ReadNone) &&
                     IInfo.hasAttribute(llvm::Attribute::NoUnwind)
                 ? MemoryBehavior::None
                 : MemoryBehavior::MayHaveSideEffects;
    }

LLVMの関数の属性 NoUnwind

  • 属性 NoUnwind
    • 例外を投げないという属性

getMemoryBehaviorの実装を見る

Swift builtin functions

  if (IInfo.hasAttribute(llvm::Attribute::ReadOnly) &&
      IInfo.hasAttribute(llvm::Attribute::NoUnwind))
    return MemoryBehavior::MayRead;
  // Read-none?
  return IInfo.hasAttribute(llvm::Attribute::ReadNone) &&
                  IInfo.hasAttribute(llvm::Attribute::NoUnwind)
              ? MemoryBehavior::None
              : MemoryBehavior::MayHaveSideEffects;
  • つまり↑のコードは
    • 例外を外に投げないで、かつ読み込みオンリーの関数は MayRead
    • 例外を外に投げる、または、メモリアクセスできる関数は MayHaveSideEffects
    • それ以外は None

getMemoryBehaviorの実装を見る

ここまでのまとめ

  • まずは、そのInstructionがbultin instructionか見る
    • もしそうであれば、LLVM IR になった後の属性を見て、メモリ上の振る舞いを判断

getMemoryBehaviorの実装を見る

  • bultin instruction ではない場合はどうか
  • 次のパートを見てみる
  // Handle full apply sites that have a resolvable callee function with an
  // effects attribute.
  if (isa<FullApplySite>(this)) {
    FullApplySite Site(const_cast<SILInstruction *>(this));
    if (auto *F = Site.getCalleeFunction()) {
      return F->getEffectsKind() == EffectsKind::ReadNone
                 ? MemoryBehavior::None
                 : MemoryBehavior::MayHaveSideEffects;
    }
  }

FullApplySite

  • apply, begin_apply といった関数呼び出しのためのInsructionがある

  • Passのコードでは、FullApplySite という型でまとめられている


SIL FunctionのAttribute

// BNF
sil-function-attribute ::= '[' sil-function-effects ']'
sil-function-effects ::= 'readonly'
sil-function-effects ::= 'readnone'
sil-function-effects ::= 'readwrite'
sil-function-effects ::= 'releasenone'

SIL FunctionのAttribute

  • sil-function-attribute はSIL Functionの宣言時に必須
// BNF
sil-function ::= 'sil' sil-linkage? sil-function-attribute+
                   sil-function-name ':' sil-type
                   '{' sil-basic-block+ '}'

getMemoryBehaviorの実装を見る

  • みたかんじ
    • 関数呼び出しのInstructionかどうか調べている
    • 関数呼び出しだったら callee(呼びたす関数)の属性を調べる
    • ReadNone じゃないなら MayHaveSideEffects
  if (isa<FullApplySite>(this)) {
    FullApplySite Site(const_cast<SILInstruction *>(this));
    if (auto *F = Site.getCalleeFunction()) {
      return F->getEffectsKind() == EffectsKind::ReadNone
                 ? MemoryBehavior::None
                 : MemoryBehavior::MayHaveSideEffects;
    }
  }

getMemoryBehaviorの実装を見る

ここまでわかったこと

  • SIL Instructionのメモリの振る舞いを調べるときは、LLVM の属性を利用している
  • もしくは SIL Function の属性

getMemoryBehaviorの実装を見る

  • 最後のパート
  • どう見てもBuiltin.def(Swift builtin funcion)のときと同じパターン
  switch (getKind()) {
#define FULL_INST(CLASS, TEXTUALNAME, PARENT, MEMBEHAVIOR, RELEASINGBEHAVIOR)  \
  case SILInstructionKind::CLASS:                                              \
    return MemoryBehavior::MEMBEHAVIOR;
#include "swift/SIL/SILNodes.def"
  }
  llvm_unreachable("We've just exhausted the switch.");

SILNodes.def のMEMBEHAVIORについて

  • SILNodes.defに各Instructionがどのようにメモリ上の振る舞うか書いてある
    • FULL_INST という情報でまとめられている
      • CLASS には、さっきの SILInstructionKind と同じ値が割り振られている ( getKind の戻り値のenum型)
      • MEMBEHAVIOR には、MemoryBehavior と同じ値が割り振られている(enum型)
  • 先程の Builtins.def のときと同じ 

getMemoryBehavior の実装を見る

  • ということは、
    • SILNodes.def にある、「Inscrutctionがメモリ上でどのように振る舞うか(MEMBEHAVIOR)」の定義をマクロで switch-case に展開している
  switch (getKind()) {
#define FULL_INST(CLASS, TEXTUALNAME, PARENT, MEMBEHAVIOR, RELEASINGBEHAVIOR)  \
  case SILInstructionKind::CLASS:                                              \
    return MemoryBehavior::MEMBEHAVIOR;
#include "swift/SIL/SILNodes.def"
  }
  llvm_unreachable("We've just exhausted the switch.");

getMemoryBehaviorの実装を見る

まとめ

  • getMemoryBehavior は以下の観点でInstructionのメモリの振る舞いを見ている
    • 変換先の LLVM IR の Instrucion は、どんな属性になるか?
      • Attrs in Builtins.def
    • 呼び出す LLVM IR の Function は、どんな属性か?
    • 呼び出している SIL Function は、どんな属性か?
    • ↑ でもわかんないなら、既に Instruction に定義されている属性を見に行く
      • MEMBEHAVIOR in SILNode.def

getMemoryBehaviorの実装を見る

全部読めた!


mayHaveSideEffects まとめ

  • 次の場合、SIL Instruction に副作用があるとコンパイラは判断する
    • 条件によっては、Runtime Failure するか?
    • 条件によっては、メモリ上で書き込みなどといったことを行うか?
bool SILInstruction::mayHaveSideEffects() const {
  // If this instruction traps then it must have side effects.
  if (mayTrap())
    return true;

  MemoryBehavior B = getMemoryBehavior();
  return B == MemoryBehavior::MayWrite ||
    B == MemoryBehavior::MayReadWrite ||
    B == MemoryBehavior::MayHaveSideEffects;
}

まとめ


コンパイラにとって「副作用がありそう」なコードとは一体?

  • Runtime Errorが起こりそうなコード
  • メモリ書き込みなどが起こりそうなコード

コンパイラにとって「副作用がありそう」の判別の仕方

  • LLVM の属性などを利用して判断している
    • Builtins.def や LLVM の関数から読み取って判断
  • SILNodes.def で SIL Instruction のメモリの振る舞いは定義されている

今日勉強したこと


参考文献

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment