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