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
///
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);
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)
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)
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)
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);
}