From b9619110af557a73bf18c504d061d2cbb8507de2 Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Wed, 23 Apr 2014 10:31:17 +0000 Subject: [LCG] Implement Tarjan's algorithm correctly this time. We have to walk up the stack finishing the exploration of each entries children before we're finished in addition to accounting for their low-links. Added a unittest that really hammers home the need for this with interlocking cycles that would each appear distinct otherwise and crash or compute the wrong result. As part of this, nuke a stale fixme and bring the rest of the implementation still more closely in line with the original algorithm. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206966 91177308-0d34-0410-b5e6-96231b3b80d8 --- unittests/Analysis/LazyCallGraphTest.cpp | 57 ++++++++++++++++++++++++++++++++ 1 file changed, 57 insertions(+) (limited to 'unittests/Analysis') diff --git a/unittests/Analysis/LazyCallGraphTest.cpp b/unittests/Analysis/LazyCallGraphTest.cpp index c224afbbb8..bdb9d15167 100644 --- a/unittests/Analysis/LazyCallGraphTest.cpp +++ b/unittests/Analysis/LazyCallGraphTest.cpp @@ -248,4 +248,61 @@ TEST(LazyCallGraphTest, BasicGraphFormation) { EXPECT_EQ(CG.postorder_scc_end(), SCCI); } +static Function &lookupFunction(Module &M, StringRef Name) { + for (Function &F : M) + if (F.getName() == Name) + return F; + report_fatal_error("Couldn't find function!"); +} + +TEST(LazyCallGraphTest, MultiArmSCC) { + // Two interlocking cycles. The really useful thing about this SCC is that it + // will require Tarjan's DFS to backtrack and finish processing all of the + // children of each node in the SCC. + std::unique_ptr M = parseAssembly( + "define void @a() {\n" + "entry:\n" + " call void @b()\n" + " call void @d()\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" + "define void @d() {\n" + "entry:\n" + " call void @e()\n" + " ret void\n" + "}\n" + "define void @e() {\n" + "entry:\n" + " call void @a()\n" + " ret void\n" + "}\n"); + LazyCallGraph CG(*M); + + // Force the graph to be fully expanded. + auto SCCI = CG.postorder_scc_begin(); + LazyCallGraph::SCC *SCC = *SCCI++; + EXPECT_EQ(CG.postorder_scc_end(), SCCI); + + LazyCallGraph::Node *A = CG.lookup(lookupFunction(*M, "a")); + LazyCallGraph::Node *B = CG.lookup(lookupFunction(*M, "b")); + LazyCallGraph::Node *C = CG.lookup(lookupFunction(*M, "c")); + LazyCallGraph::Node *D = CG.lookup(lookupFunction(*M, "d")); + LazyCallGraph::Node *E = CG.lookup(lookupFunction(*M, "e")); + EXPECT_EQ(SCC, CG.lookupSCC(A->getFunction())); + EXPECT_EQ(SCC, CG.lookupSCC(B->getFunction())); + EXPECT_EQ(SCC, CG.lookupSCC(C->getFunction())); + EXPECT_EQ(SCC, CG.lookupSCC(D->getFunction())); + EXPECT_EQ(SCC, CG.lookupSCC(E->getFunction())); +} + } -- cgit v1.2.3