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

SwiftのThin Cross Module Optimization (WIP)

Yuta Saito
September 25, 2020

SwiftのThin Cross Module Optimization (WIP)

Yuta Saito

September 25, 2020
Tweet

More Decks by Yuta Saito

Other Decks in Programming

Transcript

  1. ౰ॳͷܭը 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
  2. 6

  3. 7

  4. 13

  5. 14

  6. 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
  7. 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
  8. 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
  9. ྫ 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
  10. ౸ୡෆೳͳؔ਺Λચ͍ग़͢ 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
  11. ౸ୡෆೳͳؔ਺Λચ͍ग़͢ 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
  12. ౸ୡෆೳͳؔ਺Λચ͍ग़͢ 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
  13. ౸ୡෆೳͳؔ਺Λચ͍ग़͢ 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
  14. ౸ୡෆೳͳؔ਺Λચ͍ग़͢ 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
  15. ౸ୡෆೳͳؔ਺Λચ͍ग़͢ 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
  16. 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
  17. 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
  18. ܕ͕࢖ΘΕ͍ͯͳ͚Ε͹ςʔϒϧܦ༝Ͱϝιου͕ݺ͹ΕΔ͜ ͱ΋ͳ͍ͷͰফͤΔ 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
  19. 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
  20. 32

  21. 35