1 //===- LazyCallGraphTest.cpp - Unit tests for the lazy CG analysis --------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "llvm/Analysis/LazyCallGraph.h" 10 #include "llvm/AsmParser/Parser.h" 11 #include "llvm/IR/Function.h" 12 #include "llvm/IR/Instructions.h" 13 #include "llvm/IR/LLVMContext.h" 14 #include "llvm/IR/Module.h" 15 #include "llvm/IR/Verifier.h" 16 #include "llvm/Support/ErrorHandling.h" 17 #include "llvm/Support/SourceMgr.h" 18 #include "llvm/TargetParser/Triple.h" 19 #include "gtest/gtest.h" 20 #include <memory> 21 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(ErrMsg.c_str()); 38 39 return M; 40 } 41 42 /* 43 IR forming a call graph with a diamond of triangle-shaped SCCs: 44 45 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.removeInternalRefEdges({{&D1, &D2}}); 1173 ASSERT_EQ(2u, NewRCs.size()); 1174 LazyCallGraph::RefSCC &NewDRC = *NewRCs[0]; 1175 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1)); 1176 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3)); 1177 LazyCallGraph::RefSCC &D2RC = *NewRCs[1]; 1178 EXPECT_EQ(&D2RC, CG.lookupRefSCC(D2)); 1179 EXPECT_FALSE(NewDRC.isParentOf(D2RC)); 1180 EXPECT_TRUE(CRC.isParentOf(D2RC)); 1181 EXPECT_TRUE(CRC.isParentOf(NewDRC)); 1182 EXPECT_TRUE(D2RC.isParentOf(NewDRC)); 1183 CRC.removeOutgoingEdge(C1, D2); 1184 EXPECT_FALSE(CRC.isParentOf(D2RC)); 1185 EXPECT_TRUE(CRC.isParentOf(NewDRC)); 1186 EXPECT_TRUE(D2RC.isParentOf(NewDRC)); 1187 1188 // Now that we've updated the call graph, D2 is dead, so remove it. 1189 CG.markDeadFunction(D2F); 1190 CG.removeDeadFunctions({&D2F}); 1191 1192 // Check that the graph still looks the same. 1193 EXPECT_EQ(&ARC, CG.lookupRefSCC(A1)); 1194 EXPECT_EQ(&ARC, CG.lookupRefSCC(A2)); 1195 EXPECT_EQ(&ARC, CG.lookupRefSCC(A3)); 1196 EXPECT_EQ(&BRC, CG.lookupRefSCC(B1)); 1197 EXPECT_EQ(&BRC, CG.lookupRefSCC(B2)); 1198 EXPECT_EQ(&BRC, CG.lookupRefSCC(B3)); 1199 EXPECT_EQ(&CRC, CG.lookupRefSCC(C1)); 1200 EXPECT_EQ(&CRC, CG.lookupRefSCC(C2)); 1201 EXPECT_EQ(&CRC, CG.lookupRefSCC(C3)); 1202 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1)); 1203 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3)); 1204 EXPECT_TRUE(CRC.isParentOf(NewDRC)); 1205 1206 // Verify the post-order walk hasn't changed. 1207 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); 1208 ASSERT_NE(I, E); 1209 EXPECT_EQ(&NewDRC, &*I) << "Actual RefSCC: " << *I; 1210 ASSERT_NE(++I, E); 1211 EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I; 1212 ASSERT_NE(++I, E); 1213 EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I; 1214 ASSERT_NE(++I, E); 1215 EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I; 1216 EXPECT_EQ(++I, E); 1217 } 1218 1219 TEST(LazyCallGraphTest, InternalEdgeMutation) { 1220 LLVMContext Context; 1221 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n" 1222 "entry:\n" 1223 " call void @b()\n" 1224 " ret void\n" 1225 "}\n" 1226 "define void @b() {\n" 1227 "entry:\n" 1228 " call void @c()\n" 1229 " ret void\n" 1230 "}\n" 1231 "define void @c() {\n" 1232 "entry:\n" 1233 " call void @a()\n" 1234 " ret void\n" 1235 "}\n"); 1236 LazyCallGraph CG = buildCG(*M); 1237 1238 // Force the graph to be fully expanded. 1239 CG.buildRefSCCs(); 1240 auto I = CG.postorder_ref_scc_begin(); 1241 LazyCallGraph::RefSCC &RC = *I++; 1242 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 1243 1244 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 1245 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 1246 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 1247 EXPECT_EQ(&RC, CG.lookupRefSCC(A)); 1248 EXPECT_EQ(&RC, CG.lookupRefSCC(B)); 1249 EXPECT_EQ(&RC, CG.lookupRefSCC(C)); 1250 EXPECT_EQ(1, RC.size()); 1251 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(A)); 1252 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(B)); 1253 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(C)); 1254 1255 // Insert an edge from 'a' to 'c'. Nothing changes about the graph. 1256 RC.insertInternalRefEdge(A, C); 1257 EXPECT_EQ(2, std::distance(A->begin(), A->end())); 1258 EXPECT_EQ(&RC, CG.lookupRefSCC(A)); 1259 EXPECT_EQ(&RC, CG.lookupRefSCC(B)); 1260 EXPECT_EQ(&RC, CG.lookupRefSCC(C)); 1261 EXPECT_EQ(1, RC.size()); 1262 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(A)); 1263 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(B)); 1264 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(C)); 1265 1266 // Switch the call edge from 'b' to 'c' to a ref edge. This will break the 1267 // call cycle and cause us to form more SCCs. The RefSCC will remain the same 1268 // though. 1269 auto NewCs = RC.switchInternalEdgeToRef(B, C); 1270 EXPECT_EQ(&RC, CG.lookupRefSCC(A)); 1271 EXPECT_EQ(&RC, CG.lookupRefSCC(B)); 1272 EXPECT_EQ(&RC, CG.lookupRefSCC(C)); 1273 auto J = RC.begin(); 1274 // The SCCs must be in *post-order* which means successors before 1275 // predecessors. At this point we have call edges from C to A and from A to 1276 // B. The only valid postorder is B, A, C. 1277 EXPECT_EQ(&*J++, CG.lookupSCC(B)); 1278 EXPECT_EQ(&*J++, CG.lookupSCC(A)); 1279 EXPECT_EQ(&*J++, CG.lookupSCC(C)); 1280 EXPECT_EQ(RC.end(), J); 1281 // And the returned range must be the slice of this sequence containing new 1282 // SCCs. 1283 EXPECT_EQ(RC.begin(), NewCs.begin()); 1284 EXPECT_EQ(std::prev(RC.end()), NewCs.end()); 1285 1286 // Test turning the ref edge from A to C into a call edge. This will form an 1287 // SCC out of A and C. Since we previously had a call edge from C to A, the 1288 // C SCC should be preserved and have A merged into it while the A SCC should 1289 // be invalidated. 1290 LazyCallGraph::SCC &AC = *CG.lookupSCC(A); 1291 LazyCallGraph::SCC &CC = *CG.lookupSCC(C); 1292 EXPECT_TRUE(RC.switchInternalEdgeToCall(A, C, [&](ArrayRef<LazyCallGraph::SCC *> MergedCs) { 1293 ASSERT_EQ(1u, MergedCs.size()); 1294 EXPECT_EQ(&AC, MergedCs[0]); 1295 })); 1296 EXPECT_EQ(2, CC.size()); 1297 EXPECT_EQ(&CC, CG.lookupSCC(A)); 1298 EXPECT_EQ(&CC, CG.lookupSCC(C)); 1299 J = RC.begin(); 1300 EXPECT_EQ(&*J++, CG.lookupSCC(B)); 1301 EXPECT_EQ(&*J++, CG.lookupSCC(C)); 1302 EXPECT_EQ(RC.end(), J); 1303 } 1304 1305 TEST(LazyCallGraphTest, InternalEdgeRemoval) { 1306 LLVMContext Context; 1307 // A nice fully connected (including self-edges) RefSCC. 1308 std::unique_ptr<Module> M = parseAssembly( 1309 Context, "define void @a(i8** %ptr) {\n" 1310 "entry:\n" 1311 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" 1312 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" 1313 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" 1314 " ret void\n" 1315 "}\n" 1316 "define void @b(i8** %ptr) {\n" 1317 "entry:\n" 1318 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" 1319 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" 1320 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" 1321 " ret void\n" 1322 "}\n" 1323 "define void @c(i8** %ptr) {\n" 1324 "entry:\n" 1325 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" 1326 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" 1327 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" 1328 " ret void\n" 1329 "}\n"); 1330 LazyCallGraph CG = buildCG(*M); 1331 1332 // Force the graph to be fully expanded. 1333 CG.buildRefSCCs(); 1334 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); 1335 LazyCallGraph::RefSCC &RC = *I; 1336 EXPECT_EQ(E, std::next(I)); 1337 1338 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 1339 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 1340 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 1341 EXPECT_EQ(&RC, CG.lookupRefSCC(A)); 1342 EXPECT_EQ(&RC, CG.lookupRefSCC(B)); 1343 EXPECT_EQ(&RC, CG.lookupRefSCC(C)); 1344 1345 // Remove the edge from b -> a, which should leave the 3 functions still in 1346 // a single connected component because of a -> b -> c -> a. 1347 SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs = 1348 RC.removeInternalRefEdges({{&B, &A}}); 1349 EXPECT_EQ(0u, NewRCs.size()); 1350 EXPECT_EQ(&RC, CG.lookupRefSCC(A)); 1351 EXPECT_EQ(&RC, CG.lookupRefSCC(B)); 1352 EXPECT_EQ(&RC, CG.lookupRefSCC(C)); 1353 auto J = CG.postorder_ref_scc_begin(); 1354 EXPECT_EQ(I, J); 1355 EXPECT_EQ(&RC, &*J); 1356 EXPECT_EQ(E, std::next(J)); 1357 1358 // Increment I before we actually mutate the structure so that it remains 1359 // a valid iterator. 1360 ++I; 1361 1362 // Remove the edge from c -> a, which should leave 'a' in the original RefSCC 1363 // and form a new RefSCC for 'b' and 'c'. 1364 NewRCs = RC.removeInternalRefEdges({{&C, &A}}); 1365 ASSERT_EQ(2u, NewRCs.size()); 1366 LazyCallGraph::RefSCC &BCRC = *NewRCs[0]; 1367 LazyCallGraph::RefSCC &ARC = *NewRCs[1]; 1368 EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); 1369 EXPECT_EQ(1, std::distance(ARC.begin(), ARC.end())); 1370 EXPECT_EQ(&BCRC, CG.lookupRefSCC(B)); 1371 EXPECT_EQ(&BCRC, CG.lookupRefSCC(C)); 1372 J = CG.postorder_ref_scc_begin(); 1373 EXPECT_NE(I, J); 1374 EXPECT_EQ(&BCRC, &*J); 1375 ++J; 1376 EXPECT_NE(I, J); 1377 EXPECT_EQ(&ARC, &*J); 1378 ++J; 1379 EXPECT_EQ(I, J); 1380 EXPECT_EQ(E, J); 1381 } 1382 1383 TEST(LazyCallGraphTest, InternalMultiEdgeRemoval) { 1384 LLVMContext Context; 1385 // A nice fully connected (including self-edges) RefSCC. 1386 std::unique_ptr<Module> M = parseAssembly( 1387 Context, "define void @a(i8** %ptr) {\n" 1388 "entry:\n" 1389 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" 1390 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" 1391 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" 1392 " ret void\n" 1393 "}\n" 1394 "define void @b(i8** %ptr) {\n" 1395 "entry:\n" 1396 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" 1397 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" 1398 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" 1399 " ret void\n" 1400 "}\n" 1401 "define void @c(i8** %ptr) {\n" 1402 "entry:\n" 1403 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" 1404 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" 1405 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" 1406 " ret void\n" 1407 "}\n"); 1408 LazyCallGraph CG = buildCG(*M); 1409 1410 // Force the graph to be fully expanded. 1411 CG.buildRefSCCs(); 1412 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); 1413 LazyCallGraph::RefSCC &RC = *I; 1414 EXPECT_EQ(E, std::next(I)); 1415 1416 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 1417 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 1418 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 1419 EXPECT_EQ(&RC, CG.lookupRefSCC(A)); 1420 EXPECT_EQ(&RC, CG.lookupRefSCC(B)); 1421 EXPECT_EQ(&RC, CG.lookupRefSCC(C)); 1422 1423 // Increment I before we actually mutate the structure so that it remains 1424 // a valid iterator. 1425 ++I; 1426 1427 // Remove the edges from b -> a and b -> c, leaving b in its own RefSCC. 1428 SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs = 1429 RC.removeInternalRefEdges({{&B, &A}, {&B, &C}}); 1430 1431 ASSERT_EQ(2u, NewRCs.size()); 1432 LazyCallGraph::RefSCC &BRC = *NewRCs[0]; 1433 LazyCallGraph::RefSCC &ACRC = *NewRCs[1]; 1434 EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); 1435 EXPECT_EQ(1, std::distance(BRC.begin(), BRC.end())); 1436 EXPECT_EQ(&ACRC, CG.lookupRefSCC(A)); 1437 EXPECT_EQ(&ACRC, CG.lookupRefSCC(C)); 1438 auto J = CG.postorder_ref_scc_begin(); 1439 EXPECT_NE(I, J); 1440 EXPECT_EQ(&BRC, &*J); 1441 ++J; 1442 EXPECT_NE(I, J); 1443 EXPECT_EQ(&ACRC, &*J); 1444 ++J; 1445 EXPECT_EQ(I, J); 1446 EXPECT_EQ(E, J); 1447 } 1448 1449 TEST(LazyCallGraphTest, InternalNoOpEdgeRemoval) { 1450 LLVMContext Context; 1451 // A graph with a single cycle formed both from call and reference edges 1452 // which makes the reference edges trivial to delete. The graph looks like: 1453 // 1454 // Reference edges: a -> b -> c -> a 1455 // Call edges: a -> c -> b -> a 1456 std::unique_ptr<Module> M = parseAssembly( 1457 Context, "define void @a(i8** %ptr) {\n" 1458 "entry:\n" 1459 " call void @b(i8** %ptr)\n" 1460 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" 1461 " ret void\n" 1462 "}\n" 1463 "define void @b(i8** %ptr) {\n" 1464 "entry:\n" 1465 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" 1466 " call void @c(i8** %ptr)\n" 1467 " ret void\n" 1468 "}\n" 1469 "define void @c(i8** %ptr) {\n" 1470 "entry:\n" 1471 " call void @a(i8** %ptr)\n" 1472 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" 1473 " ret void\n" 1474 "}\n"); 1475 LazyCallGraph CG = buildCG(*M); 1476 1477 // Force the graph to be fully expanded. 1478 CG.buildRefSCCs(); 1479 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); 1480 LazyCallGraph::RefSCC &RC = *I; 1481 EXPECT_EQ(E, std::next(I)); 1482 1483 LazyCallGraph::SCC &C = *RC.begin(); 1484 EXPECT_EQ(RC.end(), std::next(RC.begin())); 1485 1486 LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a")); 1487 LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b")); 1488 LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c")); 1489 EXPECT_EQ(&RC, CG.lookupRefSCC(AN)); 1490 EXPECT_EQ(&RC, CG.lookupRefSCC(BN)); 1491 EXPECT_EQ(&RC, CG.lookupRefSCC(CN)); 1492 EXPECT_EQ(&C, CG.lookupSCC(AN)); 1493 EXPECT_EQ(&C, CG.lookupSCC(BN)); 1494 EXPECT_EQ(&C, CG.lookupSCC(CN)); 1495 1496 // Remove the edge from a -> c which doesn't change anything. 1497 SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs = 1498 RC.removeInternalRefEdges({{&AN, &CN}}); 1499 EXPECT_EQ(0u, NewRCs.size()); 1500 EXPECT_EQ(&RC, CG.lookupRefSCC(AN)); 1501 EXPECT_EQ(&RC, CG.lookupRefSCC(BN)); 1502 EXPECT_EQ(&RC, CG.lookupRefSCC(CN)); 1503 EXPECT_EQ(&C, CG.lookupSCC(AN)); 1504 EXPECT_EQ(&C, CG.lookupSCC(BN)); 1505 EXPECT_EQ(&C, CG.lookupSCC(CN)); 1506 auto J = CG.postorder_ref_scc_begin(); 1507 EXPECT_EQ(I, J); 1508 EXPECT_EQ(&RC, &*J); 1509 EXPECT_EQ(E, std::next(J)); 1510 1511 // Remove the edge from b -> a and c -> b; again this doesn't change 1512 // anything. 1513 NewRCs = RC.removeInternalRefEdges({{&BN, &AN}}); 1514 NewRCs = RC.removeInternalRefEdges({{&CN, &BN}}); 1515 EXPECT_EQ(0u, NewRCs.size()); 1516 EXPECT_EQ(&RC, CG.lookupRefSCC(AN)); 1517 EXPECT_EQ(&RC, CG.lookupRefSCC(BN)); 1518 EXPECT_EQ(&RC, CG.lookupRefSCC(CN)); 1519 EXPECT_EQ(&C, CG.lookupSCC(AN)); 1520 EXPECT_EQ(&C, CG.lookupSCC(BN)); 1521 EXPECT_EQ(&C, CG.lookupSCC(CN)); 1522 J = CG.postorder_ref_scc_begin(); 1523 EXPECT_EQ(I, J); 1524 EXPECT_EQ(&RC, &*J); 1525 EXPECT_EQ(E, std::next(J)); 1526 } 1527 1528 TEST(LazyCallGraphTest, InternalCallEdgeToRef) { 1529 LLVMContext Context; 1530 // A nice fully connected (including self-edges) SCC (and RefSCC) 1531 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n" 1532 "entry:\n" 1533 " call void @a()\n" 1534 " call void @b()\n" 1535 " call void @c()\n" 1536 " ret void\n" 1537 "}\n" 1538 "define void @b() {\n" 1539 "entry:\n" 1540 " call void @a()\n" 1541 " call void @b()\n" 1542 " call void @c()\n" 1543 " ret void\n" 1544 "}\n" 1545 "define void @c() {\n" 1546 "entry:\n" 1547 " call void @a()\n" 1548 " call void @b()\n" 1549 " call void @c()\n" 1550 " ret void\n" 1551 "}\n"); 1552 LazyCallGraph CG = buildCG(*M); 1553 1554 // Force the graph to be fully expanded. 1555 CG.buildRefSCCs(); 1556 auto I = CG.postorder_ref_scc_begin(); 1557 LazyCallGraph::RefSCC &RC = *I++; 1558 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 1559 1560 EXPECT_EQ(1, RC.size()); 1561 LazyCallGraph::SCC &AC = *RC.begin(); 1562 1563 LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a")); 1564 LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b")); 1565 LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c")); 1566 EXPECT_EQ(&AC, CG.lookupSCC(AN)); 1567 EXPECT_EQ(&AC, CG.lookupSCC(BN)); 1568 EXPECT_EQ(&AC, CG.lookupSCC(CN)); 1569 1570 // Remove the call edge from b -> a to a ref edge, which should leave the 1571 // 3 functions still in a single connected component because of a -> b -> 1572 // c -> a. 1573 auto NewCs = RC.switchInternalEdgeToRef(BN, AN); 1574 EXPECT_EQ(NewCs.begin(), NewCs.end()); 1575 EXPECT_EQ(1, RC.size()); 1576 EXPECT_EQ(&AC, CG.lookupSCC(AN)); 1577 EXPECT_EQ(&AC, CG.lookupSCC(BN)); 1578 EXPECT_EQ(&AC, CG.lookupSCC(CN)); 1579 1580 // Remove the edge from c -> a, which should leave 'a' in the original SCC 1581 // and form a new SCC for 'b' and 'c'. 1582 NewCs = RC.switchInternalEdgeToRef(CN, AN); 1583 EXPECT_EQ(1, std::distance(NewCs.begin(), NewCs.end())); 1584 EXPECT_EQ(2, RC.size()); 1585 EXPECT_EQ(&AC, CG.lookupSCC(AN)); 1586 LazyCallGraph::SCC &BC = *CG.lookupSCC(BN); 1587 EXPECT_NE(&BC, &AC); 1588 EXPECT_EQ(&BC, CG.lookupSCC(CN)); 1589 auto J = RC.find(AC); 1590 EXPECT_EQ(&AC, &*J); 1591 --J; 1592 EXPECT_EQ(&BC, &*J); 1593 EXPECT_EQ(RC.begin(), J); 1594 EXPECT_EQ(J, NewCs.begin()); 1595 1596 // Remove the edge from c -> b, which should leave 'b' in the original SCC 1597 // and form a new SCC for 'c'. It shouldn't change 'a's SCC. 1598 NewCs = RC.switchInternalEdgeToRef(CN, BN); 1599 EXPECT_EQ(1, std::distance(NewCs.begin(), NewCs.end())); 1600 EXPECT_EQ(3, RC.size()); 1601 EXPECT_EQ(&AC, CG.lookupSCC(AN)); 1602 EXPECT_EQ(&BC, CG.lookupSCC(BN)); 1603 LazyCallGraph::SCC &CC = *CG.lookupSCC(CN); 1604 EXPECT_NE(&CC, &AC); 1605 EXPECT_NE(&CC, &BC); 1606 J = RC.find(AC); 1607 EXPECT_EQ(&AC, &*J); 1608 --J; 1609 EXPECT_EQ(&BC, &*J); 1610 --J; 1611 EXPECT_EQ(&CC, &*J); 1612 EXPECT_EQ(RC.begin(), J); 1613 EXPECT_EQ(J, NewCs.begin()); 1614 } 1615 1616 TEST(LazyCallGraphTest, InternalRefEdgeToCall) { 1617 LLVMContext Context; 1618 // Basic tests for making a ref edge a call. This hits the basics of the 1619 // process only. 1620 std::unique_ptr<Module> M = 1621 parseAssembly(Context, "define void @a() {\n" 1622 "entry:\n" 1623 " call void @b()\n" 1624 " call void @c()\n" 1625 " store void()* @d, void()** undef\n" 1626 " ret void\n" 1627 "}\n" 1628 "define void @b() {\n" 1629 "entry:\n" 1630 " store void()* @c, void()** undef\n" 1631 " call void @d()\n" 1632 " ret void\n" 1633 "}\n" 1634 "define void @c() {\n" 1635 "entry:\n" 1636 " store void()* @b, void()** undef\n" 1637 " call void @d()\n" 1638 " ret void\n" 1639 "}\n" 1640 "define void @d() {\n" 1641 "entry:\n" 1642 " store void()* @a, void()** undef\n" 1643 " ret void\n" 1644 "}\n"); 1645 LazyCallGraph CG = buildCG(*M); 1646 1647 // Force the graph to be fully expanded. 1648 CG.buildRefSCCs(); 1649 auto I = CG.postorder_ref_scc_begin(); 1650 LazyCallGraph::RefSCC &RC = *I++; 1651 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 1652 1653 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 1654 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 1655 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 1656 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); 1657 LazyCallGraph::SCC &AC = *CG.lookupSCC(A); 1658 LazyCallGraph::SCC &BC = *CG.lookupSCC(B); 1659 LazyCallGraph::SCC &CC = *CG.lookupSCC(C); 1660 LazyCallGraph::SCC &DC = *CG.lookupSCC(D); 1661 1662 // Check the initial post-order. Note that B and C could be flipped here (and 1663 // in our mutation) without changing the nature of this test. 1664 ASSERT_EQ(4, RC.size()); 1665 EXPECT_EQ(&DC, &RC[0]); 1666 EXPECT_EQ(&BC, &RC[1]); 1667 EXPECT_EQ(&CC, &RC[2]); 1668 EXPECT_EQ(&AC, &RC[3]); 1669 1670 // Switch the ref edge from A -> D to a call edge. This should have no 1671 // effect as it is already in postorder and no new cycles are formed. 1672 EXPECT_FALSE(RC.switchInternalEdgeToCall(A, D)); 1673 ASSERT_EQ(4, RC.size()); 1674 EXPECT_EQ(&DC, &RC[0]); 1675 EXPECT_EQ(&BC, &RC[1]); 1676 EXPECT_EQ(&CC, &RC[2]); 1677 EXPECT_EQ(&AC, &RC[3]); 1678 1679 // Switch B -> C to a call edge. This doesn't form any new cycles but does 1680 // require reordering the SCCs. 1681 EXPECT_FALSE(RC.switchInternalEdgeToCall(B, C)); 1682 ASSERT_EQ(4, RC.size()); 1683 EXPECT_EQ(&DC, &RC[0]); 1684 EXPECT_EQ(&CC, &RC[1]); 1685 EXPECT_EQ(&BC, &RC[2]); 1686 EXPECT_EQ(&AC, &RC[3]); 1687 1688 // Switch C -> B to a call edge. This forms a cycle and forces merging SCCs. 1689 EXPECT_TRUE(RC.switchInternalEdgeToCall(C, B, [&](ArrayRef<LazyCallGraph::SCC *> MergedCs) { 1690 ASSERT_EQ(1u, MergedCs.size()); 1691 EXPECT_EQ(&CC, MergedCs[0]); 1692 })); 1693 ASSERT_EQ(3, RC.size()); 1694 EXPECT_EQ(&DC, &RC[0]); 1695 EXPECT_EQ(&BC, &RC[1]); 1696 EXPECT_EQ(&AC, &RC[2]); 1697 EXPECT_EQ(2, BC.size()); 1698 EXPECT_EQ(&BC, CG.lookupSCC(B)); 1699 EXPECT_EQ(&BC, CG.lookupSCC(C)); 1700 } 1701 1702 TEST(LazyCallGraphTest, InternalRefEdgeToCallNoCycleInterleaved) { 1703 LLVMContext Context; 1704 // Test for having a post-order prior to changing a ref edge to a call edge 1705 // with SCCs connecting to the source and connecting to the target, but not 1706 // connecting to both, interleaved between the source and target. This 1707 // ensures we correctly partition the range rather than simply moving one or 1708 // the other. 1709 std::unique_ptr<Module> M = 1710 parseAssembly(Context, "define void @a() {\n" 1711 "entry:\n" 1712 " call void @b1()\n" 1713 " call void @c1()\n" 1714 " ret void\n" 1715 "}\n" 1716 "define void @b1() {\n" 1717 "entry:\n" 1718 " call void @c1()\n" 1719 " call void @b2()\n" 1720 " ret void\n" 1721 "}\n" 1722 "define void @c1() {\n" 1723 "entry:\n" 1724 " call void @b2()\n" 1725 " call void @c2()\n" 1726 " ret void\n" 1727 "}\n" 1728 "define void @b2() {\n" 1729 "entry:\n" 1730 " call void @c2()\n" 1731 " call void @b3()\n" 1732 " ret void\n" 1733 "}\n" 1734 "define void @c2() {\n" 1735 "entry:\n" 1736 " call void @b3()\n" 1737 " call void @c3()\n" 1738 " ret void\n" 1739 "}\n" 1740 "define void @b3() {\n" 1741 "entry:\n" 1742 " call void @c3()\n" 1743 " call void @d()\n" 1744 " ret void\n" 1745 "}\n" 1746 "define void @c3() {\n" 1747 "entry:\n" 1748 " store void()* @b1, void()** undef\n" 1749 " call void @d()\n" 1750 " ret void\n" 1751 "}\n" 1752 "define void @d() {\n" 1753 "entry:\n" 1754 " store void()* @a, void()** undef\n" 1755 " ret void\n" 1756 "}\n"); 1757 LazyCallGraph CG = buildCG(*M); 1758 1759 // Force the graph to be fully expanded. 1760 CG.buildRefSCCs(); 1761 auto I = CG.postorder_ref_scc_begin(); 1762 LazyCallGraph::RefSCC &RC = *I++; 1763 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 1764 1765 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 1766 LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1")); 1767 LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2")); 1768 LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3")); 1769 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1")); 1770 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2")); 1771 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3")); 1772 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); 1773 LazyCallGraph::SCC &AC = *CG.lookupSCC(A); 1774 LazyCallGraph::SCC &B1C = *CG.lookupSCC(B1); 1775 LazyCallGraph::SCC &B2C = *CG.lookupSCC(B2); 1776 LazyCallGraph::SCC &B3C = *CG.lookupSCC(B3); 1777 LazyCallGraph::SCC &C1C = *CG.lookupSCC(C1); 1778 LazyCallGraph::SCC &C2C = *CG.lookupSCC(C2); 1779 LazyCallGraph::SCC &C3C = *CG.lookupSCC(C3); 1780 LazyCallGraph::SCC &DC = *CG.lookupSCC(D); 1781 1782 // Several call edges are initially present to force a particual post-order. 1783 // Remove them now, leaving an interleaved post-order pattern. 1784 RC.switchTrivialInternalEdgeToRef(B3, C3); 1785 RC.switchTrivialInternalEdgeToRef(C2, B3); 1786 RC.switchTrivialInternalEdgeToRef(B2, C2); 1787 RC.switchTrivialInternalEdgeToRef(C1, B2); 1788 RC.switchTrivialInternalEdgeToRef(B1, C1); 1789 1790 // Check the initial post-order. We ensure this order with the extra edges 1791 // that are nuked above. 1792 ASSERT_EQ(8, RC.size()); 1793 EXPECT_EQ(&DC, &RC[0]); 1794 EXPECT_EQ(&C3C, &RC[1]); 1795 EXPECT_EQ(&B3C, &RC[2]); 1796 EXPECT_EQ(&C2C, &RC[3]); 1797 EXPECT_EQ(&B2C, &RC[4]); 1798 EXPECT_EQ(&C1C, &RC[5]); 1799 EXPECT_EQ(&B1C, &RC[6]); 1800 EXPECT_EQ(&AC, &RC[7]); 1801 1802 // Switch C3 -> B1 to a call edge. This doesn't form any new cycles but does 1803 // require reordering the SCCs in the face of tricky internal node 1804 // structures. 1805 EXPECT_FALSE(RC.switchInternalEdgeToCall(C3, B1)); 1806 ASSERT_EQ(8, RC.size()); 1807 EXPECT_EQ(&DC, &RC[0]); 1808 EXPECT_EQ(&B3C, &RC[1]); 1809 EXPECT_EQ(&B2C, &RC[2]); 1810 EXPECT_EQ(&B1C, &RC[3]); 1811 EXPECT_EQ(&C3C, &RC[4]); 1812 EXPECT_EQ(&C2C, &RC[5]); 1813 EXPECT_EQ(&C1C, &RC[6]); 1814 EXPECT_EQ(&AC, &RC[7]); 1815 } 1816 1817 TEST(LazyCallGraphTest, InternalRefEdgeToCallBothPartitionAndMerge) { 1818 LLVMContext Context; 1819 // Test for having a postorder where between the source and target are all 1820 // three kinds of other SCCs: 1821 // 1) One connected to the target only that have to be shifted below the 1822 // source. 1823 // 2) One connected to the source only that have to be shifted below the 1824 // target. 1825 // 3) One connected to both source and target that has to remain and get 1826 // merged away. 1827 // 1828 // To achieve this we construct a heavily connected graph to force 1829 // a particular post-order. Then we remove the forcing edges and connect 1830 // a cycle. 1831 // 1832 // Diagram for the graph we want on the left and the graph we use to force 1833 // the ordering on the right. Edges point down or right. 1834 // 1835 // A | A | 1836 // / \ | / \ | 1837 // B E | B \ | 1838 // |\ | | |\ | | 1839 // | D | | C-D-E | 1840 // | \| | | \| | 1841 // C F | \ F | 1842 // \ / | \ / | 1843 // G | G | 1844 // 1845 // And we form a cycle by connecting F to B. 1846 std::unique_ptr<Module> M = 1847 parseAssembly(Context, "define void @a() {\n" 1848 "entry:\n" 1849 " call void @b()\n" 1850 " call void @e()\n" 1851 " ret void\n" 1852 "}\n" 1853 "define void @b() {\n" 1854 "entry:\n" 1855 " call void @c()\n" 1856 " call void @d()\n" 1857 " ret void\n" 1858 "}\n" 1859 "define void @c() {\n" 1860 "entry:\n" 1861 " call void @d()\n" 1862 " call void @g()\n" 1863 " ret void\n" 1864 "}\n" 1865 "define void @d() {\n" 1866 "entry:\n" 1867 " call void @e()\n" 1868 " call void @f()\n" 1869 " ret void\n" 1870 "}\n" 1871 "define void @e() {\n" 1872 "entry:\n" 1873 " call void @f()\n" 1874 " ret void\n" 1875 "}\n" 1876 "define void @f() {\n" 1877 "entry:\n" 1878 " store void()* @b, void()** undef\n" 1879 " call void @g()\n" 1880 " ret void\n" 1881 "}\n" 1882 "define void @g() {\n" 1883 "entry:\n" 1884 " store void()* @a, void()** undef\n" 1885 " ret void\n" 1886 "}\n"); 1887 LazyCallGraph CG = buildCG(*M); 1888 1889 // Force the graph to be fully expanded. 1890 CG.buildRefSCCs(); 1891 auto I = CG.postorder_ref_scc_begin(); 1892 LazyCallGraph::RefSCC &RC = *I++; 1893 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 1894 1895 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 1896 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 1897 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 1898 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); 1899 LazyCallGraph::Node &E = *CG.lookup(lookupFunction(*M, "e")); 1900 LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f")); 1901 LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g")); 1902 LazyCallGraph::SCC &AC = *CG.lookupSCC(A); 1903 LazyCallGraph::SCC &BC = *CG.lookupSCC(B); 1904 LazyCallGraph::SCC &CC = *CG.lookupSCC(C); 1905 LazyCallGraph::SCC &DC = *CG.lookupSCC(D); 1906 LazyCallGraph::SCC &EC = *CG.lookupSCC(E); 1907 LazyCallGraph::SCC &FC = *CG.lookupSCC(F); 1908 LazyCallGraph::SCC &GC = *CG.lookupSCC(G); 1909 1910 // Remove the extra edges that were used to force a particular post-order. 1911 RC.switchTrivialInternalEdgeToRef(C, D); 1912 RC.switchTrivialInternalEdgeToRef(D, E); 1913 1914 // Check the initial post-order. We ensure this order with the extra edges 1915 // that are nuked above. 1916 ASSERT_EQ(7, RC.size()); 1917 EXPECT_EQ(&GC, &RC[0]); 1918 EXPECT_EQ(&FC, &RC[1]); 1919 EXPECT_EQ(&EC, &RC[2]); 1920 EXPECT_EQ(&DC, &RC[3]); 1921 EXPECT_EQ(&CC, &RC[4]); 1922 EXPECT_EQ(&BC, &RC[5]); 1923 EXPECT_EQ(&AC, &RC[6]); 1924 1925 // Switch F -> B to a call edge. This merges B, D, and F into a single SCC, 1926 // and has to place the C and E SCCs on either side of it: 1927 // A A | 1928 // / \ / \ | 1929 // B E | E | 1930 // |\ | \ / | 1931 // | D | -> B | 1932 // | \| / \ | 1933 // C F C | | 1934 // \ / \ / | 1935 // G G | 1936 EXPECT_TRUE(RC.switchInternalEdgeToCall( 1937 F, B, [&](ArrayRef<LazyCallGraph::SCC *> MergedCs) { 1938 ASSERT_EQ(2u, MergedCs.size()); 1939 EXPECT_EQ(&FC, MergedCs[0]); 1940 EXPECT_EQ(&DC, MergedCs[1]); 1941 })); 1942 EXPECT_EQ(3, BC.size()); 1943 1944 // And make sure the postorder was updated. 1945 ASSERT_EQ(5, RC.size()); 1946 EXPECT_EQ(&GC, &RC[0]); 1947 EXPECT_EQ(&CC, &RC[1]); 1948 EXPECT_EQ(&BC, &RC[2]); 1949 EXPECT_EQ(&EC, &RC[3]); 1950 EXPECT_EQ(&AC, &RC[4]); 1951 } 1952 1953 // Test for IR containing constants using blockaddress constant expressions. 1954 // These are truly unique constructs: constant expressions with non-constant 1955 // operands. 1956 TEST(LazyCallGraphTest, HandleBlockAddress) { 1957 LLVMContext Context; 1958 std::unique_ptr<Module> M = 1959 parseAssembly(Context, "define void @f() {\n" 1960 "entry:\n" 1961 " ret void\n" 1962 "bb:\n" 1963 " unreachable\n" 1964 "}\n" 1965 "define void @g(i8** %ptr) {\n" 1966 "entry:\n" 1967 " store i8* blockaddress(@f, %bb), i8** %ptr\n" 1968 " ret void\n" 1969 "}\n"); 1970 LazyCallGraph CG = buildCG(*M); 1971 1972 CG.buildRefSCCs(); 1973 auto I = CG.postorder_ref_scc_begin(); 1974 LazyCallGraph::RefSCC &FRC = *I++; 1975 LazyCallGraph::RefSCC &GRC = *I++; 1976 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 1977 1978 LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f")); 1979 LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g")); 1980 EXPECT_EQ(&FRC, CG.lookupRefSCC(F)); 1981 EXPECT_EQ(&GRC, CG.lookupRefSCC(G)); 1982 EXPECT_FALSE(GRC.isParentOf(FRC)); 1983 EXPECT_FALSE(FRC.isParentOf(GRC)); 1984 } 1985 1986 // Test that a blockaddress that refers to itself creates no new RefSCC 1987 // connections. https://bugs.llvm.org/show_bug.cgi?id=40722 1988 TEST(LazyCallGraphTest, HandleBlockAddress2) { 1989 LLVMContext Context; 1990 std::unique_ptr<Module> M = 1991 parseAssembly(Context, "define void @f() {\n" 1992 " ret void\n" 1993 "}\n" 1994 "define void @g(i8** %ptr) {\n" 1995 "bb:\n" 1996 " store i8* blockaddress(@g, %bb), i8** %ptr\n" 1997 " ret void\n" 1998 "}\n"); 1999 LazyCallGraph CG = buildCG(*M); 2000 2001 CG.buildRefSCCs(); 2002 auto I = CG.postorder_ref_scc_begin(); 2003 LazyCallGraph::RefSCC &FRC = *I++; 2004 LazyCallGraph::RefSCC &GRC = *I++; 2005 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2006 2007 LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f")); 2008 LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g")); 2009 EXPECT_EQ(&FRC, CG.lookupRefSCC(F)); 2010 EXPECT_EQ(&GRC, CG.lookupRefSCC(G)); 2011 EXPECT_FALSE(GRC.isParentOf(FRC)); 2012 EXPECT_FALSE(FRC.isParentOf(GRC)); 2013 } 2014 2015 TEST(LazyCallGraphTest, ReplaceNodeFunction) { 2016 LLVMContext Context; 2017 // A graph with several different kinds of edges pointing at a particular 2018 // function. 2019 std::unique_ptr<Module> M = 2020 parseAssembly(Context, 2021 "define void @a(i8** %ptr) {\n" 2022 "entry:\n" 2023 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n" 2024 " ret void\n" 2025 "}\n" 2026 "define void @b(i8** %ptr) {\n" 2027 "entry:\n" 2028 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n" 2029 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n" 2030 " call void @d(i8** %ptr)" 2031 " ret void\n" 2032 "}\n" 2033 "define void @c(i8** %ptr) {\n" 2034 "entry:\n" 2035 " call void @d(i8** %ptr)" 2036 " call void @d(i8** %ptr)" 2037 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n" 2038 " ret void\n" 2039 "}\n" 2040 "define void @d(i8** %ptr) {\n" 2041 "entry:\n" 2042 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" 2043 " call void @c(i8** %ptr)" 2044 " call void @d(i8** %ptr)" 2045 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n" 2046 " ret void\n" 2047 "}\n"); 2048 LazyCallGraph CG = buildCG(*M); 2049 2050 // Force the graph to be fully expanded. 2051 CG.buildRefSCCs(); 2052 auto I = CG.postorder_ref_scc_begin(); 2053 LazyCallGraph::RefSCC &RC1 = *I++; 2054 LazyCallGraph::RefSCC &RC2 = *I++; 2055 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2056 2057 ASSERT_EQ(2, RC1.size()); 2058 LazyCallGraph::SCC &C1 = RC1[0]; 2059 LazyCallGraph::SCC &C2 = RC1[1]; 2060 2061 LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a")); 2062 LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b")); 2063 LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c")); 2064 LazyCallGraph::Node &DN = *CG.lookup(lookupFunction(*M, "d")); 2065 EXPECT_EQ(&C1, CG.lookupSCC(DN)); 2066 EXPECT_EQ(&C1, CG.lookupSCC(CN)); 2067 EXPECT_EQ(&C2, CG.lookupSCC(BN)); 2068 EXPECT_EQ(&RC1, CG.lookupRefSCC(DN)); 2069 EXPECT_EQ(&RC1, CG.lookupRefSCC(CN)); 2070 EXPECT_EQ(&RC1, CG.lookupRefSCC(BN)); 2071 EXPECT_EQ(&RC2, CG.lookupRefSCC(AN)); 2072 2073 // Now we need to build a new function 'e' with the same signature as 'd'. 2074 Function &D = DN.getFunction(); 2075 Function &E = *Function::Create(D.getFunctionType(), D.getLinkage(), "e"); 2076 D.getParent()->getFunctionList().insert(D.getIterator(), &E); 2077 2078 // Change each use of 'd' to use 'e'. This is particularly easy as they have 2079 // the same type. 2080 D.replaceAllUsesWith(&E); 2081 2082 // Splice the body of the old function into the new one. 2083 E.splice(E.begin(), &D); 2084 // And fix up the one argument. 2085 D.arg_begin()->replaceAllUsesWith(&*E.arg_begin()); 2086 E.arg_begin()->takeName(&*D.arg_begin()); 2087 2088 // Now replace the function in the graph. 2089 RC1.replaceNodeFunction(DN, E); 2090 2091 EXPECT_EQ(&E, &DN.getFunction()); 2092 EXPECT_EQ(&DN, &(*CN)[DN].getNode()); 2093 EXPECT_EQ(&DN, &(*BN)[DN].getNode()); 2094 } 2095 2096 TEST(LazyCallGraphTest, RemoveFunctionWithSpuriousRef) { 2097 LLVMContext Context; 2098 // A graph with a couple of RefSCCs. 2099 std::unique_ptr<Module> M = 2100 parseAssembly(Context, 2101 "define void @a(i8** %ptr) {\n" 2102 "entry:\n" 2103 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n" 2104 " ret void\n" 2105 "}\n" 2106 "define void @b(i8** %ptr) {\n" 2107 "entry:\n" 2108 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" 2109 " ret void\n" 2110 "}\n" 2111 "define void @c(i8** %ptr) {\n" 2112 "entry:\n" 2113 " call void @d(i8** %ptr)" 2114 " ret void\n" 2115 "}\n" 2116 "define void @d(i8** %ptr) {\n" 2117 "entry:\n" 2118 " call void @c(i8** %ptr)" 2119 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" 2120 " ret void\n" 2121 "}\n" 2122 "define void @dead() {\n" 2123 "entry:\n" 2124 " ret void\n" 2125 "}\n"); 2126 LazyCallGraph CG = buildCG(*M); 2127 2128 // Insert spurious ref edges. 2129 LazyCallGraph::Node &AN = CG.get(lookupFunction(*M, "a")); 2130 LazyCallGraph::Node &BN = CG.get(lookupFunction(*M, "b")); 2131 LazyCallGraph::Node &CN = CG.get(lookupFunction(*M, "c")); 2132 LazyCallGraph::Node &DN = CG.get(lookupFunction(*M, "d")); 2133 LazyCallGraph::Node &DeadN = CG.get(lookupFunction(*M, "dead")); 2134 AN.populate(); 2135 BN.populate(); 2136 CN.populate(); 2137 DN.populate(); 2138 DeadN.populate(); 2139 CG.insertEdge(AN, DeadN, LazyCallGraph::Edge::Ref); 2140 CG.insertEdge(BN, DeadN, LazyCallGraph::Edge::Ref); 2141 CG.insertEdge(CN, DeadN, LazyCallGraph::Edge::Ref); 2142 CG.insertEdge(DN, DeadN, LazyCallGraph::Edge::Ref); 2143 2144 // Force the graph to be fully expanded. 2145 CG.buildRefSCCs(); 2146 auto I = CG.postorder_ref_scc_begin(); 2147 LazyCallGraph::RefSCC &DeadRC = *I++; 2148 LazyCallGraph::RefSCC &RC1 = *I++; 2149 LazyCallGraph::RefSCC &RC2 = *I++; 2150 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2151 2152 ASSERT_EQ(2, RC1.size()); 2153 LazyCallGraph::SCC &C1 = RC1[0]; 2154 LazyCallGraph::SCC &C2 = RC1[1]; 2155 2156 EXPECT_EQ(&DeadRC, CG.lookupRefSCC(DeadN)); 2157 EXPECT_EQ(&C1, CG.lookupSCC(DN)); 2158 EXPECT_EQ(&C1, CG.lookupSCC(CN)); 2159 EXPECT_EQ(&C2, CG.lookupSCC(BN)); 2160 EXPECT_EQ(&RC1, CG.lookupRefSCC(DN)); 2161 EXPECT_EQ(&RC1, CG.lookupRefSCC(CN)); 2162 EXPECT_EQ(&RC1, CG.lookupRefSCC(BN)); 2163 EXPECT_EQ(&RC2, CG.lookupRefSCC(AN)); 2164 2165 // Now delete 'dead'. There are no uses of this function but there are 2166 // spurious references. 2167 CG.markDeadFunction(DeadN.getFunction()); 2168 CG.removeDeadFunctions({&DeadN.getFunction()}); 2169 2170 // The only observable change should be that the RefSCC is gone from the 2171 // postorder sequence. 2172 I = CG.postorder_ref_scc_begin(); 2173 EXPECT_EQ(&RC1, &*I++); 2174 EXPECT_EQ(&RC2, &*I++); 2175 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2176 } 2177 2178 TEST(LazyCallGraphTest, RemoveFunctionWithSpuriousRefRecursive) { 2179 LLVMContext Context; 2180 std::unique_ptr<Module> M = 2181 parseAssembly(Context, "define void @a(ptr %p) {\n" 2182 " store ptr @b, ptr %p\n" 2183 " ret void\n" 2184 "}\n" 2185 "define void @b(ptr %p) {\n" 2186 " store ptr @c, ptr %p\n" 2187 " ret void\n" 2188 "}\n" 2189 "define void @c(ptr %p) {\n" 2190 " ret void\n" 2191 "}\n"); 2192 LazyCallGraph CG = buildCG(*M); 2193 2194 LazyCallGraph::Node &AN = CG.get(lookupFunction(*M, "a")); 2195 LazyCallGraph::Node &BN = CG.get(lookupFunction(*M, "b")); 2196 LazyCallGraph::Node &CN = CG.get(lookupFunction(*M, "c")); 2197 AN.populate(); 2198 BN.populate(); 2199 CN.populate(); 2200 // Insert spurious ref edge. 2201 CG.insertEdge(CN, AN, LazyCallGraph::Edge::Ref); 2202 2203 // Force the graph to be fully expanded. 2204 CG.buildRefSCCs(); 2205 auto I = CG.postorder_ref_scc_begin(); 2206 LazyCallGraph::RefSCC &RC = *I++; 2207 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2208 2209 ASSERT_EQ(RC.size(), 3); 2210 2211 EXPECT_EQ(&RC, CG.lookupRefSCC(AN)); 2212 EXPECT_EQ(&RC, CG.lookupRefSCC(BN)); 2213 EXPECT_EQ(&RC, CG.lookupRefSCC(CN)); 2214 2215 // Now delete 'a'. There are no uses of this function but there are 2216 // spurious references. 2217 CG.markDeadFunction(AN.getFunction()); 2218 CG.removeDeadFunctions({&AN.getFunction()}); 2219 2220 // The only observable change should be that the RefSCC is gone from the 2221 // postorder sequence. 2222 I = CG.postorder_ref_scc_begin(); 2223 EXPECT_EQ(CG.lookupRefSCC(CN), &*I++); 2224 EXPECT_EQ(CG.lookupRefSCC(BN), &*I++); 2225 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2226 } 2227 2228 TEST(LazyCallGraphTest, RemoveFunctionWithSpuriousRefRecursive2) { 2229 LLVMContext Context; 2230 std::unique_ptr<Module> M = 2231 parseAssembly(Context, "define void @a(ptr %p) {\n" 2232 " store ptr @b, ptr %p\n" 2233 " ret void\n" 2234 "}\n" 2235 "define void @b(ptr %p) {\n" 2236 " store ptr @c, ptr %p\n" 2237 " ret void\n" 2238 "}\n" 2239 "define void @c(ptr %p) {\n" 2240 " store ptr @b, ptr %p\n" 2241 " store ptr @d, ptr %p\n" 2242 " ret void\n" 2243 "}\n" 2244 "define void @d(ptr %p) {\n" 2245 " ret void\n" 2246 "}\n"); 2247 LazyCallGraph CG = buildCG(*M); 2248 2249 LazyCallGraph::Node &AN = CG.get(lookupFunction(*M, "a")); 2250 LazyCallGraph::Node &BN = CG.get(lookupFunction(*M, "b")); 2251 LazyCallGraph::Node &CN = CG.get(lookupFunction(*M, "c")); 2252 LazyCallGraph::Node &DN = CG.get(lookupFunction(*M, "d")); 2253 AN.populate(); 2254 BN.populate(); 2255 CN.populate(); 2256 DN.populate(); 2257 // Insert spurious ref edge. 2258 CG.insertEdge(DN, AN, LazyCallGraph::Edge::Ref); 2259 2260 // Force the graph to be fully expanded. 2261 CG.buildRefSCCs(); 2262 auto I = CG.postorder_ref_scc_begin(); 2263 LazyCallGraph::RefSCC &RC = *I++; 2264 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2265 2266 ASSERT_EQ(4, RC.size()); 2267 2268 EXPECT_EQ(&RC, CG.lookupRefSCC(AN)); 2269 EXPECT_EQ(&RC, CG.lookupRefSCC(BN)); 2270 EXPECT_EQ(&RC, CG.lookupRefSCC(CN)); 2271 EXPECT_EQ(&RC, CG.lookupRefSCC(DN)); 2272 2273 // Now delete 'a'. There are no uses of this function but there are 2274 // spurious references. 2275 CG.markDeadFunction(AN.getFunction()); 2276 CG.removeDeadFunctions({&AN.getFunction()}); 2277 2278 // The only observable change should be that the RefSCC is gone from the 2279 // postorder sequence. 2280 I = CG.postorder_ref_scc_begin(); 2281 EXPECT_EQ(CG.lookupRefSCC(DN), &*I++); 2282 EXPECT_EQ(CG.lookupRefSCC(CN), &*I); 2283 EXPECT_EQ(CG.lookupRefSCC(BN), &*I++); 2284 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2285 } 2286 2287 TEST(LazyCallGraphTest, RemoveFunctionWithSpuriousRefRecursive3) { 2288 LLVMContext Context; 2289 std::unique_ptr<Module> M = 2290 parseAssembly(Context, "define void @a(ptr %p) {\n" 2291 " store ptr @b, ptr %p\n" 2292 " ret void\n" 2293 "}\n" 2294 "define void @b(ptr %p) {\n" 2295 " store ptr @c, ptr %p\n" 2296 " ret void\n" 2297 "}\n" 2298 "define void @c(ptr %p) {\n" 2299 " ret void\n" 2300 "}\n"); 2301 LazyCallGraph CG = buildCG(*M); 2302 2303 LazyCallGraph::Node &AN = CG.get(lookupFunction(*M, "a")); 2304 LazyCallGraph::Node &BN = CG.get(lookupFunction(*M, "b")); 2305 LazyCallGraph::Node &CN = CG.get(lookupFunction(*M, "c")); 2306 AN.populate(); 2307 BN.populate(); 2308 CN.populate(); 2309 // Insert spurious ref edges. 2310 CG.insertEdge(CN, AN, LazyCallGraph::Edge::Ref); 2311 CG.insertEdge(BN, AN, LazyCallGraph::Edge::Ref); 2312 2313 // Force the graph to be fully expanded. 2314 CG.buildRefSCCs(); 2315 auto I = CG.postorder_ref_scc_begin(); 2316 LazyCallGraph::RefSCC &RC = *I++; 2317 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2318 2319 ASSERT_EQ(RC.size(), 3); 2320 2321 EXPECT_EQ(&RC, CG.lookupRefSCC(AN)); 2322 EXPECT_EQ(&RC, CG.lookupRefSCC(BN)); 2323 EXPECT_EQ(&RC, CG.lookupRefSCC(CN)); 2324 2325 // Now delete 'a'. There are no uses of this function but there are 2326 // spurious references. 2327 CG.markDeadFunction(AN.getFunction()); 2328 CG.removeDeadFunctions({&AN.getFunction()}); 2329 2330 // The only observable change should be that the RefSCC is gone from the 2331 // postorder sequence. 2332 I = CG.postorder_ref_scc_begin(); 2333 EXPECT_EQ(CG.lookupRefSCC(CN), &*I++); 2334 EXPECT_EQ(CG.lookupRefSCC(BN), &*I++); 2335 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2336 } 2337 2338 TEST(LazyCallGraphTest, AddSplitFunction1) { 2339 LLVMContext Context; 2340 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n" 2341 " ret void\n" 2342 "}\n"); 2343 LazyCallGraph CG = buildCG(*M); 2344 2345 Function &F = lookupFunction(*M, "f"); 2346 LazyCallGraph::Node &FN = CG.get(F); 2347 2348 // Force the graph to be fully expanded. 2349 CG.buildRefSCCs(); 2350 auto I = CG.postorder_ref_scc_begin(); 2351 LazyCallGraph::RefSCC *ORC = &*I++; 2352 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2353 2354 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(), 2355 F.getAddressSpace(), "g", F.getParent()); 2356 BasicBlock *GBB = BasicBlock::Create(Context, "", G); 2357 (void)ReturnInst::Create(Context, GBB); 2358 2359 // Create f -call-> g. 2360 (void)CallInst::Create(G, {}, "", F.getEntryBlock().begin()); 2361 2362 EXPECT_FALSE(verifyModule(*M, &errs())); 2363 2364 CG.addSplitFunction(F, *G); 2365 2366 LazyCallGraph::Node *GN = CG.lookup(*G); 2367 EXPECT_TRUE(GN); 2368 2369 I = CG.postorder_ref_scc_begin(); 2370 LazyCallGraph::RefSCC *RC1 = &*I++; 2371 EXPECT_EQ(RC1, CG.lookupRefSCC(*GN)); 2372 LazyCallGraph::RefSCC *RC2 = &*I++; 2373 EXPECT_EQ(RC2, ORC); 2374 EXPECT_EQ(RC2, CG.lookupRefSCC(FN)); 2375 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2376 } 2377 2378 TEST(LazyCallGraphTest, AddSplitFunction2) { 2379 LLVMContext Context; 2380 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n" 2381 " ret void\n" 2382 "}\n"); 2383 LazyCallGraph CG = buildCG(*M); 2384 2385 Function &F = lookupFunction(*M, "f"); 2386 LazyCallGraph::Node &FN = CG.get(F); 2387 2388 // Force the graph to be fully expanded. 2389 CG.buildRefSCCs(); 2390 auto I = CG.postorder_ref_scc_begin(); 2391 LazyCallGraph::RefSCC *ORC = &*I++; 2392 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2393 2394 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(), 2395 F.getAddressSpace(), "g", F.getParent()); 2396 BasicBlock *GBB = BasicBlock::Create(Context, "", G); 2397 (void)ReturnInst::Create(Context, GBB); 2398 2399 // Create f -ref-> g. 2400 (void)CastInst::CreatePointerCast(G, PointerType::getUnqual(Context), "", 2401 F.getEntryBlock().begin()); 2402 2403 EXPECT_FALSE(verifyModule(*M, &errs())); 2404 2405 CG.addSplitFunction(F, *G); 2406 2407 LazyCallGraph::Node *GN = CG.lookup(*G); 2408 EXPECT_TRUE(GN); 2409 2410 I = CG.postorder_ref_scc_begin(); 2411 LazyCallGraph::RefSCC *RC1 = &*I++; 2412 EXPECT_EQ(RC1, CG.lookupRefSCC(*GN)); 2413 LazyCallGraph::RefSCC *RC2 = &*I++; 2414 EXPECT_EQ(RC2, ORC); 2415 EXPECT_EQ(RC2, CG.lookupRefSCC(FN)); 2416 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2417 } 2418 2419 TEST(LazyCallGraphTest, AddSplitFunction3) { 2420 LLVMContext Context; 2421 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n" 2422 " ret void\n" 2423 "}\n"); 2424 LazyCallGraph CG = buildCG(*M); 2425 2426 Function &F = lookupFunction(*M, "f"); 2427 LazyCallGraph::Node &FN = CG.get(F); 2428 2429 // Force the graph to be fully expanded. 2430 CG.buildRefSCCs(); 2431 auto I = CG.postorder_ref_scc_begin(); 2432 LazyCallGraph::RefSCC *ORC = &*I++; 2433 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2434 2435 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(), 2436 F.getAddressSpace(), "g", F.getParent()); 2437 BasicBlock *GBB = BasicBlock::Create(Context, "", G); 2438 // Create g -ref-> f. 2439 (void)CastInst::CreatePointerCast(&F, PointerType::getUnqual(Context), "", 2440 GBB); 2441 (void)ReturnInst::Create(Context, GBB); 2442 2443 // Create f -call-> g. 2444 (void)CallInst::Create(G, {}, "", F.getEntryBlock().begin()); 2445 2446 EXPECT_FALSE(verifyModule(*M, &errs())); 2447 2448 CG.addSplitFunction(F, *G); 2449 2450 LazyCallGraph::Node *GN = CG.lookup(*G); 2451 EXPECT_TRUE(GN); 2452 2453 I = CG.postorder_ref_scc_begin(); 2454 LazyCallGraph::RefSCC *RC = &*I++; 2455 EXPECT_EQ(RC, CG.lookupRefSCC(*GN)); 2456 EXPECT_EQ(RC, ORC); 2457 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2458 2459 EXPECT_EQ(2, RC->size()); 2460 EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[0]); 2461 EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[1]); 2462 } 2463 2464 TEST(LazyCallGraphTest, AddSplitFunction4) { 2465 LLVMContext Context; 2466 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n" 2467 " ret void\n" 2468 "}\n"); 2469 LazyCallGraph CG = buildCG(*M); 2470 2471 Function &F = lookupFunction(*M, "f"); 2472 LazyCallGraph::Node &FN = CG.get(F); 2473 2474 // Force the graph to be fully expanded. 2475 CG.buildRefSCCs(); 2476 auto I = CG.postorder_ref_scc_begin(); 2477 LazyCallGraph::RefSCC *ORC = &*I++; 2478 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2479 2480 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(), 2481 F.getAddressSpace(), "g", F.getParent()); 2482 BasicBlock *GBB = BasicBlock::Create(Context, "", G); 2483 // Create g -ref-> f. 2484 (void)CastInst::CreatePointerCast(&F, PointerType::getUnqual(Context), "", 2485 GBB); 2486 (void)ReturnInst::Create(Context, GBB); 2487 2488 // Create f -ref-> g. 2489 (void)CastInst::CreatePointerCast(G, PointerType::getUnqual(Context), "", 2490 F.getEntryBlock().begin()); 2491 2492 EXPECT_FALSE(verifyModule(*M, &errs())); 2493 2494 CG.addSplitFunction(F, *G); 2495 2496 LazyCallGraph::Node *GN = CG.lookup(*G); 2497 EXPECT_TRUE(GN); 2498 2499 I = CG.postorder_ref_scc_begin(); 2500 LazyCallGraph::RefSCC *RC = &*I++; 2501 EXPECT_EQ(RC, CG.lookupRefSCC(*GN)); 2502 EXPECT_EQ(RC, ORC); 2503 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2504 2505 // Order doesn't matter for sibling SCCs. 2506 EXPECT_EQ(2, RC->size()); 2507 EXPECT_EQ(&CG.lookupSCC(*GN)->getOuterRefSCC(), RC); 2508 EXPECT_EQ(&CG.lookupSCC(FN)->getOuterRefSCC(), RC); 2509 } 2510 2511 TEST(LazyCallGraphTest, AddSplitFunction5) { 2512 LLVMContext Context; 2513 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n" 2514 " ret void\n" 2515 "}\n"); 2516 LazyCallGraph CG = buildCG(*M); 2517 2518 Function &F = lookupFunction(*M, "f"); 2519 LazyCallGraph::Node &FN = CG.get(F); 2520 2521 // Force the graph to be fully expanded. 2522 CG.buildRefSCCs(); 2523 auto I = CG.postorder_ref_scc_begin(); 2524 LazyCallGraph::RefSCC *ORC = &*I++; 2525 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2526 2527 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(), 2528 F.getAddressSpace(), "g", F.getParent()); 2529 BasicBlock *GBB = BasicBlock::Create(Context, "", G); 2530 // Create g -call-> f. 2531 (void)CallInst::Create(&F, {}, "", GBB); 2532 (void)ReturnInst::Create(Context, GBB); 2533 2534 // Create f -ref-> g. 2535 (void)CastInst::CreatePointerCast(G, PointerType::getUnqual(Context), "", 2536 F.getEntryBlock().begin()); 2537 2538 EXPECT_FALSE(verifyModule(*M, &errs())); 2539 2540 CG.addSplitFunction(F, *G); 2541 2542 LazyCallGraph::Node *GN = CG.lookup(*G); 2543 EXPECT_TRUE(GN); 2544 2545 I = CG.postorder_ref_scc_begin(); 2546 LazyCallGraph::RefSCC *RC = &*I++; 2547 EXPECT_EQ(RC, CG.lookupRefSCC(*GN)); 2548 EXPECT_EQ(RC, ORC); 2549 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2550 2551 EXPECT_EQ(2, RC->size()); 2552 EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[0]); 2553 EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[1]); 2554 } 2555 2556 TEST(LazyCallGraphTest, AddSplitFunction6) { 2557 LLVMContext Context; 2558 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n" 2559 " ret void\n" 2560 "}\n"); 2561 LazyCallGraph CG = buildCG(*M); 2562 2563 Function &F = lookupFunction(*M, "f"); 2564 LazyCallGraph::Node &FN = CG.get(F); 2565 2566 // Force the graph to be fully expanded. 2567 CG.buildRefSCCs(); 2568 auto I = CG.postorder_ref_scc_begin(); 2569 LazyCallGraph::RefSCC *ORC = &*I++; 2570 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2571 2572 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(), 2573 F.getAddressSpace(), "g", F.getParent()); 2574 BasicBlock *GBB = BasicBlock::Create(Context, "", G); 2575 // Create g -call-> f. 2576 (void)CallInst::Create(&F, {}, "", GBB); 2577 (void)ReturnInst::Create(Context, GBB); 2578 2579 // Create f -call-> g. 2580 (void)CallInst::Create(G, {}, "", F.getEntryBlock().begin()); 2581 2582 EXPECT_FALSE(verifyModule(*M, &errs())); 2583 2584 CG.addSplitFunction(F, *G); 2585 2586 LazyCallGraph::Node *GN = CG.lookup(*G); 2587 EXPECT_TRUE(GN); 2588 2589 I = CG.postorder_ref_scc_begin(); 2590 LazyCallGraph::RefSCC *RC = &*I++; 2591 EXPECT_EQ(RC, CG.lookupRefSCC(*GN)); 2592 EXPECT_EQ(RC, ORC); 2593 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2594 2595 EXPECT_EQ(1, RC->size()); 2596 EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[0]); 2597 EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[0]); 2598 } 2599 2600 TEST(LazyCallGraphTest, AddSplitFunction7) { 2601 LLVMContext Context; 2602 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n" 2603 " call void @f2()\n" 2604 " ret void\n" 2605 "}\n" 2606 "define void @f2() {\n" 2607 " call void @f()\n" 2608 " ret void\n" 2609 "}\n"); 2610 LazyCallGraph CG = buildCG(*M); 2611 2612 Function &F = lookupFunction(*M, "f"); 2613 LazyCallGraph::Node &FN = CG.get(F); 2614 Function &F2 = lookupFunction(*M, "f2"); 2615 LazyCallGraph::Node &F2N = CG.get(F2); 2616 2617 // Force the graph to be fully expanded. 2618 CG.buildRefSCCs(); 2619 auto I = CG.postorder_ref_scc_begin(); 2620 LazyCallGraph::RefSCC *ORC = &*I++; 2621 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2622 2623 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(), 2624 F.getAddressSpace(), "g", F.getParent()); 2625 BasicBlock *GBB = BasicBlock::Create(Context, "", G); 2626 // Create g -call-> f2. 2627 (void)CallInst::Create(&F2, {}, "", GBB); 2628 (void)ReturnInst::Create(Context, GBB); 2629 2630 // Create f -call-> g. 2631 (void)CallInst::Create(G, {}, "", F.getEntryBlock().begin()); 2632 2633 EXPECT_FALSE(verifyModule(*M, &errs())); 2634 2635 CG.addSplitFunction(F, *G); 2636 2637 LazyCallGraph::Node *GN = CG.lookup(*G); 2638 EXPECT_TRUE(GN); 2639 2640 I = CG.postorder_ref_scc_begin(); 2641 LazyCallGraph::RefSCC *RC = &*I++; 2642 EXPECT_EQ(RC, CG.lookupRefSCC(*GN)); 2643 EXPECT_EQ(RC, ORC); 2644 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2645 2646 EXPECT_EQ(1, RC->size()); 2647 EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[0]); 2648 EXPECT_EQ(CG.lookupSCC(F2N), &(*RC)[0]); 2649 EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[0]); 2650 } 2651 2652 TEST(LazyCallGraphTest, AddSplitFunction8) { 2653 LLVMContext Context; 2654 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n" 2655 " call void @f2()\n" 2656 " ret void\n" 2657 "}\n" 2658 "define void @f2() {\n" 2659 " call void @f()\n" 2660 " ret void\n" 2661 "}\n"); 2662 LazyCallGraph CG = buildCG(*M); 2663 2664 Function &F = lookupFunction(*M, "f"); 2665 LazyCallGraph::Node &FN = CG.get(F); 2666 Function &F2 = lookupFunction(*M, "f2"); 2667 LazyCallGraph::Node &F2N = CG.get(F2); 2668 2669 // Force the graph to be fully expanded. 2670 CG.buildRefSCCs(); 2671 auto I = CG.postorder_ref_scc_begin(); 2672 LazyCallGraph::RefSCC *ORC = &*I++; 2673 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2674 2675 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(), 2676 F.getAddressSpace(), "g", F.getParent()); 2677 BasicBlock *GBB = BasicBlock::Create(Context, "", G); 2678 // Create g -call-> f2. 2679 (void)CallInst::Create(&F2, {}, "", GBB); 2680 (void)ReturnInst::Create(Context, GBB); 2681 2682 // Create f -ref-> g. 2683 (void)CastInst::CreatePointerCast(G, PointerType::getUnqual(Context), "", 2684 F.getEntryBlock().begin()); 2685 2686 EXPECT_FALSE(verifyModule(*M, &errs())); 2687 2688 CG.addSplitFunction(F, *G); 2689 2690 LazyCallGraph::Node *GN = CG.lookup(*G); 2691 EXPECT_TRUE(GN); 2692 2693 I = CG.postorder_ref_scc_begin(); 2694 LazyCallGraph::RefSCC *RC = &*I++; 2695 EXPECT_EQ(RC, CG.lookupRefSCC(*GN)); 2696 EXPECT_EQ(RC, ORC); 2697 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2698 2699 EXPECT_EQ(2, RC->size()); 2700 EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[0]); 2701 EXPECT_EQ(CG.lookupSCC(F2N), &(*RC)[0]); 2702 EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[1]); 2703 } 2704 2705 TEST(LazyCallGraphTest, AddSplitFunction9) { 2706 LLVMContext Context; 2707 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n" 2708 " call void @f2()\n" 2709 " ret void\n" 2710 "}\n" 2711 "define void @f2() {\n" 2712 " call void @f()\n" 2713 " ret void\n" 2714 "}\n"); 2715 LazyCallGraph CG = buildCG(*M); 2716 2717 Function &F = lookupFunction(*M, "f"); 2718 LazyCallGraph::Node &FN = CG.get(F); 2719 Function &F2 = lookupFunction(*M, "f2"); 2720 LazyCallGraph::Node &F2N = CG.get(F2); 2721 2722 // Force the graph to be fully expanded. 2723 CG.buildRefSCCs(); 2724 auto I = CG.postorder_ref_scc_begin(); 2725 LazyCallGraph::RefSCC *ORC = &*I++; 2726 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2727 2728 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(), 2729 F.getAddressSpace(), "g", F.getParent()); 2730 BasicBlock *GBB = BasicBlock::Create(Context, "", G); 2731 // Create g -ref-> f2. 2732 (void)CastInst::CreatePointerCast(&F2, PointerType::getUnqual(Context), "", 2733 GBB); 2734 (void)ReturnInst::Create(Context, GBB); 2735 2736 // Create f -call-> g. 2737 (void)CallInst::Create(G, {}, "", F.getEntryBlock().begin()); 2738 2739 EXPECT_FALSE(verifyModule(*M, &errs())); 2740 2741 CG.addSplitFunction(F, *G); 2742 2743 LazyCallGraph::Node *GN = CG.lookup(*G); 2744 EXPECT_TRUE(GN); 2745 2746 I = CG.postorder_ref_scc_begin(); 2747 LazyCallGraph::RefSCC *RC = &*I++; 2748 EXPECT_EQ(RC, CG.lookupRefSCC(*GN)); 2749 EXPECT_EQ(RC, ORC); 2750 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2751 2752 EXPECT_EQ(2, RC->size()); 2753 EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[0]); 2754 EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[1]); 2755 EXPECT_EQ(CG.lookupSCC(F2N), &(*RC)[1]); 2756 } 2757 2758 TEST(LazyCallGraphTest, AddSplitFunctions1) { 2759 LLVMContext Context; 2760 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n" 2761 " ret void\n" 2762 "}\n"); 2763 LazyCallGraph CG = buildCG(*M); 2764 2765 Function &F = lookupFunction(*M, "f"); 2766 LazyCallGraph::Node &FN = CG.get(F); 2767 2768 // Force the graph to be fully expanded. 2769 CG.buildRefSCCs(); 2770 auto I = CG.postorder_ref_scc_begin(); 2771 LazyCallGraph::RefSCC *ORC = &*I++; 2772 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2773 2774 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(), 2775 F.getAddressSpace(), "g", F.getParent()); 2776 BasicBlock *GBB = BasicBlock::Create(Context, "", G); 2777 (void)ReturnInst::Create(Context, GBB); 2778 2779 // Create f -ref-> g. 2780 (void)CastInst::CreatePointerCast(G, PointerType::getUnqual(Context), "", 2781 F.getEntryBlock().begin()); 2782 2783 EXPECT_FALSE(verifyModule(*M, &errs())); 2784 2785 CG.addSplitRefRecursiveFunctions(F, SmallVector<Function *, 1>({G})); 2786 2787 LazyCallGraph::Node *GN = CG.lookup(*G); 2788 EXPECT_TRUE(GN); 2789 2790 I = CG.postorder_ref_scc_begin(); 2791 LazyCallGraph::RefSCC *RC1 = &*I++; 2792 EXPECT_EQ(RC1, CG.lookupRefSCC(*GN)); 2793 LazyCallGraph::RefSCC *RC2 = &*I++; 2794 EXPECT_EQ(RC2, ORC); 2795 EXPECT_EQ(RC2, CG.lookupRefSCC(FN)); 2796 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2797 } 2798 2799 TEST(LazyCallGraphTest, AddSplitFunctions2) { 2800 LLVMContext Context; 2801 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n" 2802 " ret void\n" 2803 "}\n"); 2804 LazyCallGraph CG = buildCG(*M); 2805 2806 Function &F = lookupFunction(*M, "f"); 2807 LazyCallGraph::Node &FN = CG.get(F); 2808 2809 // Force the graph to be fully expanded. 2810 CG.buildRefSCCs(); 2811 auto I = CG.postorder_ref_scc_begin(); 2812 LazyCallGraph::RefSCC *ORC = &*I++; 2813 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2814 2815 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(), 2816 F.getAddressSpace(), "g", F.getParent()); 2817 BasicBlock *GBB = BasicBlock::Create(Context, "", G); 2818 // Create g -ref-> f. 2819 (void)CastInst::CreatePointerCast(&F, PointerType::getUnqual(Context), "", 2820 GBB); 2821 (void)ReturnInst::Create(Context, GBB); 2822 2823 // Create f -ref-> g. 2824 (void)CastInst::CreatePointerCast(G, PointerType::getUnqual(Context), "", 2825 F.getEntryBlock().begin()); 2826 2827 EXPECT_FALSE(verifyModule(*M, &errs())); 2828 2829 CG.addSplitRefRecursiveFunctions(F, SmallVector<Function *, 1>({G})); 2830 2831 LazyCallGraph::Node *GN = CG.lookup(*G); 2832 EXPECT_TRUE(GN); 2833 2834 I = CG.postorder_ref_scc_begin(); 2835 LazyCallGraph::RefSCC *RC = &*I++; 2836 EXPECT_EQ(RC, CG.lookupRefSCC(*GN)); 2837 EXPECT_EQ(RC, ORC); 2838 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2839 2840 // Order doesn't matter for sibling SCCs. 2841 EXPECT_EQ(2, RC->size()); 2842 EXPECT_EQ(&CG.lookupSCC(*GN)->getOuterRefSCC(), RC); 2843 EXPECT_EQ(&CG.lookupSCC(FN)->getOuterRefSCC(), RC); 2844 } 2845 2846 TEST(LazyCallGraphTest, AddSplitFunctions3) { 2847 LLVMContext Context; 2848 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n" 2849 " ret void\n" 2850 "}\n"); 2851 LazyCallGraph CG = buildCG(*M); 2852 2853 Function &F = lookupFunction(*M, "f"); 2854 LazyCallGraph::Node &FN = CG.get(F); 2855 2856 // Force the graph to be fully expanded. 2857 CG.buildRefSCCs(); 2858 auto I = CG.postorder_ref_scc_begin(); 2859 LazyCallGraph::RefSCC *ORC = &*I++; 2860 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2861 2862 auto *G1 = Function::Create(F.getFunctionType(), F.getLinkage(), 2863 F.getAddressSpace(), "g1", F.getParent()); 2864 auto *G2 = Function::Create(F.getFunctionType(), F.getLinkage(), 2865 F.getAddressSpace(), "g2", F.getParent()); 2866 BasicBlock *G1BB = BasicBlock::Create(Context, "", G1); 2867 BasicBlock *G2BB = BasicBlock::Create(Context, "", G2); 2868 // Create g1 -ref-> g2 and g2 -ref-> g1. 2869 (void)CastInst::CreatePointerCast(G2, PointerType::getUnqual(Context), "", 2870 G1BB); 2871 (void)CastInst::CreatePointerCast(G1, PointerType::getUnqual(Context), "", 2872 G2BB); 2873 (void)ReturnInst::Create(Context, G1BB); 2874 (void)ReturnInst::Create(Context, G2BB); 2875 2876 // Create f -ref-> g1 and f -ref-> g2. 2877 (void)CastInst::CreatePointerCast(G1, PointerType::getUnqual(Context), "", 2878 F.getEntryBlock().begin()); 2879 (void)CastInst::CreatePointerCast(G2, PointerType::getUnqual(Context), "", 2880 F.getEntryBlock().begin()); 2881 2882 EXPECT_FALSE(verifyModule(*M, &errs())); 2883 2884 CG.addSplitRefRecursiveFunctions(F, SmallVector<Function *, 1>({G1, G2})); 2885 2886 LazyCallGraph::Node *G1N = CG.lookup(*G1); 2887 EXPECT_TRUE(G1N); 2888 LazyCallGraph::Node *G2N = CG.lookup(*G2); 2889 EXPECT_TRUE(G2N); 2890 2891 I = CG.postorder_ref_scc_begin(); 2892 LazyCallGraph::RefSCC *RC1 = &*I++; 2893 EXPECT_EQ(2, RC1->size()); 2894 EXPECT_EQ(RC1, CG.lookupRefSCC(*G1N)); 2895 EXPECT_EQ(RC1, CG.lookupRefSCC(*G2N)); 2896 LazyCallGraph::RefSCC *RC2 = &*I++; 2897 EXPECT_EQ(RC2, ORC); 2898 EXPECT_EQ(RC2, CG.lookupRefSCC(FN)); 2899 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2900 } 2901 2902 TEST(LazyCallGraphTest, AddSplitFunctions4) { 2903 LLVMContext Context; 2904 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n" 2905 " ret void\n" 2906 "}\n"); 2907 LazyCallGraph CG = buildCG(*M); 2908 2909 Function &F = lookupFunction(*M, "f"); 2910 LazyCallGraph::Node &FN = CG.get(F); 2911 2912 // Force the graph to be fully expanded. 2913 CG.buildRefSCCs(); 2914 auto I = CG.postorder_ref_scc_begin(); 2915 LazyCallGraph::RefSCC *ORC = &*I++; 2916 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2917 2918 auto *G1 = Function::Create(F.getFunctionType(), F.getLinkage(), 2919 F.getAddressSpace(), "g1", F.getParent()); 2920 auto *G2 = Function::Create(F.getFunctionType(), F.getLinkage(), 2921 F.getAddressSpace(), "g2", F.getParent()); 2922 BasicBlock *G1BB = BasicBlock::Create(Context, "", G1); 2923 BasicBlock *G2BB = BasicBlock::Create(Context, "", G2); 2924 // Create g1 -ref-> g2 and g2 -ref-> g1. 2925 (void)CastInst::CreatePointerCast(G2, PointerType::getUnqual(Context), "", 2926 G1BB); 2927 (void)CastInst::CreatePointerCast(G1, PointerType::getUnqual(Context), "", 2928 G2BB); 2929 // Create g2 -ref-> f. 2930 (void)CastInst::CreatePointerCast(&F, PointerType::getUnqual(Context), "", 2931 G2BB); 2932 (void)ReturnInst::Create(Context, G1BB); 2933 (void)ReturnInst::Create(Context, G2BB); 2934 2935 // Create f -ref-> g1 and f -ref-> g2. 2936 (void)CastInst::CreatePointerCast(G1, PointerType::getUnqual(Context), "", 2937 F.getEntryBlock().begin()); 2938 (void)CastInst::CreatePointerCast(G2, PointerType::getUnqual(Context), "", 2939 F.getEntryBlock().begin()); 2940 2941 EXPECT_FALSE(verifyModule(*M, &errs())); 2942 2943 CG.addSplitRefRecursiveFunctions(F, SmallVector<Function *, 1>({G1, G2})); 2944 2945 LazyCallGraph::Node *G1N = CG.lookup(*G1); 2946 EXPECT_TRUE(G1N); 2947 LazyCallGraph::Node *G2N = CG.lookup(*G2); 2948 EXPECT_TRUE(G2N); 2949 2950 I = CG.postorder_ref_scc_begin(); 2951 LazyCallGraph::RefSCC *RC = &*I++; 2952 EXPECT_EQ(RC, ORC); 2953 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2954 2955 // Order doesn't matter for sibling SCCs. 2956 EXPECT_EQ(3, RC->size()); 2957 EXPECT_EQ(&CG.lookupSCC(FN)->getOuterRefSCC(), RC); 2958 EXPECT_EQ(&CG.lookupSCC(*G1N)->getOuterRefSCC(), RC); 2959 EXPECT_EQ(&CG.lookupSCC(*G2N)->getOuterRefSCC(), RC); 2960 EXPECT_EQ(RC, CG.lookupRefSCC(*G1N)); 2961 EXPECT_EQ(RC, CG.lookupRefSCC(*G2N)); 2962 } 2963 2964 TEST(LazyCallGraphTest, AddSplitFunctions5) { 2965 LLVMContext Context; 2966 std::unique_ptr<Module> M = 2967 parseAssembly(Context, "define void @f() {\n" 2968 " %1 = bitcast void ()* @f2 to i8*\n" 2969 " ret void\n" 2970 "}\n" 2971 "define void @f2() {\n" 2972 " call void @f()\n" 2973 " ret void\n" 2974 "}\n"); 2975 LazyCallGraph CG = buildCG(*M); 2976 2977 Function &F = lookupFunction(*M, "f"); 2978 LazyCallGraph::Node &FN = CG.get(F); 2979 Function &F2 = lookupFunction(*M, "f2"); 2980 LazyCallGraph::Node &F2N = CG.get(F); 2981 2982 // Force the graph to be fully expanded. 2983 CG.buildRefSCCs(); 2984 auto I = CG.postorder_ref_scc_begin(); 2985 LazyCallGraph::RefSCC *ORC = &*I++; 2986 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2987 2988 auto *G1 = Function::Create(F.getFunctionType(), F.getLinkage(), 2989 F.getAddressSpace(), "g1", F.getParent()); 2990 auto *G2 = Function::Create(F.getFunctionType(), F.getLinkage(), 2991 F.getAddressSpace(), "g2", F.getParent()); 2992 BasicBlock *G1BB = BasicBlock::Create(Context, "", G1); 2993 BasicBlock *G2BB = BasicBlock::Create(Context, "", G2); 2994 // Create g1 -ref-> g2 and g2 -ref-> g1. 2995 (void)CastInst::CreatePointerCast(G2, PointerType::getUnqual(Context), "", 2996 G1BB); 2997 (void)CastInst::CreatePointerCast(G1, PointerType::getUnqual(Context), "", 2998 G2BB); 2999 // Create g2 -ref-> f2. 3000 (void)CastInst::CreatePointerCast(&F2, PointerType::getUnqual(Context), "", 3001 G2BB); 3002 (void)ReturnInst::Create(Context, G1BB); 3003 (void)ReturnInst::Create(Context, G2BB); 3004 3005 // Create f -ref-> g1 and f -ref-> g2. 3006 (void)CastInst::CreatePointerCast(G1, PointerType::getUnqual(Context), "", 3007 F.getEntryBlock().begin()); 3008 (void)CastInst::CreatePointerCast(G2, PointerType::getUnqual(Context), "", 3009 F.getEntryBlock().begin()); 3010 3011 EXPECT_FALSE(verifyModule(*M, &errs())); 3012 3013 CG.addSplitRefRecursiveFunctions(F, SmallVector<Function *, 1>({G1, G2})); 3014 3015 LazyCallGraph::Node *G1N = CG.lookup(*G1); 3016 EXPECT_TRUE(G1N); 3017 LazyCallGraph::Node *G2N = CG.lookup(*G2); 3018 EXPECT_TRUE(G2N); 3019 3020 I = CG.postorder_ref_scc_begin(); 3021 LazyCallGraph::RefSCC *RC = &*I++; 3022 EXPECT_EQ(4, RC->size()); 3023 EXPECT_EQ(RC, ORC); 3024 EXPECT_EQ(RC, CG.lookupRefSCC(*G1N)); 3025 EXPECT_EQ(RC, CG.lookupRefSCC(*G2N)); 3026 EXPECT_EQ(RC, CG.lookupRefSCC(FN)); 3027 EXPECT_EQ(RC, CG.lookupRefSCC(F2N)); 3028 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 3029 } 3030 } 3031