/// \brief Internal helper to insert a callee.
void insertEdgeInternal(Function &Callee);
+ /// \brief Internal helper to insert a callee.
+ void insertEdgeInternal(Node &CalleeN);
+
/// \brief Internal helper to remove a callee from this node.
void removeEdgeInternal(Function &Callee);
/// Note that these methods sometimes have complex runtimes, so be careful
/// how you call them.
+ /// \brief Insert an edge from one node in this SCC to another in this SCC.
+ ///
+ /// By the definition of an SCC, this does not change the nature or make-up
+ /// of any SCCs.
+ void insertIntraSCCEdge(Node &CallerN, Node &CalleeN);
+
/// \brief Remove an edge whose source is in this SCC and target is *not*.
///
/// This removes an inter-SCC edge. All inter-SCC edges originating from
}
void LazyCallGraph::Node::insertEdgeInternal(Function &Callee) {
- CalleeIndexMap.insert(std::make_pair(&Callee, Callees.size()));
if (Node *N = G->lookup(Callee))
- Callees.push_back(N);
- else
- Callees.push_back(&Callee);
+ return insertEdgeInternal(*N);
+
+ CalleeIndexMap.insert(std::make_pair(&Callee, Callees.size()));
+ Callees.push_back(&Callee);
+}
+
+void LazyCallGraph::Node::insertEdgeInternal(Node &CalleeN) {
+ CalleeIndexMap.insert(std::make_pair(&CalleeN.getFunction(), Callees.size()));
+ Callees.push_back(&CalleeN);
}
void LazyCallGraph::Node::removeEdgeInternal(Function &Callee) {
G->SCCMap[&N] = this;
}
+void LazyCallGraph::SCC::insertIntraSCCEdge(Node &CallerN, Node &CalleeN) {
+ // First insert it into the caller.
+ CallerN.insertEdgeInternal(CalleeN);
+
+ assert(G->SCCMap.lookup(&CallerN) == this && "Caller must be in this SCC.");
+ assert(G->SCCMap.lookup(&CalleeN) == this && "Callee must be in this SCC.");
+
+ // Nothing changes about this SCC or any other.
+}
+
void LazyCallGraph::SCC::removeInterSCCEdge(Node &CallerN, Node &CalleeN) {
// First remove it from the node.
CallerN.removeEdgeInternal(CalleeN.getFunction());
EXPECT_EQ(BC.parent_end(), BC.parent_begin());
}
+TEST(LazyCallGraphTest, IntraSCCEdgeInsertion) {
+ std::unique_ptr<Module> M1 = parseAssembly(
+ "define void @a() {\n"
+ "entry:\n"
+ " call void @b()\n"
+ " ret void\n"
+ "}\n"
+ "define void @b() {\n"
+ "entry:\n"
+ " call void @c()\n"
+ " ret void\n"
+ "}\n"
+ "define void @c() {\n"
+ "entry:\n"
+ " call void @a()\n"
+ " ret void\n"
+ "}\n");
+ LazyCallGraph CG1(*M1);
+
+ // Force the graph to be fully expanded.
+ auto SCCI = CG1.postorder_scc_begin();
+ LazyCallGraph::SCC &SCC = *SCCI++;
+ EXPECT_EQ(CG1.postorder_scc_end(), SCCI);
+
+ LazyCallGraph::Node &A = *CG1.lookup(lookupFunction(*M1, "a"));
+ LazyCallGraph::Node &B = *CG1.lookup(lookupFunction(*M1, "b"));
+ LazyCallGraph::Node &C = *CG1.lookup(lookupFunction(*M1, "c"));
+ EXPECT_EQ(&SCC, CG1.lookupSCC(A));
+ EXPECT_EQ(&SCC, CG1.lookupSCC(B));
+ EXPECT_EQ(&SCC, CG1.lookupSCC(C));
+
+ // Insert an edge from 'a' to 'c'. Nothing changes about the SCCs.
+ SCC.insertIntraSCCEdge(A, C);
+ EXPECT_EQ(2, std::distance(A.begin(), A.end()));
+ EXPECT_EQ(&SCC, CG1.lookupSCC(A));
+ EXPECT_EQ(&SCC, CG1.lookupSCC(B));
+ EXPECT_EQ(&SCC, CG1.lookupSCC(C));
+
+ // Insert a self edge from 'a' back to 'a'.
+ SCC.insertIntraSCCEdge(A, A);
+ EXPECT_EQ(3, std::distance(A.begin(), A.end()));
+ EXPECT_EQ(&SCC, CG1.lookupSCC(A));
+ EXPECT_EQ(&SCC, CG1.lookupSCC(B));
+ EXPECT_EQ(&SCC, CG1.lookupSCC(C));
+}
+
TEST(LazyCallGraphTest, IntraSCCEdgeRemoval) {
// A nice fully connected (including self-edges) SCC.
std::unique_ptr<Module> M1 = parseAssembly(