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