diff options
author | Chandler Carruth <chandlerc@gmail.com> | 2014-04-23 10:31:17 +0000 |
---|---|---|
committer | Chandler Carruth <chandlerc@gmail.com> | 2014-04-23 10:31:17 +0000 |
commit | b9619110af557a73bf18c504d061d2cbb8507de2 (patch) | |
tree | 786d0ab1a015a0e7443d89e38f04f8de721fb973 /unittests/Analysis | |
parent | 57683b8abad0c6144cb5e88172509c3afc9fc97a (diff) | |
download | llvm-b9619110af557a73bf18c504d061d2cbb8507de2.tar.gz llvm-b9619110af557a73bf18c504d061d2cbb8507de2.tar.bz2 llvm-b9619110af557a73bf18c504d061d2cbb8507de2.tar.xz |
[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
Diffstat (limited to 'unittests/Analysis')
-rw-r--r-- | unittests/Analysis/LazyCallGraphTest.cpp | 57 |
1 files changed, 57 insertions, 0 deletions
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<Module> 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())); +} + } |