[GlobalDCE] Use DenseMap instead of unordered_multimap for GVDependencies.

[mzolotukhin]

Summary

std::unordered_multimap happens to be very slow when the number of elements
grows large. On one of our internal applications we observed a 17x compile time
improvement from changing it to DenseMap.

[davide]

Generally switching to generic containers to LLVM ones lead to improvements, but 17x seems quite large to me (not complaining).
I wonder if you can add a test (maybe to CTMark?) to make sure this doesn't regress.

[mzolotukhin]

Generally switching to generic containers to LLVM ones lead to improvements, but 17x seems quite large to me (not complaining).

17x probably comes from the test being huge: when we're building with LTO, we're getting a ~50Mb bitcode file.

I wonder if you can add a test (maybe to CTMark?) to make sure this doesn't regress.

I thought about that too. But I thought maybe we should create a compile time regression test-suite instead, which will be separate from CTMark. That is, I definitely agree that it'd be great to be able to check if tests don't regress, but I would also like to keep CTMark runs fast. It's discussable though.
Another problem with this particular test is that I cannot disclose it as is, but I guess if we just generate a huge file with tons of globals and functions that would also do.

Michael

[mzolotukhin]

Hi,

Is the patch ok to commit?

Michael

[davide]

include/llvm/Transforms/IPO/GlobalDCE.h

38 ↗

(On Diff #119002)

Why 4 ?

[mzolotukhin]

Thanks!

include/llvm/Transforms/IPO/GlobalDCE.h

38 ↗

(On Diff #119002)

No particular reason. Any advice on a more scientific option to choose this value? :)

[davide]

When it comes to this I generally try many of them until I find something reasonable. I'm pretty sure 4 is a reasonable value, but I was wondering whether you actually ran some tests on some different values before picking "the best" (for some definition of). Unlikely it's going to matter in any way, FWIW.

llvm/trunk/include/llvm/Transforms/IPO/GlobalDCE.h

 class GlobalDCEPass : public PassInfoMixin<GlobalDCEPass> {
 public:
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
 
 private:
   SmallPtrSet<GlobalValue*, 32> AliveGlobals;
 
   /// Global -> Global that uses this global.
-  std::unordered_multimap<GlobalValue *, GlobalValue *> GVDependencies;
+  DenseMap<GlobalValue *, SmallPtrSet<GlobalValue *, 4>> GVDependencies;
 
   /// Constant -> Globals that use this global cache.
   std::unordered_map<Constant *, SmallPtrSet<GlobalValue *, 8>>
       ConstantDependenciesCache;
 
   /// Comdat -> Globals in that Comdat section.
   std::unordered_multimap<Comdat *, GlobalValue *> ComdatMembers;
 

llvm/trunk/lib/Transforms/IPO/GlobalDCE.cpp

 }
 
 void GlobalDCEPass::UpdateGVDependencies(GlobalValue &GV) {
   SmallPtrSet<GlobalValue *, 8> Deps;
   for (User *User : GV.users())
     ComputeDependencies(User, Deps);
   Deps.erase(&GV); // Remove self-reference.
   for (GlobalValue *GVU : Deps) {
-    GVDependencies.insert(std::make_pair(GVU, &GV));
+    GVDependencies[GVU].insert(&GV);
   }
 }
 
 /// Mark Global value as Live
 void GlobalDCEPass::MarkLive(GlobalValue &GV,
                              SmallVectorImpl<GlobalValue *> *Updates) {
   auto const Ret = AliveGlobals.insert(&GV);
   if (!Ret.second)
PreservedAnalyses GlobalDCEPass::run(Module &M, ModuleAnalysisManager &MAM) {
   }
 
   // Propagate liveness from collected Global Values through the computed
   // dependencies.
   SmallVector<GlobalValue *, 8> NewLiveGVs{AliveGlobals.begin(),
                                            AliveGlobals.end()};
   while (!NewLiveGVs.empty()) {
     GlobalValue *LGV = NewLiveGVs.pop_back_val();
-    for (auto &&GVD : make_range(GVDependencies.equal_range(LGV)))
-      MarkLive(*GVD.second, &NewLiveGVs);
+    for (auto *GVD : GVDependencies[LGV])
+      MarkLive(*GVD, &NewLiveGVs);
   }
 
   // Now that all globals which are needed are in the AliveGlobals set, we loop
   // through the program, deleting those which are not alive.
   //
 
   // The first pass is to drop initializers of global variables which are dead.
   std::vector<GlobalVariable *> DeadGlobalVars; // Keep track of dead globals