3031 lines · cpp
1//===- LazyCallGraphTest.cpp - Unit tests for the lazy CG analysis --------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/Analysis/LazyCallGraph.h"10#include "llvm/AsmParser/Parser.h"11#include "llvm/IR/Function.h"12#include "llvm/IR/Instructions.h"13#include "llvm/IR/LLVMContext.h"14#include "llvm/IR/Module.h"15#include "llvm/IR/Verifier.h"16#include "llvm/Support/ErrorHandling.h"17#include "llvm/Support/SourceMgr.h"18#include "llvm/TargetParser/Triple.h"19#include "gtest/gtest.h"20#include <memory>21 22using namespace llvm;23 24namespace {25 26std::unique_ptr<Module> parseAssembly(LLVMContext &Context,27 const char *Assembly) {28 SMDiagnostic Error;29 std::unique_ptr<Module> M = parseAssemblyString(Assembly, Error, Context);30 31 std::string ErrMsg;32 raw_string_ostream OS(ErrMsg);33 Error.print("", OS);34 35 // A failure here means that the test itself is buggy.36 if (!M)37 report_fatal_error(ErrMsg.c_str());38 39 return M;40}41 42/*43 IR forming a call graph with a diamond of triangle-shaped SCCs:44 45 d146 / \47 d3--d248 / \49 b1 c150 / \ / \51 b3--b2 c3--c252 \ /53 a154 / \55 a3--a256 57 All call edges go up between SCCs, and clockwise around the SCC.58 */59static const char DiamondOfTriangles[] =60 "define void @a1() {\n"61 "entry:\n"62 " call void @a2()\n"63 " call void @b2()\n"64 " call void @c3()\n"65 " ret void\n"66 "}\n"67 "define void @a2() {\n"68 "entry:\n"69 " call void @a3()\n"70 " ret void\n"71 "}\n"72 "define void @a3() {\n"73 "entry:\n"74 " call void @a1()\n"75 " ret void\n"76 "}\n"77 "define void @b1() {\n"78 "entry:\n"79 " call void @b2()\n"80 " call void @d3()\n"81 " ret void\n"82 "}\n"83 "define void @b2() {\n"84 "entry:\n"85 " call void @b3()\n"86 " ret void\n"87 "}\n"88 "define void @b3() {\n"89 "entry:\n"90 " call void @b1()\n"91 " ret void\n"92 "}\n"93 "define void @c1() {\n"94 "entry:\n"95 " call void @c2()\n"96 " call void @d2()\n"97 " ret void\n"98 "}\n"99 "define void @c2() {\n"100 "entry:\n"101 " call void @c3()\n"102 " ret void\n"103 "}\n"104 "define void @c3() {\n"105 "entry:\n"106 " call void @c1()\n"107 " ret void\n"108 "}\n"109 "define void @d1() {\n"110 "entry:\n"111 " call void @d2()\n"112 " ret void\n"113 "}\n"114 "define void @d2() {\n"115 "entry:\n"116 " call void @d3()\n"117 " ret void\n"118 "}\n"119 "define void @d3() {\n"120 "entry:\n"121 " call void @d1()\n"122 " ret void\n"123 "}\n";124 125/*126 IR forming a reference graph with a diamond of triangle-shaped RefSCCs127 128 d1129 / \130 d3--d2131 / \132 b1 c1133 / \ / \134 b3--b2 c3--c2135 \ /136 a1137 / \138 a3--a2139 140 All call edges go up between RefSCCs, and clockwise around the RefSCC.141 */142static const char DiamondOfTrianglesRefGraph[] =143 "define void @a1() {\n"144 "entry:\n"145 " %a = alloca ptr\n"146 " store ptr @a2, ptr %a\n"147 " store ptr @b2, ptr %a\n"148 " store ptr @c3, ptr %a\n"149 " ret void\n"150 "}\n"151 "define void @a2() {\n"152 "entry:\n"153 " %a = alloca ptr\n"154 " store ptr @a3, ptr %a\n"155 " ret void\n"156 "}\n"157 "define void @a3() {\n"158 "entry:\n"159 " %a = alloca ptr\n"160 " store ptr @a1, ptr %a\n"161 " ret void\n"162 "}\n"163 "define void @b1() {\n"164 "entry:\n"165 " %a = alloca ptr\n"166 " store ptr @b2, ptr %a\n"167 " store ptr @d3, ptr %a\n"168 " ret void\n"169 "}\n"170 "define void @b2() {\n"171 "entry:\n"172 " %a = alloca ptr\n"173 " store ptr @b3, ptr %a\n"174 " ret void\n"175 "}\n"176 "define void @b3() {\n"177 "entry:\n"178 " %a = alloca ptr\n"179 " store ptr @b1, ptr %a\n"180 " ret void\n"181 "}\n"182 "define void @c1() {\n"183 "entry:\n"184 " %a = alloca ptr\n"185 " store ptr @c2, ptr %a\n"186 " store ptr @d2, ptr %a\n"187 " ret void\n"188 "}\n"189 "define void @c2() {\n"190 "entry:\n"191 " %a = alloca ptr\n"192 " store ptr @c3, ptr %a\n"193 " ret void\n"194 "}\n"195 "define void @c3() {\n"196 "entry:\n"197 " %a = alloca ptr\n"198 " store ptr @c1, ptr %a\n"199 " ret void\n"200 "}\n"201 "define void @d1() {\n"202 "entry:\n"203 " %a = alloca ptr\n"204 " store ptr @d2, ptr %a\n"205 " ret void\n"206 "}\n"207 "define void @d2() {\n"208 "entry:\n"209 " %a = alloca ptr\n"210 " store ptr @d3, ptr %a\n"211 " ret void\n"212 "}\n"213 "define void @d3() {\n"214 "entry:\n"215 " %a = alloca ptr\n"216 " store ptr @d1, ptr %a\n"217 " ret void\n"218 "}\n";219 220static LazyCallGraph buildCG(Module &M) {221 TargetLibraryInfoImpl TLII(M.getTargetTriple());222 TargetLibraryInfo TLI(TLII);223 auto GetTLI = [&TLI](Function &F) -> TargetLibraryInfo & { return TLI; };224 225 LazyCallGraph CG(M, GetTLI);226 return CG;227}228 229TEST(LazyCallGraphTest, BasicGraphFormation) {230 LLVMContext Context;231 std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles);232 LazyCallGraph CG = buildCG(*M);233 234 // The order of the entry nodes should be stable w.r.t. the source order of235 // the IR, and everything in our module is an entry node, so just directly236 // build variables for each node.237 auto I = CG.begin();238 LazyCallGraph::Node &A1 = (I++)->getNode();239 EXPECT_EQ("a1", A1.getFunction().getName());240 LazyCallGraph::Node &A2 = (I++)->getNode();241 EXPECT_EQ("a2", A2.getFunction().getName());242 LazyCallGraph::Node &A3 = (I++)->getNode();243 EXPECT_EQ("a3", A3.getFunction().getName());244 LazyCallGraph::Node &B1 = (I++)->getNode();245 EXPECT_EQ("b1", B1.getFunction().getName());246 LazyCallGraph::Node &B2 = (I++)->getNode();247 EXPECT_EQ("b2", B2.getFunction().getName());248 LazyCallGraph::Node &B3 = (I++)->getNode();249 EXPECT_EQ("b3", B3.getFunction().getName());250 LazyCallGraph::Node &C1 = (I++)->getNode();251 EXPECT_EQ("c1", C1.getFunction().getName());252 LazyCallGraph::Node &C2 = (I++)->getNode();253 EXPECT_EQ("c2", C2.getFunction().getName());254 LazyCallGraph::Node &C3 = (I++)->getNode();255 EXPECT_EQ("c3", C3.getFunction().getName());256 LazyCallGraph::Node &D1 = (I++)->getNode();257 EXPECT_EQ("d1", D1.getFunction().getName());258 LazyCallGraph::Node &D2 = (I++)->getNode();259 EXPECT_EQ("d2", D2.getFunction().getName());260 LazyCallGraph::Node &D3 = (I++)->getNode();261 EXPECT_EQ("d3", D3.getFunction().getName());262 EXPECT_EQ(CG.end(), I);263 264 // Build vectors and sort them for the rest of the assertions to make them265 // independent of order.266 std::vector<std::string> Nodes;267 268 for (LazyCallGraph::Edge &E : A1.populate())269 Nodes.push_back(std::string(E.getFunction().getName()));270 llvm::sort(Nodes);271 EXPECT_EQ("a2", Nodes[0]);272 EXPECT_EQ("b2", Nodes[1]);273 EXPECT_EQ("c3", Nodes[2]);274 Nodes.clear();275 276 A2.populate();277 EXPECT_EQ(A2->end(), std::next(A2->begin()));278 EXPECT_EQ("a3", A2->begin()->getFunction().getName());279 A3.populate();280 EXPECT_EQ(A3->end(), std::next(A3->begin()));281 EXPECT_EQ("a1", A3->begin()->getFunction().getName());282 283 for (LazyCallGraph::Edge &E : B1.populate())284 Nodes.push_back(std::string(E.getFunction().getName()));285 llvm::sort(Nodes);286 EXPECT_EQ("b2", Nodes[0]);287 EXPECT_EQ("d3", Nodes[1]);288 Nodes.clear();289 290 B2.populate();291 EXPECT_EQ(B2->end(), std::next(B2->begin()));292 EXPECT_EQ("b3", B2->begin()->getFunction().getName());293 B3.populate();294 EXPECT_EQ(B3->end(), std::next(B3->begin()));295 EXPECT_EQ("b1", B3->begin()->getFunction().getName());296 297 for (LazyCallGraph::Edge &E : C1.populate())298 Nodes.push_back(std::string(E.getFunction().getName()));299 llvm::sort(Nodes);300 EXPECT_EQ("c2", Nodes[0]);301 EXPECT_EQ("d2", Nodes[1]);302 Nodes.clear();303 304 C2.populate();305 EXPECT_EQ(C2->end(), std::next(C2->begin()));306 EXPECT_EQ("c3", C2->begin()->getFunction().getName());307 C3.populate();308 EXPECT_EQ(C3->end(), std::next(C3->begin()));309 EXPECT_EQ("c1", C3->begin()->getFunction().getName());310 311 D1.populate();312 EXPECT_EQ(D1->end(), std::next(D1->begin()));313 EXPECT_EQ("d2", D1->begin()->getFunction().getName());314 D2.populate();315 EXPECT_EQ(D2->end(), std::next(D2->begin()));316 EXPECT_EQ("d3", D2->begin()->getFunction().getName());317 D3.populate();318 EXPECT_EQ(D3->end(), std::next(D3->begin()));319 EXPECT_EQ("d1", D3->begin()->getFunction().getName());320 321 // Now lets look at the RefSCCs and SCCs.322 CG.buildRefSCCs();323 auto J = CG.postorder_ref_scc_begin();324 325 LazyCallGraph::RefSCC &D = *J++;326 ASSERT_EQ(1, D.size());327 for (LazyCallGraph::Node &N : *D.begin())328 Nodes.push_back(std::string(N.getFunction().getName()));329 llvm::sort(Nodes);330 EXPECT_EQ(3u, Nodes.size());331 EXPECT_EQ("d1", Nodes[0]);332 EXPECT_EQ("d2", Nodes[1]);333 EXPECT_EQ("d3", Nodes[2]);334 Nodes.clear();335 EXPECT_FALSE(D.isParentOf(D));336 EXPECT_FALSE(D.isChildOf(D));337 EXPECT_FALSE(D.isAncestorOf(D));338 EXPECT_FALSE(D.isDescendantOf(D));339 EXPECT_EQ(&D, &*CG.postorder_ref_scc_begin());340 341 LazyCallGraph::RefSCC &B = *J++;342 ASSERT_EQ(1, B.size());343 for (LazyCallGraph::Node &N : *B.begin())344 Nodes.push_back(std::string(N.getFunction().getName()));345 llvm::sort(Nodes);346 EXPECT_EQ(3u, Nodes.size());347 EXPECT_EQ("b1", Nodes[0]);348 EXPECT_EQ("b2", Nodes[1]);349 EXPECT_EQ("b3", Nodes[2]);350 Nodes.clear();351 EXPECT_TRUE(B.isParentOf(D));352 EXPECT_FALSE(B.isChildOf(D));353 EXPECT_TRUE(B.isAncestorOf(D));354 EXPECT_FALSE(B.isDescendantOf(D));355 EXPECT_EQ(&B, &*std::next(CG.postorder_ref_scc_begin()));356 357 LazyCallGraph::RefSCC &C = *J++;358 ASSERT_EQ(1, C.size());359 for (LazyCallGraph::Node &N : *C.begin())360 Nodes.push_back(std::string(N.getFunction().getName()));361 llvm::sort(Nodes);362 EXPECT_EQ(3u, Nodes.size());363 EXPECT_EQ("c1", Nodes[0]);364 EXPECT_EQ("c2", Nodes[1]);365 EXPECT_EQ("c3", Nodes[2]);366 Nodes.clear();367 EXPECT_FALSE(B.isAncestorOf(C));368 EXPECT_FALSE(C.isAncestorOf(B));369 EXPECT_TRUE(C.isParentOf(D));370 EXPECT_FALSE(C.isChildOf(D));371 EXPECT_TRUE(C.isAncestorOf(D));372 EXPECT_FALSE(C.isDescendantOf(D));373 EXPECT_EQ(&C, &*std::next(CG.postorder_ref_scc_begin(), 2));374 375 LazyCallGraph::RefSCC &A = *J++;376 ASSERT_EQ(1, A.size());377 for (LazyCallGraph::Node &N : *A.begin())378 Nodes.push_back(std::string(N.getFunction().getName()));379 llvm::sort(Nodes);380 EXPECT_EQ(3u, Nodes.size());381 EXPECT_EQ("a1", Nodes[0]);382 EXPECT_EQ("a2", Nodes[1]);383 EXPECT_EQ("a3", Nodes[2]);384 Nodes.clear();385 EXPECT_TRUE(A.isParentOf(B));386 EXPECT_TRUE(A.isParentOf(C));387 EXPECT_FALSE(A.isParentOf(D));388 EXPECT_TRUE(A.isAncestorOf(B));389 EXPECT_TRUE(A.isAncestorOf(C));390 EXPECT_TRUE(A.isAncestorOf(D));391 EXPECT_EQ(&A, &*std::next(CG.postorder_ref_scc_begin(), 3));392 393 EXPECT_EQ(CG.postorder_ref_scc_end(), J);394 EXPECT_EQ(J, std::next(CG.postorder_ref_scc_begin(), 4));395}396 397static Function &lookupFunction(Module &M, StringRef Name) {398 for (Function &F : M)399 if (F.getName() == Name)400 return F;401 report_fatal_error("Couldn't find function!");402}403 404TEST(LazyCallGraphTest, BasicGraphMutation) {405 LLVMContext Context;406 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"407 "entry:\n"408 " call void @b()\n"409 " call void @c()\n"410 " ret void\n"411 "}\n"412 "define void @b() {\n"413 "entry:\n"414 " ret void\n"415 "}\n"416 "define void @c() {\n"417 "entry:\n"418 " ret void\n"419 "}\n");420 LazyCallGraph CG = buildCG(*M);421 422 LazyCallGraph::Node &A = CG.get(lookupFunction(*M, "a"));423 LazyCallGraph::Node &B = CG.get(lookupFunction(*M, "b"));424 A.populate();425 EXPECT_EQ(2, std::distance(A->begin(), A->end()));426 B.populate();427 EXPECT_EQ(0, std::distance(B->begin(), B->end()));428 429 LazyCallGraph::Node &C = CG.get(lookupFunction(*M, "c"));430 C.populate();431 CG.insertEdge(B, C, LazyCallGraph::Edge::Call);432 EXPECT_EQ(1, std::distance(B->begin(), B->end()));433 EXPECT_EQ(0, std::distance(C->begin(), C->end()));434 435 CG.insertEdge(C, B, LazyCallGraph::Edge::Call);436 EXPECT_EQ(1, std::distance(C->begin(), C->end()));437 EXPECT_EQ(&B, &C->begin()->getNode());438 439 CG.insertEdge(C, C, LazyCallGraph::Edge::Call);440 EXPECT_EQ(2, std::distance(C->begin(), C->end()));441 EXPECT_EQ(&B, &C->begin()->getNode());442 EXPECT_EQ(&C, &std::next(C->begin())->getNode());443 444 CG.removeEdge(C, B);445 EXPECT_EQ(1, std::distance(C->begin(), C->end()));446 EXPECT_EQ(&C, &C->begin()->getNode());447 448 CG.removeEdge(C, C);449 EXPECT_EQ(0, std::distance(C->begin(), C->end()));450 451 CG.removeEdge(B, C);452 EXPECT_EQ(0, std::distance(B->begin(), B->end()));453}454 455TEST(LazyCallGraphTest, InnerSCCFormation) {456 LLVMContext Context;457 std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles);458 LazyCallGraph CG = buildCG(*M);459 460 // Now mutate the graph to connect every node into a single RefSCC to ensure461 // that our inner SCC formation handles the rest.462 LazyCallGraph::Node &D1 = CG.get(lookupFunction(*M, "d1"));463 LazyCallGraph::Node &A1 = CG.get(lookupFunction(*M, "a1"));464 A1.populate();465 D1.populate();466 CG.insertEdge(D1, A1, LazyCallGraph::Edge::Ref);467 468 // Build vectors and sort them for the rest of the assertions to make them469 // independent of order.470 std::vector<std::string> Nodes;471 472 // We should build a single RefSCC for the entire graph.473 CG.buildRefSCCs();474 auto I = CG.postorder_ref_scc_begin();475 LazyCallGraph::RefSCC &RC = *I++;476 EXPECT_EQ(CG.postorder_ref_scc_end(), I);477 478 // Now walk the four SCCs which should be in post-order.479 auto J = RC.begin();480 LazyCallGraph::SCC &D = *J++;481 for (LazyCallGraph::Node &N : D)482 Nodes.push_back(std::string(N.getFunction().getName()));483 llvm::sort(Nodes);484 EXPECT_EQ(3u, Nodes.size());485 EXPECT_EQ("d1", Nodes[0]);486 EXPECT_EQ("d2", Nodes[1]);487 EXPECT_EQ("d3", Nodes[2]);488 Nodes.clear();489 490 LazyCallGraph::SCC &B = *J++;491 for (LazyCallGraph::Node &N : B)492 Nodes.push_back(std::string(N.getFunction().getName()));493 llvm::sort(Nodes);494 EXPECT_EQ(3u, Nodes.size());495 EXPECT_EQ("b1", Nodes[0]);496 EXPECT_EQ("b2", Nodes[1]);497 EXPECT_EQ("b3", Nodes[2]);498 Nodes.clear();499 500 LazyCallGraph::SCC &C = *J++;501 for (LazyCallGraph::Node &N : C)502 Nodes.push_back(std::string(N.getFunction().getName()));503 llvm::sort(Nodes);504 EXPECT_EQ(3u, Nodes.size());505 EXPECT_EQ("c1", Nodes[0]);506 EXPECT_EQ("c2", Nodes[1]);507 EXPECT_EQ("c3", Nodes[2]);508 Nodes.clear();509 510 LazyCallGraph::SCC &A = *J++;511 for (LazyCallGraph::Node &N : A)512 Nodes.push_back(std::string(N.getFunction().getName()));513 llvm::sort(Nodes);514 EXPECT_EQ(3u, Nodes.size());515 EXPECT_EQ("a1", Nodes[0]);516 EXPECT_EQ("a2", Nodes[1]);517 EXPECT_EQ("a3", Nodes[2]);518 Nodes.clear();519 520 EXPECT_EQ(RC.end(), J);521}522 523TEST(LazyCallGraphTest, MultiArmSCC) {524 LLVMContext Context;525 // Two interlocking cycles. The really useful thing about this SCC is that it526 // will require Tarjan's DFS to backtrack and finish processing all of the527 // children of each node in the SCC. Since this involves call edges, both528 // Tarjan implementations will have to successfully navigate the structure.529 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f1() {\n"530 "entry:\n"531 " call void @f2()\n"532 " call void @f4()\n"533 " ret void\n"534 "}\n"535 "define void @f2() {\n"536 "entry:\n"537 " call void @f3()\n"538 " ret void\n"539 "}\n"540 "define void @f3() {\n"541 "entry:\n"542 " call void @f1()\n"543 " ret void\n"544 "}\n"545 "define void @f4() {\n"546 "entry:\n"547 " call void @f5()\n"548 " ret void\n"549 "}\n"550 "define void @f5() {\n"551 "entry:\n"552 " call void @f1()\n"553 " ret void\n"554 "}\n");555 LazyCallGraph CG = buildCG(*M);556 557 // Force the graph to be fully expanded.558 CG.buildRefSCCs();559 auto I = CG.postorder_ref_scc_begin();560 LazyCallGraph::RefSCC &RC = *I++;561 EXPECT_EQ(CG.postorder_ref_scc_end(), I);562 563 LazyCallGraph::Node &N1 = *CG.lookup(lookupFunction(*M, "f1"));564 LazyCallGraph::Node &N2 = *CG.lookup(lookupFunction(*M, "f2"));565 LazyCallGraph::Node &N3 = *CG.lookup(lookupFunction(*M, "f3"));566 LazyCallGraph::Node &N4 = *CG.lookup(lookupFunction(*M, "f4"));567 LazyCallGraph::Node &N5 = *CG.lookup(lookupFunction(*M, "f4"));568 EXPECT_EQ(&RC, CG.lookupRefSCC(N1));569 EXPECT_EQ(&RC, CG.lookupRefSCC(N2));570 EXPECT_EQ(&RC, CG.lookupRefSCC(N3));571 EXPECT_EQ(&RC, CG.lookupRefSCC(N4));572 EXPECT_EQ(&RC, CG.lookupRefSCC(N5));573 574 ASSERT_EQ(1, RC.size());575 576 LazyCallGraph::SCC &C = *RC.begin();577 EXPECT_EQ(&C, CG.lookupSCC(N1));578 EXPECT_EQ(&C, CG.lookupSCC(N2));579 EXPECT_EQ(&C, CG.lookupSCC(N3));580 EXPECT_EQ(&C, CG.lookupSCC(N4));581 EXPECT_EQ(&C, CG.lookupSCC(N5));582}583 584TEST(LazyCallGraphTest, OutgoingEdgeMutation) {585 LLVMContext Context;586 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"587 "entry:\n"588 " call void @b()\n"589 " call void @c()\n"590 " ret void\n"591 "}\n"592 "define void @b() {\n"593 "entry:\n"594 " call void @d()\n"595 " ret void\n"596 "}\n"597 "define void @c() {\n"598 "entry:\n"599 " call void @d()\n"600 " ret void\n"601 "}\n"602 "define void @d() {\n"603 "entry:\n"604 " ret void\n"605 "}\n");606 LazyCallGraph CG = buildCG(*M);607 608 // Force the graph to be fully expanded.609 CG.buildRefSCCs();610 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())611 dbgs() << "Formed RefSCC: " << RC << "\n";612 613 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));614 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));615 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));616 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));617 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);618 LazyCallGraph::SCC &BC = *CG.lookupSCC(B);619 LazyCallGraph::SCC &CC = *CG.lookupSCC(C);620 LazyCallGraph::SCC &DC = *CG.lookupSCC(D);621 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A);622 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B);623 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C);624 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D);625 EXPECT_TRUE(ARC.isParentOf(BRC));626 EXPECT_TRUE(AC.isParentOf(BC));627 EXPECT_TRUE(ARC.isParentOf(CRC));628 EXPECT_TRUE(AC.isParentOf(CC));629 EXPECT_FALSE(ARC.isParentOf(DRC));630 EXPECT_FALSE(AC.isParentOf(DC));631 EXPECT_TRUE(ARC.isAncestorOf(DRC));632 EXPECT_TRUE(AC.isAncestorOf(DC));633 EXPECT_FALSE(DRC.isChildOf(ARC));634 EXPECT_FALSE(DC.isChildOf(AC));635 EXPECT_TRUE(DRC.isDescendantOf(ARC));636 EXPECT_TRUE(DC.isDescendantOf(AC));637 EXPECT_TRUE(DRC.isChildOf(BRC));638 EXPECT_TRUE(DC.isChildOf(BC));639 EXPECT_TRUE(DRC.isChildOf(CRC));640 EXPECT_TRUE(DC.isChildOf(CC));641 642 EXPECT_EQ(2, std::distance(A->begin(), A->end()));643 ARC.insertOutgoingEdge(A, D, LazyCallGraph::Edge::Call);644 EXPECT_EQ(3, std::distance(A->begin(), A->end()));645 const LazyCallGraph::Edge &NewE = (*A)[D];646 EXPECT_TRUE(NewE);647 EXPECT_TRUE(NewE.isCall());648 EXPECT_EQ(&D, &NewE.getNode());649 650 // Only the parent and child tests sholud have changed. The rest of the graph651 // remains the same.652 EXPECT_TRUE(ARC.isParentOf(DRC));653 EXPECT_TRUE(AC.isParentOf(DC));654 EXPECT_TRUE(ARC.isAncestorOf(DRC));655 EXPECT_TRUE(AC.isAncestorOf(DC));656 EXPECT_TRUE(DRC.isChildOf(ARC));657 EXPECT_TRUE(DC.isChildOf(AC));658 EXPECT_TRUE(DRC.isDescendantOf(ARC));659 EXPECT_TRUE(DC.isDescendantOf(AC));660 EXPECT_EQ(&AC, CG.lookupSCC(A));661 EXPECT_EQ(&BC, CG.lookupSCC(B));662 EXPECT_EQ(&CC, CG.lookupSCC(C));663 EXPECT_EQ(&DC, CG.lookupSCC(D));664 EXPECT_EQ(&ARC, CG.lookupRefSCC(A));665 EXPECT_EQ(&BRC, CG.lookupRefSCC(B));666 EXPECT_EQ(&CRC, CG.lookupRefSCC(C));667 EXPECT_EQ(&DRC, CG.lookupRefSCC(D));668 669 ARC.switchOutgoingEdgeToRef(A, D);670 EXPECT_FALSE(NewE.isCall());671 672 // Verify the reference graph remains the same but the SCC graph is updated.673 EXPECT_TRUE(ARC.isParentOf(DRC));674 EXPECT_FALSE(AC.isParentOf(DC));675 EXPECT_TRUE(ARC.isAncestorOf(DRC));676 EXPECT_TRUE(AC.isAncestorOf(DC));677 EXPECT_TRUE(DRC.isChildOf(ARC));678 EXPECT_FALSE(DC.isChildOf(AC));679 EXPECT_TRUE(DRC.isDescendantOf(ARC));680 EXPECT_TRUE(DC.isDescendantOf(AC));681 EXPECT_EQ(&AC, CG.lookupSCC(A));682 EXPECT_EQ(&BC, CG.lookupSCC(B));683 EXPECT_EQ(&CC, CG.lookupSCC(C));684 EXPECT_EQ(&DC, CG.lookupSCC(D));685 EXPECT_EQ(&ARC, CG.lookupRefSCC(A));686 EXPECT_EQ(&BRC, CG.lookupRefSCC(B));687 EXPECT_EQ(&CRC, CG.lookupRefSCC(C));688 EXPECT_EQ(&DRC, CG.lookupRefSCC(D));689 690 ARC.switchOutgoingEdgeToCall(A, D);691 EXPECT_TRUE(NewE.isCall());692 693 // Verify the reference graph remains the same but the SCC graph is updated.694 EXPECT_TRUE(ARC.isParentOf(DRC));695 EXPECT_TRUE(AC.isParentOf(DC));696 EXPECT_TRUE(ARC.isAncestorOf(DRC));697 EXPECT_TRUE(AC.isAncestorOf(DC));698 EXPECT_TRUE(DRC.isChildOf(ARC));699 EXPECT_TRUE(DC.isChildOf(AC));700 EXPECT_TRUE(DRC.isDescendantOf(ARC));701 EXPECT_TRUE(DC.isDescendantOf(AC));702 EXPECT_EQ(&AC, CG.lookupSCC(A));703 EXPECT_EQ(&BC, CG.lookupSCC(B));704 EXPECT_EQ(&CC, CG.lookupSCC(C));705 EXPECT_EQ(&DC, CG.lookupSCC(D));706 EXPECT_EQ(&ARC, CG.lookupRefSCC(A));707 EXPECT_EQ(&BRC, CG.lookupRefSCC(B));708 EXPECT_EQ(&CRC, CG.lookupRefSCC(C));709 EXPECT_EQ(&DRC, CG.lookupRefSCC(D));710 711 ARC.removeOutgoingEdge(A, D);712 EXPECT_EQ(2, std::distance(A->begin(), A->end()));713 714 // Now the parent and child tests fail again but the rest remains the same.715 EXPECT_FALSE(ARC.isParentOf(DRC));716 EXPECT_FALSE(AC.isParentOf(DC));717 EXPECT_TRUE(ARC.isAncestorOf(DRC));718 EXPECT_TRUE(AC.isAncestorOf(DC));719 EXPECT_FALSE(DRC.isChildOf(ARC));720 EXPECT_FALSE(DC.isChildOf(AC));721 EXPECT_TRUE(DRC.isDescendantOf(ARC));722 EXPECT_TRUE(DC.isDescendantOf(AC));723 EXPECT_EQ(&AC, CG.lookupSCC(A));724 EXPECT_EQ(&BC, CG.lookupSCC(B));725 EXPECT_EQ(&CC, CG.lookupSCC(C));726 EXPECT_EQ(&DC, CG.lookupSCC(D));727 EXPECT_EQ(&ARC, CG.lookupRefSCC(A));728 EXPECT_EQ(&BRC, CG.lookupRefSCC(B));729 EXPECT_EQ(&CRC, CG.lookupRefSCC(C));730 EXPECT_EQ(&DRC, CG.lookupRefSCC(D));731}732 733TEST(LazyCallGraphTest, IncomingEdgeInsertion) {734 LLVMContext Context;735 // We want to ensure we can add edges even across complex diamond graphs, so736 // we use the diamond of triangles graph defined above. The ascii diagram is737 // repeated here for easy reference.738 //739 // d1 |740 // / \ |741 // d3--d2 |742 // / \ |743 // b1 c1 |744 // / \ / \ |745 // b3--b2 c3--c2 |746 // \ / |747 // a1 |748 // / \ |749 // a3--a2 |750 //751 std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles);752 LazyCallGraph CG = buildCG(*M);753 754 // Force the graph to be fully expanded.755 CG.buildRefSCCs();756 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())757 dbgs() << "Formed RefSCC: " << RC << "\n";758 759 LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1"));760 LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2"));761 LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3"));762 LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1"));763 LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2"));764 LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3"));765 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1"));766 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2"));767 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3"));768 LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1"));769 LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2"));770 LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3"));771 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A1);772 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B1);773 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C1);774 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D1);775 ASSERT_EQ(&ARC, CG.lookupRefSCC(A2));776 ASSERT_EQ(&ARC, CG.lookupRefSCC(A3));777 ASSERT_EQ(&BRC, CG.lookupRefSCC(B2));778 ASSERT_EQ(&BRC, CG.lookupRefSCC(B3));779 ASSERT_EQ(&CRC, CG.lookupRefSCC(C2));780 ASSERT_EQ(&CRC, CG.lookupRefSCC(C3));781 ASSERT_EQ(&DRC, CG.lookupRefSCC(D2));782 ASSERT_EQ(&DRC, CG.lookupRefSCC(D3));783 ASSERT_EQ(1, std::distance(D2->begin(), D2->end()));784 785 // Add an edge to make the graph:786 //787 // d1 |788 // / \ |789 // d3--d2---. |790 // / \ | |791 // b1 c1 | |792 // / \ / \ / |793 // b3--b2 c3--c2 |794 // \ / |795 // a1 |796 // / \ |797 // a3--a2 |798 auto MergedRCs = CRC.insertIncomingRefEdge(D2, C2);799 // Make sure we connected the nodes.800 for (LazyCallGraph::Edge E : *D2) {801 if (&E.getNode() == &D3)802 continue;803 EXPECT_EQ(&C2, &E.getNode());804 }805 // And marked the D ref-SCC as no longer valid.806 EXPECT_EQ(1u, MergedRCs.size());807 EXPECT_EQ(&DRC, MergedRCs[0]);808 809 // Make sure we have the correct nodes in the SCC sets.810 EXPECT_EQ(&ARC, CG.lookupRefSCC(A1));811 EXPECT_EQ(&ARC, CG.lookupRefSCC(A2));812 EXPECT_EQ(&ARC, CG.lookupRefSCC(A3));813 EXPECT_EQ(&BRC, CG.lookupRefSCC(B1));814 EXPECT_EQ(&BRC, CG.lookupRefSCC(B2));815 EXPECT_EQ(&BRC, CG.lookupRefSCC(B3));816 EXPECT_EQ(&CRC, CG.lookupRefSCC(C1));817 EXPECT_EQ(&CRC, CG.lookupRefSCC(C2));818 EXPECT_EQ(&CRC, CG.lookupRefSCC(C3));819 EXPECT_EQ(&CRC, CG.lookupRefSCC(D1));820 EXPECT_EQ(&CRC, CG.lookupRefSCC(D2));821 EXPECT_EQ(&CRC, CG.lookupRefSCC(D3));822 823 // And that ancestry tests have been updated.824 EXPECT_TRUE(ARC.isParentOf(CRC));825 EXPECT_TRUE(BRC.isParentOf(CRC));826 827 // And verify the post-order walk reflects the updated structure.828 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();829 ASSERT_NE(I, E);830 EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I;831 ASSERT_NE(++I, E);832 EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I;833 ASSERT_NE(++I, E);834 EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;835 EXPECT_EQ(++I, E);836}837 838TEST(LazyCallGraphTest, IncomingEdgeInsertionRefGraph) {839 LLVMContext Context;840 // Another variation of the above test but with all the edges switched to841 // references rather than calls.842 std::unique_ptr<Module> M =843 parseAssembly(Context, DiamondOfTrianglesRefGraph);844 LazyCallGraph CG = buildCG(*M);845 846 // Force the graph to be fully expanded.847 CG.buildRefSCCs();848 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())849 dbgs() << "Formed RefSCC: " << RC << "\n";850 851 LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1"));852 LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2"));853 LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3"));854 LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1"));855 LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2"));856 LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3"));857 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1"));858 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2"));859 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3"));860 LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1"));861 LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2"));862 LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3"));863 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A1);864 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B1);865 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C1);866 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D1);867 ASSERT_EQ(&ARC, CG.lookupRefSCC(A2));868 ASSERT_EQ(&ARC, CG.lookupRefSCC(A3));869 ASSERT_EQ(&BRC, CG.lookupRefSCC(B2));870 ASSERT_EQ(&BRC, CG.lookupRefSCC(B3));871 ASSERT_EQ(&CRC, CG.lookupRefSCC(C2));872 ASSERT_EQ(&CRC, CG.lookupRefSCC(C3));873 ASSERT_EQ(&DRC, CG.lookupRefSCC(D2));874 ASSERT_EQ(&DRC, CG.lookupRefSCC(D3));875 ASSERT_EQ(1, std::distance(D2->begin(), D2->end()));876 877 // Add an edge to make the graph:878 //879 // d1 |880 // / \ |881 // d3--d2---. |882 // / \ | |883 // b1 c1 | |884 // / \ / \ / |885 // b3--b2 c3--c2 |886 // \ / |887 // a1 |888 // / \ |889 // a3--a2 |890 auto MergedRCs = CRC.insertIncomingRefEdge(D2, C2);891 // Make sure we connected the nodes.892 for (LazyCallGraph::Edge E : *D2) {893 if (&E.getNode() == &D3)894 continue;895 EXPECT_EQ(&C2, &E.getNode());896 }897 // And marked the D ref-SCC as no longer valid.898 EXPECT_EQ(1u, MergedRCs.size());899 EXPECT_EQ(&DRC, MergedRCs[0]);900 901 // Make sure we have the correct nodes in the SCC sets.902 EXPECT_EQ(&ARC, CG.lookupRefSCC(A1));903 EXPECT_EQ(&ARC, CG.lookupRefSCC(A2));904 EXPECT_EQ(&ARC, CG.lookupRefSCC(A3));905 EXPECT_EQ(&BRC, CG.lookupRefSCC(B1));906 EXPECT_EQ(&BRC, CG.lookupRefSCC(B2));907 EXPECT_EQ(&BRC, CG.lookupRefSCC(B3));908 EXPECT_EQ(&CRC, CG.lookupRefSCC(C1));909 EXPECT_EQ(&CRC, CG.lookupRefSCC(C2));910 EXPECT_EQ(&CRC, CG.lookupRefSCC(C3));911 EXPECT_EQ(&CRC, CG.lookupRefSCC(D1));912 EXPECT_EQ(&CRC, CG.lookupRefSCC(D2));913 EXPECT_EQ(&CRC, CG.lookupRefSCC(D3));914 915 // And that ancestry tests have been updated.916 EXPECT_TRUE(ARC.isParentOf(CRC));917 EXPECT_TRUE(BRC.isParentOf(CRC));918 919 // And verify the post-order walk reflects the updated structure.920 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();921 ASSERT_NE(I, E);922 EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I;923 ASSERT_NE(++I, E);924 EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I;925 ASSERT_NE(++I, E);926 EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;927 EXPECT_EQ(++I, E);928}929 930TEST(LazyCallGraphTest, IncomingEdgeInsertionLargeCallCycle) {931 LLVMContext Context;932 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"933 "entry:\n"934 " call void @b()\n"935 " ret void\n"936 "}\n"937 "define void @b() {\n"938 "entry:\n"939 " call void @c()\n"940 " ret void\n"941 "}\n"942 "define void @c() {\n"943 "entry:\n"944 " call void @d()\n"945 " ret void\n"946 "}\n"947 "define void @d() {\n"948 "entry:\n"949 " ret void\n"950 "}\n");951 LazyCallGraph CG = buildCG(*M);952 953 // Force the graph to be fully expanded.954 CG.buildRefSCCs();955 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())956 dbgs() << "Formed RefSCC: " << RC << "\n";957 958 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));959 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));960 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));961 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));962 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);963 LazyCallGraph::SCC &BC = *CG.lookupSCC(B);964 LazyCallGraph::SCC &CC = *CG.lookupSCC(C);965 LazyCallGraph::SCC &DC = *CG.lookupSCC(D);966 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A);967 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B);968 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C);969 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D);970 971 // Connect the top to the bottom forming a large RefSCC made up mostly of calls.972 auto MergedRCs = ARC.insertIncomingRefEdge(D, A);973 // Make sure we connected the nodes.974 EXPECT_NE(D->begin(), D->end());975 EXPECT_EQ(&A, &D->begin()->getNode());976 977 // Check that we have the dead RCs, but ignore the order.978 EXPECT_EQ(3u, MergedRCs.size());979 EXPECT_NE(find(MergedRCs, &BRC), MergedRCs.end());980 EXPECT_NE(find(MergedRCs, &CRC), MergedRCs.end());981 EXPECT_NE(find(MergedRCs, &DRC), MergedRCs.end());982 983 // Make sure the nodes point to the right place now.984 EXPECT_EQ(&ARC, CG.lookupRefSCC(A));985 EXPECT_EQ(&ARC, CG.lookupRefSCC(B));986 EXPECT_EQ(&ARC, CG.lookupRefSCC(C));987 EXPECT_EQ(&ARC, CG.lookupRefSCC(D));988 989 // Check that the SCCs are in postorder.990 EXPECT_EQ(4, ARC.size());991 EXPECT_EQ(&DC, &ARC[0]);992 EXPECT_EQ(&CC, &ARC[1]);993 EXPECT_EQ(&BC, &ARC[2]);994 EXPECT_EQ(&AC, &ARC[3]);995 996 // And verify the post-order walk reflects the updated structure.997 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();998 ASSERT_NE(I, E);999 EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;1000 EXPECT_EQ(++I, E);1001}1002 1003TEST(LazyCallGraphTest, IncomingEdgeInsertionLargeRefCycle) {1004 LLVMContext Context;1005 std::unique_ptr<Module> M =1006 parseAssembly(Context, "define void @a() {\n"1007 "entry:\n"1008 " %p = alloca ptr\n"1009 " store ptr @b, ptr %p\n"1010 " ret void\n"1011 "}\n"1012 "define void @b() {\n"1013 "entry:\n"1014 " %p = alloca ptr\n"1015 " store ptr @c, ptr %p\n"1016 " ret void\n"1017 "}\n"1018 "define void @c() {\n"1019 "entry:\n"1020 " %p = alloca ptr\n"1021 " store ptr @d, ptr %p\n"1022 " ret void\n"1023 "}\n"1024 "define void @d() {\n"1025 "entry:\n"1026 " ret void\n"1027 "}\n");1028 LazyCallGraph CG = buildCG(*M);1029 1030 // Force the graph to be fully expanded.1031 CG.buildRefSCCs();1032 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())1033 dbgs() << "Formed RefSCC: " << RC << "\n";1034 1035 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));1036 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));1037 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));1038 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));1039 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A);1040 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B);1041 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C);1042 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D);1043 1044 // Connect the top to the bottom forming a large RefSCC made up just of1045 // references.1046 auto MergedRCs = ARC.insertIncomingRefEdge(D, A);1047 // Make sure we connected the nodes.1048 EXPECT_NE(D->begin(), D->end());1049 EXPECT_EQ(&A, &D->begin()->getNode());1050 1051 // Check that we have the dead RCs, but ignore the order.1052 EXPECT_EQ(3u, MergedRCs.size());1053 EXPECT_NE(find(MergedRCs, &BRC), MergedRCs.end());1054 EXPECT_NE(find(MergedRCs, &CRC), MergedRCs.end());1055 EXPECT_NE(find(MergedRCs, &DRC), MergedRCs.end());1056 1057 // Make sure the nodes point to the right place now.1058 EXPECT_EQ(&ARC, CG.lookupRefSCC(A));1059 EXPECT_EQ(&ARC, CG.lookupRefSCC(B));1060 EXPECT_EQ(&ARC, CG.lookupRefSCC(C));1061 EXPECT_EQ(&ARC, CG.lookupRefSCC(D));1062 1063 // And verify the post-order walk reflects the updated structure.1064 auto I = CG.postorder_ref_scc_begin(), End = CG.postorder_ref_scc_end();1065 ASSERT_NE(I, End);1066 EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;1067 EXPECT_EQ(++I, End);1068}1069 1070TEST(LazyCallGraphTest, InlineAndDeleteFunction) {1071 LLVMContext Context;1072 // We want to ensure we can delete nodes from relatively complex graphs and1073 // so use the diamond of triangles graph defined above.1074 //1075 // The ascii diagram is repeated here for easy reference.1076 //1077 // d1 |1078 // / \ |1079 // d3--d2 |1080 // / \ |1081 // b1 c1 |1082 // / \ / \ |1083 // b3--b2 c3--c2 |1084 // \ / |1085 // a1 |1086 // / \ |1087 // a3--a2 |1088 //1089 std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles);1090 LazyCallGraph CG = buildCG(*M);1091 1092 // Force the graph to be fully expanded.1093 CG.buildRefSCCs();1094 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())1095 dbgs() << "Formed RefSCC: " << RC << "\n";1096 1097 LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1"));1098 LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2"));1099 LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3"));1100 LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1"));1101 LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2"));1102 LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3"));1103 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1"));1104 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2"));1105 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3"));1106 LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1"));1107 LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2"));1108 LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3"));1109 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A1);1110 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B1);1111 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C1);1112 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D1);1113 ASSERT_EQ(&ARC, CG.lookupRefSCC(A2));1114 ASSERT_EQ(&ARC, CG.lookupRefSCC(A3));1115 ASSERT_EQ(&BRC, CG.lookupRefSCC(B2));1116 ASSERT_EQ(&BRC, CG.lookupRefSCC(B3));1117 ASSERT_EQ(&CRC, CG.lookupRefSCC(C2));1118 ASSERT_EQ(&CRC, CG.lookupRefSCC(C3));1119 ASSERT_EQ(&DRC, CG.lookupRefSCC(D2));1120 ASSERT_EQ(&DRC, CG.lookupRefSCC(D3));1121 ASSERT_EQ(1, std::distance(D2->begin(), D2->end()));1122 1123 // Delete d2 from the graph, as if it had been inlined.1124 //1125 // d1 |1126 // / / |1127 // d3--. |1128 // / \ |1129 // b1 c1 |1130 // / \ / \ |1131 // b3--b2 c3--c2 |1132 // \ / |1133 // a1 |1134 // / \ |1135 // a3--a2 |1136 1137 Function &D2F = D2.getFunction();1138 CallInst *C1Call = nullptr, *D1Call = nullptr;1139 for (User *U : D2F.users()) {1140 CallInst *CI = dyn_cast<CallInst>(U);1141 ASSERT_TRUE(CI) << "Expected a call: " << *U;1142 if (CI->getParent()->getParent() == &C1.getFunction()) {1143 ASSERT_EQ(nullptr, C1Call) << "Found too many C1 calls: " << *CI;1144 C1Call = CI;1145 } else if (CI->getParent()->getParent() == &D1.getFunction()) {1146 ASSERT_EQ(nullptr, D1Call) << "Found too many D1 calls: " << *CI;1147 D1Call = CI;1148 } else {1149 FAIL() << "Found an unexpected call instruction: " << *CI;1150 }1151 }1152 ASSERT_NE(C1Call, nullptr);1153 ASSERT_NE(D1Call, nullptr);1154 ASSERT_EQ(&D2F, C1Call->getCalledFunction());1155 ASSERT_EQ(&D2F, D1Call->getCalledFunction());1156 C1Call->setCalledFunction(&D3.getFunction());1157 D1Call->setCalledFunction(&D3.getFunction());1158 ASSERT_TRUE(D2F.use_empty());1159 1160 // Insert new edges first.1161 CRC.insertTrivialCallEdge(C1, D3);1162 DRC.insertTrivialCallEdge(D1, D3);1163 1164 // Then remove the old ones.1165 LazyCallGraph::SCC &DC = *CG.lookupSCC(D2);1166 auto NewCs = DRC.switchInternalEdgeToRef(D1, D2);1167 EXPECT_EQ(&DC, CG.lookupSCC(D2));1168 EXPECT_EQ(NewCs.end(), std::next(NewCs.begin()));1169 LazyCallGraph::SCC &NewDC = *NewCs.begin();1170 EXPECT_EQ(&NewDC, CG.lookupSCC(D1));1171 EXPECT_EQ(&NewDC, CG.lookupSCC(D3));1172 auto NewRCs = DRC.removeInternalRefEdges({{&D1, &D2}});1173 ASSERT_EQ(2u, NewRCs.size());1174 LazyCallGraph::RefSCC &NewDRC = *NewRCs[0];1175 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1));1176 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3));1177 LazyCallGraph::RefSCC &D2RC = *NewRCs[1];1178 EXPECT_EQ(&D2RC, CG.lookupRefSCC(D2));1179 EXPECT_FALSE(NewDRC.isParentOf(D2RC));1180 EXPECT_TRUE(CRC.isParentOf(D2RC));1181 EXPECT_TRUE(CRC.isParentOf(NewDRC));1182 EXPECT_TRUE(D2RC.isParentOf(NewDRC));1183 CRC.removeOutgoingEdge(C1, D2);1184 EXPECT_FALSE(CRC.isParentOf(D2RC));1185 EXPECT_TRUE(CRC.isParentOf(NewDRC));1186 EXPECT_TRUE(D2RC.isParentOf(NewDRC));1187 1188 // Now that we've updated the call graph, D2 is dead, so remove it.1189 CG.markDeadFunction(D2F);1190 CG.removeDeadFunctions({&D2F});1191 1192 // Check that the graph still looks the same.1193 EXPECT_EQ(&ARC, CG.lookupRefSCC(A1));1194 EXPECT_EQ(&ARC, CG.lookupRefSCC(A2));1195 EXPECT_EQ(&ARC, CG.lookupRefSCC(A3));1196 EXPECT_EQ(&BRC, CG.lookupRefSCC(B1));1197 EXPECT_EQ(&BRC, CG.lookupRefSCC(B2));1198 EXPECT_EQ(&BRC, CG.lookupRefSCC(B3));1199 EXPECT_EQ(&CRC, CG.lookupRefSCC(C1));1200 EXPECT_EQ(&CRC, CG.lookupRefSCC(C2));1201 EXPECT_EQ(&CRC, CG.lookupRefSCC(C3));1202 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1));1203 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3));1204 EXPECT_TRUE(CRC.isParentOf(NewDRC));1205 1206 // Verify the post-order walk hasn't changed.1207 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();1208 ASSERT_NE(I, E);1209 EXPECT_EQ(&NewDRC, &*I) << "Actual RefSCC: " << *I;1210 ASSERT_NE(++I, E);1211 EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I;1212 ASSERT_NE(++I, E);1213 EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I;1214 ASSERT_NE(++I, E);1215 EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;1216 EXPECT_EQ(++I, E);1217}1218 1219TEST(LazyCallGraphTest, InternalEdgeMutation) {1220 LLVMContext Context;1221 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"1222 "entry:\n"1223 " call void @b()\n"1224 " ret void\n"1225 "}\n"1226 "define void @b() {\n"1227 "entry:\n"1228 " call void @c()\n"1229 " ret void\n"1230 "}\n"1231 "define void @c() {\n"1232 "entry:\n"1233 " call void @a()\n"1234 " ret void\n"1235 "}\n");1236 LazyCallGraph CG = buildCG(*M);1237 1238 // Force the graph to be fully expanded.1239 CG.buildRefSCCs();1240 auto I = CG.postorder_ref_scc_begin();1241 LazyCallGraph::RefSCC &RC = *I++;1242 EXPECT_EQ(CG.postorder_ref_scc_end(), I);1243 1244 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));1245 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));1246 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));1247 EXPECT_EQ(&RC, CG.lookupRefSCC(A));1248 EXPECT_EQ(&RC, CG.lookupRefSCC(B));1249 EXPECT_EQ(&RC, CG.lookupRefSCC(C));1250 EXPECT_EQ(1, RC.size());1251 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(A));1252 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(B));1253 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(C));1254 1255 // Insert an edge from 'a' to 'c'. Nothing changes about the graph.1256 RC.insertInternalRefEdge(A, C);1257 EXPECT_EQ(2, std::distance(A->begin(), A->end()));1258 EXPECT_EQ(&RC, CG.lookupRefSCC(A));1259 EXPECT_EQ(&RC, CG.lookupRefSCC(B));1260 EXPECT_EQ(&RC, CG.lookupRefSCC(C));1261 EXPECT_EQ(1, RC.size());1262 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(A));1263 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(B));1264 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(C));1265 1266 // Switch the call edge from 'b' to 'c' to a ref edge. This will break the1267 // call cycle and cause us to form more SCCs. The RefSCC will remain the same1268 // though.1269 auto NewCs = RC.switchInternalEdgeToRef(B, C);1270 EXPECT_EQ(&RC, CG.lookupRefSCC(A));1271 EXPECT_EQ(&RC, CG.lookupRefSCC(B));1272 EXPECT_EQ(&RC, CG.lookupRefSCC(C));1273 auto J = RC.begin();1274 // The SCCs must be in *post-order* which means successors before1275 // predecessors. At this point we have call edges from C to A and from A to1276 // B. The only valid postorder is B, A, C.1277 EXPECT_EQ(&*J++, CG.lookupSCC(B));1278 EXPECT_EQ(&*J++, CG.lookupSCC(A));1279 EXPECT_EQ(&*J++, CG.lookupSCC(C));1280 EXPECT_EQ(RC.end(), J);1281 // And the returned range must be the slice of this sequence containing new1282 // SCCs.1283 EXPECT_EQ(RC.begin(), NewCs.begin());1284 EXPECT_EQ(std::prev(RC.end()), NewCs.end());1285 1286 // Test turning the ref edge from A to C into a call edge. This will form an1287 // SCC out of A and C. Since we previously had a call edge from C to A, the1288 // C SCC should be preserved and have A merged into it while the A SCC should1289 // be invalidated.1290 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);1291 LazyCallGraph::SCC &CC = *CG.lookupSCC(C);1292 EXPECT_TRUE(RC.switchInternalEdgeToCall(A, C, [&](ArrayRef<LazyCallGraph::SCC *> MergedCs) {1293 ASSERT_EQ(1u, MergedCs.size());1294 EXPECT_EQ(&AC, MergedCs[0]);1295 }));1296 EXPECT_EQ(2, CC.size());1297 EXPECT_EQ(&CC, CG.lookupSCC(A));1298 EXPECT_EQ(&CC, CG.lookupSCC(C));1299 J = RC.begin();1300 EXPECT_EQ(&*J++, CG.lookupSCC(B));1301 EXPECT_EQ(&*J++, CG.lookupSCC(C));1302 EXPECT_EQ(RC.end(), J);1303}1304 1305TEST(LazyCallGraphTest, InternalEdgeRemoval) {1306 LLVMContext Context;1307 // A nice fully connected (including self-edges) RefSCC.1308 std::unique_ptr<Module> M = parseAssembly(1309 Context, "define void @a(ptr %ptr) {\n"1310 "entry:\n"1311 " store ptr @a, ptr %ptr\n"1312 " store ptr @b, ptr %ptr\n"1313 " store ptr @c, ptr %ptr\n"1314 " ret void\n"1315 "}\n"1316 "define void @b(ptr %ptr) {\n"1317 "entry:\n"1318 " store ptr @a, ptr %ptr\n"1319 " store ptr @b, ptr %ptr\n"1320 " store ptr @c, ptr %ptr\n"1321 " ret void\n"1322 "}\n"1323 "define void @c(ptr %ptr) {\n"1324 "entry:\n"1325 " store ptr @a, ptr %ptr\n"1326 " store ptr @b, ptr %ptr\n"1327 " store ptr @c, ptr %ptr\n"1328 " ret void\n"1329 "}\n");1330 LazyCallGraph CG = buildCG(*M);1331 1332 // Force the graph to be fully expanded.1333 CG.buildRefSCCs();1334 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();1335 LazyCallGraph::RefSCC &RC = *I;1336 EXPECT_EQ(E, std::next(I));1337 1338 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));1339 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));1340 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));1341 EXPECT_EQ(&RC, CG.lookupRefSCC(A));1342 EXPECT_EQ(&RC, CG.lookupRefSCC(B));1343 EXPECT_EQ(&RC, CG.lookupRefSCC(C));1344 1345 // Remove the edge from b -> a, which should leave the 3 functions still in1346 // a single connected component because of a -> b -> c -> a.1347 SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs =1348 RC.removeInternalRefEdges({{&B, &A}});1349 EXPECT_EQ(0u, NewRCs.size());1350 EXPECT_EQ(&RC, CG.lookupRefSCC(A));1351 EXPECT_EQ(&RC, CG.lookupRefSCC(B));1352 EXPECT_EQ(&RC, CG.lookupRefSCC(C));1353 auto J = CG.postorder_ref_scc_begin();1354 EXPECT_EQ(I, J);1355 EXPECT_EQ(&RC, &*J);1356 EXPECT_EQ(E, std::next(J));1357 1358 // Increment I before we actually mutate the structure so that it remains1359 // a valid iterator.1360 ++I;1361 1362 // Remove the edge from c -> a, which should leave 'a' in the original RefSCC1363 // and form a new RefSCC for 'b' and 'c'.1364 NewRCs = RC.removeInternalRefEdges({{&C, &A}});1365 ASSERT_EQ(2u, NewRCs.size());1366 LazyCallGraph::RefSCC &BCRC = *NewRCs[0];1367 LazyCallGraph::RefSCC &ARC = *NewRCs[1];1368 EXPECT_EQ(&ARC, CG.lookupRefSCC(A));1369 EXPECT_EQ(1, std::distance(ARC.begin(), ARC.end()));1370 EXPECT_EQ(&BCRC, CG.lookupRefSCC(B));1371 EXPECT_EQ(&BCRC, CG.lookupRefSCC(C));1372 J = CG.postorder_ref_scc_begin();1373 EXPECT_NE(I, J);1374 EXPECT_EQ(&BCRC, &*J);1375 ++J;1376 EXPECT_NE(I, J);1377 EXPECT_EQ(&ARC, &*J);1378 ++J;1379 EXPECT_EQ(I, J);1380 EXPECT_EQ(E, J);1381}1382 1383TEST(LazyCallGraphTest, InternalMultiEdgeRemoval) {1384 LLVMContext Context;1385 // A nice fully connected (including self-edges) RefSCC.1386 std::unique_ptr<Module> M = parseAssembly(1387 Context, "define void @a(ptr %ptr) {\n"1388 "entry:\n"1389 " store ptr @a, ptr %ptr\n"1390 " store ptr @b, ptr %ptr\n"1391 " store ptr @c, ptr %ptr\n"1392 " ret void\n"1393 "}\n"1394 "define void @b(ptr %ptr) {\n"1395 "entry:\n"1396 " store ptr @a, ptr %ptr\n"1397 " store ptr @b, ptr %ptr\n"1398 " store ptr @c, ptr %ptr\n"1399 " ret void\n"1400 "}\n"1401 "define void @c(ptr %ptr) {\n"1402 "entry:\n"1403 " store ptr @a, ptr %ptr\n"1404 " store ptr @b, ptr %ptr\n"1405 " store ptr @c, ptr %ptr\n"1406 " ret void\n"1407 "}\n");1408 LazyCallGraph CG = buildCG(*M);1409 1410 // Force the graph to be fully expanded.1411 CG.buildRefSCCs();1412 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();1413 LazyCallGraph::RefSCC &RC = *I;1414 EXPECT_EQ(E, std::next(I));1415 1416 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));1417 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));1418 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));1419 EXPECT_EQ(&RC, CG.lookupRefSCC(A));1420 EXPECT_EQ(&RC, CG.lookupRefSCC(B));1421 EXPECT_EQ(&RC, CG.lookupRefSCC(C));1422 1423 // Increment I before we actually mutate the structure so that it remains1424 // a valid iterator.1425 ++I;1426 1427 // Remove the edges from b -> a and b -> c, leaving b in its own RefSCC.1428 SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs =1429 RC.removeInternalRefEdges({{&B, &A}, {&B, &C}});1430 1431 ASSERT_EQ(2u, NewRCs.size());1432 LazyCallGraph::RefSCC &BRC = *NewRCs[0];1433 LazyCallGraph::RefSCC &ACRC = *NewRCs[1];1434 EXPECT_EQ(&BRC, CG.lookupRefSCC(B));1435 EXPECT_EQ(1, std::distance(BRC.begin(), BRC.end()));1436 EXPECT_EQ(&ACRC, CG.lookupRefSCC(A));1437 EXPECT_EQ(&ACRC, CG.lookupRefSCC(C));1438 auto J = CG.postorder_ref_scc_begin();1439 EXPECT_NE(I, J);1440 EXPECT_EQ(&BRC, &*J);1441 ++J;1442 EXPECT_NE(I, J);1443 EXPECT_EQ(&ACRC, &*J);1444 ++J;1445 EXPECT_EQ(I, J);1446 EXPECT_EQ(E, J);1447}1448 1449TEST(LazyCallGraphTest, InternalNoOpEdgeRemoval) {1450 LLVMContext Context;1451 // A graph with a single cycle formed both from call and reference edges1452 // which makes the reference edges trivial to delete. The graph looks like:1453 //1454 // Reference edges: a -> b -> c -> a1455 // Call edges: a -> c -> b -> a1456 std::unique_ptr<Module> M = parseAssembly(1457 Context, "define void @a(ptr %ptr) {\n"1458 "entry:\n"1459 " call void @b(ptr %ptr)\n"1460 " store ptr @c, ptr %ptr\n"1461 " ret void\n"1462 "}\n"1463 "define void @b(ptr %ptr) {\n"1464 "entry:\n"1465 " store ptr @a, ptr %ptr\n"1466 " call void @c(ptr %ptr)\n"1467 " ret void\n"1468 "}\n"1469 "define void @c(ptr %ptr) {\n"1470 "entry:\n"1471 " call void @a(ptr %ptr)\n"1472 " store ptr @b, ptr %ptr\n"1473 " ret void\n"1474 "}\n");1475 LazyCallGraph CG = buildCG(*M);1476 1477 // Force the graph to be fully expanded.1478 CG.buildRefSCCs();1479 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();1480 LazyCallGraph::RefSCC &RC = *I;1481 EXPECT_EQ(E, std::next(I));1482 1483 LazyCallGraph::SCC &C = *RC.begin();1484 EXPECT_EQ(RC.end(), std::next(RC.begin()));1485 1486 LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a"));1487 LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b"));1488 LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c"));1489 EXPECT_EQ(&RC, CG.lookupRefSCC(AN));1490 EXPECT_EQ(&RC, CG.lookupRefSCC(BN));1491 EXPECT_EQ(&RC, CG.lookupRefSCC(CN));1492 EXPECT_EQ(&C, CG.lookupSCC(AN));1493 EXPECT_EQ(&C, CG.lookupSCC(BN));1494 EXPECT_EQ(&C, CG.lookupSCC(CN));1495 1496 // Remove the edge from a -> c which doesn't change anything.1497 SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs =1498 RC.removeInternalRefEdges({{&AN, &CN}});1499 EXPECT_EQ(0u, NewRCs.size());1500 EXPECT_EQ(&RC, CG.lookupRefSCC(AN));1501 EXPECT_EQ(&RC, CG.lookupRefSCC(BN));1502 EXPECT_EQ(&RC, CG.lookupRefSCC(CN));1503 EXPECT_EQ(&C, CG.lookupSCC(AN));1504 EXPECT_EQ(&C, CG.lookupSCC(BN));1505 EXPECT_EQ(&C, CG.lookupSCC(CN));1506 auto J = CG.postorder_ref_scc_begin();1507 EXPECT_EQ(I, J);1508 EXPECT_EQ(&RC, &*J);1509 EXPECT_EQ(E, std::next(J));1510 1511 // Remove the edge from b -> a and c -> b; again this doesn't change1512 // anything.1513 NewRCs = RC.removeInternalRefEdges({{&BN, &AN}});1514 NewRCs = RC.removeInternalRefEdges({{&CN, &BN}});1515 EXPECT_EQ(0u, NewRCs.size());1516 EXPECT_EQ(&RC, CG.lookupRefSCC(AN));1517 EXPECT_EQ(&RC, CG.lookupRefSCC(BN));1518 EXPECT_EQ(&RC, CG.lookupRefSCC(CN));1519 EXPECT_EQ(&C, CG.lookupSCC(AN));1520 EXPECT_EQ(&C, CG.lookupSCC(BN));1521 EXPECT_EQ(&C, CG.lookupSCC(CN));1522 J = CG.postorder_ref_scc_begin();1523 EXPECT_EQ(I, J);1524 EXPECT_EQ(&RC, &*J);1525 EXPECT_EQ(E, std::next(J));1526}1527 1528TEST(LazyCallGraphTest, InternalCallEdgeToRef) {1529 LLVMContext Context;1530 // A nice fully connected (including self-edges) SCC (and RefSCC)1531 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"1532 "entry:\n"1533 " call void @a()\n"1534 " call void @b()\n"1535 " call void @c()\n"1536 " ret void\n"1537 "}\n"1538 "define void @b() {\n"1539 "entry:\n"1540 " call void @a()\n"1541 " call void @b()\n"1542 " call void @c()\n"1543 " ret void\n"1544 "}\n"1545 "define void @c() {\n"1546 "entry:\n"1547 " call void @a()\n"1548 " call void @b()\n"1549 " call void @c()\n"1550 " ret void\n"1551 "}\n");1552 LazyCallGraph CG = buildCG(*M);1553 1554 // Force the graph to be fully expanded.1555 CG.buildRefSCCs();1556 auto I = CG.postorder_ref_scc_begin();1557 LazyCallGraph::RefSCC &RC = *I++;1558 EXPECT_EQ(CG.postorder_ref_scc_end(), I);1559 1560 EXPECT_EQ(1, RC.size());1561 LazyCallGraph::SCC &AC = *RC.begin();1562 1563 LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a"));1564 LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b"));1565 LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c"));1566 EXPECT_EQ(&AC, CG.lookupSCC(AN));1567 EXPECT_EQ(&AC, CG.lookupSCC(BN));1568 EXPECT_EQ(&AC, CG.lookupSCC(CN));1569 1570 // Remove the call edge from b -> a to a ref edge, which should leave the1571 // 3 functions still in a single connected component because of a -> b ->1572 // c -> a.1573 auto NewCs = RC.switchInternalEdgeToRef(BN, AN);1574 EXPECT_EQ(NewCs.begin(), NewCs.end());1575 EXPECT_EQ(1, RC.size());1576 EXPECT_EQ(&AC, CG.lookupSCC(AN));1577 EXPECT_EQ(&AC, CG.lookupSCC(BN));1578 EXPECT_EQ(&AC, CG.lookupSCC(CN));1579 1580 // Remove the edge from c -> a, which should leave 'a' in the original SCC1581 // and form a new SCC for 'b' and 'c'.1582 NewCs = RC.switchInternalEdgeToRef(CN, AN);1583 EXPECT_EQ(1, std::distance(NewCs.begin(), NewCs.end()));1584 EXPECT_EQ(2, RC.size());1585 EXPECT_EQ(&AC, CG.lookupSCC(AN));1586 LazyCallGraph::SCC &BC = *CG.lookupSCC(BN);1587 EXPECT_NE(&BC, &AC);1588 EXPECT_EQ(&BC, CG.lookupSCC(CN));1589 auto J = RC.find(AC);1590 EXPECT_EQ(&AC, &*J);1591 --J;1592 EXPECT_EQ(&BC, &*J);1593 EXPECT_EQ(RC.begin(), J);1594 EXPECT_EQ(J, NewCs.begin());1595 1596 // Remove the edge from c -> b, which should leave 'b' in the original SCC1597 // and form a new SCC for 'c'. It shouldn't change 'a's SCC.1598 NewCs = RC.switchInternalEdgeToRef(CN, BN);1599 EXPECT_EQ(1, std::distance(NewCs.begin(), NewCs.end()));1600 EXPECT_EQ(3, RC.size());1601 EXPECT_EQ(&AC, CG.lookupSCC(AN));1602 EXPECT_EQ(&BC, CG.lookupSCC(BN));1603 LazyCallGraph::SCC &CC = *CG.lookupSCC(CN);1604 EXPECT_NE(&CC, &AC);1605 EXPECT_NE(&CC, &BC);1606 J = RC.find(AC);1607 EXPECT_EQ(&AC, &*J);1608 --J;1609 EXPECT_EQ(&BC, &*J);1610 --J;1611 EXPECT_EQ(&CC, &*J);1612 EXPECT_EQ(RC.begin(), J);1613 EXPECT_EQ(J, NewCs.begin());1614}1615 1616TEST(LazyCallGraphTest, InternalRefEdgeToCall) {1617 LLVMContext Context;1618 // Basic tests for making a ref edge a call. This hits the basics of the1619 // process only.1620 std::unique_ptr<Module> M =1621 parseAssembly(Context, "define void @a() {\n"1622 "entry:\n"1623 " call void @b()\n"1624 " call void @c()\n"1625 " store ptr @d, ptr undef\n"1626 " ret void\n"1627 "}\n"1628 "define void @b() {\n"1629 "entry:\n"1630 " store ptr @c, ptr undef\n"1631 " call void @d()\n"1632 " ret void\n"1633 "}\n"1634 "define void @c() {\n"1635 "entry:\n"1636 " store ptr @b, ptr undef\n"1637 " call void @d()\n"1638 " ret void\n"1639 "}\n"1640 "define void @d() {\n"1641 "entry:\n"1642 " store ptr @a, ptr undef\n"1643 " ret void\n"1644 "}\n");1645 LazyCallGraph CG = buildCG(*M);1646 1647 // Force the graph to be fully expanded.1648 CG.buildRefSCCs();1649 auto I = CG.postorder_ref_scc_begin();1650 LazyCallGraph::RefSCC &RC = *I++;1651 EXPECT_EQ(CG.postorder_ref_scc_end(), I);1652 1653 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));1654 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));1655 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));1656 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));1657 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);1658 LazyCallGraph::SCC &BC = *CG.lookupSCC(B);1659 LazyCallGraph::SCC &CC = *CG.lookupSCC(C);1660 LazyCallGraph::SCC &DC = *CG.lookupSCC(D);1661 1662 // Check the initial post-order. Note that B and C could be flipped here (and1663 // in our mutation) without changing the nature of this test.1664 ASSERT_EQ(4, RC.size());1665 EXPECT_EQ(&DC, &RC[0]);1666 EXPECT_EQ(&BC, &RC[1]);1667 EXPECT_EQ(&CC, &RC[2]);1668 EXPECT_EQ(&AC, &RC[3]);1669 1670 // Switch the ref edge from A -> D to a call edge. This should have no1671 // effect as it is already in postorder and no new cycles are formed.1672 EXPECT_FALSE(RC.switchInternalEdgeToCall(A, D));1673 ASSERT_EQ(4, RC.size());1674 EXPECT_EQ(&DC, &RC[0]);1675 EXPECT_EQ(&BC, &RC[1]);1676 EXPECT_EQ(&CC, &RC[2]);1677 EXPECT_EQ(&AC, &RC[3]);1678 1679 // Switch B -> C to a call edge. This doesn't form any new cycles but does1680 // require reordering the SCCs.1681 EXPECT_FALSE(RC.switchInternalEdgeToCall(B, C));1682 ASSERT_EQ(4, RC.size());1683 EXPECT_EQ(&DC, &RC[0]);1684 EXPECT_EQ(&CC, &RC[1]);1685 EXPECT_EQ(&BC, &RC[2]);1686 EXPECT_EQ(&AC, &RC[3]);1687 1688 // Switch C -> B to a call edge. This forms a cycle and forces merging SCCs.1689 EXPECT_TRUE(RC.switchInternalEdgeToCall(C, B, [&](ArrayRef<LazyCallGraph::SCC *> MergedCs) {1690 ASSERT_EQ(1u, MergedCs.size());1691 EXPECT_EQ(&CC, MergedCs[0]);1692 }));1693 ASSERT_EQ(3, RC.size());1694 EXPECT_EQ(&DC, &RC[0]);1695 EXPECT_EQ(&BC, &RC[1]);1696 EXPECT_EQ(&AC, &RC[2]);1697 EXPECT_EQ(2, BC.size());1698 EXPECT_EQ(&BC, CG.lookupSCC(B));1699 EXPECT_EQ(&BC, CG.lookupSCC(C));1700}1701 1702TEST(LazyCallGraphTest, InternalRefEdgeToCallNoCycleInterleaved) {1703 LLVMContext Context;1704 // Test for having a post-order prior to changing a ref edge to a call edge1705 // with SCCs connecting to the source and connecting to the target, but not1706 // connecting to both, interleaved between the source and target. This1707 // ensures we correctly partition the range rather than simply moving one or1708 // the other.1709 std::unique_ptr<Module> M =1710 parseAssembly(Context, "define void @a() {\n"1711 "entry:\n"1712 " call void @b1()\n"1713 " call void @c1()\n"1714 " ret void\n"1715 "}\n"1716 "define void @b1() {\n"1717 "entry:\n"1718 " call void @c1()\n"1719 " call void @b2()\n"1720 " ret void\n"1721 "}\n"1722 "define void @c1() {\n"1723 "entry:\n"1724 " call void @b2()\n"1725 " call void @c2()\n"1726 " ret void\n"1727 "}\n"1728 "define void @b2() {\n"1729 "entry:\n"1730 " call void @c2()\n"1731 " call void @b3()\n"1732 " ret void\n"1733 "}\n"1734 "define void @c2() {\n"1735 "entry:\n"1736 " call void @b3()\n"1737 " call void @c3()\n"1738 " ret void\n"1739 "}\n"1740 "define void @b3() {\n"1741 "entry:\n"1742 " call void @c3()\n"1743 " call void @d()\n"1744 " ret void\n"1745 "}\n"1746 "define void @c3() {\n"1747 "entry:\n"1748 " store ptr @b1, ptr undef\n"1749 " call void @d()\n"1750 " ret void\n"1751 "}\n"1752 "define void @d() {\n"1753 "entry:\n"1754 " store ptr @a, ptr undef\n"1755 " ret void\n"1756 "}\n");1757 LazyCallGraph CG = buildCG(*M);1758 1759 // Force the graph to be fully expanded.1760 CG.buildRefSCCs();1761 auto I = CG.postorder_ref_scc_begin();1762 LazyCallGraph::RefSCC &RC = *I++;1763 EXPECT_EQ(CG.postorder_ref_scc_end(), I);1764 1765 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));1766 LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1"));1767 LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2"));1768 LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3"));1769 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1"));1770 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2"));1771 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3"));1772 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));1773 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);1774 LazyCallGraph::SCC &B1C = *CG.lookupSCC(B1);1775 LazyCallGraph::SCC &B2C = *CG.lookupSCC(B2);1776 LazyCallGraph::SCC &B3C = *CG.lookupSCC(B3);1777 LazyCallGraph::SCC &C1C = *CG.lookupSCC(C1);1778 LazyCallGraph::SCC &C2C = *CG.lookupSCC(C2);1779 LazyCallGraph::SCC &C3C = *CG.lookupSCC(C3);1780 LazyCallGraph::SCC &DC = *CG.lookupSCC(D);1781 1782 // Several call edges are initially present to force a particual post-order.1783 // Remove them now, leaving an interleaved post-order pattern.1784 RC.switchTrivialInternalEdgeToRef(B3, C3);1785 RC.switchTrivialInternalEdgeToRef(C2, B3);1786 RC.switchTrivialInternalEdgeToRef(B2, C2);1787 RC.switchTrivialInternalEdgeToRef(C1, B2);1788 RC.switchTrivialInternalEdgeToRef(B1, C1);1789 1790 // Check the initial post-order. We ensure this order with the extra edges1791 // that are nuked above.1792 ASSERT_EQ(8, RC.size());1793 EXPECT_EQ(&DC, &RC[0]);1794 EXPECT_EQ(&C3C, &RC[1]);1795 EXPECT_EQ(&B3C, &RC[2]);1796 EXPECT_EQ(&C2C, &RC[3]);1797 EXPECT_EQ(&B2C, &RC[4]);1798 EXPECT_EQ(&C1C, &RC[5]);1799 EXPECT_EQ(&B1C, &RC[6]);1800 EXPECT_EQ(&AC, &RC[7]);1801 1802 // Switch C3 -> B1 to a call edge. This doesn't form any new cycles but does1803 // require reordering the SCCs in the face of tricky internal node1804 // structures.1805 EXPECT_FALSE(RC.switchInternalEdgeToCall(C3, B1));1806 ASSERT_EQ(8, RC.size());1807 EXPECT_EQ(&DC, &RC[0]);1808 EXPECT_EQ(&B3C, &RC[1]);1809 EXPECT_EQ(&B2C, &RC[2]);1810 EXPECT_EQ(&B1C, &RC[3]);1811 EXPECT_EQ(&C3C, &RC[4]);1812 EXPECT_EQ(&C2C, &RC[5]);1813 EXPECT_EQ(&C1C, &RC[6]);1814 EXPECT_EQ(&AC, &RC[7]);1815}1816 1817TEST(LazyCallGraphTest, InternalRefEdgeToCallBothPartitionAndMerge) {1818 LLVMContext Context;1819 // Test for having a postorder where between the source and target are all1820 // three kinds of other SCCs:1821 // 1) One connected to the target only that have to be shifted below the1822 // source.1823 // 2) One connected to the source only that have to be shifted below the1824 // target.1825 // 3) One connected to both source and target that has to remain and get1826 // merged away.1827 //1828 // To achieve this we construct a heavily connected graph to force1829 // a particular post-order. Then we remove the forcing edges and connect1830 // a cycle.1831 //1832 // Diagram for the graph we want on the left and the graph we use to force1833 // the ordering on the right. Edges point down or right.1834 //1835 // A | A |1836 // / \ | / \ |1837 // B E | B \ |1838 // |\ | | |\ | |1839 // | D | | C-D-E |1840 // | \| | | \| |1841 // C F | \ F |1842 // \ / | \ / |1843 // G | G |1844 //1845 // And we form a cycle by connecting F to B.1846 std::unique_ptr<Module> M =1847 parseAssembly(Context, "define void @a() {\n"1848 "entry:\n"1849 " call void @b()\n"1850 " call void @e()\n"1851 " ret void\n"1852 "}\n"1853 "define void @b() {\n"1854 "entry:\n"1855 " call void @c()\n"1856 " call void @d()\n"1857 " ret void\n"1858 "}\n"1859 "define void @c() {\n"1860 "entry:\n"1861 " call void @d()\n"1862 " call void @g()\n"1863 " ret void\n"1864 "}\n"1865 "define void @d() {\n"1866 "entry:\n"1867 " call void @e()\n"1868 " call void @f()\n"1869 " ret void\n"1870 "}\n"1871 "define void @e() {\n"1872 "entry:\n"1873 " call void @f()\n"1874 " ret void\n"1875 "}\n"1876 "define void @f() {\n"1877 "entry:\n"1878 " store ptr @b, ptr undef\n"1879 " call void @g()\n"1880 " ret void\n"1881 "}\n"1882 "define void @g() {\n"1883 "entry:\n"1884 " store ptr @a, ptr undef\n"1885 " ret void\n"1886 "}\n");1887 LazyCallGraph CG = buildCG(*M);1888 1889 // Force the graph to be fully expanded.1890 CG.buildRefSCCs();1891 auto I = CG.postorder_ref_scc_begin();1892 LazyCallGraph::RefSCC &RC = *I++;1893 EXPECT_EQ(CG.postorder_ref_scc_end(), I);1894 1895 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));1896 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));1897 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));1898 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));1899 LazyCallGraph::Node &E = *CG.lookup(lookupFunction(*M, "e"));1900 LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f"));1901 LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g"));1902 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);1903 LazyCallGraph::SCC &BC = *CG.lookupSCC(B);1904 LazyCallGraph::SCC &CC = *CG.lookupSCC(C);1905 LazyCallGraph::SCC &DC = *CG.lookupSCC(D);1906 LazyCallGraph::SCC &EC = *CG.lookupSCC(E);1907 LazyCallGraph::SCC &FC = *CG.lookupSCC(F);1908 LazyCallGraph::SCC &GC = *CG.lookupSCC(G);1909 1910 // Remove the extra edges that were used to force a particular post-order.1911 RC.switchTrivialInternalEdgeToRef(C, D);1912 RC.switchTrivialInternalEdgeToRef(D, E);1913 1914 // Check the initial post-order. We ensure this order with the extra edges1915 // that are nuked above.1916 ASSERT_EQ(7, RC.size());1917 EXPECT_EQ(&GC, &RC[0]);1918 EXPECT_EQ(&FC, &RC[1]);1919 EXPECT_EQ(&EC, &RC[2]);1920 EXPECT_EQ(&DC, &RC[3]);1921 EXPECT_EQ(&CC, &RC[4]);1922 EXPECT_EQ(&BC, &RC[5]);1923 EXPECT_EQ(&AC, &RC[6]);1924 1925 // Switch F -> B to a call edge. This merges B, D, and F into a single SCC,1926 // and has to place the C and E SCCs on either side of it:1927 // A A |1928 // / \ / \ |1929 // B E | E |1930 // |\ | \ / |1931 // | D | -> B |1932 // | \| / \ |1933 // C F C | |1934 // \ / \ / |1935 // G G |1936 EXPECT_TRUE(RC.switchInternalEdgeToCall(1937 F, B, [&](ArrayRef<LazyCallGraph::SCC *> MergedCs) {1938 ASSERT_EQ(2u, MergedCs.size());1939 EXPECT_EQ(&FC, MergedCs[0]);1940 EXPECT_EQ(&DC, MergedCs[1]);1941 }));1942 EXPECT_EQ(3, BC.size());1943 1944 // And make sure the postorder was updated.1945 ASSERT_EQ(5, RC.size());1946 EXPECT_EQ(&GC, &RC[0]);1947 EXPECT_EQ(&CC, &RC[1]);1948 EXPECT_EQ(&BC, &RC[2]);1949 EXPECT_EQ(&EC, &RC[3]);1950 EXPECT_EQ(&AC, &RC[4]);1951}1952 1953// Test for IR containing constants using blockaddress constant expressions.1954// These are truly unique constructs: constant expressions with non-constant1955// operands.1956TEST(LazyCallGraphTest, HandleBlockAddress) {1957 LLVMContext Context;1958 std::unique_ptr<Module> M =1959 parseAssembly(Context, "define void @f() {\n"1960 "entry:\n"1961 " ret void\n"1962 "bb:\n"1963 " unreachable\n"1964 "}\n"1965 "define void @g(ptr %ptr) {\n"1966 "entry:\n"1967 " store ptr blockaddress(@f, %bb), ptr %ptr\n"1968 " ret void\n"1969 "}\n");1970 LazyCallGraph CG = buildCG(*M);1971 1972 CG.buildRefSCCs();1973 auto I = CG.postorder_ref_scc_begin();1974 LazyCallGraph::RefSCC &FRC = *I++;1975 LazyCallGraph::RefSCC &GRC = *I++;1976 EXPECT_EQ(CG.postorder_ref_scc_end(), I);1977 1978 LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f"));1979 LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g"));1980 EXPECT_EQ(&FRC, CG.lookupRefSCC(F));1981 EXPECT_EQ(&GRC, CG.lookupRefSCC(G));1982 EXPECT_FALSE(GRC.isParentOf(FRC));1983 EXPECT_FALSE(FRC.isParentOf(GRC));1984}1985 1986// Test that a blockaddress that refers to itself creates no new RefSCC1987// connections. https://bugs.llvm.org/show_bug.cgi?id=407221988TEST(LazyCallGraphTest, HandleBlockAddress2) {1989 LLVMContext Context;1990 std::unique_ptr<Module> M =1991 parseAssembly(Context, "define void @f() {\n"1992 " ret void\n"1993 "}\n"1994 "define void @g(ptr %ptr) {\n"1995 "bb:\n"1996 " store ptr blockaddress(@g, %bb), ptr %ptr\n"1997 " ret void\n"1998 "}\n");1999 LazyCallGraph CG = buildCG(*M);2000 2001 CG.buildRefSCCs();2002 auto I = CG.postorder_ref_scc_begin();2003 LazyCallGraph::RefSCC &FRC = *I++;2004 LazyCallGraph::RefSCC &GRC = *I++;2005 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2006 2007 LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f"));2008 LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g"));2009 EXPECT_EQ(&FRC, CG.lookupRefSCC(F));2010 EXPECT_EQ(&GRC, CG.lookupRefSCC(G));2011 EXPECT_FALSE(GRC.isParentOf(FRC));2012 EXPECT_FALSE(FRC.isParentOf(GRC));2013}2014 2015TEST(LazyCallGraphTest, ReplaceNodeFunction) {2016 LLVMContext Context;2017 // A graph with several different kinds of edges pointing at a particular2018 // function.2019 std::unique_ptr<Module> M =2020 parseAssembly(Context,2021 "define void @a(ptr %ptr) {\n"2022 "entry:\n"2023 " store ptr @d, ptr %ptr\n"2024 " ret void\n"2025 "}\n"2026 "define void @b(ptr %ptr) {\n"2027 "entry:\n"2028 " store ptr @d, ptr %ptr\n"2029 " store ptr @d, ptr %ptr\n"2030 " call void @d(ptr %ptr)"2031 " ret void\n"2032 "}\n"2033 "define void @c(ptr %ptr) {\n"2034 "entry:\n"2035 " call void @d(ptr %ptr)"2036 " call void @d(ptr %ptr)"2037 " store ptr @d, ptr %ptr\n"2038 " ret void\n"2039 "}\n"2040 "define void @d(ptr %ptr) {\n"2041 "entry:\n"2042 " store ptr @b, ptr %ptr\n"2043 " call void @c(ptr %ptr)"2044 " call void @d(ptr %ptr)"2045 " store ptr @d, ptr %ptr\n"2046 " ret void\n"2047 "}\n");2048 LazyCallGraph CG = buildCG(*M);2049 2050 // Force the graph to be fully expanded.2051 CG.buildRefSCCs();2052 auto I = CG.postorder_ref_scc_begin();2053 LazyCallGraph::RefSCC &RC1 = *I++;2054 LazyCallGraph::RefSCC &RC2 = *I++;2055 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2056 2057 ASSERT_EQ(2, RC1.size());2058 LazyCallGraph::SCC &C1 = RC1[0];2059 LazyCallGraph::SCC &C2 = RC1[1];2060 2061 LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a"));2062 LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b"));2063 LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c"));2064 LazyCallGraph::Node &DN = *CG.lookup(lookupFunction(*M, "d"));2065 EXPECT_EQ(&C1, CG.lookupSCC(DN));2066 EXPECT_EQ(&C1, CG.lookupSCC(CN));2067 EXPECT_EQ(&C2, CG.lookupSCC(BN));2068 EXPECT_EQ(&RC1, CG.lookupRefSCC(DN));2069 EXPECT_EQ(&RC1, CG.lookupRefSCC(CN));2070 EXPECT_EQ(&RC1, CG.lookupRefSCC(BN));2071 EXPECT_EQ(&RC2, CG.lookupRefSCC(AN));2072 2073 // Now we need to build a new function 'e' with the same signature as 'd'.2074 Function &D = DN.getFunction();2075 Function &E = *Function::Create(D.getFunctionType(), D.getLinkage(), "e");2076 D.getParent()->getFunctionList().insert(D.getIterator(), &E);2077 2078 // Change each use of 'd' to use 'e'. This is particularly easy as they have2079 // the same type.2080 D.replaceAllUsesWith(&E);2081 2082 // Splice the body of the old function into the new one.2083 E.splice(E.begin(), &D);2084 // And fix up the one argument.2085 D.arg_begin()->replaceAllUsesWith(&*E.arg_begin());2086 E.arg_begin()->takeName(&*D.arg_begin());2087 2088 // Now replace the function in the graph.2089 RC1.replaceNodeFunction(DN, E);2090 2091 EXPECT_EQ(&E, &DN.getFunction());2092 EXPECT_EQ(&DN, &(*CN)[DN].getNode());2093 EXPECT_EQ(&DN, &(*BN)[DN].getNode());2094}2095 2096TEST(LazyCallGraphTest, RemoveFunctionWithSpuriousRef) {2097 LLVMContext Context;2098 // A graph with a couple of RefSCCs.2099 std::unique_ptr<Module> M =2100 parseAssembly(Context,2101 "define void @a(ptr %ptr) {\n"2102 "entry:\n"2103 " store ptr @d, ptr %ptr\n"2104 " ret void\n"2105 "}\n"2106 "define void @b(ptr %ptr) {\n"2107 "entry:\n"2108 " store ptr @c, ptr %ptr\n"2109 " ret void\n"2110 "}\n"2111 "define void @c(ptr %ptr) {\n"2112 "entry:\n"2113 " call void @d(ptr %ptr)"2114 " ret void\n"2115 "}\n"2116 "define void @d(ptr %ptr) {\n"2117 "entry:\n"2118 " call void @c(ptr %ptr)"2119 " store ptr @b, ptr %ptr\n"2120 " ret void\n"2121 "}\n"2122 "define void @dead() {\n"2123 "entry:\n"2124 " ret void\n"2125 "}\n");2126 LazyCallGraph CG = buildCG(*M);2127 2128 // Insert spurious ref edges.2129 LazyCallGraph::Node &AN = CG.get(lookupFunction(*M, "a"));2130 LazyCallGraph::Node &BN = CG.get(lookupFunction(*M, "b"));2131 LazyCallGraph::Node &CN = CG.get(lookupFunction(*M, "c"));2132 LazyCallGraph::Node &DN = CG.get(lookupFunction(*M, "d"));2133 LazyCallGraph::Node &DeadN = CG.get(lookupFunction(*M, "dead"));2134 AN.populate();2135 BN.populate();2136 CN.populate();2137 DN.populate();2138 DeadN.populate();2139 CG.insertEdge(AN, DeadN, LazyCallGraph::Edge::Ref);2140 CG.insertEdge(BN, DeadN, LazyCallGraph::Edge::Ref);2141 CG.insertEdge(CN, DeadN, LazyCallGraph::Edge::Ref);2142 CG.insertEdge(DN, DeadN, LazyCallGraph::Edge::Ref);2143 2144 // Force the graph to be fully expanded.2145 CG.buildRefSCCs();2146 auto I = CG.postorder_ref_scc_begin();2147 LazyCallGraph::RefSCC &DeadRC = *I++;2148 LazyCallGraph::RefSCC &RC1 = *I++;2149 LazyCallGraph::RefSCC &RC2 = *I++;2150 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2151 2152 ASSERT_EQ(2, RC1.size());2153 LazyCallGraph::SCC &C1 = RC1[0];2154 LazyCallGraph::SCC &C2 = RC1[1];2155 2156 EXPECT_EQ(&DeadRC, CG.lookupRefSCC(DeadN));2157 EXPECT_EQ(&C1, CG.lookupSCC(DN));2158 EXPECT_EQ(&C1, CG.lookupSCC(CN));2159 EXPECT_EQ(&C2, CG.lookupSCC(BN));2160 EXPECT_EQ(&RC1, CG.lookupRefSCC(DN));2161 EXPECT_EQ(&RC1, CG.lookupRefSCC(CN));2162 EXPECT_EQ(&RC1, CG.lookupRefSCC(BN));2163 EXPECT_EQ(&RC2, CG.lookupRefSCC(AN));2164 2165 // Now delete 'dead'. There are no uses of this function but there are2166 // spurious references.2167 CG.markDeadFunction(DeadN.getFunction());2168 CG.removeDeadFunctions({&DeadN.getFunction()});2169 2170 // The only observable change should be that the RefSCC is gone from the2171 // postorder sequence.2172 I = CG.postorder_ref_scc_begin();2173 EXPECT_EQ(&RC1, &*I++);2174 EXPECT_EQ(&RC2, &*I++);2175 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2176}2177 2178TEST(LazyCallGraphTest, RemoveFunctionWithSpuriousRefRecursive) {2179 LLVMContext Context;2180 std::unique_ptr<Module> M =2181 parseAssembly(Context, "define void @a(ptr %p) {\n"2182 " store ptr @b, ptr %p\n"2183 " ret void\n"2184 "}\n"2185 "define void @b(ptr %p) {\n"2186 " store ptr @c, ptr %p\n"2187 " ret void\n"2188 "}\n"2189 "define void @c(ptr %p) {\n"2190 " ret void\n"2191 "}\n");2192 LazyCallGraph CG = buildCG(*M);2193 2194 LazyCallGraph::Node &AN = CG.get(lookupFunction(*M, "a"));2195 LazyCallGraph::Node &BN = CG.get(lookupFunction(*M, "b"));2196 LazyCallGraph::Node &CN = CG.get(lookupFunction(*M, "c"));2197 AN.populate();2198 BN.populate();2199 CN.populate();2200 // Insert spurious ref edge.2201 CG.insertEdge(CN, AN, LazyCallGraph::Edge::Ref);2202 2203 // Force the graph to be fully expanded.2204 CG.buildRefSCCs();2205 auto I = CG.postorder_ref_scc_begin();2206 LazyCallGraph::RefSCC &RC = *I++;2207 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2208 2209 ASSERT_EQ(RC.size(), 3);2210 2211 EXPECT_EQ(&RC, CG.lookupRefSCC(AN));2212 EXPECT_EQ(&RC, CG.lookupRefSCC(BN));2213 EXPECT_EQ(&RC, CG.lookupRefSCC(CN));2214 2215 // Now delete 'a'. There are no uses of this function but there are2216 // spurious references.2217 CG.markDeadFunction(AN.getFunction());2218 CG.removeDeadFunctions({&AN.getFunction()});2219 2220 // The only observable change should be that the RefSCC is gone from the2221 // postorder sequence.2222 I = CG.postorder_ref_scc_begin();2223 EXPECT_EQ(CG.lookupRefSCC(CN), &*I++);2224 EXPECT_EQ(CG.lookupRefSCC(BN), &*I++);2225 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2226}2227 2228TEST(LazyCallGraphTest, RemoveFunctionWithSpuriousRefRecursive2) {2229 LLVMContext Context;2230 std::unique_ptr<Module> M =2231 parseAssembly(Context, "define void @a(ptr %p) {\n"2232 " store ptr @b, ptr %p\n"2233 " ret void\n"2234 "}\n"2235 "define void @b(ptr %p) {\n"2236 " store ptr @c, ptr %p\n"2237 " ret void\n"2238 "}\n"2239 "define void @c(ptr %p) {\n"2240 " store ptr @b, ptr %p\n"2241 " store ptr @d, ptr %p\n"2242 " ret void\n"2243 "}\n"2244 "define void @d(ptr %p) {\n"2245 " ret void\n"2246 "}\n");2247 LazyCallGraph CG = buildCG(*M);2248 2249 LazyCallGraph::Node &AN = CG.get(lookupFunction(*M, "a"));2250 LazyCallGraph::Node &BN = CG.get(lookupFunction(*M, "b"));2251 LazyCallGraph::Node &CN = CG.get(lookupFunction(*M, "c"));2252 LazyCallGraph::Node &DN = CG.get(lookupFunction(*M, "d"));2253 AN.populate();2254 BN.populate();2255 CN.populate();2256 DN.populate();2257 // Insert spurious ref edge.2258 CG.insertEdge(DN, AN, LazyCallGraph::Edge::Ref);2259 2260 // Force the graph to be fully expanded.2261 CG.buildRefSCCs();2262 auto I = CG.postorder_ref_scc_begin();2263 LazyCallGraph::RefSCC &RC = *I++;2264 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2265 2266 ASSERT_EQ(4, RC.size());2267 2268 EXPECT_EQ(&RC, CG.lookupRefSCC(AN));2269 EXPECT_EQ(&RC, CG.lookupRefSCC(BN));2270 EXPECT_EQ(&RC, CG.lookupRefSCC(CN));2271 EXPECT_EQ(&RC, CG.lookupRefSCC(DN));2272 2273 // Now delete 'a'. There are no uses of this function but there are2274 // spurious references.2275 CG.markDeadFunction(AN.getFunction());2276 CG.removeDeadFunctions({&AN.getFunction()});2277 2278 // The only observable change should be that the RefSCC is gone from the2279 // postorder sequence.2280 I = CG.postorder_ref_scc_begin();2281 EXPECT_EQ(CG.lookupRefSCC(DN), &*I++);2282 EXPECT_EQ(CG.lookupRefSCC(CN), &*I);2283 EXPECT_EQ(CG.lookupRefSCC(BN), &*I++);2284 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2285}2286 2287TEST(LazyCallGraphTest, RemoveFunctionWithSpuriousRefRecursive3) {2288 LLVMContext Context;2289 std::unique_ptr<Module> M =2290 parseAssembly(Context, "define void @a(ptr %p) {\n"2291 " store ptr @b, ptr %p\n"2292 " ret void\n"2293 "}\n"2294 "define void @b(ptr %p) {\n"2295 " store ptr @c, ptr %p\n"2296 " ret void\n"2297 "}\n"2298 "define void @c(ptr %p) {\n"2299 " ret void\n"2300 "}\n");2301 LazyCallGraph CG = buildCG(*M);2302 2303 LazyCallGraph::Node &AN = CG.get(lookupFunction(*M, "a"));2304 LazyCallGraph::Node &BN = CG.get(lookupFunction(*M, "b"));2305 LazyCallGraph::Node &CN = CG.get(lookupFunction(*M, "c"));2306 AN.populate();2307 BN.populate();2308 CN.populate();2309 // Insert spurious ref edges.2310 CG.insertEdge(CN, AN, LazyCallGraph::Edge::Ref);2311 CG.insertEdge(BN, AN, LazyCallGraph::Edge::Ref);2312 2313 // Force the graph to be fully expanded.2314 CG.buildRefSCCs();2315 auto I = CG.postorder_ref_scc_begin();2316 LazyCallGraph::RefSCC &RC = *I++;2317 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2318 2319 ASSERT_EQ(RC.size(), 3);2320 2321 EXPECT_EQ(&RC, CG.lookupRefSCC(AN));2322 EXPECT_EQ(&RC, CG.lookupRefSCC(BN));2323 EXPECT_EQ(&RC, CG.lookupRefSCC(CN));2324 2325 // Now delete 'a'. There are no uses of this function but there are2326 // spurious references.2327 CG.markDeadFunction(AN.getFunction());2328 CG.removeDeadFunctions({&AN.getFunction()});2329 2330 // The only observable change should be that the RefSCC is gone from the2331 // postorder sequence.2332 I = CG.postorder_ref_scc_begin();2333 EXPECT_EQ(CG.lookupRefSCC(CN), &*I++);2334 EXPECT_EQ(CG.lookupRefSCC(BN), &*I++);2335 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2336}2337 2338TEST(LazyCallGraphTest, AddSplitFunction1) {2339 LLVMContext Context;2340 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"2341 " ret void\n"2342 "}\n");2343 LazyCallGraph CG = buildCG(*M);2344 2345 Function &F = lookupFunction(*M, "f");2346 LazyCallGraph::Node &FN = CG.get(F);2347 2348 // Force the graph to be fully expanded.2349 CG.buildRefSCCs();2350 auto I = CG.postorder_ref_scc_begin();2351 LazyCallGraph::RefSCC *ORC = &*I++;2352 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2353 2354 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),2355 F.getAddressSpace(), "g", F.getParent());2356 BasicBlock *GBB = BasicBlock::Create(Context, "", G);2357 (void)ReturnInst::Create(Context, GBB);2358 2359 // Create f -call-> g.2360 (void)CallInst::Create(G, {}, "", F.getEntryBlock().begin());2361 2362 EXPECT_FALSE(verifyModule(*M, &errs()));2363 2364 CG.addSplitFunction(F, *G);2365 2366 LazyCallGraph::Node *GN = CG.lookup(*G);2367 EXPECT_TRUE(GN);2368 2369 I = CG.postorder_ref_scc_begin();2370 LazyCallGraph::RefSCC *RC1 = &*I++;2371 EXPECT_EQ(RC1, CG.lookupRefSCC(*GN));2372 LazyCallGraph::RefSCC *RC2 = &*I++;2373 EXPECT_EQ(RC2, ORC);2374 EXPECT_EQ(RC2, CG.lookupRefSCC(FN));2375 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2376}2377 2378TEST(LazyCallGraphTest, AddSplitFunction2) {2379 LLVMContext Context;2380 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"2381 " ret void\n"2382 "}\n");2383 LazyCallGraph CG = buildCG(*M);2384 2385 Function &F = lookupFunction(*M, "f");2386 LazyCallGraph::Node &FN = CG.get(F);2387 2388 // Force the graph to be fully expanded.2389 CG.buildRefSCCs();2390 auto I = CG.postorder_ref_scc_begin();2391 LazyCallGraph::RefSCC *ORC = &*I++;2392 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2393 2394 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),2395 F.getAddressSpace(), "g", F.getParent());2396 BasicBlock *GBB = BasicBlock::Create(Context, "", G);2397 (void)ReturnInst::Create(Context, GBB);2398 2399 // Create f -ref-> g.2400 (void)CastInst::CreatePointerCast(G, PointerType::getUnqual(Context), "",2401 F.getEntryBlock().begin());2402 2403 EXPECT_FALSE(verifyModule(*M, &errs()));2404 2405 CG.addSplitFunction(F, *G);2406 2407 LazyCallGraph::Node *GN = CG.lookup(*G);2408 EXPECT_TRUE(GN);2409 2410 I = CG.postorder_ref_scc_begin();2411 LazyCallGraph::RefSCC *RC1 = &*I++;2412 EXPECT_EQ(RC1, CG.lookupRefSCC(*GN));2413 LazyCallGraph::RefSCC *RC2 = &*I++;2414 EXPECT_EQ(RC2, ORC);2415 EXPECT_EQ(RC2, CG.lookupRefSCC(FN));2416 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2417}2418 2419TEST(LazyCallGraphTest, AddSplitFunction3) {2420 LLVMContext Context;2421 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"2422 " ret void\n"2423 "}\n");2424 LazyCallGraph CG = buildCG(*M);2425 2426 Function &F = lookupFunction(*M, "f");2427 LazyCallGraph::Node &FN = CG.get(F);2428 2429 // Force the graph to be fully expanded.2430 CG.buildRefSCCs();2431 auto I = CG.postorder_ref_scc_begin();2432 LazyCallGraph::RefSCC *ORC = &*I++;2433 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2434 2435 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),2436 F.getAddressSpace(), "g", F.getParent());2437 BasicBlock *GBB = BasicBlock::Create(Context, "", G);2438 // Create g -ref-> f.2439 (void)CastInst::CreatePointerCast(&F, PointerType::getUnqual(Context), "",2440 GBB);2441 (void)ReturnInst::Create(Context, GBB);2442 2443 // Create f -call-> g.2444 (void)CallInst::Create(G, {}, "", F.getEntryBlock().begin());2445 2446 EXPECT_FALSE(verifyModule(*M, &errs()));2447 2448 CG.addSplitFunction(F, *G);2449 2450 LazyCallGraph::Node *GN = CG.lookup(*G);2451 EXPECT_TRUE(GN);2452 2453 I = CG.postorder_ref_scc_begin();2454 LazyCallGraph::RefSCC *RC = &*I++;2455 EXPECT_EQ(RC, CG.lookupRefSCC(*GN));2456 EXPECT_EQ(RC, ORC);2457 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2458 2459 EXPECT_EQ(2, RC->size());2460 EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[0]);2461 EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[1]);2462}2463 2464TEST(LazyCallGraphTest, AddSplitFunction4) {2465 LLVMContext Context;2466 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"2467 " ret void\n"2468 "}\n");2469 LazyCallGraph CG = buildCG(*M);2470 2471 Function &F = lookupFunction(*M, "f");2472 LazyCallGraph::Node &FN = CG.get(F);2473 2474 // Force the graph to be fully expanded.2475 CG.buildRefSCCs();2476 auto I = CG.postorder_ref_scc_begin();2477 LazyCallGraph::RefSCC *ORC = &*I++;2478 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2479 2480 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),2481 F.getAddressSpace(), "g", F.getParent());2482 BasicBlock *GBB = BasicBlock::Create(Context, "", G);2483 // Create g -ref-> f.2484 (void)CastInst::CreatePointerCast(&F, PointerType::getUnqual(Context), "",2485 GBB);2486 (void)ReturnInst::Create(Context, GBB);2487 2488 // Create f -ref-> g.2489 (void)CastInst::CreatePointerCast(G, PointerType::getUnqual(Context), "",2490 F.getEntryBlock().begin());2491 2492 EXPECT_FALSE(verifyModule(*M, &errs()));2493 2494 CG.addSplitFunction(F, *G);2495 2496 LazyCallGraph::Node *GN = CG.lookup(*G);2497 EXPECT_TRUE(GN);2498 2499 I = CG.postorder_ref_scc_begin();2500 LazyCallGraph::RefSCC *RC = &*I++;2501 EXPECT_EQ(RC, CG.lookupRefSCC(*GN));2502 EXPECT_EQ(RC, ORC);2503 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2504 2505 // Order doesn't matter for sibling SCCs.2506 EXPECT_EQ(2, RC->size());2507 EXPECT_EQ(&CG.lookupSCC(*GN)->getOuterRefSCC(), RC);2508 EXPECT_EQ(&CG.lookupSCC(FN)->getOuterRefSCC(), RC);2509}2510 2511TEST(LazyCallGraphTest, AddSplitFunction5) {2512 LLVMContext Context;2513 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"2514 " ret void\n"2515 "}\n");2516 LazyCallGraph CG = buildCG(*M);2517 2518 Function &F = lookupFunction(*M, "f");2519 LazyCallGraph::Node &FN = CG.get(F);2520 2521 // Force the graph to be fully expanded.2522 CG.buildRefSCCs();2523 auto I = CG.postorder_ref_scc_begin();2524 LazyCallGraph::RefSCC *ORC = &*I++;2525 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2526 2527 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),2528 F.getAddressSpace(), "g", F.getParent());2529 BasicBlock *GBB = BasicBlock::Create(Context, "", G);2530 // Create g -call-> f.2531 (void)CallInst::Create(&F, {}, "", GBB);2532 (void)ReturnInst::Create(Context, GBB);2533 2534 // Create f -ref-> g.2535 (void)CastInst::CreatePointerCast(G, PointerType::getUnqual(Context), "",2536 F.getEntryBlock().begin());2537 2538 EXPECT_FALSE(verifyModule(*M, &errs()));2539 2540 CG.addSplitFunction(F, *G);2541 2542 LazyCallGraph::Node *GN = CG.lookup(*G);2543 EXPECT_TRUE(GN);2544 2545 I = CG.postorder_ref_scc_begin();2546 LazyCallGraph::RefSCC *RC = &*I++;2547 EXPECT_EQ(RC, CG.lookupRefSCC(*GN));2548 EXPECT_EQ(RC, ORC);2549 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2550 2551 EXPECT_EQ(2, RC->size());2552 EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[0]);2553 EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[1]);2554}2555 2556TEST(LazyCallGraphTest, AddSplitFunction6) {2557 LLVMContext Context;2558 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"2559 " ret void\n"2560 "}\n");2561 LazyCallGraph CG = buildCG(*M);2562 2563 Function &F = lookupFunction(*M, "f");2564 LazyCallGraph::Node &FN = CG.get(F);2565 2566 // Force the graph to be fully expanded.2567 CG.buildRefSCCs();2568 auto I = CG.postorder_ref_scc_begin();2569 LazyCallGraph::RefSCC *ORC = &*I++;2570 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2571 2572 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),2573 F.getAddressSpace(), "g", F.getParent());2574 BasicBlock *GBB = BasicBlock::Create(Context, "", G);2575 // Create g -call-> f.2576 (void)CallInst::Create(&F, {}, "", GBB);2577 (void)ReturnInst::Create(Context, GBB);2578 2579 // Create f -call-> g.2580 (void)CallInst::Create(G, {}, "", F.getEntryBlock().begin());2581 2582 EXPECT_FALSE(verifyModule(*M, &errs()));2583 2584 CG.addSplitFunction(F, *G);2585 2586 LazyCallGraph::Node *GN = CG.lookup(*G);2587 EXPECT_TRUE(GN);2588 2589 I = CG.postorder_ref_scc_begin();2590 LazyCallGraph::RefSCC *RC = &*I++;2591 EXPECT_EQ(RC, CG.lookupRefSCC(*GN));2592 EXPECT_EQ(RC, ORC);2593 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2594 2595 EXPECT_EQ(1, RC->size());2596 EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[0]);2597 EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[0]);2598}2599 2600TEST(LazyCallGraphTest, AddSplitFunction7) {2601 LLVMContext Context;2602 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"2603 " call void @f2()\n"2604 " ret void\n"2605 "}\n"2606 "define void @f2() {\n"2607 " call void @f()\n"2608 " ret void\n"2609 "}\n");2610 LazyCallGraph CG = buildCG(*M);2611 2612 Function &F = lookupFunction(*M, "f");2613 LazyCallGraph::Node &FN = CG.get(F);2614 Function &F2 = lookupFunction(*M, "f2");2615 LazyCallGraph::Node &F2N = CG.get(F2);2616 2617 // Force the graph to be fully expanded.2618 CG.buildRefSCCs();2619 auto I = CG.postorder_ref_scc_begin();2620 LazyCallGraph::RefSCC *ORC = &*I++;2621 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2622 2623 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),2624 F.getAddressSpace(), "g", F.getParent());2625 BasicBlock *GBB = BasicBlock::Create(Context, "", G);2626 // Create g -call-> f2.2627 (void)CallInst::Create(&F2, {}, "", GBB);2628 (void)ReturnInst::Create(Context, GBB);2629 2630 // Create f -call-> g.2631 (void)CallInst::Create(G, {}, "", F.getEntryBlock().begin());2632 2633 EXPECT_FALSE(verifyModule(*M, &errs()));2634 2635 CG.addSplitFunction(F, *G);2636 2637 LazyCallGraph::Node *GN = CG.lookup(*G);2638 EXPECT_TRUE(GN);2639 2640 I = CG.postorder_ref_scc_begin();2641 LazyCallGraph::RefSCC *RC = &*I++;2642 EXPECT_EQ(RC, CG.lookupRefSCC(*GN));2643 EXPECT_EQ(RC, ORC);2644 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2645 2646 EXPECT_EQ(1, RC->size());2647 EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[0]);2648 EXPECT_EQ(CG.lookupSCC(F2N), &(*RC)[0]);2649 EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[0]);2650}2651 2652TEST(LazyCallGraphTest, AddSplitFunction8) {2653 LLVMContext Context;2654 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"2655 " call void @f2()\n"2656 " ret void\n"2657 "}\n"2658 "define void @f2() {\n"2659 " call void @f()\n"2660 " ret void\n"2661 "}\n");2662 LazyCallGraph CG = buildCG(*M);2663 2664 Function &F = lookupFunction(*M, "f");2665 LazyCallGraph::Node &FN = CG.get(F);2666 Function &F2 = lookupFunction(*M, "f2");2667 LazyCallGraph::Node &F2N = CG.get(F2);2668 2669 // Force the graph to be fully expanded.2670 CG.buildRefSCCs();2671 auto I = CG.postorder_ref_scc_begin();2672 LazyCallGraph::RefSCC *ORC = &*I++;2673 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2674 2675 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),2676 F.getAddressSpace(), "g", F.getParent());2677 BasicBlock *GBB = BasicBlock::Create(Context, "", G);2678 // Create g -call-> f2.2679 (void)CallInst::Create(&F2, {}, "", GBB);2680 (void)ReturnInst::Create(Context, GBB);2681 2682 // Create f -ref-> g.2683 (void)CastInst::CreatePointerCast(G, PointerType::getUnqual(Context), "",2684 F.getEntryBlock().begin());2685 2686 EXPECT_FALSE(verifyModule(*M, &errs()));2687 2688 CG.addSplitFunction(F, *G);2689 2690 LazyCallGraph::Node *GN = CG.lookup(*G);2691 EXPECT_TRUE(GN);2692 2693 I = CG.postorder_ref_scc_begin();2694 LazyCallGraph::RefSCC *RC = &*I++;2695 EXPECT_EQ(RC, CG.lookupRefSCC(*GN));2696 EXPECT_EQ(RC, ORC);2697 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2698 2699 EXPECT_EQ(2, RC->size());2700 EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[0]);2701 EXPECT_EQ(CG.lookupSCC(F2N), &(*RC)[0]);2702 EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[1]);2703}2704 2705TEST(LazyCallGraphTest, AddSplitFunction9) {2706 LLVMContext Context;2707 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"2708 " call void @f2()\n"2709 " ret void\n"2710 "}\n"2711 "define void @f2() {\n"2712 " call void @f()\n"2713 " ret void\n"2714 "}\n");2715 LazyCallGraph CG = buildCG(*M);2716 2717 Function &F = lookupFunction(*M, "f");2718 LazyCallGraph::Node &FN = CG.get(F);2719 Function &F2 = lookupFunction(*M, "f2");2720 LazyCallGraph::Node &F2N = CG.get(F2);2721 2722 // Force the graph to be fully expanded.2723 CG.buildRefSCCs();2724 auto I = CG.postorder_ref_scc_begin();2725 LazyCallGraph::RefSCC *ORC = &*I++;2726 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2727 2728 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),2729 F.getAddressSpace(), "g", F.getParent());2730 BasicBlock *GBB = BasicBlock::Create(Context, "", G);2731 // Create g -ref-> f2.2732 (void)CastInst::CreatePointerCast(&F2, PointerType::getUnqual(Context), "",2733 GBB);2734 (void)ReturnInst::Create(Context, GBB);2735 2736 // Create f -call-> g.2737 (void)CallInst::Create(G, {}, "", F.getEntryBlock().begin());2738 2739 EXPECT_FALSE(verifyModule(*M, &errs()));2740 2741 CG.addSplitFunction(F, *G);2742 2743 LazyCallGraph::Node *GN = CG.lookup(*G);2744 EXPECT_TRUE(GN);2745 2746 I = CG.postorder_ref_scc_begin();2747 LazyCallGraph::RefSCC *RC = &*I++;2748 EXPECT_EQ(RC, CG.lookupRefSCC(*GN));2749 EXPECT_EQ(RC, ORC);2750 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2751 2752 EXPECT_EQ(2, RC->size());2753 EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[0]);2754 EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[1]);2755 EXPECT_EQ(CG.lookupSCC(F2N), &(*RC)[1]);2756}2757 2758TEST(LazyCallGraphTest, AddSplitFunctions1) {2759 LLVMContext Context;2760 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"2761 " ret void\n"2762 "}\n");2763 LazyCallGraph CG = buildCG(*M);2764 2765 Function &F = lookupFunction(*M, "f");2766 LazyCallGraph::Node &FN = CG.get(F);2767 2768 // Force the graph to be fully expanded.2769 CG.buildRefSCCs();2770 auto I = CG.postorder_ref_scc_begin();2771 LazyCallGraph::RefSCC *ORC = &*I++;2772 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2773 2774 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),2775 F.getAddressSpace(), "g", F.getParent());2776 BasicBlock *GBB = BasicBlock::Create(Context, "", G);2777 (void)ReturnInst::Create(Context, GBB);2778 2779 // Create f -ref-> g.2780 (void)CastInst::CreatePointerCast(G, PointerType::getUnqual(Context), "",2781 F.getEntryBlock().begin());2782 2783 EXPECT_FALSE(verifyModule(*M, &errs()));2784 2785 CG.addSplitRefRecursiveFunctions(F, SmallVector<Function *, 1>({G}));2786 2787 LazyCallGraph::Node *GN = CG.lookup(*G);2788 EXPECT_TRUE(GN);2789 2790 I = CG.postorder_ref_scc_begin();2791 LazyCallGraph::RefSCC *RC1 = &*I++;2792 EXPECT_EQ(RC1, CG.lookupRefSCC(*GN));2793 LazyCallGraph::RefSCC *RC2 = &*I++;2794 EXPECT_EQ(RC2, ORC);2795 EXPECT_EQ(RC2, CG.lookupRefSCC(FN));2796 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2797}2798 2799TEST(LazyCallGraphTest, AddSplitFunctions2) {2800 LLVMContext Context;2801 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"2802 " ret void\n"2803 "}\n");2804 LazyCallGraph CG = buildCG(*M);2805 2806 Function &F = lookupFunction(*M, "f");2807 LazyCallGraph::Node &FN = CG.get(F);2808 2809 // Force the graph to be fully expanded.2810 CG.buildRefSCCs();2811 auto I = CG.postorder_ref_scc_begin();2812 LazyCallGraph::RefSCC *ORC = &*I++;2813 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2814 2815 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),2816 F.getAddressSpace(), "g", F.getParent());2817 BasicBlock *GBB = BasicBlock::Create(Context, "", G);2818 // Create g -ref-> f.2819 (void)CastInst::CreatePointerCast(&F, PointerType::getUnqual(Context), "",2820 GBB);2821 (void)ReturnInst::Create(Context, GBB);2822 2823 // Create f -ref-> g.2824 (void)CastInst::CreatePointerCast(G, PointerType::getUnqual(Context), "",2825 F.getEntryBlock().begin());2826 2827 EXPECT_FALSE(verifyModule(*M, &errs()));2828 2829 CG.addSplitRefRecursiveFunctions(F, SmallVector<Function *, 1>({G}));2830 2831 LazyCallGraph::Node *GN = CG.lookup(*G);2832 EXPECT_TRUE(GN);2833 2834 I = CG.postorder_ref_scc_begin();2835 LazyCallGraph::RefSCC *RC = &*I++;2836 EXPECT_EQ(RC, CG.lookupRefSCC(*GN));2837 EXPECT_EQ(RC, ORC);2838 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2839 2840 // Order doesn't matter for sibling SCCs.2841 EXPECT_EQ(2, RC->size());2842 EXPECT_EQ(&CG.lookupSCC(*GN)->getOuterRefSCC(), RC);2843 EXPECT_EQ(&CG.lookupSCC(FN)->getOuterRefSCC(), RC);2844}2845 2846TEST(LazyCallGraphTest, AddSplitFunctions3) {2847 LLVMContext Context;2848 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"2849 " ret void\n"2850 "}\n");2851 LazyCallGraph CG = buildCG(*M);2852 2853 Function &F = lookupFunction(*M, "f");2854 LazyCallGraph::Node &FN = CG.get(F);2855 2856 // Force the graph to be fully expanded.2857 CG.buildRefSCCs();2858 auto I = CG.postorder_ref_scc_begin();2859 LazyCallGraph::RefSCC *ORC = &*I++;2860 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2861 2862 auto *G1 = Function::Create(F.getFunctionType(), F.getLinkage(),2863 F.getAddressSpace(), "g1", F.getParent());2864 auto *G2 = Function::Create(F.getFunctionType(), F.getLinkage(),2865 F.getAddressSpace(), "g2", F.getParent());2866 BasicBlock *G1BB = BasicBlock::Create(Context, "", G1);2867 BasicBlock *G2BB = BasicBlock::Create(Context, "", G2);2868 // Create g1 -ref-> g2 and g2 -ref-> g1.2869 (void)CastInst::CreatePointerCast(G2, PointerType::getUnqual(Context), "",2870 G1BB);2871 (void)CastInst::CreatePointerCast(G1, PointerType::getUnqual(Context), "",2872 G2BB);2873 (void)ReturnInst::Create(Context, G1BB);2874 (void)ReturnInst::Create(Context, G2BB);2875 2876 // Create f -ref-> g1 and f -ref-> g2.2877 (void)CastInst::CreatePointerCast(G1, PointerType::getUnqual(Context), "",2878 F.getEntryBlock().begin());2879 (void)CastInst::CreatePointerCast(G2, PointerType::getUnqual(Context), "",2880 F.getEntryBlock().begin());2881 2882 EXPECT_FALSE(verifyModule(*M, &errs()));2883 2884 CG.addSplitRefRecursiveFunctions(F, SmallVector<Function *, 1>({G1, G2}));2885 2886 LazyCallGraph::Node *G1N = CG.lookup(*G1);2887 EXPECT_TRUE(G1N);2888 LazyCallGraph::Node *G2N = CG.lookup(*G2);2889 EXPECT_TRUE(G2N);2890 2891 I = CG.postorder_ref_scc_begin();2892 LazyCallGraph::RefSCC *RC1 = &*I++;2893 EXPECT_EQ(2, RC1->size());2894 EXPECT_EQ(RC1, CG.lookupRefSCC(*G1N));2895 EXPECT_EQ(RC1, CG.lookupRefSCC(*G2N));2896 LazyCallGraph::RefSCC *RC2 = &*I++;2897 EXPECT_EQ(RC2, ORC);2898 EXPECT_EQ(RC2, CG.lookupRefSCC(FN));2899 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2900}2901 2902TEST(LazyCallGraphTest, AddSplitFunctions4) {2903 LLVMContext Context;2904 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"2905 " ret void\n"2906 "}\n");2907 LazyCallGraph CG = buildCG(*M);2908 2909 Function &F = lookupFunction(*M, "f");2910 LazyCallGraph::Node &FN = CG.get(F);2911 2912 // Force the graph to be fully expanded.2913 CG.buildRefSCCs();2914 auto I = CG.postorder_ref_scc_begin();2915 LazyCallGraph::RefSCC *ORC = &*I++;2916 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2917 2918 auto *G1 = Function::Create(F.getFunctionType(), F.getLinkage(),2919 F.getAddressSpace(), "g1", F.getParent());2920 auto *G2 = Function::Create(F.getFunctionType(), F.getLinkage(),2921 F.getAddressSpace(), "g2", F.getParent());2922 BasicBlock *G1BB = BasicBlock::Create(Context, "", G1);2923 BasicBlock *G2BB = BasicBlock::Create(Context, "", G2);2924 // Create g1 -ref-> g2 and g2 -ref-> g1.2925 (void)CastInst::CreatePointerCast(G2, PointerType::getUnqual(Context), "",2926 G1BB);2927 (void)CastInst::CreatePointerCast(G1, PointerType::getUnqual(Context), "",2928 G2BB);2929 // Create g2 -ref-> f.2930 (void)CastInst::CreatePointerCast(&F, PointerType::getUnqual(Context), "",2931 G2BB);2932 (void)ReturnInst::Create(Context, G1BB);2933 (void)ReturnInst::Create(Context, G2BB);2934 2935 // Create f -ref-> g1 and f -ref-> g2.2936 (void)CastInst::CreatePointerCast(G1, PointerType::getUnqual(Context), "",2937 F.getEntryBlock().begin());2938 (void)CastInst::CreatePointerCast(G2, PointerType::getUnqual(Context), "",2939 F.getEntryBlock().begin());2940 2941 EXPECT_FALSE(verifyModule(*M, &errs()));2942 2943 CG.addSplitRefRecursiveFunctions(F, SmallVector<Function *, 1>({G1, G2}));2944 2945 LazyCallGraph::Node *G1N = CG.lookup(*G1);2946 EXPECT_TRUE(G1N);2947 LazyCallGraph::Node *G2N = CG.lookup(*G2);2948 EXPECT_TRUE(G2N);2949 2950 I = CG.postorder_ref_scc_begin();2951 LazyCallGraph::RefSCC *RC = &*I++;2952 EXPECT_EQ(RC, ORC);2953 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2954 2955 // Order doesn't matter for sibling SCCs.2956 EXPECT_EQ(3, RC->size());2957 EXPECT_EQ(&CG.lookupSCC(FN)->getOuterRefSCC(), RC);2958 EXPECT_EQ(&CG.lookupSCC(*G1N)->getOuterRefSCC(), RC);2959 EXPECT_EQ(&CG.lookupSCC(*G2N)->getOuterRefSCC(), RC);2960 EXPECT_EQ(RC, CG.lookupRefSCC(*G1N));2961 EXPECT_EQ(RC, CG.lookupRefSCC(*G2N));2962}2963 2964TEST(LazyCallGraphTest, AddSplitFunctions5) {2965 LLVMContext Context;2966 std::unique_ptr<Module> M =2967 parseAssembly(Context, "define void @f() {\n"2968 " %1 = bitcast ptr @f2 to ptr\n"2969 " ret void\n"2970 "}\n"2971 "define void @f2() {\n"2972 " call void @f()\n"2973 " ret void\n"2974 "}\n");2975 LazyCallGraph CG = buildCG(*M);2976 2977 Function &F = lookupFunction(*M, "f");2978 LazyCallGraph::Node &FN = CG.get(F);2979 Function &F2 = lookupFunction(*M, "f2");2980 LazyCallGraph::Node &F2N = CG.get(F);2981 2982 // Force the graph to be fully expanded.2983 CG.buildRefSCCs();2984 auto I = CG.postorder_ref_scc_begin();2985 LazyCallGraph::RefSCC *ORC = &*I++;2986 EXPECT_EQ(CG.postorder_ref_scc_end(), I);2987 2988 auto *G1 = Function::Create(F.getFunctionType(), F.getLinkage(),2989 F.getAddressSpace(), "g1", F.getParent());2990 auto *G2 = Function::Create(F.getFunctionType(), F.getLinkage(),2991 F.getAddressSpace(), "g2", F.getParent());2992 BasicBlock *G1BB = BasicBlock::Create(Context, "", G1);2993 BasicBlock *G2BB = BasicBlock::Create(Context, "", G2);2994 // Create g1 -ref-> g2 and g2 -ref-> g1.2995 (void)CastInst::CreatePointerCast(G2, PointerType::getUnqual(Context), "",2996 G1BB);2997 (void)CastInst::CreatePointerCast(G1, PointerType::getUnqual(Context), "",2998 G2BB);2999 // Create g2 -ref-> f2.3000 (void)CastInst::CreatePointerCast(&F2, PointerType::getUnqual(Context), "",3001 G2BB);3002 (void)ReturnInst::Create(Context, G1BB);3003 (void)ReturnInst::Create(Context, G2BB);3004 3005 // Create f -ref-> g1 and f -ref-> g2.3006 (void)CastInst::CreatePointerCast(G1, PointerType::getUnqual(Context), "",3007 F.getEntryBlock().begin());3008 (void)CastInst::CreatePointerCast(G2, PointerType::getUnqual(Context), "",3009 F.getEntryBlock().begin());3010 3011 EXPECT_FALSE(verifyModule(*M, &errs()));3012 3013 CG.addSplitRefRecursiveFunctions(F, SmallVector<Function *, 1>({G1, G2}));3014 3015 LazyCallGraph::Node *G1N = CG.lookup(*G1);3016 EXPECT_TRUE(G1N);3017 LazyCallGraph::Node *G2N = CG.lookup(*G2);3018 EXPECT_TRUE(G2N);3019 3020 I = CG.postorder_ref_scc_begin();3021 LazyCallGraph::RefSCC *RC = &*I++;3022 EXPECT_EQ(4, RC->size());3023 EXPECT_EQ(RC, ORC);3024 EXPECT_EQ(RC, CG.lookupRefSCC(*G1N));3025 EXPECT_EQ(RC, CG.lookupRefSCC(*G2N));3026 EXPECT_EQ(RC, CG.lookupRefSCC(FN));3027 EXPECT_EQ(RC, CG.lookupRefSCC(F2N));3028 EXPECT_EQ(CG.postorder_ref_scc_end(), I);3029}3030}3031