Global DCE performance improvement

[serge-sans-paille]

Summary

Change the original algorithm so that it scales better when meeting very large bitcode where every instruction does not implies a global.

[mehdi_amini]

Can you add a description to the revision summarizing what you're doing before I try to infer it from the diff?
Thanks!

[davide]

Do you have numbers showing up the improvement?
What's the effect of memoization on memory usage?

[mehdi_amini]

include/llvm/Transforms/IPO/GlobalDCE.h

35

Why did you rename this? Some part of this diff could disappear without this change.

36

DenseMap is intended to contains small value, SmallPtrSet seems a bit fat here?

Also, after reading the algorithm, this could be a vector, you should not need dedup by construction.

38

We don't suffix member names.
Also it'd be nice to document these.

lib/Transforms/IPO/GlobalDCE.cpp

101

The recursion is bound by the fact that we only recurse on constant and stop at the first GV reached. I'd rather have this as a comment in the code.

103

So the memorization is only used for constants (GV initializers, GEP, what else?), I'd rename it to make it explicit that this cache only applies to constants.

Also can such constant have multiple uses? I'm failing to remember in which case right now. If they only have a single use we could just traverse and remove the memorization entirely.

113

Why not passing GV to ComputeDependencies instead of Deps and populate directly GVDependencies_ ?

114

No braces

118

GlobalValue & GV does not seems formatted, I'd suggest running git clang-format on this patch.

120

Early return.

121

What does this do? Isn't it redundant with the one two lines above?

126

What's the bound on the recursion? How do we guarantee that we won't run out of stack? Worth a comment.

187

pop_back_val()

190

No brace

[serge-sans-paille]

In D28549#643081, @davide wrote:

Do you have numbers showing up the improvement?

The complexity of the original algorithm is roughly in O(|live function instruction|), and the complexity of this algorithm is roughly in O(|globals users|).

So if there's a big global function, previous algorithm is more costly (and that's the original motivating example).
If there's a big dead function, this algorithm is more costly.

On average test cases, it does not make much difference, It's only noticeable on very large functions (> 1000000 instructions) which happens to be my use case.

What's the effect of memoization on memory usage?

memoization of constants was already implemented in the previous algorithm, so not much difference here.
This algorithm contains an additional map that holds the global dependencies, so it should have a bigger memory consumption.

include/llvm/Transforms/IPO/GlobalDCE.h

36

According to my tests, DenseMap performs better on large test case than std::unorderd_map (by a factor of two)

Correct for Set->Vector

lib/Transforms/IPO/GlobalDCE.cpp

103

See r179458

113

I think it's clearer like this, as it separates the dependencies build from the GVDependencies update.

126

There's a finite number of globals and they can only be visited once because of the set check.

[mehdi_amini]

include/llvm/Transforms/IPO/GlobalDCE.h

36

I'm not sure what you mean by "large test case"? Do you mean lots of entries? My point was about sizeof(Map[key]) and memory consumption.

lib/Transforms/IPO/GlobalDCE.cpp

103

Thanks for the pointer!

126

I'm not worried about *infinite* recursion, but *too large* recursion for the limit stack size in some environment. If the recursion is in O(global) that's a potential stack overflow.

[davide]

Can you please add a comment in the code explaining how the new algorithm works? I'd like to see figures on a case where this actually matters (e.g. take the bitcode, run through opt -globaldce -time-passes with the old/new algorithm and see what's the performance difference)

lib/Transforms/IPO/GlobalDCE.cpp

173

Capital letter, ending with a dot (here and everywhere else).

185

This whole patch needs to be clang-formatted, this should look like
while (blah).

241

stray newline.

[serge-sans-paille]

include/llvm/Transforms/IPO/GlobalDCE.h

36

Yeah I meant lots of entries. I've done the tests with an std::vector instead and it does not impact the execution time, and it's indeeded better on the memory usage, switching to this.

lib/Transforms/IPO/GlobalDCE.cpp

126

