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 ↗

(On Diff #83934)

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

36 ↗

(On Diff #83934)

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 ↗

(On Diff #83934)

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

lib/Transforms/IPO/GlobalDCE.cpp

101 ↗

(On Diff #83934)

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 ↗

(On Diff #83934)

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 ↗

(On Diff #83934)

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

114 ↗

(On Diff #83934)

No braces

118 ↗

(On Diff #83934)

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

120 ↗

(On Diff #83934)

Early return.

121 ↗

(On Diff #83934)

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

126 ↗

(On Diff #83934)

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

187 ↗

(On Diff #83934)

pop_back_val()

190 ↗

(On Diff #83934)

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 ↗

(On Diff #83934)

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 ↗

(On Diff #83934)

See r179458

113 ↗

(On Diff #83934)

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

126 ↗

(On Diff #83934)

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 ↗

(On Diff #83934)

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 ↗

(On Diff #83934)

Thanks for the pointer!

126 ↗

(On Diff #83934)

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 ↗

(On Diff #84096)

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

185 ↗

(On Diff #84096)

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

234 ↗

(On Diff #84096)

stray newline.

[serge-sans-paille]

include/llvm/Transforms/IPO/GlobalDCE.h

36 ↗

(On Diff #83934)

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 ↗

(On Diff #83934)

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 ↗

(On Diff #84331)

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

lib/Transforms/IPO/GlobalDCE.cpp

126 ↗

(On Diff #83934)

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 ↗

(On Diff #84641)

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

lib/Transforms/IPO/GlobalDCE.cpp

132 ↗

(On Diff #84641)

stray newline?

187 ↗

(On Diff #84641)

Please use an explicit type here

188 ↗

(On Diff #84641)

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

189 ↗

(On Diff #84641)

Why did you remove this comment?

[serge-sans-paille]

include/llvm/Transforms/IPO/GlobalDCE.h

22 ↗

(On Diff #84641)

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

41 ↗

(On Diff #84642)

DenseMap?

[mehdi_amini]

include/llvm/Transforms/IPO/GlobalDCE.h

41 ↗

(On Diff #84642)

DenseMap with a SmallPtrSet?

44 ↗

(On Diff #84642)

Doxygen like-prefix.

lib/Transforms/IPO/GlobalDCE.cpp

81 ↗

(On Diff #84642)

End sentence with a dot.

82 ↗

(On Diff #84642)

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

41 ↗

(On Diff #84642)

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

41 ↗

(On Diff #84642)

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

41 ↗

(On Diff #84642)

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!

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

 // deletes whatever is left over.  This allows it to delete recursive chunks of
 // the program which are unreachable.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_IPO_GLOBALDCE_H
 #define LLVM_TRANSFORMS_IPO_GLOBALDCE_H
 
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PassManager.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;
+
+  /// Global -> Global that uses this global.
+  std::unordered_multimap<GlobalValue *, GlobalValue *> 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;
 
-  /// 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);
+  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

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

 #include "llvm/ADT/Statistic.h"
 #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.
+/// The recursion stops as soon as a GlobalValue is met.
+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)) {
+    // Avoid walking the whole tree of a big ConstantExprs multiple times.
+    auto Where = ConstantDependenciesCache.find(CE);
+    if (Where != ConstantDependenciesCache.end()) {
+      auto const &K = Where->second;
+      Deps.insert(K.begin(), K.end());
+    } else {
+      SmallPtrSetImpl<GlobalValue *> &LocalDeps = ConstantDependenciesCache[CE];
+      for (User *CEUser : CE->users())
+        ComputeDependencies(CEUser, LocalDeps);
+      Deps.insert(LocalDeps.begin(), LocalDeps.end());
+    }
+  }
+}
+
+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));
+  }
+}
+
+/// Mark Global value as Live
+void GlobalDCEPass::MarkLive(GlobalValue &GV,
+                             SmallVectorImpl<GlobalValue *> *Updates) {
+  auto const Ret = AliveGlobals.insert(&GV);
+  if (!Ret.second)
+    return;
+
+  if (Updates)
+    Updates->push_back(&GV);
+  if (Comdat *C = GV.getComdat()) {
+    for (auto &&CM : make_range(ComdatMembers.equal_range(C)))
+      MarkLive(*CM.second, Updates); // Recursion depth is only two because only
+                                     // globals in the same comdat are visited.
+  }
+}
+
 PreservedAnalyses GlobalDCEPass::run(Module &M, ModuleAnalysisManager &MAM) {
   bool Changed = false;
 
+  // The algorithm first computes the set L of global variables that are
+  // trivially live.  Then it walks the initialization of these variables to
+  // compute the globals used to initialize them, which effectively builds a
+  // directed graph where nodes are global variables, and an edge from A to B
+  // means B is used to initialize A.  Finally, it propagates the liveness
+  // information through the graph starting from the nodes in L. Nodes note
+  // marked as alive are discarded.
+
   // 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));
   for (GlobalVariable &GV : M.globals())
     if (Comdat *C = GV.getComdat())
       ComdatMembers.insert(std::make_pair(C, &GV));
   for (GlobalAlias &GA : M.aliases())
     if (Comdat *C = GA.getComdat())
       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{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);
   }
 
   // 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
PreservedAnalyses GlobalDCEPass::run(Module &M, ModuleAnalysisManager &MAM) {
   // The third pass drops targets of aliases which are dead...
   std::vector<GlobalAlias*> DeadAliases;
   for (GlobalAlias &GA : M.aliases())
     if (!AliveGlobals.count(&GA)) {
       DeadAliases.push_back(&GA);
       GA.setAliasee(nullptr);
     }
 
-  // The third pass drops targets of ifuncs which are dead...
+  // The fourth pass drops targets of ifuncs which are dead...
   std::vector<GlobalIFunc*> DeadIFuncs;
   for (GlobalIFunc &GIF : M.ifuncs())
     if (!AliveGlobals.count(&GIF)) {
       DeadIFuncs.push_back(&GIF);
       GIF.setResolver(nullptr);
     }
 
   // Now that all interferences have been dropped, delete the actual objects
for (GlobalAlias *GA : DeadAliases)
     EraseUnusedGlobalValue(GA);
 
   NumIFuncs += DeadIFuncs.size();
   for (GlobalIFunc *GIF : DeadIFuncs)
     EraseUnusedGlobalValue(GIF);
 
   // Make sure that all memory is released
   AliveGlobals.clear();
-  SeenConstants.clear();
+  ConstantDependenciesCache.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();
 }