[LCG] Add support for building persistent and connected SCCs to the

LazyCallGraph. This is the start of the whole point of this different
abstraction, but it is just the initial bits. Here is a run-down of
what's going on here. I'm planning to incorporate some (or all) of this
into comments going forward, hopefully with better editing and wording.
=]

The crux of the problem with the traditional way of building SCCs is
that they are ephemeral. The new pass manager however really needs the
ability to associate analysis passes and results of analysis passes with
SCCs in order to expose these analysis passes to the SCC passes. Making
this work is kind-of the whole point of the new pass manager. =]

So, when we're building SCCs for the call graph, we actually want to
build persistent nodes that stick around and can be reasoned about
later. We'd also like the ability to walk the SCC graph in more complex
ways than just the traditional postorder traversal of the current CGSCC
walk. That means that in addition to being persistent, the SCCs need to
be connected into a useful graph structure.

However, we still want the SCCs to be formed lazily where possible.

These constraints are quite hard to satisfy with the SCC iterator. Also,
using that would bypass our ability to actually add data to the nodes of
the call graph to facilite implementing the Tarjan walk. So I've
re-implemented things in a more direct and embedded way. This
immediately makes it easy to get the persistence and connectivity
correct, and it also allows leveraging the existing nodes to simplify
the algorithm. I've worked somewhat to make this implementation more
closely follow the traditional paper's nomenclature and strategy,
although it is still a bit obtuse because it isn't recursive, using
an explicit stack and a tail call instead, and it is interruptable,
resuming each time we need another SCC.

The other tricky bit here, and what actually took almost all the time
and trials and errors I spent building this, is exactly *what* graph
structure to build for the SCCs. The naive thing to build is the call
graph in its newly acyclic form. I wrote about 4 versions of this which
did precisely this. Inevitably, when I experimented with them across
various use cases, they became incredibly awkward. It was all
implementable, but it felt like a complete wrong fit. Square peg, round
hole. There were two overriding aspects that pushed me in a different
direction:

1) We want to discover the SCC graph in a postorder fashion. That means
   the root node will be the *last* node we find. Using the call-SCC DAG
   as the graph structure of the SCCs results in an orphaned graph until
   we discover a root.

2) We will eventually want to walk the SCC graph in parallel, exploring
   distinct sub-graphs independently, and synchronizing at merge points.
   This again is not helped by the call-SCC DAG structure.

The structure which, quite surprisingly, ended up being completely
natural to use is the *inverse* of the call-SCC DAG. We add the leaf
SCCs to the graph as "roots", and have edges to the caller SCCs. Once
I switched to building this structure, everything just fell into place
elegantly.

Aside from general cleanups (there are FIXMEs and too few comments
overall) that are still needed, the other missing piece of this is
support for iterating across levels of the SCC graph. These will become
useful for implementing #2, but they aren't an immediate priority.

Once SCCs are in good shape, I'll be working on adding mutation support
for incremental updates and adding the pass manager that this analysis
enables.

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

1 files changed, 118 insertions, 4 deletions

diff --git a/lib/Analysis/LazyCallGraph.cpp b/lib/Analysis/LazyCallGraph.cpp
index 8a0d00ac49..dd5c7df784 100644
--- a/lib/Analysis/LazyCallGraph.cpp
+++ b/lib/Analysis/LazyCallGraph.cpp
@@ -8,7 +8,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/LazyCallGraph.h"
-#include "llvm/ADT/SCCIterator.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/InstVisitor.h"
 #include "llvm/IR/Instructions.h"
@@ -46,7 +46,8 @@ static void findCallees(
   }
 }
 