Previous algorithm worst case recursion depth was in `O(|global|)` and that happened, for instance, when a global function references a static function that references a static function that ... etc.

I'm not 100% sure but this function has a worst case recursion depth of two, has it only propagates the liveness to the whole comdat section. If you agree with my analyse, I'll update the comment.

[serge-sans-paille]

I've updated the diff, formated with git clang-format as suggested. However there's no -U option to that command so the diff does not appear with the whole contxt, and sipmly running clang-format on the files produces too much noise.

[mehdi_amini]

In D28549#645475, @serge-sans-paille wrote:

I've updated the diff, formated with git clang-format as suggested. However there's no -U option to that command so the diff does not appear with the whole contxt, and sipmly running clang-format on the files produces too much noise.

FYI, My workflow is:

• git clang-format HEAD~ (will format only the last commit).
• git diff (just to check the formatting changes)
• git commit -a --amend
• generate the patch for phab, I'm using arc diff HEAD~ which handles everything, otherwise manually with git diff -U9999 HEAD~ you get the full context patched to be updated.

[mehdi_amini]

I wonder if your diff is correct, it seems that you updated the diff compare to the previous diff state (like if you didn't squash commits).

include/llvm/Transforms/IPO/GlobalDCE.h

42

Put the comments on the line before the variables, and use /// (doxygen-like prefix).

lib/Transforms/IPO/GlobalDCE.cpp

126

Yes I guess a GV can belong only to a single comdat so it should be fine!

[serge-sans-paille]

Patch correctly formatted, thanks @mehdi_amini for sharing your workflow.
Also updated the comments.

[davide]

include/llvm/Transforms/IPO/GlobalDCE.h

22

Are you still using SmallSet or is this a dead include?

lib/Transforms/IPO/GlobalDCE.cpp

132

stray newline?

188

Please use an explicit type here

189

Why did you remove this comment?

189

and here, and I guess everywhere else the type is not really obvious (for consistency with what's already in the pass).

[serge-sans-paille]

include/llvm/Transforms/IPO/GlobalDCE.h

22

It's still used for `ConstantDependeciesCache`.

[davide]

This looks much better now. Can you please add a comment in the code explaining the algorithm (if I missed it, please point out) while I take a last look? Thanks.

[majnemer]

include/llvm/Transforms/IPO/GlobalDCE.h

39

DenseMap?

[mehdi_amini]

include/llvm/Transforms/IPO/GlobalDCE.h

39

DenseMap with a SmallPtrSet?

42

Doxygen like-prefix.

lib/Transforms/IPO/GlobalDCE.cpp

82

End sentence with a dot.

83

Doxygen-like prefix.

[mehdi_amini]

In D28549#648403, @davide wrote:

This looks much better now. Can you please add a comment in the code explaining the algorithm (if I missed it, please point out) while I take a last look? Thanks.

To be fair: the algorithm isn't changed, it is just the "uses" graph edges that are reversed as a pre-step.
I.e. the question is "how to you get all the globals referenced by another global"?

Before this patch, it was doing this by walking the body (or the initializer) and collecting the references. What this patch is doing, it precomputing the answer to this query for the whole module by walking the use-list of every global instead.
I believe it is the only change.

[davide]

In D28549#648456, @mehdi_amini wrote:

In D28549#648403, @davide wrote:

This looks much better now. Can you please add a comment in the code explaining the algorithm (if I missed it, please point out) while I take a last look? Thanks.

To be fair: the algorithm isn't changed, it is just the "uses" graph edges that are reversed as a pre-step.
I.e. the question is "how to you get all the globals referenced by another global"?

Before this patch, it was doing this by walking the body (or the initializer) and collecting the references. What this patch is doing, it precomputing the answer to this query for the whole module by walking the use-list of every global instead.
I believe it is the only change.

That should go in a comment, this is my point.

[serge-sans-paille]

include/llvm/Transforms/IPO/GlobalDCE.h

39

I've kept the original Moving to a std::unordered_multimap for GVDEpendencies, not sure about what you expect for the ConstantDependenciesCache. What's the pro/con of using a DenseMap?

[mehdi_amini]

include/llvm/Transforms/IPO/GlobalDCE.h

39

DenseMap is an open-addressing hashmap where the bucket are allocated with the key, hence "dense". This is very performance but for the memory consumption: empty buckets are taking the same amount of space as occupied ones.
So we usually avoid DenseMap containing "large" elements.

[serge-sans-paille]

include/llvm/Transforms/IPO/GlobalDCE.h

39

ok, thanks for the extra info. Everything looks much nicer now.

[serge-sans-paille]

Hi all,
the review seems ok now, do you have any other suggestion/advices/flames?

As a side note : I don't have the commit right in llvm trunk, so if one of you could take care of that step?

[mehdi_amini]

Davide, any other comment?

[davide]

LGTM. Serge, one of us can commit that for you once llvm.org decides to go back online.

[serge-sans-paille]

Thanks!

[mehdi_amini]

I can't apply on trunk, mind rebasing?

[serge-sans-paille]

@mehdi_amini : rebased!

include/llvm/Transforms/IPO/GlobalDCE.h

 // the program which are unreachable.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_IPO_GLOBALDCE_H
 #define LLVM_TRANSFORMS_IPO_GLOBALDCE_H
 
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PassManager.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/DenseMap.h"
 #include <unordered_map>
 
 namespace llvm {
 
 /// Pass to remove unused function declarations.
 class GlobalDCEPass : public PassInfoMixin<GlobalDCEPass> {
 public:
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
 
 private:
-  SmallPtrSet<GlobalValue*, 32> AliveGlobals;
-  SmallPtrSet<Constant *, 8> SeenConstants;
-  std::unordered_multimap<Comdat *, GlobalValue *> ComdatMembers;
-
-  /// Mark the specific global value as needed, and
-  /// recursively mark anything that it uses as also needed.
-  void GlobalIsNeeded(GlobalValue *GV);
-  void MarkUsedGlobalsAsNeeded(Constant *C);
+  SmallPtrSet<GlobalValue*, 16> LiveGVs_;
+  DenseMap<GlobalValue*, SmallPtrSet<GlobalValue*, 8>> GVDependencies_;
+  std::unordered_map<Constant*, SmallPtrSet<GlobalValue*, 8>> DependenciesCache_;
+  std::unordered_multimap<Comdat*, GlobalValue *> ComdatMembers_;
+
+  void UpdateGVDependencies(GlobalValue &GV);
+  void MarkLive(GlobalValue &GV, SmallVectorImpl<GlobalValue*>* Updates=nullptr);
   bool RemoveUnusedGlobalValue(GlobalValue &GV);
+
+  void ComputeDependencies(Value *V, SmallPtrSetImpl<GlobalValue*>& U);
 };
 
 }
 
 #endif // LLVM_TRANSFORMS_IPO_GLOBALDCE_H

lib/Transforms/IPO/GlobalDCE.cpp

 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Pass.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/Utils/CtorUtils.h"
 #include "llvm/Transforms/Utils/GlobalStatus.h"
 #include <unordered_map>
+
 using namespace llvm;
 
 #define DEBUG_TYPE "globaldce"
 
 STATISTIC(NumAliases  , "Number of global aliases removed");
 STATISTIC(NumFunctions, "Number of functions removed");
 STATISTIC(NumIFuncs,    "Number of indirect functions removed");
 STATISTIC(NumVariables, "Number of global variables removed");

 static bool isEmptyFunction(Function *F) {
   BasicBlock &Entry = F->getEntryBlock();
   if (Entry.size() != 1 || !isa<ReturnInst>(Entry.front()))
     return false;
   ReturnInst &RI = cast<ReturnInst>(Entry.front());
   return RI.getReturnValue() == nullptr;
 }
 
+// Compute the set of GlobalValue that depends from V
+// This repetitive walk is memoized as it can be called a lot for the same value.
+void GlobalDCEPass::ComputeDependencies(Value* V, SmallPtrSetImpl<GlobalValue*>& Deps) {
+  if(auto *I = dyn_cast<Instruction>(V)) {
+    Function* Parent = I->getParent()->getParent();
+    Deps.insert(Parent);
+  }
+  else if(auto* GV = dyn_cast<GlobalValue>(V)) {
+    Deps.insert(GV);
+  }
+  else if(auto* CE = dyn_cast<Constant>(V)) {
+    auto Where = DependenciesCache_.find(CE);
+    if(Where != DependenciesCache_.end()) {
+      auto const& K = Where->second;
+      Deps.insert(K.begin(), K.end());
+    }
+    else {
+      auto &LocalDeps = DependenciesCache_[CE];
+      for(auto* CEUser : CE->users())
+        ComputeDependencies(CEUser, LocalDeps);
+      Deps.insert(LocalDeps.begin(), LocalDeps.end());
+    }
+  }
+}
+
+void GlobalDCEPass::UpdateGVDependencies(GlobalValue& GV) {
+  SmallPtrSet<GlobalValue*, 8> Deps;
+  for(auto* User: GV.users())
+    ComputeDependencies(User, Deps);
+  Deps.erase(&GV); // remove self-reference
+  for(auto* GVU : Deps) {
+    GVDependencies_[GVU].insert(&GV);
+  }
+}
+
+// Mark Global value as Live
+void GlobalDCEPass::MarkLive(GlobalValue & GV, SmallVectorImpl<GlobalValue*>* Updates) {
+  auto const Ret = LiveGVs_.insert(&GV);
+  if(Ret.second) {
+    LiveGVs_.insert(&GV);
+    if(Updates)
+      Updates->push_back(&GV);
+    if (Comdat *C = GV.getComdat()) {
+      for (auto &&CM : make_range(ComdatMembers_.equal_range(C)))
+        MarkLive(*CM.second, Updates);
+    }
+  }
+}
+
 PreservedAnalyses GlobalDCEPass::run(Module &M, ModuleAnalysisManager &) {
+
   bool Changed = false;
 
   // Remove empty functions from the global ctors list.
   Changed |= optimizeGlobalCtorsList(M, isEmptyFunction);
 
   // Collect the set of members for each comdat.
   for (Function &F : M)
     if (Comdat *C = F.getComdat())
-      ComdatMembers.insert(std::make_pair(C, &F));
+      ComdatMembers_.insert(std::make_pair(C, &F));
   for (GlobalVariable &GV : M.globals())
     if (Comdat *C = GV.getComdat())
-      ComdatMembers.insert(std::make_pair(C, &GV));
+      ComdatMembers_.insert(std::make_pair(C, &GV));
   for (GlobalAlias &GA : M.aliases())
     if (Comdat *C = GA.getComdat())
-      ComdatMembers.insert(std::make_pair(C, &GA));
+      ComdatMembers_.insert(std::make_pair(C, &GA));
 
   // Loop over the module, adding globals which are obviously necessary.
   for (GlobalObject &GO : M.global_objects()) {
     Changed |= RemoveUnusedGlobalValue(GO);
     // Functions with external linkage are needed if they have a body.
     // Externally visible & appending globals are needed, if they have an
     // initializer.
     if (!GO.isDeclaration() && !GO.hasAvailableExternallyLinkage())
       if (!GO.isDiscardableIfUnused())
-        GlobalIsNeeded(&GO);
+        MarkLive(GO);
+
+    UpdateGVDependencies(GO);
   }
 
+
+  // compute direct dependencies of aliases
   for (GlobalAlias &GA : M.aliases()) {
     Changed |= RemoveUnusedGlobalValue(GA);
     // Externally visible aliases are needed.
     if (!GA.isDiscardableIfUnused())
-      GlobalIsNeeded(&GA);
+      MarkLive(GA);
+
+    UpdateGVDependencies(GA);
   }
 
+  // compute direct dependencies of ifuncs
   for (GlobalIFunc &GIF : M.ifuncs()) {
     Changed |= RemoveUnusedGlobalValue(GIF);
     // Externally visible ifuncs are needed.
     if (!GIF.isDiscardableIfUnused())
-      GlobalIsNeeded(&GIF);
+      MarkLive(GIF);
+
+    UpdateGVDependencies(GIF);
+  }
+
+  // propagate liveness from collected Global Values through the computed dependencies
+  SmallVector<GlobalValue*, 8> NewLiveGVs{LiveGVs_.begin(), LiveGVs_.end()};
+  while(!NewLiveGVs.empty()) {
+    auto * LGV = NewLiveGVs.back();
+    NewLiveGVs.pop_back();
+    for(auto* GV : GVDependencies_[LGV]) {
+      MarkLive(*GV, &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
-  for (GlobalVariable &GV : M.globals())
-    if (!AliveGlobals.count(&GV)) {
-      DeadGlobalVars.push_back(&GV);         // Keep track of dead globals
-      if (GV.hasInitializer()) {
+  SmallVector<GlobalVariable*, 8> DeadGlobalVars;
+  for(GlobalVariable& GV : M.globals()) {
+    if(LiveGVs_.count(&GV) == 0) {
+      DeadGlobalVars.push_back(&GV);
+      if(GV.hasInitializer()) {
         Constant *Init = GV.getInitializer();
         GV.setInitializer(nullptr);
         if (isSafeToDestroyConstant(Init))
           Init->destroyConstant();
       }
     }
+  }
 
   // The second pass drops the bodies of functions which are dead...
-  std::vector<Function *> DeadFunctions;
-  for (Function &F : M)
-    if (!AliveGlobals.count(&F)) {
-      DeadFunctions.push_back(&F);         // Keep track of dead globals
+  SmallVector<Function*, 8> DeadFunctions;
+  for(Function& F : M) {
+    if(LiveGVs_.count(&F) == 0) {
+      DeadFunctions.push_back(&F);
       if (!F.isDeclaration())
         F.deleteBody();
     }
+  }
 
   // The third pass drops targets of aliases which are dead...
-  std::vector<GlobalAlias*> DeadAliases;
-  for (GlobalAlias &GA : M.aliases())
-    if (!AliveGlobals.count(&GA)) {
+  SmallVector<GlobalAlias*, 8> DeadAliases;
+  for(auto& GA : M.aliases()) {
+    if(LiveGVs_.count(&GA) == 0) {
       DeadAliases.push_back(&GA);
       GA.setAliasee(nullptr);
     }
+  }
 
-  // The third pass drops targets of ifuncs which are dead...
-  std::vector<GlobalIFunc*> DeadIFuncs;
-  for (GlobalIFunc &GIF : M.ifuncs())
-    if (!AliveGlobals.count(&GIF)) {
+  // The fourth pass drops targets of ifuncs which are dead...
+  SmallVector<GlobalIFunc*, 8> DeadIFuncs;
+  for (GlobalIFunc &GIF : M.ifuncs()) {
+    if(LiveGVs_.count(&GIF) == 0) {
       DeadIFuncs.push_back(&GIF);
       GIF.setResolver(nullptr);
     }
+  }
+
 
   // Now that all interferences have been dropped, delete the actual objects
   // themselves.
   auto EraseUnusedGlobalValue = [&](GlobalValue *GV) {
     RemoveUnusedGlobalValue(*GV);
     GV->eraseFromParent();
     Changed = true;
   };
 
   NumFunctions += DeadFunctions.size();
-  for (Function *F : DeadFunctions)
-    EraseUnusedGlobalValue(F);
+  for(auto* DGV : DeadFunctions)
+    EraseUnusedGlobalValue(DGV);
 
   NumVariables += DeadGlobalVars.size();
-  for (GlobalVariable *GV : DeadGlobalVars)
-    EraseUnusedGlobalValue(GV);
+  for(auto* DGV : DeadGlobalVars)
+    EraseUnusedGlobalValue(DGV);
 
   NumAliases += DeadAliases.size();
-  for (GlobalAlias *GA : DeadAliases)
-    EraseUnusedGlobalValue(GA);
+  for(auto* DGV : DeadAliases)
+    EraseUnusedGlobalValue(DGV);
 
   NumIFuncs += DeadIFuncs.size();
-  for (GlobalIFunc *GIF : DeadIFuncs)
-    EraseUnusedGlobalValue(GIF);
+  for(auto* DGV : DeadIFuncs)
+    EraseUnusedGlobalValue(DGV);
 
-  // Make sure that all memory is released
-  AliveGlobals.clear();
-  SeenConstants.clear();
-  ComdatMembers.clear();
+  LiveGVs_.clear();
+  DependenciesCache_.clear();
+  GVDependencies_.clear();
+  ComdatMembers_.clear();
 
   if (Changed)
     return PreservedAnalyses::none();
   return PreservedAnalyses::all();
 }
 
-/// GlobalIsNeeded - the specific global value as needed, and
-/// recursively mark anything that it uses as also needed.
-void GlobalDCEPass::GlobalIsNeeded(GlobalValue *G) {
-  // If the global is already in the set, no need to reprocess it.
-  if (!AliveGlobals.insert(G).second)
-    return;
-
-  if (Comdat *C = G->getComdat()) {
-    for (auto &&CM : make_range(ComdatMembers.equal_range(C)))
-      GlobalIsNeeded(CM.second);
-  }
-
-  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(G)) {
-    // If this is a global variable, we must make sure to add any global values
-    // referenced by the initializer to the alive set.
-    if (GV->hasInitializer())
-      MarkUsedGlobalsAsNeeded(GV->getInitializer());
-  } else if (GlobalIndirectSymbol *GIS = dyn_cast<GlobalIndirectSymbol>(G)) {
-    // The target of a global alias or ifunc is needed.
-    MarkUsedGlobalsAsNeeded(GIS->getIndirectSymbol());
-  } else {
-    // Otherwise this must be a function object.  We have to scan the body of
-    // the function looking for constants and global values which are used as
-    // operands.  Any operands of these types must be processed to ensure that
-    // any globals used will be marked as needed.
-    Function *F = cast<Function>(G);
-
-    for (Use &U : F->operands())
-      MarkUsedGlobalsAsNeeded(cast<Constant>(U.get()));
-
-    for (BasicBlock &BB : *F)
-      for (Instruction &I : BB)
-        for (Use &U : I.operands())
-          if (GlobalValue *GV = dyn_cast<GlobalValue>(U))
-            GlobalIsNeeded(GV);
-          else if (Constant *C = dyn_cast<Constant>(U))
-            MarkUsedGlobalsAsNeeded(C);
-  }
-}
-
-void GlobalDCEPass::MarkUsedGlobalsAsNeeded(Constant *C) {
-  if (GlobalValue *GV = dyn_cast<GlobalValue>(C))
-    return GlobalIsNeeded(GV);
-
-  // Loop over all of the operands of the constant, adding any globals they
-  // use to the list of needed globals.
-  for (Use &U : C->operands()) {
-    // If we've already processed this constant there's no need to do it again.
-    Constant *Op = dyn_cast<Constant>(U);
-    if (Op && SeenConstants.insert(Op).second)
-      MarkUsedGlobalsAsNeeded(Op);
-  }
-}
-
 // RemoveUnusedGlobalValue - Loop over all of the uses of the specified
 // GlobalValue, looking for the constant pointer ref that may be pointing to it.
 // If found, check to see if the constant pointer ref is safe to destroy, and if
 // so, nuke it.  This will reduce the reference count on the global value, which
 // might make it deader.
 //
 bool GlobalDCEPass::RemoveUnusedGlobalValue(GlobalValue &GV) {
   if (GV.use_empty())
     return false;
   GV.removeDeadConstantUsers();
   return GV.use_empty();
 }