SwiftのThin Cross Module Optimization (WIP)

https://iosdiscord.connpass.com/event/188624/

1. SwiftͷThin Cross Module Optimization (WIP) Θ͍Θ͍swiftc #22 @kateinoigakukun 1
2. GSoC (Google Summer of Code) https://summerofcode.withgoogle.com • Google͕ೝఆͨ͠ΦʔϓϯιʔεͷϓϩδΣΫτʹࢀՃ͢Δ ͱGoogle͔ΒใुΛ΋Β͑Δɺֶੜ޲͚Πϕϯτ • Swift΋ࢀՃ͍ͯ͠Δ 2
3. https://summerofcode.withgoogle.com/projects/#6691362033893376 3
4. ݱࡏͷεςʔλε • GSoCظ͕ؒऴΘͬͨ • ࣗ෼ͷϒϥϯνͰͷ࡞ۀ͸େମऴΘ͍ͬͯΔ • Ϛʔδ͞Ε͍ͯͳ͍PR͕ͨ͘͞Μ࢒͍ͬͯΔͷͰϨϏϡΞʔ Λ୳ͯ͠ఆظతʹಥ෇͍ͯΔ 4
5. ౰ॳͷܭը libLTO.dylibతͳϦϯΧϓϥάΠϯΛ࡞Δ༧ఆͩͬͨɻ $ clang -flto file1.c file2.c -c $ ls file1.c file1.o file2.c file2.o $ file file1.o file1.o: LLVM bitcode, wrapper x86_64 $ ld file1.o file2.o -lto_library path/to/libLTO.dylib 5
8. ͜ͷΞʔΩςΫνϟͷ໰୊఺ ϦϯΧ͕SIBશମΛಡΜͰղੳ͢Δ͜ͱʹͳΔͷͰɺ࠷దԽ࣌ؒ తʹεέʔϥϒϧͰͳ͍ -> LLVM ͷLTOͰ΋Ҏલಉ༷ͷ໰୊͕͋ͬͨɻ 8
9. http://llvm.org/devmtg/2016-11/Slides/Amini-Johnson-ThinLTO.pdf 9
10. http://llvm.org/devmtg/2016-11/Slides/Amini-Johnson-ThinLTO.pdf 10
11. LLVM Thin LTO • Bitcode͔Βͷίʔυੜ੒ΛฒྻԽͰ͖Δ • αϚϦʔΛૢ࡞͢ΔThin Link͸௚ྻʹͳΔ͕ɺLLVM໋ྩΛ ղੳ͠ͳ͍ͷͰ͍ܰ 11
12. LLVM Thin LTOϞσϧΛࢀߟʹ৽͍͠ύΠϓϥΠϯΛ࣮૷ͯ͠Έ ͨɻ • SwiftϞδϡʔϧͷαϚϦΛग़ྗ • ΫϩεϞδϡʔϧͰղੳ͢Δͱ͖SIBΛશͯύʔε͢Δඞཁ͕ ແ͘ͳΔ 12
15. ࣮ࡍͷίϚϯυ 15
16. Compile Module A $ swift-frontend A1.swift A2.swift \ -whole-module-optimization \ -emit-module -emit-module-summary -emit-sib \ -o A.swiftmodule ग़ྗ: A.swiftmodule, A.swiftmodulesummary, A.sib 16
17. Compile Module B $ swift-frontend B1.swift B2.swift \ -whole-module-optimization \ -emit-module -emit-module-summary -emit-sib \ -I. \ -o B.swiftmodule ग़ྗ: B.swiftmodule, B.swiftmodulesummary, B.sib 17
18. Merge Module Summary ௚ྻϙΠϯτ $ swift-frontend -merge-module-summary \ A.swiftmodulesummary B.swiftmodulesummary \ -o merged-module.swiftmodulesummary 18
19. CodeGen ͜͜͸ฒྻʹͰ͖Δ $ swift-frontend -emit-object A.sib -o A.o \ -module-summary-path merged-module.swiftmodulesummary $ swift-frontend -emit-object B.sib -o B.o \ -module-summary-path merged-module.swiftmodulesummary 19
20. Swift Module Summary SILModuleΛཁ໿ͨ͠ΦϒδΣΫτɻ • ؔ਺ͷίʔϧάϥϑ • ؔ਺ςʔϒϧͷந৅ͱ࣮૷ͷରԠؔ܎ Λ࣋ͭ 20
21. ྫ func myPrint(_ text: String) { ... } public protocol Animal { func bark() } public struct Cat: Animal { public func bark() { myPrint("mew") } } public struct Dog: Animal { public func bark() { myPrint("bow")} } public func callBark<T: Animal>(_ animal: T) { animal.bark() } 21
22. ϚʔδͷλΠϛϯάͰ΍͍ͬͯΔ͜ͱ 1. swiftmodulesummaryΛҰͭͷαϚϦʔΦϒδΣΫτʹϩʔ υͯ͠ϦϯΫ 2. PreservedͳγϯϘϧΛऩू 3. PreservedͳγϯϘϧ͔Βḷ࣮ͬͯߦ࣌ࢀরՄೳͳܕΛϚʔΫ 4. PreservedͳγϯϘϧ͔Β౸ୡՄೳͳؔ਺Λliveͱͯ͠ϚʔΫ ͯ͠౸ୡෆೳͳؔ਺Λચ͍ग़͢ 22
23. ౸ୡෆೳͳؔ਺Λચ͍ग़͢ void markDeadSymbols(ModuleSummaryIndex &summary, llvm::DenseSet<GUID> &PreservedGUIDs) { SmallVector<GUID, 8> Worklist; for (auto GUID : PreservedGUIDs) { Worklist.push_back(GUID); } while (!Worklist.empty()) { auto GUID = Worklist.pop_back_val(); auto Func = summary.getFunction(GUID); if (Func->isLive()) continue; Func->setLive(true); for (auto Call : Func->calls()) { switch (Call.getKind()) { case EdgeTy::Kind::Static: { Worklist.push_back(Call.getCallee()); continue; } case EdgeTy::Kind::Witness: case EdgeTy::Kind::VTable: { auto Impls = summary.getImplementations(Call); for (auto Impl : Impls) { Worklist.push_back(Impl); } break; } } } } 23
24. ౸ୡෆೳͳؔ਺Λચ͍ग़͢ void markDeadSymbols(ModuleSummaryIndex &summary, llvm::DenseSet<GUID> &PreservedGUIDs) { SmallVector<GUID, 8> Worklist; for (auto GUID : PreservedGUIDs) { Worklist.push_back(GUID); } while (!Worklist.empty()) { auto GUID = Worklist.pop_back_val(); auto Func = summary.getFunction(GUID); if (Func->isLive()) continue; Func->setLive(true); for (auto Call : Func->calls()) { switch (Call.getKind()) { case EdgeTy::Kind::Static: { Worklist.push_back(Call.getCallee()); continue; } case EdgeTy::Kind::Witness: case EdgeTy::Kind::VTable: { auto Impls = summary.getImplementations(Call); for (auto Impl : Impls) { Worklist.push_back(Impl); } break; } } } } 23
25. ౸ୡෆೳͳؔ਺Λચ͍ग़͢ void markDeadSymbols(ModuleSummaryIndex &summary, llvm::DenseSet<GUID> &PreservedGUIDs) { SmallVector<GUID, 8> Worklist; for (auto GUID : PreservedGUIDs) { Worklist.push_back(GUID); } while (!Worklist.empty()) { auto GUID = Worklist.pop_back_val(); auto Func = summary.getFunction(GUID); if (Func->isLive()) continue; Func->setLive(true); for (auto Call : Func->calls()) { switch (Call.getKind()) { case EdgeTy::Kind::Static: { Worklist.push_back(Call.getCallee()); continue; } case EdgeTy::Kind::Witness: case EdgeTy::Kind::VTable: { auto Impls = summary.getImplementations(Call); for (auto Impl : Impls) { Worklist.push_back(Impl); } break; } } } } 23
26. ౸ୡෆೳͳؔ਺Λચ͍ग़͢ void markDeadSymbols(ModuleSummaryIndex &summary, llvm::DenseSet<GUID> &PreservedGUIDs) { SmallVector<GUID, 8> Worklist; for (auto GUID : PreservedGUIDs) { Worklist.push_back(GUID); } while (!Worklist.empty()) { auto GUID = Worklist.pop_back_val(); auto Func = summary.getFunction(GUID); if (Func->isLive()) continue; Func->setLive(true); for (auto Call : Func->calls()) { switch (Call.getKind()) { case EdgeTy::Kind::Static: { Worklist.push_back(Call.getCallee()); continue; } case EdgeTy::Kind::Witness: case EdgeTy::Kind::VTable: { auto Impls = summary.getImplementations(Call); for (auto Impl : Impls) { Worklist.push_back(Impl); } break; } } } } 23
27. ౸ୡෆೳͳؔ਺Λચ͍ग़͢ void markDeadSymbols(ModuleSummaryIndex &summary, llvm::DenseSet<GUID> &PreservedGUIDs) { SmallVector<GUID, 8> Worklist; for (auto GUID : PreservedGUIDs) { Worklist.push_back(GUID); } while (!Worklist.empty()) { auto GUID = Worklist.pop_back_val(); auto Func = summary.getFunction(GUID); if (Func->isLive()) continue; Func->setLive(true); for (auto Call : Func->calls()) { switch (Call.getKind()) { case EdgeTy::Kind::Static: { Worklist.push_back(Call.getCallee()); continue; } case EdgeTy::Kind::Witness: case EdgeTy::Kind::VTable: { auto Impls = summary.getImplementations(Call); for (auto Impl : Impls) { Worklist.push_back(Impl); } break; } } } } 23
28. ౸ୡෆೳͳؔ਺Λચ͍ग़͢ void markDeadSymbols(ModuleSummaryIndex &summary, llvm::DenseSet<GUID> &PreservedGUIDs) { SmallVector<GUID, 8> Worklist; for (auto GUID : PreservedGUIDs) { Worklist.push_back(GUID); } while (!Worklist.empty()) { auto GUID = Worklist.pop_back_val(); auto Func = summary.getFunction(GUID); if (Func->isLive()) continue; Func->setLive(true); for (auto Call : Func->calls()) { switch (Call.getKind()) { case EdgeTy::Kind::Static: { Worklist.push_back(Call.getCallee()); continue; } case EdgeTy::Kind::Witness: case EdgeTy::Kind::VTable: { auto Impls = summary.getImplementations(Call); for (auto Impl : Impls) { Worklist.push_back(Impl); } break; } } } } 23
29. void markDeadSymbols(ModuleSummaryIndex &summary, llvm::DenseSet<GUID> &PreservedGUIDs) { ... for (auto Call : Func->calls()) { switch (Call.getKind()) { case EdgeTy::Kind::Static: { Worklist.push_back(Call.getCallee()); continue; } case EdgeTy::Kind::Witness: case EdgeTy::Kind::VTable: { auto Impls = summary.getImplementations(Call); for (auto Impl : Impls) { Worklist.push_back(Impl); } break; } } ... } 24
30. void markDeadSymbols(ModuleSummaryIndex &summary, llvm::DenseSet<GUID> &PreservedGUIDs) { ... for (auto Call : Func->calls()) { switch (Call.getKind()) { case EdgeTy::Kind::Static: { Worklist.push_back(Call.getCallee()); continue; } case EdgeTy::Kind::Witness: case EdgeTy::Kind::VTable: { auto Impls = summary.getImplementations(Call); for (auto Impl : Impls) { Worklist.push_back(Impl); } break; } } ... } 24
31. ܕ͕࢖ΘΕ͍ͯͳ͚Ε͹ςʔϒϧܦ༝Ͱϝιου͕ݺ͹ΕΔ͜ ͱ΋ͳ͍ͷͰফͤΔ void markDeadSymbols(ModuleSummaryIndex &summary, llvm::DenseSet<GUID> &PreservedGUIDs) { ... for (auto Call : Func->calls()) { switch (Call.getKind()) { case EdgeTy::Kind::Static: { Worklist.push_back(Call.getCallee()); continue; } case EdgeTy::Kind::Witness: case EdgeTy::Kind::VTable: { auto Impls = summary.getImplementations(Call); for (auto Impl : Impls) { if (UsedTypes.find(Impl.Type) == UsedTypes.end()) { continue; } Worklist.push_back(Impl); } break; } } ... } 25
32. ϕϯνϚʔΫ https://github.com/kateinoigakukun/swift-lto-benchmark 26
33. Stdlib ର৅ίʔυ: https:// github.com/kateinoigakukun/ swift-lto-benchmark/blob/ master/Example/ SwiftStdlibExample.swift let alphabet = "abcdefghijklmnopqrstuvwxyz" /// All edits that are one edit away from `word` func edits(_ word: String) -> Set<String> { let splits = word.indices.map { (String(word[..<$0]), String(word[$0...])) } var result: Array<String> = [] for (left, right) in splits { // drop a character result.append(left + right.dropFirst()) // transpose two characters if let fst = right.first { let drop1 = right.dropFirst() if let snd = drop1.first { result.append(left + [snd,fst] + drop1.dropFirst()) } } // replace each character with another for letter in alphabet { result.append(left + [letter] + right.dropFirst()) } // insert rogue characters for letter in alphabet { result.append(left + [letter] + right) } } // have to map back to strings right at the end return Set(result) } 27
34. όΠφϦαΠζ 28
35. Ϗϧυ࣌ؒ 29
36. • 60%ऑͷόΠφϦαΠζ࡟ݮ • SIL -> IRͷม׵ύε͕ߴίετͳͷͰɺ߱Լͤ͞Δؔ਺͕ ݮͬͨ͜ͱʹΑͬͯίϯύΠϧ࣌ؒ΋ݮগ͍ͯ͠Δɻ 30
37. Ϗϧυ࣌ؒͷ಺༁ ninjatracing ͱ͍͏πʔϧͰninjaͷϏϧυϩά͔ΒϏϧυ࣌ ؒΛChromeͰϏδϡΞϥΠζͰ͖ΔϑΥʔϚοτʹม׵Ͱ͖ Δ https://github.com/nico/ninjatracing 31
39. ফͤͳ͍ؔ਺ͷղੳ ཧ૝తʹ͸ফ͍͕ͨ͠liveϚʔΫ͕෇͍ͯ͠·͍ͬͯΔؔ਺͕ ࢒͍ͬͯΔͷͰղੳ͍ͨ͠ɻ ղੳͷΞΠσΟΞ • ίʔϧάϥϑΛϏδϡΞϥΠζͯ͠ΈΔ • ίʔϧάϥϑ͔Βࢧ഑໦(Dominator Tree)Λߏஙͯ͠େ͖ͳ ؔ਺ΛҾ͖࿈Εͯ͘ΔݪҼΛݟ͚ͭΔ 33
40. ίʔϧάϥϑΛϏδϡΞϥΠζͯ͠ΈΔ ΍ͬͯΈͨɻ 34
42. ਓ͕ؒݟΒΕΔάϥϑ͡Όͳ͔ͬͨ 36
43. Dominator Tree (ࢧ഑໦) • ίϯύΠϥͷϑϩʔղੳʹΑ͘࢖ΘΕΔ • ༗޲άϥϑʹରͯ͠ߏஙͰ͖Δ໦ߏ଄ • ͋Δϊʔυʹ౸ୡ͢ΔͨΊʹඞͣ௨ΔҰ൪͍ۙϊʔυΛ਌ʹ ͱΔߏ଄ 37
44. ྫ ݩͷ༗޲άϥϑ ࢧ഑໦ 1 2 3 4 5 6 https://en.wikipedia.org/wiki/Dominator(graphtheory) 38
45. Dominator TreeΛ࢖͏ͱͲͷؔ਺͕୔ࢁ໋ྩΛҾ͖࿈Ε͍ͯΔ ͔ղੳ͠΍͘͢ͳΔɻ 39
46. ղੳͨ݁͠Ռ • RxSwiftͷ৔߹͸ɺdeinit ͕৭ʑҾ͖࿈Ε͖͍ͯͯͨɻ • disposeΛεέδϡʔϥʹࡌ͍ͤͯΔॲཧ͕ॏ͍ • deinit͸ϥϯλΠϜ͕ಈతʹݺͿͷͰpreserve͍ͯͨ͠ɻ • Stdlibͷ৔߹͸ɺΫϥογϡ࣌ʹϥϯλΠϜ͔Βݺ͹ΕΔ debugPrint͕ॏ͔ͬͨɻ 40
47. ରԠͷߏ૝ • deinit • ʮalloc ͞Εͳ͚Ε͹deinit΋ݺ͹Εͳ͍ʯΛ࢖ͬͯফ͠ ͯΈΔ • debugPrint • Ϋϥογϡ࣌ʹԿ΋ग़ྗ͠ͳ͍Ͱࢮ͵ϞʔυΛ௥Ճͯ͠Έ Δʁ 41
48. ײ૝ • λΠϜκʔϯͷҧ͍͕େม • ίϯύΠϥΤϯδχΞͬΆ͍࢓ࣄ͕Ͱָ͖͔ͯͬͨ͠ • ํ਑స׵͸͠ΜͲ͔͕ͬͨɺσΟεΧογϣϯͯ͠ྑ͍Ξϓ ϩʔνʹͳͬͨͷ͸ྑ͔ͬͨ 42
49. ֤छϦϯΫ ϓϩϙʔβϧ: https://docs.google.com/document/d/ 1qT77pc7rJaisuds4msSMfGPYCjy4uiJ-J1U7-nEW2Y0 ϑΥʔϥϜ: • https://forums.swift.org/t/refactoring-plan-of-silvisitor-for- lto/37678 • https://forums.swift.org/t/gsoc-lto-support-progress-report/ 37149 43