[ThinLTO] Efficiency improvement when writing module path string table

[tejohnson]

Summary

When writing the combined index, we are walking the entire module
path StringMap in the full index, and checking whether each one should be
included in the index being written. For distributed backends, where we
write an individual combined index for each file, each with only a few
module paths, this is incredibly inefficient. Add a method that takes
a callback and hides the details of whether we are writing the full
combined index, or just a slice, and in the latter case it walks the set
of modules to include instead of the entire index.

For a huge application with around 23K files (i.e. where we were iterating
through the 23K-entry modulePath StringMap 23K times), this change improved
the thin link time by a whopping 48%.

[pcc]

LGTM

lib/Bitcode/Writer/BitcodeWriter.cpp

if (ModuleToSummariesForIndex) {
           Callback(Summary);
     } else {
       for (auto &Summaries : Index)
         for (auto &Summary : Summaries.second.SummaryList)
           Callback({Summaries.first, Summary.get()});
     }
   }
 
+  /// Calls the callback for each entry in the modulePaths StringMap that
+  /// should be written to the module path string table. This hides the details
+  /// of whether they are being pulled from the entire index or just those in a
+  /// provided ModuleToSummariesForIndex map.
+  void
+  forEachModule(std::function<
+                void(const StringMapEntry<std::pair<uint64_t, ModuleHash>> &)>
+                    Callback) {
+    if (ModuleToSummariesForIndex) {
+      for (const auto &M : *ModuleToSummariesForIndex) {
+        const auto &MPI = Index.modulePaths().find(M.first);
+        if (MPI == Index.modulePaths().end()) {
+          // This should only happen if the bitcode file was empty, in which
+          // case we shouldn't be importing (the ModuleToSummariesForIndex
+          // would only include the module we are writing and index for).
+          assert(ModuleToSummariesForIndex->size() == 1);
+          continue;
+        }
+        Callback(*MPI);
+      }
+    } else {
+      for (const auto &MPSE : Index.modulePaths())
+        Callback(MPSE);
+    }
+  }
+
   /// Main entry point for writing a combined index to bitcode.
   void write();
 
 private:
   void writeModStrings();
   void writeCombinedGlobalValueSummary();
 
-  /// Indicates whether the provided \p ModulePath should be written into
-  /// the module string table, e.g. if full index written or if it is in
-  /// the provided subset.
-  bool doIncludeModule(StringRef ModulePath) {
-    return !ModuleToSummariesForIndex ||
-           ModuleToSummariesForIndex->count(ModulePath);
-  }
-
   Optional<unsigned> getValueId(GlobalValue::GUID ValGUID) {
     auto VMI = GUIDToValueIdMap.find(ValGUID);
     if (VMI == GUIDToValueIdMap.end())
       return None;
     return VMI->second;
   }
   std::map<GlobalValue::GUID, unsigned> &valueIds() { return GUIDToValueIdMap; }
 };
void IndexBitcodeWriter::writeModStrings() {
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32));
   unsigned AbbrevHash = Stream.EmitAbbrev(std::move(Abbv));
 
   SmallVector<unsigned, 64> Vals;
-  for (const auto &MPSE : Index.modulePaths()) {
-    if (!doIncludeModule(MPSE.getKey()))
-      continue;
+  forEachModule(
+      [&](const StringMapEntry<std::pair<uint64_t, ModuleHash>> &MPSE) {
         StringEncoding Bits =
             getStringEncoding(MPSE.getKey().data(), MPSE.getKey().size());
         unsigned AbbrevToUse = Abbrev8Bit;
         if (Bits == SE_Char6)
           AbbrevToUse = Abbrev6Bit;
         else if (Bits == SE_Fixed7)
           AbbrevToUse = Abbrev7Bit;
 
         Vals.push_back(MPSE.getValue().first);
 
         for (const auto P : MPSE.getKey())
           Vals.push_back((unsigned char)P);
 
         // Emit the finished record.
         Stream.EmitRecord(bitc::MST_CODE_ENTRY, Vals, AbbrevToUse);
 
         Vals.clear();
         // Emit an optional hash for the module now
         auto &Hash = MPSE.getValue().second;
-    bool AllZero = true; // Detect if the hash is empty, and do not generate it
+        bool AllZero =
+            true; // Detect if the hash is empty, and do not generate it
         for (auto Val : Hash) {
           if (Val)
             AllZero = false;
           Vals.push_back(Val);
         }
         if (!AllZero) {
           // Emit the hash record.
           Stream.EmitRecord(bitc::MST_CODE_HASH, Vals, AbbrevHash);
         }
 
         Vals.clear();
-  }
+      });
   Stream.ExitBlock();
 }
 
 /// Write the function type metadata related records that need to appear before
 /// a function summary entry (whether per-module or combined).
 static void writeFunctionTypeMetadataRecords(BitstreamWriter &Stream,
                                              FunctionSummary *FS) {
   if (!FS->type_tests().empty())