Use DenseMap instead std::map for GVSummaryMapTy.

[danielcdh]

Summary

This speeds-up thin-link by ~47% for large programs.

[tejohnson]

LGTM

[mehdi_amini]

When we used an std::map originally it was because we needed the ordering. Have you checked that we don't iterate on any instance of this map?

lib/LTO/LTO.cpp

1033

Can we use GVSummaryMapTy here?

[tejohnson]

In D35148#803193, @mehdi_amini wrote:

When we used an std::map originally it was because we needed the ordering. Have you checked that we don't iterate on any instance of this map?

From http://llvm.org/docs/ProgrammersManual.html#llvm-adt-densemap-h it doesn't appear that iteration order is an issue for DenseMap. StringMap on the other hand does not have a deterministic iteration ordering, and I recall using a std::map somewhere instead of a StringMap for that reason.

Note the index itself still uses a std::map, for other reasons (documented at the declaration). We also still use a std::map where we write out the individual index files for the backends in the distributed backend case. In any case from what I can tell, we typically query this map, rather than iterate. The only place I see an iteration is when we are computing imports for a module, so I suppose that could affect the debug output ordering, but does that matter (if iteration order is even non-deterministic for DenseMap, and from what I can tell from the LLVM doc linked above it isn't).

[mehdi_amini]

In D35148#803251, @tejohnson wrote:

In D35148#803193, @mehdi_amini wrote:

When we used an std::map originally it was because we needed the ordering. Have you checked that we don't iterate on any instance of this map?

From http://llvm.org/docs/ProgrammersManual.html#llvm-adt-densemap-h it doesn't appear that iteration order is an issue for DenseMap.

As long as keys aren't pointers...
(But just as every hash_map right?)

StringMap on the other hand does not have a deterministic iteration ordering, and I recall using a std::map somewhere instead of a StringMap for that reason.

Really? I'm pretty sure the order is deterministic, but just like any hash_map (including DenseMap): the order of insertion and the hash function are determining the resulting order.

Note the index itself still uses a std::map, for other reasons (documented at the declaration). We also still use a std::map where we write out the individual index files for the backends in the distributed backend case. In any case from what I can tell, we typically query this map, rather than iterate. The only place I see an iteration is when we are computing imports for a module, so I suppose that could affect the debug output ordering, but does that matter (if iteration order is even non-deterministic for DenseMap, and from what I can tell from the LLVM doc linked above it isn't).

OK!

[danielcdh]

update

[danielcdh]

How should we proceed with this patch?

There are indeed some code that iterates through this type, e.g.:

// Populate the worklist with the import for the functions in the current
// module
for (auto &GVSummary : DefinedGVSummaries) {
  if (!Index.isGlobalValueLive(GVSummary.second)) {
    DEBUG(dbgs() << "Ignores Dead GUID: " << GVSummary.first << "\n");
    continue;
  }
  auto *Summary = GVSummary.second;
  if (auto *AS = dyn_cast<AliasSummary>(Summary))
    Summary = &AS->getAliasee();
  auto *FuncSummary = dyn_cast<FunctionSummary>(Summary);
  if (!FuncSummary)
    // Skip import for global variables
    continue;
  DEBUG(dbgs() << "Initalize import for " << GVSummary.first << "\n");
  computeImportForFunction(*FuncSummary, Index, ImportInstrLimit,
                           DefinedGVSummaries, Worklist, ImportList,
                           ExportLists);
}

include/llvm/IR/ModuleSummaryIndex.h

 
 /// String table to hold/own module path strings, which additionally holds the
 /// module ID assigned to each module during the plugin step, as well as a hash
 /// of the module. The StringMap makes a copy of and owns inserted strings.
 using ModulePathStringTableTy = StringMap<std::pair<uint64_t, ModuleHash>>;
 
 /// Map of global value GUID to its summary, used to identify values defined in
 /// a particular module, and provide efficient access to their summary.
-using GVSummaryMapTy = std::map<GlobalValue::GUID, GlobalValueSummary *>;
+using GVSummaryMapTy = DenseMap<GlobalValue::GUID, GlobalValueSummary *>;
 
 /// Class to hold module path string table and global value map,
 /// and encapsulate methods for operating on them.
 class ModuleSummaryIndex {
 private:
   /// Map from value name to list of summary instances for values of that
   /// name (may be duplicates in the COMDAT case, e.g.).
   GlobalValueSummaryMapTy GlobalValueMap;

lib/LTO/LTO.cpp

Error LTO::runThinLTO(AddStreamFn AddStream, NativeObjectCache Cache,
   if (ThinLTO.ModuleMap.empty())
     return Error::success();
 
   if (Conf.CombinedIndexHook && !Conf.CombinedIndexHook(ThinLTO.CombinedIndex))
     return Error::success();
 
   // Collect for each module the list of function it defines (GUID ->
   // Summary).
-  StringMap<std::map<GlobalValue::GUID, GlobalValueSummary *>>
+  StringMap<GVSummaryMapTy>
       ModuleToDefinedGVSummaries(ThinLTO.ModuleMap.size());
   ThinLTO.CombinedIndex.collectDefinedGVSummariesPerModule(
       ModuleToDefinedGVSummaries);
   // Create entries for any modules that didn't have any GV summaries
   // (either they didn't have any GVs to start with, or we suppressed
   // generation of the summaries because they e.g. had inline assembly
   // uses that couldn't be promoted/renamed on export). This is so
   // InProcessThinBackend::start can still launch a backend thread, which