Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Utilizing LLVM LTO for Swift

Utilizing LLVM LTO for Swift

わいわいswiftc #34 オンライン
https://iosdiscord.connpass.com/event/239673/

Yuta Saito

March 14, 2022
Tweet

More Decks by Yuta Saito

Other Decks in Programming

Transcript

  1. Swiftͷ࠷దԽύε • SIL Optimizer • Thin Cross Module Optimizer (a.k.a

    Swift LTO) • LLVM Optimizer • LLVM LTO/ThinLTO • ࠓ೔͸ίί 4
  2. SwiftͱLLVM LTOͷาΈ • 2020: LLVM LTOͷ༗ޮԽ by katei • 2021~:

    Hermetic seal at link by kubamracek • LLVM LTOͱSwiftͷ࿈ܞڧԽ 8
  3. LLVM LTOͰग़དྷΔ࠷దԽ DFEͱVFE͸αΠζʹΑ͘ޮ͘ ! • Dead Function Elimination (DFE) •

    Virtual Function Elimination (VFE) • Whole Program Devirtualization • Inlining • etc... 12
  4. ୯७ͳέʔε // LibX.swift public func unusedFunc() {} // ফͤΔ public

    func usedFunc() {} // main.swift import LibX usedFunc() 14
  5. ୯७ͳέʔε # 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 15
  6. ʮ࢖༻ʯ͕શͯݟ͑ΔϦϯέʔδ • 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); } 2 https://github.com/llvm/llvm-project/blob/62bcfcb5a588e5e844f8e4e42a2e4d15c907a746/llvm/include/llvm/IR/ GlobalValue.h#L369-L374 17
  7. DFEͰফͤͳ͍έʔε // 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() 22
  8. DFEͰফͤͳ͍έʔε $ 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 23
  9. ͓͞Β͍ɿ VTable class A { func foo() {} func bar()

    {} } class B : A { override func bar() {} } class C : B { override func foo() {} func fizz() {} } ಈతϙϦϞʔϑΟζϜΛ࣮ݱ ͢ΔͨΊͷσʔλߏ଄ Class Slot[0] Slot[1] Slot[2] A A.foo A.bar B A.foo B.bar C C.foo B.bar C.fizz 25
  10. VTable in Type Metadata ; 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 26
  11. VTable in Type Descriptor ; 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 • ؔ਺ϙΠϯλ͕૬ରϙΠϯ λͱͯ͠ຒΊࠐ·ΕͯΔ 27
  12. Virtual Function Elimination • 2019೥10݄ʹLLVMʹಋೖ3 • ݁ߏ࠷ۙ ! • VTableͷߏ଄ʹLLVMϝλσʔλΛ෇͚ͯɺ

    ࢖ΘΕ͍ͯͳ͍εϩοτͷϝιουΛ࡟আ • ΋ͱ΋ͱ͸C++޲͚ 3 https://reviews.llvm.org/D63932 28
  13. VTableϝλσʔλ૷০ͷྫ ʢItanium C++ ABIʣ • લఏ: γϯϘϧ͸hidden4 • ݺ͹ΕΔՄೳੑ͕͋Δͷ͸ B::fooͱA::bar͚ͩ

    Class Slot[0] Slot[1] A A::foo A::bar B B::foo A::bar 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); } 4 ίϚϯυ clang++ -cc1 -flto -flto-unit -fvirtual-function-elimination -fwhole-program-vtables -fvisibility hidden 29
  14. !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" } 30
  15. 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" } 31
  16. 32

  17. @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 } 33
  18. @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 } 34
  19. Virtual Function Elimination for Swift https://github.com/apple/swift/pull/39128 • -enable-llvm-vfe • VTableܦ༝ͷϝιουσΟεύονʹ

    @llvm.type.checked.loadΛ࢖͏Α͏ʹ • Type MetadataͱType DescriptorΛVTableɺ ϕʔεϝιουΛtypeidͱͯ͠!typeϝλσʔλΛ௥Ճ 37
  20. ద༻ͯ͠ΈΔ 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 40
  21. ; 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} 41
  22. ; 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} 42
  23. 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 } 43
  24. 44

  25. DFEͰফͤͳ͔ͬͨέʔεΛVFEʹ͔͚ͯΈΔ unusedFunc ফ͑ͯͨ ✌ $ 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 ... 45
  26. WMEͰফͤΔέʔε // 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() 47
  27. ; 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 } 48
  28. -experimental-hermetic-seal-at-link • Virtual Method EliminationɺWitness Method Eliminationɺ +α ͕༗ޮʹͳΔΦϓγϣϯ •

    ͜ͷΦϓγϣϯͰϏϧυ͞ΕͨϞδϡʔϧͷʮ࢖༻ʯ͸ ϦϯΫ࣌ʹશͯݟ͍͑ͯΔඞཁ͕͋Δɻ • Ϗϧυ͞ΕͨϞδϡʔϧ͸ɺ-experimental-hermetic- seal-at-linkΛ෇͚͔ͨ࣌͠importͰ͖ͳ͍ɻ 50
  29. ϦϯΫ • 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 · 53