[Verifier] Fix performance regression for LTO builds

[krasin]

Summary

Fix a significant performance regression by introducing GlobalValueVisited field and reusing the map.
This is a follow up to r257823 that slowed down linking Chrome with LTO by 2.5x.

If you revert this commit, please, also revert r257823.

BUG=https://llvm.org/bugs/show_bug.cgi?id=26214

[pcc]

lib/IR/Verifier.cpp

526

I don't think you want to clear every time. Verifier::VisitIt is checking a property of V, not of GV.

[loladiro]

lib/IR/Verifier.cpp

526

Correct, don't clear this.

[krasin]

do not clear Visited map.

[krasin]

Done. Is it good for a test now?

[krasin]

For submit

[krasin]

Remove unnecessary empty line diff.

[krasin1]

Since it's a pretty basic fix that does not change the logic (except of reusing GlobalValueVisited, which was already reviewed), I will go ahead and submit this revision.

Feel free to revert it, but in this case, I would also ask to revert r257823, so that we unbreak 'CFI Linux ToT' buildbot in Chrome.

Feel free to improve the CL (for example, by making forEachUser more reusable), but please, keep an eye on https://build.chromium.org/p/chromium.fyi/builders/CFI%20Linux%20ToT.

[mehdi_amini]

lib/IR/Verifier.cpp

476–500

What was the problem with this being a lambda? I missed why you needed to change this for this patch?

505

You changed the implementation of the function but kept the name, which is now no longer representative of what this does.

[krasin]

forEachUser -> forEachUserGlobalValue

[krasin1]

lib/IR/Verifier.cpp

505

Agree. I have renamed it forEachUserGlobalValue.

I expect that Keno would like to make a template implementation of forEachUser, then this function will go away.

[krasin]

one more place to rename.

[krasin1]

lib/IR/Verifier.cpp

476–501

