summaryrefslogtreecommitdiffstats
path: root/llvm/unittests/Analysis
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/unittests/Analysis')
-rw-r--r--llvm/unittests/Analysis/LazyCallGraphTest.cpp318
1 files changed, 318 insertions, 0 deletions
diff --git a/llvm/unittests/Analysis/LazyCallGraphTest.cpp b/llvm/unittests/Analysis/LazyCallGraphTest.cpp
index 0ac9b6554c2..66cd9a1e485 100644
--- a/llvm/unittests/Analysis/LazyCallGraphTest.cpp
+++ b/llvm/unittests/Analysis/LazyCallGraphTest.cpp
@@ -9,6 +9,7 @@
#include "llvm/Analysis/LazyCallGraph.h"
#include "llvm/AsmParser/Parser.h"
+#include "llvm/IR/Instructions.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
@@ -1105,6 +1106,323 @@ TEST(LazyCallGraphTest, IncomingEdgeInsertionLargeRefCycle) {
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(*M);
+
+ // Force the graph to be fully expanded.
+ 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);
+ EXPECT_EQ(&DRC, CG.lookupRefSCC(D2));
+ EXPECT_EQ(NewRCs.end(), std::next(NewRCs.begin()));
+ LazyCallGraph::RefSCC &NewDRC = **NewRCs.begin();
+ EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1));
+ EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3));
+ EXPECT_FALSE(NewDRC.isParentOf(DRC));
+ EXPECT_TRUE(CRC.isParentOf(DRC));
+ EXPECT_TRUE(CRC.isParentOf(NewDRC));
+ EXPECT_TRUE(DRC.isParentOf(NewDRC));
+ CRC.removeOutgoingEdge(C1, D2);
+ EXPECT_FALSE(CRC.isParentOf(DRC));
+ EXPECT_TRUE(CRC.isParentOf(NewDRC));
+ EXPECT_TRUE(DRC.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, InlineAndDeleteFunctionMidTraversal) {
+ LLVMContext Context;
+ // This is the same fundamental test as the previous, but we perform it
+ // having only partially walked the RefSCCs of the graph.
+ //
+ // 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(*M);
+
+ // Walk the RefSCCs until we find the one containing 'c1'.
+ auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
+ ASSERT_NE(I, E);
+ LazyCallGraph::RefSCC &DRC = *I;
+ ASSERT_NE(&DRC, nullptr);
+ ++I;
+ ASSERT_NE(I, E);
+ LazyCallGraph::RefSCC &CRC = *I;
+ ASSERT_NE(&CRC, nullptr);
+
+ ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a1")));
+ ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a2")));
+ ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a3")));
+ ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b1")));
+ ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b2")));
+ ASSERT_EQ(nullptr, 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"));
+ ASSERT_EQ(&CRC, CG.lookupRefSCC(C1));
+ ASSERT_EQ(&CRC, CG.lookupRefSCC(C2));
+ ASSERT_EQ(&CRC, CG.lookupRefSCC(C3));
+ ASSERT_EQ(&DRC, CG.lookupRefSCC(D1));
+ 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);
+ EXPECT_EQ(&DRC, CG.lookupRefSCC(D2));
+ EXPECT_EQ(NewRCs.end(), std::next(NewRCs.begin()));
+ LazyCallGraph::RefSCC &NewDRC = **NewRCs.begin();
+ EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1));
+ EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3));
+ EXPECT_FALSE(NewDRC.isParentOf(DRC));
+ EXPECT_TRUE(CRC.isParentOf(DRC));
+ EXPECT_TRUE(CRC.isParentOf(NewDRC));
+ EXPECT_TRUE(DRC.isParentOf(NewDRC));
+ CRC.removeOutgoingEdge(C1, D2);
+ EXPECT_FALSE(CRC.isParentOf(DRC));
+ EXPECT_TRUE(CRC.isParentOf(NewDRC));
+ EXPECT_TRUE(DRC.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(&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 that the post-order walk reflects the updated but still incomplete
+ // structure.
+ auto J = CG.postorder_ref_scc_begin();
+ EXPECT_NE(J, E);
+ EXPECT_EQ(&NewDRC, &*J) << "Actual RefSCC: " << *J;
+ ++J;
+ EXPECT_NE(J, E);
+ EXPECT_EQ(&CRC, &*J) << "Actual RefSCC: " << *J;
+ EXPECT_EQ(I, J);
+
+ // Check that we can form the last two RefSCCs now, and even that we can do
+ // it with alternating iterators.
+ ++J;
+ EXPECT_NE(J, E);
+ LazyCallGraph::RefSCC &BRC = *J;
+ EXPECT_NE(&BRC, nullptr);
+ EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b1"))));
+ EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b2"))));
+ EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b3"))));
+ EXPECT_TRUE(BRC.isParentOf(NewDRC));
+ ++I;
+ EXPECT_EQ(J, I);
+ EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I;
+
+ // Increment I this time to form the new RefSCC, flopping back to the first
+ // iterator.
+ ++I;
+ EXPECT_NE(I, E);
+ LazyCallGraph::RefSCC &ARC = *I;
+ EXPECT_NE(&ARC, nullptr);
+ EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a1"))));
+ EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a2"))));
+ EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a3"))));
+ EXPECT_TRUE(ARC.isParentOf(BRC));
+ EXPECT_TRUE(ARC.isParentOf(CRC));
+ ++J;
+ EXPECT_EQ(I, J);
+ EXPECT_EQ(&ARC, &*J) << "Actual RefSCC: " << *J;
+ ++I;
+ EXPECT_EQ(E, I);
+ ++J;
+ EXPECT_EQ(E, J);
+}
+
TEST(LazyCallGraphTest, InternalEdgeMutation) {
LLVMContext Context;
std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"
OpenPOWER on IntegriCloud