From b8f462501b625cff6835ea8ff290e4b6524cf400 Mon Sep 17 00:00:00 2001
From: Chandler Carruth <chandlerc@gmail.com>
Date: Thu, 1 May 2014 12:12:42 +0000
Subject: [PATCH] [LCG] Add some basic methods for querying the parent/child
 relationships of SCCs in the SCC DAG. Exercise them in the big graph test
 case. These will be especially useful for establishing invariants in
 insertion logic.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207749 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/Analysis/LazyCallGraph.h    | 14 ++++++++++++++
 lib/Analysis/LazyCallGraph.cpp           | 15 +++++++++++++++
 unittests/Analysis/LazyCallGraphTest.cpp | 20 ++++++++++++++++++++
 3 files changed, 49 insertions(+)

diff --git a/include/llvm/Analysis/LazyCallGraph.h b/include/llvm/Analysis/LazyCallGraph.h
index e5dd5cc2caa..df4fddf8669 100644
--- a/include/llvm/Analysis/LazyCallGraph.h
+++ b/include/llvm/Analysis/LazyCallGraph.h
@@ -238,6 +238,20 @@ public:
       return iterator_range<parent_iterator>(parent_begin(), parent_end());
     }
 
+    /// \brief Test if this SCC is a parent of \a C.
+    bool isParentOf(const SCC &C) const { return C.isChildOf(*this); }
+
+    /// \brief Test if this SCC is an ancestor of \a C.
+    bool isAncestorOf(const SCC &C) const { return C.isDescendantOf(*this); }
+
+    /// \brief Test if this SCC is a child of \a C.
+    bool isChildOf(const SCC &C) const {
+      return ParentSCCs.count(const_cast<SCC *>(&C));
+    }
+
+    /// \brief Test if this SCC is a descendant of \a C.
+    bool isDescendantOf(const SCC &C) const;
+
     ///@{
     /// \name Mutation API
     ///
diff --git a/lib/Analysis/LazyCallGraph.cpp b/lib/Analysis/LazyCallGraph.cpp
index 6c4574f867c..f88fc79fbd7 100644
--- a/lib/Analysis/LazyCallGraph.cpp
+++ b/lib/Analysis/LazyCallGraph.cpp
@@ -162,6 +162,21 @@ void LazyCallGraph::SCC::insert(Node &N) {
   G->SCCMap[&N] = this;
 }
 
+bool LazyCallGraph::SCC::isDescendantOf(const SCC &C) const {
+  // Walk up the parents of this SCC and verify that we eventually find C.
+  SmallVector<const SCC *, 4> AncestorWorklist;
+  AncestorWorklist.push_back(this);
+  do {
+    const SCC *AncestorC = AncestorWorklist.pop_back_val();
+    if (AncestorC->isChildOf(C))
+      return true;
+    for (const SCC *ParentC : AncestorC->ParentSCCs)
+      AncestorWorklist.push_back(ParentC);
+  } while (!AncestorWorklist.empty());
+
+  return false;
+}
+
 void LazyCallGraph::SCC::insertIntraSCCEdge(Node &CallerN, Node &CalleeN) {
   // First insert it into the caller.
   CallerN.insertEdgeInternal(CalleeN);
diff --git a/unittests/Analysis/LazyCallGraphTest.cpp b/unittests/Analysis/LazyCallGraphTest.cpp
index ea68fa77c03..24ca2c9433d 100644
--- a/unittests/Analysis/LazyCallGraphTest.cpp
+++ b/unittests/Analysis/LazyCallGraphTest.cpp
@@ -214,6 +214,10 @@ TEST(LazyCallGraphTest, BasicGraphFormation) {
   EXPECT_EQ("d2", Nodes[1]);
   EXPECT_EQ("d3", Nodes[2]);
   Nodes.clear();
+  EXPECT_FALSE(D.isParentOf(D));
+  EXPECT_FALSE(D.isChildOf(D));
+  EXPECT_FALSE(D.isAncestorOf(D));
+  EXPECT_FALSE(D.isDescendantOf(D));
 
   LazyCallGraph::SCC &C = *SCCI++;
   for (LazyCallGraph::Node *N : C)
@@ -224,6 +228,10 @@ TEST(LazyCallGraphTest, BasicGraphFormation) {
   EXPECT_EQ("c2", Nodes[1]);
   EXPECT_EQ("c3", Nodes[2]);
   Nodes.clear();
+  EXPECT_TRUE(C.isParentOf(D));
+  EXPECT_FALSE(C.isChildOf(D));
+  EXPECT_TRUE(C.isAncestorOf(D));
+  EXPECT_FALSE(C.isDescendantOf(D));
 
   LazyCallGraph::SCC &B = *SCCI++;
   for (LazyCallGraph::Node *N : B)
@@ -234,6 +242,12 @@ TEST(LazyCallGraphTest, BasicGraphFormation) {
   EXPECT_EQ("b2", Nodes[1]);
   EXPECT_EQ("b3", Nodes[2]);
   Nodes.clear();
+  EXPECT_TRUE(B.isParentOf(D));
+  EXPECT_FALSE(B.isChildOf(D));
+  EXPECT_TRUE(B.isAncestorOf(D));
+  EXPECT_FALSE(B.isDescendantOf(D));
+  EXPECT_FALSE(B.isAncestorOf(C));
+  EXPECT_FALSE(C.isAncestorOf(B));
 
   LazyCallGraph::SCC &A = *SCCI++;
   for (LazyCallGraph::Node *N : A)
@@ -244,6 +258,12 @@ TEST(LazyCallGraphTest, BasicGraphFormation) {
   EXPECT_EQ("a2", Nodes[1]);
   EXPECT_EQ("a3", Nodes[2]);
   Nodes.clear();
+  EXPECT_TRUE(A.isParentOf(B));
+  EXPECT_TRUE(A.isParentOf(C));
+  EXPECT_FALSE(A.isParentOf(D));
+  EXPECT_TRUE(A.isAncestorOf(B));
+  EXPECT_TRUE(A.isAncestorOf(C));
+  EXPECT_TRUE(A.isAncestorOf(D));
 
   EXPECT_EQ(CG.postorder_scc_end(), SCCI);
 }
-- 
2.34.1