From b0015735153741b6f0978127976002fda9503a3c Mon Sep 17 00:00:00 2001
From: Chandler Carruth <chandlerc@gmail.com>
Date: Wed, 23 Apr 2014 06:09:03 +0000
Subject: [LCG] Hoist the logic for forming a new SCC from the top of the
 DFSStack into a helper function. I plan to re-use it for doing incremental
 DFS-based updates to the SCCs when we mutate the call graph.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206948 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Analysis/LazyCallGraph.cpp | 88 ++++++++++++++++++++++--------------------
 1 file changed, 47 insertions(+), 41 deletions(-)

(limited to 'lib/Analysis/LazyCallGraph.cpp')

diff --git a/lib/Analysis/LazyCallGraph.cpp b/lib/Analysis/LazyCallGraph.cpp
index 201e644da9..cb5c052c18 100644
--- a/lib/Analysis/LazyCallGraph.cpp
+++ b/lib/Analysis/LazyCallGraph.cpp
@@ -151,45 +151,8 @@ void LazyCallGraph::updateGraphPtrs() {
   }
 }
 
-LazyCallGraph::SCC *LazyCallGraph::getNextSCCInPostOrder() {
-  // When the stack is empty, there are no more SCCs to walk in this graph.
-  if (DFSStack.empty()) {
-    // If we've handled all candidate entry nodes to the SCC forest, we're done.
-    if (SCCEntryNodes.empty())
-      return nullptr;
-
-    Node *N = get(*SCCEntryNodes.pop_back_val());
-    DFSStack.push_back(std::make_pair(N, N->begin()));
-  }
-
-  Node *N = DFSStack.back().first;
-  if (N->DFSNumber == 0) {
-    // This node hasn't been visited before, assign it a DFS number and remove
-    // it from the entry set.
-    N->LowLink = N->DFSNumber = NextDFSNumber++;
-    SCCEntryNodes.remove(&N->getFunction());
-  }
-
-  for (auto I = DFSStack.back().second, E = N->end(); I != E; ++I) {
-    Node *ChildN = *I;
-    if (ChildN->DFSNumber == 0) {
-      // Mark that we should start at this child when next this node is the
-      // top of the stack. We don't start at the next child to ensure this
-      // child's lowlink is reflected.
-      // FIXME: I don't actually think this is required, and we could start
-      // at the next child.
-      DFSStack.back().second = I;
-
-      // Recurse onto this node via a tail call.
-      DFSStack.push_back(std::make_pair(ChildN, ChildN->begin()));
-      return LazyCallGraph::getNextSCCInPostOrder();
-    }
-
-    // Track the lowest link of the childen, if any are still in the stack.
-    if (ChildN->LowLink < N->LowLink && !SCCMap.count(&ChildN->getFunction()))
-      N->LowLink = ChildN->LowLink;
-  }
-
+LazyCallGraph::SCC *LazyCallGraph::formSCCFromDFSStack(
+    SmallVectorImpl<std::pair<Node *, Node::iterator>> &DFSStack) {
   // The tail of the stack is the new SCC. Allocate the SCC and pop the stack
   // into it.
   SCC *NewSCC = new (SCCBPA.Allocate()) SCC();
@@ -197,10 +160,10 @@ LazyCallGraph::SCC *LazyCallGraph::getNextSCCInPostOrder() {
   // Because we don't follow the strict Tarjan recursive formulation, walk
   // from the top of the stack down, propagating the lowest link and stopping
   // when the DFS number is the lowest link.
-  int LowestLink = N->LowLink;
+  int LowestLink = DFSStack.back().first->LowLink;
   do {
     Node *SCCN = DFSStack.pop_back_val().first;
-    SCCMap.insert(std::make_pair(&SCCN->getFunction(), NewSCC));
+    SCCMap[&SCCN->getFunction()] = NewSCC;
     NewSCC->Nodes.push_back(SCCN);
     LowestLink = std::min(LowestLink, SCCN->LowLink);
     bool Inserted =
@@ -233,6 +196,49 @@ LazyCallGraph::SCC *LazyCallGraph::getNextSCCInPostOrder() {
   return NewSCC;
 }
 
+LazyCallGraph::SCC *LazyCallGraph::getNextSCCInPostOrder() {
+  // When the stack is empty, there are no more SCCs to walk in this graph.
+  if (DFSStack.empty()) {
+    // If we've handled all candidate entry nodes to the SCC forest, we're done.
+    if (SCCEntryNodes.empty())
+      return nullptr;
+
+    Node *N = get(*SCCEntryNodes.pop_back_val());
+    DFSStack.push_back(std::make_pair(N, N->begin()));
+  }
+
+  Node *N = DFSStack.back().first;
+  if (N->DFSNumber == 0) {
+    // This node hasn't been visited before, assign it a DFS number and remove
+    // it from the entry set.
+    N->LowLink = N->DFSNumber = NextDFSNumber++;
+    SCCEntryNodes.remove(&N->getFunction());
+  }
+
+  for (auto I = DFSStack.back().second, E = N->end(); I != E; ++I) {
+    Node *ChildN = *I;
+    if (ChildN->DFSNumber == 0) {
+      // Mark that we should start at this child when next this node is the
+      // top of the stack. We don't start at the next child to ensure this
+      // child's lowlink is reflected.
+      // FIXME: I don't actually think this is required, and we could start
+      // at the next child.
+      DFSStack.back().second = I;
+
+      // Recurse onto this node via a tail call.
+      DFSStack.push_back(std::make_pair(ChildN, ChildN->begin()));
+      return LazyCallGraph::getNextSCCInPostOrder();
+    }
+
+    // Track the lowest link of the childen, if any are still in the stack.
+    if (ChildN->LowLink < N->LowLink && !SCCMap.count(&ChildN->getFunction()))
+      N->LowLink = ChildN->LowLink;
+  }
+
+  // Form the new SCC out of the top of the DFS stack.
+  return formSCCFromDFSStack(DFSStack);
+}
+
 char LazyCallGraphAnalysis::PassID;
 
 LazyCallGraphPrinterPass::LazyCallGraphPrinterPass(raw_ostream &OS) : OS(OS) {}
-- 
cgit v1.2.3