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