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