Keno made a guess (https://llvm.org/bugs/show_bug.cgi?id=26214#c1), which I verified (took 4 hours). It could be that the major savings are from reusing the map, but my time budget for firefighting is limited. I am perfectly fine if Keno (or anyone else) to make another try with lambdas or templates. I will give a hint, if there's a visible regression due to that.

[krasin]

just extract the map; keep the lambda.

[krasin1]

I felt lonely and made another round of trials. Turns out it's the map reuse (or the lack of thereof) was the reason for the regression.

[mehdi_amini]

LGTM.

[mehdi_amini]

lib/IR/Verifier.cpp

503–504

I'm wondering which use case this recursive is catching? Why isn't looking at one level enough here?
(it's late here, I may miss something obvious)

[loladiro]

You could have a constant user that's not associated to a module.

[loladiro]

Also @krasin, thanks for taking care of this, I appreciate it.

[krasin1]

In D16338#330978, @loladiro wrote:

Also @krasin, thanks for taking care of this, I appreciate it.

No problem. While my knowledge of lib/IR is limited (so, your guidance was very helpful), I really was in the position to reliably reproduce the issue.

lib/IR/Verifier.cpp

class Verifier : public InstVisitor<Verifier>, VerifierSupport {
 
   // Maps catchswitches and cleanuppads that unwind to siblings to the
   // terminators that indicate the unwind, used to detect cycles therein.
   MapVector<Instruction *, TerminatorInst *> SiblingFuncletInfo;
 
   /// Cache of constants visited in search of ConstantExprs.
   SmallPtrSet<const Constant *, 32> ConstantExprVisited;
 
+  // Verify that this GlobalValue is only used in this module.
+  // This map is used to avoid visiting uses twice. We can arrive at a user
+  // twice, if they have multiple operands. In particular for very large
+  // constant expressions, we can arrive at a particular user many times.
+  SmallPtrSet<const Value *, 32> GlobalValueVisited;
+
   void checkAtomicMemAccessSize(const Module *M, Type *Ty,
                                 const Instruction *I);
+
 public:
   explicit Verifier(raw_ostream &OS)
       : VerifierSupport(OS), Context(nullptr), LandingPadResultTy(nullptr),
         SawFrameEscape(false) {}
 
   bool verify(const Function &F) {
     M = F.getParent();
     Context = &M->getContext();
bool verify(const Module &M) {
     verifyTypeRefs();
 
     return !Broken;
   }
 
 private:
   // Verification methods...
   void visitGlobalValue(const GlobalValue &GV);
+  bool doVisitGlobalValue(const GlobalValue &GV, const Value *V);
+  void forEachUser(const Value *User,
+                   const GlobalValue &GV);
+
   void visitGlobalVariable(const GlobalVariable &GV);
   void visitGlobalAlias(const GlobalAlias &GA);
   void visitAliaseeSubExpr(const GlobalAlias &A, const Constant &C);
   void visitAliaseeSubExpr(SmallPtrSetImpl<const GlobalAlias *> &Visited,
                            const GlobalAlias &A, const Constant &C);
   void visitNamedMDNode(const NamedMDNode &NMD);
   void visitMDNode(const MDNode &MD);
   void visitMetadataAsValue(const MetadataAsValue &MD, Function *F);
#define Assert(C, ...) \
   do { if (!(C)) { CheckFailed(__VA_ARGS__); return; } } while (0)
 
 void Verifier::visit(Instruction &I) {
   for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i)
     Assert(I.getOperand(i) != nullptr, "Operand is null", &I);
   InstVisitor<Verifier>::visit(I);
 }
 
-// Helper to recursively iterate over indirect users. By
-// returning false, the callback can ask to stop recursing
-// further.
-static void forEachUser(const Value *User,
-                        SmallPtrSet<const Value *, 32> &Visited,
-                        llvm::function_ref<bool(const Value *)> Callback) {
-  if (!Visited.insert(User).second)
+bool Verifier::doVisitGlobalValue(const GlobalValue &GV, const Value *V) {
+  if (const Instruction *I = dyn_cast<Instruction>(V)) {
+    if (!I->getParent() || !I->getParent()->getParent())
+      CheckFailed("Global is referenced by parentless instruction!", &GV,
+                  M, I);
+    else if (I->getParent()->getParent()->getParent() != M)
+      CheckFailed("Global is referenced in a different module!", &GV,
+                  M, I, I->getParent()->getParent(),
+                  I->getParent()->getParent()->getParent());
+    return false;
+  } else if (const Function *F = dyn_cast<Function>(V)) {
+    if (F->getParent() != M)
+      CheckFailed("Global is used by function in a different module", &GV,
+                  M, F, F->getParent());
+    return false;
+  }
+  return true;
+}
+
+// Helper to recursively iterate over indirect users of
+// a global value. By returning false, doVisitGlobalValue
+// can ask to stop recursing further.
+void Verifier::forEachUser(const Value *User,
+                           const GlobalValue &GV) {
+  if (!GlobalValueVisited.insert(User).second)
     return;
   for (const Value *TheNextUser : User->materialized_users())
-    if (Callback(TheNextUser))
-      forEachUser(TheNextUser, Visited, Callback);
+    if (doVisitGlobalValue(GV, TheNextUser))
+      forEachUser(TheNextUser, GV);
 }
 
 void Verifier::visitGlobalValue(const GlobalValue &GV) {
   Assert(!GV.isDeclaration() || GV.hasExternalLinkage() ||
              GV.hasExternalWeakLinkage(),
          "Global is external, but doesn't have external or weak linkage!", &GV);
 
   Assert(GV.getAlignment() <= Value::MaximumAlignment,
          "huge alignment values are unsupported", &GV);
   Assert(!GV.hasAppendingLinkage() || isa<GlobalVariable>(GV),
          "Only global variables can have appending linkage!", &GV);
 
   if (GV.hasAppendingLinkage()) {
     const GlobalVariable *GVar = dyn_cast<GlobalVariable>(&GV);
     Assert(GVar && GVar->getValueType()->isArrayTy(),
            "Only global arrays can have appending linkage!", GVar);
   }
 
   if (GV.isDeclarationForLinker())
     Assert(!GV.hasComdat(), "Declaration may not be in a Comdat!", &GV);
 
-  // Verify that this GlobalValue is only used in this module.
-  // This map is used to avoid visiting uses twice. We can arrive at a user
-  // twice, if they have multiple operands. In particular for very large
-  // constant expressions, we can arrive at a particular user many times.
-  SmallPtrSet<const Value *, 32> Visited;
-  forEachUser(&GV, Visited, [&](const Value *V) -> bool {
-    if (const Instruction *I = dyn_cast<Instruction>(V)) {
-      if (!I->getParent() || !I->getParent()->getParent())
-        CheckFailed("Global is referenced by parentless instruction!", &GV,
-                    M, I);
-      else if (I->getParent()->getParent()->getParent() != M)
-        CheckFailed("Global is referenced in a different module!", &GV,
-                    M, I, I->getParent()->getParent(),
-                    I->getParent()->getParent()->getParent());
-      return false;
-    } else if (const Function *F = dyn_cast<Function>(V)) {
-      if (F->getParent() != M)
-        CheckFailed("Global is used by function in a different module", &GV,
-                    M, F, F->getParent());
-      return false;
-    }
-    return true;
-  });
+  forEachUser(&GV, GV);
 }
 
 void Verifier::visitGlobalVariable(const GlobalVariable &GV) {
   if (GV.hasInitializer()) {
     Assert(GV.getInitializer()->getType() == GV.getValueType(),
            "Global variable initializer type does not match global "
            "variable type!",
            &GV);