Only verify LazyCallGraph under expensive checks

[aeubanks]

Summary

These verify calls are causing a lot of slowdown on some files, up to 8x.
The LazyCallGraph infra has been tested a lot over the years, so I'm fairly confident that we don't always need to run the verifys.

llvm/lib/Analysis/CGSCCPassManager.cpp

static LazyCallGraph::SCC &updateCGAndAnalysisManagerForPass(
   LazyCallGraph::visitReferences(Worklist, Visited, VisitRef);
 
   // Handle new ref edges.
   for (Node *RefTarget : NewRefEdges) {
     SCC &TargetC = *G.lookupSCC(*RefTarget);
     RefSCC &TargetRC = TargetC.getOuterRefSCC();
     (void)TargetRC;
     // TODO: This only allows trivial edges to be added for now.
+#ifdef EXPENSIVE_CHECKS
     assert((RC == &TargetRC ||
            RC->isAncestorOf(TargetRC)) && "New ref edge is not trivial!");
+#endif
     RC->insertTrivialRefEdge(N, *RefTarget);
   }
 
   // Handle new call edges.
   for (Node *CallTarget : NewCallEdges) {
     SCC &TargetC = *G.lookupSCC(*CallTarget);
     RefSCC &TargetRC = TargetC.getOuterRefSCC();
     (void)TargetRC;
     // TODO: This only allows trivial edges to be added for now.
+#ifdef EXPENSIVE_CHECKS
     assert((RC == &TargetRC ||
            RC->isAncestorOf(TargetRC)) && "New call edge is not trivial!");
+#endif
     // Add a trivial ref edge to be promoted later on alongside
     // PromotedRefTargets.
     RC->insertTrivialRefEdge(N, *CallTarget);
   }
 
   // Include synthetic reference edges to known, defined lib functions.
   for (auto *LibFn : G.getLibFunctions())
     // While the list of lib functions doesn't have repeats, don't re-visit
#endif
   // form cycles that this would break.
   for (Node *RefTarget : DemotedCallTargets) {
     SCC &TargetC = *G.lookupSCC(*RefTarget);
     RefSCC &TargetRC = TargetC.getOuterRefSCC();
 
     // The easy case is when the target RefSCC is not this RefSCC. This is
     // only supported when the target RefSCC is a child of this RefSCC.
     if (&TargetRC != RC) {
+#ifdef EXPENSIVE_CHECKS
       assert(RC->isAncestorOf(TargetRC) &&
              "Cannot potentially form RefSCC cycles here!");
+#endif
       RC->switchOutgoingEdgeToRef(N, *RefTarget);
       LLVM_DEBUG(dbgs() << "Switch outgoing call edge to a ref edge from '" << N
                         << "' to '" << *RefTarget << "'\n");
       continue;
     }
 
     // We are switching an internal call edge to a ref edge. This may split up
     // some SCCs.
#endif
   // Now promote ref edges into call edges.
   for (Node *CallTarget : PromotedRefTargets) {
     SCC &TargetC = *G.lookupSCC(*CallTarget);
     RefSCC &TargetRC = TargetC.getOuterRefSCC();
 
     // The easy case is when the target RefSCC is not this RefSCC. This is
     // only supported when the target RefSCC is a child of this RefSCC.
     if (&TargetRC != RC) {
+#ifdef EXPENSIVE_CHECKS
       assert(RC->isAncestorOf(TargetRC) &&
              "Cannot potentially form RefSCC cycles here!");
+#endif
       RC->switchOutgoingEdgeToCall(N, *CallTarget);
       LLVM_DEBUG(dbgs() << "Switch outgoing ref edge to a call edge from '" << N
                         << "' to '" << *CallTarget << "'\n");
       continue;
     }
     LLVM_DEBUG(dbgs() << "Switch an internal ref edge to a call edge from '"
                       << N << "' to '" << *CallTarget << "'\n");
 

llvm/lib/Analysis/LazyCallGraph.cpp

 
 bool
 LazyCallGraph::RefSCC::switchInternalEdgeToCall(
     Node &SourceN, Node &TargetN,
     function_ref<void(ArrayRef<SCC *> MergeSCCs)> MergeCB) {
   assert(!(*SourceN)[TargetN].isCall() && "Must start with a ref edge!");
   SmallVector<SCC *, 1> DeletedSCCs;
 
-#ifndef NDEBUG
-  // In a debug build, verify the RefSCC is valid to start with and when this
-  // routine finishes.
+#ifdef EXPENSIVE_CHECKS
   verify();
   auto VerifyOnExit = make_scope_exit([&]() { verify(); });
 #endif
 
   SCC &SourceSCC = *G->lookupSCC(SourceN);
   SCC &TargetSCC = *G->lookupSCC(TargetN);
 
   // If the two nodes are already part of the same SCC, we're also done as
#endif
   int TargetIdx = SCCIndices[&TargetSCC];
   if (TargetIdx < SourceIdx) {
     SourceN->setEdgeKind(TargetN, Edge::Call);
     return false; // No new cycle.
   }
 
   // Compute the SCCs which (transitively) reach the source.
   auto ComputeSourceConnectedSet = [&](SmallPtrSetImpl<SCC *> &ConnectedSet) {
-#ifndef NDEBUG
+#ifdef EXPENSIVE_CHECKS
     // Check that the RefSCC is still valid before computing this as the
     // results will be nonsensical of we've broken its invariants.
     verify();
 #endif
     ConnectedSet.insert(&SourceSCC);
     auto IsConnected = [&](SCC &C) {
       for (Node &N : C)
         for (Edge &E : N->calls())
for (SCC *C :
         ConnectedSet.insert(C);
   };
 
   // Use a normal worklist to find which SCCs the target connects to. We still
   // bound the search based on the range in the postorder list we care about,
   // but because this is forward connectivity we just "recurse" through the
   // edges.
   auto ComputeTargetConnectedSet = [&](SmallPtrSetImpl<SCC *> &ConnectedSet) {
-#ifndef NDEBUG
+#ifdef EXPENSIVE_CHECKS
     // Check that the RefSCC is still valid before computing this as the
     // results will be nonsensical of we've broken its invariants.
     verify();
 #endif
     ConnectedSet.insert(&TargetSCC);
     SmallVector<SCC *, 4> Worklist;
     Worklist.push_back(&TargetSCC);
     do {
#endif
   // If the merge range is empty, then adding the edge didn't actually form any
   // new cycles. We're done.
   if (MergeRange.empty()) {
     // Now that the SCC structure is finalized, flip the kind to call.
     SourceN->setEdgeKind(TargetN, Edge::Call);
     return false; // No new cycle.
   }
 
-#ifndef NDEBUG
+#ifdef EXPENSIVE_CHECKS
   // Before merging, check that the RefSCC remains valid after all the
   // postorder updates.
   verify();
 #endif
 
   // Otherwise we need to merge all of the SCCs in the cycle into a single
   // result SCC.
   //
#endif
   // And we're done, but we did form a new cycle.
   return true;
 }
 
 void LazyCallGraph::RefSCC::switchTrivialInternalEdgeToRef(Node &SourceN,
                                                            Node &TargetN) {
   assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!");
 
-#ifndef NDEBUG
-  // In a debug build, verify the RefSCC is valid to start with and when this
-  // routine finishes.
+#ifdef EXPENSIVE_CHECKS
   verify();
   auto VerifyOnExit = make_scope_exit([&]() { verify(); });
 #endif
 
   assert(G->lookupRefSCC(SourceN) == this &&
          "Source must be in this RefSCC.");
   assert(G->lookupRefSCC(TargetN) == this &&
          "Target must be in this RefSCC.");
   assert(G->lookupSCC(SourceN) != G->lookupSCC(TargetN) &&
          "Source and Target must be in separate SCCs for this to be trivial!");
 
   // Set the edge kind.
   SourceN->setEdgeKind(TargetN, Edge::Ref);
 }
 
 iterator_range<LazyCallGraph::RefSCC::iterator>
 LazyCallGraph::RefSCC::switchInternalEdgeToRef(Node &SourceN, Node &TargetN) {
   assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!");
 
-#ifndef NDEBUG
-  // In a debug build, verify the RefSCC is valid to start with and when this
-  // routine finishes.
+#ifdef EXPENSIVE_CHECKS
   verify();
   auto VerifyOnExit = make_scope_exit([&]() { verify(); });
 #endif
 
   assert(G->lookupRefSCC(SourceN) == this &&
          "Source must be in this RefSCC.");
   assert(G->lookupRefSCC(TargetN) == this &&
          "Target must be in this RefSCC.");
#ifdef EXPENSIVE_CHECKS
   assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) &&
          "Target must be a descendant of the Source.");
 #endif
 
   // Edges between RefSCCs are the same regardless of call or ref, so we can
   // just flip the edge here.
   SourceN->setEdgeKind(TargetN, Edge::Call);
 
-#ifndef NDEBUG
-  // Check that the RefSCC is still valid.
+#ifdef EXPENSIVE_CHECKS
   verify();
 #endif
 }
 
 void LazyCallGraph::RefSCC::switchOutgoingEdgeToRef(Node &SourceN,
                                                     Node &TargetN) {
   assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!");
 
   assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
   assert(G->lookupRefSCC(TargetN) != this &&
          "Target must not be in this RefSCC.");
 #ifdef EXPENSIVE_CHECKS
   assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) &&
          "Target must be a descendant of the Source.");
 #endif
 
   // Edges between RefSCCs are the same regardless of call or ref, so we can
   // just flip the edge here.
   SourceN->setEdgeKind(TargetN, Edge::Ref);
 
-#ifndef NDEBUG
-  // Check that the RefSCC is still valid.
+#ifdef EXPENSIVE_CHECKS
   verify();
 #endif
 }
 
 void LazyCallGraph::RefSCC::insertInternalRefEdge(Node &SourceN,
                                                   Node &TargetN) {
   assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
   assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
 
   SourceN->insertEdgeInternal(TargetN, Edge::Ref);
 
-#ifndef NDEBUG
-  // Check that the RefSCC is still valid.
+#ifdef EXPENSIVE_CHECKS
   verify();
 #endif
 }
 
 void LazyCallGraph::RefSCC::insertOutgoingEdge(Node &SourceN, Node &TargetN,
                                                Edge::Kind EK) {
   // First insert it into the caller.
   SourceN->insertEdgeInternal(TargetN, EK);
 
   assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
 
   assert(G->lookupRefSCC(TargetN) != this &&
          "Target must not be in this RefSCC.");
 #ifdef EXPENSIVE_CHECKS
   assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) &&
          "Target must be a descendant of the Source.");
 #endif
 
-#ifndef NDEBUG
-  // Check that the RefSCC is still valid.
+#ifdef EXPENSIVE_CHECKS
   verify();
 #endif
 }
 
 SmallVector<LazyCallGraph::RefSCC *, 1>
 LazyCallGraph::RefSCC::insertIncomingRefEdge(Node &SourceN, Node &TargetN) {
   assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
   RefSCC &SourceC = *G->lookupRefSCC(SourceN);
   assert(&SourceC != this && "Source must not be in this RefSCC.");
 #ifdef EXPENSIVE_CHECKS
   assert(SourceC.isDescendantOf(*this) &&
          "Source must be a descendant of the Target.");
 #endif
 
   SmallVector<RefSCC *, 1> DeletedRefSCCs;
 
-#ifndef NDEBUG
-  // In a debug build, verify the RefSCC is valid to start with and when this
-  // routine finishes.
+#ifdef EXPENSIVE_CHECKS
   verify();
   auto VerifyOnExit = make_scope_exit([&]() { verify(); });
 #endif
 
   int SourceIdx = G->RefSCCIndices[&SourceC];
   int TargetIdx = G->RefSCCIndices[this];
   assert(SourceIdx < TargetIdx &&
          "Postorder list doesn't see edge as incoming!");

 }
 
 void LazyCallGraph::RefSCC::removeOutgoingEdge(Node &SourceN, Node &TargetN) {
   assert(G->lookupRefSCC(SourceN) == this &&
          "The source must be a member of this RefSCC.");
   assert(G->lookupRefSCC(TargetN) != this &&
          "The target must not be a member of this RefSCC");
 
-#ifndef NDEBUG
-  // In a debug build, verify the RefSCC is valid to start with and when this
-  // routine finishes.
+#ifdef EXPENSIVE_CHECKS
   verify();
   auto VerifyOnExit = make_scope_exit([&]() { verify(); });
 #endif
 
   // First remove it from the node.
   bool Removed = SourceN->removeEdgeInternal(TargetN);
   (void)Removed;
   assert(Removed && "Target not in the edge set for this caller?");
 }
 
 SmallVector<LazyCallGraph::RefSCC *, 1>
 LazyCallGraph::RefSCC::removeInternalRefEdge(Node &SourceN,
                                              ArrayRef<Node *> TargetNs) {
   // We return a list of the resulting *new* RefSCCs in post-order.
   SmallVector<RefSCC *, 1> Result;
 
-#ifndef NDEBUG
-  // In a debug build, verify the RefSCC is valid to start with and that either
-  // we return an empty list of result RefSCCs and this RefSCC remains valid,
-  // or we return new RefSCCs and this RefSCC is dead.
+#ifdef EXPENSIVE_CHECKS
+  // Verify the RefSCC is valid to start with and that either we return an empty
+  // list of result RefSCCs and this RefSCC remains valid, or we return new
+  // RefSCCs and this RefSCC is dead.
   verify();
   auto VerifyOnExit = make_scope_exit([&]() {
     // If we didn't replace our RefSCC with new ones, check that this one
     // remains valid.
     if (G)
       verify();
   });
 #endif
#endif
   }
 
   // Now that we've moved things into the new RefSCCs, clear out our current
   // one.
   G = nullptr;
   SCCs.clear();
   SCCIndices.clear();
 
-#ifndef NDEBUG
+#ifdef EXPENSIVE_CHECKS
   // Verify the new RefSCCs we've built.
   for (RefSCC *RC : Result)
     RC->verify();
 #endif
 
   // Return the new list of SCCs.
   return Result;
 }
 
 void LazyCallGraph::RefSCC::insertTrivialCallEdge(Node &SourceN,
                                                   Node &TargetN) {
-#ifndef NDEBUG
-  // Check that the RefSCC is still valid when we finish.
+#ifdef EXPENSIVE_CHECKS
   auto ExitVerifier = make_scope_exit([this] { verify(); });
 
-#ifdef EXPENSIVE_CHECKS
   // Check that we aren't breaking some invariants of the SCC graph. Note that
   // this is quadratic in the number of edges in the call graph!
   SCC &SourceC = *G->lookupSCC(SourceN);
   SCC &TargetC = *G->lookupSCC(TargetN);
   if (&SourceC != &TargetC)
     assert(SourceC.isAncestorOf(TargetC) &&
            "Call edge is not trivial in the SCC graph!");
-#endif // EXPENSIVE_CHECKS
-#endif // NDEBUG
+#endif
 
   // First insert it into the source or find the existing edge.
   auto InsertResult =
       SourceN->EdgeIndexMap.insert({&TargetN, SourceN->Edges.size()});
   if (!InsertResult.second) {
     // Already an edge, just update it.
     Edge &E = SourceN->Edges[InsertResult.first->second];
     if (E.isCall())
       return; // Nothing to do!
     E.setKind(Edge::Call);
   } else {
     // Create the new edge.
     SourceN->Edges.emplace_back(TargetN, Edge::Call);
   }
 }
 
 void LazyCallGraph::RefSCC::insertTrivialRefEdge(Node &SourceN, Node &TargetN) {
-#ifndef NDEBUG
-  // Check that the RefSCC is still valid when we finish.
+#ifdef EXPENSIVE_CHECKS
   auto ExitVerifier = make_scope_exit([this] { verify(); });
 
-#ifdef EXPENSIVE_CHECKS
   // Check that we aren't breaking some invariants of the RefSCC graph.
   RefSCC &SourceRC = *G->lookupRefSCC(SourceN);
   RefSCC &TargetRC = *G->lookupRefSCC(TargetN);
   if (&SourceRC != &TargetRC)
     assert(SourceRC.isAncestorOf(TargetRC) &&
            "Ref edge is not trivial in the RefSCC graph!");
-#endif // EXPENSIVE_CHECKS
-#endif // NDEBUG
+#endif
 
   // First insert it into the source or find the existing edge.
   auto InsertResult =
       SourceN->EdgeIndexMap.insert({&TargetN, SourceN->Edges.size()});
   if (!InsertResult.second)
     // Already an edge, we're done.
     return;
 
   // Create the new edge.
   SourceN->Edges.emplace_back(TargetN, Edge::Ref);
 }
 
 void LazyCallGraph::RefSCC::replaceNodeFunction(Node &N, Function &NewF) {
   Function &OldF = N.getFunction();
 
-#ifndef NDEBUG
-  // Check that the RefSCC is still valid when we finish.
+#ifdef EXPENSIVE_CHECKS
   auto ExitVerifier = make_scope_exit([this] { verify(); });
 
   assert(G->lookupRefSCC(N) == this &&
          "Cannot replace the function of a node outside this RefSCC.");
 
   assert(G->NodeMap.find(&NewF) == G->NodeMap.end() &&
          "Must not have already walked the new function!'");
 

 void LazyCallGraph::addSplitFunction(Function &OriginalFunction,
                                      Function &NewFunction) {
   assert(lookup(OriginalFunction) &&
          "Original function's node should already exist");
   Node &OriginalN = get(OriginalFunction);
   SCC *OriginalC = lookupSCC(OriginalN);
   RefSCC *OriginalRC = lookupRefSCC(OriginalN);
 
-#ifndef NDEBUG
+#ifdef EXPENSIVE_CHECKS
   OriginalRC->verify();
   auto VerifyOnExit = make_scope_exit([&]() { OriginalRC->verify(); });
 #endif
 
   assert(!lookup(NewFunction) &&
          "New function's node should not already exist");
   Node &NewN = initNode(NewFunction);
 

 void LazyCallGraph::addSplitRefRecursiveFunctions(
     Function &OriginalFunction, ArrayRef<Function *> NewFunctions) {
   assert(!NewFunctions.empty() && "Can't add zero functions");
   assert(lookup(OriginalFunction) &&
          "Original function's node should already exist");
   Node &OriginalN = get(OriginalFunction);
   RefSCC *OriginalRC = lookupRefSCC(OriginalN);
 
-#ifndef NDEBUG
+#ifdef EXPENSIVE_CHECKS
   OriginalRC->verify();
   auto VerifyOnExit = make_scope_exit([&]() {
     OriginalRC->verify();
-#ifdef EXPENSIVE_CHECKS
     for (Function *NewFunction : NewFunctions)
       lookupRefSCC(get(*NewFunction))->verify();
-#endif
   });
 #endif
 
   bool ExistsRefToOriginalRefSCC = false;
 
   for (Function *NewFunction : NewFunctions) {
     Node &NewN = initNode(*NewFunction);
 
buildGenericSCCs(
 
         // Push the new node into the postorder list and remember its position
         // in the index map.
         bool Inserted =
             RefSCCIndices.insert({NewRC, PostOrderRefSCCs.size()}).second;
         (void)Inserted;
         assert(Inserted && "Cannot already have this RefSCC in the index map!");
         PostOrderRefSCCs.push_back(NewRC);
-#ifndef NDEBUG
+#ifdef EXPENSIVE_CHECKS
         NewRC->verify();
 #endif
       });
 }
 
 AnalysisKey LazyCallGraphAnalysis::Key;
 
 LazyCallGraphPrinterPass::LazyCallGraphPrinterPass(raw_ostream &OS) : OS(OS) {}