You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
1306 lines
49 KiB
1306 lines
49 KiB
//===- 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/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";
|
|
|
|
TEST(LazyCallGraphTest, BasicGraphFormation) {
|
|
LLVMContext Context;
|
|
std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles);
|
|
LazyCallGraph CG(*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(CG);
|
|
EXPECT_EQ("a1", A1.getFunction().getName());
|
|
LazyCallGraph::Node &A2 = (I++)->getNode(CG);
|
|
EXPECT_EQ("a2", A2.getFunction().getName());
|
|
LazyCallGraph::Node &A3 = (I++)->getNode(CG);
|
|
EXPECT_EQ("a3", A3.getFunction().getName());
|
|
LazyCallGraph::Node &B1 = (I++)->getNode(CG);
|
|
EXPECT_EQ("b1", B1.getFunction().getName());
|
|
LazyCallGraph::Node &B2 = (I++)->getNode(CG);
|
|
EXPECT_EQ("b2", B2.getFunction().getName());
|
|
LazyCallGraph::Node &B3 = (I++)->getNode(CG);
|
|
EXPECT_EQ("b3", B3.getFunction().getName());
|
|
LazyCallGraph::Node &C1 = (I++)->getNode(CG);
|
|
EXPECT_EQ("c1", C1.getFunction().getName());
|
|
LazyCallGraph::Node &C2 = (I++)->getNode(CG);
|
|
EXPECT_EQ("c2", C2.getFunction().getName());
|
|
LazyCallGraph::Node &C3 = (I++)->getNode(CG);
|
|
EXPECT_EQ("c3", C3.getFunction().getName());
|
|
LazyCallGraph::Node &D1 = (I++)->getNode(CG);
|
|
EXPECT_EQ("d1", D1.getFunction().getName());
|
|
LazyCallGraph::Node &D2 = (I++)->getNode(CG);
|
|
EXPECT_EQ("d2", D2.getFunction().getName());
|
|
LazyCallGraph::Node &D3 = (I++)->getNode(CG);
|
|
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)
|
|
Nodes.push_back(E.getFunction().getName());
|
|
std::sort(Nodes.begin(), Nodes.end());
|
|
EXPECT_EQ("a2", Nodes[0]);
|
|
EXPECT_EQ("b2", Nodes[1]);
|
|
EXPECT_EQ("c3", Nodes[2]);
|
|
Nodes.clear();
|
|
|
|
EXPECT_EQ(A2.end(), std::next(A2.begin()));
|
|
EXPECT_EQ("a3", A2.begin()->getFunction().getName());
|
|
EXPECT_EQ(A3.end(), std::next(A3.begin()));
|
|
EXPECT_EQ("a1", A3.begin()->getFunction().getName());
|
|
|
|
for (LazyCallGraph::Edge &E : B1)
|
|
Nodes.push_back(E.getFunction().getName());
|
|
std::sort(Nodes.begin(), Nodes.end());
|
|
EXPECT_EQ("b2", Nodes[0]);
|
|
EXPECT_EQ("d3", Nodes[1]);
|
|
Nodes.clear();
|
|
|
|
EXPECT_EQ(B2.end(), std::next(B2.begin()));
|
|
EXPECT_EQ("b3", B2.begin()->getFunction().getName());
|
|
EXPECT_EQ(B3.end(), std::next(B3.begin()));
|
|
EXPECT_EQ("b1", B3.begin()->getFunction().getName());
|
|
|
|
for (LazyCallGraph::Edge &E : C1)
|
|
Nodes.push_back(E.getFunction().getName());
|
|
std::sort(Nodes.begin(), Nodes.end());
|
|
EXPECT_EQ("c2", Nodes[0]);
|
|
EXPECT_EQ("d2", Nodes[1]);
|
|
Nodes.clear();
|
|
|
|
EXPECT_EQ(C2.end(), std::next(C2.begin()));
|
|
EXPECT_EQ("c3", C2.begin()->getFunction().getName());
|
|
EXPECT_EQ(C3.end(), std::next(C3.begin()));
|
|
EXPECT_EQ("c1", C3.begin()->getFunction().getName());
|
|
|
|
EXPECT_EQ(D1.end(), std::next(D1.begin()));
|
|
EXPECT_EQ("d2", D1.begin()->getFunction().getName());
|
|
EXPECT_EQ(D2.end(), std::next(D2.begin()));
|
|
EXPECT_EQ("d3", D2.begin()->getFunction().getName());
|
|
EXPECT_EQ(D3.end(), std::next(D3.begin()));
|
|
EXPECT_EQ("d1", D3.begin()->getFunction().getName());
|
|
|
|
// Now lets look at the RefSCCs and SCCs.
|
|
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());
|
|
std::sort(Nodes.begin(), Nodes.end());
|
|
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));
|
|
|
|
LazyCallGraph::RefSCC &C = *J++;
|
|
ASSERT_EQ(1, C.size());
|
|
for (LazyCallGraph::Node &N : *C.begin())
|
|
Nodes.push_back(N.getFunction().getName());
|
|
std::sort(Nodes.begin(), Nodes.end());
|
|
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));
|
|
|
|
LazyCallGraph::RefSCC &B = *J++;
|
|
ASSERT_EQ(1, B.size());
|
|
for (LazyCallGraph::Node &N : *B.begin())
|
|
Nodes.push_back(N.getFunction().getName());
|
|
std::sort(Nodes.begin(), Nodes.end());
|
|
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));
|
|
|
|
LazyCallGraph::RefSCC &A = *J++;
|
|
ASSERT_EQ(1, A.size());
|
|
for (LazyCallGraph::Node &N : *A.begin())
|
|
Nodes.push_back(N.getFunction().getName());
|
|
std::sort(Nodes.begin(), Nodes.end());
|
|
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(CG.postorder_ref_scc_end(), J);
|
|
}
|
|
|
|
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(*M);
|
|
|
|
LazyCallGraph::Node &A = CG.get(lookupFunction(*M, "a"));
|
|
LazyCallGraph::Node &B = CG.get(lookupFunction(*M, "b"));
|
|
EXPECT_EQ(2, std::distance(A.begin(), A.end()));
|
|
EXPECT_EQ(0, std::distance(B.begin(), B.end()));
|
|
|
|
CG.insertEdge(B, lookupFunction(*M, "c"), LazyCallGraph::Edge::Call);
|
|
EXPECT_EQ(1, std::distance(B.begin(), B.end()));
|
|
LazyCallGraph::Node &C = B.begin()->getNode(CG);
|
|
EXPECT_EQ(0, std::distance(C.begin(), C.end()));
|
|
|
|
CG.insertEdge(C, B.getFunction(), LazyCallGraph::Edge::Call);
|
|
EXPECT_EQ(1, std::distance(C.begin(), C.end()));
|
|
EXPECT_EQ(&B, C.begin()->getNode());
|
|
|
|
CG.insertEdge(C, C.getFunction(), 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.getFunction());
|
|
EXPECT_EQ(1, std::distance(C.begin(), C.end()));
|
|
EXPECT_EQ(&C, C.begin()->getNode());
|
|
|
|
CG.removeEdge(C, C.getFunction());
|
|
EXPECT_EQ(0, std::distance(C.begin(), C.end()));
|
|
|
|
CG.removeEdge(B, C.getFunction());
|
|
EXPECT_EQ(0, std::distance(B.begin(), B.end()));
|
|
}
|
|
|
|
TEST(LazyCallGraphTest, InnerSCCFormation) {
|
|
LLVMContext Context;
|
|
std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles);
|
|
LazyCallGraph CG(*M);
|
|
|
|
// Now mutate the graph to connect every node into a single RefSCC to ensure
|
|
// that our inner SCC formation handles the rest.
|
|
CG.insertEdge(lookupFunction(*M, "d1"), lookupFunction(*M, "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.
|
|
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());
|
|
std::sort(Nodes.begin(), Nodes.end());
|
|
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());
|
|
std::sort(Nodes.begin(), Nodes.end());
|
|
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());
|
|
std::sort(Nodes.begin(), Nodes.end());
|
|
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());
|
|
std::sort(Nodes.begin(), Nodes.end());
|
|
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(*M);
|
|
|
|
// Force the graph to be fully expanded.
|
|
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(*M);
|
|
|
|
// Force the graph to be fully expanded.
|
|
for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
|
|
(void)RC;
|
|
|
|
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(ARC.isParentOf(CRC));
|
|
EXPECT_FALSE(ARC.isParentOf(DRC));
|
|
EXPECT_TRUE(ARC.isAncestorOf(DRC));
|
|
EXPECT_FALSE(DRC.isChildOf(ARC));
|
|
EXPECT_TRUE(DRC.isDescendantOf(ARC));
|
|
EXPECT_TRUE(DRC.isChildOf(BRC));
|
|
EXPECT_TRUE(DRC.isChildOf(CRC));
|
|
|
|
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(ARC.isAncestorOf(DRC));
|
|
EXPECT_TRUE(DRC.isChildOf(ARC));
|
|
EXPECT_TRUE(DRC.isDescendantOf(ARC));
|
|
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 graph remains the same.
|
|
EXPECT_TRUE(ARC.isParentOf(DRC));
|
|
EXPECT_TRUE(ARC.isAncestorOf(DRC));
|
|
EXPECT_TRUE(DRC.isChildOf(ARC));
|
|
EXPECT_TRUE(DRC.isDescendantOf(ARC));
|
|
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 graph remains the same.
|
|
EXPECT_TRUE(ARC.isParentOf(DRC));
|
|
EXPECT_TRUE(ARC.isAncestorOf(DRC));
|
|
EXPECT_TRUE(DRC.isChildOf(ARC));
|
|
EXPECT_TRUE(DRC.isDescendantOf(ARC));
|
|
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_TRUE(ARC.isAncestorOf(DRC));
|
|
EXPECT_FALSE(DRC.isChildOf(ARC));
|
|
EXPECT_TRUE(DRC.isDescendantOf(ARC));
|
|
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(*M);
|
|
|
|
// Force the graph to be fully expanded.
|
|
for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
|
|
(void)RC;
|
|
|
|
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));
|
|
}
|
|
|
|
TEST(LazyCallGraphTest, IncomingEdgeInsertionMidTraversal) {
|
|
LLVMContext Context;
|
|
// This is the same fundamental test as the previous, but we perform it
|
|
// having only partially walked the RefSCCs of the graph.
|
|
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()));
|
|
|
|
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 RefSCCs.
|
|
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));
|
|
|
|
// Check that we can form the last two RefSCCs now in a coherent way.
|
|
++I;
|
|
EXPECT_NE(I, E);
|
|
LazyCallGraph::RefSCC &BRC = *I;
|
|
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(CRC));
|
|
++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(CRC));
|
|
++I;
|
|
EXPECT_EQ(E, I);
|
|
}
|
|
|
|
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(*M);
|
|
|
|
// Force the graph to be fully expanded.
|
|
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.
|
|
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);
|
|
|
|
// 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);
|
|
auto InvalidatedSCCs = RC.switchInternalEdgeToCall(A, C);
|
|
ASSERT_EQ(1u, InvalidatedSCCs.size());
|
|
EXPECT_EQ(&AC, InvalidatedSCCs[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(*M);
|
|
|
|
// Force the graph to be fully expanded.
|
|
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));
|
|
|
|
// 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));
|
|
|
|
// 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);
|
|
EXPECT_EQ(1u, NewRCs.size());
|
|
EXPECT_EQ(&RC, CG.lookupRefSCC(A));
|
|
EXPECT_EQ(1, std::distance(RC.begin(), RC.end()));
|
|
LazyCallGraph::RefSCC *RC2 = CG.lookupRefSCC(B);
|
|
EXPECT_EQ(RC2, CG.lookupRefSCC(C));
|
|
EXPECT_EQ(RC2, NewRCs[0]);
|
|
}
|
|
|
|
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(*M);
|
|
|
|
// Force the graph to be fully expanded.
|
|
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 &CallC = *RC.begin();
|
|
|
|
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(&CallC, CG.lookupSCC(A));
|
|
EXPECT_EQ(&CallC, CG.lookupSCC(B));
|
|
EXPECT_EQ(&CallC, CG.lookupSCC(C));
|
|
|
|
// 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.
|
|
RC.switchInternalEdgeToRef(B, A);
|
|
EXPECT_EQ(1, RC.size());
|
|
EXPECT_EQ(&CallC, CG.lookupSCC(A));
|
|
EXPECT_EQ(&CallC, CG.lookupSCC(B));
|
|
EXPECT_EQ(&CallC, CG.lookupSCC(C));
|
|
|
|
// Remove the edge from c -> a, which should leave 'a' in the original SCC
|
|
// and form a new SCC for 'b' and 'c'.
|
|
RC.switchInternalEdgeToRef(C, A);
|
|
EXPECT_EQ(2, RC.size());
|
|
EXPECT_EQ(&CallC, CG.lookupSCC(A));
|
|
LazyCallGraph::SCC &BCallC = *CG.lookupSCC(B);
|
|
EXPECT_NE(&BCallC, &CallC);
|
|
EXPECT_EQ(&BCallC, CG.lookupSCC(C));
|
|
auto J = RC.find(CallC);
|
|
EXPECT_EQ(&CallC, &*J);
|
|
--J;
|
|
EXPECT_EQ(&BCallC, &*J);
|
|
EXPECT_EQ(RC.begin(), J);
|
|
|
|
// 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.
|
|
RC.switchInternalEdgeToRef(C, B);
|
|
EXPECT_EQ(3, RC.size());
|
|
EXPECT_EQ(&CallC, CG.lookupSCC(A));
|
|
EXPECT_EQ(&BCallC, CG.lookupSCC(B));
|
|
LazyCallGraph::SCC &CCallC = *CG.lookupSCC(C);
|
|
EXPECT_NE(&CCallC, &CallC);
|
|
EXPECT_NE(&CCallC, &BCallC);
|
|
J = RC.find(CallC);
|
|
EXPECT_EQ(&CallC, &*J);
|
|
--J;
|
|
EXPECT_EQ(&BCallC, &*J);
|
|
--J;
|
|
EXPECT_EQ(&CCallC, &*J);
|
|
EXPECT_EQ(RC.begin(), J);
|
|
}
|
|
|
|
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(*M);
|
|
|
|
// Force the graph to be fully expanded.
|
|
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.
|
|
auto MergedCs = RC.switchInternalEdgeToCall(A, D);
|
|
EXPECT_EQ(0u, MergedCs.size());
|
|
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.
|
|
MergedCs = RC.switchInternalEdgeToCall(B, C);
|
|
EXPECT_EQ(0u, MergedCs.size());
|
|
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.
|
|
MergedCs = RC.switchInternalEdgeToCall(C, B);
|
|
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(*M);
|
|
|
|
// Force the graph to be fully expanded.
|
|
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.switchInternalEdgeToRef(B3, C3);
|
|
RC.switchInternalEdgeToRef(C2, B3);
|
|
RC.switchInternalEdgeToRef(B2, C2);
|
|
RC.switchInternalEdgeToRef(C1, B2);
|
|
RC.switchInternalEdgeToRef(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.
|
|
auto MergedCs = RC.switchInternalEdgeToCall(C3, B1);
|
|
EXPECT_EQ(0u, MergedCs.size());
|
|
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(*M);
|
|
|
|
// Force the graph to be fully expanded.
|
|
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.switchInternalEdgeToRef(C, D);
|
|
RC.switchInternalEdgeToRef(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 |
|
|
auto MergedCs = RC.switchInternalEdgeToCall(F, B);
|
|
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]);
|
|
}
|
|
|
|
}
|