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(AC.isParentOf(BC)); 598 EXPECT_TRUE(ARC.isParentOf(CRC)); 599 EXPECT_TRUE(AC.isParentOf(CC)); 600 EXPECT_FALSE(ARC.isParentOf(DRC)); 601 EXPECT_FALSE(AC.isParentOf(DC)); 602 EXPECT_TRUE(ARC.isAncestorOf(DRC)); 603 EXPECT_TRUE(AC.isAncestorOf(DC)); 604 EXPECT_FALSE(DRC.isChildOf(ARC)); 605 EXPECT_FALSE(DC.isChildOf(AC)); 606 EXPECT_TRUE(DRC.isDescendantOf(ARC)); 607 EXPECT_TRUE(DC.isDescendantOf(AC)); 608 EXPECT_TRUE(DRC.isChildOf(BRC)); 609 EXPECT_TRUE(DC.isChildOf(BC)); 610 EXPECT_TRUE(DRC.isChildOf(CRC)); 611 EXPECT_TRUE(DC.isChildOf(CC)); 612 613 EXPECT_EQ(2, std::distance(A.begin(), A.end())); 614 ARC.insertOutgoingEdge(A, D, LazyCallGraph::Edge::Call); 615 EXPECT_EQ(3, std::distance(A.begin(), A.end())); 616 const LazyCallGraph::Edge &NewE = A[D]; 617 EXPECT_TRUE(NewE); 618 EXPECT_TRUE(NewE.isCall()); 619 EXPECT_EQ(&D, NewE.getNode()); 620 621 // Only the parent and child tests sholud have changed. The rest of the graph 622 // remains the same. 623 EXPECT_TRUE(ARC.isParentOf(DRC)); 624 EXPECT_TRUE(AC.isParentOf(DC)); 625 EXPECT_TRUE(ARC.isAncestorOf(DRC)); 626 EXPECT_TRUE(AC.isAncestorOf(DC)); 627 EXPECT_TRUE(DRC.isChildOf(ARC)); 628 EXPECT_TRUE(DC.isChildOf(AC)); 629 EXPECT_TRUE(DRC.isDescendantOf(ARC)); 630 EXPECT_TRUE(DC.isDescendantOf(AC)); 631 EXPECT_EQ(&AC, CG.lookupSCC(A)); 632 EXPECT_EQ(&BC, CG.lookupSCC(B)); 633 EXPECT_EQ(&CC, CG.lookupSCC(C)); 634 EXPECT_EQ(&DC, CG.lookupSCC(D)); 635 EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); 636 EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); 637 EXPECT_EQ(&CRC, CG.lookupRefSCC(C)); 638 EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); 639 640 ARC.switchOutgoingEdgeToRef(A, D); 641 EXPECT_FALSE(NewE.isCall()); 642 643 // Verify the reference graph remains the same but the SCC graph is updated. 644 EXPECT_TRUE(ARC.isParentOf(DRC)); 645 EXPECT_FALSE(AC.isParentOf(DC)); 646 EXPECT_TRUE(ARC.isAncestorOf(DRC)); 647 EXPECT_TRUE(AC.isAncestorOf(DC)); 648 EXPECT_TRUE(DRC.isChildOf(ARC)); 649 EXPECT_FALSE(DC.isChildOf(AC)); 650 EXPECT_TRUE(DRC.isDescendantOf(ARC)); 651 EXPECT_TRUE(DC.isDescendantOf(AC)); 652 EXPECT_EQ(&AC, CG.lookupSCC(A)); 653 EXPECT_EQ(&BC, CG.lookupSCC(B)); 654 EXPECT_EQ(&CC, CG.lookupSCC(C)); 655 EXPECT_EQ(&DC, CG.lookupSCC(D)); 656 EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); 657 EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); 658 EXPECT_EQ(&CRC, CG.lookupRefSCC(C)); 659 EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); 660 661 ARC.switchOutgoingEdgeToCall(A, D); 662 EXPECT_TRUE(NewE.isCall()); 663 664 // Verify the reference graph remains the same but the SCC graph is updated. 665 EXPECT_TRUE(ARC.isParentOf(DRC)); 666 EXPECT_TRUE(AC.isParentOf(DC)); 667 EXPECT_TRUE(ARC.isAncestorOf(DRC)); 668 EXPECT_TRUE(AC.isAncestorOf(DC)); 669 EXPECT_TRUE(DRC.isChildOf(ARC)); 670 EXPECT_TRUE(DC.isChildOf(AC)); 671 EXPECT_TRUE(DRC.isDescendantOf(ARC)); 672 EXPECT_TRUE(DC.isDescendantOf(AC)); 673 EXPECT_EQ(&AC, CG.lookupSCC(A)); 674 EXPECT_EQ(&BC, CG.lookupSCC(B)); 675 EXPECT_EQ(&CC, CG.lookupSCC(C)); 676 EXPECT_EQ(&DC, CG.lookupSCC(D)); 677 EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); 678 EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); 679 EXPECT_EQ(&CRC, CG.lookupRefSCC(C)); 680 EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); 681 682 ARC.removeOutgoingEdge(A, D); 683 EXPECT_EQ(2, std::distance(A.begin(), A.end())); 684 685 // Now the parent and child tests fail again but the rest remains the same. 686 EXPECT_FALSE(ARC.isParentOf(DRC)); 687 EXPECT_FALSE(AC.isParentOf(DC)); 688 EXPECT_TRUE(ARC.isAncestorOf(DRC)); 689 EXPECT_TRUE(AC.isAncestorOf(DC)); 690 EXPECT_FALSE(DRC.isChildOf(ARC)); 691 EXPECT_FALSE(DC.isChildOf(AC)); 692 EXPECT_TRUE(DRC.isDescendantOf(ARC)); 693 EXPECT_TRUE(DC.isDescendantOf(AC)); 694 EXPECT_EQ(&AC, CG.lookupSCC(A)); 695 EXPECT_EQ(&BC, CG.lookupSCC(B)); 696 EXPECT_EQ(&CC, CG.lookupSCC(C)); 697 EXPECT_EQ(&DC, CG.lookupSCC(D)); 698 EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); 699 EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); 700 EXPECT_EQ(&CRC, CG.lookupRefSCC(C)); 701 EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); 702 } 703 704 TEST(LazyCallGraphTest, IncomingEdgeInsertion) { 705 LLVMContext Context; 706 // We want to ensure we can add edges even across complex diamond graphs, so 707 // we use the diamond of triangles graph defined above. The ascii diagram is 708 // repeated here for easy reference. 709 // 710 // d1 | 711 // / \ | 712 // d3--d2 | 713 // / \ | 714 // b1 c1 | 715 // / \ / \ | 716 // b3--b2 c3--c2 | 717 // \ / | 718 // a1 | 719 // / \ | 720 // a3--a2 | 721 // 722 std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles); 723 LazyCallGraph CG(*M); 724 725 // Force the graph to be fully expanded. 726 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) 727 dbgs() << "Formed RefSCC: " << RC << "\n"; 728 729 LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1")); 730 LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2")); 731 LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3")); 732 LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1")); 733 LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2")); 734 LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3")); 735 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1")); 736 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2")); 737 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3")); 738 LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1")); 739 LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2")); 740 LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3")); 741 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A1); 742 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B1); 743 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C1); 744 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D1); 745 ASSERT_EQ(&ARC, CG.lookupRefSCC(A2)); 746 ASSERT_EQ(&ARC, CG.lookupRefSCC(A3)); 747 ASSERT_EQ(&BRC, CG.lookupRefSCC(B2)); 748 ASSERT_EQ(&BRC, CG.lookupRefSCC(B3)); 749 ASSERT_EQ(&CRC, CG.lookupRefSCC(C2)); 750 ASSERT_EQ(&CRC, CG.lookupRefSCC(C3)); 751 ASSERT_EQ(&DRC, CG.lookupRefSCC(D2)); 752 ASSERT_EQ(&DRC, CG.lookupRefSCC(D3)); 753 ASSERT_EQ(1, std::distance(D2.begin(), D2.end())); 754 755 // Add an edge to make the graph: 756 // 757 // d1 | 758 // / \ | 759 // d3--d2---. | 760 // / \ | | 761 // b1 c1 | | 762 // / \ / \ / | 763 // b3--b2 c3--c2 | 764 // \ / | 765 // a1 | 766 // / \ | 767 // a3--a2 | 768 auto MergedRCs = CRC.insertIncomingRefEdge(D2, C2); 769 // Make sure we connected the nodes. 770 for (LazyCallGraph::Edge E : D2) { 771 if (E.getNode() == &D3) 772 continue; 773 EXPECT_EQ(&C2, E.getNode()); 774 } 775 // And marked the D ref-SCC as no longer valid. 776 EXPECT_EQ(1u, MergedRCs.size()); 777 EXPECT_EQ(&DRC, MergedRCs[0]); 778 779 // Make sure we have the correct nodes in the SCC sets. 780 EXPECT_EQ(&ARC, CG.lookupRefSCC(A1)); 781 EXPECT_EQ(&ARC, CG.lookupRefSCC(A2)); 782 EXPECT_EQ(&ARC, CG.lookupRefSCC(A3)); 783 EXPECT_EQ(&BRC, CG.lookupRefSCC(B1)); 784 EXPECT_EQ(&BRC, CG.lookupRefSCC(B2)); 785 EXPECT_EQ(&BRC, CG.lookupRefSCC(B3)); 786 EXPECT_EQ(&CRC, CG.lookupRefSCC(C1)); 787 EXPECT_EQ(&CRC, CG.lookupRefSCC(C2)); 788 EXPECT_EQ(&CRC, CG.lookupRefSCC(C3)); 789 EXPECT_EQ(&CRC, CG.lookupRefSCC(D1)); 790 EXPECT_EQ(&CRC, CG.lookupRefSCC(D2)); 791 EXPECT_EQ(&CRC, CG.lookupRefSCC(D3)); 792 793 // And that ancestry tests have been updated. 794 EXPECT_TRUE(ARC.isParentOf(CRC)); 795 EXPECT_TRUE(BRC.isParentOf(CRC)); 796 797 // And verify the post-order walk reflects the updated structure. 798 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); 799 ASSERT_NE(I, E); 800 EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I; 801 ASSERT_NE(++I, E); 802 EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I; 803 ASSERT_NE(++I, E); 804 EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I; 805 EXPECT_EQ(++I, E); 806 } 807 808 TEST(LazyCallGraphTest, IncomingEdgeInsertionMidTraversal) { 809 LLVMContext Context; 810 // This is the same fundamental test as the previous, but we perform it 811 // having only partially walked the RefSCCs of the graph. 812 std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles); 813 LazyCallGraph CG(*M); 814 815 // Walk the RefSCCs until we find the one containing 'c1'. 816 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); 817 ASSERT_NE(I, E); 818 LazyCallGraph::RefSCC &DRC = *I; 819 ASSERT_NE(&DRC, nullptr); 820 ++I; 821 ASSERT_NE(I, E); 822 LazyCallGraph::RefSCC &CRC = *I; 823 ASSERT_NE(&CRC, nullptr); 824 825 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a1"))); 826 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a2"))); 827 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a3"))); 828 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b1"))); 829 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b2"))); 830 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b3"))); 831 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1")); 832 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2")); 833 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3")); 834 LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1")); 835 LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2")); 836 LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3")); 837 ASSERT_EQ(&CRC, CG.lookupRefSCC(C1)); 838 ASSERT_EQ(&CRC, CG.lookupRefSCC(C2)); 839 ASSERT_EQ(&CRC, CG.lookupRefSCC(C3)); 840 ASSERT_EQ(&DRC, CG.lookupRefSCC(D1)); 841 ASSERT_EQ(&DRC, CG.lookupRefSCC(D2)); 842 ASSERT_EQ(&DRC, CG.lookupRefSCC(D3)); 843 ASSERT_EQ(1, std::distance(D2.begin(), D2.end())); 844 845 auto MergedRCs = CRC.insertIncomingRefEdge(D2, C2); 846 // Make sure we connected the nodes. 847 for (LazyCallGraph::Edge E : D2) { 848 if (E.getNode() == &D3) 849 continue; 850 EXPECT_EQ(&C2, E.getNode()); 851 } 852 // And marked the D ref-SCC as no longer valid. 853 EXPECT_EQ(1u, MergedRCs.size()); 854 EXPECT_EQ(&DRC, MergedRCs[0]); 855 856 // Make sure we have the correct nodes in the RefSCCs. 857 EXPECT_EQ(&CRC, CG.lookupRefSCC(C1)); 858 EXPECT_EQ(&CRC, CG.lookupRefSCC(C2)); 859 EXPECT_EQ(&CRC, CG.lookupRefSCC(C3)); 860 EXPECT_EQ(&CRC, CG.lookupRefSCC(D1)); 861 EXPECT_EQ(&CRC, CG.lookupRefSCC(D2)); 862 EXPECT_EQ(&CRC, CG.lookupRefSCC(D3)); 863 864 // Verify that the post-order walk reflects the updated but still incomplete 865 // structure. 866 auto J = CG.postorder_ref_scc_begin(); 867 EXPECT_NE(J, E); 868 EXPECT_EQ(&CRC, &*J) << "Actual RefSCC: " << *J; 869 EXPECT_EQ(I, J); 870 871 // Check that we can form the last two RefSCCs now, and even that we can do 872 // it with alternating iterators. 873 ++J; 874 EXPECT_NE(J, E); 875 LazyCallGraph::RefSCC &BRC = *J; 876 EXPECT_NE(&BRC, nullptr); 877 EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b1")))); 878 EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b2")))); 879 EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b3")))); 880 EXPECT_TRUE(BRC.isParentOf(CRC)); 881 ++I; 882 EXPECT_EQ(J, I); 883 EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I; 884 885 // Increment I this time to form the new RefSCC, flopping back to the first 886 // iterator. 887 ++I; 888 EXPECT_NE(I, E); 889 LazyCallGraph::RefSCC &ARC = *I; 890 EXPECT_NE(&ARC, nullptr); 891 EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a1")))); 892 EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a2")))); 893 EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a3")))); 894 EXPECT_TRUE(ARC.isParentOf(CRC)); 895 ++J; 896 EXPECT_EQ(I, J); 897 EXPECT_EQ(&ARC, &*J) << "Actual RefSCC: " << *J; 898 ++I; 899 EXPECT_EQ(E, I); 900 ++J; 901 EXPECT_EQ(E, J); 902 } 903 904 TEST(LazyCallGraphTest, IncomingEdgeInsertionRefGraph) { 905 LLVMContext Context; 906 // Another variation of the above test but with all the edges switched to 907 // references rather than calls. 908 std::unique_ptr<Module> M = 909 parseAssembly(Context, DiamondOfTrianglesRefGraph); 910 LazyCallGraph CG(*M); 911 912 // Force the graph to be fully expanded. 913 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) 914 dbgs() << "Formed RefSCC: " << RC << "\n"; 915 916 LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1")); 917 LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2")); 918 LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3")); 919 LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1")); 920 LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2")); 921 LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3")); 922 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1")); 923 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2")); 924 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3")); 925 LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1")); 926 LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2")); 927 LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3")); 928 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A1); 929 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B1); 930 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C1); 931 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D1); 932 ASSERT_EQ(&ARC, CG.lookupRefSCC(A2)); 933 ASSERT_EQ(&ARC, CG.lookupRefSCC(A3)); 934 ASSERT_EQ(&BRC, CG.lookupRefSCC(B2)); 935 ASSERT_EQ(&BRC, CG.lookupRefSCC(B3)); 936 ASSERT_EQ(&CRC, CG.lookupRefSCC(C2)); 937 ASSERT_EQ(&CRC, CG.lookupRefSCC(C3)); 938 ASSERT_EQ(&DRC, CG.lookupRefSCC(D2)); 939 ASSERT_EQ(&DRC, CG.lookupRefSCC(D3)); 940 ASSERT_EQ(1, std::distance(D2.begin(), D2.end())); 941 942 // Add an edge to make the graph: 943 // 944 // d1 | 945 // / \ | 946 // d3--d2---. | 947 // / \ | | 948 // b1 c1 | | 949 // / \ / \ / | 950 // b3--b2 c3--c2 | 951 // \ / | 952 // a1 | 953 // / \ | 954 // a3--a2 | 955 auto MergedRCs = CRC.insertIncomingRefEdge(D2, C2); 956 // Make sure we connected the nodes. 957 for (LazyCallGraph::Edge E : D2) { 958 if (E.getNode() == &D3) 959 continue; 960 EXPECT_EQ(&C2, E.getNode()); 961 } 962 // And marked the D ref-SCC as no longer valid. 963 EXPECT_EQ(1u, MergedRCs.size()); 964 EXPECT_EQ(&DRC, MergedRCs[0]); 965 966 // Make sure we have the correct nodes in the SCC sets. 967 EXPECT_EQ(&ARC, CG.lookupRefSCC(A1)); 968 EXPECT_EQ(&ARC, CG.lookupRefSCC(A2)); 969 EXPECT_EQ(&ARC, CG.lookupRefSCC(A3)); 970 EXPECT_EQ(&BRC, CG.lookupRefSCC(B1)); 971 EXPECT_EQ(&BRC, CG.lookupRefSCC(B2)); 972 EXPECT_EQ(&BRC, CG.lookupRefSCC(B3)); 973 EXPECT_EQ(&CRC, CG.lookupRefSCC(C1)); 974 EXPECT_EQ(&CRC, CG.lookupRefSCC(C2)); 975 EXPECT_EQ(&CRC, CG.lookupRefSCC(C3)); 976 EXPECT_EQ(&CRC, CG.lookupRefSCC(D1)); 977 EXPECT_EQ(&CRC, CG.lookupRefSCC(D2)); 978 EXPECT_EQ(&CRC, CG.lookupRefSCC(D3)); 979 980 // And that ancestry tests have been updated. 981 EXPECT_TRUE(ARC.isParentOf(CRC)); 982 EXPECT_TRUE(BRC.isParentOf(CRC)); 983 984 // And verify the post-order walk reflects the updated structure. 985 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); 986 ASSERT_NE(I, E); 987 EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I; 988 ASSERT_NE(++I, E); 989 EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I; 990 ASSERT_NE(++I, E); 991 EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I; 992 EXPECT_EQ(++I, E); 993 } 994 995 TEST(LazyCallGraphTest, IncomingEdgeInsertionLargeCallCycle) { 996 LLVMContext Context; 997 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n" 998 "entry:\n" 999 " call void @b()\n" 1000 " ret void\n" 1001 "}\n" 1002 "define void @b() {\n" 1003 "entry:\n" 1004 " call void @c()\n" 1005 " ret void\n" 1006 "}\n" 1007 "define void @c() {\n" 1008 "entry:\n" 1009 " call void @d()\n" 1010 " ret void\n" 1011 "}\n" 1012 "define void @d() {\n" 1013 "entry:\n" 1014 " ret void\n" 1015 "}\n"); 1016 LazyCallGraph CG(*M); 1017 1018 // Force the graph to be fully expanded. 1019 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) 1020 dbgs() << "Formed RefSCC: " << RC << "\n"; 1021 1022 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 1023 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 1024 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 1025 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); 1026 LazyCallGraph::SCC &AC = *CG.lookupSCC(A); 1027 LazyCallGraph::SCC &BC = *CG.lookupSCC(B); 1028 LazyCallGraph::SCC &CC = *CG.lookupSCC(C); 1029 LazyCallGraph::SCC &DC = *CG.lookupSCC(D); 1030 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A); 1031 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B); 1032 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C); 1033 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D); 1034 1035 // Connect the top to the bottom forming a large RefSCC made up mostly of calls. 1036 auto MergedRCs = ARC.insertIncomingRefEdge(D, A); 1037 // Make sure we connected the nodes. 1038 EXPECT_NE(D.begin(), D.end()); 1039 EXPECT_EQ(&A, D.begin()->getNode()); 1040 1041 // Check that we have the dead RCs, but ignore the order. 1042 EXPECT_EQ(3u, MergedRCs.size()); 1043 EXPECT_NE(find(MergedRCs, &BRC), MergedRCs.end()); 1044 EXPECT_NE(find(MergedRCs, &CRC), MergedRCs.end()); 1045 EXPECT_NE(find(MergedRCs, &DRC), MergedRCs.end()); 1046 1047 // Make sure the nodes point to the right place now. 1048 EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); 1049 EXPECT_EQ(&ARC, CG.lookupRefSCC(B)); 1050 EXPECT_EQ(&ARC, CG.lookupRefSCC(C)); 1051 EXPECT_EQ(&ARC, CG.lookupRefSCC(D)); 1052 1053 // Check that the SCCs are in postorder. 1054 EXPECT_EQ(4, ARC.size()); 1055 EXPECT_EQ(&DC, &ARC[0]); 1056 EXPECT_EQ(&CC, &ARC[1]); 1057 EXPECT_EQ(&BC, &ARC[2]); 1058 EXPECT_EQ(&AC, &ARC[3]); 1059 1060 // And verify the post-order walk reflects the updated structure. 1061 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); 1062 ASSERT_NE(I, E); 1063 EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I; 1064 EXPECT_EQ(++I, E); 1065 } 1066 1067 TEST(LazyCallGraphTest, IncomingEdgeInsertionLargeRefCycle) { 1068 LLVMContext Context; 1069 std::unique_ptr<Module> M = 1070 parseAssembly(Context, "define void @a() {\n" 1071 "entry:\n" 1072 " %p = alloca void ()*\n" 1073 " store void ()* @b, void ()** %p\n" 1074 " ret void\n" 1075 "}\n" 1076 "define void @b() {\n" 1077 "entry:\n" 1078 " %p = alloca void ()*\n" 1079 " store void ()* @c, void ()** %p\n" 1080 " ret void\n" 1081 "}\n" 1082 "define void @c() {\n" 1083 "entry:\n" 1084 " %p = alloca void ()*\n" 1085 " store void ()* @d, void ()** %p\n" 1086 " ret void\n" 1087 "}\n" 1088 "define void @d() {\n" 1089 "entry:\n" 1090 " ret void\n" 1091 "}\n"); 1092 LazyCallGraph CG(*M); 1093 1094 // Force the graph to be fully expanded. 1095 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) 1096 dbgs() << "Formed RefSCC: " << RC << "\n"; 1097 1098 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 1099 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 1100 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 1101 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); 1102 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A); 1103 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B); 1104 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C); 1105 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D); 1106 1107 // Connect the top to the bottom forming a large RefSCC made up just of 1108 // references. 1109 auto MergedRCs = ARC.insertIncomingRefEdge(D, A); 1110 // Make sure we connected the nodes. 1111 EXPECT_NE(D.begin(), D.end()); 1112 EXPECT_EQ(&A, D.begin()->getNode()); 1113 1114 // Check that we have the dead RCs, but ignore the order. 1115 EXPECT_EQ(3u, MergedRCs.size()); 1116 EXPECT_NE(find(MergedRCs, &BRC), MergedRCs.end()); 1117 EXPECT_NE(find(MergedRCs, &CRC), MergedRCs.end()); 1118 EXPECT_NE(find(MergedRCs, &DRC), MergedRCs.end()); 1119 1120 // Make sure the nodes point to the right place now. 1121 EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); 1122 EXPECT_EQ(&ARC, CG.lookupRefSCC(B)); 1123 EXPECT_EQ(&ARC, CG.lookupRefSCC(C)); 1124 EXPECT_EQ(&ARC, CG.lookupRefSCC(D)); 1125 1126 // And verify the post-order walk reflects the updated structure. 1127 auto I = CG.postorder_ref_scc_begin(), End = CG.postorder_ref_scc_end(); 1128 ASSERT_NE(I, End); 1129 EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I; 1130 EXPECT_EQ(++I, End); 1131 } 1132 1133 TEST(LazyCallGraphTest, InlineAndDeleteFunction) { 1134 LLVMContext Context; 1135 // We want to ensure we can delete nodes from relatively complex graphs and 1136 // so use the diamond of triangles graph defined above. 1137 // 1138 // The ascii diagram is repeated here for easy reference. 1139 // 1140 // d1 | 1141 // / \ | 1142 // d3--d2 | 1143 // / \ | 1144 // b1 c1 | 1145 // / \ / \ | 1146 // b3--b2 c3--c2 | 1147 // \ / | 1148 // a1 | 1149 // / \ | 1150 // a3--a2 | 1151 // 1152 std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles); 1153 LazyCallGraph CG(*M); 1154 1155 // Force the graph to be fully expanded. 1156 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) 1157 dbgs() << "Formed RefSCC: " << RC << "\n"; 1158 1159 LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1")); 1160 LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2")); 1161 LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3")); 1162 LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1")); 1163 LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2")); 1164 LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3")); 1165 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1")); 1166 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2")); 1167 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3")); 1168 LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1")); 1169 LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2")); 1170 LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3")); 1171 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A1); 1172 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B1); 1173 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C1); 1174 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D1); 1175 ASSERT_EQ(&ARC, CG.lookupRefSCC(A2)); 1176 ASSERT_EQ(&ARC, CG.lookupRefSCC(A3)); 1177 ASSERT_EQ(&BRC, CG.lookupRefSCC(B2)); 1178 ASSERT_EQ(&BRC, CG.lookupRefSCC(B3)); 1179 ASSERT_EQ(&CRC, CG.lookupRefSCC(C2)); 1180 ASSERT_EQ(&CRC, CG.lookupRefSCC(C3)); 1181 ASSERT_EQ(&DRC, CG.lookupRefSCC(D2)); 1182 ASSERT_EQ(&DRC, CG.lookupRefSCC(D3)); 1183 ASSERT_EQ(1, std::distance(D2.begin(), D2.end())); 1184 1185 // Delete d2 from the graph, as if it had been inlined. 1186 // 1187 // d1 | 1188 // / / | 1189 // d3--. | 1190 // / \ | 1191 // b1 c1 | 1192 // / \ / \ | 1193 // b3--b2 c3--c2 | 1194 // \ / | 1195 // a1 | 1196 // / \ | 1197 // a3--a2 | 1198 1199 Function &D2F = D2.getFunction(); 1200 CallInst *C1Call = nullptr, *D1Call = nullptr; 1201 for (User *U : D2F.users()) { 1202 CallInst *CI = dyn_cast<CallInst>(U); 1203 ASSERT_TRUE(CI) << "Expected a call: " << *U; 1204 if (CI->getParent()->getParent() == &C1.getFunction()) { 1205 ASSERT_EQ(nullptr, C1Call) << "Found too many C1 calls: " << *CI; 1206 C1Call = CI; 1207 } else if (CI->getParent()->getParent() == &D1.getFunction()) { 1208 ASSERT_EQ(nullptr, D1Call) << "Found too many D1 calls: " << *CI; 1209 D1Call = CI; 1210 } else { 1211 FAIL() << "Found an unexpected call instruction: " << *CI; 1212 } 1213 } 1214 ASSERT_NE(C1Call, nullptr); 1215 ASSERT_NE(D1Call, nullptr); 1216 ASSERT_EQ(&D2F, C1Call->getCalledFunction()); 1217 ASSERT_EQ(&D2F, D1Call->getCalledFunction()); 1218 C1Call->setCalledFunction(&D3.getFunction()); 1219 D1Call->setCalledFunction(&D3.getFunction()); 1220 ASSERT_EQ(0u, D2F.getNumUses()); 1221 1222 // Insert new edges first. 1223 CRC.insertTrivialCallEdge(C1, D3); 1224 DRC.insertTrivialCallEdge(D1, D3); 1225 1226 // Then remove the old ones. 1227 LazyCallGraph::SCC &DC = *CG.lookupSCC(D2); 1228 auto NewCs = DRC.switchInternalEdgeToRef(D1, D2); 1229 EXPECT_EQ(&DC, CG.lookupSCC(D2)); 1230 EXPECT_EQ(NewCs.end(), std::next(NewCs.begin())); 1231 LazyCallGraph::SCC &NewDC = *NewCs.begin(); 1232 EXPECT_EQ(&NewDC, CG.lookupSCC(D1)); 1233 EXPECT_EQ(&NewDC, CG.lookupSCC(D3)); 1234 auto NewRCs = DRC.removeInternalRefEdge(D1, D2); 1235 EXPECT_EQ(&DRC, CG.lookupRefSCC(D2)); 1236 EXPECT_EQ(NewRCs.end(), std::next(NewRCs.begin())); 1237 LazyCallGraph::RefSCC &NewDRC = **NewRCs.begin(); 1238 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1)); 1239 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3)); 1240 EXPECT_FALSE(NewDRC.isParentOf(DRC)); 1241 EXPECT_TRUE(CRC.isParentOf(DRC)); 1242 EXPECT_TRUE(CRC.isParentOf(NewDRC)); 1243 EXPECT_TRUE(DRC.isParentOf(NewDRC)); 1244 CRC.removeOutgoingEdge(C1, D2); 1245 EXPECT_FALSE(CRC.isParentOf(DRC)); 1246 EXPECT_TRUE(CRC.isParentOf(NewDRC)); 1247 EXPECT_TRUE(DRC.isParentOf(NewDRC)); 1248 1249 // Now that we've updated the call graph, D2 is dead, so remove it. 1250 CG.removeDeadFunction(D2F); 1251 1252 // Check that the graph still looks the same. 1253 EXPECT_EQ(&ARC, CG.lookupRefSCC(A1)); 1254 EXPECT_EQ(&ARC, CG.lookupRefSCC(A2)); 1255 EXPECT_EQ(&ARC, CG.lookupRefSCC(A3)); 1256 EXPECT_EQ(&BRC, CG.lookupRefSCC(B1)); 1257 EXPECT_EQ(&BRC, CG.lookupRefSCC(B2)); 1258 EXPECT_EQ(&BRC, CG.lookupRefSCC(B3)); 1259 EXPECT_EQ(&CRC, CG.lookupRefSCC(C1)); 1260 EXPECT_EQ(&CRC, CG.lookupRefSCC(C2)); 1261 EXPECT_EQ(&CRC, CG.lookupRefSCC(C3)); 1262 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1)); 1263 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3)); 1264 EXPECT_TRUE(CRC.isParentOf(NewDRC)); 1265 1266 // Verify the post-order walk hasn't changed. 1267 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); 1268 ASSERT_NE(I, E); 1269 EXPECT_EQ(&NewDRC, &*I) << "Actual RefSCC: " << *I; 1270 ASSERT_NE(++I, E); 1271 EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I; 1272 ASSERT_NE(++I, E); 1273 EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I; 1274 ASSERT_NE(++I, E); 1275 EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I; 1276 EXPECT_EQ(++I, E); 1277 } 1278 1279 TEST(LazyCallGraphTest, InlineAndDeleteFunctionMidTraversal) { 1280 LLVMContext Context; 1281 // This is the same fundamental test as the previous, but we perform it 1282 // having only partially walked the RefSCCs of the graph. 1283 // 1284 // The ascii diagram is repeated here for easy reference. 1285 // 1286 // d1 | 1287 // / \ | 1288 // d3--d2 | 1289 // / \ | 1290 // b1 c1 | 1291 // / \ / \ | 1292 // b3--b2 c3--c2 | 1293 // \ / | 1294 // a1 | 1295 // / \ | 1296 // a3--a2 | 1297 // 1298 std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles); 1299 LazyCallGraph CG(*M); 1300 1301 // Walk the RefSCCs until we find the one containing 'c1'. 1302 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); 1303 ASSERT_NE(I, E); 1304 LazyCallGraph::RefSCC &DRC = *I; 1305 ASSERT_NE(&DRC, nullptr); 1306 ++I; 1307 ASSERT_NE(I, E); 1308 LazyCallGraph::RefSCC &CRC = *I; 1309 ASSERT_NE(&CRC, nullptr); 1310 1311 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a1"))); 1312 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a2"))); 1313 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a3"))); 1314 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b1"))); 1315 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b2"))); 1316 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b3"))); 1317 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1")); 1318 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2")); 1319 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3")); 1320 LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1")); 1321 LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2")); 1322 LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3")); 1323 ASSERT_EQ(&CRC, CG.lookupRefSCC(C1)); 1324 ASSERT_EQ(&CRC, CG.lookupRefSCC(C2)); 1325 ASSERT_EQ(&CRC, CG.lookupRefSCC(C3)); 1326 ASSERT_EQ(&DRC, CG.lookupRefSCC(D1)); 1327 ASSERT_EQ(&DRC, CG.lookupRefSCC(D2)); 1328 ASSERT_EQ(&DRC, CG.lookupRefSCC(D3)); 1329 ASSERT_EQ(1, std::distance(D2.begin(), D2.end())); 1330 1331 // Delete d2 from the graph, as if it had been inlined. 1332 // 1333 // d1 | 1334 // / / | 1335 // d3--. | 1336 // / \ | 1337 // b1 c1 | 1338 // / \ / \ | 1339 // b3--b2 c3--c2 | 1340 // \ / | 1341 // a1 | 1342 // / \ | 1343 // a3--a2 | 1344 1345 Function &D2F = D2.getFunction(); 1346 CallInst *C1Call = nullptr, *D1Call = nullptr; 1347 for (User *U : D2F.users()) { 1348 CallInst *CI = dyn_cast<CallInst>(U); 1349 ASSERT_TRUE(CI) << "Expected a call: " << *U; 1350 if (CI->getParent()->getParent() == &C1.getFunction()) { 1351 ASSERT_EQ(nullptr, C1Call) << "Found too many C1 calls: " << *CI; 1352 C1Call = CI; 1353 } else if (CI->getParent()->getParent() == &D1.getFunction()) { 1354 ASSERT_EQ(nullptr, D1Call) << "Found too many D1 calls: " << *CI; 1355 D1Call = CI; 1356 } else { 1357 FAIL() << "Found an unexpected call instruction: " << *CI; 1358 } 1359 } 1360 ASSERT_NE(C1Call, nullptr); 1361 ASSERT_NE(D1Call, nullptr); 1362 ASSERT_EQ(&D2F, C1Call->getCalledFunction()); 1363 ASSERT_EQ(&D2F, D1Call->getCalledFunction()); 1364 C1Call->setCalledFunction(&D3.getFunction()); 1365 D1Call->setCalledFunction(&D3.getFunction()); 1366 ASSERT_EQ(0u, D2F.getNumUses()); 1367 1368 // Insert new edges first. 1369 CRC.insertTrivialCallEdge(C1, D3); 1370 DRC.insertTrivialCallEdge(D1, D3); 1371 1372 // Then remove the old ones. 1373 LazyCallGraph::SCC &DC = *CG.lookupSCC(D2); 1374 auto NewCs = DRC.switchInternalEdgeToRef(D1, D2); 1375 EXPECT_EQ(&DC, CG.lookupSCC(D2)); 1376 EXPECT_EQ(NewCs.end(), std::next(NewCs.begin())); 1377 LazyCallGraph::SCC &NewDC = *NewCs.begin(); 1378 EXPECT_EQ(&NewDC, CG.lookupSCC(D1)); 1379 EXPECT_EQ(&NewDC, CG.lookupSCC(D3)); 1380 auto NewRCs = DRC.removeInternalRefEdge(D1, D2); 1381 EXPECT_EQ(&DRC, CG.lookupRefSCC(D2)); 1382 EXPECT_EQ(NewRCs.end(), std::next(NewRCs.begin())); 1383 LazyCallGraph::RefSCC &NewDRC = **NewRCs.begin(); 1384 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1)); 1385 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3)); 1386 EXPECT_FALSE(NewDRC.isParentOf(DRC)); 1387 EXPECT_TRUE(CRC.isParentOf(DRC)); 1388 EXPECT_TRUE(CRC.isParentOf(NewDRC)); 1389 EXPECT_TRUE(DRC.isParentOf(NewDRC)); 1390 CRC.removeOutgoingEdge(C1, D2); 1391 EXPECT_FALSE(CRC.isParentOf(DRC)); 1392 EXPECT_TRUE(CRC.isParentOf(NewDRC)); 1393 EXPECT_TRUE(DRC.isParentOf(NewDRC)); 1394 1395 // Now that we've updated the call graph, D2 is dead, so remove it. 1396 CG.removeDeadFunction(D2F); 1397 1398 // Check that the graph still looks the same. 1399 EXPECT_EQ(&CRC, CG.lookupRefSCC(C1)); 1400 EXPECT_EQ(&CRC, CG.lookupRefSCC(C2)); 1401 EXPECT_EQ(&CRC, CG.lookupRefSCC(C3)); 1402 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1)); 1403 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3)); 1404 EXPECT_TRUE(CRC.isParentOf(NewDRC)); 1405 1406 // Verify that the post-order walk reflects the updated but still incomplete 1407 // structure. 1408 auto J = CG.postorder_ref_scc_begin(); 1409 EXPECT_NE(J, E); 1410 EXPECT_EQ(&NewDRC, &*J) << "Actual RefSCC: " << *J; 1411 ++J; 1412 EXPECT_NE(J, E); 1413 EXPECT_EQ(&CRC, &*J) << "Actual RefSCC: " << *J; 1414 EXPECT_EQ(I, J); 1415 1416 // Check that we can form the last two RefSCCs now, and even that we can do 1417 // it with alternating iterators. 1418 ++J; 1419 EXPECT_NE(J, E); 1420 LazyCallGraph::RefSCC &BRC = *J; 1421 EXPECT_NE(&BRC, nullptr); 1422 EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b1")))); 1423 EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b2")))); 1424 EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b3")))); 1425 EXPECT_TRUE(BRC.isParentOf(NewDRC)); 1426 ++I; 1427 EXPECT_EQ(J, I); 1428 EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I; 1429 1430 // Increment I this time to form the new RefSCC, flopping back to the first 1431 // iterator. 1432 ++I; 1433 EXPECT_NE(I, E); 1434 LazyCallGraph::RefSCC &ARC = *I; 1435 EXPECT_NE(&ARC, nullptr); 1436 EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a1")))); 1437 EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a2")))); 1438 EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a3")))); 1439 EXPECT_TRUE(ARC.isParentOf(BRC)); 1440 EXPECT_TRUE(ARC.isParentOf(CRC)); 1441 ++J; 1442 EXPECT_EQ(I, J); 1443 EXPECT_EQ(&ARC, &*J) << "Actual RefSCC: " << *J; 1444 ++I; 1445 EXPECT_EQ(E, I); 1446 ++J; 1447 EXPECT_EQ(E, J); 1448 } 1449 1450 TEST(LazyCallGraphTest, InternalEdgeMutation) { 1451 LLVMContext Context; 1452 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n" 1453 "entry:\n" 1454 " call void @b()\n" 1455 " ret void\n" 1456 "}\n" 1457 "define void @b() {\n" 1458 "entry:\n" 1459 " call void @c()\n" 1460 " ret void\n" 1461 "}\n" 1462 "define void @c() {\n" 1463 "entry:\n" 1464 " call void @a()\n" 1465 " ret void\n" 1466 "}\n"); 1467 LazyCallGraph CG(*M); 1468 1469 // Force the graph to be fully expanded. 1470 auto I = CG.postorder_ref_scc_begin(); 1471 LazyCallGraph::RefSCC &RC = *I++; 1472 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 1473 1474 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 1475 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 1476 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 1477 EXPECT_EQ(&RC, CG.lookupRefSCC(A)); 1478 EXPECT_EQ(&RC, CG.lookupRefSCC(B)); 1479 EXPECT_EQ(&RC, CG.lookupRefSCC(C)); 1480 EXPECT_EQ(1, RC.size()); 1481 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(A)); 1482 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(B)); 1483 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(C)); 1484 1485 // Insert an edge from 'a' to 'c'. Nothing changes about the graph. 1486 RC.insertInternalRefEdge(A, C); 1487 EXPECT_EQ(2, std::distance(A.begin(), A.end())); 1488 EXPECT_EQ(&RC, CG.lookupRefSCC(A)); 1489 EXPECT_EQ(&RC, CG.lookupRefSCC(B)); 1490 EXPECT_EQ(&RC, CG.lookupRefSCC(C)); 1491 EXPECT_EQ(1, RC.size()); 1492 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(A)); 1493 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(B)); 1494 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(C)); 1495 1496 // Switch the call edge from 'b' to 'c' to a ref edge. This will break the 1497 // call cycle and cause us to form more SCCs. The RefSCC will remain the same 1498 // though. 1499 auto NewCs = RC.switchInternalEdgeToRef(B, C); 1500 EXPECT_EQ(&RC, CG.lookupRefSCC(A)); 1501 EXPECT_EQ(&RC, CG.lookupRefSCC(B)); 1502 EXPECT_EQ(&RC, CG.lookupRefSCC(C)); 1503 auto J = RC.begin(); 1504 // The SCCs must be in *post-order* which means successors before 1505 // predecessors. At this point we have call edges from C to A and from A to 1506 // B. The only valid postorder is B, A, C. 1507 EXPECT_EQ(&*J++, CG.lookupSCC(B)); 1508 EXPECT_EQ(&*J++, CG.lookupSCC(A)); 1509 EXPECT_EQ(&*J++, CG.lookupSCC(C)); 1510 EXPECT_EQ(RC.end(), J); 1511 // And the returned range must be the slice of this sequence containing new 1512 // SCCs. 1513 EXPECT_EQ(RC.begin(), NewCs.begin()); 1514 EXPECT_EQ(std::prev(RC.end()), NewCs.end()); 1515 1516 // Test turning the ref edge from A to C into a call edge. This will form an 1517 // SCC out of A and C. Since we previously had a call edge from C to A, the 1518 // C SCC should be preserved and have A merged into it while the A SCC should 1519 // be invalidated. 1520 LazyCallGraph::SCC &AC = *CG.lookupSCC(A); 1521 LazyCallGraph::SCC &CC = *CG.lookupSCC(C); 1522 auto InvalidatedSCCs = RC.switchInternalEdgeToCall(A, C); 1523 ASSERT_EQ(1u, InvalidatedSCCs.size()); 1524 EXPECT_EQ(&AC, InvalidatedSCCs[0]); 1525 EXPECT_EQ(2, CC.size()); 1526 EXPECT_EQ(&CC, CG.lookupSCC(A)); 1527 EXPECT_EQ(&CC, CG.lookupSCC(C)); 1528 J = RC.begin(); 1529 EXPECT_EQ(&*J++, CG.lookupSCC(B)); 1530 EXPECT_EQ(&*J++, CG.lookupSCC(C)); 1531 EXPECT_EQ(RC.end(), J); 1532 } 1533 1534 TEST(LazyCallGraphTest, InternalEdgeRemoval) { 1535 LLVMContext Context; 1536 // A nice fully connected (including self-edges) RefSCC. 1537 std::unique_ptr<Module> M = parseAssembly( 1538 Context, "define void @a(i8** %ptr) {\n" 1539 "entry:\n" 1540 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" 1541 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" 1542 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" 1543 " ret void\n" 1544 "}\n" 1545 "define void @b(i8** %ptr) {\n" 1546 "entry:\n" 1547 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" 1548 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" 1549 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" 1550 " ret void\n" 1551 "}\n" 1552 "define void @c(i8** %ptr) {\n" 1553 "entry:\n" 1554 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" 1555 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" 1556 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" 1557 " ret void\n" 1558 "}\n"); 1559 LazyCallGraph CG(*M); 1560 1561 // Force the graph to be fully expanded. 1562 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); 1563 LazyCallGraph::RefSCC &RC = *I; 1564 EXPECT_EQ(E, std::next(I)); 1565 1566 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 1567 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 1568 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 1569 EXPECT_EQ(&RC, CG.lookupRefSCC(A)); 1570 EXPECT_EQ(&RC, CG.lookupRefSCC(B)); 1571 EXPECT_EQ(&RC, CG.lookupRefSCC(C)); 1572 1573 // Remove the edge from b -> a, which should leave the 3 functions still in 1574 // a single connected component because of a -> b -> c -> a. 1575 SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs = 1576 RC.removeInternalRefEdge(B, A); 1577 EXPECT_EQ(0u, NewRCs.size()); 1578 EXPECT_EQ(&RC, CG.lookupRefSCC(A)); 1579 EXPECT_EQ(&RC, CG.lookupRefSCC(B)); 1580 EXPECT_EQ(&RC, CG.lookupRefSCC(C)); 1581 auto J = CG.postorder_ref_scc_begin(); 1582 EXPECT_EQ(I, J); 1583 EXPECT_EQ(&RC, &*J); 1584 EXPECT_EQ(E, std::next(J)); 1585 1586 // Remove the edge from c -> a, which should leave 'a' in the original RefSCC 1587 // and form a new RefSCC for 'b' and 'c'. 1588 NewRCs = RC.removeInternalRefEdge(C, A); 1589 EXPECT_EQ(1u, NewRCs.size()); 1590 EXPECT_EQ(&RC, CG.lookupRefSCC(A)); 1591 EXPECT_EQ(1, std::distance(RC.begin(), RC.end())); 1592 LazyCallGraph::RefSCC &RC2 = *CG.lookupRefSCC(B); 1593 EXPECT_EQ(&RC2, CG.lookupRefSCC(C)); 1594 EXPECT_EQ(&RC2, NewRCs[0]); 1595 J = CG.postorder_ref_scc_begin(); 1596 EXPECT_NE(I, J); 1597 EXPECT_EQ(&RC2, &*J); 1598 ++J; 1599 EXPECT_EQ(I, J); 1600 EXPECT_EQ(&RC, &*J); 1601 ++I; 1602 EXPECT_EQ(E, I); 1603 ++J; 1604 EXPECT_EQ(E, J); 1605 } 1606 1607 TEST(LazyCallGraphTest, InternalNoOpEdgeRemoval) { 1608 LLVMContext Context; 1609 // A graph with a single cycle formed both from call and reference edges 1610 // which makes the reference edges trivial to delete. The graph looks like: 1611 // 1612 // Reference edges: a -> b -> c -> a 1613 // Call edges: a -> c -> b -> a 1614 std::unique_ptr<Module> M = parseAssembly( 1615 Context, "define void @a(i8** %ptr) {\n" 1616 "entry:\n" 1617 " call void @b(i8** %ptr)\n" 1618 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" 1619 " ret void\n" 1620 "}\n" 1621 "define void @b(i8** %ptr) {\n" 1622 "entry:\n" 1623 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" 1624 " call void @c(i8** %ptr)\n" 1625 " ret void\n" 1626 "}\n" 1627 "define void @c(i8** %ptr) {\n" 1628 "entry:\n" 1629 " call void @a(i8** %ptr)\n" 1630 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" 1631 " ret void\n" 1632 "}\n"); 1633 LazyCallGraph CG(*M); 1634 1635 // Force the graph to be fully expanded. 1636 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); 1637 LazyCallGraph::RefSCC &RC = *I; 1638 EXPECT_EQ(E, std::next(I)); 1639 1640 LazyCallGraph::SCC &C = *RC.begin(); 1641 EXPECT_EQ(RC.end(), std::next(RC.begin())); 1642 1643 LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a")); 1644 LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b")); 1645 LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c")); 1646 EXPECT_EQ(&RC, CG.lookupRefSCC(AN)); 1647 EXPECT_EQ(&RC, CG.lookupRefSCC(BN)); 1648 EXPECT_EQ(&RC, CG.lookupRefSCC(CN)); 1649 EXPECT_EQ(&C, CG.lookupSCC(AN)); 1650 EXPECT_EQ(&C, CG.lookupSCC(BN)); 1651 EXPECT_EQ(&C, CG.lookupSCC(CN)); 1652 1653 // Remove the edge from a -> c which doesn't change anything. 1654 SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs = 1655 RC.removeInternalRefEdge(AN, CN); 1656 EXPECT_EQ(0u, NewRCs.size()); 1657 EXPECT_EQ(&RC, CG.lookupRefSCC(AN)); 1658 EXPECT_EQ(&RC, CG.lookupRefSCC(BN)); 1659 EXPECT_EQ(&RC, CG.lookupRefSCC(CN)); 1660 EXPECT_EQ(&C, CG.lookupSCC(AN)); 1661 EXPECT_EQ(&C, CG.lookupSCC(BN)); 1662 EXPECT_EQ(&C, CG.lookupSCC(CN)); 1663 auto J = CG.postorder_ref_scc_begin(); 1664 EXPECT_EQ(I, J); 1665 EXPECT_EQ(&RC, &*J); 1666 EXPECT_EQ(E, std::next(J)); 1667 1668 // Remove the edge from b -> a and c -> b; again this doesn't change 1669 // anything. 1670 NewRCs = RC.removeInternalRefEdge(BN, AN); 1671 NewRCs = RC.removeInternalRefEdge(CN, BN); 1672 EXPECT_EQ(0u, NewRCs.size()); 1673 EXPECT_EQ(&RC, CG.lookupRefSCC(AN)); 1674 EXPECT_EQ(&RC, CG.lookupRefSCC(BN)); 1675 EXPECT_EQ(&RC, CG.lookupRefSCC(CN)); 1676 EXPECT_EQ(&C, CG.lookupSCC(AN)); 1677 EXPECT_EQ(&C, CG.lookupSCC(BN)); 1678 EXPECT_EQ(&C, CG.lookupSCC(CN)); 1679 J = CG.postorder_ref_scc_begin(); 1680 EXPECT_EQ(I, J); 1681 EXPECT_EQ(&RC, &*J); 1682 EXPECT_EQ(E, std::next(J)); 1683 } 1684 1685 TEST(LazyCallGraphTest, InternalCallEdgeToRef) { 1686 LLVMContext Context; 1687 // A nice fully connected (including self-edges) SCC (and RefSCC) 1688 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n" 1689 "entry:\n" 1690 " call void @a()\n" 1691 " call void @b()\n" 1692 " call void @c()\n" 1693 " ret void\n" 1694 "}\n" 1695 "define void @b() {\n" 1696 "entry:\n" 1697 " call void @a()\n" 1698 " call void @b()\n" 1699 " call void @c()\n" 1700 " ret void\n" 1701 "}\n" 1702 "define void @c() {\n" 1703 "entry:\n" 1704 " call void @a()\n" 1705 " call void @b()\n" 1706 " call void @c()\n" 1707 " ret void\n" 1708 "}\n"); 1709 LazyCallGraph CG(*M); 1710 1711 // Force the graph to be fully expanded. 1712 auto I = CG.postorder_ref_scc_begin(); 1713 LazyCallGraph::RefSCC &RC = *I++; 1714 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 1715 1716 EXPECT_EQ(1, RC.size()); 1717 LazyCallGraph::SCC &AC = *RC.begin(); 1718 1719 LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a")); 1720 LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b")); 1721 LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c")); 1722 EXPECT_EQ(&AC, CG.lookupSCC(AN)); 1723 EXPECT_EQ(&AC, CG.lookupSCC(BN)); 1724 EXPECT_EQ(&AC, CG.lookupSCC(CN)); 1725 1726 // Remove the call edge from b -> a to a ref edge, which should leave the 1727 // 3 functions still in a single connected component because of a -> b -> 1728 // c -> a. 1729 auto NewCs = RC.switchInternalEdgeToRef(BN, AN); 1730 EXPECT_EQ(NewCs.begin(), NewCs.end()); 1731 EXPECT_EQ(1, RC.size()); 1732 EXPECT_EQ(&AC, CG.lookupSCC(AN)); 1733 EXPECT_EQ(&AC, CG.lookupSCC(BN)); 1734 EXPECT_EQ(&AC, CG.lookupSCC(CN)); 1735 1736 // Remove the edge from c -> a, which should leave 'a' in the original SCC 1737 // and form a new SCC for 'b' and 'c'. 1738 NewCs = RC.switchInternalEdgeToRef(CN, AN); 1739 EXPECT_EQ(1, std::distance(NewCs.begin(), NewCs.end())); 1740 EXPECT_EQ(2, RC.size()); 1741 EXPECT_EQ(&AC, CG.lookupSCC(AN)); 1742 LazyCallGraph::SCC &BC = *CG.lookupSCC(BN); 1743 EXPECT_NE(&BC, &AC); 1744 EXPECT_EQ(&BC, CG.lookupSCC(CN)); 1745 auto J = RC.find(AC); 1746 EXPECT_EQ(&AC, &*J); 1747 --J; 1748 EXPECT_EQ(&BC, &*J); 1749 EXPECT_EQ(RC.begin(), J); 1750 EXPECT_EQ(J, NewCs.begin()); 1751 1752 // Remove the edge from c -> b, which should leave 'b' in the original SCC 1753 // and form a new SCC for 'c'. It shouldn't change 'a's SCC. 1754 NewCs = RC.switchInternalEdgeToRef(CN, BN); 1755 EXPECT_EQ(1, std::distance(NewCs.begin(), NewCs.end())); 1756 EXPECT_EQ(3, RC.size()); 1757 EXPECT_EQ(&AC, CG.lookupSCC(AN)); 1758 EXPECT_EQ(&BC, CG.lookupSCC(BN)); 1759 LazyCallGraph::SCC &CC = *CG.lookupSCC(CN); 1760 EXPECT_NE(&CC, &AC); 1761 EXPECT_NE(&CC, &BC); 1762 J = RC.find(AC); 1763 EXPECT_EQ(&AC, &*J); 1764 --J; 1765 EXPECT_EQ(&BC, &*J); 1766 --J; 1767 EXPECT_EQ(&CC, &*J); 1768 EXPECT_EQ(RC.begin(), J); 1769 EXPECT_EQ(J, NewCs.begin()); 1770 } 1771 1772 TEST(LazyCallGraphTest, InternalRefEdgeToCall) { 1773 LLVMContext Context; 1774 // Basic tests for making a ref edge a call. This hits the basics of the 1775 // process only. 1776 std::unique_ptr<Module> M = 1777 parseAssembly(Context, "define void @a() {\n" 1778 "entry:\n" 1779 " call void @b()\n" 1780 " call void @c()\n" 1781 " store void()* @d, void()** undef\n" 1782 " ret void\n" 1783 "}\n" 1784 "define void @b() {\n" 1785 "entry:\n" 1786 " store void()* @c, void()** undef\n" 1787 " call void @d()\n" 1788 " ret void\n" 1789 "}\n" 1790 "define void @c() {\n" 1791 "entry:\n" 1792 " store void()* @b, void()** undef\n" 1793 " call void @d()\n" 1794 " ret void\n" 1795 "}\n" 1796 "define void @d() {\n" 1797 "entry:\n" 1798 " store void()* @a, void()** undef\n" 1799 " ret void\n" 1800 "}\n"); 1801 LazyCallGraph CG(*M); 1802 1803 // Force the graph to be fully expanded. 1804 auto I = CG.postorder_ref_scc_begin(); 1805 LazyCallGraph::RefSCC &RC = *I++; 1806 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 1807 1808 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 1809 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 1810 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 1811 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); 1812 LazyCallGraph::SCC &AC = *CG.lookupSCC(A); 1813 LazyCallGraph::SCC &BC = *CG.lookupSCC(B); 1814 LazyCallGraph::SCC &CC = *CG.lookupSCC(C); 1815 LazyCallGraph::SCC &DC = *CG.lookupSCC(D); 1816 1817 // Check the initial post-order. Note that B and C could be flipped here (and 1818 // in our mutation) without changing the nature of this test. 1819 ASSERT_EQ(4, RC.size()); 1820 EXPECT_EQ(&DC, &RC[0]); 1821 EXPECT_EQ(&BC, &RC[1]); 1822 EXPECT_EQ(&CC, &RC[2]); 1823 EXPECT_EQ(&AC, &RC[3]); 1824 1825 // Switch the ref edge from A -> D to a call edge. This should have no 1826 // effect as it is already in postorder and no new cycles are formed. 1827 auto MergedCs = RC.switchInternalEdgeToCall(A, D); 1828 EXPECT_EQ(0u, MergedCs.size()); 1829 ASSERT_EQ(4, RC.size()); 1830 EXPECT_EQ(&DC, &RC[0]); 1831 EXPECT_EQ(&BC, &RC[1]); 1832 EXPECT_EQ(&CC, &RC[2]); 1833 EXPECT_EQ(&AC, &RC[3]); 1834 1835 // Switch B -> C to a call edge. This doesn't form any new cycles but does 1836 // require reordering the SCCs. 1837 MergedCs = RC.switchInternalEdgeToCall(B, C); 1838 EXPECT_EQ(0u, MergedCs.size()); 1839 ASSERT_EQ(4, RC.size()); 1840 EXPECT_EQ(&DC, &RC[0]); 1841 EXPECT_EQ(&CC, &RC[1]); 1842 EXPECT_EQ(&BC, &RC[2]); 1843 EXPECT_EQ(&AC, &RC[3]); 1844 1845 // Switch C -> B to a call edge. This forms a cycle and forces merging SCCs. 1846 MergedCs = RC.switchInternalEdgeToCall(C, B); 1847 ASSERT_EQ(1u, MergedCs.size()); 1848 EXPECT_EQ(&CC, MergedCs[0]); 1849 ASSERT_EQ(3, RC.size()); 1850 EXPECT_EQ(&DC, &RC[0]); 1851 EXPECT_EQ(&BC, &RC[1]); 1852 EXPECT_EQ(&AC, &RC[2]); 1853 EXPECT_EQ(2, BC.size()); 1854 EXPECT_EQ(&BC, CG.lookupSCC(B)); 1855 EXPECT_EQ(&BC, CG.lookupSCC(C)); 1856 } 1857 1858 TEST(LazyCallGraphTest, InternalRefEdgeToCallNoCycleInterleaved) { 1859 LLVMContext Context; 1860 // Test for having a post-order prior to changing a ref edge to a call edge 1861 // with SCCs connecting to the source and connecting to the target, but not 1862 // connecting to both, interleaved between the source and target. This 1863 // ensures we correctly partition the range rather than simply moving one or 1864 // the other. 1865 std::unique_ptr<Module> M = 1866 parseAssembly(Context, "define void @a() {\n" 1867 "entry:\n" 1868 " call void @b1()\n" 1869 " call void @c1()\n" 1870 " ret void\n" 1871 "}\n" 1872 "define void @b1() {\n" 1873 "entry:\n" 1874 " call void @c1()\n" 1875 " call void @b2()\n" 1876 " ret void\n" 1877 "}\n" 1878 "define void @c1() {\n" 1879 "entry:\n" 1880 " call void @b2()\n" 1881 " call void @c2()\n" 1882 " ret void\n" 1883 "}\n" 1884 "define void @b2() {\n" 1885 "entry:\n" 1886 " call void @c2()\n" 1887 " call void @b3()\n" 1888 " ret void\n" 1889 "}\n" 1890 "define void @c2() {\n" 1891 "entry:\n" 1892 " call void @b3()\n" 1893 " call void @c3()\n" 1894 " ret void\n" 1895 "}\n" 1896 "define void @b3() {\n" 1897 "entry:\n" 1898 " call void @c3()\n" 1899 " call void @d()\n" 1900 " ret void\n" 1901 "}\n" 1902 "define void @c3() {\n" 1903 "entry:\n" 1904 " store void()* @b1, void()** undef\n" 1905 " call void @d()\n" 1906 " ret void\n" 1907 "}\n" 1908 "define void @d() {\n" 1909 "entry:\n" 1910 " store void()* @a, void()** undef\n" 1911 " ret void\n" 1912 "}\n"); 1913 LazyCallGraph CG(*M); 1914 1915 // Force the graph to be fully expanded. 1916 auto I = CG.postorder_ref_scc_begin(); 1917 LazyCallGraph::RefSCC &RC = *I++; 1918 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 1919 1920 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 1921 LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1")); 1922 LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2")); 1923 LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3")); 1924 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1")); 1925 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2")); 1926 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3")); 1927 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); 1928 LazyCallGraph::SCC &AC = *CG.lookupSCC(A); 1929 LazyCallGraph::SCC &B1C = *CG.lookupSCC(B1); 1930 LazyCallGraph::SCC &B2C = *CG.lookupSCC(B2); 1931 LazyCallGraph::SCC &B3C = *CG.lookupSCC(B3); 1932 LazyCallGraph::SCC &C1C = *CG.lookupSCC(C1); 1933 LazyCallGraph::SCC &C2C = *CG.lookupSCC(C2); 1934 LazyCallGraph::SCC &C3C = *CG.lookupSCC(C3); 1935 LazyCallGraph::SCC &DC = *CG.lookupSCC(D); 1936 1937 // Several call edges are initially present to force a particual post-order. 1938 // Remove them now, leaving an interleaved post-order pattern. 1939 RC.switchTrivialInternalEdgeToRef(B3, C3); 1940 RC.switchTrivialInternalEdgeToRef(C2, B3); 1941 RC.switchTrivialInternalEdgeToRef(B2, C2); 1942 RC.switchTrivialInternalEdgeToRef(C1, B2); 1943 RC.switchTrivialInternalEdgeToRef(B1, C1); 1944 1945 // Check the initial post-order. We ensure this order with the extra edges 1946 // that are nuked above. 1947 ASSERT_EQ(8, RC.size()); 1948 EXPECT_EQ(&DC, &RC[0]); 1949 EXPECT_EQ(&C3C, &RC[1]); 1950 EXPECT_EQ(&B3C, &RC[2]); 1951 EXPECT_EQ(&C2C, &RC[3]); 1952 EXPECT_EQ(&B2C, &RC[4]); 1953 EXPECT_EQ(&C1C, &RC[5]); 1954 EXPECT_EQ(&B1C, &RC[6]); 1955 EXPECT_EQ(&AC, &RC[7]); 1956 1957 // Switch C3 -> B1 to a call edge. This doesn't form any new cycles but does 1958 // require reordering the SCCs in the face of tricky internal node 1959 // structures. 1960 auto MergedCs = RC.switchInternalEdgeToCall(C3, B1); 1961 EXPECT_EQ(0u, MergedCs.size()); 1962 ASSERT_EQ(8, RC.size()); 1963 EXPECT_EQ(&DC, &RC[0]); 1964 EXPECT_EQ(&B3C, &RC[1]); 1965 EXPECT_EQ(&B2C, &RC[2]); 1966 EXPECT_EQ(&B1C, &RC[3]); 1967 EXPECT_EQ(&C3C, &RC[4]); 1968 EXPECT_EQ(&C2C, &RC[5]); 1969 EXPECT_EQ(&C1C, &RC[6]); 1970 EXPECT_EQ(&AC, &RC[7]); 1971 } 1972 1973 TEST(LazyCallGraphTest, InternalRefEdgeToCallBothPartitionAndMerge) { 1974 LLVMContext Context; 1975 // Test for having a postorder where between the source and target are all 1976 // three kinds of other SCCs: 1977 // 1) One connected to the target only that have to be shifted below the 1978 // source. 1979 // 2) One connected to the source only that have to be shifted below the 1980 // target. 1981 // 3) One connected to both source and target that has to remain and get 1982 // merged away. 1983 // 1984 // To achieve this we construct a heavily connected graph to force 1985 // a particular post-order. Then we remove the forcing edges and connect 1986 // a cycle. 1987 // 1988 // Diagram for the graph we want on the left and the graph we use to force 1989 // the ordering on the right. Edges ponit down or right. 1990 // 1991 // A | A | 1992 // / \ | / \ | 1993 // B E | B \ | 1994 // |\ | | |\ | | 1995 // | D | | C-D-E | 1996 // | \| | | \| | 1997 // C F | \ F | 1998 // \ / | \ / | 1999 // G | G | 2000 // 2001 // And we form a cycle by connecting F to B. 2002 std::unique_ptr<Module> M = 2003 parseAssembly(Context, "define void @a() {\n" 2004 "entry:\n" 2005 " call void @b()\n" 2006 " call void @e()\n" 2007 " ret void\n" 2008 "}\n" 2009 "define void @b() {\n" 2010 "entry:\n" 2011 " call void @c()\n" 2012 " call void @d()\n" 2013 " ret void\n" 2014 "}\n" 2015 "define void @c() {\n" 2016 "entry:\n" 2017 " call void @d()\n" 2018 " call void @g()\n" 2019 " ret void\n" 2020 "}\n" 2021 "define void @d() {\n" 2022 "entry:\n" 2023 " call void @e()\n" 2024 " call void @f()\n" 2025 " ret void\n" 2026 "}\n" 2027 "define void @e() {\n" 2028 "entry:\n" 2029 " call void @f()\n" 2030 " ret void\n" 2031 "}\n" 2032 "define void @f() {\n" 2033 "entry:\n" 2034 " store void()* @b, void()** undef\n" 2035 " call void @g()\n" 2036 " ret void\n" 2037 "}\n" 2038 "define void @g() {\n" 2039 "entry:\n" 2040 " store void()* @a, void()** undef\n" 2041 " ret void\n" 2042 "}\n"); 2043 LazyCallGraph CG(*M); 2044 2045 // Force the graph to be fully expanded. 2046 auto I = CG.postorder_ref_scc_begin(); 2047 LazyCallGraph::RefSCC &RC = *I++; 2048 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2049 2050 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 2051 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 2052 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 2053 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); 2054 LazyCallGraph::Node &E = *CG.lookup(lookupFunction(*M, "e")); 2055 LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f")); 2056 LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g")); 2057 LazyCallGraph::SCC &AC = *CG.lookupSCC(A); 2058 LazyCallGraph::SCC &BC = *CG.lookupSCC(B); 2059 LazyCallGraph::SCC &CC = *CG.lookupSCC(C); 2060 LazyCallGraph::SCC &DC = *CG.lookupSCC(D); 2061 LazyCallGraph::SCC &EC = *CG.lookupSCC(E); 2062 LazyCallGraph::SCC &FC = *CG.lookupSCC(F); 2063 LazyCallGraph::SCC &GC = *CG.lookupSCC(G); 2064 2065 // Remove the extra edges that were used to force a particular post-order. 2066 RC.switchTrivialInternalEdgeToRef(C, D); 2067 RC.switchTrivialInternalEdgeToRef(D, E); 2068 2069 // Check the initial post-order. We ensure this order with the extra edges 2070 // that are nuked above. 2071 ASSERT_EQ(7, RC.size()); 2072 EXPECT_EQ(&GC, &RC[0]); 2073 EXPECT_EQ(&FC, &RC[1]); 2074 EXPECT_EQ(&EC, &RC[2]); 2075 EXPECT_EQ(&DC, &RC[3]); 2076 EXPECT_EQ(&CC, &RC[4]); 2077 EXPECT_EQ(&BC, &RC[5]); 2078 EXPECT_EQ(&AC, &RC[6]); 2079 2080 // Switch F -> B to a call edge. This merges B, D, and F into a single SCC, 2081 // and has to place the C and E SCCs on either side of it: 2082 // A A | 2083 // / \ / \ | 2084 // B E | E | 2085 // |\ | \ / | 2086 // | D | -> B | 2087 // | \| / \ | 2088 // C F C | | 2089 // \ / \ / | 2090 // G G | 2091 auto MergedCs = RC.switchInternalEdgeToCall(F, B); 2092 ASSERT_EQ(2u, MergedCs.size()); 2093 EXPECT_EQ(&FC, MergedCs[0]); 2094 EXPECT_EQ(&DC, MergedCs[1]); 2095 EXPECT_EQ(3, BC.size()); 2096 2097 // And make sure the postorder was updated. 2098 ASSERT_EQ(5, RC.size()); 2099 EXPECT_EQ(&GC, &RC[0]); 2100 EXPECT_EQ(&CC, &RC[1]); 2101 EXPECT_EQ(&BC, &RC[2]); 2102 EXPECT_EQ(&EC, &RC[3]); 2103 EXPECT_EQ(&AC, &RC[4]); 2104 } 2105 2106 // Test for IR containing constants using blockaddress constant expressions. 2107 // These are truly unique constructs: constant expressions with non-constant 2108 // operands. 2109 TEST(LazyCallGraphTest, HandleBlockAddress) { 2110 LLVMContext Context; 2111 std::unique_ptr<Module> M = 2112 parseAssembly(Context, "define void @f() {\n" 2113 "entry:\n" 2114 " ret void\n" 2115 "bb:\n" 2116 " unreachable\n" 2117 "}\n" 2118 "define void @g(i8** %ptr) {\n" 2119 "entry:\n" 2120 " store i8* blockaddress(@f, %bb), i8** %ptr\n" 2121 " ret void\n" 2122 "}\n"); 2123 LazyCallGraph CG(*M); 2124 2125 auto I = CG.postorder_ref_scc_begin(); 2126 LazyCallGraph::RefSCC &FRC = *I++; 2127 LazyCallGraph::RefSCC &GRC = *I++; 2128 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 2129 2130 LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f")); 2131 LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g")); 2132 EXPECT_EQ(&FRC, CG.lookupRefSCC(F)); 2133 EXPECT_EQ(&GRC, CG.lookupRefSCC(G)); 2134 EXPECT_TRUE(GRC.isParentOf(FRC)); 2135 } 2136 2137 } 2138