[LCG] Hoist the main DFS loop out of the edge removal function. This

makes working through the worklist much cleaner, and makes it possible
to avoid the 'bool-to-continue-the-outer-loop' hack. Not a huge
difference, but I think this is approaching as polished as I can make
it.

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

1 files changed, 70 insertions, 74 deletions

diff --git a/lib/Analysis/LazyCallGraph.cpp b/lib/Analysis/LazyCallGraph.cpp
index 45d289b8c0..1e7f796057 100644
--- a/lib/Analysis/LazyCallGraph.cpp
+++ b/lib/Analysis/LazyCallGraph.cpp
@@ -180,71 +180,21 @@ void LazyCallGraph::SCC::removeEdge(LazyCallGraph &G, Function &Caller,
     G.LeafSCCs.push_back(this);
 }
 
-SmallVector<LazyCallGraph::SCC *, 1>
-LazyCallGraph::SCC::removeInternalEdge(LazyCallGraph &G, Node &Caller,
-                                       Node &Callee) {
-  // We return a list of the resulting SCCs, where 'this' is always the first
-  // element.
-  SmallVector<SCC *, 1> ResultSCCs;
-  ResultSCCs.push_back(this);
-
-  // Direct recursion doesn't impact the SCC graph at all.
-  if (&Caller == &Callee)
-    return ResultSCCs;
-
-  // We're going to do a full mini-Tarjan's walk using a local stack here.
-  int NextDFSNumber;
-  SmallVector<std::pair<Node *, Node::iterator>, 4> DFSStack;
-  SmallVector<Node *, 4> PendingSCCStack;
-
-  // The worklist is every node in the original SCC.
-  SmallVector<Node *, 1> Worklist;
-  Worklist.swap(Nodes);
-  for (Node *N : Worklist) {
-    // The nodes formerly in this SCC are no longer in any SCC.
-    N->DFSNumber = 0;
-    N->LowLink = 0;
-    G.SCCMap.erase(N);
-  }
-  assert(Worklist.size() > 1 && "We have to have at least two nodes to have an "
-                                "edge between them that is within the SCC.");
-
-  // The callee can already reach every node in this SCC (by definition). It is
-  // the only node we know will stay inside this SCC. Everything which
-  // transitively reaches Callee will also remain in the SCC. To model this we
-  // incrementally add any chain of nodes which reaches something in the new
-  // node set to the new node set. This short circuits one side of the Tarjan's
-  // walk.
-  insert(G, Callee);
-
-  Node *N = nullptr;
-  Node::iterator ChildI;
+void LazyCallGraph::SCC::internalDFS(
+    LazyCallGraph &G,
+    SmallVectorImpl<std::pair<Node *, Node::iterator>> &DFSStack,
+    SmallVectorImpl<Node *> &PendingSCCStack, Node *N,
+    SmallVectorImpl<SCC *> &ResultSCCs) {
+  Node::iterator I = N->begin();
+  N->LowLink = N->DFSNumber = 1;
+  int NextDFSNumber = 2;
   for (;;) {
-    if (!N) {
-      if (!DFSStack.empty()) {
-        N = DFSStack.back().first;
-        ChildI = DFSStack.back().second;
-        DFSStack.pop_back();
-      } else {
-        // Clear off any nodes which have already been visited in the DFS.
-        while (!Worklist.empty() && Worklist.back()->DFSNumber != 0)
-          Worklist.pop_back();
-        if (Worklist.empty())
-          break;
-        N = Worklist.pop_back_val();
-        N->LowLink = N->DFSNumber = 1;
-        NextDFSNumber = 2;
-        ChildI = N->begin();
-        assert(PendingSCCStack.empty() && "Cannot start a fresh DFS walk with "
-                                          "pending nodes from a prior walk.");
-      }
-    }
     assert(N->DFSNumber != 0 && "We should always assign a DFS number "
                                 "before processing a node.");
 
     // We simulate recursion by popping out of the nested loop and continuing.
-    bool Recurse = false;
-    for (auto I = ChildI, E = N->end(); I != E; ++I) {
+    Node::iterator E = N->end();
+    while (I != E) {
       Node &ChildN = *I;
       if (SCC *ChildSCC = G.SCCMap.lookup(&ChildN)) {
         // Check if we have reached a node in the new (known connected) set of
@@ -256,14 +206,13 @@ LazyCallGraph::SCC::removeInternalEdge(LazyCallGraph &G, Node &Caller,
             insert(G, *PendingSCCStack.pop_back_val());
           while (!DFSStack.empty())
             insert(G, *DFSStack.pop_back_val().first);
-          N = nullptr;
-          Recurse = true;
-          break;
+          return;
         }
 
         // If this child isn't currently in this SCC, no need to process it.
         // However, we do need to remove this SCC from its SCC's parent set.
         ChildSCC->ParentSCCs.erase(this);
+        ++I;
         continue;
       }
 
@@ -273,12 +222,12 @@ LazyCallGraph::SCC::removeInternalEdge(LazyCallGraph &G, Node &Caller,
         // child's lowlink is reflected.
         DFSStack.push_back(std::make_pair(N, I));
 
-        // Recurse onto this node via a tail call.
+        // Continue, resetting to the child node.
         ChildN.LowLink = ChildN.DFSNumber = NextDFSNumber++;
         N = &ChildN;
-        ChildI = ChildN.begin();
-        Recurse = true;
-        break;
+        I = ChildN.begin();
+        E = ChildN.end();
+        continue;
       }
 
       // Track the lowest link of the childen, if any are still in the stack.
@@ -287,11 +236,14 @@ LazyCallGraph::SCC::removeInternalEdge(LazyCallGraph &G, Node &Caller,
              "Low-link must not be zero with a non-zero DFS number.");
       if (ChildN.LowLink >= 0 && ChildN.LowLink < N->LowLink)
         N->LowLink = ChildN.LowLink;
+      ++I;
     }
-    if (Recurse)
-      continue;
 
-    if (N->LowLink != N->DFSNumber) {
+    if (N->LowLink == N->DFSNumber) {
+      ResultSCCs.push_back(G.formSCC(N, PendingSCCStack));
+      if (DFSStack.empty())
+        return;
+    } else {
       // At this point we know that N cannot ever be an SCC root. Its low-link
       // is not its dfs-number, and we've processed all of its children. It is
       // just sitting here waiting until some node further down the stack gets
@@ -300,13 +252,57 @@ LazyCallGraph::SCC::removeInternalEdge(LazyCallGraph &G, Node &Caller,
       PendingSCCStack.push_back(N);
 
       assert(!DFSStack.empty() && "We shouldn't have an empty stack!");
-      N = nullptr;
-      continue;
     }
 
-    ResultSCCs.push_back(G.formSCC(N, PendingSCCStack));
-    N = nullptr;
+    N = DFSStack.back().first;
+    I = DFSStack.back().second;
+    DFSStack.pop_back();
+  }
+}
+
+SmallVector<LazyCallGraph::SCC *, 1>
+LazyCallGraph::SCC::removeInternalEdge(LazyCallGraph &G, Node &Caller,
+                                       Node &Callee) {
+  // We return a list of the resulting SCCs, where 'this' is always the first
+  // element.
+  SmallVector<SCC *, 1> ResultSCCs;
+  ResultSCCs.push_back(this);
+
+  // Direct recursion doesn't impact the SCC graph at all.
+  if (&Caller == &Callee)
+    return ResultSCCs;
+
+  // The worklist is every node in the original SCC.
+  SmallVector<Node *, 1> Worklist;
+  Worklist.swap(Nodes);
+  for (Node *N : Worklist) {
+    // The nodes formerly in this SCC are no longer in any SCC.
+    N->DFSNumber = 0;
+    N->LowLink = 0;
+    G.SCCMap.erase(N);
   }
+  assert(Worklist.size() > 1 && "We have to have at least two nodes to have an "
+                                "edge between them that is within the SCC.");
+
+  // The callee can already reach every node in this SCC (by definition). It is
+  // the only node we know will stay inside this SCC. Everything which
+  // transitively reaches Callee will also remain in the SCC. To model this we
+  // incrementally add any chain of nodes which reaches something in the new
+  // node set to the new node set. This short circuits one side of the Tarjan's
+  // walk.
+  insert(G, Callee);
+
+  // We're going to do a full mini-Tarjan's walk using a local stack here.
+  SmallVector<std::pair<Node *, Node::iterator>, 4> DFSStack;
+  SmallVector<Node *, 4> PendingSCCStack;
+  do {
+    Node *N = Worklist.pop_back_val();
+    if (N->DFSNumber == 0)
+      internalDFS(G, DFSStack, PendingSCCStack, N, ResultSCCs);
+
+    assert(DFSStack.empty() && "Didn't flush the entire DFS stack!");
+    assert(PendingSCCStack.empty() && "Didn't flush all pending SCC nodes!");
+  } while (!Worklist.empty());
 
   // Now we need to reconnect the current SCC to the graph.
   bool IsLeafSCC = true;