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