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