Skip to content

Instantly share code, notes, and snippets.

@kateinoigakukun
Created June 18, 2020 09:48
Show Gist options
  • Save kateinoigakukun/9d56120c353ff0afcd27bd28546ebfad to your computer and use it in GitHub Desktop.
Save kateinoigakukun/9d56120c353ff0afcd27bd28546ebfad to your computer and use it in GitHub Desktop.

theme: Next, 4 slidenumbers: true

Swiftのリンク時最適化プロジェクト

わいわいswiftc #21

@kateinoigakukun


Swiftの最適化レベル

  • ファイル単位 ( -O )
  • モジュール単位 ( -whole-module-optimization )

inline

[.footer: http://llvm.org/devmtg/2016-10/slides/GroffLattner-SILHighLevelIR.pdf]


Swiftの最適化レベル

  • ファイル単位 ( -O )
  • モジュール単位 ( -whole-module-optimization )
  • (New ➕) プログラム全体 at LLVMレベル
  • (New ➕) プログラム全体 at SILレベル

LTO (Link Time Optimization)

コンパイラではなく,リンカが実行する最適化.プログラム全体を一つの単位として最適化する.

inline


LTO (Link Time Optimization)

メリット

  • バイナリの依存物すべての情報を使える
  • リンカ内部のシンボルテーブルを再利用できる

LLVM レベル LTO

オブジェクトファイルではなく,LLVMビットコードを入力ファイルとして受け付ける.

inline


LLVM レベル LTO

特徴

  • 抽象度の高い最適化
  • LLVMの最適化パスを再利用

例えば

// LibX.swift
public func unusedPublicFunc() {}
public func publicFunc() {}

// main.swift

import LibX

publicFunc()

[.code-highlight: all] [.code-highlight: 6-9, 15]

// LibX.ll
define swiftcc void @"$s4LibX16unusedPublicFuncyyF"() #0 {
entry:
  ret void
}
define swiftcc void @"$s4LibX10publicFuncyyF"() #0 {
entry:
  ret void
}

// main.ll
define i32 @main(i32 %0, i8** %1) #0 {
entry:
  %2 = bitcast i8** %1 to i8*
  call swiftcc void @"$s4LibX10publicFuncyyF"()
  ret i32 0
}

LLVM レベルだと難しい最適化

  • 言語に依存したメタデータの取り扱い
  • 型パラメータのスペシャライズ
  • 関数テーブルに載った関数のDFE (Dead Function Elimination)

例えば

[.column]

// LibX.swift

public protocol P {
  func foo()
  func unusedMethod()
}

public struct S: P {
  public func foo() {}
  public func unusedMethod() {}
}

[.column]

// main.swift

import LibX

func useP<T: P>(_ value: T) {
  value.foo()
}
useP(S())

[.code-highlight: 2-6, 8-9] [.code-highlight: 12-20] [.code-highlight: 22-29]

// LibX.ll
@"$s4LibX1SVAA1PAAWP" = constant [3 x i8*] [
  ...,
  i8* bitcast (void (%T4LibX1SV*, %swift.type*, i8**)* @"$s4LibX1SVAA1PA2aDP3fooyyFTW" to i8*),
  i8* bitcast (void (%T4LibX1SV*, %swift.type*, i8**)* @"$s4LibX1SVAA1PA2aDP12unusedMethodyyFTW" to i8*)
], align 8

define linkonce_odr hidden swiftcc void @"$s4LibX1SVAA1PA2aDP3fooyyFTW"(...) { ... }
define linkonce_odr hidden swiftcc void @"$s4LibX1SVAA1PA2aDP12unusedMethodyyFTW"(...) { ... }

// main.ll
define i32 @main(i32 %0, i8** %1) #0 {
entry:
  ...
  call swiftcc void @"$s4main4usePyyx4LibX1PRzlF"(
    %swift.opaque* noalias nocapture undef,
    %swift.type* @"$s4LibX1SVN", i8** @"$s4LibX1SVAA1PAAWP"
  )
  ret i32 0
}

define hidden swiftcc void @"$s4main4usePyyx4LibX1PRzlF"(%swift.opaque* noalias nocapture %0, %swift.type* %T, i8** %T.P) {
entry:
  %1 = getelementptr inbounds i8*, i8** %T.P, i32 1
  %2 = load i8*, i8** %1, align 8, !invariant.load !14
  %3 = bitcast i8* %2 to void (%swift.opaque*, %swift.type*, i8**)*
  call swiftcc void %3(%swift.opaque* noalias nocapture swiftself %0, %swift.type* %T, i8** %T.P)
  ret void
}

SIL レベル LTO

inline


SIL レベル LTO

inline


SIL レベル LTO の モチベーション

  • LLVM IRより抽象度の高い最適化
  • Swiftのセマンティクスを維持したままLTOしたい
  • どうせ静的リンクするなら、ABI resiliencyを無視した最適化をしたい。
  • 実行時パフォーマンスの改善とバイナリサイズの縮小を期待

最適化ポイント (未実装)


1. Cross Module Devirtualization


inline

[.footer: https://speakerdeck.com/kateinoigakukun/konpairakaraniu-jie-kuswift-method-dispatch-1?slide=39]


inline

[.footer: https://speakerdeck.com/kateinoigakukun/konpairakaraniu-jie-kuswift-method-dispatch-1?slide=55]


inline


Cross Module Devirtualization

  • すべてのモジュールがLTO対象なら、メソッドがオーバーライドされているか必ず分かる

    • 実質final認定できる呼び出しが増える
  • ABI resiliencyのためのテーブル経由呼び出しを静的呼び出しにできる。


// LibX.swift

open class A {
  public func foo1() {}
  open func foo2() {}
}

public func invokeFoo1InModule(_ a: A) {
  // これは現状の最適化パスでdevirtできる
  a.foo1()
}

// main.swift

import LibX

func invokeFoo1(_ a: A) {
  // [LTO] 外部モジュールの関数だが、ABI resiliency無視でdevirtできる。
  a.foo1()
  // [LTO] 外部モジュールの関数だが、誰もoverrideしていないのでdevirtできる。
  a.foo2()
}

2. Cross Module Specialization


Cross Module Specialization

  • モジュールをまたいだスペシャライズ
  • ABI resiliencyを無視して、全てに@inlinable がついているイメージ
  • バイナリサイズの肥大化が心配

// LibX.swift
public protocol Animal {
    func bark()
}
public struct Cat: Animal {
    func bark() { }
}

// main.swift
import LibX

public callBark<T: Animal>(_ animal: T) {
    animal.bark()
}

3. Dead Table Elimination


Dead Table Elimination

  • 通常、publicなVTableやProtocol Witness Tableは常に出力される
  • LTOの場合、クロスモジュールで使われている場合だけ出力すればいい。
  • devirtとスペシャライズでテーブルへの参照が消えると、このパスがより効果的になる
  • 冒頭の例

4. Dead public Function Elimination


Dead public Function Elimination

  • 通常のDFEはinternalな関数が対象
  • LTOの場合、public関数も消せる
  • 実際にはDead Table Eliminationと同時にやる
  • main関数から依存する関数を幅優先探索でマークしていく

作業進捗

週報をフォーラムに書いてる https://forums.swift.org/t/gsoc-lto-support-progress-report/37149


LTOが特に嬉しい場面

inline


stdlibを丸ごと静的リンクするため、使っていない機能もバイナリに入ってしまう。 Hello, worldですら10MB。まさにLTOの出番

inline

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