theme: Next, 4 slidenumbers: true
- 前回の登壇は半年前 😲(2021年9月)
- 🆕 Swiftコミッタになった
- 🆕 Rubyコミッタにもなった
- SIL Optimizer
- Thin Cross Module Optimizer (a.k.a Swift LTO)
- LLVM Optimizer
- LLVM LTO/ThinLTO
- 今日はココ
- リンカの中で最適化
- コンパイラでは出来ない、翻訳単位を跨いだ最適化ができる
- 翻訳単位: 1オブジェクトファイルの生成元となるソース
- 2020: LLVM LTOの有効化 by katei
- 2021~: Hermetic seal at link by kubamracek
- LLVM LTOとSwiftの連携強化
どうしてLTOが必要なのか?(推定)
- どうやらFreestanding環境のサポートを 🍎 で進めている様子
- Freestanding: OS無しの環境(C、C++の用語らしい)1
- カーネルの中でSwiftが動く?
- OSが無いので、動的リンクができない
- stdlibも静的リンク
- サイズが肥大化して困った
- LTOならstdlibのサイズも減らせる!
DFEとVFEはサイズによく効く 💉
- Dead Function Elimination (DFE)
- Virtual Function Elimination (VFE)
- Whole Program Devirtualization
- Inlining
- etc...
- どこからも「使用」されていない関数を削除する
- 翻訳単位でも適用されてる
- 可視性によっては、リンク時に全ての「使用」が見えることが保証されるので、消せる可能性が増える
// LibX.swift
public func unusedFunc() {} // 🧹 消せる
public func usedFunc() {}
// main.swift
import LibX
usedFunc()
[.code-highlight: all] [.code-highlight: 5-6, 15]
# LTOなし
$ swiftc LibX.swift -emit-library -static -emit-module
$ swiftc main.swift -I. -L. -lLibX
$ nm main | swift demangle
0000000100003fa0 T LibX.unusedFunc() -> ()
0000000100003fa4 T LibX.usedFunc() -> ()
0000000100003fac s ___swift_reflection_version
0000000100000000 T __mh_execute_header
0000000100003f88 T _main
# LTOあり
$ swiftc LibX.swift -lto=llvm-thin -Xfrontend -internalize-at-link -emit-library -static -emit-module
$ swiftc main.swift -lto=llvm-thin -Xfrontend -internalize-at-link -I. -L. -lLibX
$ nm main | swift demangle
0000000100003fac T LibX.usedFunc() -> ()
0000000100003fb0 s ___swift_reflection_version
0000000100000000 T __mh_execute_header
0000000100003fa4 T _main
シンボルXが消せる条件
- 外部から見えるシンボルから、Xの「使用」に到達しない
- Xの「使用」が全て見えることが保証できる
linkonce
,internal
,private
,available_externally
2
/// Whether the definition of this global may be discarded if it is not used
/// in its compilation unit.
static bool isDiscardableIfUnused(LinkageTypes Linkage) {
return isLinkOnceLinkage(Linkage) || isLocalLinkage(Linkage) ||
isAvailableExternallyLinkage(Linkage);
}
linkonce
: Thunk関数など(シグネチャが同じなら使い回せる)
- もし外部で使われていても、使う側が出力するので、使われていない最適化単位では消してOK
internal
, private
: 同じLLVM module内でのみ使用可能
- だいたいSwiftのprivate関数
available_externally
: インライン化のために外部から持ち出された関数定義
- そもそもオブジェクトファイルに出力されないものなので、使われて無くて、最適化チャンスが無ければ消してOK
- LTO時に、ビットコード化されていない外側のオブジェクトファイルが要求するシンボルが分かる
- 外側のオブジェクトファイルが要求していなければ、
internal
にできる。
// LibX.swift
public class A {
public func unusedFunc() {} // 消せない
public func usedFunc() {}
public init() {}
}
public class B : A {
override func usedFunc() {}
}
// main.swift
import LibX
let a: A = B()
a.usedFunc()
[.code-highlight: all] [.code-highlight: 4-5]
$ swiftc -lto=llvm-thin -Xfrontend -internalize-at-link -emit-library -static -emit-module LibX.swift
$ swiftc -lto=llvm-thin -Xfrontend -internalize-at-link main.swift -I. -L. -lLibX
$ nm main | swift demangle
0000000100003eac t LibX.A.unusedFunc() -> ()
0000000100003eb0 t LibX.A.usedFunc() -> ()
0000000100003eb4 T LibX.A.__allocating_init() -> LibX.A
0000000100003ec4 T LibX.A.init() -> LibX.A
どうして消せない?
- Type DescriptorとType MetadataのVTableから参照されてるから
[.column]
class A {
func foo() {}
func bar() {}
}
class B : A {
override func bar() {}
}
class C : B {
override func foo() {}
func fizz() {}
}
[.column]
動的ポリモーフィズムを実現するためのデータ構造
Class | Slot[0] | Slot[1] | Slot[2] |
---|---|---|---|
A | A.foo | A.bar | |
B | A.foo | B.bar | |
C | C.foo | B.bar | C.fizz |
VTable in Type Metadata
[.code-highlight: all] [.code-highlight: 21-24]
; full type metadata for LibX.A
@"$s4LibX1ACMf" = internal global <{ ... }> <{
; A.__deallocating_deinit
void (%T4LibX1AC*)* @"$s4LibX1ACfD",
; value witness table for Builtin.NativeObject
i8** @"$sBoWV",
; MetadataKind::Class
i64 0,
; superclass
%swift.type* null,
; ClassFlags::UsesSwiftRefcounting, InstanceAddressPoint
i32 2, i32 0,
; InstanceSize, InstanceAlignMask, RuntimeReservedBits
i32 16, i16 7, i16 0,
; ClassSize, ClassAddressPoint
i32 96, i32 16,
; nominal type descriptor for LibX.A
<{ ... }>* @"$s4LibX1ACMn",
; IVarDestroyer
i8* null,
; VTable[0]: LibX.A.unusedFunc() -> ()
void (%T4LibX1AC*)* @"$s4LibX1AC10unusedFuncyyF",
; VTable[1]: LibX.A.usedFunc() -> ()
void (%T4LibX1AC*)* @"$s4LibX1AC8usedFuncyyF",
; VTable[2]: LibX.A.__allocating_init() -> LibX.A
%T4LibX1AC* (%swift.type*)* @"$s4LibX1ACACycfC"
}>, align 8
VTable in Type Descriptor
[.column] [.code-highlight: all] [.code-highlight: 21-28]
; nominal type descriptor for LibX.A
@"$s4LibX1ACMn" = constant <{ ... }> <{
; ContextDescriptorFlags
i32 -2147483568,
; Parent Descriptor: module descriptor LibX
i32 cast_relptr <{ ... }> @"$s4LibXMXM",
; Name: "A\00"
i32 cast_relptr [2 x i8] @.str.1,
; type metadata accessor for LibX.A
i32 cast_relptr %swift.metadata_response (i64)* @"$s4LibX1ACMa",
; reflection metadata field descriptor LibX.A
i32 cast_relptr { i32, i32, i16, i16, i32 }* @"$s4LibX1ACMF",
; SuperclassType, MetadataNegativeSizeInWords
i32 0, i32 2,
; MetadataPositiveSizeInWords, NumImmediateMembers
i32 10, i32 3,
; NumFields, FieldOffsetVectorOffset
i32 0, i32 7,
; VTable Offset, VTable Size
i32 7, i32 3,
; VTable
%swift.method_descriptor {
; Kind::Method, LibX.A.unusedFunc() -> ()
i32 16, i32 cast_relptr void (%T4LibX1AC*)* @"$s4LibX1AC10unusedFuncyyF",
},
%swift.method_descriptor {
; Kind::Method, LibX.A.usedFunc() -> ()
i32 16, i32 cast_relptr void (%T4LibX1AC*)* @"$s4LibX1AC8usedFuncyyF",
},
%swift.method_descriptor {
; Kind::Init, LibX.A.__allocating_init() -> LibX.A
i32 1, i32 cast_relptr void (%T4LibX1AC*)* @"$s4LibX1ACACycfC",
}
}>, section "__TEXT,__const", align 4
[.column]
- 関数ポインタが相対ポインタとして埋め込まれてる
-
2019年10月にLLVMに導入3
- 結構最近 😲
-
VTableの構造にLLVMメタデータを付けて、 使われていないスロットのメソッドを削除
-
もともとはC++向け
[.column]
- 前提: シンボルはhidden4
- 呼ばれる可能性があるのは B::fooとA::barだけ
Class | Slot[0] | Slot[1] |
---|---|---|
A | A::foo | A::bar |
B | B::foo | A::bar |
[.column]
struct A {
A() = default;
virtual int foo(int);
virtual int bar(float);
};
struct B : A {
B() = default;
virtual int foo(int);
};
int A::foo(int) { return 1; }
int A::bar(float) { return 2; }
int B::foo(int) { return 3; }
extern "C" int test(B *p) {
return p->foo(42);
}
extern "C" int test2(A *p) {
return p->bar(24);
}
!type
は互換なVTableを表現
; vtable for A
@_ZTV1A = dso_local unnamed_addr constant { [4 x i8*] } { [4 x i8*] [
; [ 0]
i8* null,
; [ 8] typeinfo for A
i8* bitcast ({ i8*, i8* }* @_ZTI1A to i8*),
; [16] A::foo(int)
i8* bitcast (i32 (%struct.A*, i32)* @_ZN1A3fooEi to i8*),
; [24] A::bar(float)
i8* bitcast (i32 (%struct.A*, float)* @_ZN1A3barEf to i8*)
] }, align 8, !type !0
; { vtable offset, typeid }
!0 = !{i64 16, !"_ZTS1A" }
BのVTableはAとBのVTableと互換
; vtable for B
@_ZTV1B = dso_local unnamed_addr constant { [4 x i8*] } { [4 x i8*] [
; [ 0]
i8* null,
; [ 8] typeinfo for B
i8* bitcast ({ i8*, i8*, i8* }* @_ZTI1B to i8*),
; [16] B::foo(int)
i8* bitcast (i32 (%struct.B*, i32)* @_ZN1B3fooEi to i8*),
; [24] A::bar(float)
i8* bitcast (i32 (%struct.A*, float)* @_ZN1A3barEf to i8*)
] }, align 8, !type !0, !type !1
; { vtable offset, typeid }
!0 = !{i64 16, !"_ZTS1A" }
!1 = !{i64 16, !"_ZTS1B" }
[.text: text-scale(0.8)]
@llvm.type.checked.load(i8* %vtbl, i32 0, metadata !"_ZTS1B")
でB互換VTableのオフセット16 + 0のスロット(foo)をロード
define hidden i32 @test(%struct.B* %p) #0 {
entry:
%p.addr = alloca %struct.B*, align 8
store %struct.B* %p, %struct.B** %p.addr, align 8
%0 = load %struct.B*, %struct.B** %p.addr, align 8
%1 = bitcast %struct.B* %0 to i32 (%struct.B*, i32)***
%vtable = load i32 (%struct.B*, i32)**, i32 (%struct.B*, i32)*** %1, align 8
%2 = bitcast i32 (%struct.B*, i32)** %vtable to i8*
%3 = call { i8*, i1 } @llvm.type.checked.load(i8* %2, i32 0, metadata !"_ZTS1B")
%4 = extractvalue { i8*, i1 } %3, 1
%5 = extractvalue { i8*, i1 } %3, 0
%6 = bitcast i8* %5 to i32 (%struct.B*, i32)*
%call = call i32 %6(%struct.B* nonnull dereferenceable(8) %0, i32 42)
ret i32 %call
}
[.text: text-scale(0.8)]
@llvm.type.checked.load(i8* %vtbl, i32 0, metadata !"_ZTS1B")
でA互換VTableのオフセット16 + 8のスロット(bar)をロード
define hidden i32 @test2(%struct.B* %p) #0 {
entry:
%p.addr = alloca %struct.B*, align 8
store %struct.B* %p, %struct.B** %p.addr, align 8
%0 = load %struct.B*, %struct.B** %p.addr, align 8
%1 = bitcast %struct.B* %0 to %struct.A*
%2 = bitcast %struct.A* %1 to i32 (%struct.A*, float)***
%vtable = load i32 (%struct.A*, float)**, i32 (%struct.A*, float)*** %2, align 8
%3 = bitcast i32 (%struct.A*, float)** %vtable to i8*
%4 = call { i8*, i1 } @llvm.type.checked.load(i8* %3, i32 8, metadata !"_ZTS1A")
%5 = extractvalue { i8*, i1 } %4, 1
%6 = extractvalue { i8*, i1 } %4, 0
%7 = bitcast i8* %6 to i32 (%struct.A*, float)*
%call = call i32 %7(%struct.A* nonnull dereferenceable(8) %1, float 2.400000e+01)
ret i32 %call
}
[.column]
- 呼び出しに使われうるVTableとそのスロットが静的に分かる
- 使われないVTableのスロットをnullptrに置換できる
- 今回は②と③だけが使われてるので、
A::foo
が消せる
[.column]
Swiftの関数テーブルにLLVMメタデータを与えれば、C++と同様にテーブルからの参照を消せる
- VFE: Virtual Function Elimination
- WME: Witness Method Elimination
-enable-llvm-vfe
- VTable経由のメソッドディスパッチに
@llvm.type.checked.load
を使うように - Type MetadataとType DescriptorをVTable、
ベースメソッドをtypeidとして
!type
メタデータを追加
VTableのエントリとして相対ポインタをサポート
アドホックに相対ポインタのパターンを解釈
@symbol = ... {
i32 trunc (i64 sub (i64 ptrtoint (<type> @target to i64), i64 ptrtoint (... @symbol to i64)) to i32)
}
VTableの関数エントリの範囲を指定できる
!vcall_visibility
拡張
- https://reviews.llvm.org/D108741
- SwiftのType Descriptorにはメタデータアクセサなど、VFEで消しちゃいけない関数が入っているため
- C++のVTableは他のメタデータから独立したテーブルで、入っている関数ポインタは全てVFEで消せた
class A {
func unusedFunc() {}
func usedFunc() {}
init() {}
}
class B : A {
override func usedFunc() {}
}
func test() {
let a: A = B()
a.usedFunc()
}
$ swiftc -emit-ir LibX.swift \
-Xfrontend -disable-objc-interop \
-Xfrontend -enable-llvm-vfe
; nominal type descriptor for LibX.A
@"$s4LibX1ACMn" = constant <{ ... }> <{
; ...
; VTable
%swift.method_descriptor {
; [52] Kind::Method, [56] LibX.A.unusedFunc() -> ()
i32 16, i32 cast_relptr void (%T4LibX1AC*)* @"$s4LibX1AC10unusedFuncyyF",
},
%swift.method_descriptor {
; [60] Kind::Method, [64] LibX.A.usedFunc() -> ()
i32 16, i32 cast_relptr void (%T4LibX1AC*)* @"$s4LibX1AC8usedFuncyyF",
},
%swift.method_descriptor {
; [68] Kind::Init, [72] LibX.A.__allocating_init() -> LibX.A
i32 1, i32 cast_relptr void (%T4LibX1AC*)* @"$s4LibX1ACACycfC",
}
}>, section "__TEXT,__const", align 4, !type !0, !type !1, !type !2, !vcall_visibility !3
; method descriptor for LibX.A.unusedFunc() -> ()
!0 = !{i64 56, !"$s4LibX1AC10unusedFuncyyFTq"}
; method descriptor for LibX.A.usedFunc() -> ()
!1 = !{i64 64, !"$s4LibX1AC8usedFuncyyFTq"}
; method descriptor for LibX.A.__allocating_init() -> LibX.A
!2 = !{i64 72, !"$s4LibX1ACACycfCTq"}
; { VCallVisibilityPublic, rangeStart, rangeEnd }
!3 = !{i64 0, i64 56, i64 76}
; full type metadata for LibX.A
@"$s4LibX1ACMf" = internal global <{ ... }> <{
; ...
; [56] nominal type descriptor for LibX.A
<{ ... }>* @"$s4LibX1ACMn",
; [64] IVarDestroyer
i8* null,
; [72] VTable[0]: LibX.A.unusedFunc() -> ()
void (%T4LibX1AC*)* @"$s4LibX1AC10unusedFuncyyF",
; [80] VTable[1]: LibX.A.usedFunc() -> ()
void (%T4LibX1AC*)* @"$s4LibX1AC8usedFuncyyF",
; [88] VTable[2]: LibX.A.__allocating_init() -> LibX.A
%T4LibX1AC* (%swift.type*)* @"$s4LibX1ACACycfC"
}>, align 8, !type !5, !type !6, !type !7, !vcall_visibility !8
; method descriptor for LibX.A.unusedFunc() -> ()
!5 = !{i64 72, !"$s4LibX1AC10unusedFuncyyFTq"}
; method descriptor for LibX.A.usedFunc() -> ()
!6 = !{i64 80, !"$s4LibX1AC8usedFuncyyFTq"}
; method descriptor for LibX.A.__allocating_init() -> LibX.A
!7 = !{i64 88, !"$s4LibX1ACACycfCTq"}
; { VCallVisibilityPublic, rangeStart, rangeEnd }
!8 = !{i64 0, i64 72, i64 92}
[.text: text-scale(0.7)]
typeid=$s4LibX1AC8usedFuncyyFTq
のテーブルのオフセット0のスロットをロード
(オフセット0は固定)
define hidden swiftcc void @"$s4LibX4testyyF"() #0 {
entry:
%a.debug = alloca %T4LibX1AC*, align 8
%0 = bitcast %T4LibX1AC** %a.debug to i8*
call void @llvm.memset.p0i8.i64(i8* align 8 %0, i8 0, i64 8, i1 false)
%1 = call swiftcc %swift.metadata_response @"$s4LibX1BCMa"(i64 0) #8
%2 = extractvalue %swift.metadata_response %1, 0
%3 = call swiftcc %T4LibX1BC* @"$s4LibX1BCACycfC"(%swift.type* swiftself %2)
%4 = bitcast %T4LibX1BC* %3 to %T4LibX1AC*
store %T4LibX1AC* %4, %T4LibX1AC** %a.debug, align 8
%5 = getelementptr inbounds %T4LibX1AC, %T4LibX1AC* %4, i32 0, i32 0, i32 0
%6 = load %swift.type*, %swift.type** %5, align 8
%7 = bitcast %swift.type* %6 to void (%T4LibX1AC*)**
%8 = getelementptr inbounds void (%T4LibX1AC*)*, void (%T4LibX1AC*)** %7, i64 8
%9 = bitcast void (%T4LibX1AC*)** %8 to i8*
; method descriptor for LibX.A.usedFunc() -> ()
%10 = call { i8*, i1 } @llvm.type.checked.load(i8* %9, i32 0, metadata !"$s4LibX1AC8usedFuncyyFTq")
%11 = extractvalue { i8*, i1 } %10, 0
%12 = bitcast i8* %11 to void (%T4LibX1AC*)*
call swiftcc void %12(%T4LibX1AC* swiftself %4)
call void bitcast (void (%swift.refcounted*)* @swift_release to void (%T4LibX1AC*)*)(%T4LibX1AC* %4) #2
ret void
}
unusedFunc
消えてた ✌️
[.code-highlight: all] [.code-highlight: 10-15]
$ swiftc -lto=llvm-full \
-Xfrontend -internalize-at-link \
-Xfrontend -enable-llvm-vfe \
-emit-library -static -emit-module LibX.swift
$ swiftc -lto=llvm-full \
-Xfrontend -internalize-at-link \
-Xfrontend -enable-llvm-vfe \
-I. -L. -lLibX main.swift
$ nm main | swift demangle
0000000100003ed4 t LibX.A.usedFunc() -> ()
0000000100003ed8 t LibX.A.__allocating_init() -> LibX.A
0000000100003f9c s reflection metadata field descriptor LibX.A
0000000100003eb8 t type metadata accessor for LibX.A
...
-enable-llvm-wme
- WitnessテーブルのエントリもVTableと同様にマーキング
- Witness Methodをtypeidとする
// LibX.swift
public protocol TheProtocol {
func unusedFunc()
func usedFunc()
}
public struct A : TheProtocol {
public func unusedFunc() {} // 消える 🧹
public func usedFunc() {}
public init() {}
}
// main.swift
import LibX
let a: TheProtocol = A()
// @llvm.type.checked.load(
// i8* %usedFuncSlot, i32 0,
// ; method descriptor for LibX.TheProtocol.usedFunc() -> ()
// metadata !"$s4LibX11TheProtocolP8usedFuncyyFTq"
// )
a.usedFunc()
; protocol witness table for LibX.A : LibX.TheProtocol in LibX
@"$s4LibX1AVAA11TheProtocolAAWP" = constant [3 x i8*] [
; [ 0] protocol conformance descriptor for LibX.A : LibX.TheProtocol in LibX
i8* bitcast (%swift.protocol_conformance_descriptor* @"$s4LibX1AVAA11TheProtocolAAMc" to i8*),
; [ 8] protocol witness for LibX.TheProtocol.unusedFunc() -> () in conformance LibX.A : LibX.TheProtocol in LibX
i8* bitcast (void (%T4LibX1AV*, %swift.type*, i8**)* @"$s4LibX1AVAA11TheProtocolA2aDP10unusedFuncyyFTW" to i8*),
; [16] protocol witness for LibX.TheProtocol.usedFunc() -> () in conformance LibX.A : LibX.TheProtocol in LibX
i8* bitcast (void (%T4LibX1AV*, %swift.type*, i8**)* @"$s4LibX1AVAA11TheProtocolA2aDP8usedFuncyyFTW" to i8*)
], align 8, !type !0, !type !1, !vcall_visibility !2, !typed_global_not_for_cfi !3
; method descriptor for LibX.TheProtocol.unusedFunc() -> ()
!0 = !{i64 8, !"$s4LibX11TheProtocolP10unusedFuncyyFTq"}
; method descriptor for LibX.TheProtocol.usedFunc() -> ()
!1 = !{i64 16, !"$s4LibX11TheProtocolP8usedFuncyyFTq"}
; { VCallVisibilityLinkageUnit, rangeStart, rangeEnd }
!2 = !{i64 1, i64 8, i64 20 }
最適化 | 消せる対象 |
---|---|
DFE | 関数, static関数, finalメソッド |
VFE | クラスのメソッド |
WME | プロトコルのメソッド |
- Virtual Method Elimination、Witness Method Elimination、+α が有効になるオプション
- このオプションでビルドされたモジュールの「使用」は
リンク時に全て見えている必要がある。
- ビルドされたモジュールは、
-experimental-hermetic-seal-at-link
を付けた時しかimportできない。
- ビルドされたモジュールは、
SwiftyJSONで計測
(参考値)Swift LTOのベンチマーク(当時) for SwiftyJSON
- Add a 'standalone_minimal' preset to build a minimal, static, OS independent, self-contained binaries of stdlib. by kubamracek · Pull Request #33286 · apple/swift
- Implement LLVM IR Virtual Function Elimination for Swift classes. by kubamracek · Pull Request #39128 · apple/swift
- Implement LLVM IR Witness Method Elimination for Swift witness tables. by kubamracek · Pull Request #39287 · apple/swift
- Implement conditional stripping of type descriptors, protocols and protocol conformances via !llvm.used.conditional by kubamracek · Pull Request #39313 · apple/swift
Footnotes
-
https://github.com/llvm/llvm-project/blob/62bcfcb5a588e5e844f8e4e42a2e4d15c907a746/llvm/include/llvm/IR/GlobalValue.h#L369-L374 ↩
-
コマンド clang++ -cc1 -flto -flto-unit -fvirtual-function-elimination -fwhole-program-vtables -fvisibility hidden ↩