-LazyCallGraph::Node::Node(LazyCallGraph &G, Function &F) : G(&G), F(F) {
+LazyCallGraph::Node::Node(LazyCallGraph &G, Function &F)
+    : G(&G), F(F), DFSNumber(0), LowLink(0) {
   SmallVector<Constant *, 16> Worklist;
   SmallPtrSet<Constant *, 16> Visited;
   // Find all the potential callees in this function. First walk the
@@ -65,7 +66,7 @@ LazyCallGraph::Node::Node(LazyCallGraph &G, Function &F) : G(&G), F(F) {
 }
 
 LazyCallGraph::Node::Node(LazyCallGraph &G, const Node &OtherN)
-    : G(&G), F(OtherN.F), CalleeSet(OtherN.CalleeSet) {
+    : G(&G), F(OtherN.F), DFSNumber(0), LowLink(0), CalleeSet(OtherN.CalleeSet) {
   // Loop over the other node's callees, adding the Function*s to our list
   // directly, and recursing to add the Node*s.
   Callees.reserve(OtherN.Callees.size());
@@ -91,6 +92,12 @@ LazyCallGraph::LazyCallGraph(Module &M) {
         Worklist.push_back(GV.getInitializer());
 
   findCallees(Worklist, Visited, EntryNodes, EntryNodeSet);
+
+  for (auto &Entry : EntryNodes)
+    if (Function *F = Entry.dyn_cast<Function *>())
+      SCCEntryNodes.insert(F);
+    else
+      SCCEntryNodes.insert(&Entry.get<Node *>()->getFunction());
 }
 
 LazyCallGraph::LazyCallGraph(const LazyCallGraph &G)
@@ -101,11 +108,22 @@ LazyCallGraph::LazyCallGraph(const LazyCallGraph &G)
       EntryNodes.push_back(Callee);
     else
       EntryNodes.push_back(copyInto(*EntryNode.get<Node *>()));
+
+  // Just re-populate the SCCEntryNodes structure so we recompute the SCCs if
+  // needed.
+  for (auto &Entry : EntryNodes)
+    if (Function *F = Entry.dyn_cast<Function *>())
+      SCCEntryNodes.insert(F);
+    else
+      SCCEntryNodes.insert(&Entry.get<Node *>()->getFunction());
 }
 
 LazyCallGraph::LazyCallGraph(LazyCallGraph &&G)
     : BPA(std::move(G.BPA)), EntryNodes(std::move(G.EntryNodes)),
-      EntryNodeSet(std::move(G.EntryNodeSet)) {
+      EntryNodeSet(std::move(G.EntryNodeSet)), SCCBPA(std::move(G.SCCBPA)),
+      SCCMap(std::move(G.SCCMap)), LeafSCCs(std::move(G.LeafSCCs)),
+      DFSStack(std::move(G.DFSStack)),
+      SCCEntryNodes(std::move(G.SCCEntryNodes)) {
   // Process all nodes updating the graph pointers.
   SmallVector<Node *, 16> Worklist;
   for (auto &Entry : EntryNodes)
@@ -133,6 +151,88 @@ LazyCallGraph::Node *LazyCallGraph::copyInto(const Node &OtherN) {
   return new (N = BPA.Allocate()) Node(*this, OtherN);
 }
 
+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;
+  }
+
+  // The tail of the stack is the new SCC. Allocate the SCC and pop the stack
+  // into it.
+  SCC *NewSCC = new (SCCBPA.Allocate()) SCC();
+
+  // 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;
+  do {
+    Node *SCCN = DFSStack.pop_back_val().first;
+    SCCMap.insert(std::make_pair(&SCCN->getFunction(), NewSCC));
+    NewSCC->Nodes.push_back(SCCN);
+    LowestLink = std::min(LowestLink, SCCN->LowLink);
+    bool Inserted =
+        NewSCC->NodeSet.insert(&SCCN->getFunction());
+    (void)Inserted;
+    assert(Inserted && "Cannot have duplicates in the DFSStack!");
+  } while (!DFSStack.empty() && LowestLink <= DFSStack.back().first->DFSNumber);
+  assert(LowestLink == NewSCC->Nodes.back()->DFSNumber &&
+         "Cannot stop with a DFS number greater than the lowest link!");
+
+  // A final pass over all edges in the SCC (this remains linear as we only
+  // do this once when we build the SCC) to connect it to the parent sets of
+  // its children.
+  bool IsLeafSCC = true;
+  for (Node *SCCN : NewSCC->Nodes)
+    for (Node *SCCChildN : *SCCN) {
+      if (NewSCC->NodeSet.count(&SCCChildN->getFunction()))
+        continue;
+      SCC *ChildSCC = SCCMap.lookup(&SCCChildN->getFunction());
+      assert(ChildSCC &&
+             "Must have all child SCCs processed when building a new SCC!");
+      ChildSCC->ParentSCCs.insert(NewSCC);
+      IsLeafSCC = false;
+    }
+
+  // For the SCCs where we fine no child SCCs, add them to the leaf list.
+  if (IsLeafSCC)
+    LeafSCCs.push_back(NewSCC);
+
+  return NewSCC;
+}
+
 char LazyCallGraphAnalysis::PassID;
 
 LazyCallGraphPrinterPass::LazyCallGraphPrinterPass(raw_ostream &OS) : OS(OS) {}
@@ -151,6 +251,16 @@ static void printNodes(raw_ostream &OS, LazyCallGraph::Node &N,
   OS << "\n";
 }
 
+static void printSCC(raw_ostream &OS, LazyCallGraph::SCC &SCC) {
+  ptrdiff_t SCCSize = std::distance(SCC.begin(), SCC.end());
+  OS << "  SCC with " << SCCSize << " functions:\n";
+
+  for (LazyCallGraph::Node *N : SCC)
+    OS << "    " << N->getFunction().getName() << "\n";
+
+  OS << "\n";
+}
+
 PreservedAnalyses LazyCallGraphPrinterPass::run(Module *M,
                                                 ModuleAnalysisManager *AM) {
   LazyCallGraph &G = AM->getResult<LazyCallGraphAnalysis>(M);
@@ -163,5 +273,9 @@ PreservedAnalyses LazyCallGraphPrinterPass::run(Module *M,
     if (Printed.insert(N))
       printNodes(OS, *N, Printed);
 
+  for (LazyCallGraph::SCC *SCC : G.postorder_sccs())
+    printSCC(OS, *SCC);
+
   return PreservedAnalyses::all();
+
 }