1dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines//===- LazyCallGraphTest.cpp - Unit tests for the lazy CG analysis --------===// 2dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// 3dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// The LLVM Compiler Infrastructure 4dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// 5dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// This file is distributed under the University of Illinois Open Source 6dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// License. See LICENSE.TXT for details. 7dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// 8dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines//===----------------------------------------------------------------------===// 9dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 10dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include "llvm/Analysis/LazyCallGraph.h" 11dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include "llvm/AsmParser/Parser.h" 12dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include "llvm/IR/Function.h" 13dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include "llvm/IR/LLVMContext.h" 14dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include "llvm/IR/Module.h" 15dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include "llvm/Support/ErrorHandling.h" 16dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include "llvm/Support/SourceMgr.h" 17dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include "gtest/gtest.h" 18dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include <memory> 19dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 20dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesusing namespace llvm; 21dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 22dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesnamespace { 23dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 24dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstd::unique_ptr<Module> parseAssembly(const char *Assembly) { 25dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines auto M = make_unique<Module>("Module", getGlobalContext()); 26dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 27dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SMDiagnostic Error; 28dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool Parsed = 29dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ParseAssemblyString(Assembly, M.get(), Error, M->getContext()) == M.get(); 30dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 31dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::string ErrMsg; 32dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines raw_string_ostream OS(ErrMsg); 33dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Error.print("", OS); 34dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 35dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // A failure here means that the test itself is buggy. 36dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!Parsed) 37dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines report_fatal_error(OS.str().c_str()); 38dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 39dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return M; 40dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 41dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 42dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// IR forming a call graph with a diamond of triangle-shaped SCCs: 43dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// 44dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// d1 45dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// / \ 46dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// d3--d2 47dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// / \ 48dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// b1 c1 49dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// / \ / \ 50dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// b3--b2 c3--c2 51dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// \ / 52dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// a1 53dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// / \ 54dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// a3--a2 55dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// 56dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// All call edges go up between SCCs, and clockwise around the SCC. 57dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstatic const char DiamondOfTriangles[] = 58dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @a1() {\n" 59dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 60dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @a2()\n" 61dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @b2()\n" 62dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @c3()\n" 63dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 64dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n" 65dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @a2() {\n" 66dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 67dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @a3()\n" 68dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 69dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n" 70dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @a3() {\n" 71dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 72dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @a1()\n" 73dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 74dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n" 75dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @b1() {\n" 76dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 77dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @b2()\n" 78dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @d3()\n" 79dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 80dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n" 81dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @b2() {\n" 82dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 83dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @b3()\n" 84dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 85dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n" 86dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @b3() {\n" 87dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 88dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @b1()\n" 89dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 90dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n" 91dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @c1() {\n" 92dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 93dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @c2()\n" 94dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @d2()\n" 95dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 96dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n" 97dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @c2() {\n" 98dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 99dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @c3()\n" 100dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 101dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n" 102dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @c3() {\n" 103dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 104dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @c1()\n" 105dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 106dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n" 107dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @d1() {\n" 108dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 109dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @d2()\n" 110dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 111dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n" 112dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @d2() {\n" 113dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 114dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @d3()\n" 115dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 116dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n" 117dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @d3() {\n" 118dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 119dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @d1()\n" 120dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 121dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n"; 122dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 123dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesTEST(LazyCallGraphTest, BasicGraphFormation) { 124dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::unique_ptr<Module> M = parseAssembly(DiamondOfTriangles); 125dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph CG(*M); 126dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 127dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // The order of the entry nodes should be stable w.r.t. the source order of 128dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // the IR, and everything in our module is an entry node, so just directly 129dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // build variables for each node. 130dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines auto I = CG.begin(); 131dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &A1 = *I++; 132dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("a1", A1.getFunction().getName()); 133dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &A2 = *I++; 134dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("a2", A2.getFunction().getName()); 135dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &A3 = *I++; 136dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("a3", A3.getFunction().getName()); 137dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &B1 = *I++; 138dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("b1", B1.getFunction().getName()); 139dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &B2 = *I++; 140dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("b2", B2.getFunction().getName()); 141dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &B3 = *I++; 142dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("b3", B3.getFunction().getName()); 143dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &C1 = *I++; 144dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("c1", C1.getFunction().getName()); 145dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &C2 = *I++; 146dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("c2", C2.getFunction().getName()); 147dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &C3 = *I++; 148dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("c3", C3.getFunction().getName()); 149dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &D1 = *I++; 150dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("d1", D1.getFunction().getName()); 151dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &D2 = *I++; 152dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("d2", D2.getFunction().getName()); 153dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &D3 = *I++; 154dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("d3", D3.getFunction().getName()); 155dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(CG.end(), I); 156dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 157dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Build vectors and sort them for the rest of the assertions to make them 158dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // independent of order. 159dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::vector<std::string> Nodes; 160dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 161dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (LazyCallGraph::Node &N : A1) 162dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Nodes.push_back(N.getFunction().getName()); 163dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::sort(Nodes.begin(), Nodes.end()); 164dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("a2", Nodes[0]); 165dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("b2", Nodes[1]); 166dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("c3", Nodes[2]); 167dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Nodes.clear(); 168dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 169dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(A2.end(), std::next(A2.begin())); 170dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("a3", A2.begin()->getFunction().getName()); 171dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(A3.end(), std::next(A3.begin())); 172dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("a1", A3.begin()->getFunction().getName()); 173dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 174dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (LazyCallGraph::Node &N : B1) 175dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Nodes.push_back(N.getFunction().getName()); 176dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::sort(Nodes.begin(), Nodes.end()); 177dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("b2", Nodes[0]); 178dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("d3", Nodes[1]); 179dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Nodes.clear(); 180dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 181dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(B2.end(), std::next(B2.begin())); 182dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("b3", B2.begin()->getFunction().getName()); 183dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(B3.end(), std::next(B3.begin())); 184dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("b1", B3.begin()->getFunction().getName()); 185dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 186dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (LazyCallGraph::Node &N : C1) 187dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Nodes.push_back(N.getFunction().getName()); 188dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::sort(Nodes.begin(), Nodes.end()); 189dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("c2", Nodes[0]); 190dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("d2", Nodes[1]); 191dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Nodes.clear(); 192dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 193dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(C2.end(), std::next(C2.begin())); 194dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("c3", C2.begin()->getFunction().getName()); 195dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(C3.end(), std::next(C3.begin())); 196dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("c1", C3.begin()->getFunction().getName()); 197dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 198dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(D1.end(), std::next(D1.begin())); 199dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("d2", D1.begin()->getFunction().getName()); 200dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(D2.end(), std::next(D2.begin())); 201dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("d3", D2.begin()->getFunction().getName()); 202dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(D3.end(), std::next(D3.begin())); 203dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("d1", D3.begin()->getFunction().getName()); 204dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 205dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Now lets look at the SCCs. 206dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines auto SCCI = CG.postorder_scc_begin(); 207dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 208dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::SCC &D = *SCCI++; 209dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (LazyCallGraph::Node *N : D) 210dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Nodes.push_back(N->getFunction().getName()); 211dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::sort(Nodes.begin(), Nodes.end()); 212dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(3u, Nodes.size()); 213dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("d1", Nodes[0]); 214dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("d2", Nodes[1]); 215dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("d3", Nodes[2]); 216dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Nodes.clear(); 217dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_FALSE(D.isParentOf(D)); 218dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_FALSE(D.isChildOf(D)); 219dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_FALSE(D.isAncestorOf(D)); 220dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_FALSE(D.isDescendantOf(D)); 221dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 222dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::SCC &C = *SCCI++; 223dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (LazyCallGraph::Node *N : C) 224dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Nodes.push_back(N->getFunction().getName()); 225dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::sort(Nodes.begin(), Nodes.end()); 226dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(3u, Nodes.size()); 227dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("c1", Nodes[0]); 228dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("c2", Nodes[1]); 229dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("c3", Nodes[2]); 230dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Nodes.clear(); 231dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_TRUE(C.isParentOf(D)); 232dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_FALSE(C.isChildOf(D)); 233dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_TRUE(C.isAncestorOf(D)); 234dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_FALSE(C.isDescendantOf(D)); 235dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 236dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::SCC &B = *SCCI++; 237dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (LazyCallGraph::Node *N : B) 238dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Nodes.push_back(N->getFunction().getName()); 239dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::sort(Nodes.begin(), Nodes.end()); 240dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(3u, Nodes.size()); 241dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("b1", Nodes[0]); 242dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("b2", Nodes[1]); 243dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("b3", Nodes[2]); 244dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Nodes.clear(); 245dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_TRUE(B.isParentOf(D)); 246dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_FALSE(B.isChildOf(D)); 247dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_TRUE(B.isAncestorOf(D)); 248dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_FALSE(B.isDescendantOf(D)); 249dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_FALSE(B.isAncestorOf(C)); 250dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_FALSE(C.isAncestorOf(B)); 251dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 252dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::SCC &A = *SCCI++; 253dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (LazyCallGraph::Node *N : A) 254dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Nodes.push_back(N->getFunction().getName()); 255dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::sort(Nodes.begin(), Nodes.end()); 256dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(3u, Nodes.size()); 257dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("a1", Nodes[0]); 258dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("a2", Nodes[1]); 259dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("a3", Nodes[2]); 260dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Nodes.clear(); 261dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_TRUE(A.isParentOf(B)); 262dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_TRUE(A.isParentOf(C)); 263dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_FALSE(A.isParentOf(D)); 264dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_TRUE(A.isAncestorOf(B)); 265dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_TRUE(A.isAncestorOf(C)); 266dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_TRUE(A.isAncestorOf(D)); 267dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 268dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(CG.postorder_scc_end(), SCCI); 269dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 270dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 271dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstatic Function &lookupFunction(Module &M, StringRef Name) { 272dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (Function &F : M) 273dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (F.getName() == Name) 274dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return F; 275dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines report_fatal_error("Couldn't find function!"); 276dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 277dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 278dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesTEST(LazyCallGraphTest, BasicGraphMutation) { 279dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::unique_ptr<Module> M = parseAssembly( 280dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @a() {\n" 281dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 282dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @b()\n" 283dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @c()\n" 284dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 285dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n" 286dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @b() {\n" 287dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 288dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 289dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n" 290dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @c() {\n" 291dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 292dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 293dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n"); 294dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph CG(*M); 295dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 296dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &A = CG.get(lookupFunction(*M, "a")); 297dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &B = CG.get(lookupFunction(*M, "b")); 298dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(2, std::distance(A.begin(), A.end())); 299dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(0, std::distance(B.begin(), B.end())); 300dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 301dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CG.insertEdge(B, lookupFunction(*M, "c")); 302dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(1, std::distance(B.begin(), B.end())); 303dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &C = *B.begin(); 304dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(0, std::distance(C.begin(), C.end())); 305dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 306dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CG.insertEdge(C, B.getFunction()); 307dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(1, std::distance(C.begin(), C.end())); 308dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&B, &*C.begin()); 309dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 310dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CG.insertEdge(C, C.getFunction()); 311dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(2, std::distance(C.begin(), C.end())); 312dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&B, &*C.begin()); 313dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&C, &*std::next(C.begin())); 314dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 315dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CG.removeEdge(C, B.getFunction()); 316dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(1, std::distance(C.begin(), C.end())); 317dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&C, &*C.begin()); 318dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 319dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CG.removeEdge(C, C.getFunction()); 320dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(0, std::distance(C.begin(), C.end())); 321dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 322dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CG.removeEdge(B, C.getFunction()); 323dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(0, std::distance(B.begin(), B.end())); 324dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 325dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 326dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesTEST(LazyCallGraphTest, MultiArmSCC) { 327dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Two interlocking cycles. The really useful thing about this SCC is that it 328dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // will require Tarjan's DFS to backtrack and finish processing all of the 329dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // children of each node in the SCC. 330dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::unique_ptr<Module> M = parseAssembly( 331dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @a() {\n" 332dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 333dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @b()\n" 334dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @d()\n" 335dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 336dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n" 337dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @b() {\n" 338dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 339dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @c()\n" 340dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 341dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n" 342dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @c() {\n" 343dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 344dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @a()\n" 345dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 346dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n" 347dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @d() {\n" 348dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 349dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @e()\n" 350dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 351dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n" 352dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @e() {\n" 353dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 354dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @a()\n" 355dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 356dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n"); 357dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph CG(*M); 358dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 359dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Force the graph to be fully expanded. 360dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines auto SCCI = CG.postorder_scc_begin(); 361dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::SCC &SCC = *SCCI++; 362dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(CG.postorder_scc_end(), SCCI); 363dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 364dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 365dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 366dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 367dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); 368dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &E = *CG.lookup(lookupFunction(*M, "e")); 369dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&SCC, CG.lookupSCC(A)); 370dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&SCC, CG.lookupSCC(B)); 371dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&SCC, CG.lookupSCC(C)); 372dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&SCC, CG.lookupSCC(D)); 373dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&SCC, CG.lookupSCC(E)); 374dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 375dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 376dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesTEST(LazyCallGraphTest, OutgoingSCCEdgeInsertion) { 377dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::unique_ptr<Module> M = parseAssembly( 378dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @a() {\n" 379dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 380dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @b()\n" 381dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @c()\n" 382dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 383dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n" 384dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @b() {\n" 385dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 386dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @d()\n" 387dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 388dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n" 389dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @c() {\n" 390dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 391dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @d()\n" 392dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 393dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n" 394dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @d() {\n" 395dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 396dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 397dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n"); 398dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph CG(*M); 399dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 400dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Force the graph to be fully expanded. 401dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (LazyCallGraph::SCC &C : CG.postorder_sccs()) 402dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines (void)C; 403dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 404dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 405dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 406dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 407dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); 408dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::SCC &AC = *CG.lookupSCC(A); 409dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::SCC &BC = *CG.lookupSCC(B); 410dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::SCC &CC = *CG.lookupSCC(C); 411dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::SCC &DC = *CG.lookupSCC(D); 412dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_TRUE(AC.isAncestorOf(BC)); 413dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_TRUE(AC.isAncestorOf(CC)); 414dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_TRUE(AC.isAncestorOf(DC)); 415dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_TRUE(DC.isDescendantOf(AC)); 416dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_TRUE(DC.isDescendantOf(BC)); 417dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_TRUE(DC.isDescendantOf(CC)); 418dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 419dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(2, std::distance(A.begin(), A.end())); 420dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines AC.insertOutgoingEdge(A, D); 421dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(3, std::distance(A.begin(), A.end())); 422dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_TRUE(AC.isParentOf(DC)); 423dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&AC, CG.lookupSCC(A)); 424dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&BC, CG.lookupSCC(B)); 425dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&CC, CG.lookupSCC(C)); 426dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&DC, CG.lookupSCC(D)); 427dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 428dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 429dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesTEST(LazyCallGraphTest, IncomingSCCEdgeInsertion) { 430dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // We want to ensure we can add edges even across complex diamond graphs, so 431dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // we use the diamond of triangles graph defined above. The ascii diagram is 432dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // repeated here for easy reference. 433dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // 434dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // d1 | 435dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // / \ | 436dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // d3--d2 | 437dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // / \ | 438dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // b1 c1 | 439dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // / \ / \ | 440dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // b3--b2 c3--c2 | 441dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // \ / | 442dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // a1 | 443dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // / \ | 444dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // a3--a2 | 445dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // 446dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::unique_ptr<Module> M = parseAssembly(DiamondOfTriangles); 447dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph CG(*M); 448dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 449dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Force the graph to be fully expanded. 450dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (LazyCallGraph::SCC &C : CG.postorder_sccs()) 451dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines (void)C; 452dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 453dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1")); 454dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2")); 455dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3")); 456dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1")); 457dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2")); 458dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3")); 459dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1")); 460dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2")); 461dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3")); 462dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1")); 463dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2")); 464dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3")); 465dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::SCC &AC = *CG.lookupSCC(A1); 466dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::SCC &BC = *CG.lookupSCC(B1); 467dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::SCC &CC = *CG.lookupSCC(C1); 468dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::SCC &DC = *CG.lookupSCC(D1); 469dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ASSERT_EQ(&AC, CG.lookupSCC(A2)); 470dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ASSERT_EQ(&AC, CG.lookupSCC(A3)); 471dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ASSERT_EQ(&BC, CG.lookupSCC(B2)); 472dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ASSERT_EQ(&BC, CG.lookupSCC(B3)); 473dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ASSERT_EQ(&CC, CG.lookupSCC(C2)); 474dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ASSERT_EQ(&CC, CG.lookupSCC(C3)); 475dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ASSERT_EQ(&DC, CG.lookupSCC(D2)); 476dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ASSERT_EQ(&DC, CG.lookupSCC(D3)); 477dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ASSERT_EQ(1, std::distance(D2.begin(), D2.end())); 478dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 479dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Add an edge to make the graph: 480dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // 481dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // d1 | 482dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // / \ | 483dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // d3--d2---. | 484dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // / \ | | 485dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // b1 c1 | | 486dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // / \ / \ / | 487dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // b3--b2 c3--c2 | 488dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // \ / | 489dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // a1 | 490dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // / \ | 491dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // a3--a2 | 492dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CC.insertIncomingEdge(D2, C2); 493dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Make sure we connected the nodes. 494dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(2, std::distance(D2.begin(), D2.end())); 495dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 496dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Make sure we have the correct nodes in the SCC sets. 497dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&AC, CG.lookupSCC(A1)); 498dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&AC, CG.lookupSCC(A2)); 499dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&AC, CG.lookupSCC(A3)); 500dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&BC, CG.lookupSCC(B1)); 501dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&BC, CG.lookupSCC(B2)); 502dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&BC, CG.lookupSCC(B3)); 503dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&CC, CG.lookupSCC(C1)); 504dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&CC, CG.lookupSCC(C2)); 505dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&CC, CG.lookupSCC(C3)); 506dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&CC, CG.lookupSCC(D1)); 507dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&CC, CG.lookupSCC(D2)); 508dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&CC, CG.lookupSCC(D3)); 509dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 510dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // And that ancestry tests have been updated. 511dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_TRUE(AC.isParentOf(BC)); 512dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_TRUE(AC.isParentOf(CC)); 513dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_FALSE(AC.isAncestorOf(DC)); 514dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_FALSE(BC.isAncestorOf(DC)); 515dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_FALSE(CC.isAncestorOf(DC)); 516dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 517dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 518dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesTEST(LazyCallGraphTest, IncomingSCCEdgeInsertionMidTraversal) { 519dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // This is the same fundamental test as the previous, but we perform it 520dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // having only partially walked the SCCs of the graph. 521dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::unique_ptr<Module> M = parseAssembly(DiamondOfTriangles); 522dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph CG(*M); 523dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 524dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Walk the SCCs until we find the one containing 'c1'. 525dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines auto SCCI = CG.postorder_scc_begin(), SCCE = CG.postorder_scc_end(); 526dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ASSERT_NE(SCCI, SCCE); 527dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::SCC &DC = *SCCI; 528dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ASSERT_NE(&DC, nullptr); 529dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ++SCCI; 530dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ASSERT_NE(SCCI, SCCE); 531dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::SCC &CC = *SCCI; 532dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ASSERT_NE(&CC, nullptr); 533dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 534dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a1"))); 535dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a2"))); 536dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a3"))); 537dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b1"))); 538dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b2"))); 539dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b3"))); 540dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1")); 541dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2")); 542dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3")); 543dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1")); 544dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2")); 545dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3")); 546dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ASSERT_EQ(&CC, CG.lookupSCC(C1)); 547dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ASSERT_EQ(&CC, CG.lookupSCC(C2)); 548dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ASSERT_EQ(&CC, CG.lookupSCC(C3)); 549dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ASSERT_EQ(&DC, CG.lookupSCC(D1)); 550dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ASSERT_EQ(&DC, CG.lookupSCC(D2)); 551dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ASSERT_EQ(&DC, CG.lookupSCC(D3)); 552dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ASSERT_EQ(1, std::distance(D2.begin(), D2.end())); 553dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 554dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CC.insertIncomingEdge(D2, C2); 555dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(2, std::distance(D2.begin(), D2.end())); 556dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 557dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Make sure we have the correct nodes in the SCC sets. 558dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&CC, CG.lookupSCC(C1)); 559dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&CC, CG.lookupSCC(C2)); 560dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&CC, CG.lookupSCC(C3)); 561dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&CC, CG.lookupSCC(D1)); 562dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&CC, CG.lookupSCC(D2)); 563dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&CC, CG.lookupSCC(D3)); 564dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 565dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Check that we can form the last two SCCs now in a coherent way. 566dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ++SCCI; 567dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_NE(SCCI, SCCE); 568dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::SCC &BC = *SCCI; 569dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_NE(&BC, nullptr); 570dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&BC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "b1")))); 571dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&BC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "b2")))); 572dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&BC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "b3")))); 573dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ++SCCI; 574dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_NE(SCCI, SCCE); 575dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::SCC &AC = *SCCI; 576dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_NE(&AC, nullptr); 577dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&AC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "a1")))); 578dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&AC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "a2")))); 579dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&AC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "a3")))); 580dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ++SCCI; 581dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(SCCI, SCCE); 582dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 583dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 584dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesTEST(LazyCallGraphTest, InterSCCEdgeRemoval) { 585dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::unique_ptr<Module> M = parseAssembly( 586dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @a() {\n" 587dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 588dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @b()\n" 589dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 590dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n" 591dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @b() {\n" 592dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 593dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 594dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n"); 595dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph CG(*M); 596dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 597dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Force the graph to be fully expanded. 598dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (LazyCallGraph::SCC &C : CG.postorder_sccs()) 599dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines (void)C; 600dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 601dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 602dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 603dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::SCC &AC = *CG.lookupSCC(A); 604dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::SCC &BC = *CG.lookupSCC(B); 605dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 606dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ("b", A.begin()->getFunction().getName()); 607dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(B.end(), B.begin()); 608dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&AC, &*BC.parent_begin()); 609dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 610dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines AC.removeInterSCCEdge(A, B); 611dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 612dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(A.end(), A.begin()); 613dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(B.end(), B.begin()); 614dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(BC.parent_end(), BC.parent_begin()); 615dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 616dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 617dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesTEST(LazyCallGraphTest, IntraSCCEdgeInsertion) { 618dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::unique_ptr<Module> M1 = parseAssembly( 619dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @a() {\n" 620dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 621dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @b()\n" 622dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 623dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n" 624dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @b() {\n" 625dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 626dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @c()\n" 627dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 628dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n" 629dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @c() {\n" 630dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 631dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @a()\n" 632dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 633dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n"); 634dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph CG1(*M1); 635dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 636dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Force the graph to be fully expanded. 637dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines auto SCCI = CG1.postorder_scc_begin(); 638dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::SCC &SCC = *SCCI++; 639dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(CG1.postorder_scc_end(), SCCI); 640dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 641dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &A = *CG1.lookup(lookupFunction(*M1, "a")); 642dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &B = *CG1.lookup(lookupFunction(*M1, "b")); 643dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &C = *CG1.lookup(lookupFunction(*M1, "c")); 644dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&SCC, CG1.lookupSCC(A)); 645dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&SCC, CG1.lookupSCC(B)); 646dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&SCC, CG1.lookupSCC(C)); 647dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 648dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Insert an edge from 'a' to 'c'. Nothing changes about the SCCs. 649dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SCC.insertIntraSCCEdge(A, C); 650dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(2, std::distance(A.begin(), A.end())); 651dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&SCC, CG1.lookupSCC(A)); 652dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&SCC, CG1.lookupSCC(B)); 653dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&SCC, CG1.lookupSCC(C)); 654dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 655dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Insert a self edge from 'a' back to 'a'. 656dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SCC.insertIntraSCCEdge(A, A); 657dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(3, std::distance(A.begin(), A.end())); 658dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&SCC, CG1.lookupSCC(A)); 659dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&SCC, CG1.lookupSCC(B)); 660dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&SCC, CG1.lookupSCC(C)); 661dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 662dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 663dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesTEST(LazyCallGraphTest, IntraSCCEdgeRemoval) { 664dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // A nice fully connected (including self-edges) SCC. 665dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::unique_ptr<Module> M1 = parseAssembly( 666dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @a() {\n" 667dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 668dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @a()\n" 669dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @b()\n" 670dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @c()\n" 671dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 672dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n" 673dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @b() {\n" 674dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 675dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @a()\n" 676dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @b()\n" 677dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @c()\n" 678dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 679dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n" 680dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "define void @c() {\n" 681dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "entry:\n" 682dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @a()\n" 683dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @b()\n" 684dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " call void @c()\n" 685dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " ret void\n" 686dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "}\n"); 687dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph CG1(*M1); 688dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 689dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Force the graph to be fully expanded. 690dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines auto SCCI = CG1.postorder_scc_begin(); 691dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::SCC &SCC = *SCCI++; 692dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(CG1.postorder_scc_end(), SCCI); 693dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 694dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &A = *CG1.lookup(lookupFunction(*M1, "a")); 695dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &B = *CG1.lookup(lookupFunction(*M1, "b")); 696dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::Node &C = *CG1.lookup(lookupFunction(*M1, "c")); 697dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&SCC, CG1.lookupSCC(A)); 698dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&SCC, CG1.lookupSCC(B)); 699dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&SCC, CG1.lookupSCC(C)); 700dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 701dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Remove the edge from b -> a, which should leave the 3 functions still in 702dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // a single connected component because of a -> b -> c -> a. 703dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SmallVector<LazyCallGraph::SCC *, 1> NewSCCs = SCC.removeIntraSCCEdge(B, A); 704dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(0u, NewSCCs.size()); 705dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&SCC, CG1.lookupSCC(A)); 706dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&SCC, CG1.lookupSCC(B)); 707dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&SCC, CG1.lookupSCC(C)); 708dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 709dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Remove the edge from c -> a, which should leave 'a' in the original SCC 710dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // and form a new SCC for 'b' and 'c'. 711dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines NewSCCs = SCC.removeIntraSCCEdge(C, A); 712dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(1u, NewSCCs.size()); 713dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(&SCC, CG1.lookupSCC(A)); 714dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(1, std::distance(SCC.begin(), SCC.end())); 715dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::SCC *SCC2 = CG1.lookupSCC(B); 716dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(SCC2, CG1.lookupSCC(C)); 717dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(SCC2, NewSCCs[0]); 718dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 719dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 720dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 721