diff options
author | Chandler Carruth <chandlerc@gmail.com> | 2014-05-01 12:12:42 +0000 |
---|---|---|
committer | Chandler Carruth <chandlerc@gmail.com> | 2014-05-01 12:12:42 +0000 |
commit | b8f462501b625cff6835ea8ff290e4b6524cf400 (patch) | |
tree | 9c23e2fbf508d96ab67baeb70670fa197989d3d3 | |
parent | 217b5866d1449b68d51fba0f654e30afb9dd9418 (diff) | |
download | llvm-b8f462501b625cff6835ea8ff290e4b6524cf400.tar.gz llvm-b8f462501b625cff6835ea8ff290e4b6524cf400.tar.bz2 llvm-b8f462501b625cff6835ea8ff290e4b6524cf400.tar.xz |
[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
-rw-r--r-- | include/llvm/Analysis/LazyCallGraph.h | 14 | ||||
-rw-r--r-- | lib/Analysis/LazyCallGraph.cpp | 15 | ||||
-rw-r--r-- | unittests/Analysis/LazyCallGraphTest.cpp | 20 |
3 files changed, 49 insertions, 0 deletions
diff --git a/include/llvm/Analysis/LazyCallGraph.h b/include/llvm/Analysis/LazyCallGraph.h index e5dd5cc2ca..df4fddf866 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 6c4574f867..f88fc79fbd 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 ea68fa77c0..24ca2c9433 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); } |