1 //===- LazyCallGraphTest.cpp - Unit tests for the lazy CG analysis --------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 #include "llvm/Analysis/LazyCallGraph.h" 11 #include "llvm/AsmParser/Parser.h" 12 #include "llvm/IR/Function.h" 13 #include "llvm/IR/LLVMContext.h" 14 #include "llvm/IR/Module.h" 15 #include "llvm/Support/ErrorHandling.h" 16 #include "llvm/Support/SourceMgr.h" 17 #include "gtest/gtest.h" 18 #include <memory> 19 20 using namespace llvm; 21 22 namespace { 23 24 std::unique_ptr<Module> parseAssembly(const char *Assembly) { 25 SMDiagnostic Error; 26 std::unique_ptr<Module> M = 27 parseAssemblyString(Assembly, Error, getGlobalContext()); 28 29 std::string ErrMsg; 30 raw_string_ostream OS(ErrMsg); 31 Error.print("", OS); 32 33 // A failure here means that the test itself is buggy. 34 if (!M) 35 report_fatal_error(OS.str().c_str()); 36 37 return M; 38 } 39 40 // IR forming a call graph with a diamond of triangle-shaped SCCs: 41 // 42 // d1 43 // / \ 44 // d3--d2 45 // / \ 46 // b1 c1 47 // / \ / \ 48 // b3--b2 c3--c2 49 // \ / 50 // a1 51 // / \ 52 // a3--a2 53 // 54 // All call edges go up between SCCs, and clockwise around the SCC. 55 static const char DiamondOfTriangles[] = 56 "define void @a1() {\n" 57 "entry:\n" 58 " call void @a2()\n" 59 " call void @b2()\n" 60 " call void @c3()\n" 61 " ret void\n" 62 "}\n" 63 "define void @a2() {\n" 64 "entry:\n" 65 " call void @a3()\n" 66 " ret void\n" 67 "}\n" 68 "define void @a3() {\n" 69 "entry:\n" 70 " call void @a1()\n" 71 " ret void\n" 72 "}\n" 73 "define void @b1() {\n" 74 "entry:\n" 75 " call void @b2()\n" 76 " call void @d3()\n" 77 " ret void\n" 78 "}\n" 79 "define void @b2() {\n" 80 "entry:\n" 81 " call void @b3()\n" 82 " ret void\n" 83 "}\n" 84 "define void @b3() {\n" 85 "entry:\n" 86 " call void @b1()\n" 87 " ret void\n" 88 "}\n" 89 "define void @c1() {\n" 90 "entry:\n" 91 " call void @c2()\n" 92 " call void @d2()\n" 93 " ret void\n" 94 "}\n" 95 "define void @c2() {\n" 96 "entry:\n" 97 " call void @c3()\n" 98 " ret void\n" 99 "}\n" 100 "define void @c3() {\n" 101 "entry:\n" 102 " call void @c1()\n" 103 " ret void\n" 104 "}\n" 105 "define void @d1() {\n" 106 "entry:\n" 107 " call void @d2()\n" 108 " ret void\n" 109 "}\n" 110 "define void @d2() {\n" 111 "entry:\n" 112 " call void @d3()\n" 113 " ret void\n" 114 "}\n" 115 "define void @d3() {\n" 116 "entry:\n" 117 " call void @d1()\n" 118 " ret void\n" 119 "}\n"; 120 121 TEST(LazyCallGraphTest, BasicGraphFormation) { 122 std::unique_ptr<Module> M = parseAssembly(DiamondOfTriangles); 123 LazyCallGraph CG(*M); 124 125 // The order of the entry nodes should be stable w.r.t. the source order of 126 // the IR, and everything in our module is an entry node, so just directly 127 // build variables for each node. 128 auto I = CG.begin(); 129 LazyCallGraph::Node &A1 = *I++; 130 EXPECT_EQ("a1", A1.getFunction().getName()); 131 LazyCallGraph::Node &A2 = *I++; 132 EXPECT_EQ("a2", A2.getFunction().getName()); 133 LazyCallGraph::Node &A3 = *I++; 134 EXPECT_EQ("a3", A3.getFunction().getName()); 135 LazyCallGraph::Node &B1 = *I++; 136 EXPECT_EQ("b1", B1.getFunction().getName()); 137 LazyCallGraph::Node &B2 = *I++; 138 EXPECT_EQ("b2", B2.getFunction().getName()); 139 LazyCallGraph::Node &B3 = *I++; 140 EXPECT_EQ("b3", B3.getFunction().getName()); 141 LazyCallGraph::Node &C1 = *I++; 142 EXPECT_EQ("c1", C1.getFunction().getName()); 143 LazyCallGraph::Node &C2 = *I++; 144 EXPECT_EQ("c2", C2.getFunction().getName()); 145 LazyCallGraph::Node &C3 = *I++; 146 EXPECT_EQ("c3", C3.getFunction().getName()); 147 LazyCallGraph::Node &D1 = *I++; 148 EXPECT_EQ("d1", D1.getFunction().getName()); 149 LazyCallGraph::Node &D2 = *I++; 150 EXPECT_EQ("d2", D2.getFunction().getName()); 151 LazyCallGraph::Node &D3 = *I++; 152 EXPECT_EQ("d3", D3.getFunction().getName()); 153 EXPECT_EQ(CG.end(), I); 154 155 // Build vectors and sort them for the rest of the assertions to make them 156 // independent of order. 157 std::vector<std::string> Nodes; 158 159 for (LazyCallGraph::Node &N : A1) 160 Nodes.push_back(N.getFunction().getName()); 161 std::sort(Nodes.begin(), Nodes.end()); 162 EXPECT_EQ("a2", Nodes[0]); 163 EXPECT_EQ("b2", Nodes[1]); 164 EXPECT_EQ("c3", Nodes[2]); 165 Nodes.clear(); 166 167 EXPECT_EQ(A2.end(), std::next(A2.begin())); 168 EXPECT_EQ("a3", A2.begin()->getFunction().getName()); 169 EXPECT_EQ(A3.end(), std::next(A3.begin())); 170 EXPECT_EQ("a1", A3.begin()->getFunction().getName()); 171 172 for (LazyCallGraph::Node &N : B1) 173 Nodes.push_back(N.getFunction().getName()); 174 std::sort(Nodes.begin(), Nodes.end()); 175 EXPECT_EQ("b2", Nodes[0]); 176 EXPECT_EQ("d3", Nodes[1]); 177 Nodes.clear(); 178 179 EXPECT_EQ(B2.end(), std::next(B2.begin())); 180 EXPECT_EQ("b3", B2.begin()->getFunction().getName()); 181 EXPECT_EQ(B3.end(), std::next(B3.begin())); 182 EXPECT_EQ("b1", B3.begin()->getFunction().getName()); 183 184 for (LazyCallGraph::Node &N : C1) 185 Nodes.push_back(N.getFunction().getName()); 186 std::sort(Nodes.begin(), Nodes.end()); 187 EXPECT_EQ("c2", Nodes[0]); 188 EXPECT_EQ("d2", Nodes[1]); 189 Nodes.clear(); 190 191 EXPECT_EQ(C2.end(), std::next(C2.begin())); 192 EXPECT_EQ("c3", C2.begin()->getFunction().getName()); 193 EXPECT_EQ(C3.end(), std::next(C3.begin())); 194 EXPECT_EQ("c1", C3.begin()->getFunction().getName()); 195 196 EXPECT_EQ(D1.end(), std::next(D1.begin())); 197 EXPECT_EQ("d2", D1.begin()->getFunction().getName()); 198 EXPECT_EQ(D2.end(), std::next(D2.begin())); 199 EXPECT_EQ("d3", D2.begin()->getFunction().getName()); 200 EXPECT_EQ(D3.end(), std::next(D3.begin())); 201 EXPECT_EQ("d1", D3.begin()->getFunction().getName()); 202 203 // Now lets look at the SCCs. 204 auto SCCI = CG.postorder_scc_begin(); 205 206 LazyCallGraph::SCC &D = *SCCI++; 207 for (LazyCallGraph::Node *N : D) 208 Nodes.push_back(N->getFunction().getName()); 209 std::sort(Nodes.begin(), Nodes.end()); 210 EXPECT_EQ(3u, Nodes.size()); 211 EXPECT_EQ("d1", Nodes[0]); 212 EXPECT_EQ("d2", Nodes[1]); 213 EXPECT_EQ("d3", Nodes[2]); 214 Nodes.clear(); 215 EXPECT_FALSE(D.isParentOf(D)); 216 EXPECT_FALSE(D.isChildOf(D)); 217 EXPECT_FALSE(D.isAncestorOf(D)); 218 EXPECT_FALSE(D.isDescendantOf(D)); 219 220 LazyCallGraph::SCC &C = *SCCI++; 221 for (LazyCallGraph::Node *N : C) 222 Nodes.push_back(N->getFunction().getName()); 223 std::sort(Nodes.begin(), Nodes.end()); 224 EXPECT_EQ(3u, Nodes.size()); 225 EXPECT_EQ("c1", Nodes[0]); 226 EXPECT_EQ("c2", Nodes[1]); 227 EXPECT_EQ("c3", Nodes[2]); 228 Nodes.clear(); 229 EXPECT_TRUE(C.isParentOf(D)); 230 EXPECT_FALSE(C.isChildOf(D)); 231 EXPECT_TRUE(C.isAncestorOf(D)); 232 EXPECT_FALSE(C.isDescendantOf(D)); 233 234 LazyCallGraph::SCC &B = *SCCI++; 235 for (LazyCallGraph::Node *N : B) 236 Nodes.push_back(N->getFunction().getName()); 237 std::sort(Nodes.begin(), Nodes.end()); 238 EXPECT_EQ(3u, Nodes.size()); 239 EXPECT_EQ("b1", Nodes[0]); 240 EXPECT_EQ("b2", Nodes[1]); 241 EXPECT_EQ("b3", Nodes[2]); 242 Nodes.clear(); 243 EXPECT_TRUE(B.isParentOf(D)); 244 EXPECT_FALSE(B.isChildOf(D)); 245 EXPECT_TRUE(B.isAncestorOf(D)); 246 EXPECT_FALSE(B.isDescendantOf(D)); 247 EXPECT_FALSE(B.isAncestorOf(C)); 248 EXPECT_FALSE(C.isAncestorOf(B)); 249 250 LazyCallGraph::SCC &A = *SCCI++; 251 for (LazyCallGraph::Node *N : A) 252 Nodes.push_back(N->getFunction().getName()); 253 std::sort(Nodes.begin(), Nodes.end()); 254 EXPECT_EQ(3u, Nodes.size()); 255 EXPECT_EQ("a1", Nodes[0]); 256 EXPECT_EQ("a2", Nodes[1]); 257 EXPECT_EQ("a3", Nodes[2]); 258 Nodes.clear(); 259 EXPECT_TRUE(A.isParentOf(B)); 260 EXPECT_TRUE(A.isParentOf(C)); 261 EXPECT_FALSE(A.isParentOf(D)); 262 EXPECT_TRUE(A.isAncestorOf(B)); 263 EXPECT_TRUE(A.isAncestorOf(C)); 264 EXPECT_TRUE(A.isAncestorOf(D)); 265 266 EXPECT_EQ(CG.postorder_scc_end(), SCCI); 267 } 268 269 static Function &lookupFunction(Module &M, StringRef Name) { 270 for (Function &F : M) 271 if (F.getName() == Name) 272 return F; 273 report_fatal_error("Couldn't find function!"); 274 } 275 276 TEST(LazyCallGraphTest, BasicGraphMutation) { 277 std::unique_ptr<Module> M = parseAssembly( 278 "define void @a() {\n" 279 "entry:\n" 280 " call void @b()\n" 281 " call void @c()\n" 282 " ret void\n" 283 "}\n" 284 "define void @b() {\n" 285 "entry:\n" 286 " ret void\n" 287 "}\n" 288 "define void @c() {\n" 289 "entry:\n" 290 " ret void\n" 291 "}\n"); 292 LazyCallGraph CG(*M); 293 294 LazyCallGraph::Node &A = CG.get(lookupFunction(*M, "a")); 295 LazyCallGraph::Node &B = CG.get(lookupFunction(*M, "b")); 296 EXPECT_EQ(2, std::distance(A.begin(), A.end())); 297 EXPECT_EQ(0, std::distance(B.begin(), B.end())); 298 299 CG.insertEdge(B, lookupFunction(*M, "c")); 300 EXPECT_EQ(1, std::distance(B.begin(), B.end())); 301 LazyCallGraph::Node &C = *B.begin(); 302 EXPECT_EQ(0, std::distance(C.begin(), C.end())); 303 304 CG.insertEdge(C, B.getFunction()); 305 EXPECT_EQ(1, std::distance(C.begin(), C.end())); 306 EXPECT_EQ(&B, &*C.begin()); 307 308 CG.insertEdge(C, C.getFunction()); 309 EXPECT_EQ(2, std::distance(C.begin(), C.end())); 310 EXPECT_EQ(&B, &*C.begin()); 311 EXPECT_EQ(&C, &*std::next(C.begin())); 312 313 CG.removeEdge(C, B.getFunction()); 314 EXPECT_EQ(1, std::distance(C.begin(), C.end())); 315 EXPECT_EQ(&C, &*C.begin()); 316 317 CG.removeEdge(C, C.getFunction()); 318 EXPECT_EQ(0, std::distance(C.begin(), C.end())); 319 320 CG.removeEdge(B, C.getFunction()); 321 EXPECT_EQ(0, std::distance(B.begin(), B.end())); 322 } 323 324 TEST(LazyCallGraphTest, MultiArmSCC) { 325 // Two interlocking cycles. The really useful thing about this SCC is that it 326 // will require Tarjan's DFS to backtrack and finish processing all of the 327 // children of each node in the SCC. 328 std::unique_ptr<Module> M = parseAssembly( 329 "define void @a() {\n" 330 "entry:\n" 331 " call void @b()\n" 332 " call void @d()\n" 333 " ret void\n" 334 "}\n" 335 "define void @b() {\n" 336 "entry:\n" 337 " call void @c()\n" 338 " ret void\n" 339 "}\n" 340 "define void @c() {\n" 341 "entry:\n" 342 " call void @a()\n" 343 " ret void\n" 344 "}\n" 345 "define void @d() {\n" 346 "entry:\n" 347 " call void @e()\n" 348 " ret void\n" 349 "}\n" 350 "define void @e() {\n" 351 "entry:\n" 352 " call void @a()\n" 353 " ret void\n" 354 "}\n"); 355 LazyCallGraph CG(*M); 356 357 // Force the graph to be fully expanded. 358 auto SCCI = CG.postorder_scc_begin(); 359 LazyCallGraph::SCC &SCC = *SCCI++; 360 EXPECT_EQ(CG.postorder_scc_end(), SCCI); 361 362 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 363 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 364 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 365 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); 366 LazyCallGraph::Node &E = *CG.lookup(lookupFunction(*M, "e")); 367 EXPECT_EQ(&SCC, CG.lookupSCC(A)); 368 EXPECT_EQ(&SCC, CG.lookupSCC(B)); 369 EXPECT_EQ(&SCC, CG.lookupSCC(C)); 370 EXPECT_EQ(&SCC, CG.lookupSCC(D)); 371 EXPECT_EQ(&SCC, CG.lookupSCC(E)); 372 } 373 374 TEST(LazyCallGraphTest, OutgoingSCCEdgeInsertion) { 375 std::unique_ptr<Module> M = parseAssembly( 376 "define void @a() {\n" 377 "entry:\n" 378 " call void @b()\n" 379 " call void @c()\n" 380 " ret void\n" 381 "}\n" 382 "define void @b() {\n" 383 "entry:\n" 384 " call void @d()\n" 385 " ret void\n" 386 "}\n" 387 "define void @c() {\n" 388 "entry:\n" 389 " call void @d()\n" 390 " ret void\n" 391 "}\n" 392 "define void @d() {\n" 393 "entry:\n" 394 " ret void\n" 395 "}\n"); 396 LazyCallGraph CG(*M); 397 398 // Force the graph to be fully expanded. 399 for (LazyCallGraph::SCC &C : CG.postorder_sccs()) 400 (void)C; 401 402 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 403 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 404 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 405 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); 406 LazyCallGraph::SCC &AC = *CG.lookupSCC(A); 407 LazyCallGraph::SCC &BC = *CG.lookupSCC(B); 408 LazyCallGraph::SCC &CC = *CG.lookupSCC(C); 409 LazyCallGraph::SCC &DC = *CG.lookupSCC(D); 410 EXPECT_TRUE(AC.isAncestorOf(BC)); 411 EXPECT_TRUE(AC.isAncestorOf(CC)); 412 EXPECT_TRUE(AC.isAncestorOf(DC)); 413 EXPECT_TRUE(DC.isDescendantOf(AC)); 414 EXPECT_TRUE(DC.isDescendantOf(BC)); 415 EXPECT_TRUE(DC.isDescendantOf(CC)); 416 417 EXPECT_EQ(2, std::distance(A.begin(), A.end())); 418 AC.insertOutgoingEdge(A, D); 419 EXPECT_EQ(3, std::distance(A.begin(), A.end())); 420 EXPECT_TRUE(AC.isParentOf(DC)); 421 EXPECT_EQ(&AC, CG.lookupSCC(A)); 422 EXPECT_EQ(&BC, CG.lookupSCC(B)); 423 EXPECT_EQ(&CC, CG.lookupSCC(C)); 424 EXPECT_EQ(&DC, CG.lookupSCC(D)); 425 } 426 427 TEST(LazyCallGraphTest, IncomingSCCEdgeInsertion) { 428 // We want to ensure we can add edges even across complex diamond graphs, so 429 // we use the diamond of triangles graph defined above. The ascii diagram is 430 // repeated here for easy reference. 431 // 432 // d1 | 433 // / \ | 434 // d3--d2 | 435 // / \ | 436 // b1 c1 | 437 // / \ / \ | 438 // b3--b2 c3--c2 | 439 // \ / | 440 // a1 | 441 // / \ | 442 // a3--a2 | 443 // 444 std::unique_ptr<Module> M = parseAssembly(DiamondOfTriangles); 445 LazyCallGraph CG(*M); 446 447 // Force the graph to be fully expanded. 448 for (LazyCallGraph::SCC &C : CG.postorder_sccs()) 449 (void)C; 450 451 LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1")); 452 LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2")); 453 LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3")); 454 LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1")); 455 LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2")); 456 LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3")); 457 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1")); 458 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2")); 459 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3")); 460 LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1")); 461 LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2")); 462 LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3")); 463 LazyCallGraph::SCC &AC = *CG.lookupSCC(A1); 464 LazyCallGraph::SCC &BC = *CG.lookupSCC(B1); 465 LazyCallGraph::SCC &CC = *CG.lookupSCC(C1); 466 LazyCallGraph::SCC &DC = *CG.lookupSCC(D1); 467 ASSERT_EQ(&AC, CG.lookupSCC(A2)); 468 ASSERT_EQ(&AC, CG.lookupSCC(A3)); 469 ASSERT_EQ(&BC, CG.lookupSCC(B2)); 470 ASSERT_EQ(&BC, CG.lookupSCC(B3)); 471 ASSERT_EQ(&CC, CG.lookupSCC(C2)); 472 ASSERT_EQ(&CC, CG.lookupSCC(C3)); 473 ASSERT_EQ(&DC, CG.lookupSCC(D2)); 474 ASSERT_EQ(&DC, CG.lookupSCC(D3)); 475 ASSERT_EQ(1, std::distance(D2.begin(), D2.end())); 476 477 // Add an edge to make the graph: 478 // 479 // d1 | 480 // / \ | 481 // d3--d2---. | 482 // / \ | | 483 // b1 c1 | | 484 // / \ / \ / | 485 // b3--b2 c3--c2 | 486 // \ / | 487 // a1 | 488 // / \ | 489 // a3--a2 | 490 CC.insertIncomingEdge(D2, C2); 491 // Make sure we connected the nodes. 492 EXPECT_EQ(2, std::distance(D2.begin(), D2.end())); 493 494 // Make sure we have the correct nodes in the SCC sets. 495 EXPECT_EQ(&AC, CG.lookupSCC(A1)); 496 EXPECT_EQ(&AC, CG.lookupSCC(A2)); 497 EXPECT_EQ(&AC, CG.lookupSCC(A3)); 498 EXPECT_EQ(&BC, CG.lookupSCC(B1)); 499 EXPECT_EQ(&BC, CG.lookupSCC(B2)); 500 EXPECT_EQ(&BC, CG.lookupSCC(B3)); 501 EXPECT_EQ(&CC, CG.lookupSCC(C1)); 502 EXPECT_EQ(&CC, CG.lookupSCC(C2)); 503 EXPECT_EQ(&CC, CG.lookupSCC(C3)); 504 EXPECT_EQ(&CC, CG.lookupSCC(D1)); 505 EXPECT_EQ(&CC, CG.lookupSCC(D2)); 506 EXPECT_EQ(&CC, CG.lookupSCC(D3)); 507 508 // And that ancestry tests have been updated. 509 EXPECT_TRUE(AC.isParentOf(BC)); 510 EXPECT_TRUE(AC.isParentOf(CC)); 511 EXPECT_FALSE(AC.isAncestorOf(DC)); 512 EXPECT_FALSE(BC.isAncestorOf(DC)); 513 EXPECT_FALSE(CC.isAncestorOf(DC)); 514 } 515 516 TEST(LazyCallGraphTest, IncomingSCCEdgeInsertionMidTraversal) { 517 // This is the same fundamental test as the previous, but we perform it 518 // having only partially walked the SCCs of the graph. 519 std::unique_ptr<Module> M = parseAssembly(DiamondOfTriangles); 520 LazyCallGraph CG(*M); 521 522 // Walk the SCCs until we find the one containing 'c1'. 523 auto SCCI = CG.postorder_scc_begin(), SCCE = CG.postorder_scc_end(); 524 ASSERT_NE(SCCI, SCCE); 525 LazyCallGraph::SCC &DC = *SCCI; 526 ASSERT_NE(&DC, nullptr); 527 ++SCCI; 528 ASSERT_NE(SCCI, SCCE); 529 LazyCallGraph::SCC &CC = *SCCI; 530 ASSERT_NE(&CC, nullptr); 531 532 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a1"))); 533 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a2"))); 534 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a3"))); 535 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b1"))); 536 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b2"))); 537 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b3"))); 538 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1")); 539 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2")); 540 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3")); 541 LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1")); 542 LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2")); 543 LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3")); 544 ASSERT_EQ(&CC, CG.lookupSCC(C1)); 545 ASSERT_EQ(&CC, CG.lookupSCC(C2)); 546 ASSERT_EQ(&CC, CG.lookupSCC(C3)); 547 ASSERT_EQ(&DC, CG.lookupSCC(D1)); 548 ASSERT_EQ(&DC, CG.lookupSCC(D2)); 549 ASSERT_EQ(&DC, CG.lookupSCC(D3)); 550 ASSERT_EQ(1, std::distance(D2.begin(), D2.end())); 551 552 CC.insertIncomingEdge(D2, C2); 553 EXPECT_EQ(2, std::distance(D2.begin(), D2.end())); 554 555 // Make sure we have the correct nodes in the SCC sets. 556 EXPECT_EQ(&CC, CG.lookupSCC(C1)); 557 EXPECT_EQ(&CC, CG.lookupSCC(C2)); 558 EXPECT_EQ(&CC, CG.lookupSCC(C3)); 559 EXPECT_EQ(&CC, CG.lookupSCC(D1)); 560 EXPECT_EQ(&CC, CG.lookupSCC(D2)); 561 EXPECT_EQ(&CC, CG.lookupSCC(D3)); 562 563 // Check that we can form the last two SCCs now in a coherent way. 564 ++SCCI; 565 EXPECT_NE(SCCI, SCCE); 566 LazyCallGraph::SCC &BC = *SCCI; 567 EXPECT_NE(&BC, nullptr); 568 EXPECT_EQ(&BC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "b1")))); 569 EXPECT_EQ(&BC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "b2")))); 570 EXPECT_EQ(&BC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "b3")))); 571 ++SCCI; 572 EXPECT_NE(SCCI, SCCE); 573 LazyCallGraph::SCC &AC = *SCCI; 574 EXPECT_NE(&AC, nullptr); 575 EXPECT_EQ(&AC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "a1")))); 576 EXPECT_EQ(&AC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "a2")))); 577 EXPECT_EQ(&AC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "a3")))); 578 ++SCCI; 579 EXPECT_EQ(SCCI, SCCE); 580 } 581 582 TEST(LazyCallGraphTest, InterSCCEdgeRemoval) { 583 std::unique_ptr<Module> M = parseAssembly( 584 "define void @a() {\n" 585 "entry:\n" 586 " call void @b()\n" 587 " ret void\n" 588 "}\n" 589 "define void @b() {\n" 590 "entry:\n" 591 " ret void\n" 592 "}\n"); 593 LazyCallGraph CG(*M); 594 595 // Force the graph to be fully expanded. 596 for (LazyCallGraph::SCC &C : CG.postorder_sccs()) 597 (void)C; 598 599 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 600 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 601 LazyCallGraph::SCC &AC = *CG.lookupSCC(A); 602 LazyCallGraph::SCC &BC = *CG.lookupSCC(B); 603 604 EXPECT_EQ("b", A.begin()->getFunction().getName()); 605 EXPECT_EQ(B.end(), B.begin()); 606 EXPECT_EQ(&AC, &*BC.parent_begin()); 607 608 AC.removeInterSCCEdge(A, B); 609 610 EXPECT_EQ(A.end(), A.begin()); 611 EXPECT_EQ(B.end(), B.begin()); 612 EXPECT_EQ(BC.parent_end(), BC.parent_begin()); 613 } 614 615 TEST(LazyCallGraphTest, IntraSCCEdgeInsertion) { 616 std::unique_ptr<Module> M1 = parseAssembly( 617 "define void @a() {\n" 618 "entry:\n" 619 " call void @b()\n" 620 " ret void\n" 621 "}\n" 622 "define void @b() {\n" 623 "entry:\n" 624 " call void @c()\n" 625 " ret void\n" 626 "}\n" 627 "define void @c() {\n" 628 "entry:\n" 629 " call void @a()\n" 630 " ret void\n" 631 "}\n"); 632 LazyCallGraph CG1(*M1); 633 634 // Force the graph to be fully expanded. 635 auto SCCI = CG1.postorder_scc_begin(); 636 LazyCallGraph::SCC &SCC = *SCCI++; 637 EXPECT_EQ(CG1.postorder_scc_end(), SCCI); 638 639 LazyCallGraph::Node &A = *CG1.lookup(lookupFunction(*M1, "a")); 640 LazyCallGraph::Node &B = *CG1.lookup(lookupFunction(*M1, "b")); 641 LazyCallGraph::Node &C = *CG1.lookup(lookupFunction(*M1, "c")); 642 EXPECT_EQ(&SCC, CG1.lookupSCC(A)); 643 EXPECT_EQ(&SCC, CG1.lookupSCC(B)); 644 EXPECT_EQ(&SCC, CG1.lookupSCC(C)); 645 646 // Insert an edge from 'a' to 'c'. Nothing changes about the SCCs. 647 SCC.insertIntraSCCEdge(A, C); 648 EXPECT_EQ(2, std::distance(A.begin(), A.end())); 649 EXPECT_EQ(&SCC, CG1.lookupSCC(A)); 650 EXPECT_EQ(&SCC, CG1.lookupSCC(B)); 651 EXPECT_EQ(&SCC, CG1.lookupSCC(C)); 652 653 // Insert a self edge from 'a' back to 'a'. 654 SCC.insertIntraSCCEdge(A, A); 655 EXPECT_EQ(3, std::distance(A.begin(), A.end())); 656 EXPECT_EQ(&SCC, CG1.lookupSCC(A)); 657 EXPECT_EQ(&SCC, CG1.lookupSCC(B)); 658 EXPECT_EQ(&SCC, CG1.lookupSCC(C)); 659 } 660 661 TEST(LazyCallGraphTest, IntraSCCEdgeRemoval) { 662 // A nice fully connected (including self-edges) SCC. 663 std::unique_ptr<Module> M1 = parseAssembly( 664 "define void @a() {\n" 665 "entry:\n" 666 " call void @a()\n" 667 " call void @b()\n" 668 " call void @c()\n" 669 " ret void\n" 670 "}\n" 671 "define void @b() {\n" 672 "entry:\n" 673 " call void @a()\n" 674 " call void @b()\n" 675 " call void @c()\n" 676 " ret void\n" 677 "}\n" 678 "define void @c() {\n" 679 "entry:\n" 680 " call void @a()\n" 681 " call void @b()\n" 682 " call void @c()\n" 683 " ret void\n" 684 "}\n"); 685 LazyCallGraph CG1(*M1); 686 687 // Force the graph to be fully expanded. 688 auto SCCI = CG1.postorder_scc_begin(); 689 LazyCallGraph::SCC &SCC = *SCCI++; 690 EXPECT_EQ(CG1.postorder_scc_end(), SCCI); 691 692 LazyCallGraph::Node &A = *CG1.lookup(lookupFunction(*M1, "a")); 693 LazyCallGraph::Node &B = *CG1.lookup(lookupFunction(*M1, "b")); 694 LazyCallGraph::Node &C = *CG1.lookup(lookupFunction(*M1, "c")); 695 EXPECT_EQ(&SCC, CG1.lookupSCC(A)); 696 EXPECT_EQ(&SCC, CG1.lookupSCC(B)); 697 EXPECT_EQ(&SCC, CG1.lookupSCC(C)); 698 699 // Remove the edge from b -> a, which should leave the 3 functions still in 700 // a single connected component because of a -> b -> c -> a. 701 SmallVector<LazyCallGraph::SCC *, 1> NewSCCs = SCC.removeIntraSCCEdge(B, A); 702 EXPECT_EQ(0u, NewSCCs.size()); 703 EXPECT_EQ(&SCC, CG1.lookupSCC(A)); 704 EXPECT_EQ(&SCC, CG1.lookupSCC(B)); 705 EXPECT_EQ(&SCC, CG1.lookupSCC(C)); 706 707 // Remove the edge from c -> a, which should leave 'a' in the original SCC 708 // and form a new SCC for 'b' and 'c'. 709 NewSCCs = SCC.removeIntraSCCEdge(C, A); 710 EXPECT_EQ(1u, NewSCCs.size()); 711 EXPECT_EQ(&SCC, CG1.lookupSCC(A)); 712 EXPECT_EQ(1, std::distance(SCC.begin(), SCC.end())); 713 LazyCallGraph::SCC *SCC2 = CG1.lookupSCC(B); 714 EXPECT_EQ(SCC2, CG1.lookupSCC(C)); 715 EXPECT_EQ(SCC2, NewSCCs[0]); 716 } 717 718 } 719