[LCG] Rather than removing nodes from the SCC entry set when we process

them, just skip over any DFS-numbered nodes when finding the next root
of a DFS. This allows the entry set to just be a vector as we populate
it from a uniqued source. It also removes the possibility for a linear
scan of the entry set to actually do the removal which can make things
go quadratic if we get unlucky.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207312 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/include/llvm/Analysis/LazyCallGraph.h b/include/llvm/Analysis/LazyCallGraph.h
index d4b2d354f18f4520be2a50acaf1b95a83237d353..07ba0004bd850a63375458bf9baab0ff424fa96b 100644 (file)
--- a/include/llvm/Analysis/LazyCallGraph.h
+++ b/include/llvm/Analysis/LazyCallGraph.h
@@ -384,7 +384,7 @@ private:
   SmallVector<std::pair<Node *, iterator>, 4> DFSStack;
 
   /// \brief Set of entry nodes not-yet-processed into SCCs.
-  SmallSetVector<Function *, 4> SCCEntryNodes;
+  SmallVector<Function *, 4> SCCEntryNodes;
 
   /// \brief Stack of nodes the DFS has walked but not yet put into a SCC.
   SmallVector<Node *, 4> PendingSCCStack;

diff --git a/lib/Analysis/LazyCallGraph.cpp b/lib/Analysis/LazyCallGraph.cpp
index 50accb3a75315165e63323df86666595cecb0e78..196003430a43d4564b006cfd4c50dce6c5911e73 100644 (file)
--- a/lib/Analysis/LazyCallGraph.cpp
+++ b/lib/Analysis/LazyCallGraph.cpp
@@ -100,9 +100,9 @@ LazyCallGraph::LazyCallGraph(Module &M) : NextDFSNumber(0) {
 
   for (auto &Entry : EntryNodes)
     if (Function *F = Entry.dyn_cast<Function *>())
-      SCCEntryNodes.insert(F);
+      SCCEntryNodes.push_back(F);
     else
-      SCCEntryNodes.insert(&Entry.get<Node *>()->getFunction());
+      SCCEntryNodes.push_back(&Entry.get<Node *>()->getFunction());
 }
 
 LazyCallGraph::LazyCallGraph(LazyCallGraph &&G)
@@ -437,10 +437,12 @@ LazyCallGraph::SCC *LazyCallGraph::getNextSCCInPostOrder() {
     DFSStack.pop_back();
   } else {
     // If we've handled all candidate entry nodes to the SCC forest, we're done.
-    if (SCCEntryNodes.empty())
-      return nullptr;
+    do {
+      if (SCCEntryNodes.empty())
+        return nullptr;
 
-    N = &get(*SCCEntryNodes.pop_back_val());
+      N = &get(*SCCEntryNodes.pop_back_val());
+    } while (N->DFSNumber != 0);
     I = N->begin();
     N->LowLink = N->DFSNumber = 1;
     NextDFSNumber = 2;
@@ -463,7 +465,6 @@ LazyCallGraph::SCC *LazyCallGraph::getNextSCCInPostOrder() {
         assert(!SCCMap.count(&ChildN) &&
                "Found a node with 0 DFS number but already in an SCC!");
         ChildN.LowLink = ChildN.DFSNumber = NextDFSNumber++;
-        SCCEntryNodes.remove(&ChildN.getFunction());
         N = &ChildN;
         I = ChildN.begin();
         E = ChildN.end();