diff options
Diffstat (limited to 'gnu/llvm/unittests/Analysis/LazyCallGraphTest.cpp')
| -rw-r--r-- | gnu/llvm/unittests/Analysis/LazyCallGraphTest.cpp | 2142 |
1 files changed, 0 insertions, 2142 deletions
diff --git a/gnu/llvm/unittests/Analysis/LazyCallGraphTest.cpp b/gnu/llvm/unittests/Analysis/LazyCallGraphTest.cpp deleted file mode 100644 index 5e6dd1aee5a..00000000000 --- a/gnu/llvm/unittests/Analysis/LazyCallGraphTest.cpp +++ /dev/null @@ -1,2142 +0,0 @@ -//===- LazyCallGraphTest.cpp - Unit tests for the lazy CG analysis --------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/LazyCallGraph.h" -#include "llvm/AsmParser/Parser.h" -#include "llvm/IR/Function.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/LLVMContext.h" -#include "llvm/IR/Module.h" -#include "llvm/Support/ErrorHandling.h" -#include "llvm/Support/SourceMgr.h" -#include "gtest/gtest.h" -#include <memory> - -using namespace llvm; - -namespace { - -std::unique_ptr<Module> parseAssembly(LLVMContext &Context, - const char *Assembly) { - SMDiagnostic Error; - std::unique_ptr<Module> M = parseAssemblyString(Assembly, Error, Context); - - std::string ErrMsg; - raw_string_ostream OS(ErrMsg); - Error.print("", OS); - - // A failure here means that the test itself is buggy. - if (!M) - report_fatal_error(OS.str().c_str()); - - return M; -} - -/* - IR forming a call graph with a diamond of triangle-shaped SCCs: - - d1 - / \ - d3--d2 - / \ - b1 c1 - / \ / \ - b3--b2 c3--c2 - \ / - a1 - / \ - a3--a2 - - All call edges go up between SCCs, and clockwise around the SCC. - */ -static const char DiamondOfTriangles[] = - "define void @a1() {\n" - "entry:\n" - " call void @a2()\n" - " call void @b2()\n" - " call void @c3()\n" - " ret void\n" - "}\n" - "define void @a2() {\n" - "entry:\n" - " call void @a3()\n" - " ret void\n" - "}\n" - "define void @a3() {\n" - "entry:\n" - " call void @a1()\n" - " ret void\n" - "}\n" - "define void @b1() {\n" - "entry:\n" - " call void @b2()\n" - " call void @d3()\n" - " ret void\n" - "}\n" - "define void @b2() {\n" - "entry:\n" - " call void @b3()\n" - " ret void\n" - "}\n" - "define void @b3() {\n" - "entry:\n" - " call void @b1()\n" - " ret void\n" - "}\n" - "define void @c1() {\n" - "entry:\n" - " call void @c2()\n" - " call void @d2()\n" - " ret void\n" - "}\n" - "define void @c2() {\n" - "entry:\n" - " call void @c3()\n" - " ret void\n" - "}\n" - "define void @c3() {\n" - "entry:\n" - " call void @c1()\n" - " ret void\n" - "}\n" - "define void @d1() {\n" - "entry:\n" - " call void @d2()\n" - " ret void\n" - "}\n" - "define void @d2() {\n" - "entry:\n" - " call void @d3()\n" - " ret void\n" - "}\n" - "define void @d3() {\n" - "entry:\n" - " call void @d1()\n" - " ret void\n" - "}\n"; - -/* - IR forming a reference graph with a diamond of triangle-shaped RefSCCs - - d1 - / \ - d3--d2 - / \ - b1 c1 - / \ / \ - b3--b2 c3--c2 - \ / - a1 - / \ - a3--a2 - - All call edges go up between RefSCCs, and clockwise around the RefSCC. - */ -static const char DiamondOfTrianglesRefGraph[] = - "define void @a1() {\n" - "entry:\n" - " %a = alloca void ()*\n" - " store void ()* @a2, void ()** %a\n" - " store void ()* @b2, void ()** %a\n" - " store void ()* @c3, void ()** %a\n" - " ret void\n" - "}\n" - "define void @a2() {\n" - "entry:\n" - " %a = alloca void ()*\n" - " store void ()* @a3, void ()** %a\n" - " ret void\n" - "}\n" - "define void @a3() {\n" - "entry:\n" - " %a = alloca void ()*\n" - " store void ()* @a1, void ()** %a\n" - " ret void\n" - "}\n" - "define void @b1() {\n" - "entry:\n" - " %a = alloca void ()*\n" - " store void ()* @b2, void ()** %a\n" - " store void ()* @d3, void ()** %a\n" - " ret void\n" - "}\n" - "define void @b2() {\n" - "entry:\n" - " %a = alloca void ()*\n" - " store void ()* @b3, void ()** %a\n" - " ret void\n" - "}\n" - "define void @b3() {\n" - "entry:\n" - " %a = alloca void ()*\n" - " store void ()* @b1, void ()** %a\n" - " ret void\n" - "}\n" - "define void @c1() {\n" - "entry:\n" - " %a = alloca void ()*\n" - " store void ()* @c2, void ()** %a\n" - " store void ()* @d2, void ()** %a\n" - " ret void\n" - "}\n" - "define void @c2() {\n" - "entry:\n" - " %a = alloca void ()*\n" - " store void ()* @c3, void ()** %a\n" - " ret void\n" - "}\n" - "define void @c3() {\n" - "entry:\n" - " %a = alloca void ()*\n" - " store void ()* @c1, void ()** %a\n" - " ret void\n" - "}\n" - "define void @d1() {\n" - "entry:\n" - " %a = alloca void ()*\n" - " store void ()* @d2, void ()** %a\n" - " ret void\n" - "}\n" - "define void @d2() {\n" - "entry:\n" - " %a = alloca void ()*\n" - " store void ()* @d3, void ()** %a\n" - " ret void\n" - "}\n" - "define void @d3() {\n" - "entry:\n" - " %a = alloca void ()*\n" - " store void ()* @d1, void ()** %a\n" - " ret void\n" - "}\n"; - -static LazyCallGraph buildCG(Module &M) { - TargetLibraryInfoImpl TLII(Triple(M.getTargetTriple())); - TargetLibraryInfo TLI(TLII); - LazyCallGraph CG(M, TLI); - return CG; -} - -TEST(LazyCallGraphTest, BasicGraphFormation) { - LLVMContext Context; - std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles); - LazyCallGraph CG = buildCG(*M); - - // The order of the entry nodes should be stable w.r.t. the source order of - // the IR, and everything in our module is an entry node, so just directly - // build variables for each node. - auto I = CG.begin(); - LazyCallGraph::Node &A1 = (I++)->getNode(); - EXPECT_EQ("a1", A1.getFunction().getName()); - LazyCallGraph::Node &A2 = (I++)->getNode(); - EXPECT_EQ("a2", A2.getFunction().getName()); - LazyCallGraph::Node &A3 = (I++)->getNode(); - EXPECT_EQ("a3", A3.getFunction().getName()); - LazyCallGraph::Node &B1 = (I++)->getNode(); - EXPECT_EQ("b1", B1.getFunction().getName()); - LazyCallGraph::Node &B2 = (I++)->getNode(); - EXPECT_EQ("b2", B2.getFunction().getName()); - LazyCallGraph::Node &B3 = (I++)->getNode(); - EXPECT_EQ("b3", B3.getFunction().getName()); - LazyCallGraph::Node &C1 = (I++)->getNode(); - EXPECT_EQ("c1", C1.getFunction().getName()); - LazyCallGraph::Node &C2 = (I++)->getNode(); - EXPECT_EQ("c2", C2.getFunction().getName()); - LazyCallGraph::Node &C3 = (I++)->getNode(); - EXPECT_EQ("c3", C3.getFunction().getName()); - LazyCallGraph::Node &D1 = (I++)->getNode(); - EXPECT_EQ("d1", D1.getFunction().getName()); - LazyCallGraph::Node &D2 = (I++)->getNode(); - EXPECT_EQ("d2", D2.getFunction().getName()); - LazyCallGraph::Node &D3 = (I++)->getNode(); - EXPECT_EQ("d3", D3.getFunction().getName()); - EXPECT_EQ(CG.end(), I); - - // Build vectors and sort them for the rest of the assertions to make them - // independent of order. - std::vector<std::string> Nodes; - - for (LazyCallGraph::Edge &E : A1.populate()) - Nodes.push_back(E.getFunction().getName()); - llvm::sort(Nodes); - EXPECT_EQ("a2", Nodes[0]); - EXPECT_EQ("b2", Nodes[1]); - EXPECT_EQ("c3", Nodes[2]); - Nodes.clear(); - - A2.populate(); - EXPECT_EQ(A2->end(), std::next(A2->begin())); - EXPECT_EQ("a3", A2->begin()->getFunction().getName()); - A3.populate(); - EXPECT_EQ(A3->end(), std::next(A3->begin())); - EXPECT_EQ("a1", A3->begin()->getFunction().getName()); - - for (LazyCallGraph::Edge &E : B1.populate()) - Nodes.push_back(E.getFunction().getName()); - llvm::sort(Nodes); - EXPECT_EQ("b2", Nodes[0]); - EXPECT_EQ("d3", Nodes[1]); - Nodes.clear(); - - B2.populate(); - EXPECT_EQ(B2->end(), std::next(B2->begin())); - EXPECT_EQ("b3", B2->begin()->getFunction().getName()); - B3.populate(); - EXPECT_EQ(B3->end(), std::next(B3->begin())); - EXPECT_EQ("b1", B3->begin()->getFunction().getName()); - - for (LazyCallGraph::Edge &E : C1.populate()) - Nodes.push_back(E.getFunction().getName()); - llvm::sort(Nodes); - EXPECT_EQ("c2", Nodes[0]); - EXPECT_EQ("d2", Nodes[1]); - Nodes.clear(); - - C2.populate(); - EXPECT_EQ(C2->end(), std::next(C2->begin())); - EXPECT_EQ("c3", C2->begin()->getFunction().getName()); - C3.populate(); - EXPECT_EQ(C3->end(), std::next(C3->begin())); - EXPECT_EQ("c1", C3->begin()->getFunction().getName()); - - D1.populate(); - EXPECT_EQ(D1->end(), std::next(D1->begin())); - EXPECT_EQ("d2", D1->begin()->getFunction().getName()); - D2.populate(); - EXPECT_EQ(D2->end(), std::next(D2->begin())); - EXPECT_EQ("d3", D2->begin()->getFunction().getName()); - D3.populate(); - EXPECT_EQ(D3->end(), std::next(D3->begin())); - EXPECT_EQ("d1", D3->begin()->getFunction().getName()); - - // Now lets look at the RefSCCs and SCCs. - CG.buildRefSCCs(); - auto J = CG.postorder_ref_scc_begin(); - - LazyCallGraph::RefSCC &D = *J++; - ASSERT_EQ(1, D.size()); - for (LazyCallGraph::Node &N : *D.begin()) - Nodes.push_back(N.getFunction().getName()); - llvm::sort(Nodes); - EXPECT_EQ(3u, Nodes.size()); - EXPECT_EQ("d1", Nodes[0]); - 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)); - EXPECT_EQ(&D, &*CG.postorder_ref_scc_begin()); - - LazyCallGraph::RefSCC &C = *J++; - ASSERT_EQ(1, C.size()); - for (LazyCallGraph::Node &N : *C.begin()) - Nodes.push_back(N.getFunction().getName()); - llvm::sort(Nodes); - EXPECT_EQ(3u, Nodes.size()); - EXPECT_EQ("c1", Nodes[0]); - 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)); - EXPECT_EQ(&C, &*std::next(CG.postorder_ref_scc_begin())); - - LazyCallGraph::RefSCC &B = *J++; - ASSERT_EQ(1, B.size()); - for (LazyCallGraph::Node &N : *B.begin()) - Nodes.push_back(N.getFunction().getName()); - llvm::sort(Nodes); - EXPECT_EQ(3u, Nodes.size()); - EXPECT_EQ("b1", Nodes[0]); - 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)); - EXPECT_EQ(&B, &*std::next(CG.postorder_ref_scc_begin(), 2)); - - LazyCallGraph::RefSCC &A = *J++; - ASSERT_EQ(1, A.size()); - for (LazyCallGraph::Node &N : *A.begin()) - Nodes.push_back(N.getFunction().getName()); - llvm::sort(Nodes); - EXPECT_EQ(3u, Nodes.size()); - EXPECT_EQ("a1", Nodes[0]); - 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(&A, &*std::next(CG.postorder_ref_scc_begin(), 3)); - - EXPECT_EQ(CG.postorder_ref_scc_end(), J); - EXPECT_EQ(J, std::next(CG.postorder_ref_scc_begin(), 4)); -} - -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, BasicGraphMutation) { - LLVMContext Context; - std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n" - "entry:\n" - " call void @b()\n" - " call void @c()\n" - " ret void\n" - "}\n" - "define void @b() {\n" - "entry:\n" - " ret void\n" - "}\n" - "define void @c() {\n" - "entry:\n" - " ret void\n" - "}\n"); - LazyCallGraph CG = buildCG(*M); - - LazyCallGraph::Node &A = CG.get(lookupFunction(*M, "a")); - LazyCallGraph::Node &B = CG.get(lookupFunction(*M, "b")); - A.populate(); - EXPECT_EQ(2, std::distance(A->begin(), A->end())); - B.populate(); - EXPECT_EQ(0, std::distance(B->begin(), B->end())); - - LazyCallGraph::Node &C = CG.get(lookupFunction(*M, "c")); - C.populate(); - CG.insertEdge(B, C, LazyCallGraph::Edge::Call); - EXPECT_EQ(1, std::distance(B->begin(), B->end())); - EXPECT_EQ(0, std::distance(C->begin(), C->end())); - - CG.insertEdge(C, B, LazyCallGraph::Edge::Call); - EXPECT_EQ(1, std::distance(C->begin(), C->end())); - EXPECT_EQ(&B, &C->begin()->getNode()); - - CG.insertEdge(C, C, LazyCallGraph::Edge::Call); - EXPECT_EQ(2, std::distance(C->begin(), C->end())); - EXPECT_EQ(&B, &C->begin()->getNode()); - EXPECT_EQ(&C, &std::next(C->begin())->getNode()); - - CG.removeEdge(C, B); - EXPECT_EQ(1, std::distance(C->begin(), C->end())); - EXPECT_EQ(&C, &C->begin()->getNode()); - - CG.removeEdge(C, C); - EXPECT_EQ(0, std::distance(C->begin(), C->end())); - - CG.removeEdge(B, C); - EXPECT_EQ(0, std::distance(B->begin(), B->end())); -} - -TEST(LazyCallGraphTest, InnerSCCFormation) { - LLVMContext Context; - std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles); - LazyCallGraph CG = buildCG(*M); - - // Now mutate the graph to connect every node into a single RefSCC to ensure - // that our inner SCC formation handles the rest. - LazyCallGraph::Node &D1 = CG.get(lookupFunction(*M, "d1")); - LazyCallGraph::Node &A1 = CG.get(lookupFunction(*M, "a1")); - A1.populate(); - D1.populate(); - CG.insertEdge(D1, A1, LazyCallGraph::Edge::Ref); - - // Build vectors and sort them for the rest of the assertions to make them - // independent of order. - std::vector<std::string> Nodes; - - // We should build a single RefSCC for the entire graph. - CG.buildRefSCCs(); - auto I = CG.postorder_ref_scc_begin(); - LazyCallGraph::RefSCC &RC = *I++; - EXPECT_EQ(CG.postorder_ref_scc_end(), I); - - // Now walk the four SCCs which should be in post-order. - auto J = RC.begin(); - LazyCallGraph::SCC &D = *J++; - for (LazyCallGraph::Node &N : D) - Nodes.push_back(N.getFunction().getName()); - llvm::sort(Nodes); - EXPECT_EQ(3u, Nodes.size()); - EXPECT_EQ("d1", Nodes[0]); - EXPECT_EQ("d2", Nodes[1]); - EXPECT_EQ("d3", Nodes[2]); - Nodes.clear(); - - LazyCallGraph::SCC &B = *J++; - for (LazyCallGraph::Node &N : B) - Nodes.push_back(N.getFunction().getName()); - llvm::sort(Nodes); - EXPECT_EQ(3u, Nodes.size()); - EXPECT_EQ("b1", Nodes[0]); - EXPECT_EQ("b2", Nodes[1]); - EXPECT_EQ("b3", Nodes[2]); - Nodes.clear(); - - LazyCallGraph::SCC &C = *J++; - for (LazyCallGraph::Node &N : C) - Nodes.push_back(N.getFunction().getName()); - llvm::sort(Nodes); - EXPECT_EQ(3u, Nodes.size()); - EXPECT_EQ("c1", Nodes[0]); - EXPECT_EQ("c2", Nodes[1]); - EXPECT_EQ("c3", Nodes[2]); - Nodes.clear(); - - LazyCallGraph::SCC &A = *J++; - for (LazyCallGraph::Node &N : A) - Nodes.push_back(N.getFunction().getName()); - llvm::sort(Nodes); - EXPECT_EQ(3u, Nodes.size()); - EXPECT_EQ("a1", Nodes[0]); - EXPECT_EQ("a2", Nodes[1]); - EXPECT_EQ("a3", Nodes[2]); - Nodes.clear(); - - EXPECT_EQ(RC.end(), J); -} - -TEST(LazyCallGraphTest, MultiArmSCC) { - LLVMContext Context; - // 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. Since this involves call edges, both - // Tarjan implementations will have to successfully navigate the structure. - std::unique_ptr<Module> M = parseAssembly(Context, "define void @f1() {\n" - "entry:\n" - " call void @f2()\n" - " call void @f4()\n" - " ret void\n" - "}\n" - "define void @f2() {\n" - "entry:\n" - " call void @f3()\n" - " ret void\n" - "}\n" - "define void @f3() {\n" - "entry:\n" - " call void @f1()\n" - " ret void\n" - "}\n" - "define void @f4() {\n" - "entry:\n" - " call void @f5()\n" - " ret void\n" - "}\n" - "define void @f5() {\n" - "entry:\n" - " call void @f1()\n" - " ret void\n" - "}\n"); - LazyCallGraph CG = buildCG(*M); - - // Force the graph to be fully expanded. - CG.buildRefSCCs(); - auto I = CG.postorder_ref_scc_begin(); - LazyCallGraph::RefSCC &RC = *I++; - EXPECT_EQ(CG.postorder_ref_scc_end(), I); - - LazyCallGraph::Node &N1 = *CG.lookup(lookupFunction(*M, "f1")); - LazyCallGraph::Node &N2 = *CG.lookup(lookupFunction(*M, "f2")); - LazyCallGraph::Node &N3 = *CG.lookup(lookupFunction(*M, "f3")); - LazyCallGraph::Node &N4 = *CG.lookup(lookupFunction(*M, "f4")); - LazyCallGraph::Node &N5 = *CG.lookup(lookupFunction(*M, "f4")); - EXPECT_EQ(&RC, CG.lookupRefSCC(N1)); - EXPECT_EQ(&RC, CG.lookupRefSCC(N2)); - EXPECT_EQ(&RC, CG.lookupRefSCC(N3)); - EXPECT_EQ(&RC, CG.lookupRefSCC(N4)); - EXPECT_EQ(&RC, CG.lookupRefSCC(N5)); - - ASSERT_EQ(1, RC.size()); - - LazyCallGraph::SCC &C = *RC.begin(); - EXPECT_EQ(&C, CG.lookupSCC(N1)); - EXPECT_EQ(&C, CG.lookupSCC(N2)); - EXPECT_EQ(&C, CG.lookupSCC(N3)); - EXPECT_EQ(&C, CG.lookupSCC(N4)); - EXPECT_EQ(&C, CG.lookupSCC(N5)); -} - -TEST(LazyCallGraphTest, OutgoingEdgeMutation) { - LLVMContext Context; - std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n" - "entry:\n" - " call void @b()\n" - " call void @c()\n" - " ret void\n" - "}\n" - "define void @b() {\n" - "entry:\n" - " call void @d()\n" - " ret void\n" - "}\n" - "define void @c() {\n" - "entry:\n" - " call void @d()\n" - " ret void\n" - "}\n" - "define void @d() {\n" - "entry:\n" - " ret void\n" - "}\n"); - LazyCallGraph CG = buildCG(*M); - - // Force the graph to be fully expanded. - CG.buildRefSCCs(); - for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) - dbgs() << "Formed RefSCC: " << RC << "\n"; - - 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::SCC &AC = *CG.lookupSCC(A); - LazyCallGraph::SCC &BC = *CG.lookupSCC(B); - LazyCallGraph::SCC &CC = *CG.lookupSCC(C); - LazyCallGraph::SCC &DC = *CG.lookupSCC(D); - LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A); - LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B); - LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C); - LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D); - EXPECT_TRUE(ARC.isParentOf(BRC)); - EXPECT_TRUE(AC.isParentOf(BC)); - EXPECT_TRUE(ARC.isParentOf(CRC)); - EXPECT_TRUE(AC.isParentOf(CC)); - EXPECT_FALSE(ARC.isParentOf(DRC)); - EXPECT_FALSE(AC.isParentOf(DC)); - EXPECT_TRUE(ARC.isAncestorOf(DRC)); - EXPECT_TRUE(AC.isAncestorOf(DC)); - EXPECT_FALSE(DRC.isChildOf(ARC)); - EXPECT_FALSE(DC.isChildOf(AC)); - EXPECT_TRUE(DRC.isDescendantOf(ARC)); - EXPECT_TRUE(DC.isDescendantOf(AC)); - EXPECT_TRUE(DRC.isChildOf(BRC)); - EXPECT_TRUE(DC.isChildOf(BC)); - EXPECT_TRUE(DRC.isChildOf(CRC)); - EXPECT_TRUE(DC.isChildOf(CC)); - - EXPECT_EQ(2, std::distance(A->begin(), A->end())); - ARC.insertOutgoingEdge(A, D, LazyCallGraph::Edge::Call); - EXPECT_EQ(3, std::distance(A->begin(), A->end())); - const LazyCallGraph::Edge &NewE = (*A)[D]; - EXPECT_TRUE(NewE); - EXPECT_TRUE(NewE.isCall()); - EXPECT_EQ(&D, &NewE.getNode()); - - // Only the parent and child tests sholud have changed. The rest of the graph - // remains the same. - EXPECT_TRUE(ARC.isParentOf(DRC)); - EXPECT_TRUE(AC.isParentOf(DC)); - EXPECT_TRUE(ARC.isAncestorOf(DRC)); - EXPECT_TRUE(AC.isAncestorOf(DC)); - EXPECT_TRUE(DRC.isChildOf(ARC)); - EXPECT_TRUE(DC.isChildOf(AC)); - EXPECT_TRUE(DRC.isDescendantOf(ARC)); - EXPECT_TRUE(DC.isDescendantOf(AC)); - EXPECT_EQ(&AC, CG.lookupSCC(A)); - EXPECT_EQ(&BC, CG.lookupSCC(B)); - EXPECT_EQ(&CC, CG.lookupSCC(C)); - EXPECT_EQ(&DC, CG.lookupSCC(D)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); - EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C)); - EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); - - ARC.switchOutgoingEdgeToRef(A, D); - EXPECT_FALSE(NewE.isCall()); - - // Verify the reference graph remains the same but the SCC graph is updated. - EXPECT_TRUE(ARC.isParentOf(DRC)); - EXPECT_FALSE(AC.isParentOf(DC)); - EXPECT_TRUE(ARC.isAncestorOf(DRC)); - EXPECT_TRUE(AC.isAncestorOf(DC)); - EXPECT_TRUE(DRC.isChildOf(ARC)); - EXPECT_FALSE(DC.isChildOf(AC)); - EXPECT_TRUE(DRC.isDescendantOf(ARC)); - EXPECT_TRUE(DC.isDescendantOf(AC)); - EXPECT_EQ(&AC, CG.lookupSCC(A)); - EXPECT_EQ(&BC, CG.lookupSCC(B)); - EXPECT_EQ(&CC, CG.lookupSCC(C)); - EXPECT_EQ(&DC, CG.lookupSCC(D)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); - EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C)); - EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); - - ARC.switchOutgoingEdgeToCall(A, D); - EXPECT_TRUE(NewE.isCall()); - - // Verify the reference graph remains the same but the SCC graph is updated. - EXPECT_TRUE(ARC.isParentOf(DRC)); - EXPECT_TRUE(AC.isParentOf(DC)); - EXPECT_TRUE(ARC.isAncestorOf(DRC)); - EXPECT_TRUE(AC.isAncestorOf(DC)); - EXPECT_TRUE(DRC.isChildOf(ARC)); - EXPECT_TRUE(DC.isChildOf(AC)); - EXPECT_TRUE(DRC.isDescendantOf(ARC)); - EXPECT_TRUE(DC.isDescendantOf(AC)); - EXPECT_EQ(&AC, CG.lookupSCC(A)); - EXPECT_EQ(&BC, CG.lookupSCC(B)); - EXPECT_EQ(&CC, CG.lookupSCC(C)); - EXPECT_EQ(&DC, CG.lookupSCC(D)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); - EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C)); - EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); - - ARC.removeOutgoingEdge(A, D); - EXPECT_EQ(2, std::distance(A->begin(), A->end())); - - // Now the parent and child tests fail again but the rest remains the same. - EXPECT_FALSE(ARC.isParentOf(DRC)); - EXPECT_FALSE(AC.isParentOf(DC)); - EXPECT_TRUE(ARC.isAncestorOf(DRC)); - EXPECT_TRUE(AC.isAncestorOf(DC)); - EXPECT_FALSE(DRC.isChildOf(ARC)); - EXPECT_FALSE(DC.isChildOf(AC)); - EXPECT_TRUE(DRC.isDescendantOf(ARC)); - EXPECT_TRUE(DC.isDescendantOf(AC)); - EXPECT_EQ(&AC, CG.lookupSCC(A)); - EXPECT_EQ(&BC, CG.lookupSCC(B)); - EXPECT_EQ(&CC, CG.lookupSCC(C)); - EXPECT_EQ(&DC, CG.lookupSCC(D)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); - EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C)); - EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); -} - -TEST(LazyCallGraphTest, IncomingEdgeInsertion) { - LLVMContext Context; - // We want to ensure we can add edges even across complex diamond graphs, so - // we use the diamond of triangles graph defined above. The ascii diagram is - // repeated here for easy reference. - // - // d1 | - // / \ | - // d3--d2 | - // / \ | - // b1 c1 | - // / \ / \ | - // b3--b2 c3--c2 | - // \ / | - // a1 | - // / \ | - // a3--a2 | - // - std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles); - LazyCallGraph CG = buildCG(*M); - - // Force the graph to be fully expanded. - CG.buildRefSCCs(); - for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) - dbgs() << "Formed RefSCC: " << RC << "\n"; - - LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1")); - LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2")); - LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3")); - LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1")); - LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2")); - LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3")); - LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1")); - LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2")); - LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3")); - LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1")); - LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2")); - LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3")); - LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A1); - LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B1); - LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C1); - LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D1); - ASSERT_EQ(&ARC, CG.lookupRefSCC(A2)); - ASSERT_EQ(&ARC, CG.lookupRefSCC(A3)); - ASSERT_EQ(&BRC, CG.lookupRefSCC(B2)); - ASSERT_EQ(&BRC, CG.lookupRefSCC(B3)); - ASSERT_EQ(&CRC, CG.lookupRefSCC(C2)); - ASSERT_EQ(&CRC, CG.lookupRefSCC(C3)); - ASSERT_EQ(&DRC, CG.lookupRefSCC(D2)); - ASSERT_EQ(&DRC, CG.lookupRefSCC(D3)); - ASSERT_EQ(1, std::distance(D2->begin(), D2->end())); - - // Add an edge to make the graph: - // - // d1 | - // / \ | - // d3--d2---. | - // / \ | | - // b1 c1 | | - // / \ / \ / | - // b3--b2 c3--c2 | - // \ / | - // a1 | - // / \ | - // a3--a2 | - auto MergedRCs = CRC.insertIncomingRefEdge(D2, C2); - // Make sure we connected the nodes. - for (LazyCallGraph::Edge E : *D2) { - if (&E.getNode() == &D3) - continue; - EXPECT_EQ(&C2, &E.getNode()); - } - // And marked the D ref-SCC as no longer valid. - EXPECT_EQ(1u, MergedRCs.size()); - EXPECT_EQ(&DRC, MergedRCs[0]); - - // Make sure we have the correct nodes in the SCC sets. - EXPECT_EQ(&ARC, CG.lookupRefSCC(A1)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(A2)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(A3)); - EXPECT_EQ(&BRC, CG.lookupRefSCC(B1)); - EXPECT_EQ(&BRC, CG.lookupRefSCC(B2)); - EXPECT_EQ(&BRC, CG.lookupRefSCC(B3)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C1)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C2)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C3)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(D1)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(D2)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(D3)); - - // And that ancestry tests have been updated. - EXPECT_TRUE(ARC.isParentOf(CRC)); - EXPECT_TRUE(BRC.isParentOf(CRC)); - - // And verify the post-order walk reflects the updated structure. - auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); - ASSERT_NE(I, E); - EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I; - ASSERT_NE(++I, E); - EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I; - ASSERT_NE(++I, E); - EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I; - EXPECT_EQ(++I, E); -} - -TEST(LazyCallGraphTest, IncomingEdgeInsertionRefGraph) { - LLVMContext Context; - // Another variation of the above test but with all the edges switched to - // references rather than calls. - std::unique_ptr<Module> M = - parseAssembly(Context, DiamondOfTrianglesRefGraph); - LazyCallGraph CG = buildCG(*M); - - // Force the graph to be fully expanded. - CG.buildRefSCCs(); - for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) - dbgs() << "Formed RefSCC: " << RC << "\n"; - - LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1")); - LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2")); - LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3")); - LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1")); - LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2")); - LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3")); - LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1")); - LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2")); - LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3")); - LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1")); - LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2")); - LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3")); - LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A1); - LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B1); - LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C1); - LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D1); - ASSERT_EQ(&ARC, CG.lookupRefSCC(A2)); - ASSERT_EQ(&ARC, CG.lookupRefSCC(A3)); - ASSERT_EQ(&BRC, CG.lookupRefSCC(B2)); - ASSERT_EQ(&BRC, CG.lookupRefSCC(B3)); - ASSERT_EQ(&CRC, CG.lookupRefSCC(C2)); - ASSERT_EQ(&CRC, CG.lookupRefSCC(C3)); - ASSERT_EQ(&DRC, CG.lookupRefSCC(D2)); - ASSERT_EQ(&DRC, CG.lookupRefSCC(D3)); - ASSERT_EQ(1, std::distance(D2->begin(), D2->end())); - - // Add an edge to make the graph: - // - // d1 | - // / \ | - // d3--d2---. | - // / \ | | - // b1 c1 | | - // / \ / \ / | - // b3--b2 c3--c2 | - // \ / | - // a1 | - // / \ | - // a3--a2 | - auto MergedRCs = CRC.insertIncomingRefEdge(D2, C2); - // Make sure we connected the nodes. - for (LazyCallGraph::Edge E : *D2) { - if (&E.getNode() == &D3) - continue; - EXPECT_EQ(&C2, &E.getNode()); - } - // And marked the D ref-SCC as no longer valid. - EXPECT_EQ(1u, MergedRCs.size()); - EXPECT_EQ(&DRC, MergedRCs[0]); - - // Make sure we have the correct nodes in the SCC sets. - EXPECT_EQ(&ARC, CG.lookupRefSCC(A1)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(A2)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(A3)); - EXPECT_EQ(&BRC, CG.lookupRefSCC(B1)); - EXPECT_EQ(&BRC, CG.lookupRefSCC(B2)); - EXPECT_EQ(&BRC, CG.lookupRefSCC(B3)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C1)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C2)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C3)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(D1)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(D2)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(D3)); - - // And that ancestry tests have been updated. - EXPECT_TRUE(ARC.isParentOf(CRC)); - EXPECT_TRUE(BRC.isParentOf(CRC)); - - // And verify the post-order walk reflects the updated structure. - auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); - ASSERT_NE(I, E); - EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I; - ASSERT_NE(++I, E); - EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I; - ASSERT_NE(++I, E); - EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I; - EXPECT_EQ(++I, E); -} - -TEST(LazyCallGraphTest, IncomingEdgeInsertionLargeCallCycle) { - LLVMContext Context; - std::unique_ptr<Module> M = parseAssembly(Context, "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 @d()\n" - " ret void\n" - "}\n" - "define void @d() {\n" - "entry:\n" - " ret void\n" - "}\n"); - LazyCallGraph CG = buildCG(*M); - - // Force the graph to be fully expanded. - CG.buildRefSCCs(); - for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) - dbgs() << "Formed RefSCC: " << RC << "\n"; - - 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::SCC &AC = *CG.lookupSCC(A); - LazyCallGraph::SCC &BC = *CG.lookupSCC(B); - LazyCallGraph::SCC &CC = *CG.lookupSCC(C); - LazyCallGraph::SCC &DC = *CG.lookupSCC(D); - LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A); - LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B); - LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C); - LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D); - - // Connect the top to the bottom forming a large RefSCC made up mostly of calls. - auto MergedRCs = ARC.insertIncomingRefEdge(D, A); - // Make sure we connected the nodes. - EXPECT_NE(D->begin(), D->end()); - EXPECT_EQ(&A, &D->begin()->getNode()); - - // Check that we have the dead RCs, but ignore the order. - EXPECT_EQ(3u, MergedRCs.size()); - EXPECT_NE(find(MergedRCs, &BRC), MergedRCs.end()); - EXPECT_NE(find(MergedRCs, &CRC), MergedRCs.end()); - EXPECT_NE(find(MergedRCs, &DRC), MergedRCs.end()); - - // Make sure the nodes point to the right place now. - EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(B)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(C)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(D)); - - // Check that the SCCs are in postorder. - EXPECT_EQ(4, ARC.size()); - EXPECT_EQ(&DC, &ARC[0]); - EXPECT_EQ(&CC, &ARC[1]); - EXPECT_EQ(&BC, &ARC[2]); - EXPECT_EQ(&AC, &ARC[3]); - - // And verify the post-order walk reflects the updated structure. - auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); - ASSERT_NE(I, E); - EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I; - EXPECT_EQ(++I, E); -} - -TEST(LazyCallGraphTest, IncomingEdgeInsertionLargeRefCycle) { - LLVMContext Context; - std::unique_ptr<Module> M = - parseAssembly(Context, "define void @a() {\n" - "entry:\n" - " %p = alloca void ()*\n" - " store void ()* @b, void ()** %p\n" - " ret void\n" - "}\n" - "define void @b() {\n" - "entry:\n" - " %p = alloca void ()*\n" - " store void ()* @c, void ()** %p\n" - " ret void\n" - "}\n" - "define void @c() {\n" - "entry:\n" - " %p = alloca void ()*\n" - " store void ()* @d, void ()** %p\n" - " ret void\n" - "}\n" - "define void @d() {\n" - "entry:\n" - " ret void\n" - "}\n"); - LazyCallGraph CG = buildCG(*M); - - // Force the graph to be fully expanded. - CG.buildRefSCCs(); - for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) - dbgs() << "Formed RefSCC: " << RC << "\n"; - - 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::RefSCC &ARC = *CG.lookupRefSCC(A); - LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B); - LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C); - LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D); - - // Connect the top to the bottom forming a large RefSCC made up just of - // references. - auto MergedRCs = ARC.insertIncomingRefEdge(D, A); - // Make sure we connected the nodes. - EXPECT_NE(D->begin(), D->end()); - EXPECT_EQ(&A, &D->begin()->getNode()); - - // Check that we have the dead RCs, but ignore the order. - EXPECT_EQ(3u, MergedRCs.size()); - EXPECT_NE(find(MergedRCs, &BRC), MergedRCs.end()); - EXPECT_NE(find(MergedRCs, &CRC), MergedRCs.end()); - EXPECT_NE(find(MergedRCs, &DRC), MergedRCs.end()); - - // Make sure the nodes point to the right place now. - EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(B)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(C)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(D)); - - // And verify the post-order walk reflects the updated structure. - auto I = CG.postorder_ref_scc_begin(), End = CG.postorder_ref_scc_end(); - ASSERT_NE(I, End); - EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I; - EXPECT_EQ(++I, End); -} - -TEST(LazyCallGraphTest, InlineAndDeleteFunction) { - LLVMContext Context; - // We want to ensure we can delete nodes from relatively complex graphs and - // so use the diamond of triangles graph defined above. - // - // The ascii diagram is repeated here for easy reference. - // - // d1 | - // / \ | - // d3--d2 | - // / \ | - // b1 c1 | - // / \ / \ | - // b3--b2 c3--c2 | - // \ / | - // a1 | - // / \ | - // a3--a2 | - // - std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles); - LazyCallGraph CG = buildCG(*M); - - // Force the graph to be fully expanded. - CG.buildRefSCCs(); - for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) - dbgs() << "Formed RefSCC: " << RC << "\n"; - - LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1")); - LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2")); - LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3")); - LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1")); - LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2")); - LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3")); - LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1")); - LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2")); - LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3")); - LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1")); - LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2")); - LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3")); - LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A1); - LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B1); - LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C1); - LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D1); - ASSERT_EQ(&ARC, CG.lookupRefSCC(A2)); - ASSERT_EQ(&ARC, CG.lookupRefSCC(A3)); - ASSERT_EQ(&BRC, CG.lookupRefSCC(B2)); - ASSERT_EQ(&BRC, CG.lookupRefSCC(B3)); - ASSERT_EQ(&CRC, CG.lookupRefSCC(C2)); - ASSERT_EQ(&CRC, CG.lookupRefSCC(C3)); - ASSERT_EQ(&DRC, CG.lookupRefSCC(D2)); - ASSERT_EQ(&DRC, CG.lookupRefSCC(D3)); - ASSERT_EQ(1, std::distance(D2->begin(), D2->end())); - - // Delete d2 from the graph, as if it had been inlined. - // - // d1 | - // / / | - // d3--. | - // / \ | - // b1 c1 | - // / \ / \ | - // b3--b2 c3--c2 | - // \ / | - // a1 | - // / \ | - // a3--a2 | - - Function &D2F = D2.getFunction(); - CallInst *C1Call = nullptr, *D1Call = nullptr; - for (User *U : D2F.users()) { - CallInst *CI = dyn_cast<CallInst>(U); - ASSERT_TRUE(CI) << "Expected a call: " << *U; - if (CI->getParent()->getParent() == &C1.getFunction()) { - ASSERT_EQ(nullptr, C1Call) << "Found too many C1 calls: " << *CI; - C1Call = CI; - } else if (CI->getParent()->getParent() == &D1.getFunction()) { - ASSERT_EQ(nullptr, D1Call) << "Found too many D1 calls: " << *CI; - D1Call = CI; - } else { - FAIL() << "Found an unexpected call instruction: " << *CI; - } - } - ASSERT_NE(C1Call, nullptr); - ASSERT_NE(D1Call, nullptr); - ASSERT_EQ(&D2F, C1Call->getCalledFunction()); - ASSERT_EQ(&D2F, D1Call->getCalledFunction()); - C1Call->setCalledFunction(&D3.getFunction()); - D1Call->setCalledFunction(&D3.getFunction()); - ASSERT_EQ(0u, D2F.getNumUses()); - - // Insert new edges first. - CRC.insertTrivialCallEdge(C1, D3); - DRC.insertTrivialCallEdge(D1, D3); - - // Then remove the old ones. - LazyCallGraph::SCC &DC = *CG.lookupSCC(D2); - auto NewCs = DRC.switchInternalEdgeToRef(D1, D2); - EXPECT_EQ(&DC, CG.lookupSCC(D2)); - EXPECT_EQ(NewCs.end(), std::next(NewCs.begin())); - LazyCallGraph::SCC &NewDC = *NewCs.begin(); - EXPECT_EQ(&NewDC, CG.lookupSCC(D1)); - EXPECT_EQ(&NewDC, CG.lookupSCC(D3)); - auto NewRCs = DRC.removeInternalRefEdge(D1, {&D2}); - ASSERT_EQ(2u, NewRCs.size()); - LazyCallGraph::RefSCC &NewDRC = *NewRCs[0]; - EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1)); - EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3)); - LazyCallGraph::RefSCC &D2RC = *NewRCs[1]; - EXPECT_EQ(&D2RC, CG.lookupRefSCC(D2)); - EXPECT_FALSE(NewDRC.isParentOf(D2RC)); - EXPECT_TRUE(CRC.isParentOf(D2RC)); - EXPECT_TRUE(CRC.isParentOf(NewDRC)); - EXPECT_TRUE(D2RC.isParentOf(NewDRC)); - CRC.removeOutgoingEdge(C1, D2); - EXPECT_FALSE(CRC.isParentOf(D2RC)); - EXPECT_TRUE(CRC.isParentOf(NewDRC)); - EXPECT_TRUE(D2RC.isParentOf(NewDRC)); - - // Now that we've updated the call graph, D2 is dead, so remove it. - CG.removeDeadFunction(D2F); - - // Check that the graph still looks the same. - EXPECT_EQ(&ARC, CG.lookupRefSCC(A1)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(A2)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(A3)); - EXPECT_EQ(&BRC, CG.lookupRefSCC(B1)); - EXPECT_EQ(&BRC, CG.lookupRefSCC(B2)); - EXPECT_EQ(&BRC, CG.lookupRefSCC(B3)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C1)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C2)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C3)); - EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1)); - EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3)); - EXPECT_TRUE(CRC.isParentOf(NewDRC)); - - // Verify the post-order walk hasn't changed. - auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); - ASSERT_NE(I, E); - EXPECT_EQ(&NewDRC, &*I) << "Actual RefSCC: " << *I; - ASSERT_NE(++I, E); - EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I; - ASSERT_NE(++I, E); - EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I; - ASSERT_NE(++I, E); - EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I; - EXPECT_EQ(++I, E); -} - -TEST(LazyCallGraphTest, InternalEdgeMutation) { - LLVMContext Context; - std::unique_ptr<Module> M = parseAssembly(Context, "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 CG = buildCG(*M); - - // Force the graph to be fully expanded. - CG.buildRefSCCs(); - auto I = CG.postorder_ref_scc_begin(); - LazyCallGraph::RefSCC &RC = *I++; - EXPECT_EQ(CG.postorder_ref_scc_end(), I); - - LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); - LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); - LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); - EXPECT_EQ(&RC, CG.lookupRefSCC(A)); - EXPECT_EQ(&RC, CG.lookupRefSCC(B)); - EXPECT_EQ(&RC, CG.lookupRefSCC(C)); - EXPECT_EQ(1, RC.size()); - EXPECT_EQ(&*RC.begin(), CG.lookupSCC(A)); - EXPECT_EQ(&*RC.begin(), CG.lookupSCC(B)); - EXPECT_EQ(&*RC.begin(), CG.lookupSCC(C)); - - // Insert an edge from 'a' to 'c'. Nothing changes about the graph. - RC.insertInternalRefEdge(A, C); - EXPECT_EQ(2, std::distance(A->begin(), A->end())); - EXPECT_EQ(&RC, CG.lookupRefSCC(A)); - EXPECT_EQ(&RC, CG.lookupRefSCC(B)); - EXPECT_EQ(&RC, CG.lookupRefSCC(C)); - EXPECT_EQ(1, RC.size()); - EXPECT_EQ(&*RC.begin(), CG.lookupSCC(A)); - EXPECT_EQ(&*RC.begin(), CG.lookupSCC(B)); - EXPECT_EQ(&*RC.begin(), CG.lookupSCC(C)); - - // Switch the call edge from 'b' to 'c' to a ref edge. This will break the - // call cycle and cause us to form more SCCs. The RefSCC will remain the same - // though. - auto NewCs = RC.switchInternalEdgeToRef(B, C); - EXPECT_EQ(&RC, CG.lookupRefSCC(A)); - EXPECT_EQ(&RC, CG.lookupRefSCC(B)); - EXPECT_EQ(&RC, CG.lookupRefSCC(C)); - auto J = RC.begin(); - // The SCCs must be in *post-order* which means successors before - // predecessors. At this point we have call edges from C to A and from A to - // B. The only valid postorder is B, A, C. - EXPECT_EQ(&*J++, CG.lookupSCC(B)); - EXPECT_EQ(&*J++, CG.lookupSCC(A)); - EXPECT_EQ(&*J++, CG.lookupSCC(C)); - EXPECT_EQ(RC.end(), J); - // And the returned range must be the slice of this sequence containing new - // SCCs. - EXPECT_EQ(RC.begin(), NewCs.begin()); - EXPECT_EQ(std::prev(RC.end()), NewCs.end()); - - // Test turning the ref edge from A to C into a call edge. This will form an - // SCC out of A and C. Since we previously had a call edge from C to A, the - // C SCC should be preserved and have A merged into it while the A SCC should - // be invalidated. - LazyCallGraph::SCC &AC = *CG.lookupSCC(A); - LazyCallGraph::SCC &CC = *CG.lookupSCC(C); - EXPECT_TRUE(RC.switchInternalEdgeToCall(A, C, [&](ArrayRef<LazyCallGraph::SCC *> MergedCs) { - ASSERT_EQ(1u, MergedCs.size()); - EXPECT_EQ(&AC, MergedCs[0]); - })); - EXPECT_EQ(2, CC.size()); - EXPECT_EQ(&CC, CG.lookupSCC(A)); - EXPECT_EQ(&CC, CG.lookupSCC(C)); - J = RC.begin(); - EXPECT_EQ(&*J++, CG.lookupSCC(B)); - EXPECT_EQ(&*J++, CG.lookupSCC(C)); - EXPECT_EQ(RC.end(), J); -} - -TEST(LazyCallGraphTest, InternalEdgeRemoval) { - LLVMContext Context; - // A nice fully connected (including self-edges) RefSCC. - std::unique_ptr<Module> M = parseAssembly( - Context, "define void @a(i8** %ptr) {\n" - "entry:\n" - " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" - " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" - " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" - " ret void\n" - "}\n" - "define void @b(i8** %ptr) {\n" - "entry:\n" - " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" - " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" - " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" - " ret void\n" - "}\n" - "define void @c(i8** %ptr) {\n" - "entry:\n" - " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" - " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" - " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" - " ret void\n" - "}\n"); - LazyCallGraph CG = buildCG(*M); - - // Force the graph to be fully expanded. - CG.buildRefSCCs(); - auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); - LazyCallGraph::RefSCC &RC = *I; - EXPECT_EQ(E, std::next(I)); - - LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); - LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); - LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); - EXPECT_EQ(&RC, CG.lookupRefSCC(A)); - EXPECT_EQ(&RC, CG.lookupRefSCC(B)); - EXPECT_EQ(&RC, CG.lookupRefSCC(C)); - - // Remove the edge from b -> a, which should leave the 3 functions still in - // a single connected component because of a -> b -> c -> a. - SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs = - RC.removeInternalRefEdge(B, {&A}); - EXPECT_EQ(0u, NewRCs.size()); - EXPECT_EQ(&RC, CG.lookupRefSCC(A)); - EXPECT_EQ(&RC, CG.lookupRefSCC(B)); - EXPECT_EQ(&RC, CG.lookupRefSCC(C)); - auto J = CG.postorder_ref_scc_begin(); - EXPECT_EQ(I, J); - EXPECT_EQ(&RC, &*J); - EXPECT_EQ(E, std::next(J)); - - // Increment I before we actually mutate the structure so that it remains - // a valid iterator. - ++I; - - // Remove the edge from c -> a, which should leave 'a' in the original RefSCC - // and form a new RefSCC for 'b' and 'c'. - NewRCs = RC.removeInternalRefEdge(C, {&A}); - ASSERT_EQ(2u, NewRCs.size()); - LazyCallGraph::RefSCC &BCRC = *NewRCs[0]; - LazyCallGraph::RefSCC &ARC = *NewRCs[1]; - EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); - EXPECT_EQ(1, std::distance(ARC.begin(), ARC.end())); - EXPECT_EQ(&BCRC, CG.lookupRefSCC(B)); - EXPECT_EQ(&BCRC, CG.lookupRefSCC(C)); - J = CG.postorder_ref_scc_begin(); - EXPECT_NE(I, J); - EXPECT_EQ(&BCRC, &*J); - ++J; - EXPECT_NE(I, J); - EXPECT_EQ(&ARC, &*J); - ++J; - EXPECT_EQ(I, J); - EXPECT_EQ(E, J); -} - -TEST(LazyCallGraphTest, InternalMultiEdgeRemoval) { - LLVMContext Context; - // A nice fully connected (including self-edges) RefSCC. - std::unique_ptr<Module> M = parseAssembly( - Context, "define void @a(i8** %ptr) {\n" - "entry:\n" - " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" - " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" - " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" - " ret void\n" - "}\n" - "define void @b(i8** %ptr) {\n" - "entry:\n" - " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" - " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" - " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" - " ret void\n" - "}\n" - "define void @c(i8** %ptr) {\n" - "entry:\n" - " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" - " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" - " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" - " ret void\n" - "}\n"); - LazyCallGraph CG = buildCG(*M); - - // Force the graph to be fully expanded. - CG.buildRefSCCs(); - auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); - LazyCallGraph::RefSCC &RC = *I; - EXPECT_EQ(E, std::next(I)); - - LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); - LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); - LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); - EXPECT_EQ(&RC, CG.lookupRefSCC(A)); - EXPECT_EQ(&RC, CG.lookupRefSCC(B)); - EXPECT_EQ(&RC, CG.lookupRefSCC(C)); - - // Increment I before we actually mutate the structure so that it remains - // a valid iterator. - ++I; - - // Remove the edges from b -> a and b -> c, leaving b in its own RefSCC. - SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs = - RC.removeInternalRefEdge(B, {&A, &C}); - - ASSERT_EQ(2u, NewRCs.size()); - LazyCallGraph::RefSCC &BRC = *NewRCs[0]; - LazyCallGraph::RefSCC &ACRC = *NewRCs[1]; - EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); - EXPECT_EQ(1, std::distance(BRC.begin(), BRC.end())); - EXPECT_EQ(&ACRC, CG.lookupRefSCC(A)); - EXPECT_EQ(&ACRC, CG.lookupRefSCC(C)); - auto J = CG.postorder_ref_scc_begin(); - EXPECT_NE(I, J); - EXPECT_EQ(&BRC, &*J); - ++J; - EXPECT_NE(I, J); - EXPECT_EQ(&ACRC, &*J); - ++J; - EXPECT_EQ(I, J); - EXPECT_EQ(E, J); -} - -TEST(LazyCallGraphTest, InternalNoOpEdgeRemoval) { - LLVMContext Context; - // A graph with a single cycle formed both from call and reference edges - // which makes the reference edges trivial to delete. The graph looks like: - // - // Reference edges: a -> b -> c -> a - // Call edges: a -> c -> b -> a - std::unique_ptr<Module> M = parseAssembly( - Context, "define void @a(i8** %ptr) {\n" - "entry:\n" - " call void @b(i8** %ptr)\n" - " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" - " ret void\n" - "}\n" - "define void @b(i8** %ptr) {\n" - "entry:\n" - " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" - " call void @c(i8** %ptr)\n" - " ret void\n" - "}\n" - "define void @c(i8** %ptr) {\n" - "entry:\n" - " call void @a(i8** %ptr)\n" - " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" - " ret void\n" - "}\n"); - LazyCallGraph CG = buildCG(*M); - - // Force the graph to be fully expanded. - CG.buildRefSCCs(); - auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); - LazyCallGraph::RefSCC &RC = *I; - EXPECT_EQ(E, std::next(I)); - - LazyCallGraph::SCC &C = *RC.begin(); - EXPECT_EQ(RC.end(), std::next(RC.begin())); - - LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a")); - LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b")); - LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c")); - EXPECT_EQ(&RC, CG.lookupRefSCC(AN)); - EXPECT_EQ(&RC, CG.lookupRefSCC(BN)); - EXPECT_EQ(&RC, CG.lookupRefSCC(CN)); - EXPECT_EQ(&C, CG.lookupSCC(AN)); - EXPECT_EQ(&C, CG.lookupSCC(BN)); - EXPECT_EQ(&C, CG.lookupSCC(CN)); - - // Remove the edge from a -> c which doesn't change anything. - SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs = - RC.removeInternalRefEdge(AN, {&CN}); - EXPECT_EQ(0u, NewRCs.size()); - EXPECT_EQ(&RC, CG.lookupRefSCC(AN)); - EXPECT_EQ(&RC, CG.lookupRefSCC(BN)); - EXPECT_EQ(&RC, CG.lookupRefSCC(CN)); - EXPECT_EQ(&C, CG.lookupSCC(AN)); - EXPECT_EQ(&C, CG.lookupSCC(BN)); - EXPECT_EQ(&C, CG.lookupSCC(CN)); - auto J = CG.postorder_ref_scc_begin(); - EXPECT_EQ(I, J); - EXPECT_EQ(&RC, &*J); - EXPECT_EQ(E, std::next(J)); - - // Remove the edge from b -> a and c -> b; again this doesn't change - // anything. - NewRCs = RC.removeInternalRefEdge(BN, {&AN}); - NewRCs = RC.removeInternalRefEdge(CN, {&BN}); - EXPECT_EQ(0u, NewRCs.size()); - EXPECT_EQ(&RC, CG.lookupRefSCC(AN)); - EXPECT_EQ(&RC, CG.lookupRefSCC(BN)); - EXPECT_EQ(&RC, CG.lookupRefSCC(CN)); - EXPECT_EQ(&C, CG.lookupSCC(AN)); - EXPECT_EQ(&C, CG.lookupSCC(BN)); - EXPECT_EQ(&C, CG.lookupSCC(CN)); - J = CG.postorder_ref_scc_begin(); - EXPECT_EQ(I, J); - EXPECT_EQ(&RC, &*J); - EXPECT_EQ(E, std::next(J)); -} - -TEST(LazyCallGraphTest, InternalCallEdgeToRef) { - LLVMContext Context; - // A nice fully connected (including self-edges) SCC (and RefSCC) - std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n" - "entry:\n" - " call void @a()\n" - " call void @b()\n" - " call void @c()\n" - " ret void\n" - "}\n" - "define void @b() {\n" - "entry:\n" - " call void @a()\n" - " call void @b()\n" - " call void @c()\n" - " ret void\n" - "}\n" - "define void @c() {\n" - "entry:\n" - " call void @a()\n" - " call void @b()\n" - " call void @c()\n" - " ret void\n" - "}\n"); - LazyCallGraph CG = buildCG(*M); - - // Force the graph to be fully expanded. - CG.buildRefSCCs(); - auto I = CG.postorder_ref_scc_begin(); - LazyCallGraph::RefSCC &RC = *I++; - EXPECT_EQ(CG.postorder_ref_scc_end(), I); - - EXPECT_EQ(1, RC.size()); - LazyCallGraph::SCC &AC = *RC.begin(); - - LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a")); - LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b")); - LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c")); - EXPECT_EQ(&AC, CG.lookupSCC(AN)); - EXPECT_EQ(&AC, CG.lookupSCC(BN)); - EXPECT_EQ(&AC, CG.lookupSCC(CN)); - - // Remove the call edge from b -> a to a ref edge, which should leave the - // 3 functions still in a single connected component because of a -> b -> - // c -> a. - auto NewCs = RC.switchInternalEdgeToRef(BN, AN); - EXPECT_EQ(NewCs.begin(), NewCs.end()); - EXPECT_EQ(1, RC.size()); - EXPECT_EQ(&AC, CG.lookupSCC(AN)); - EXPECT_EQ(&AC, CG.lookupSCC(BN)); - EXPECT_EQ(&AC, CG.lookupSCC(CN)); - - // Remove the edge from c -> a, which should leave 'a' in the original SCC - // and form a new SCC for 'b' and 'c'. - NewCs = RC.switchInternalEdgeToRef(CN, AN); - EXPECT_EQ(1, std::distance(NewCs.begin(), NewCs.end())); - EXPECT_EQ(2, RC.size()); - EXPECT_EQ(&AC, CG.lookupSCC(AN)); - LazyCallGraph::SCC &BC = *CG.lookupSCC(BN); - EXPECT_NE(&BC, &AC); - EXPECT_EQ(&BC, CG.lookupSCC(CN)); - auto J = RC.find(AC); - EXPECT_EQ(&AC, &*J); - --J; - EXPECT_EQ(&BC, &*J); - EXPECT_EQ(RC.begin(), J); - EXPECT_EQ(J, NewCs.begin()); - - // Remove the edge from c -> b, which should leave 'b' in the original SCC - // and form a new SCC for 'c'. It shouldn't change 'a's SCC. - NewCs = RC.switchInternalEdgeToRef(CN, BN); - EXPECT_EQ(1, std::distance(NewCs.begin(), NewCs.end())); - EXPECT_EQ(3, RC.size()); - EXPECT_EQ(&AC, CG.lookupSCC(AN)); - EXPECT_EQ(&BC, CG.lookupSCC(BN)); - LazyCallGraph::SCC &CC = *CG.lookupSCC(CN); - EXPECT_NE(&CC, &AC); - EXPECT_NE(&CC, &BC); - J = RC.find(AC); - EXPECT_EQ(&AC, &*J); - --J; - EXPECT_EQ(&BC, &*J); - --J; - EXPECT_EQ(&CC, &*J); - EXPECT_EQ(RC.begin(), J); - EXPECT_EQ(J, NewCs.begin()); -} - -TEST(LazyCallGraphTest, InternalRefEdgeToCall) { - LLVMContext Context; - // Basic tests for making a ref edge a call. This hits the basics of the - // process only. - std::unique_ptr<Module> M = - parseAssembly(Context, "define void @a() {\n" - "entry:\n" - " call void @b()\n" - " call void @c()\n" - " store void()* @d, void()** undef\n" - " ret void\n" - "}\n" - "define void @b() {\n" - "entry:\n" - " store void()* @c, void()** undef\n" - " call void @d()\n" - " ret void\n" - "}\n" - "define void @c() {\n" - "entry:\n" - " store void()* @b, void()** undef\n" - " call void @d()\n" - " ret void\n" - "}\n" - "define void @d() {\n" - "entry:\n" - " store void()* @a, void()** undef\n" - " ret void\n" - "}\n"); - LazyCallGraph CG = buildCG(*M); - - // Force the graph to be fully expanded. - CG.buildRefSCCs(); - auto I = CG.postorder_ref_scc_begin(); - LazyCallGraph::RefSCC &RC = *I++; - EXPECT_EQ(CG.postorder_ref_scc_end(), I); - - 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::SCC &AC = *CG.lookupSCC(A); - LazyCallGraph::SCC &BC = *CG.lookupSCC(B); - LazyCallGraph::SCC &CC = *CG.lookupSCC(C); - LazyCallGraph::SCC &DC = *CG.lookupSCC(D); - - // Check the initial post-order. Note that B and C could be flipped here (and - // in our mutation) without changing the nature of this test. - ASSERT_EQ(4, RC.size()); - EXPECT_EQ(&DC, &RC[0]); - EXPECT_EQ(&BC, &RC[1]); - EXPECT_EQ(&CC, &RC[2]); - EXPECT_EQ(&AC, &RC[3]); - - // Switch the ref edge from A -> D to a call edge. This should have no - // effect as it is already in postorder and no new cycles are formed. - EXPECT_FALSE(RC.switchInternalEdgeToCall(A, D)); - ASSERT_EQ(4, RC.size()); - EXPECT_EQ(&DC, &RC[0]); - EXPECT_EQ(&BC, &RC[1]); - EXPECT_EQ(&CC, &RC[2]); - EXPECT_EQ(&AC, &RC[3]); - - // Switch B -> C to a call edge. This doesn't form any new cycles but does - // require reordering the SCCs. - EXPECT_FALSE(RC.switchInternalEdgeToCall(B, C)); - ASSERT_EQ(4, RC.size()); - EXPECT_EQ(&DC, &RC[0]); - EXPECT_EQ(&CC, &RC[1]); - EXPECT_EQ(&BC, &RC[2]); - EXPECT_EQ(&AC, &RC[3]); - - // Switch C -> B to a call edge. This forms a cycle and forces merging SCCs. - EXPECT_TRUE(RC.switchInternalEdgeToCall(C, B, [&](ArrayRef<LazyCallGraph::SCC *> MergedCs) { - ASSERT_EQ(1u, MergedCs.size()); - EXPECT_EQ(&CC, MergedCs[0]); - })); - ASSERT_EQ(3, RC.size()); - EXPECT_EQ(&DC, &RC[0]); - EXPECT_EQ(&BC, &RC[1]); - EXPECT_EQ(&AC, &RC[2]); - EXPECT_EQ(2, BC.size()); - EXPECT_EQ(&BC, CG.lookupSCC(B)); - EXPECT_EQ(&BC, CG.lookupSCC(C)); -} - -TEST(LazyCallGraphTest, InternalRefEdgeToCallNoCycleInterleaved) { - LLVMContext Context; - // Test for having a post-order prior to changing a ref edge to a call edge - // with SCCs connecting to the source and connecting to the target, but not - // connecting to both, interleaved between the source and target. This - // ensures we correctly partition the range rather than simply moving one or - // the other. - std::unique_ptr<Module> M = - parseAssembly(Context, "define void @a() {\n" - "entry:\n" - " call void @b1()\n" - " call void @c1()\n" - " ret void\n" - "}\n" - "define void @b1() {\n" - "entry:\n" - " call void @c1()\n" - " call void @b2()\n" - " ret void\n" - "}\n" - "define void @c1() {\n" - "entry:\n" - " call void @b2()\n" - " call void @c2()\n" - " ret void\n" - "}\n" - "define void @b2() {\n" - "entry:\n" - " call void @c2()\n" - " call void @b3()\n" - " ret void\n" - "}\n" - "define void @c2() {\n" - "entry:\n" - " call void @b3()\n" - " call void @c3()\n" - " ret void\n" - "}\n" - "define void @b3() {\n" - "entry:\n" - " call void @c3()\n" - " call void @d()\n" - " ret void\n" - "}\n" - "define void @c3() {\n" - "entry:\n" - " store void()* @b1, void()** undef\n" - " call void @d()\n" - " ret void\n" - "}\n" - "define void @d() {\n" - "entry:\n" - " store void()* @a, void()** undef\n" - " ret void\n" - "}\n"); - LazyCallGraph CG = buildCG(*M); - - // Force the graph to be fully expanded. - CG.buildRefSCCs(); - auto I = CG.postorder_ref_scc_begin(); - LazyCallGraph::RefSCC &RC = *I++; - EXPECT_EQ(CG.postorder_ref_scc_end(), I); - - LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); - LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1")); - LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2")); - LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3")); - LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1")); - LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2")); - LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3")); - LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); - LazyCallGraph::SCC &AC = *CG.lookupSCC(A); - LazyCallGraph::SCC &B1C = *CG.lookupSCC(B1); - LazyCallGraph::SCC &B2C = *CG.lookupSCC(B2); - LazyCallGraph::SCC &B3C = *CG.lookupSCC(B3); - LazyCallGraph::SCC &C1C = *CG.lookupSCC(C1); - LazyCallGraph::SCC &C2C = *CG.lookupSCC(C2); - LazyCallGraph::SCC &C3C = *CG.lookupSCC(C3); - LazyCallGraph::SCC &DC = *CG.lookupSCC(D); - - // Several call edges are initially present to force a particual post-order. - // Remove them now, leaving an interleaved post-order pattern. - RC.switchTrivialInternalEdgeToRef(B3, C3); - RC.switchTrivialInternalEdgeToRef(C2, B3); - RC.switchTrivialInternalEdgeToRef(B2, C2); - RC.switchTrivialInternalEdgeToRef(C1, B2); - RC.switchTrivialInternalEdgeToRef(B1, C1); - - // Check the initial post-order. We ensure this order with the extra edges - // that are nuked above. - ASSERT_EQ(8, RC.size()); - EXPECT_EQ(&DC, &RC[0]); - EXPECT_EQ(&C3C, &RC[1]); - EXPECT_EQ(&B3C, &RC[2]); - EXPECT_EQ(&C2C, &RC[3]); - EXPECT_EQ(&B2C, &RC[4]); - EXPECT_EQ(&C1C, &RC[5]); - EXPECT_EQ(&B1C, &RC[6]); - EXPECT_EQ(&AC, &RC[7]); - - // Switch C3 -> B1 to a call edge. This doesn't form any new cycles but does - // require reordering the SCCs in the face of tricky internal node - // structures. - EXPECT_FALSE(RC.switchInternalEdgeToCall(C3, B1)); - ASSERT_EQ(8, RC.size()); - EXPECT_EQ(&DC, &RC[0]); - EXPECT_EQ(&B3C, &RC[1]); - EXPECT_EQ(&B2C, &RC[2]); - EXPECT_EQ(&B1C, &RC[3]); - EXPECT_EQ(&C3C, &RC[4]); - EXPECT_EQ(&C2C, &RC[5]); - EXPECT_EQ(&C1C, &RC[6]); - EXPECT_EQ(&AC, &RC[7]); -} - -TEST(LazyCallGraphTest, InternalRefEdgeToCallBothPartitionAndMerge) { - LLVMContext Context; - // Test for having a postorder where between the source and target are all - // three kinds of other SCCs: - // 1) One connected to the target only that have to be shifted below the - // source. - // 2) One connected to the source only that have to be shifted below the - // target. - // 3) One connected to both source and target that has to remain and get - // merged away. - // - // To achieve this we construct a heavily connected graph to force - // a particular post-order. Then we remove the forcing edges and connect - // a cycle. - // - // Diagram for the graph we want on the left and the graph we use to force - // the ordering on the right. Edges ponit down or right. - // - // A | A | - // / \ | / \ | - // B E | B \ | - // |\ | | |\ | | - // | D | | C-D-E | - // | \| | | \| | - // C F | \ F | - // \ / | \ / | - // G | G | - // - // And we form a cycle by connecting F to B. - std::unique_ptr<Module> M = - parseAssembly(Context, "define void @a() {\n" - "entry:\n" - " call void @b()\n" - " call void @e()\n" - " ret void\n" - "}\n" - "define void @b() {\n" - "entry:\n" - " call void @c()\n" - " call void @d()\n" - " ret void\n" - "}\n" - "define void @c() {\n" - "entry:\n" - " call void @d()\n" - " call void @g()\n" - " ret void\n" - "}\n" - "define void @d() {\n" - "entry:\n" - " call void @e()\n" - " call void @f()\n" - " ret void\n" - "}\n" - "define void @e() {\n" - "entry:\n" - " call void @f()\n" - " ret void\n" - "}\n" - "define void @f() {\n" - "entry:\n" - " store void()* @b, void()** undef\n" - " call void @g()\n" - " ret void\n" - "}\n" - "define void @g() {\n" - "entry:\n" - " store void()* @a, void()** undef\n" - " ret void\n" - "}\n"); - LazyCallGraph CG = buildCG(*M); - - // Force the graph to be fully expanded. - CG.buildRefSCCs(); - auto I = CG.postorder_ref_scc_begin(); - LazyCallGraph::RefSCC &RC = *I++; - EXPECT_EQ(CG.postorder_ref_scc_end(), I); - - 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")); - LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f")); - LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g")); - LazyCallGraph::SCC &AC = *CG.lookupSCC(A); - LazyCallGraph::SCC &BC = *CG.lookupSCC(B); - LazyCallGraph::SCC &CC = *CG.lookupSCC(C); - LazyCallGraph::SCC &DC = *CG.lookupSCC(D); - LazyCallGraph::SCC &EC = *CG.lookupSCC(E); - LazyCallGraph::SCC &FC = *CG.lookupSCC(F); - LazyCallGraph::SCC &GC = *CG.lookupSCC(G); - - // Remove the extra edges that were used to force a particular post-order. - RC.switchTrivialInternalEdgeToRef(C, D); - RC.switchTrivialInternalEdgeToRef(D, E); - - // Check the initial post-order. We ensure this order with the extra edges - // that are nuked above. - ASSERT_EQ(7, RC.size()); - EXPECT_EQ(&GC, &RC[0]); - EXPECT_EQ(&FC, &RC[1]); - EXPECT_EQ(&EC, &RC[2]); - EXPECT_EQ(&DC, &RC[3]); - EXPECT_EQ(&CC, &RC[4]); - EXPECT_EQ(&BC, &RC[5]); - EXPECT_EQ(&AC, &RC[6]); - - // Switch F -> B to a call edge. This merges B, D, and F into a single SCC, - // and has to place the C and E SCCs on either side of it: - // A A | - // / \ / \ | - // B E | E | - // |\ | \ / | - // | D | -> B | - // | \| / \ | - // C F C | | - // \ / \ / | - // G G | - EXPECT_TRUE(RC.switchInternalEdgeToCall( - F, B, [&](ArrayRef<LazyCallGraph::SCC *> MergedCs) { - ASSERT_EQ(2u, MergedCs.size()); - EXPECT_EQ(&FC, MergedCs[0]); - EXPECT_EQ(&DC, MergedCs[1]); - })); - EXPECT_EQ(3, BC.size()); - - // And make sure the postorder was updated. - ASSERT_EQ(5, RC.size()); - EXPECT_EQ(&GC, &RC[0]); - EXPECT_EQ(&CC, &RC[1]); - EXPECT_EQ(&BC, &RC[2]); - EXPECT_EQ(&EC, &RC[3]); - EXPECT_EQ(&AC, &RC[4]); -} - -// Test for IR containing constants using blockaddress constant expressions. -// These are truly unique constructs: constant expressions with non-constant -// operands. -TEST(LazyCallGraphTest, HandleBlockAddress) { - LLVMContext Context; - std::unique_ptr<Module> M = - parseAssembly(Context, "define void @f() {\n" - "entry:\n" - " ret void\n" - "bb:\n" - " unreachable\n" - "}\n" - "define void @g(i8** %ptr) {\n" - "entry:\n" - " store i8* blockaddress(@f, %bb), i8** %ptr\n" - " ret void\n" - "}\n"); - LazyCallGraph CG = buildCG(*M); - - CG.buildRefSCCs(); - auto I = CG.postorder_ref_scc_begin(); - LazyCallGraph::RefSCC &FRC = *I++; - LazyCallGraph::RefSCC &GRC = *I++; - EXPECT_EQ(CG.postorder_ref_scc_end(), I); - - LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f")); - LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g")); - EXPECT_EQ(&FRC, CG.lookupRefSCC(F)); - EXPECT_EQ(&GRC, CG.lookupRefSCC(G)); - EXPECT_TRUE(GRC.isParentOf(FRC)); -} - -TEST(LazyCallGraphTest, ReplaceNodeFunction) { - LLVMContext Context; - // A graph with several different kinds of edges pointing at a particular - // function. - std::unique_ptr<Module> M = - parseAssembly(Context, - "define void @a(i8** %ptr) {\n" - "entry:\n" - " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n" - " ret void\n" - "}\n" - "define void @b(i8** %ptr) {\n" - "entry:\n" - " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n" - " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n" - " call void @d(i8** %ptr)" - " ret void\n" - "}\n" - "define void @c(i8** %ptr) {\n" - "entry:\n" - " call void @d(i8** %ptr)" - " call void @d(i8** %ptr)" - " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n" - " ret void\n" - "}\n" - "define void @d(i8** %ptr) {\n" - "entry:\n" - " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" - " call void @c(i8** %ptr)" - " call void @d(i8** %ptr)" - " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n" - " ret void\n" - "}\n"); - LazyCallGraph CG = buildCG(*M); - - // Force the graph to be fully expanded. - CG.buildRefSCCs(); - auto I = CG.postorder_ref_scc_begin(); - LazyCallGraph::RefSCC &RC1 = *I++; - LazyCallGraph::RefSCC &RC2 = *I++; - EXPECT_EQ(CG.postorder_ref_scc_end(), I); - - ASSERT_EQ(2, RC1.size()); - LazyCallGraph::SCC &C1 = RC1[0]; - LazyCallGraph::SCC &C2 = RC1[1]; - - LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a")); - LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b")); - LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c")); - LazyCallGraph::Node &DN = *CG.lookup(lookupFunction(*M, "d")); - EXPECT_EQ(&C1, CG.lookupSCC(DN)); - EXPECT_EQ(&C1, CG.lookupSCC(CN)); - EXPECT_EQ(&C2, CG.lookupSCC(BN)); - EXPECT_EQ(&RC1, CG.lookupRefSCC(DN)); - EXPECT_EQ(&RC1, CG.lookupRefSCC(CN)); - EXPECT_EQ(&RC1, CG.lookupRefSCC(BN)); - EXPECT_EQ(&RC2, CG.lookupRefSCC(AN)); - - // Now we need to build a new function 'e' with the same signature as 'd'. - Function &D = DN.getFunction(); - Function &E = *Function::Create(D.getFunctionType(), D.getLinkage(), "e"); - D.getParent()->getFunctionList().insert(D.getIterator(), &E); - - // Change each use of 'd' to use 'e'. This is particularly easy as they have - // the same type. - D.replaceAllUsesWith(&E); - - // Splice the body of the old function into the new one. - E.getBasicBlockList().splice(E.begin(), D.getBasicBlockList()); - // And fix up the one argument. - D.arg_begin()->replaceAllUsesWith(&*E.arg_begin()); - E.arg_begin()->takeName(&*D.arg_begin()); - - // Now replace the function in the graph. - RC1.replaceNodeFunction(DN, E); - - EXPECT_EQ(&E, &DN.getFunction()); - EXPECT_EQ(&DN, &(*CN)[DN].getNode()); - EXPECT_EQ(&DN, &(*BN)[DN].getNode()); -} - -TEST(LazyCallGraphTest, RemoveFunctionWithSpurriousRef) { - LLVMContext Context; - // A graph with a couple of RefSCCs. - std::unique_ptr<Module> M = - parseAssembly(Context, - "define void @a(i8** %ptr) {\n" - "entry:\n" - " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n" - " ret void\n" - "}\n" - "define void @b(i8** %ptr) {\n" - "entry:\n" - " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" - " ret void\n" - "}\n" - "define void @c(i8** %ptr) {\n" - "entry:\n" - " call void @d(i8** %ptr)" - " ret void\n" - "}\n" - "define void @d(i8** %ptr) {\n" - "entry:\n" - " call void @c(i8** %ptr)" - " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" - " ret void\n" - "}\n" - "define void @dead() {\n" - "entry:\n" - " ret void\n" - "}\n"); - LazyCallGraph CG = buildCG(*M); - - // Insert spurious ref edges. - LazyCallGraph::Node &AN = CG.get(lookupFunction(*M, "a")); - LazyCallGraph::Node &BN = CG.get(lookupFunction(*M, "b")); - LazyCallGraph::Node &CN = CG.get(lookupFunction(*M, "c")); - LazyCallGraph::Node &DN = CG.get(lookupFunction(*M, "d")); - LazyCallGraph::Node &DeadN = CG.get(lookupFunction(*M, "dead")); - AN.populate(); - BN.populate(); - CN.populate(); - DN.populate(); - DeadN.populate(); - CG.insertEdge(AN, DeadN, LazyCallGraph::Edge::Ref); - CG.insertEdge(BN, DeadN, LazyCallGraph::Edge::Ref); - CG.insertEdge(CN, DeadN, LazyCallGraph::Edge::Ref); - CG.insertEdge(DN, DeadN, LazyCallGraph::Edge::Ref); - - // Force the graph to be fully expanded. - CG.buildRefSCCs(); - auto I = CG.postorder_ref_scc_begin(); - LazyCallGraph::RefSCC &DeadRC = *I++; - LazyCallGraph::RefSCC &RC1 = *I++; - LazyCallGraph::RefSCC &RC2 = *I++; - EXPECT_EQ(CG.postorder_ref_scc_end(), I); - - ASSERT_EQ(2, RC1.size()); - LazyCallGraph::SCC &C1 = RC1[0]; - LazyCallGraph::SCC &C2 = RC1[1]; - - EXPECT_EQ(&DeadRC, CG.lookupRefSCC(DeadN)); - EXPECT_EQ(&C1, CG.lookupSCC(DN)); - EXPECT_EQ(&C1, CG.lookupSCC(CN)); - EXPECT_EQ(&C2, CG.lookupSCC(BN)); - EXPECT_EQ(&RC1, CG.lookupRefSCC(DN)); - EXPECT_EQ(&RC1, CG.lookupRefSCC(CN)); - EXPECT_EQ(&RC1, CG.lookupRefSCC(BN)); - EXPECT_EQ(&RC2, CG.lookupRefSCC(AN)); - - // Now delete 'dead'. There are no uses of this function but there are - // spurious references. - CG.removeDeadFunction(DeadN.getFunction()); - - // The only observable change should be that the RefSCC is gone from the - // postorder sequence. - I = CG.postorder_ref_scc_begin(); - EXPECT_EQ(&RC1, &*I++); - EXPECT_EQ(&RC2, &*I++); - EXPECT_EQ(CG.postorder_ref_scc_end(), I); -} -} |