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