From 38bd6b50ef500c2bf166593712443c609a3356ba Mon Sep 17 00:00:00 2001
From: Chandler Carruth <chandlerc@gmail.com>
Date: Sat, 5 Aug 2017 06:24:09 +0000
Subject: [PATCH] [LCG] Re-implement the basic isParentOf, isAncestorOf,
 isChildOf, and isDescendantOf methods on RefSCCs in terms of the forward
 edges rather than the parent sets.

This is technically slower, but probably not interestingly slower, and
all of these routines were already so expensive that they're guarded
behind both !NDEBUG and EXPENSIVE_CHECKS.

This removes another non-critical usage of parent sets.

I've also added some comments to try and help clarify to any potential
users the costs of these routines. They're mostly useful for debugging,
asserts, or other queries.

llvm-svn: 310170
---
 llvm/include/llvm/Analysis/LazyCallGraph.h | 34 ++++++++++++++-------
 llvm/lib/Analysis/LazyCallGraph.cpp        | 47 +++++++++++++++++++++++-------
 2 files changed, 61 insertions(+), 20 deletions(-)

diff --git a/llvm/include/llvm/Analysis/LazyCallGraph.h b/llvm/include/llvm/Analysis/LazyCallGraph.h
index 0cf0a6f..05c3136 100644
--- a/llvm/include/llvm/Analysis/LazyCallGraph.h
+++ b/llvm/include/llvm/Analysis/LazyCallGraph.h
@@ -631,19 +631,33 @@ public:
       return make_range(parent_begin(), parent_end());
     }
 
-    /// Test if this RefSCC is a parent of \a C.
-    bool isParentOf(const RefSCC &C) const { return C.isChildOf(*this); }
+    /// Test if this RefSCC is a parent of \a RC.
+    ///
+    /// CAUTION: This method walks every edge in the \c RefSCC, it can be very
+    /// expensive.
+    bool isParentOf(const RefSCC &RC) const;
 
-    /// Test if this RefSCC is an ancestor of \a C.
-    bool isAncestorOf(const RefSCC &C) const { return C.isDescendantOf(*this); }
+    /// Test if this RefSCC is an ancestor of \a RC.
+    ///
+    /// CAUTION: This method walks the directed graph of edges as far as
+    /// necessary to find a possible path to the argument. In the worst case
+    /// this may walk the entire graph and can be extremely expensive.
+    bool isAncestorOf(const RefSCC &RC) const;
 
-    /// Test if this RefSCC is a child of \a C.
-    bool isChildOf(const RefSCC &C) const {
-      return Parents.count(const_cast<RefSCC *>(&C));
-    }
+    /// Test if this RefSCC is a child of \a RC.
+    ///
+    /// CAUTION: This method walks every edge in the argument \c RefSCC, it can
+    /// be very expensive.
+    bool isChildOf(const RefSCC &RC) const { return RC.isParentOf(*this); }
 
-    /// Test if this RefSCC is a descendant of \a C.
-    bool isDescendantOf(const RefSCC &C) const;
+    /// Test if this RefSCC is a descendant of \a RC.
+    ///
+    /// CAUTION: This method walks the directed graph of edges as far as
+    /// necessary to find a possible path from the argument. In the worst case
+    /// this may walk the entire graph and can be extremely expensive.
+    bool isDescendantOf(const RefSCC &RC) const {
+      return RC.isAncestorOf(*this);
+    }
 
     /// Provide a short name by printing this RefSCC to a std::string.
     ///
diff --git a/llvm/lib/Analysis/LazyCallGraph.cpp b/llvm/lib/Analysis/LazyCallGraph.cpp
index 6c55a3f..4bdfbda 100644
--- a/llvm/lib/Analysis/LazyCallGraph.cpp
+++ b/llvm/lib/Analysis/LazyCallGraph.cpp
@@ -334,17 +334,44 @@ void LazyCallGraph::RefSCC::verify() {
 }
 #endif
 
-bool LazyCallGraph::RefSCC::isDescendantOf(const RefSCC &C) const {
-  // Walk up the parents of this SCC and verify that we eventually find C.
-  SmallVector<const RefSCC *, 4> AncestorWorklist;
-  AncestorWorklist.push_back(this);
+bool LazyCallGraph::RefSCC::isParentOf(const RefSCC &RC) const {
+  if (&RC == this)
+    return false;
+
+  // Search all edges to see if this is a parent.
+  for (SCC &C : *this)
+    for (Node &N : C)
+      for (Edge &E : *N)
+        if (G->lookupRefSCC(E.getNode()) == &RC)
+          return true;
+
+  return false;
+}
+
+bool LazyCallGraph::RefSCC::isAncestorOf(const RefSCC &RC) const {
+  if (&RC == this)
+    return false;
+
+  // For each descendant of this RefSCC, see if one of its children is the
+  // argument. If not, add that descendant to the worklist and continue
+  // searching.
+  SmallVector<const RefSCC *, 4> Worklist;
+  SmallPtrSet<const RefSCC *, 4> Visited;
+  Worklist.push_back(this);
+  Visited.insert(this);
   do {
-    const RefSCC *AncestorC = AncestorWorklist.pop_back_val();
-    if (AncestorC->isChildOf(C))
-      return true;
-    for (const RefSCC *ParentC : AncestorC->Parents)
-      AncestorWorklist.push_back(ParentC);
-  } while (!AncestorWorklist.empty());
+    const RefSCC &DescendantRC = *Worklist.pop_back_val();
+    for (SCC &C : DescendantRC)
+      for (Node &N : C)
+        for (Edge &E : *N) {
+          auto *ChildRC = G->lookupRefSCC(E.getNode());
+          if (ChildRC == &RC)
+            return true;
+          if (!ChildRC || !Visited.insert(ChildRC).second)
+            continue;
+          Worklist.push_back(ChildRC);
+        }
+  } while (!Worklist.empty());
 
   return false;
 }
-- 
2.7.4