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