[LCG] Add utilities to compute parent and ascestor relationships between SCCs.

[chandlerc]

Summary

These will be fairly expensive routines to call and might be abused in
real code, but are quite useful when debugging or in asserts and are
reasonable and well formed properties to query.

I've used one of them in an assert that was requested in a code review
here.

My real question: are these utilities worth adding now that we see the
amount of code involved? I just want to double check that this is what
was expected when it was brought up in code review.

Provided this is what we want, I'll add more comprehensive coverage of
these routines in the unittests to make sure they actually work
correctly, etc. Just wanted the sanity check first.

[sanjoy]

I'm in favor of adding this -- IME verification like this has always paid off (recent examples include the LCSSA verification that @mzolotukhin has been working on).

I do have one comment inline.

lib/Analysis/LazyCallGraph.cpp

212

Why not walk over SCC instances directly? The way you've written these, I think you'll spend time "re-discovering" the SCC structures (that is walking intra-SCC call edges) when that is avoidable.

[reames]

In D25506#571111, @sanjoy wrote:

I'm in favor of adding this -- IME verification like this has always paid off (recent examples include the LCSSA verification that @mzolotukhin has been working on).

I'm also in support for the same reasons.

[chandlerc]

Address Sanjoy's comment.

[chandlerc]

lib/Analysis/LazyCallGraph.cpp

212

Good idea. I was thinking that it wouldn't be any better to do this because we have to walk the nodes anyways, but you're totally right this is much more efficient if it collapses immediately to SCCs. Please have a look and make sure this matches what you expected.

[sanjoy]

lgtm

lib/Analysis/LazyCallGraph.cpp

1406

I'd drop the "potentially" -- not sure what that means here.

include/llvm/Analysis/LazyCallGraph.h

public:
 
     iterator begin() const { return Nodes.begin(); }
     iterator end() const { return Nodes.end(); }
 
     int size() const { return Nodes.size(); }
 
     RefSCC &getOuterRefSCC() const { return *OuterRefSCC; }
 
+    /// Test if this SCC is a parent of \a C.
+    ///
+    /// Note that this is linear in the number of edges departing the current
+    /// SCC.
+    bool isParentOf(const SCC &C) const;
+
+    /// Test if this SCC is an ancestor of \a C.
+    ///
+    /// Note that in the worst case this is linear in the number of edges
+    /// departing the current SCC and every SCC in the entire graph reachable
+    /// from this SCC. Thus this very well may walk every edge in the entire
+    /// call graph! Do not call this in a tight loop!
+    bool isAncestorOf(const SCC &C) const;
+
+    /// Test if this SCC is a child of \a C.
+    ///
+    /// See the comments for \c isParentOf for detailed notes about the
+    /// complexity of this routine.
+    bool isChildOf(const SCC &C) const { return C.isParentOf(*this); }
+
+    /// Test if this SCC is a descendant of \a C.
+    ///
+    /// See the comments for \c isParentOf for detailed notes about the
+    /// complexity of this routine.
+    bool isDescendantOf(const SCC &C) const { return C.isAncestorOf(*this); }
+
     /// Provide a short name by printing this SCC to a std::string.
     ///
     /// This copes with the fact that we don't have a name per-se for an SCC
     /// while still making the use of this in debugging and logging useful.
     std::string getName() const {
       std::string Name;
       raw_string_ostream OS(Name);
       OS << *this;

lib/Analysis/LazyCallGraph.cpp

for (Node *N : Nodes) {
     assert(N->LowLink == -1 &&
            "Must set low link to -1 when adding a node to an SCC!");
     for (Edge &E : *N)
       assert(E.getNode() && "Can't have an edge to a raw function!");
   }
 }
 #endif
 
+bool LazyCallGraph::SCC::isParentOf(const SCC &C) const {
+  if (this == &C)
+    return false;
+
+  for (Node &N : *this)
+    for (Edge &E : N.calls())
+      if (Node *CalleeN = E.getNode())
+        if (OuterRefSCC->G->lookupSCC(*CalleeN) == &C)
+          return true;
+
+  // No edges found.
+  return false;
+}
+
+bool LazyCallGraph::SCC::isAncestorOf(const SCC &C) const {
+  if (this == &C)
+    return false;
+
+  LazyCallGraph &G = *OuterRefSCC->G;
+
+  // Start with the nodes in this SCC.
+  SmallPtrSet<Node *, 16> Visited(Nodes.begin(), Nodes.end());
+  SmallVector<Node *, 16> Worklist(Nodes.begin(), Nodes.end());
+
+  // Walk down the graph until we run out of edges or find a path to C.
+  do {
+    Node &N = *Worklist.pop_back_val();
+    for (Edge &E : N.calls()) {
+      Node *CalleeN = E.getNode();
+      if (!CalleeN)
+        continue;
+      // Don't revisit nodes we've already checked (and queued).
+      if (!Visited.insert(CalleeN).second)
+        continue;
+
+      // If this node is in C, we're done.
+      if (G.lookupSCC(*CalleeN) == &C)
+        return true;
+
+      // Otherwise put it on the worklist.
+      Worklist.push_back(CalleeN);
+    }
+  } while (!Worklist.empty());
+
+  // No paths found.
+  return false;
+}
+
 LazyCallGraph::RefSCC::RefSCC(LazyCallGraph &G) : G(&G) {}
 
 void LazyCallGraph::RefSCC::dump() const {
   dbgs() << *this << '\n';
 }
 
 #ifndef NDEBUG
 void LazyCallGraph::RefSCC::verify() {
void LazyCallGraph::RefSCC::handleTrivialEdgeInsertion(Node &SourceN,
   TargetRC.Parents.insert(this);
 }
 
 void LazyCallGraph::RefSCC::insertTrivialCallEdge(Node &SourceN,
                                                   Node &TargetN) {
 #ifndef NDEBUG
   // Check that the RefSCC is still valid when we finish.
   auto ExitVerifier = make_scope_exit([this] { verify(); });
+
+  // Check that we aren't potentially breaking some invariants of the SCC graph.
+  SCC &SourceC = *G->lookupSCC(SourceN);
+  SCC &TargetC = *G->lookupSCC(TargetN);
+  if (&SourceC != &TargetC)
+    assert(SourceC.isAncestorOf(TargetC) &&
+           "Call edge is not trivial in the SCC graph!");
 #endif
         // First insert it into the source or find the existing edge.
         auto InsertResult = SourceN.EdgeIndexMap.insert(
             {&TargetN.getFunction(), SourceN.Edges.size()});
   if (!InsertResult.second) {
     // Already an edge, just update it.
     Edge &E = SourceN.Edges[InsertResult.first->second];
     if (E.isCall())
       return; // Nothing to do!
     E.setKind(Edge::Call);
   } else {
     // Create the new edge.