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