[LCG] Incorporate the core trick of improvements on the naive Tarjan's

algorithm here: http://dl.acm.org/citation.cfm?id=177301.

The idea of isolating the roots has even more relevance when using the
stack not just to implement the DFS but also to implement the recursive
step. Because we use it for the recursive step, to isolate the roots we
need to maintain two stacks: one for our recursive DFS walk, and another
of the nodes that have been walked. The nice thing is that the latter
will be half the size. It also fixes a complete hack where we scanned
backwards over the stack to find the next potential-root to continue
processing. Now that is always the top of the DFS stack.

While this is a really nice improvement already (IMO) it further opens
the door for two important simplifications:

1) De-duplicating some of the code across the two different walks. I've
   actually made the duplication a bit worse in some senses with this
   patch because the two are starting to converge.
2) Dramatically simplifying the loop structures of both walks.

I wanted to do those separately as they'll be essentially *just* CFG
restructuring. This patch on the other hand actually uses different
datastructures to implement the algorithm itself.

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

1 files changed, 5 insertions, 4 deletions

diff --git a/include/llvm/Analysis/LazyCallGraph.h b/include/llvm/Analysis/LazyCallGraph.h
index b53e77b4f7..2ed3cd0d13 100644
--- a/include/llvm/Analysis/LazyCallGraph.h
+++ b/include/llvm/Analysis/LazyCallGraph.h
@@ -370,12 +370,15 @@ private:
   /// These are all of the SCCs which have no children.
   SmallVector<SCC *, 4> LeafSCCs;
 
-  /// \brief Stack of nodes not-yet-processed into SCCs.
+  /// \brief Stack of nodes in the DFS walk.
   SmallVector<std::pair<Node *, iterator>, 4> DFSStack;
 
   /// \brief Set of entry nodes not-yet-processed into SCCs.
   SmallSetVector<Function *, 4> SCCEntryNodes;
 
+  /// \brief Stack of nodes the DFS has walked but not yet put into a SCC.
+  SmallVector<Node *, 4> PendingSCCStack;
+
   /// \brief Counter for the next DFS number to assign.
   int NextDFSNumber;
 
@@ -388,9 +391,7 @@ private:
 
   /// \brief Helper to form a new SCC out of the top of a DFSStack-like
   /// structure.
-  SCC *formSCCFromDFSStack(
-      SmallVectorImpl<std::pair<Node *, Node::iterator>> &DFSStack,
-      SmallVectorImpl<std::pair<Node *, Node::iterator>>::iterator SCCBegin);
+  SCC *formSCC(Node *RootN, SmallVectorImpl<Node *> &NodeStack);
 
   /// \brief Retrieve the next node in the post-order SCC walk of the call graph.
   SCC *getNextSCCInPostOrder();