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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "llvm/Analysis/LazyCallGraph.h" 10 #include "llvm/ADT/Triple.h" 11 #include "llvm/AsmParser/Parser.h" 12 #include "llvm/IR/Function.h" 13 #include "llvm/IR/Instructions.h" 14 #include "llvm/IR/LLVMContext.h" 15 #include "llvm/IR/Module.h" 16 #include "llvm/Support/ErrorHandling.h" 17 #include "llvm/Support/SourceMgr.h" 18 #include "gtest/gtest.h" 19 #include <memory> 20 21 using namespace llvm; 22 23 namespace { 24 25 std::unique_ptr<Module> parseAssembly(LLVMContext &Context, 26 const char *Assembly) { 27 SMDiagnostic Error; 28 std::unique_ptr<Module> M = parseAssemblyString(Assembly, Error, Context); 29 30 std::string ErrMsg; 31 raw_string_ostream OS(ErrMsg); 32 Error.print("", OS); 33 34 // A failure here means that the test itself is buggy. 35 if (!M) 36 report_fatal_error(OS.str().c_str()); 37 38 return M; 39 } 40 41 /* 42 IR forming a call graph with a diamond of triangle-shaped SCCs: 43 44 d1 45 / \ 46 d3--d2 47 / \ 48 b1 c1 49 / \ / \ 50 b3--b2 c3--c2 51 \ / 52 a1 53 / \ 54 a3--a2 55 56 All call edges go up between SCCs, and clockwise around the SCC. 57 */ 58 static const char DiamondOfTriangles[] = 59 "define void @a1() {\n" 60 "entry:\n" 61 " call void @a2()\n" 62 " call void @b2()\n" 63 " call void @c3()\n" 64 " ret void\n" 65 "}\n" 66 "define void @a2() {\n" 67 "entry:\n" 68 " call void @a3()\n" 69 " ret void\n" 70 "}\n" 71 "define void @a3() {\n" 72 "entry:\n" 73 " call void @a1()\n" 74 " ret void\n" 75 "}\n" 76 "define void @b1() {\n" 77 "entry:\n" 78 " call void @b2()\n" 79 " call void @d3()\n" 80 " ret void\n" 81 "}\n" 82 "define void @b2() {\n" 83 "entry:\n" 84 " call void @b3()\n" 85 " ret void\n" 86 "}\n" 87 "define void @b3() {\n" 88 "entry:\n" 89 " call void @b1()\n" 90 " ret void\n" 91 "}\n" 92 "define void @c1() {\n" 93 "entry:\n" 94 " call void @c2()\n" 95 " call void @d2()\n" 96 " ret void\n" 97 "}\n" 98 "define void @c2() {\n" 99 "entry:\n" 100 " call void @c3()\n" 101 " ret void\n" 102 "}\n" 103 "define void @c3() {\n" 104 "entry:\n" 105 " call void @c1()\n" 106 " ret void\n" 107 "}\n" 108 "define void @d1() {\n" 109 "entry:\n" 110 " call void @d2()\n" 111 " ret void\n" 112 "}\n" 113 "define void @d2() {\n" 114 "entry:\n" 115 " call void @d3()\n" 116 " ret void\n" 117 "}\n" 118 "define void @d3() {\n" 119 "entry:\n" 120 " call void @d1()\n" 121 " ret void\n" 122 "}\n"; 123 124 /* 125 IR forming a reference graph with a diamond of triangle-shaped RefSCCs 126 127 d1 128 / \ 129 d3--d2 130 / \ 131 b1 c1 132 / \ / \ 133 b3--b2 c3--c2 134 \ / 135 a1 136 / \ 137 a3--a2 138 139 All call edges go up between RefSCCs, and clockwise around the RefSCC. 140 */ 141 static const char DiamondOfTrianglesRefGraph[] = 142 "define void @a1() {\n" 143 "entry:\n" 144 " %a = alloca void ()*\n" 145 " store void ()* @a2, void ()** %a\n" 146 " store void ()* @b2, void ()** %a\n" 147 " store void ()* @c3, void ()** %a\n" 148 " ret void\n" 149 "}\n" 150 "define void @a2() {\n" 151 "entry:\n" 152 " %a = alloca void ()*\n" 153 " store void ()* @a3, void ()** %a\n" 154 " ret void\n" 155 "}\n" 156 "define void @a3() {\n" 157 "entry:\n" 158 " %a = alloca void ()*\n" 159 " store void ()* @a1, void ()** %a\n" 160 " ret void\n" 161 "}\n" 162 "define void @b1() {\n" 163 "entry:\n" 164 " %a = alloca void ()*\n" 165 " store void ()* @b2, void ()** %a\n" 166 " store void ()* @d3, void ()** %a\n" 167 " ret void\n" 168 "}\n" 169 "define void @b2() {\n" 170 "entry:\n" 171 " %a = alloca void ()*\n" 172 " store void ()* @b3, void ()** %a\n" 173 " ret void\n" 174 "}\n" 175 "define void @b3() {\n" 176 "entry:\n" 177 " %a = alloca void ()*\n" 178 " store void ()* @b1, void ()** %a\n" 179 " ret void\n" 180 "}\n" 181 "define void @c1() {\n" 182 "entry:\n" 183 " %a = alloca void ()*\n" 184 " store void ()* @c2, void ()** %a\n" 185 " store void ()* @d2, void ()** %a\n" 186 " ret void\n" 187 "}\n" 188 "define void @c2() {\n" 189 "entry:\n" 190 " %a = alloca void ()*\n" 191 " store void ()* @c3, void ()** %a\n" 192 " ret void\n" 193 "}\n" 194 "define void @c3() {\n" 195 "entry:\n" 196 " %a = alloca void ()*\n" 197 " store void ()* @c1, void ()** %a\n" 198 " ret void\n" 199 "}\n" 200 "define void @d1() {\n" 201 "entry:\n" 202 " %a = alloca void ()*\n" 203 " store void ()* @d2, void ()** %a\n" 204 " ret void\n" 205 "}\n" 206 "define void @d2() {\n" 207 "entry:\n" 208 " %a = alloca void ()*\n" 209 " store void ()* @d3, void ()** %a\n" 210 " ret void\n" 211 "}\n" 212 "define void @d3() {\n" 213 "entry:\n" 214 " %a = alloca void ()*\n" 215 " store void ()* @d1, void ()** %a\n" 216 " ret void\n" 217 "}\n"; 218 219 static LazyCallGraph buildCG(Module &M) { 220 TargetLibraryInfoImpl TLII(Triple(M.getTargetTriple())); 221 TargetLibraryInfo TLI(TLII); 222 auto GetTLI = [&TLI](Function &F) -> TargetLibraryInfo & { return TLI; }; 223 224 LazyCallGraph CG(M, GetTLI); 225 return CG; 226 } 227 228 TEST(LazyCallGraphTest, BasicGraphFormation) { 229 LLVMContext Context; 230 std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles); 231 LazyCallGraph CG = buildCG(*M); 232 233 // The order of the entry nodes should be stable w.r.t. the source order of 234 // the IR, and everything in our module is an entry node, so just directly 235 // build variables for each node. 236 auto I = CG.begin(); 237 LazyCallGraph::Node &A1 = (I++)->getNode(); 238 EXPECT_EQ("a1", A1.getFunction().getName()); 239 LazyCallGraph::Node &A2 = (I++)->getNode(); 240 EXPECT_EQ("a2", A2.getFunction().getName()); 241 LazyCallGraph::Node &A3 = (I++)->getNode(); 242 EXPECT_EQ("a3", A3.getFunction().getName()); 243 LazyCallGraph::Node &B1 = (I++)->getNode(); 244 EXPECT_EQ("b1", B1.getFunction().getName()); 245 LazyCallGraph::Node &B2 = (I++)->getNode(); 246 EXPECT_EQ("b2", B2.getFunction().getName()); 247 LazyCallGraph::Node &B3 = (I++)->getNode(); 248 EXPECT_EQ("b3", B3.getFunction().getName()); 249 LazyCallGraph::Node &C1 = (I++)->getNode(); 250 EXPECT_EQ("c1", C1.getFunction().getName()); 251 LazyCallGraph::Node &C2 = (I++)->getNode(); 252 EXPECT_EQ("c2", C2.getFunction().getName()); 253 LazyCallGraph::Node &C3 = (I++)->getNode(); 254 EXPECT_EQ("c3", C3.getFunction().getName()); 255 LazyCallGraph::Node &D1 = (I++)->getNode(); 256 EXPECT_EQ("d1", D1.getFunction().getName()); 257 LazyCallGraph::Node &D2 = (I++)->getNode(); 258 EXPECT_EQ("d2", D2.getFunction().getName()); 259 LazyCallGraph::Node &D3 = (I++)->getNode(); 260 EXPECT_EQ("d3", D3.getFunction().getName()); 261 EXPECT_EQ(CG.end(), I); 262 263 // Build vectors and sort them for the rest of the assertions to make them 264 // independent of order. 265 std::vector<std::string> Nodes; 266 267 for (LazyCallGraph::Edge &E : A1.populate()) 268 Nodes.push_back(std::string(E.getFunction().getName())); 269 llvm::sort(Nodes); 270 EXPECT_EQ("a2", Nodes[0]); 271 EXPECT_EQ("b2", Nodes[1]); 272 EXPECT_EQ("c3", Nodes[2]); 273 Nodes.clear(); 274 275 A2.populate(); 276 EXPECT_EQ(A2->end(), std::next(A2->begin())); 277 EXPECT_EQ("a3", A2->begin()->getFunction().getName()); 278 A3.populate(); 279 EXPECT_EQ(A3->end(), std::next(A3->begin())); 280 EXPECT_EQ("a1", A3->begin()->getFunction().getName()); 281 282 for (LazyCallGraph::Edge &E : B1.populate()) 283 Nodes.push_back(std::string(E.getFunction().getName())); 284 llvm::sort(Nodes); 285 EXPECT_EQ("b2", Nodes[0]); 286 EXPECT_EQ("d3", Nodes[1]); 287 Nodes.clear(); 288 289 B2.populate(); 290 EXPECT_EQ(B2->end(), std::next(B2->begin())); 291 EXPECT_EQ("b3", B2->begin()->getFunction().getName()); 292 B3.populate(); 293 EXPECT_EQ(B3->end(), std::next(B3->begin())); 294 EXPECT_EQ("b1", B3->begin()->getFunction().getName()); 295 296 for (LazyCallGraph::Edge &E : C1.populate()) 297 Nodes.push_back(std::string(E.getFunction().getName())); 298 llvm::sort(Nodes); 299 EXPECT_EQ("c2", Nodes[0]); 300 EXPECT_EQ("d2", Nodes[1]); 301 Nodes.clear(); 302 303 C2.populate(); 304 EXPECT_EQ(C2->end(), std::next(C2->begin())); 305 EXPECT_EQ("c3", C2->begin()->getFunction().getName()); 306 C3.populate(); 307 EXPECT_EQ(C3->end(), std::next(C3->begin())); 308 EXPECT_EQ("c1", C3->begin()->getFunction().getName()); 309 310 D1.populate(); 311 EXPECT_EQ(D1->end(), std::next(D1->begin())); 312 EXPECT_EQ("d2", D1->begin()->getFunction().getName()); 313 D2.populate(); 314 EXPECT_EQ(D2->end(), std::next(D2->begin())); 315 EXPECT_EQ("d3", D2->begin()->getFunction().getName()); 316 D3.populate(); 317 EXPECT_EQ(D3->end(), std::next(D3->begin())); 318 EXPECT_EQ("d1", D3->begin()->getFunction().getName()); 319 320 // Now lets look at the RefSCCs and SCCs. 321 CG.buildRefSCCs(); 322 auto J = CG.postorder_ref_scc_begin(); 323 324 LazyCallGraph::RefSCC &D = *J++; 325 ASSERT_EQ(1, D.size()); 326 for (LazyCallGraph::Node &N : *D.begin()) 327 Nodes.push_back(std::string(N.getFunction().getName())); 328 llvm::sort(Nodes); 329 EXPECT_EQ(3u, Nodes.size()); 330 EXPECT_EQ("d1", Nodes[0]); 331 EXPECT_EQ("d2", Nodes[1]); 332 EXPECT_EQ("d3", Nodes[2]); 333 Nodes.clear(); 334 EXPECT_FALSE(D.isParentOf(D)); 335 EXPECT_FALSE(D.isChildOf(D)); 336 EXPECT_FALSE(D.isAncestorOf(D)); 337 EXPECT_FALSE(D.isDescendantOf(D)); 338 EXPECT_EQ(&D, &*CG.postorder_ref_scc_begin()); 339 340 LazyCallGraph::RefSCC &C = *J++; 341 ASSERT_EQ(1, C.size()); 342 for (LazyCallGraph::Node &N : *C.begin()) 343 Nodes.push_back(std::string(N.getFunction().getName())); 344 llvm::sort(Nodes); 345 EXPECT_EQ(3u, Nodes.size()); 346 EXPECT_EQ("c1", Nodes[0]); 347 EXPECT_EQ("c2", Nodes[1]); 348 EXPECT_EQ("c3", Nodes[2]); 349 Nodes.clear(); 350 EXPECT_TRUE(C.isParentOf(D)); 351 EXPECT_FALSE(C.isChildOf(D)); 352 EXPECT_TRUE(C.isAncestorOf(D)); 353 EXPECT_FALSE(C.isDescendantOf(D)); 354 EXPECT_EQ(&C, &*std::next(CG.postorder_ref_scc_begin())); 355 356 LazyCallGraph::RefSCC &B = *J++; 357 ASSERT_EQ(1, B.size()); 358 for (LazyCallGraph::Node &N : *B.begin()) 359 Nodes.push_back(std::string(N.getFunction().getName())); 360 llvm::sort(Nodes); 361 EXPECT_EQ(3u, Nodes.size()); 362 EXPECT_EQ("b1", Nodes[0]); 363 EXPECT_EQ("b2", Nodes[1]); 364 EXPECT_EQ("b3", Nodes[2]); 365 Nodes.clear(); 366 EXPECT_TRUE(B.isParentOf(D)); 367 EXPECT_FALSE(B.isChildOf(D)); 368 EXPECT_TRUE(B.isAncestorOf(D)); 369 EXPECT_FALSE(B.isDescendantOf(D)); 370 EXPECT_FALSE(B.isAncestorOf(C)); 371 EXPECT_FALSE(C.isAncestorOf(B)); 372 EXPECT_EQ(&B, &*std::next(CG.postorder_ref_scc_begin(), 2)); 373 374 LazyCallGraph::RefSCC &A = *J++; 375 ASSERT_EQ(1, A.size()); 376 for (LazyCallGraph::Node &N : *A.begin()) 377 Nodes.push_back(std::string(N.getFunction().getName())); 378 llvm::sort(Nodes); 379 EXPECT_EQ(3u, Nodes.size()); 380 EXPECT_EQ("a1", Nodes[0]); 381 EXPECT_EQ("a2", Nodes[1]); 382 EXPECT_EQ("a3", Nodes[2]); 383 Nodes.clear(); 384 EXPECT_TRUE(A.isParentOf(B)); 385 EXPECT_TRUE(A.isParentOf(C)); 386 EXPECT_FALSE(A.isParentOf(D)); 387 EXPECT_TRUE(A.isAncestorOf(B)); 388 EXPECT_TRUE(A.isAncestorOf(C)); 389 EXPECT_TRUE(A.isAncestorOf(D)); 390 EXPECT_EQ(&A, &*std::next(CG.postorder_ref_scc_begin(), 3)); 391 392 EXPECT_EQ(CG.postorder_ref_scc_end(), J); 393 EXPECT_EQ(J, std::next(CG.postorder_ref_scc_begin(), 4)); 394 } 395 396 static Function &lookupFunction(Module &M, StringRef Name) { 397 for (Function &F : M) 398 if (F.getName() == Name) 399 return F; 400 report_fatal_error("Couldn't find function!"); 401 } 402 403 TEST(LazyCallGraphTest, BasicGraphMutation) { 404 LLVMContext Context; 405 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n" 406 "entry:\n" 407 " call void @b()\n" 408 " call void @c()\n" 409 " ret void\n" 410 "}\n" 411 "define void @b() {\n" 412 "entry:\n" 413 " ret void\n" 414 "}\n" 415 "define void @c() {\n" 416 "entry:\n" 417 " ret void\n" 418 "}\n"); 419 LazyCallGraph CG = buildCG(*M); 420 421 LazyCallGraph::Node &A = CG.get(lookupFunction(*M, "a")); 422 LazyCallGraph::Node &B = CG.get(lookupFunction(*M, "b")); 423 A.populate(); 424 EXPECT_EQ(2, std::distance(A->begin(), A->end())); 425 B.populate(); 426 EXPECT_EQ(0, std::distance(B->begin(), B->end())); 427 428 LazyCallGraph::Node &C = CG.get(lookupFunction(*M, "c")); 429 C.populate(); 430 CG.insertEdge(B, C, LazyCallGraph::Edge::Call); 431 EXPECT_EQ(1, std::distance(B->begin(), B->end())); 432 EXPECT_EQ(0, std::distance(C->begin(), C->end())); 433 434 CG.insertEdge(C, B, LazyCallGraph::Edge::Call); 435 EXPECT_EQ(1, std::distance(C->begin(), C->end())); 436 EXPECT_EQ(&B, &C->begin()->getNode()); 437 438 CG.insertEdge(C, C, LazyCallGraph::Edge::Call); 439 EXPECT_EQ(2, std::distance(C->begin(), C->end())); 440 EXPECT_EQ(&B, &C->begin()->getNode()); 441 EXPECT_EQ(&C, &std::next(C->begin())->getNode()); 442 443 CG.removeEdge(C, B); 444 EXPECT_EQ(1, std::distance(C->begin(), C->end())); 445 EXPECT_EQ(&C, &C->begin()->getNode()); 446 447 CG.removeEdge(C, C); 448 EXPECT_EQ(0, std::distance(C->begin(), C->end())); 449 450 CG.removeEdge(B, C); 451 EXPECT_EQ(0, std::distance(B->begin(), B->end())); 452 } 453 454 TEST(LazyCallGraphTest, BasicGraphMutationOutlining) { 455 LLVMContext Context; 456 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n" 457 "entry:\n" 458 " call void @b()\n" 459 " call void @c()\n" 460 " ret void\n" 461 "}\n" 462 "define void @b() {\n" 463 "entry:\n" 464 " ret void\n" 465 "}\n" 466 "define void @c() {\n" 467 "entry:\n" 468 " ret void\n" 469 "}\n"); 470 LazyCallGraph CG = buildCG(*M); 471 472 LazyCallGraph::Node &A = CG.get(lookupFunction(*M, "a")); 473 LazyCallGraph::Node &B = CG.get(lookupFunction(*M, "b")); 474 LazyCallGraph::Node &C = CG.get(lookupFunction(*M, "c")); 475 A.populate(); 476 B.populate(); 477 C.populate(); 478 CG.buildRefSCCs(); 479 480 // Add a new function that is called from @b and verify it is in the same SCC. 481 Function &BFn = B.getFunction(); 482 Function *NewFn = 483 Function::Create(BFn.getFunctionType(), BFn.getLinkage(), "NewFn", *M); 484 auto IP = BFn.getEntryBlock().getFirstInsertionPt(); 485 CallInst::Create(NewFn, "", &*IP); 486 CG.addNewFunctionIntoSCC(*NewFn, *CG.lookupSCC(B)); 487 488 EXPECT_EQ(CG.lookupSCC(A)->size(), 1); 489 EXPECT_EQ(CG.lookupSCC(B)->size(), 2); 490 EXPECT_EQ(CG.lookupSCC(C)->size(), 1); 491 EXPECT_EQ(CG.lookupSCC(*CG.lookup(*NewFn))->size(), 2); 492 EXPECT_EQ(CG.lookupSCC(*CG.lookup(*NewFn))->size(), CG.lookupSCC(B)->size()); 493 } 494 495 TEST(LazyCallGraphTest, InnerSCCFormation) { 496 LLVMContext Context; 497 std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles); 498 LazyCallGraph CG = buildCG(*M); 499 500 // Now mutate the graph to connect every node into a single RefSCC to ensure 501 // that our inner SCC formation handles the rest. 502 LazyCallGraph::Node &D1 = CG.get(lookupFunction(*M, "d1")); 503 LazyCallGraph::Node &A1 = CG.get(lookupFunction(*M, "a1")); 504 A1.populate(); 505 D1.populate(); 506 CG.insertEdge(D1, A1, LazyCallGraph::Edge::Ref); 507 508 // Build vectors and sort them for the rest of the assertions to make them 509 // independent of order. 510 std::vector<std::string> Nodes; 511 512 // We should build a single RefSCC for the entire graph. 513 CG.buildRefSCCs(); 514 auto I = CG.postorder_ref_scc_begin(); 515 LazyCallGraph::RefSCC &RC = *I++; 516 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 517 518 // Now walk the four SCCs which should be in post-order. 519 auto J = RC.begin(); 520 LazyCallGraph::SCC &D = *J++; 521 for (LazyCallGraph::Node &N : D) 522 Nodes.push_back(std::string(N.getFunction().getName())); 523 llvm::sort(Nodes); 524 EXPECT_EQ(3u, Nodes.size()); 525 EXPECT_EQ("d1", Nodes[0]); 526 EXPECT_EQ("d2", Nodes[1]); 527 EXPECT_EQ("d3", Nodes[2]); 528 Nodes.clear(); 529 530 LazyCallGraph::SCC &B = *J++; 531 for (LazyCallGraph::Node &N : B) 532 Nodes.push_back(std::string(N.getFunction().getName())); 533 llvm::sort(Nodes); 534 EXPECT_EQ(3u, Nodes.size()); 535 EXPECT_EQ("b1", Nodes[0]); 536 EXPECT_EQ("b2", Nodes[1]); 537 EXPECT_EQ("b3", Nodes[2]); 538 Nodes.clear(); 539 540 LazyCallGraph::SCC &C = *J++; 541 for (LazyCallGraph::Node &N : C) 542 Nodes.push_back(std::string(N.getFunction().getName())); 543 llvm::sort(Nodes); 544 EXPECT_EQ(3u, Nodes.size()); 545 EXPECT_EQ("c1", Nodes[0]); 546 EXPECT_EQ("c2", Nodes[1]); 547 EXPECT_EQ("c3", Nodes[2]); 548 Nodes.clear(); 549 550 LazyCallGraph::SCC &A = *J++; 551 for (LazyCallGraph::Node &N : A) 552 Nodes.push_back(std::string(N.getFunction().getName())); 553 llvm::sort(Nodes); 554 EXPECT_EQ(3u, Nodes.size()); 555 EXPECT_EQ("a1", Nodes[0]); 556 EXPECT_EQ("a2", Nodes[1]); 557 EXPECT_EQ("a3", Nodes[2]); 558 Nodes.clear(); 559 560 EXPECT_EQ(RC.end(), J); 561 } 562 563 TEST(LazyCallGraphTest, MultiArmSCC) { 564 LLVMContext Context; 565 // Two interlocking cycles. The really useful thing about this SCC is that it 566 // will require Tarjan's DFS to backtrack and finish processing all of the 567 // children of each node in the SCC. Since this involves call edges, both 568 // Tarjan implementations will have to successfully navigate the structure. 569 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f1() {\n" 570 "entry:\n" 571 " call void @f2()\n" 572 " call void @f4()\n" 573 " ret void\n" 574 "}\n" 575 "define void @f2() {\n" 576 "entry:\n" 577 " call void @f3()\n" 578 " ret void\n" 579 "}\n" 580 "define void @f3() {\n" 581 "entry:\n" 582 " call void @f1()\n" 583 " ret void\n" 584 "}\n" 585 "define void @f4() {\n" 586 "entry:\n" 587 " call void @f5()\n" 588 " ret void\n" 589 "}\n" 590 "define void @f5() {\n" 591 "entry:\n" 592 " call void @f1()\n" 593 " ret void\n" 594 "}\n"); 595 LazyCallGraph CG = buildCG(*M); 596 597 // Force the graph to be fully expanded. 598 CG.buildRefSCCs(); 599 auto I = CG.postorder_ref_scc_begin(); 600 LazyCallGraph::RefSCC &RC = *I++; 601 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 602 603 LazyCallGraph::Node &N1 = *CG.lookup(lookupFunction(*M, "f1")); 604 LazyCallGraph::Node &N2 = *CG.lookup(lookupFunction(*M, "f2")); 605 LazyCallGraph::Node &N3 = *CG.lookup(lookupFunction(*M, "f3")); 606 LazyCallGraph::Node &N4 = *CG.lookup(lookupFunction(*M, "f4")); 607 LazyCallGraph::Node &N5 = *CG.lookup(lookupFunction(*M, "f4")); 608 EXPECT_EQ(&RC, CG.lookupRefSCC(N1)); 609 EXPECT_EQ(&RC, CG.lookupRefSCC(N2)); 610 EXPECT_EQ(&RC, CG.lookupRefSCC(N3)); 611 EXPECT_EQ(&RC, CG.lookupRefSCC(N4)); 612 EXPECT_EQ(&RC, CG.lookupRefSCC(N5)); 613 614 ASSERT_EQ(1, RC.size()); 615 616 LazyCallGraph::SCC &C = *RC.begin(); 617 EXPECT_EQ(&C, CG.lookupSCC(N1)); 618 EXPECT_EQ(&C, CG.lookupSCC(N2)); 619 EXPECT_EQ(&C, CG.lookupSCC(N3)); 620 EXPECT_EQ(&C, CG.lookupSCC(N4)); 621 EXPECT_EQ(&C, CG.lookupSCC(N5)); 622 } 623 624 TEST(LazyCallGraphTest, OutgoingEdgeMutation) { 625 LLVMContext Context; 626 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n" 627 "entry:\n" 628 " call void @b()\n" 629 " call void @c()\n" 630 " ret void\n" 631 "}\n" 632 "define void @b() {\n" 633 "entry:\n" 634 " call void @d()\n" 635 " ret void\n" 636 "}\n" 637 "define void @c() {\n" 638 "entry:\n" 639 " call void @d()\n" 640 " ret void\n" 641 "}\n" 642 "define void @d() {\n" 643 "entry:\n" 644 " ret void\n" 645 "}\n"); 646 LazyCallGraph CG = buildCG(*M); 647 648 // Force the graph to be fully expanded. 649 CG.buildRefSCCs(); 650 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) 651 dbgs() << "Formed RefSCC: " << RC << "\n"; 652 653 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 654 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 655 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 656 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); 657 LazyCallGraph::SCC &AC = *CG.lookupSCC(A); 658 LazyCallGraph::SCC &BC = *CG.lookupSCC(B); 659 LazyCallGraph::SCC &CC = *CG.lookupSCC(C); 660 LazyCallGraph::SCC &DC = *CG.lookupSCC(D); 661 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A); 662 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B); 663 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C); 664 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D); 665 EXPECT_TRUE(ARC.isParentOf(BRC)); 666 EXPECT_TRUE(AC.isParentOf(BC)); 667 EXPECT_TRUE(ARC.isParentOf(CRC)); 668 EXPECT_TRUE(AC.isParentOf(CC)); 669 EXPECT_FALSE(ARC.isParentOf(DRC)); 670 EXPECT_FALSE(AC.isParentOf(DC)); 671 EXPECT_TRUE(ARC.isAncestorOf(DRC)); 672 EXPECT_TRUE(AC.isAncestorOf(DC)); 673 EXPECT_FALSE(DRC.isChildOf(ARC)); 674 EXPECT_FALSE(DC.isChildOf(AC)); 675 EXPECT_TRUE(DRC.isDescendantOf(ARC)); 676 EXPECT_TRUE(DC.isDescendantOf(AC)); 677 EXPECT_TRUE(DRC.isChildOf(BRC)); 678 EXPECT_TRUE(DC.isChildOf(BC)); 679 EXPECT_TRUE(DRC.isChildOf(CRC)); 680 EXPECT_TRUE(DC.isChildOf(CC)); 681 682 EXPECT_EQ(2, std::distance(A->begin(), A->end())); 683 ARC.insertOutgoingEdge(A, D, LazyCallGraph::Edge::Call); 684 EXPECT_EQ(3, std::distance(A->begin(), A->end())); 685 const LazyCallGraph::Edge &NewE = (*A)[D]; 686 EXPECT_TRUE(NewE); 687 EXPECT_TRUE(NewE.isCall()); 688 EXPECT_EQ(&D, &NewE.getNode()); 689 690 // Only the parent and child tests sholud have changed. The rest of the graph 691 // remains the same. 692 EXPECT_TRUE(ARC.isParentOf(DRC)); 693 EXPECT_TRUE(AC.isParentOf(DC)); 694 EXPECT_TRUE(ARC.isAncestorOf(DRC)); 695 EXPECT_TRUE(AC.isAncestorOf(DC)); 696 EXPECT_TRUE(DRC.isChildOf(ARC)); 697 EXPECT_TRUE(DC.isChildOf(AC)); 698 EXPECT_TRUE(DRC.isDescendantOf(ARC)); 699 EXPECT_TRUE(DC.isDescendantOf(AC)); 700 EXPECT_EQ(&AC, CG.lookupSCC(A)); 701 EXPECT_EQ(&BC, CG.lookupSCC(B)); 702 EXPECT_EQ(&CC, CG.lookupSCC(C)); 703 EXPECT_EQ(&DC, CG.lookupSCC(D)); 704 EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); 705 EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); 706 EXPECT_EQ(&CRC, CG.lookupRefSCC(C)); 707 EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); 708 709 ARC.switchOutgoingEdgeToRef(A, D); 710 EXPECT_FALSE(NewE.isCall()); 711 712 // Verify the reference graph remains the same but the SCC graph is updated. 713 EXPECT_TRUE(ARC.isParentOf(DRC)); 714 EXPECT_FALSE(AC.isParentOf(DC)); 715 EXPECT_TRUE(ARC.isAncestorOf(DRC)); 716 EXPECT_TRUE(AC.isAncestorOf(DC)); 717 EXPECT_TRUE(DRC.isChildOf(ARC)); 718 EXPECT_FALSE(DC.isChildOf(AC)); 719 EXPECT_TRUE(DRC.isDescendantOf(ARC)); 720 EXPECT_TRUE(DC.isDescendantOf(AC)); 721 EXPECT_EQ(&AC, CG.lookupSCC(A)); 722 EXPECT_EQ(&BC, CG.lookupSCC(B)); 723 EXPECT_EQ(&CC, CG.lookupSCC(C)); 724 EXPECT_EQ(&DC, CG.lookupSCC(D)); 725 EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); 726 EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); 727 EXPECT_EQ(&CRC, CG.lookupRefSCC(C)); 728 EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); 729 730 ARC.switchOutgoingEdgeToCall(A, D); 731 EXPECT_TRUE(NewE.isCall()); 732 733 // Verify the reference graph remains the same but the SCC graph is updated. 734 EXPECT_TRUE(ARC.isParentOf(DRC)); 735 EXPECT_TRUE(AC.isParentOf(DC)); 736 EXPECT_TRUE(ARC.isAncestorOf(DRC)); 737 EXPECT_TRUE(AC.isAncestorOf(DC)); 738 EXPECT_TRUE(DRC.isChildOf(ARC)); 739 EXPECT_TRUE(DC.isChildOf(AC)); 740 EXPECT_TRUE(DRC.isDescendantOf(ARC)); 741 EXPECT_TRUE(DC.isDescendantOf(AC)); 742 EXPECT_EQ(&AC, CG.lookupSCC(A)); 743 EXPECT_EQ(&BC, CG.lookupSCC(B)); 744 EXPECT_EQ(&CC, CG.lookupSCC(C)); 745 EXPECT_EQ(&DC, CG.lookupSCC(D)); 746 EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); 747 EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); 748 EXPECT_EQ(&CRC, CG.lookupRefSCC(C)); 749 EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); 750 751 ARC.removeOutgoingEdge(A, D); 752 EXPECT_EQ(2, std::distance(A->begin(), A->end())); 753 754 // Now the parent and child tests fail again but the rest remains the same. 755 EXPECT_FALSE(ARC.isParentOf(DRC)); 756 EXPECT_FALSE(AC.isParentOf(DC)); 757 EXPECT_TRUE(ARC.isAncestorOf(DRC)); 758 EXPECT_TRUE(AC.isAncestorOf(DC)); 759 EXPECT_FALSE(DRC.isChildOf(ARC)); 760 EXPECT_FALSE(DC.isChildOf(AC)); 761 EXPECT_TRUE(DRC.isDescendantOf(ARC)); 762 EXPECT_TRUE(DC.isDescendantOf(AC)); 763 EXPECT_EQ(&AC, CG.lookupSCC(A)); 764 EXPECT_EQ(&BC, CG.lookupSCC(B)); 765 EXPECT_EQ(&CC, CG.lookupSCC(C)); 766 EXPECT_EQ(&DC, CG.lookupSCC(D)); 767 EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); 768 EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); 769 EXPECT_EQ(&CRC, CG.lookupRefSCC(C)); 770 EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); 771 } 772 773 TEST(LazyCallGraphTest, IncomingEdgeInsertion) { 774 LLVMContext Context; 775 // We want to ensure we can add edges even across complex diamond graphs, so 776 // we use the diamond of triangles graph defined above. The ascii diagram is 777 // repeated here for easy reference. 778 // 779 // d1 | 780 // / \ | 781 // d3--d2 | 782 // / \ | 783 // b1 c1 | 784 // / \ / \ | 785 // b3--b2 c3--c2 | 786 // \ / | 787 // a1 | 788 // / \ | 789 // a3--a2 | 790 // 791 std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles); 792 LazyCallGraph CG = buildCG(*M); 793 794 // Force the graph to be fully expanded. 795 CG.buildRefSCCs(); 796 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) 797 dbgs() << "Formed RefSCC: " << RC << "\n"; 798 799 LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1")); 800 LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2")); 801 LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3")); 802 LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1")); 803 LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2")); 804 LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3")); 805 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1")); 806 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2")); 807 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3")); 808 LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1")); 809 LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2")); 810 LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3")); 811 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A1); 812 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B1); 813 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C1); 814 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D1); 815 ASSERT_EQ(&ARC, CG.lookupRefSCC(A2)); 816 ASSERT_EQ(&ARC, CG.lookupRefSCC(A3)); 817 ASSERT_EQ(&BRC, CG.lookupRefSCC(B2)); 818 ASSERT_EQ(&BRC, CG.lookupRefSCC(B3)); 819 ASSERT_EQ(&CRC, CG.lookupRefSCC(C2)); 820 ASSERT_EQ(&CRC, CG.lookupRefSCC(C3)); 821 ASSERT_EQ(&DRC, CG.lookupRefSCC(D2)); 822 ASSERT_EQ(&DRC, CG.lookupRefSCC(D3)); 823 ASSERT_EQ(1, std::distance(D2->begin(), D2->end())); 824 825 // Add an edge to make the graph: 826 // 827 // d1 | 828 // / \ | 829 // d3--d2---. | 830 // / \ | | 831 // b1 c1 | | 832 // / \ / \ / | 833 // b3--b2 c3--c2 | 834 // \ / | 835 // a1 | 836 // / \ | 837 // a3--a2 | 838 auto MergedRCs = CRC.insertIncomingRefEdge(D2, C2); 839 // Make sure we connected the nodes. 840 for (LazyCallGraph::Edge E : *D2) { 841 if (&E.getNode() == &D3) 842 continue; 843 EXPECT_EQ(&C2, &E.getNode()); 844 } 845 // And marked the D ref-SCC as no longer valid. 846 EXPECT_EQ(1u, MergedRCs.size()); 847 EXPECT_EQ(&DRC, MergedRCs[0]); 848 849 // Make sure we have the correct nodes in the SCC sets. 850 EXPECT_EQ(&ARC, CG.lookupRefSCC(A1)); 851 EXPECT_EQ(&ARC, CG.lookupRefSCC(A2)); 852 EXPECT_EQ(&ARC, CG.lookupRefSCC(A3)); 853 EXPECT_EQ(&BRC, CG.lookupRefSCC(B1)); 854 EXPECT_EQ(&BRC, CG.lookupRefSCC(B2)); 855 EXPECT_EQ(&BRC, CG.lookupRefSCC(B3)); 856 EXPECT_EQ(&CRC, CG.lookupRefSCC(C1)); 857 EXPECT_EQ(&CRC, CG.lookupRefSCC(C2)); 858 EXPECT_EQ(&CRC, CG.lookupRefSCC(C3)); 859 EXPECT_EQ(&CRC, CG.lookupRefSCC(D1)); 860 EXPECT_EQ(&CRC, CG.lookupRefSCC(D2)); 861 EXPECT_EQ(&CRC, CG.lookupRefSCC(D3)); 862 863 // And that ancestry tests have been updated. 864 EXPECT_TRUE(ARC.isParentOf(CRC)); 865 EXPECT_TRUE(BRC.isParentOf(CRC)); 866 867 // And verify the post-order walk reflects the updated structure. 868 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); 869 ASSERT_NE(I, E); 870 EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I; 871 ASSERT_NE(++I, E); 872 EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I; 873 ASSERT_NE(++I, E); 874 EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I; 875 EXPECT_EQ(++I, E); 876 } 877 878 TEST(LazyCallGraphTest, IncomingEdgeInsertionRefGraph) { 879 LLVMContext Context; 880 // Another variation of the above test but with all the edges switched to 881 // references rather than calls. 882 std::unique_ptr<Module> M = 883 parseAssembly(Context, DiamondOfTrianglesRefGraph); 884 LazyCallGraph CG = buildCG(*M); 885 886 // Force the graph to be fully expanded. 887 CG.buildRefSCCs(); 888 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) 889 dbgs() << "Formed RefSCC: " << RC << "\n"; 890 891 LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1")); 892 LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2")); 893 LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3")); 894 LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1")); 895 LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2")); 896 LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3")); 897 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1")); 898 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2")); 899 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3")); 900 LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1")); 901 LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2")); 902 LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3")); 903 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A1); 904 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B1); 905 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C1); 906 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D1); 907 ASSERT_EQ(&ARC, CG.lookupRefSCC(A2)); 908 ASSERT_EQ(&ARC, CG.lookupRefSCC(A3)); 909 ASSERT_EQ(&BRC, CG.lookupRefSCC(B2)); 910 ASSERT_EQ(&BRC, CG.lookupRefSCC(B3)); 911 ASSERT_EQ(&CRC, CG.lookupRefSCC(C2)); 912 ASSERT_EQ(&CRC, CG.lookupRefSCC(C3)); 913 ASSERT_EQ(&DRC, CG.lookupRefSCC(D2)); 914 ASSERT_EQ(&DRC, CG.lookupRefSCC(D3)); 915 ASSERT_EQ(1, std::distance(D2->begin(), D2->end())); 916 917 // Add an edge to make the graph: 918 // 919 // d1 | 920 // / \ | 921 // d3--d2---. | 922 // / \ | | 923 // b1 c1 | | 924 // / \ / \ / | 925 // b3--b2 c3--c2 | 926 // \ / | 927 // a1 | 928 // / \ | 929 // a3--a2 | 930 auto MergedRCs = CRC.insertIncomingRefEdge(D2, C2); 931 // Make sure we connected the nodes. 932 for (LazyCallGraph::Edge E : *D2) { 933 if (&E.getNode() == &D3) 934 continue; 935 EXPECT_EQ(&C2, &E.getNode()); 936 } 937 // And marked the D ref-SCC as no longer valid. 938 EXPECT_EQ(1u, MergedRCs.size()); 939 EXPECT_EQ(&DRC, MergedRCs[0]); 940 941 // Make sure we have the correct nodes in the SCC sets. 942 EXPECT_EQ(&ARC, CG.lookupRefSCC(A1)); 943 EXPECT_EQ(&ARC, CG.lookupRefSCC(A2)); 944 EXPECT_EQ(&ARC, CG.lookupRefSCC(A3)); 945 EXPECT_EQ(&BRC, CG.lookupRefSCC(B1)); 946 EXPECT_EQ(&BRC, CG.lookupRefSCC(B2)); 947 EXPECT_EQ(&BRC, CG.lookupRefSCC(B3)); 948 EXPECT_EQ(&CRC, CG.lookupRefSCC(C1)); 949 EXPECT_EQ(&CRC, CG.lookupRefSCC(C2)); 950 EXPECT_EQ(&CRC, CG.lookupRefSCC(C3)); 951 EXPECT_EQ(&CRC, CG.lookupRefSCC(D1)); 952 EXPECT_EQ(&CRC, CG.lookupRefSCC(D2)); 953 EXPECT_EQ(&CRC, CG.lookupRefSCC(D3)); 954 955 // And that ancestry tests have been updated. 956 EXPECT_TRUE(ARC.isParentOf(CRC)); 957 EXPECT_TRUE(BRC.isParentOf(CRC)); 958 959 // And verify the post-order walk reflects the updated structure. 960 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); 961 ASSERT_NE(I, E); 962 EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I; 963 ASSERT_NE(++I, E); 964 EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I; 965 ASSERT_NE(++I, E); 966 EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I; 967 EXPECT_EQ(++I, E); 968 } 969 970 TEST(LazyCallGraphTest, IncomingEdgeInsertionLargeCallCycle) { 971 LLVMContext Context; 972 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n" 973 "entry:\n" 974 " call void @b()\n" 975 " ret void\n" 976 "}\n" 977 "define void @b() {\n" 978 "entry:\n" 979 " call void @c()\n" 980 " ret void\n" 981 "}\n" 982 "define void @c() {\n" 983 "entry:\n" 984 " call void @d()\n" 985 " ret void\n" 986 "}\n" 987 "define void @d() {\n" 988 "entry:\n" 989 " ret void\n" 990 "}\n"); 991 LazyCallGraph CG = buildCG(*M); 992 993 // Force the graph to be fully expanded. 994 CG.buildRefSCCs(); 995 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) 996 dbgs() << "Formed RefSCC: " << RC << "\n"; 997 998 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 999 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 1000 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 1001 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); 1002 LazyCallGraph::SCC &AC = *CG.lookupSCC(A); 1003 LazyCallGraph::SCC &BC = *CG.lookupSCC(B); 1004 LazyCallGraph::SCC &CC = *CG.lookupSCC(C); 1005 LazyCallGraph::SCC &DC = *CG.lookupSCC(D); 1006 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A); 1007 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B); 1008 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C); 1009 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D); 1010 1011 // Connect the top to the bottom forming a large RefSCC made up mostly of calls. 1012 auto MergedRCs = ARC.insertIncomingRefEdge(D, A); 1013 // Make sure we connected the nodes. 1014 EXPECT_NE(D->begin(), D->end()); 1015 EXPECT_EQ(&A, &D->begin()->getNode()); 1016 1017 // Check that we have the dead RCs, but ignore the order. 1018 EXPECT_EQ(3u, MergedRCs.size()); 1019 EXPECT_NE(find(MergedRCs, &BRC), MergedRCs.end()); 1020 EXPECT_NE(find(MergedRCs, &CRC), MergedRCs.end()); 1021 EXPECT_NE(find(MergedRCs, &DRC), MergedRCs.end()); 1022 1023 // Make sure the nodes point to the right place now. 1024 EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); 1025 EXPECT_EQ(&ARC, CG.lookupRefSCC(B)); 1026 EXPECT_EQ(&ARC, CG.lookupRefSCC(C)); 1027 EXPECT_EQ(&ARC, CG.lookupRefSCC(D)); 1028 1029 // Check that the SCCs are in postorder. 1030 EXPECT_EQ(4, ARC.size()); 1031 EXPECT_EQ(&DC, &ARC[0]); 1032 EXPECT_EQ(&CC, &ARC[1]); 1033 EXPECT_EQ(&BC, &ARC[2]); 1034 EXPECT_EQ(&AC, &ARC[3]); 1035 1036 // And verify the post-order walk reflects the updated structure. 1037 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); 1038 ASSERT_NE(I, E); 1039 EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I; 1040 EXPECT_EQ(++I, E); 1041 } 1042 1043 TEST(LazyCallGraphTest, IncomingEdgeInsertionLargeRefCycle) { 1044 LLVMContext Context; 1045 std::unique_ptr<Module> M = 1046 parseAssembly(Context, "define void @a() {\n" 1047 "entry:\n" 1048 " %p = alloca void ()*\n" 1049 " store void ()* @b, void ()** %p\n" 1050 " ret void\n" 1051 "}\n" 1052 "define void @b() {\n" 1053 "entry:\n" 1054 " %p = alloca void ()*\n" 1055 " store void ()* @c, void ()** %p\n" 1056 " ret void\n" 1057 "}\n" 1058 "define void @c() {\n" 1059 "entry:\n" 1060 " %p = alloca void ()*\n" 1061 " store void ()* @d, void ()** %p\n" 1062 " ret void\n" 1063 "}\n" 1064 "define void @d() {\n" 1065 "entry:\n" 1066 " ret void\n" 1067 "}\n"); 1068 LazyCallGraph CG = buildCG(*M); 1069 1070 // Force the graph to be fully expanded. 1071 CG.buildRefSCCs(); 1072 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) 1073 dbgs() << "Formed RefSCC: " << RC << "\n"; 1074 1075 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 1076 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 1077 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 1078 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); 1079 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A); 1080 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B); 1081 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C); 1082 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D); 1083 1084 // Connect the top to the bottom forming a large RefSCC made up just of 1085 // references. 1086 auto MergedRCs = ARC.insertIncomingRefEdge(D, A); 1087 // Make sure we connected the nodes. 1088 EXPECT_NE(D->begin(), D->end()); 1089 EXPECT_EQ(&A, &D->begin()->getNode()); 1090 1091 // Check that we have the dead RCs, but ignore the order. 1092 EXPECT_EQ(3u, MergedRCs.size()); 1093 EXPECT_NE(find(MergedRCs, &BRC), MergedRCs.end()); 1094 EXPECT_NE(find(MergedRCs, &CRC), MergedRCs.end()); 1095 EXPECT_NE(find(MergedRCs, &DRC), MergedRCs.end()); 1096 1097 // Make sure the nodes point to the right place now. 1098 EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); 1099 EXPECT_EQ(&ARC, CG.lookupRefSCC(B)); 1100 EXPECT_EQ(&ARC, CG.lookupRefSCC(C)); 1101 EXPECT_EQ(&ARC, CG.lookupRefSCC(D)); 1102 1103 // And verify the post-order walk reflects the updated structure. 1104 auto I = CG.postorder_ref_scc_begin(), End = CG.postorder_ref_scc_end(); 1105 ASSERT_NE(I, End); 1106 EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I; 1107 EXPECT_EQ(++I, End); 1108 } 1109 1110 TEST(LazyCallGraphTest, InlineAndDeleteFunction) { 1111 LLVMContext Context; 1112 // We want to ensure we can delete nodes from relatively complex graphs and 1113 // so use the diamond of triangles graph defined above. 1114 // 1115 // The ascii diagram is repeated here for easy reference. 1116 // 1117 // d1 | 1118 // / \ | 1119 // d3--d2 | 1120 // / \ | 1121 // b1 c1 | 1122 // / \ / \ | 1123 // b3--b2 c3--c2 | 1124 // \ / | 1125 // a1 | 1126 // / \ | 1127 // a3--a2 | 1128 // 1129 std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles); 1130 LazyCallGraph CG = buildCG(*M); 1131 1132 // Force the graph to be fully expanded. 1133 CG.buildRefSCCs(); 1134 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) 1135 dbgs() << "Formed RefSCC: " << RC << "\n"; 1136 1137 LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1")); 1138 LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2")); 1139 LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3")); 1140 LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1")); 1141 LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2")); 1142 LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3")); 1143 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1")); 1144 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2")); 1145 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3")); 1146 LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1")); 1147 LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2")); 1148 LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3")); 1149 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A1); 1150 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B1); 1151 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C1); 1152 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D1); 1153 ASSERT_EQ(&ARC, CG.lookupRefSCC(A2)); 1154 ASSERT_EQ(&ARC, CG.lookupRefSCC(A3)); 1155 ASSERT_EQ(&BRC, CG.lookupRefSCC(B2)); 1156 ASSERT_EQ(&BRC, CG.lookupRefSCC(B3)); 1157 ASSERT_EQ(&CRC, CG.lookupRefSCC(C2)); 1158 ASSERT_EQ(&CRC, CG.lookupRefSCC(C3)); 1159 ASSERT_EQ(&DRC, CG.lookupRefSCC(D2)); 1160 ASSERT_EQ(&DRC, CG.lookupRefSCC(D3)); 1161 ASSERT_EQ(1, std::distance(D2->begin(), D2->end())); 1162 1163 // Delete d2 from the graph, as if it had been inlined. 1164 // 1165 // d1 | 1166 // / / | 1167 // d3--. | 1168 // / \ | 1169 // b1 c1 | 1170 // / \ / \ | 1171 // b3--b2 c3--c2 | 1172 // \ / | 1173 // a1 | 1174 // / \ | 1175 // a3--a2 | 1176 1177 Function &D2F = D2.getFunction(); 1178 CallInst *C1Call = nullptr, *D1Call = nullptr; 1179 for (User *U : D2F.users()) { 1180 CallInst *CI = dyn_cast<CallInst>(U); 1181 ASSERT_TRUE(CI) << "Expected a call: " << *U; 1182 if (CI->getParent()->getParent() == &C1.getFunction()) { 1183 ASSERT_EQ(nullptr, C1Call) << "Found too many C1 calls: " << *CI; 1184 C1Call = CI; 1185 } else if (CI->getParent()->getParent() == &D1.getFunction()) { 1186 ASSERT_EQ(nullptr, D1Call) << "Found too many D1 calls: " << *CI; 1187 D1Call = CI; 1188 } else { 1189 FAIL() << "Found an unexpected call instruction: " << *CI; 1190 } 1191 } 1192 ASSERT_NE(C1Call, nullptr); 1193 ASSERT_NE(D1Call, nullptr); 1194 ASSERT_EQ(&D2F, C1Call->getCalledFunction()); 1195 ASSERT_EQ(&D2F, D1Call->getCalledFunction()); 1196 C1Call->setCalledFunction(&D3.getFunction()); 1197 D1Call->setCalledFunction(&D3.getFunction()); 1198 ASSERT_EQ(0u, D2F.getNumUses()); 1199 1200 // Insert new edges first. 1201 CRC.insertTrivialCallEdge(C1, D3); 1202 DRC.insertTrivialCallEdge(D1, D3); 1203 1204 // Then remove the old ones. 1205 LazyCallGraph::SCC &DC = *CG.lookupSCC(D2); 1206 auto NewCs = DRC.switchInternalEdgeToRef(D1, D2); 1207 EXPECT_EQ(&DC, CG.lookupSCC(D2)); 1208 EXPECT_EQ(NewCs.end(), std::next(NewCs.begin())); 1209 LazyCallGraph::SCC &NewDC = *NewCs.begin(); 1210 EXPECT_EQ(&NewDC, CG.lookupSCC(D1)); 1211 EXPECT_EQ(&NewDC, CG.lookupSCC(D3)); 1212 auto NewRCs = DRC.removeInternalRefEdge(D1, {&D2}); 1213 ASSERT_EQ(2u, NewRCs.size()); 1214 LazyCallGraph::RefSCC &NewDRC = *NewRCs[0]; 1215 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1)); 1216 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3)); 1217 LazyCallGraph::RefSCC &D2RC = *NewRCs[1]; 1218 EXPECT_EQ(&D2RC, CG.lookupRefSCC(D2)); 1219 EXPECT_FALSE(NewDRC.isParentOf(D2RC)); 1220 EXPECT_TRUE(CRC.isParentOf(D2RC)); 1221 EXPECT_TRUE(CRC.isParentOf(NewDRC)); 1222 EXPECT_TRUE(D2RC.isParentOf(NewDRC)); 1223 CRC.removeOutgoingEdge(C1, D2); 1224 EXPECT_FALSE(CRC.isParentOf(D2RC)); 1225 EXPECT_TRUE(CRC.isParentOf(NewDRC)); 1226 EXPECT_TRUE(D2RC.isParentOf(NewDRC)); 1227 1228 // Now that we've updated the call graph, D2 is dead, so remove it. 1229 CG.removeDeadFunction(D2F); 1230 1231 // Check that the graph still looks the same. 1232 EXPECT_EQ(&ARC, CG.lookupRefSCC(A1)); 1233 EXPECT_EQ(&ARC, CG.lookupRefSCC(A2)); 1234 EXPECT_EQ(&ARC, CG.lookupRefSCC(A3)); 1235 EXPECT_EQ(&BRC, CG.lookupRefSCC(B1)); 1236 EXPECT_EQ(&BRC, CG.lookupRefSCC(B2)); 1237 EXPECT_EQ(&BRC, CG.lookupRefSCC(B3)); 1238 EXPECT_EQ(&CRC, CG.lookupRefSCC(C1)); 1239 EXPECT_EQ(&CRC, CG.lookupRefSCC(C2)); 1240 EXPECT_EQ(&CRC, CG.lookupRefSCC(C3)); 1241 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1)); 1242 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3)); 1243 EXPECT_TRUE(CRC.isParentOf(NewDRC)); 1244 1245 // Verify the post-order walk hasn't changed. 1246 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); 1247 ASSERT_NE(I, E); 1248 EXPECT_EQ(&NewDRC, &*I) << "Actual RefSCC: " << *I; 1249 ASSERT_NE(++I, E); 1250 EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I; 1251 ASSERT_NE(++I, E); 1252 EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I; 1253 ASSERT_NE(++I, E); 1254 EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I; 1255 EXPECT_EQ(++I, E); 1256 } 1257 1258 TEST(LazyCallGraphTest, InternalEdgeMutation) { 1259 LLVMContext Context; 1260 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n" 1261 "entry:\n" 1262 " call void @b()\n" 1263 " ret void\n" 1264 "}\n" 1265 "define void @b() {\n" 1266 "entry:\n" 1267 " call void @c()\n" 1268 " ret void\n" 1269 "}\n" 1270 "define void @c() {\n" 1271 "entry:\n" 1272 " call void @a()\n" 1273 " ret void\n" 1274 "}\n"); 1275 LazyCallGraph CG = buildCG(*M); 1276 1277 // Force the graph to be fully expanded. 1278 CG.buildRefSCCs(); 1279 auto I = CG.postorder_ref_scc_begin(); 1280 LazyCallGraph::RefSCC &RC = *I++; 1281 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 1282 1283 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 1284 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 1285 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 1286 EXPECT_EQ(&RC, CG.lookupRefSCC(A)); 1287 EXPECT_EQ(&RC, CG.lookupRefSCC(B)); 1288 EXPECT_EQ(&RC, CG.lookupRefSCC(C)); 1289 EXPECT_EQ(1, RC.size()); 1290 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(A)); 1291 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(B)); 1292 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(C)); 1293 1294 // Insert an edge from 'a' to 'c'. Nothing changes about the graph. 1295 RC.insertInternalRefEdge(A, C); 1296 EXPECT_EQ(2, std::distance(A->begin(), A->end())); 1297 EXPECT_EQ(&RC, CG.lookupRefSCC(A)); 1298 EXPECT_EQ(&RC, CG.lookupRefSCC(B)); 1299 EXPECT_EQ(&RC, CG.lookupRefSCC(C)); 1300 EXPECT_EQ(1, RC.size()); 1301 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(A)); 1302 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(B)); 1303 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(C)); 1304 1305 // Switch the call edge from 'b' to 'c' to a ref edge. This will break the 1306 // call cycle and cause us to form more SCCs. The RefSCC will remain the same 1307 // though. 1308 auto NewCs = RC.switchInternalEdgeToRef(B, C); 1309 EXPECT_EQ(&RC, CG.lookupRefSCC(A)); 1310 EXPECT_EQ(&RC, CG.lookupRefSCC(B)); 1311 EXPECT_EQ(&RC, CG.lookupRefSCC(C)); 1312 auto J = RC.begin(); 1313 // The SCCs must be in *post-order* which means successors before 1314 // predecessors. At this point we have call edges from C to A and from A to 1315 // B. The only valid postorder is B, A, C. 1316 EXPECT_EQ(&*J++, CG.lookupSCC(B)); 1317 EXPECT_EQ(&*J++, CG.lookupSCC(A)); 1318 EXPECT_EQ(&*J++, CG.lookupSCC(C)); 1319 EXPECT_EQ(RC.end(), J); 1320 // And the returned range must be the slice of this sequence containing new 1321 // SCCs. 1322 EXPECT_EQ(RC.begin(), NewCs.begin()); 1323 EXPECT_EQ(std::prev(RC.end()), NewCs.end()); 1324 1325 // Test turning the ref edge from A to C into a call edge. This will form an 1326 // SCC out of A and C. Since we previously had a call edge from C to A, the 1327 // C SCC should be preserved and have A merged into it while the A SCC should 1328 // be invalidated. 1329 LazyCallGraph::SCC &AC = *CG.lookupSCC(A); 1330 LazyCallGraph::SCC &CC = *CG.lookupSCC(C); 1331 EXPECT_TRUE(RC.switchInternalEdgeToCall(A, C, [&](ArrayRef<LazyCallGraph::SCC *> MergedCs) { 1332 ASSERT_EQ(1u, MergedCs.size()); 1333 EXPECT_EQ(&AC, MergedCs[0]); 1334 })); 1335 EXPECT_EQ(2, CC.size()); 1336 EXPECT_EQ(&CC, CG.lookupSCC(A)); 1337 EXPECT_EQ(&CC, CG.lookupSCC(C)); 1338 J = RC.begin(); 1339 EXPECT_EQ(&*J++, CG.lookupSCC(B)); 1340 EXPECT_EQ(&*J++, CG.lookupSCC(C)); 1341 EXPECT_EQ(RC.end(), J); 1342 } 1343 1344 TEST(LazyCallGraphTest, InternalEdgeRemoval) { 1345 LLVMContext Context; 1346 // A nice fully connected (including self-edges) RefSCC. 1347 std::unique_ptr<Module> M = parseAssembly( 1348 Context, "define void @a(i8** %ptr) {\n" 1349 "entry:\n" 1350 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" 1351 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" 1352 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" 1353 " ret void\n" 1354 "}\n" 1355 "define void @b(i8** %ptr) {\n" 1356 "entry:\n" 1357 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" 1358 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" 1359 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" 1360 " ret void\n" 1361 "}\n" 1362 "define void @c(i8** %ptr) {\n" 1363 "entry:\n" 1364 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" 1365 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" 1366 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" 1367 " ret void\n" 1368 "}\n"); 1369 LazyCallGraph CG = buildCG(*M); 1370 1371 // Force the graph to be fully expanded. 1372 CG.buildRefSCCs(); 1373 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); 1374 LazyCallGraph::RefSCC &RC = *I; 1375 EXPECT_EQ(E, std::next(I)); 1376 1377 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 1378 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 1379 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 1380 EXPECT_EQ(&RC, CG.lookupRefSCC(A)); 1381 EXPECT_EQ(&RC, CG.lookupRefSCC(B)); 1382 EXPECT_EQ(&RC, CG.lookupRefSCC(C)); 1383 1384 // Remove the edge from b -> a, which should leave the 3 functions still in 1385 // a single connected component because of a -> b -> c -> a. 1386 SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs = 1387 RC.removeInternalRefEdge(B, {&A}); 1388 EXPECT_EQ(0u, NewRCs.size()); 1389 EXPECT_EQ(&RC, CG.lookupRefSCC(A)); 1390 EXPECT_EQ(&RC, CG.lookupRefSCC(B)); 1391 EXPECT_EQ(&RC, CG.lookupRefSCC(C)); 1392 auto J = CG.postorder_ref_scc_begin(); 1393 EXPECT_EQ(I, J); 1394 EXPECT_EQ(&RC, &*J); 1395 EXPECT_EQ(E, std::next(J)); 1396 1397 // Increment I before we actually mutate the structure so that it remains 1398 // a valid iterator. 1399 ++I; 1400 1401 // Remove the edge from c -> a, which should leave 'a' in the original RefSCC 1402 // and form a new RefSCC for 'b' and 'c'. 1403 NewRCs = RC.removeInternalRefEdge(C, {&A}); 1404 ASSERT_EQ(2u, NewRCs.size()); 1405 LazyCallGraph::RefSCC &BCRC = *NewRCs[0]; 1406 LazyCallGraph::RefSCC &ARC = *NewRCs[1]; 1407 EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); 1408 EXPECT_EQ(1, std::distance(ARC.begin(), ARC.end())); 1409 EXPECT_EQ(&BCRC, CG.lookupRefSCC(B)); 1410 EXPECT_EQ(&BCRC, CG.lookupRefSCC(C)); 1411 J = CG.postorder_ref_scc_begin(); 1412 EXPECT_NE(I, J); 1413 EXPECT_EQ(&BCRC, &*J); 1414 ++J; 1415 EXPECT_NE(I, J); 1416 EXPECT_EQ(&ARC, &*J); 1417 ++J; 1418 EXPECT_EQ(I, J); 1419 EXPECT_EQ(E, J); 1420 } 1421 1422 TEST(LazyCallGraphTest, InternalMultiEdgeRemoval) { 1423 LLVMContext Context; 1424 // A nice fully connected (including self-edges) RefSCC. 1425 std::unique_ptr<Module> M = parseAssembly( 1426 Context, "define void @a(i8** %ptr) {\n" 1427 "entry:\n" 1428 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" 1429 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" 1430 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" 1431 " ret void\n" 1432 "}\n" 1433 "define void @b(i8** %ptr) {\n" 1434 "entry:\n" 1435 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" 1436 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" 1437 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" 1438 " ret void\n" 1439 "}\n" 1440 "define void @c(i8** %ptr) {\n" 1441 "entry:\n" 1442 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" 1443 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" 1444 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" 1445 " ret void\n" 1446 "}\n"); 1447 LazyCallGraph CG = buildCG(*M); 1448 1449 // Force the graph to be fully expanded. 1450 CG.buildRefSCCs(); 1451 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); 1452 LazyCallGraph::RefSCC &RC = *I; 1453 EXPECT_EQ(E, std::next(I)); 1454 1455 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 1456 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 1457 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 1458 EXPECT_EQ(&RC, CG.lookupRefSCC(A)); 1459 EXPECT_EQ(&RC, CG.lookupRefSCC(B)); 1460 EXPECT_EQ(&RC, CG.lookupRefSCC(C)); 1461 1462 // Increment I before we actually mutate the structure so that it remains 1463 // a valid iterator. 1464 ++I; 1465 1466 // Remove the edges from b -> a and b -> c, leaving b in its own RefSCC. 1467 SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs = 1468 RC.removeInternalRefEdge(B, {&A, &C}); 1469 1470 ASSERT_EQ(2u, NewRCs.size()); 1471 LazyCallGraph::RefSCC &BRC = *NewRCs[0]; 1472 LazyCallGraph::RefSCC &ACRC = *NewRCs[1]; 1473 EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); 1474 EXPECT_EQ(1, std::distance(BRC.begin(), BRC.end())); 1475 EXPECT_EQ(&ACRC, CG.lookupRefSCC(A)); 1476 EXPECT_EQ(&ACRC, CG.lookupRefSCC(C)); 1477 auto J = CG.postorder_ref_scc_begin(); 1478 EXPECT_NE(I, J); 1479 EXPECT_EQ(&BRC, &*J); 1480 ++J; 1481 EXPECT_NE(I, J); 1482 EXPECT_EQ(&ACRC, &*J); 1483 ++J; 1484 EXPECT_EQ(I, J); 1485 EXPECT_EQ(E, J); 1486 } 1487 1488 TEST(LazyCallGraphTest, InternalNoOpEdgeRemoval) { 1489 LLVMContext Context; 1490 // A graph with a single cycle formed both from call and reference edges 1491 // which makes the reference edges trivial to delete. The graph looks like: 1492 // 1493 // Reference edges: a -> b -> c -> a 1494 // Call edges: a -> c -> b -> a 1495 std::unique_ptr<Module> M = parseAssembly( 1496 Context, "define void @a(i8** %ptr) {\n" 1497 "entry:\n" 1498 " call void @b(i8** %ptr)\n" 1499 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" 1500 " ret void\n" 1501 "}\n" 1502 "define void @b(i8** %ptr) {\n" 1503 "entry:\n" 1504 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" 1505 " call void @c(i8** %ptr)\n" 1506 " ret void\n" 1507 "}\n" 1508 "define void @c(i8** %ptr) {\n" 1509 "entry:\n" 1510 " call void @a(i8** %ptr)\n" 1511 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" 1512 " ret void\n" 1513 "}\n"); 1514 LazyCallGraph CG = buildCG(*M); 1515 1516 // Force the graph to be fully expanded. 1517 CG.buildRefSCCs(); 1518 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); 1519 LazyCallGraph::RefSCC &RC = *I; 1520 EXPECT_EQ(E, std::next(I)); 1521 1522 LazyCallGraph::SCC &C = *RC.begin(); 1523 EXPECT_EQ(RC.end(), std::next(RC.begin())); 1524 1525 LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a")); 1526 LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b")); 1527 LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c")); 1528 EXPECT_EQ(&RC, CG.lookupRefSCC(AN)); 1529 EXPECT_EQ(&RC, CG.lookupRefSCC(BN)); 1530 EXPECT_EQ(&RC, CG.lookupRefSCC(CN)); 1531 EXPECT_EQ(&C, CG.lookupSCC(AN)); 1532 EXPECT_EQ(&C, CG.lookupSCC(BN)); 1533 EXPECT_EQ(&C, CG.lookupSCC(CN)); 1534 1535 // Remove the edge from a -> c which doesn't change anything. 1536 SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs = 1537 RC.removeInternalRefEdge(AN, {&CN}); 1538 EXPECT_EQ(0u, NewRCs.size()); 1539 EXPECT_EQ(&RC, CG.lookupRefSCC(AN)); 1540 EXPECT_EQ(&RC, CG.lookupRefSCC(BN)); 1541 EXPECT_EQ(&RC, CG.lookupRefSCC(CN)); 1542 EXPECT_EQ(&C, CG.lookupSCC(AN)); 1543 EXPECT_EQ(&C, CG.lookupSCC(BN)); 1544 EXPECT_EQ(&C, CG.lookupSCC(CN)); 1545 auto J = CG.postorder_ref_scc_begin(); 1546 EXPECT_EQ(I, J); 1547 EXPECT_EQ(&RC, &*J); 1548 EXPECT_EQ(E, std::next(J)); 1549 1550 // Remove the edge from b -> a and c -> b; again this doesn't change 1551 // anything. 1552 NewRCs = RC.removeInternalRefEdge(BN, {&AN}); 1553 NewRCs = RC.removeInternalRefEdge(CN, {&BN}); 1554 EXPECT_EQ(0u, NewRCs.size()); 1555 EXPECT_EQ(&RC, CG.lookupRefSCC(AN)); 1556 EXPECT_EQ(&RC, CG.lookupRefSCC(BN)); 1557 EXPECT_EQ(&RC, CG.lookupRefSCC(CN)); 1558 EXPECT_EQ(&C, CG.lookupSCC(AN)); 1559 EXPECT_EQ(&C, CG.lookupSCC(BN)); 1560 EXPECT_EQ(&C, CG.lookupSCC(CN)); 1561 J = CG.postorder_ref_scc_begin(); 1562 EXPECT_EQ(I, J); 1563 EXPECT_EQ(&RC, &*J); 1564 EXPECT_EQ(E, std::next(J)); 1565 } 1566 1567 TEST(LazyCallGraphTest, InternalCallEdgeToRef) { 1568 LLVMContext Context; 1569 // A nice fully connected (including self-edges) SCC (and RefSCC) 1570 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n" 1571 "entry:\n" 1572 " call void @a()\n" 1573 " call void @b()\n" 1574 " call void @c()\n" 1575 " ret void\n" 1576 "}\n" 1577 "define void @b() {\n" 1578 "entry:\n" 1579 " call void @a()\n" 1580 " call void @b()\n" 1581 " call void @c()\n" 1582 " ret void\n" 1583 "}\n" 1584 "define void @c() {\n" 1585 "entry:\n" 1586 " call void @a()\n" 1587 " call void @b()\n" 1588 " call void @c()\n" 1589 " ret void\n" 1590 "}\n"); 1591 LazyCallGraph CG = buildCG(*M); 1592 1593 // Force the graph to be fully expanded. 1594 CG.buildRefSCCs(); 1595 auto I = CG.postorder_ref_scc_begin(); 1596 LazyCallGraph::RefSCC &RC = *I++; 1597 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 1598 1599 EXPECT_EQ(1, RC.size()); 1600 LazyCallGraph::SCC &AC = *RC.begin(); 1601 1602 LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a")); 1603 LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b")); 1604 LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c")); 1605 EXPECT_EQ(&AC, CG.lookupSCC(AN)); 1606 EXPECT_EQ(&AC, CG.lookupSCC(BN)); 1607 EXPECT_EQ(&AC, CG.lookupSCC(CN)); 1608 1609 // Remove the call edge from b -> a to a ref edge, which should leave the 1610 // 3 functions still in a single connected component because of a -> b -> 1611 // c -> a. 1612 auto NewCs = RC.switchInternalEdgeToRef(BN, AN); 1613 EXPECT_EQ(NewCs.begin(), NewCs.end()); 1614 EXPECT_EQ(1, RC.size()); 1615 EXPECT_EQ(&AC, CG.lookupSCC(AN)); 1616 EXPECT_EQ(&AC, CG.lookupSCC(BN)); 1617 EXPECT_EQ(&AC, CG.lookupSCC(CN)); 1618 1619 // Remove the edge from c -> a, which should leave 'a' in the original SCC 1620 // and form a new SCC for 'b' and 'c'. 1621 NewCs = RC.switchInternalEdgeToRef(CN, AN); 1622 EXPECT_EQ(1, std::distance(NewCs.begin(), NewCs.end())); 1623 EXPECT_EQ(2, RC.size()); 1624 EXPECT_EQ(&AC, CG.lookupSCC(AN)); 1625 LazyCallGraph::SCC &BC = *CG.lookupSCC(BN); 1626 EXPECT_NE(&BC, &AC); 1627 EXPECT_EQ(&BC, CG.lookupSCC(CN)); 1628 auto J = RC.find(AC); 1629 EXPECT_EQ(&AC, &*J); 1630 --J; 1631 EXPECT_EQ(&BC, &*J); 1632 EXPECT_EQ(RC.begin(), J); 1633 EXPECT_EQ(J, NewCs.begin()); 1634 1635 // Remove the edge from c -> b, which should leave 'b' in the original SCC 1636 // and form a new SCC for 'c'. It shouldn't change 'a's SCC. 1637 NewCs = RC.switchInternalEdgeToRef(CN, BN); 1638 EXPECT_EQ(1, std::distance(NewCs.begin(), NewCs.end())); 1639 EXPECT_EQ(3, RC.size()); 1640 EXPECT_EQ(&AC, CG.lookupSCC(AN)); 1641 EXPECT_EQ(&BC, CG.lookupSCC(BN)); 1642 LazyCallGraph::SCC &CC = *CG.lookupSCC(CN); 1643 EXPECT_NE(&CC, &AC); 1644 EXPECT_NE(&CC, &BC); 1645 J = RC.find(AC); 1646 EXPECT_EQ(&AC, &*J); 1647 --J; 1648 EXPECT_EQ(&BC, &*J); 1649 --J; 1650 EXPECT_EQ(&CC, &*J); 1651 EXPECT_EQ(RC.begin(), J); 1652 EXPECT_EQ(J, NewCs.begin()); 1653 } 1654 1655 TEST(LazyCallGraphTest, InternalRefEdgeToCall) { 1656 LLVMContext Context; 1657 // Basic tests for making a ref edge a call. This hits the basics of the 1658 // process only. 1659 std::unique_ptr<Module> M = 1660 parseAssembly(Context, "define void @a() {\n" 1661 "entry:\n" 1662 " call void @b()\n" 1663 " call void @c()\n" 1664 " store void()* @d, void()** undef\n" 1665 " ret void\n" 1666 "}\n" 1667 "define void @b() {\n" 1668 "entry:\n" 1669 " store void()* @c, void()** undef\n" 1670 " call void @d()\n" 1671 " ret void\n" 1672 "}\n" 1673 "define void @c() {\n" 1674 "entry:\n" 1675 " store void()* @b, void()** undef\n" 1676 " call void @d()\n" 1677 " ret void\n" 1678 "}\n" 1679 "define void @d() {\n" 1680 "entry:\n" 1681 " store void()* @a, void()** undef\n" 1682 " ret void\n" 1683 "}\n"); 1684 LazyCallGraph CG = buildCG(*M); 1685 1686 // Force the graph to be fully expanded. 1687 CG.buildRefSCCs(); 1688 auto I = CG.postorder_ref_scc_begin(); 1689 LazyCallGraph::RefSCC &RC = *I++; 1690 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 1691 1692 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 1693 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 1694 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 1695 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); 1696 LazyCallGraph::SCC &AC = *CG.lookupSCC(A); 1697 LazyCallGraph::SCC &BC = *CG.lookupSCC(B); 1698 LazyCallGraph::SCC &CC = *CG.lookupSCC(C); 1699 LazyCallGraph::SCC &DC = *CG.lookupSCC(D); 1700 1701 // Check the initial post-order. Note that B and C could be flipped here (and 1702 // in our mutation) without changing the nature of this test. 1703 ASSERT_EQ(4, RC.size()); 1704 EXPECT_EQ(&DC, &RC[0]); 1705 EXPECT_EQ(&BC, &RC[1]); 1706 EXPECT_EQ(&CC, &RC[2]); 1707 EXPECT_EQ(&AC, &RC[3]); 1708 1709 // Switch the ref edge from A -> D to a call edge. This should have no 1710 // effect as it is already in postorder and no new cycles are formed. 1711 EXPECT_FALSE(RC.switchInternalEdgeToCall(A, D)); 1712 ASSERT_EQ(4, RC.size()); 1713 EXPECT_EQ(&DC, &RC[0]); 1714 EXPECT_EQ(&BC, &RC[1]); 1715 EXPECT_EQ(&CC, &RC[2]); 1716 EXPECT_EQ(&AC, &RC[3]); 1717 1718 // Switch B -> C to a call edge. This doesn't form any new cycles but does 1719 // require reordering the SCCs. 1720 EXPECT_FALSE(RC.switchInternalEdgeToCall(B, C)); 1721 ASSERT_EQ(4, RC.size()); 1722 EXPECT_EQ(&DC, &RC[0]); 1723 EXPECT_EQ(&CC, &RC[1]); 1724 EXPECT_EQ(&BC, &RC[2]); 1725 EXPECT_EQ(&AC, &RC[3]); 1726 1727 // Switch C -> B to a call edge. This forms a cycle and forces merging SCCs. 1728 EXPECT_TRUE(RC.switchInternalEdgeToCall(C, B, [&](ArrayRef<LazyCallGraph::SCC *> MergedCs) { 1729 ASSERT_EQ(1u, MergedCs.size()); 1730 EXPECT_EQ(&CC, MergedCs[0]); 1731 })); 1732 ASSERT_EQ(3, RC.size()); 1733 EXPECT_EQ(&DC, &RC[0]); 1734 EXPECT_EQ(&BC, &RC[1]); 1735 EXPECT_EQ(&AC, &RC[2]); 1736 EXPECT_EQ(2, BC.size()); 1737 EXPECT_EQ(&BC, CG.lookupSCC(B)); 1738 EXPECT_EQ(&BC, CG.lookupSCC(C)); 1739 } 1740 1741 TEST(LazyCallGraphTest, InternalRefEdgeToCallNoCycleInterleaved) { 1742 LLVMContext Context; 1743 // Test for having a post-order prior to changing a ref edge to a call edge 1744 // with SCCs connecting to the source and connecting to the target, but not 1745 // connecting to both, interleaved between the source and target. This 1746 // ensures we correctly partition the range rather than simply moving one or 1747 // the other. 1748 std::unique_ptr<Module> M = 1749 parseAssembly(Context, "define void @a() {\n" 1750 "entry:\n" 1751 " call void @b1()\n" 1752 " call void @c1()\n" 1753 " ret void\n" 1754 "}\n" 1755 "define void @b1() {\n" 1756 "entry:\n" 1757 " call void @c1()\n" 1758 " call void @b2()\n" 1759 " ret void\n" 1760 "}\n" 1761 "define void @c1() {\n" 1762 "entry:\n" 1763 " call void @b2()\n" 1764 " call void @c2()\n" 1765 " ret void\n" 1766 "}\n" 1767 "define void @b2() {\n" 1768 "entry:\n" 1769 " call void @c2()\n" 1770 " call void @b3()\n" 1771 " ret void\n" 1772 "}\n" 1773 "define void @c2() {\n" 1774 "entry:\n" 1775 " call void @b3()\n" 1776 " call void @c3()\n" 1777 " ret void\n" 1778 "}\n" 1779 "define void @b3() {\n" 1780 "entry:\n" 1781 " call void @c3()\n" 1782 " call void @d()\n" 1783 " ret void\n" 1784 "}\n" 1785 "define void @c3() {\n" 1786 "entry:\n" 1787 " store void()* @b1, void()** undef\n" 1788 " call void @d()\n" 1789 " ret void\n" 1790 "}\n" 1791 "define void @d() {\n" 1792 "entry:\n" 1793 " store void()* @a, void()** undef\n" 1794 " ret void\n" 1795 "}\n"); 1796 LazyCallGraph CG = buildCG(*M); 1797 1798 // Force the graph to be fully expanded. 1799 CG.buildRefSCCs(); 1800 auto I = CG.postorder_ref_scc_begin(); 1801 LazyCallGraph::RefSCC &RC = *I++; 1802 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 1803 1804 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 1805 LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1")); 1806 LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2")); 1807 LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3")); 1808 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1")); 1809 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2")); 1810 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3")); 1811 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); 1812 LazyCallGraph::SCC &AC = *CG.lookupSCC(A); 1813 LazyCallGraph::SCC &B1C = *CG.lookupSCC(B1); 1814 LazyCallGraph::SCC &B2C = *CG.lookupSCC(B2); 1815 LazyCallGraph::SCC &B3C = *CG.lookupSCC(B3); 1816 LazyCallGraph::SCC &C1C = *CG.lookupSCC(C1); 1817 LazyCallGraph::SCC &C2C = *CG.lookupSCC(C2); 1818 LazyCallGraph::SCC &C3C = *CG.lookupSCC(C3); 1819 LazyCallGraph::SCC &DC = *CG.lookupSCC(D); 1820 1821 // Several call edges are initially present to force a particual post-order. 1822 // Remove them now, leaving an interleaved post-order pattern. 1823 RC.switchTrivialInternalEdgeToRef(B3, C3); 1824 RC.switchTrivialInternalEdgeToRef(C2, B3); 1825 RC.switchTrivialInternalEdgeToRef(B2, C2); 1826 RC.switchTrivialInternalEdgeToRef(C1, B2); 1827 RC.switchTrivialInternalEdgeToRef(B1, C1); 1828 1829 // Check the initial post-order. We ensure this order with the extra edges 1830 // that are nuked above. 1831 ASSERT_EQ(8, RC.size()); 1832 EXPECT_EQ(&DC, &RC[0]); 1833 EXPECT_EQ(&C3C, &RC[1]); 1834 EXPECT_EQ(&B3C, &RC[2]); 1835 EXPECT_EQ(&C2C, &RC[3]); 1836 EXPECT_EQ(&B2C, &RC[4]); 1837 EXPECT_EQ(&C1C, &RC[5]); 1838 EXPECT_EQ(&B1C, &RC[6]); 1839 EXPECT_EQ(&AC, &RC[7]); 1840 1841 // Switch C3 -> B1 to a call edge. This doesn't form any new cycles but does 1842 // require reordering the SCCs in the face of tricky internal node 1843 // structures. 1844 EXPECT_FALSE(RC.switchInternalEdgeToCall(C3, B1)); 1845 ASSERT_EQ(8, RC.size()); 1846 EXPECT_EQ(&DC, &RC[0]); 1847 EXPECT_EQ(&B3C, &RC[1]); 1848 EXPECT_EQ(&B2C, &RC[2]); 1849 EXPECT_EQ(&B1C, &RC[3]); 1850 EXPECT_EQ(&C3C, &RC[4]); 1851 EXPECT_EQ(&C2C, &RC[5]); 1852 EXPECT_EQ(&C1C, &RC[6]); 1853 EXPECT_EQ(&AC, &RC[7]); 1854 } 1855 1856 TEST(LazyCallGraphTest, InternalRefEdgeToCallBothPartitionAndMerge) { 1857 LLVMContext Context; 1858 // Test for having a postorder where between the source and target are all 1859 // three kinds of other SCCs: 1860 // 1) One connected to the target only that have to be shifted below the 1861 // source. 1862 // 2) One connected to the source only that have to be shifted below the 1863 // target. 1864 // 3) One connected to both source and target that has to remain and get 1865 // merged away. 1866 // 1867 // To achieve this we construct a heavily connected graph to force 1868 // a particular post-order. Then we remove the forcing edges and connect 1869 // a cycle. 1870 // 1871 // Diagram for the graph we want on the left and the graph we use to force 1872 // the ordering on the right. Edges ponit down or right. 1873 // 1874 // A | A | 1875 // / \ | / \ | 1876 // B E | B \ | 1877 // |\ | | |\ | | 1878 // | D | | C-D-E | 1879 // | \| | | \| | 1880 // C F | \ F | 1881 // \ / | \ / | 1882 // G | G | 1883 // 1884 // And we form a cycle by connecting F to B. 1885 std::unique_ptr<Module> M = 1886 parseAssembly(Context, "define void @a() {\n" 1887 "entry:\n" 1888 " call void @b()\n" 1889 " call void @e()\n" 1890 " ret void\n" 1891 "}\n" 1892 "define void @b() {\n" 1893 "entry:\n" 1894 " call void @c()\n" 1895 " call void @d()\n" 1896 " ret void\n" 1897 "}\n" 1898 "define void @c() {\n" 1899 "entry:\n" 1900 " call void @d()\n" 1901 " call void @g()\n" 1902 " ret void\n" 1903 "}\n" 1904 "define void @d() {\n" 1905 "entry:\n" 1906 " call void @e()\n" 1907 " call void @f()\n" 1908 " ret void\n" 1909 "}\n" 1910 "define void @e() {\n" 1911 "entry:\n" 1912 " call void @f()\n" 1913 " ret void\n" 1914 "}\n" 1915 "define void @f() {\n" 1916 "entry:\n" 1917 " store void()* @b, void()** undef\n" 1918 " call void @g()\n" 1919 " ret void\n" 1920 "}\n" 1921 "define void @g() {\n" 1922 "entry:\n" 1923 " store void()* @a, void()** undef\n" 1924 " ret void\n" 1925 "}\n"); 1926 LazyCallGraph CG = buildCG(*M); 1927 1928 // Force the graph to be fully expanded. 1929 CG.buildRefSCCs(); 1930 auto I = CG.postorder_ref_scc_begin(); 1931 LazyCallGraph::RefSCC &RC = *I++; 1932 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 1933 1934 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 1935 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 1936 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 1937 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); 1938 LazyCallGraph::Node &E = *CG.lookup(lookupFunction(*M, "e")); 1939 LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f")); 1940 LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g")); 1941 LazyCallGraph::SCC &AC = *CG.lookupSCC(A); 1942 LazyCallGraph::SCC &BC = *CG.lookupSCC(B); 1943 LazyCallGraph::SCC &CC = *CG.lookupSCC(C); 1944 LazyCallGraph::SCC &DC = *CG.lookupSCC(D); 1945 LazyCallGraph::SCC &EC = *CG.lookupSCC(E); 1946 LazyCallGraph::SCC &FC = *CG.lookupSCC(F); 1947 LazyCallGraph::SCC &GC = *CG.lookupSCC(G); 1948 1949 // Remove the extra edges that were used to force a particular post-order. 1950 RC.switchTrivialInternalEdgeToRef(C, D); 1951 RC.switchTrivialInternalEdgeToRef(D, E); 1952 1953 // Check the initial post-order. We ensure this order with the extra edges 1954 // that are nuked above. 1955 ASSERT_EQ(7, RC.size()); 1956 EXPECT_EQ(&GC, &RC[0]); 1957 EXPECT_EQ(&FC, &RC[1]); 1958 EXPECT_EQ(&EC, &RC[2]); 1959 EXPECT_EQ(&DC, &RC[3]); 1960 EXPECT_EQ(&CC, &RC[4]); 1961 EXPECT_EQ(&BC, &RC[5]); 1962 EXPECT_EQ(&AC, &RC[6]); 1963 1964 // Switch F -> B to a call edge. This merges B, D, and F into a single SCC, 1965 // and has to place the C and E SCCs on either side of it: 1966 // A A | 1967 // / \ / \ | 1968 // B E | E | 1969 // |\ | \ / | 1970 // | D | -> B | 1971 // | \| / \ | 1972 // C F C | | 1973 // \ / \ / | 1974 // G G | 1975 EXPECT_TRUE(RC.switchInternalEdgeToCall( 1976 F, B, [&](ArrayRef<LazyCallGraph::SCC *> MergedCs) { 1977 ASSERT_EQ(2u, MergedCs.size()); 1978 EXPECT_EQ(&FC, MergedCs[0]); 1979 EXPECT_EQ(&DC, MergedCs[1]); 1980 })); 1981 EXPECT_EQ(3, BC.size()); 1982 1983 // And make sure the postorder was updated. 1984 ASSERT_EQ(5, RC.size()); 1985 EXPECT_EQ(&GC, &RC[0]); 1986 EXPECT_EQ(&CC, &RC[1]); 1987 EXPECT_EQ(&BC, &RC[2]); 1988 EXPECT_EQ(&EC, &RC[3]); 1989 EXPECT_EQ(&AC, &RC[4]); 1990 } 1991 1992 // Test for IR containing constants using blockaddress constant expressions. 1993 // These are truly unique constructs: constant expressions with non-constant 1994 // operands. 1995 TEST(LazyCallGraphTest, HandleBlockAddress) { 1996 LLVMContext Context; 1997 std::unique_ptr<Module> M = 1998 parseAssembly(Context, "define void @f() {\n" 1999 "entry:\n" 2000 " ret void\n" 2001 "bb:\n" 2002 " unreachable\n" 2003 "}\n" 2004 "define void @g(i8** %ptr) {\n" 2005 "entry:\n" 2006 " store i8* blockaddress(@f, %bb), i8** %ptr\n" 2007 " ret void\n" 2008 "}\n"); 2009 LazyCallGraph CG = buildCG(*M); 2010 2011 CG.buildRefSCCs(); 2012 auto I = CG.postorder_ref_scc_begin(); 2013 LazyCallGraph::RefSCC &FRC = *I++; 2014 LazyCallGraph::RefSCC &GRC = *I++; 2015 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2016 2017 LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f")); 2018 LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g")); 2019 EXPECT_EQ(&FRC, CG.lookupRefSCC(F)); 2020 EXPECT_EQ(&GRC, CG.lookupRefSCC(G)); 2021 EXPECT_TRUE(GRC.isParentOf(FRC)); 2022 } 2023 2024 // Test that a blockaddress that refers to itself creates no new RefSCC 2025 // connections. https://bugs.llvm.org/show_bug.cgi?id=40722 2026 TEST(LazyCallGraphTest, HandleBlockAddress2) { 2027 LLVMContext Context; 2028 std::unique_ptr<Module> M = 2029 parseAssembly(Context, "define void @f() {\n" 2030 " ret void\n" 2031 "}\n" 2032 "define void @g(i8** %ptr) {\n" 2033 "bb:\n" 2034 " store i8* blockaddress(@g, %bb), i8** %ptr\n" 2035 " ret void\n" 2036 "}\n"); 2037 LazyCallGraph CG = buildCG(*M); 2038 2039 CG.buildRefSCCs(); 2040 auto I = CG.postorder_ref_scc_begin(); 2041 LazyCallGraph::RefSCC &GRC = *I++; 2042 LazyCallGraph::RefSCC &FRC = *I++; 2043 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2044 2045 LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f")); 2046 LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g")); 2047 EXPECT_EQ(&FRC, CG.lookupRefSCC(F)); 2048 EXPECT_EQ(&GRC, CG.lookupRefSCC(G)); 2049 EXPECT_FALSE(GRC.isParentOf(FRC)); 2050 EXPECT_FALSE(FRC.isParentOf(GRC)); 2051 } 2052 2053 TEST(LazyCallGraphTest, ReplaceNodeFunction) { 2054 LLVMContext Context; 2055 // A graph with several different kinds of edges pointing at a particular 2056 // function. 2057 std::unique_ptr<Module> M = 2058 parseAssembly(Context, 2059 "define void @a(i8** %ptr) {\n" 2060 "entry:\n" 2061 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n" 2062 " ret void\n" 2063 "}\n" 2064 "define void @b(i8** %ptr) {\n" 2065 "entry:\n" 2066 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n" 2067 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n" 2068 " call void @d(i8** %ptr)" 2069 " ret void\n" 2070 "}\n" 2071 "define void @c(i8** %ptr) {\n" 2072 "entry:\n" 2073 " call void @d(i8** %ptr)" 2074 " call void @d(i8** %ptr)" 2075 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n" 2076 " ret void\n" 2077 "}\n" 2078 "define void @d(i8** %ptr) {\n" 2079 "entry:\n" 2080 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" 2081 " call void @c(i8** %ptr)" 2082 " call void @d(i8** %ptr)" 2083 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n" 2084 " ret void\n" 2085 "}\n"); 2086 LazyCallGraph CG = buildCG(*M); 2087 2088 // Force the graph to be fully expanded. 2089 CG.buildRefSCCs(); 2090 auto I = CG.postorder_ref_scc_begin(); 2091 LazyCallGraph::RefSCC &RC1 = *I++; 2092 LazyCallGraph::RefSCC &RC2 = *I++; 2093 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2094 2095 ASSERT_EQ(2, RC1.size()); 2096 LazyCallGraph::SCC &C1 = RC1[0]; 2097 LazyCallGraph::SCC &C2 = RC1[1]; 2098 2099 LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a")); 2100 LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b")); 2101 LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c")); 2102 LazyCallGraph::Node &DN = *CG.lookup(lookupFunction(*M, "d")); 2103 EXPECT_EQ(&C1, CG.lookupSCC(DN)); 2104 EXPECT_EQ(&C1, CG.lookupSCC(CN)); 2105 EXPECT_EQ(&C2, CG.lookupSCC(BN)); 2106 EXPECT_EQ(&RC1, CG.lookupRefSCC(DN)); 2107 EXPECT_EQ(&RC1, CG.lookupRefSCC(CN)); 2108 EXPECT_EQ(&RC1, CG.lookupRefSCC(BN)); 2109 EXPECT_EQ(&RC2, CG.lookupRefSCC(AN)); 2110 2111 // Now we need to build a new function 'e' with the same signature as 'd'. 2112 Function &D = DN.getFunction(); 2113 Function &E = *Function::Create(D.getFunctionType(), D.getLinkage(), "e"); 2114 D.getParent()->getFunctionList().insert(D.getIterator(), &E); 2115 2116 // Change each use of 'd' to use 'e'. This is particularly easy as they have 2117 // the same type. 2118 D.replaceAllUsesWith(&E); 2119 2120 // Splice the body of the old function into the new one. 2121 E.getBasicBlockList().splice(E.begin(), D.getBasicBlockList()); 2122 // And fix up the one argument. 2123 D.arg_begin()->replaceAllUsesWith(&*E.arg_begin()); 2124 E.arg_begin()->takeName(&*D.arg_begin()); 2125 2126 // Now replace the function in the graph. 2127 RC1.replaceNodeFunction(DN, E); 2128 2129 EXPECT_EQ(&E, &DN.getFunction()); 2130 EXPECT_EQ(&DN, &(*CN)[DN].getNode()); 2131 EXPECT_EQ(&DN, &(*BN)[DN].getNode()); 2132 } 2133 2134 TEST(LazyCallGraphTest, RemoveFunctionWithSpurriousRef) { 2135 LLVMContext Context; 2136 // A graph with a couple of RefSCCs. 2137 std::unique_ptr<Module> M = 2138 parseAssembly(Context, 2139 "define void @a(i8** %ptr) {\n" 2140 "entry:\n" 2141 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n" 2142 " ret void\n" 2143 "}\n" 2144 "define void @b(i8** %ptr) {\n" 2145 "entry:\n" 2146 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" 2147 " ret void\n" 2148 "}\n" 2149 "define void @c(i8** %ptr) {\n" 2150 "entry:\n" 2151 " call void @d(i8** %ptr)" 2152 " ret void\n" 2153 "}\n" 2154 "define void @d(i8** %ptr) {\n" 2155 "entry:\n" 2156 " call void @c(i8** %ptr)" 2157 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" 2158 " ret void\n" 2159 "}\n" 2160 "define void @dead() {\n" 2161 "entry:\n" 2162 " ret void\n" 2163 "}\n"); 2164 LazyCallGraph CG = buildCG(*M); 2165 2166 // Insert spurious ref edges. 2167 LazyCallGraph::Node &AN = CG.get(lookupFunction(*M, "a")); 2168 LazyCallGraph::Node &BN = CG.get(lookupFunction(*M, "b")); 2169 LazyCallGraph::Node &CN = CG.get(lookupFunction(*M, "c")); 2170 LazyCallGraph::Node &DN = CG.get(lookupFunction(*M, "d")); 2171 LazyCallGraph::Node &DeadN = CG.get(lookupFunction(*M, "dead")); 2172 AN.populate(); 2173 BN.populate(); 2174 CN.populate(); 2175 DN.populate(); 2176 DeadN.populate(); 2177 CG.insertEdge(AN, DeadN, LazyCallGraph::Edge::Ref); 2178 CG.insertEdge(BN, DeadN, LazyCallGraph::Edge::Ref); 2179 CG.insertEdge(CN, DeadN, LazyCallGraph::Edge::Ref); 2180 CG.insertEdge(DN, DeadN, LazyCallGraph::Edge::Ref); 2181 2182 // Force the graph to be fully expanded. 2183 CG.buildRefSCCs(); 2184 auto I = CG.postorder_ref_scc_begin(); 2185 LazyCallGraph::RefSCC &DeadRC = *I++; 2186 LazyCallGraph::RefSCC &RC1 = *I++; 2187 LazyCallGraph::RefSCC &RC2 = *I++; 2188 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2189 2190 ASSERT_EQ(2, RC1.size()); 2191 LazyCallGraph::SCC &C1 = RC1[0]; 2192 LazyCallGraph::SCC &C2 = RC1[1]; 2193 2194 EXPECT_EQ(&DeadRC, CG.lookupRefSCC(DeadN)); 2195 EXPECT_EQ(&C1, CG.lookupSCC(DN)); 2196 EXPECT_EQ(&C1, CG.lookupSCC(CN)); 2197 EXPECT_EQ(&C2, CG.lookupSCC(BN)); 2198 EXPECT_EQ(&RC1, CG.lookupRefSCC(DN)); 2199 EXPECT_EQ(&RC1, CG.lookupRefSCC(CN)); 2200 EXPECT_EQ(&RC1, CG.lookupRefSCC(BN)); 2201 EXPECT_EQ(&RC2, CG.lookupRefSCC(AN)); 2202 2203 // Now delete 'dead'. There are no uses of this function but there are 2204 // spurious references. 2205 CG.removeDeadFunction(DeadN.getFunction()); 2206 2207 // The only observable change should be that the RefSCC is gone from the 2208 // postorder sequence. 2209 I = CG.postorder_ref_scc_begin(); 2210 EXPECT_EQ(&RC1, &*I++); 2211 EXPECT_EQ(&RC2, &*I++); 2212 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2213 } 2214 2215 TEST(LazyCallGraphTest, AddNewFunctionIntoRefSCC) { 2216 LLVMContext Context; 2217 // Build and populate a graph composed of a single, self-referential node. 2218 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n" 2219 "entry:\n" 2220 " call void @f()\n" 2221 " ret void\n" 2222 "}\n"); 2223 LazyCallGraph CG = buildCG(*M); 2224 CG.buildRefSCCs(); 2225 2226 // At this point 'f' is in the call graph. 2227 auto &F = lookupFunction(*M, "f"); 2228 LazyCallGraph::Node *FN = CG.lookup(F); 2229 EXPECT_NE(FN, nullptr); 2230 2231 // And it has an SCC, of course. 2232 auto *FSCC = CG.lookupSCC(*FN); 2233 EXPECT_NE(FSCC, nullptr); 2234 2235 // Now, create a new function 'g'. 2236 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(), 2237 F.getAddressSpace(), "g", F.getParent()); 2238 BasicBlock::Create(F.getParent()->getContext(), "entry", G); 2239 2240 // Instruct the LazyCallGraph to create a new node for 'g', within the same 2241 // RefSCC as 'f', but in a separate SCC. 2242 CG.addNewFunctionIntoRefSCC(*G, FSCC->getOuterRefSCC()); 2243 2244 // 'g' should now be in the call graph. 2245 LazyCallGraph::Node *GN = CG.lookup(*G); 2246 EXPECT_NE(GN, nullptr); 2247 // 'g' should have an SCC, composed of the singular node 'g'. 2248 // ('f' should not be included in the 'g' SCC.) 2249 LazyCallGraph::SCC *GSCC = CG.lookupSCC(*GN); 2250 EXPECT_NE(GSCC, nullptr); 2251 EXPECT_EQ(GSCC->size(), 1); 2252 EXPECT_NE(GSCC, FSCC); 2253 // 'g' and 'f' should be part of the same RefSCC. 2254 EXPECT_EQ(&GSCC->getOuterRefSCC(), &FSCC->getOuterRefSCC()); 2255 } 2256 } 2257