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