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++)->getNode(CG); 132 EXPECT_EQ("a1", A1.getFunction().getName()); 133 LazyCallGraph::Node &A2 = (I++)->getNode(CG); 134 EXPECT_EQ("a2", A2.getFunction().getName()); 135 LazyCallGraph::Node &A3 = (I++)->getNode(CG); 136 EXPECT_EQ("a3", A3.getFunction().getName()); 137 LazyCallGraph::Node &B1 = (I++)->getNode(CG); 138 EXPECT_EQ("b1", B1.getFunction().getName()); 139 LazyCallGraph::Node &B2 = (I++)->getNode(CG); 140 EXPECT_EQ("b2", B2.getFunction().getName()); 141 LazyCallGraph::Node &B3 = (I++)->getNode(CG); 142 EXPECT_EQ("b3", B3.getFunction().getName()); 143 LazyCallGraph::Node &C1 = (I++)->getNode(CG); 144 EXPECT_EQ("c1", C1.getFunction().getName()); 145 LazyCallGraph::Node &C2 = (I++)->getNode(CG); 146 EXPECT_EQ("c2", C2.getFunction().getName()); 147 LazyCallGraph::Node &C3 = (I++)->getNode(CG); 148 EXPECT_EQ("c3", C3.getFunction().getName()); 149 LazyCallGraph::Node &D1 = (I++)->getNode(CG); 150 EXPECT_EQ("d1", D1.getFunction().getName()); 151 LazyCallGraph::Node &D2 = (I++)->getNode(CG); 152 EXPECT_EQ("d2", D2.getFunction().getName()); 153 LazyCallGraph::Node &D3 = (I++)->getNode(CG); 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::Edge &E : A1) 162 Nodes.push_back(E.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::Edge &E : B1) 175 Nodes.push_back(E.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::Edge &E : C1) 187 Nodes.push_back(E.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 RefSCCs and SCCs. 206 auto J = CG.postorder_ref_scc_begin(); 207 208 LazyCallGraph::RefSCC &D = *J++; 209 ASSERT_EQ(1, D.size()); 210 for (LazyCallGraph::Node &N : *D.begin()) 211 Nodes.push_back(N.getFunction().getName()); 212 std::sort(Nodes.begin(), Nodes.end()); 213 EXPECT_EQ(3u, Nodes.size()); 214 EXPECT_EQ("d1", Nodes[0]); 215 EXPECT_EQ("d2", Nodes[1]); 216 EXPECT_EQ("d3", Nodes[2]); 217 Nodes.clear(); 218 EXPECT_FALSE(D.isParentOf(D)); 219 EXPECT_FALSE(D.isChildOf(D)); 220 EXPECT_FALSE(D.isAncestorOf(D)); 221 EXPECT_FALSE(D.isDescendantOf(D)); 222 223 LazyCallGraph::RefSCC &C = *J++; 224 ASSERT_EQ(1, C.size()); 225 for (LazyCallGraph::Node &N : *C.begin()) 226 Nodes.push_back(N.getFunction().getName()); 227 std::sort(Nodes.begin(), Nodes.end()); 228 EXPECT_EQ(3u, Nodes.size()); 229 EXPECT_EQ("c1", Nodes[0]); 230 EXPECT_EQ("c2", Nodes[1]); 231 EXPECT_EQ("c3", Nodes[2]); 232 Nodes.clear(); 233 EXPECT_TRUE(C.isParentOf(D)); 234 EXPECT_FALSE(C.isChildOf(D)); 235 EXPECT_TRUE(C.isAncestorOf(D)); 236 EXPECT_FALSE(C.isDescendantOf(D)); 237 238 LazyCallGraph::RefSCC &B = *J++; 239 ASSERT_EQ(1, B.size()); 240 for (LazyCallGraph::Node &N : *B.begin()) 241 Nodes.push_back(N.getFunction().getName()); 242 std::sort(Nodes.begin(), Nodes.end()); 243 EXPECT_EQ(3u, Nodes.size()); 244 EXPECT_EQ("b1", Nodes[0]); 245 EXPECT_EQ("b2", Nodes[1]); 246 EXPECT_EQ("b3", Nodes[2]); 247 Nodes.clear(); 248 EXPECT_TRUE(B.isParentOf(D)); 249 EXPECT_FALSE(B.isChildOf(D)); 250 EXPECT_TRUE(B.isAncestorOf(D)); 251 EXPECT_FALSE(B.isDescendantOf(D)); 252 EXPECT_FALSE(B.isAncestorOf(C)); 253 EXPECT_FALSE(C.isAncestorOf(B)); 254 255 LazyCallGraph::RefSCC &A = *J++; 256 ASSERT_EQ(1, A.size()); 257 for (LazyCallGraph::Node &N : *A.begin()) 258 Nodes.push_back(N.getFunction().getName()); 259 std::sort(Nodes.begin(), Nodes.end()); 260 EXPECT_EQ(3u, Nodes.size()); 261 EXPECT_EQ("a1", Nodes[0]); 262 EXPECT_EQ("a2", Nodes[1]); 263 EXPECT_EQ("a3", Nodes[2]); 264 Nodes.clear(); 265 EXPECT_TRUE(A.isParentOf(B)); 266 EXPECT_TRUE(A.isParentOf(C)); 267 EXPECT_FALSE(A.isParentOf(D)); 268 EXPECT_TRUE(A.isAncestorOf(B)); 269 EXPECT_TRUE(A.isAncestorOf(C)); 270 EXPECT_TRUE(A.isAncestorOf(D)); 271 272 EXPECT_EQ(CG.postorder_ref_scc_end(), J); 273 } 274 275 static Function &lookupFunction(Module &M, StringRef Name) { 276 for (Function &F : M) 277 if (F.getName() == Name) 278 return F; 279 report_fatal_error("Couldn't find function!"); 280 } 281 282 TEST(LazyCallGraphTest, BasicGraphMutation) { 283 std::unique_ptr<Module> M = parseAssembly( 284 "define void @a() {\n" 285 "entry:\n" 286 " call void @b()\n" 287 " call void @c()\n" 288 " ret void\n" 289 "}\n" 290 "define void @b() {\n" 291 "entry:\n" 292 " ret void\n" 293 "}\n" 294 "define void @c() {\n" 295 "entry:\n" 296 " ret void\n" 297 "}\n"); 298 LazyCallGraph CG(*M); 299 300 LazyCallGraph::Node &A = CG.get(lookupFunction(*M, "a")); 301 LazyCallGraph::Node &B = CG.get(lookupFunction(*M, "b")); 302 EXPECT_EQ(2, std::distance(A.begin(), A.end())); 303 EXPECT_EQ(0, std::distance(B.begin(), B.end())); 304 305 CG.insertEdge(B, lookupFunction(*M, "c"), LazyCallGraph::Edge::Call); 306 EXPECT_EQ(1, std::distance(B.begin(), B.end())); 307 LazyCallGraph::Node &C = B.begin()->getNode(CG); 308 EXPECT_EQ(0, std::distance(C.begin(), C.end())); 309 310 CG.insertEdge(C, B.getFunction(), LazyCallGraph::Edge::Call); 311 EXPECT_EQ(1, std::distance(C.begin(), C.end())); 312 EXPECT_EQ(&B, C.begin()->getNode()); 313 314 CG.insertEdge(C, C.getFunction(), LazyCallGraph::Edge::Call); 315 EXPECT_EQ(2, std::distance(C.begin(), C.end())); 316 EXPECT_EQ(&B, C.begin()->getNode()); 317 EXPECT_EQ(&C, std::next(C.begin())->getNode()); 318 319 CG.removeEdge(C, B.getFunction()); 320 EXPECT_EQ(1, std::distance(C.begin(), C.end())); 321 EXPECT_EQ(&C, C.begin()->getNode()); 322 323 CG.removeEdge(C, C.getFunction()); 324 EXPECT_EQ(0, std::distance(C.begin(), C.end())); 325 326 CG.removeEdge(B, C.getFunction()); 327 EXPECT_EQ(0, std::distance(B.begin(), B.end())); 328 } 329 330 TEST(LazyCallGraphTest, InnerSCCFormation) { 331 std::unique_ptr<Module> M = parseAssembly(DiamondOfTriangles); 332 LazyCallGraph CG(*M); 333 334 // Now mutate the graph to connect every node into a single RefSCC to ensure 335 // that our inner SCC formation handles the rest. 336 CG.insertEdge(lookupFunction(*M, "d1"), lookupFunction(*M, "a1"), 337 LazyCallGraph::Edge::Ref); 338 339 // Build vectors and sort them for the rest of the assertions to make them 340 // independent of order. 341 std::vector<std::string> Nodes; 342 343 // We should build a single RefSCC for the entire graph. 344 auto I = CG.postorder_ref_scc_begin(); 345 LazyCallGraph::RefSCC &RC = *I++; 346 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 347 348 // Now walk the four SCCs which should be in post-order. 349 auto J = RC.begin(); 350 LazyCallGraph::SCC &D = *J++; 351 for (LazyCallGraph::Node &N : D) 352 Nodes.push_back(N.getFunction().getName()); 353 std::sort(Nodes.begin(), Nodes.end()); 354 EXPECT_EQ(3u, Nodes.size()); 355 EXPECT_EQ("d1", Nodes[0]); 356 EXPECT_EQ("d2", Nodes[1]); 357 EXPECT_EQ("d3", Nodes[2]); 358 Nodes.clear(); 359 360 LazyCallGraph::SCC &B = *J++; 361 for (LazyCallGraph::Node &N : B) 362 Nodes.push_back(N.getFunction().getName()); 363 std::sort(Nodes.begin(), Nodes.end()); 364 EXPECT_EQ(3u, Nodes.size()); 365 EXPECT_EQ("b1", Nodes[0]); 366 EXPECT_EQ("b2", Nodes[1]); 367 EXPECT_EQ("b3", Nodes[2]); 368 Nodes.clear(); 369 370 LazyCallGraph::SCC &C = *J++; 371 for (LazyCallGraph::Node &N : C) 372 Nodes.push_back(N.getFunction().getName()); 373 std::sort(Nodes.begin(), Nodes.end()); 374 EXPECT_EQ(3u, Nodes.size()); 375 EXPECT_EQ("c1", Nodes[0]); 376 EXPECT_EQ("c2", Nodes[1]); 377 EXPECT_EQ("c3", Nodes[2]); 378 Nodes.clear(); 379 380 LazyCallGraph::SCC &A = *J++; 381 for (LazyCallGraph::Node &N : A) 382 Nodes.push_back(N.getFunction().getName()); 383 std::sort(Nodes.begin(), Nodes.end()); 384 EXPECT_EQ(3u, Nodes.size()); 385 EXPECT_EQ("a1", Nodes[0]); 386 EXPECT_EQ("a2", Nodes[1]); 387 EXPECT_EQ("a3", Nodes[2]); 388 Nodes.clear(); 389 390 EXPECT_EQ(RC.end(), J); 391 } 392 393 TEST(LazyCallGraphTest, MultiArmSCC) { 394 // Two interlocking cycles. The really useful thing about this SCC is that it 395 // will require Tarjan's DFS to backtrack and finish processing all of the 396 // children of each node in the SCC. Since this involves call edges, both 397 // Tarjan implementations will have to successfully navigate the structure. 398 std::unique_ptr<Module> M = parseAssembly( 399 "define void @f1() {\n" 400 "entry:\n" 401 " call void @f2()\n" 402 " call void @f4()\n" 403 " ret void\n" 404 "}\n" 405 "define void @f2() {\n" 406 "entry:\n" 407 " call void @f3()\n" 408 " ret void\n" 409 "}\n" 410 "define void @f3() {\n" 411 "entry:\n" 412 " call void @f1()\n" 413 " ret void\n" 414 "}\n" 415 "define void @f4() {\n" 416 "entry:\n" 417 " call void @f5()\n" 418 " ret void\n" 419 "}\n" 420 "define void @f5() {\n" 421 "entry:\n" 422 " call void @f1()\n" 423 " ret void\n" 424 "}\n"); 425 LazyCallGraph CG(*M); 426 427 // Force the graph to be fully expanded. 428 auto I = CG.postorder_ref_scc_begin(); 429 LazyCallGraph::RefSCC &RC = *I++; 430 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 431 432 LazyCallGraph::Node &N1 = *CG.lookup(lookupFunction(*M, "f1")); 433 LazyCallGraph::Node &N2 = *CG.lookup(lookupFunction(*M, "f2")); 434 LazyCallGraph::Node &N3 = *CG.lookup(lookupFunction(*M, "f3")); 435 LazyCallGraph::Node &N4 = *CG.lookup(lookupFunction(*M, "f4")); 436 LazyCallGraph::Node &N5 = *CG.lookup(lookupFunction(*M, "f4")); 437 EXPECT_EQ(&RC, CG.lookupRefSCC(N1)); 438 EXPECT_EQ(&RC, CG.lookupRefSCC(N2)); 439 EXPECT_EQ(&RC, CG.lookupRefSCC(N3)); 440 EXPECT_EQ(&RC, CG.lookupRefSCC(N4)); 441 EXPECT_EQ(&RC, CG.lookupRefSCC(N5)); 442 443 ASSERT_EQ(1, RC.size()); 444 445 LazyCallGraph::SCC &C = *RC.begin(); 446 EXPECT_EQ(&C, CG.lookupSCC(N1)); 447 EXPECT_EQ(&C, CG.lookupSCC(N2)); 448 EXPECT_EQ(&C, CG.lookupSCC(N3)); 449 EXPECT_EQ(&C, CG.lookupSCC(N4)); 450 EXPECT_EQ(&C, CG.lookupSCC(N5)); 451 } 452 453 TEST(LazyCallGraphTest, OutgoingEdgeMutation) { 454 std::unique_ptr<Module> M = parseAssembly( 455 "define void @a() {\n" 456 "entry:\n" 457 " call void @b()\n" 458 " call void @c()\n" 459 " ret void\n" 460 "}\n" 461 "define void @b() {\n" 462 "entry:\n" 463 " call void @d()\n" 464 " ret void\n" 465 "}\n" 466 "define void @c() {\n" 467 "entry:\n" 468 " call void @d()\n" 469 " ret void\n" 470 "}\n" 471 "define void @d() {\n" 472 "entry:\n" 473 " ret void\n" 474 "}\n"); 475 LazyCallGraph CG(*M); 476 477 // Force the graph to be fully expanded. 478 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) 479 (void)RC; 480 481 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 482 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 483 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 484 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); 485 LazyCallGraph::SCC &AC = *CG.lookupSCC(A); 486 LazyCallGraph::SCC &BC = *CG.lookupSCC(B); 487 LazyCallGraph::SCC &CC = *CG.lookupSCC(C); 488 LazyCallGraph::SCC &DC = *CG.lookupSCC(D); 489 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A); 490 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B); 491 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C); 492 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D); 493 EXPECT_TRUE(ARC.isParentOf(BRC)); 494 EXPECT_TRUE(ARC.isParentOf(CRC)); 495 EXPECT_FALSE(ARC.isParentOf(DRC)); 496 EXPECT_TRUE(ARC.isAncestorOf(DRC)); 497 EXPECT_FALSE(DRC.isChildOf(ARC)); 498 EXPECT_TRUE(DRC.isDescendantOf(ARC)); 499 EXPECT_TRUE(DRC.isChildOf(BRC)); 500 EXPECT_TRUE(DRC.isChildOf(CRC)); 501 502 EXPECT_EQ(2, std::distance(A.begin(), A.end())); 503 ARC.insertOutgoingEdge(A, D, LazyCallGraph::Edge::Call); 504 EXPECT_EQ(3, std::distance(A.begin(), A.end())); 505 const LazyCallGraph::Edge &NewE = A[D]; 506 EXPECT_TRUE(NewE); 507 EXPECT_TRUE(NewE.isCall()); 508 EXPECT_EQ(&D, NewE.getNode()); 509 510 // Only the parent and child tests sholud have changed. The rest of the graph 511 // remains the same. 512 EXPECT_TRUE(ARC.isParentOf(DRC)); 513 EXPECT_TRUE(ARC.isAncestorOf(DRC)); 514 EXPECT_TRUE(DRC.isChildOf(ARC)); 515 EXPECT_TRUE(DRC.isDescendantOf(ARC)); 516 EXPECT_EQ(&AC, CG.lookupSCC(A)); 517 EXPECT_EQ(&BC, CG.lookupSCC(B)); 518 EXPECT_EQ(&CC, CG.lookupSCC(C)); 519 EXPECT_EQ(&DC, CG.lookupSCC(D)); 520 EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); 521 EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); 522 EXPECT_EQ(&CRC, CG.lookupRefSCC(C)); 523 EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); 524 525 ARC.switchOutgoingEdgeToRef(A, D); 526 EXPECT_FALSE(NewE.isCall()); 527 528 // Verify the graph remains the same. 529 EXPECT_TRUE(ARC.isParentOf(DRC)); 530 EXPECT_TRUE(ARC.isAncestorOf(DRC)); 531 EXPECT_TRUE(DRC.isChildOf(ARC)); 532 EXPECT_TRUE(DRC.isDescendantOf(ARC)); 533 EXPECT_EQ(&AC, CG.lookupSCC(A)); 534 EXPECT_EQ(&BC, CG.lookupSCC(B)); 535 EXPECT_EQ(&CC, CG.lookupSCC(C)); 536 EXPECT_EQ(&DC, CG.lookupSCC(D)); 537 EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); 538 EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); 539 EXPECT_EQ(&CRC, CG.lookupRefSCC(C)); 540 EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); 541 542 ARC.switchOutgoingEdgeToCall(A, D); 543 EXPECT_TRUE(NewE.isCall()); 544 545 // Verify the graph remains the same. 546 EXPECT_TRUE(ARC.isParentOf(DRC)); 547 EXPECT_TRUE(ARC.isAncestorOf(DRC)); 548 EXPECT_TRUE(DRC.isChildOf(ARC)); 549 EXPECT_TRUE(DRC.isDescendantOf(ARC)); 550 EXPECT_EQ(&AC, CG.lookupSCC(A)); 551 EXPECT_EQ(&BC, CG.lookupSCC(B)); 552 EXPECT_EQ(&CC, CG.lookupSCC(C)); 553 EXPECT_EQ(&DC, CG.lookupSCC(D)); 554 EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); 555 EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); 556 EXPECT_EQ(&CRC, CG.lookupRefSCC(C)); 557 EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); 558 559 ARC.removeOutgoingEdge(A, D); 560 EXPECT_EQ(2, std::distance(A.begin(), A.end())); 561 562 // Now the parent and child tests fail again but the rest remains the same. 563 EXPECT_FALSE(ARC.isParentOf(DRC)); 564 EXPECT_TRUE(ARC.isAncestorOf(DRC)); 565 EXPECT_FALSE(DRC.isChildOf(ARC)); 566 EXPECT_TRUE(DRC.isDescendantOf(ARC)); 567 EXPECT_EQ(&AC, CG.lookupSCC(A)); 568 EXPECT_EQ(&BC, CG.lookupSCC(B)); 569 EXPECT_EQ(&CC, CG.lookupSCC(C)); 570 EXPECT_EQ(&DC, CG.lookupSCC(D)); 571 EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); 572 EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); 573 EXPECT_EQ(&CRC, CG.lookupRefSCC(C)); 574 EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); 575 } 576 577 TEST(LazyCallGraphTest, IncomingEdgeInsertion) { 578 // We want to ensure we can add edges even across complex diamond graphs, so 579 // we use the diamond of triangles graph defined above. The ascii diagram is 580 // repeated here for easy reference. 581 // 582 // d1 | 583 // / \ | 584 // d3--d2 | 585 // / \ | 586 // b1 c1 | 587 // / \ / \ | 588 // b3--b2 c3--c2 | 589 // \ / | 590 // a1 | 591 // / \ | 592 // a3--a2 | 593 // 594 std::unique_ptr<Module> M = parseAssembly(DiamondOfTriangles); 595 LazyCallGraph CG(*M); 596 597 // Force the graph to be fully expanded. 598 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) 599 (void)RC; 600 601 LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1")); 602 LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2")); 603 LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3")); 604 LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1")); 605 LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2")); 606 LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3")); 607 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1")); 608 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2")); 609 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3")); 610 LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1")); 611 LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2")); 612 LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3")); 613 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A1); 614 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B1); 615 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C1); 616 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D1); 617 ASSERT_EQ(&ARC, CG.lookupRefSCC(A2)); 618 ASSERT_EQ(&ARC, CG.lookupRefSCC(A3)); 619 ASSERT_EQ(&BRC, CG.lookupRefSCC(B2)); 620 ASSERT_EQ(&BRC, CG.lookupRefSCC(B3)); 621 ASSERT_EQ(&CRC, CG.lookupRefSCC(C2)); 622 ASSERT_EQ(&CRC, CG.lookupRefSCC(C3)); 623 ASSERT_EQ(&DRC, CG.lookupRefSCC(D2)); 624 ASSERT_EQ(&DRC, CG.lookupRefSCC(D3)); 625 ASSERT_EQ(1, std::distance(D2.begin(), D2.end())); 626 627 // Add an edge to make the graph: 628 // 629 // d1 | 630 // / \ | 631 // d3--d2---. | 632 // / \ | | 633 // b1 c1 | | 634 // / \ / \ / | 635 // b3--b2 c3--c2 | 636 // \ / | 637 // a1 | 638 // / \ | 639 // a3--a2 | 640 auto MergedRCs = CRC.insertIncomingRefEdge(D2, C2); 641 // Make sure we connected the nodes. 642 for (LazyCallGraph::Edge E : D2) { 643 if (E.getNode() == &D3) 644 continue; 645 EXPECT_EQ(&C2, E.getNode()); 646 } 647 // And marked the D ref-SCC as no longer valid. 648 EXPECT_EQ(1u, MergedRCs.size()); 649 EXPECT_EQ(&DRC, MergedRCs[0]); 650 651 // Make sure we have the correct nodes in the SCC sets. 652 EXPECT_EQ(&ARC, CG.lookupRefSCC(A1)); 653 EXPECT_EQ(&ARC, CG.lookupRefSCC(A2)); 654 EXPECT_EQ(&ARC, CG.lookupRefSCC(A3)); 655 EXPECT_EQ(&BRC, CG.lookupRefSCC(B1)); 656 EXPECT_EQ(&BRC, CG.lookupRefSCC(B2)); 657 EXPECT_EQ(&BRC, CG.lookupRefSCC(B3)); 658 EXPECT_EQ(&CRC, CG.lookupRefSCC(C1)); 659 EXPECT_EQ(&CRC, CG.lookupRefSCC(C2)); 660 EXPECT_EQ(&CRC, CG.lookupRefSCC(C3)); 661 EXPECT_EQ(&CRC, CG.lookupRefSCC(D1)); 662 EXPECT_EQ(&CRC, CG.lookupRefSCC(D2)); 663 EXPECT_EQ(&CRC, CG.lookupRefSCC(D3)); 664 665 // And that ancestry tests have been updated. 666 EXPECT_TRUE(ARC.isParentOf(CRC)); 667 EXPECT_TRUE(BRC.isParentOf(CRC)); 668 } 669 670 TEST(LazyCallGraphTest, IncomingEdgeInsertionMidTraversal) { 671 // This is the same fundamental test as the previous, but we perform it 672 // having only partially walked the RefSCCs of the graph. 673 std::unique_ptr<Module> M = parseAssembly(DiamondOfTriangles); 674 LazyCallGraph CG(*M); 675 676 // Walk the RefSCCs until we find the one containing 'c1'. 677 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); 678 ASSERT_NE(I, E); 679 LazyCallGraph::RefSCC &DRC = *I; 680 ASSERT_NE(&DRC, nullptr); 681 ++I; 682 ASSERT_NE(I, E); 683 LazyCallGraph::RefSCC &CRC = *I; 684 ASSERT_NE(&CRC, nullptr); 685 686 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a1"))); 687 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a2"))); 688 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a3"))); 689 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b1"))); 690 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b2"))); 691 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b3"))); 692 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1")); 693 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2")); 694 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3")); 695 LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1")); 696 LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2")); 697 LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3")); 698 ASSERT_EQ(&CRC, CG.lookupRefSCC(C1)); 699 ASSERT_EQ(&CRC, CG.lookupRefSCC(C2)); 700 ASSERT_EQ(&CRC, CG.lookupRefSCC(C3)); 701 ASSERT_EQ(&DRC, CG.lookupRefSCC(D1)); 702 ASSERT_EQ(&DRC, CG.lookupRefSCC(D2)); 703 ASSERT_EQ(&DRC, CG.lookupRefSCC(D3)); 704 ASSERT_EQ(1, std::distance(D2.begin(), D2.end())); 705 706 auto MergedRCs = CRC.insertIncomingRefEdge(D2, C2); 707 // Make sure we connected the nodes. 708 for (LazyCallGraph::Edge E : D2) { 709 if (E.getNode() == &D3) 710 continue; 711 EXPECT_EQ(&C2, E.getNode()); 712 } 713 // And marked the D ref-SCC as no longer valid. 714 EXPECT_EQ(1u, MergedRCs.size()); 715 EXPECT_EQ(&DRC, MergedRCs[0]); 716 717 // Make sure we have the correct nodes in the RefSCCs. 718 EXPECT_EQ(&CRC, CG.lookupRefSCC(C1)); 719 EXPECT_EQ(&CRC, CG.lookupRefSCC(C2)); 720 EXPECT_EQ(&CRC, CG.lookupRefSCC(C3)); 721 EXPECT_EQ(&CRC, CG.lookupRefSCC(D1)); 722 EXPECT_EQ(&CRC, CG.lookupRefSCC(D2)); 723 EXPECT_EQ(&CRC, CG.lookupRefSCC(D3)); 724 725 // Check that we can form the last two RefSCCs now in a coherent way. 726 ++I; 727 EXPECT_NE(I, E); 728 LazyCallGraph::RefSCC &BRC = *I; 729 EXPECT_NE(&BRC, nullptr); 730 EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b1")))); 731 EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b2")))); 732 EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b3")))); 733 EXPECT_TRUE(BRC.isParentOf(CRC)); 734 ++I; 735 EXPECT_NE(I, E); 736 LazyCallGraph::RefSCC &ARC = *I; 737 EXPECT_NE(&ARC, nullptr); 738 EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a1")))); 739 EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a2")))); 740 EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a3")))); 741 EXPECT_TRUE(ARC.isParentOf(CRC)); 742 ++I; 743 EXPECT_EQ(E, I); 744 } 745 746 TEST(LazyCallGraphTest, InternalEdgeMutation) { 747 std::unique_ptr<Module> M = parseAssembly( 748 "define void @a() {\n" 749 "entry:\n" 750 " call void @b()\n" 751 " ret void\n" 752 "}\n" 753 "define void @b() {\n" 754 "entry:\n" 755 " call void @c()\n" 756 " ret void\n" 757 "}\n" 758 "define void @c() {\n" 759 "entry:\n" 760 " call void @a()\n" 761 " ret void\n" 762 "}\n"); 763 LazyCallGraph CG(*M); 764 765 // Force the graph to be fully expanded. 766 auto I = CG.postorder_ref_scc_begin(); 767 LazyCallGraph::RefSCC &RC = *I++; 768 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 769 770 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 771 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 772 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 773 EXPECT_EQ(&RC, CG.lookupRefSCC(A)); 774 EXPECT_EQ(&RC, CG.lookupRefSCC(B)); 775 EXPECT_EQ(&RC, CG.lookupRefSCC(C)); 776 EXPECT_EQ(1, RC.size()); 777 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(A)); 778 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(B)); 779 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(C)); 780 781 // Insert an edge from 'a' to 'c'. Nothing changes about the graph. 782 RC.insertInternalRefEdge(A, C); 783 EXPECT_EQ(2, std::distance(A.begin(), A.end())); 784 EXPECT_EQ(&RC, CG.lookupRefSCC(A)); 785 EXPECT_EQ(&RC, CG.lookupRefSCC(B)); 786 EXPECT_EQ(&RC, CG.lookupRefSCC(C)); 787 EXPECT_EQ(1, RC.size()); 788 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(A)); 789 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(B)); 790 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(C)); 791 792 // Switch the call edge from 'b' to 'c' to a ref edge. This will break the 793 // call cycle and cause us to form more SCCs. The RefSCC will remain the same 794 // though. 795 RC.switchInternalEdgeToRef(B, C); 796 EXPECT_EQ(&RC, CG.lookupRefSCC(A)); 797 EXPECT_EQ(&RC, CG.lookupRefSCC(B)); 798 EXPECT_EQ(&RC, CG.lookupRefSCC(C)); 799 auto J = RC.begin(); 800 // The SCCs must be in *post-order* which means successors before 801 // predecessors. At this point we have call edges from C to A and from A to 802 // B. The only valid postorder is B, A, C. 803 EXPECT_EQ(&*J++, CG.lookupSCC(B)); 804 EXPECT_EQ(&*J++, CG.lookupSCC(A)); 805 EXPECT_EQ(&*J++, CG.lookupSCC(C)); 806 EXPECT_EQ(RC.end(), J); 807 808 // Test turning the ref edge from A to C into a call edge. This will form an 809 // SCC out of A and C. Since we previously had a call edge from C to A, the 810 // C SCC should be preserved and have A merged into it while the A SCC should 811 // be invalidated. 812 LazyCallGraph::SCC &AC = *CG.lookupSCC(A); 813 LazyCallGraph::SCC &CC = *CG.lookupSCC(C); 814 auto InvalidatedSCCs = RC.switchInternalEdgeToCall(A, C); 815 ASSERT_EQ(1u, InvalidatedSCCs.size()); 816 EXPECT_EQ(&AC, InvalidatedSCCs[0]); 817 EXPECT_EQ(2, CC.size()); 818 EXPECT_EQ(&CC, CG.lookupSCC(A)); 819 EXPECT_EQ(&CC, CG.lookupSCC(C)); 820 J = RC.begin(); 821 EXPECT_EQ(&*J++, CG.lookupSCC(B)); 822 EXPECT_EQ(&*J++, CG.lookupSCC(C)); 823 EXPECT_EQ(RC.end(), J); 824 } 825 826 TEST(LazyCallGraphTest, InternalEdgeRemoval) { 827 // A nice fully connected (including self-edges) RefSCC. 828 std::unique_ptr<Module> M = parseAssembly( 829 "define void @a(i8** %ptr) {\n" 830 "entry:\n" 831 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" 832 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" 833 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" 834 " ret void\n" 835 "}\n" 836 "define void @b(i8** %ptr) {\n" 837 "entry:\n" 838 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" 839 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" 840 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" 841 " ret void\n" 842 "}\n" 843 "define void @c(i8** %ptr) {\n" 844 "entry:\n" 845 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" 846 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" 847 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" 848 " ret void\n" 849 "}\n"); 850 LazyCallGraph CG(*M); 851 852 // Force the graph to be fully expanded. 853 auto I = CG.postorder_ref_scc_begin(); 854 LazyCallGraph::RefSCC &RC = *I++; 855 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 856 857 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 858 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 859 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 860 EXPECT_EQ(&RC, CG.lookupRefSCC(A)); 861 EXPECT_EQ(&RC, CG.lookupRefSCC(B)); 862 EXPECT_EQ(&RC, CG.lookupRefSCC(C)); 863 864 // Remove the edge from b -> a, which should leave the 3 functions still in 865 // a single connected component because of a -> b -> c -> a. 866 SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs = 867 RC.removeInternalRefEdge(B, A); 868 EXPECT_EQ(0u, NewRCs.size()); 869 EXPECT_EQ(&RC, CG.lookupRefSCC(A)); 870 EXPECT_EQ(&RC, CG.lookupRefSCC(B)); 871 EXPECT_EQ(&RC, CG.lookupRefSCC(C)); 872 873 // Remove the edge from c -> a, which should leave 'a' in the original RefSCC 874 // and form a new RefSCC for 'b' and 'c'. 875 NewRCs = RC.removeInternalRefEdge(C, A); 876 EXPECT_EQ(1u, NewRCs.size()); 877 EXPECT_EQ(&RC, CG.lookupRefSCC(A)); 878 EXPECT_EQ(1, std::distance(RC.begin(), RC.end())); 879 LazyCallGraph::RefSCC *RC2 = CG.lookupRefSCC(B); 880 EXPECT_EQ(RC2, CG.lookupRefSCC(C)); 881 EXPECT_EQ(RC2, NewRCs[0]); 882 } 883 884 TEST(LazyCallGraphTest, InternalCallEdgeToRef) { 885 // A nice fully connected (including self-edges) SCC (and RefSCC) 886 std::unique_ptr<Module> M = parseAssembly( 887 "define void @a() {\n" 888 "entry:\n" 889 " call void @a()\n" 890 " call void @b()\n" 891 " call void @c()\n" 892 " ret void\n" 893 "}\n" 894 "define void @b() {\n" 895 "entry:\n" 896 " call void @a()\n" 897 " call void @b()\n" 898 " call void @c()\n" 899 " ret void\n" 900 "}\n" 901 "define void @c() {\n" 902 "entry:\n" 903 " call void @a()\n" 904 " call void @b()\n" 905 " call void @c()\n" 906 " ret void\n" 907 "}\n"); 908 LazyCallGraph CG(*M); 909 910 // Force the graph to be fully expanded. 911 auto I = CG.postorder_ref_scc_begin(); 912 LazyCallGraph::RefSCC &RC = *I++; 913 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 914 915 EXPECT_EQ(1, RC.size()); 916 LazyCallGraph::SCC &CallC = *RC.begin(); 917 918 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 919 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 920 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 921 EXPECT_EQ(&CallC, CG.lookupSCC(A)); 922 EXPECT_EQ(&CallC, CG.lookupSCC(B)); 923 EXPECT_EQ(&CallC, CG.lookupSCC(C)); 924 925 // Remove the call edge from b -> a to a ref edge, which should leave the 926 // 3 functions still in a single connected component because of a -> b -> 927 // c -> a. 928 RC.switchInternalEdgeToRef(B, A); 929 EXPECT_EQ(1, RC.size()); 930 EXPECT_EQ(&CallC, CG.lookupSCC(A)); 931 EXPECT_EQ(&CallC, CG.lookupSCC(B)); 932 EXPECT_EQ(&CallC, CG.lookupSCC(C)); 933 934 // Remove the edge from c -> a, which should leave 'a' in the original SCC 935 // and form a new SCC for 'b' and 'c'. 936 RC.switchInternalEdgeToRef(C, A); 937 EXPECT_EQ(2, RC.size()); 938 EXPECT_EQ(&CallC, CG.lookupSCC(A)); 939 LazyCallGraph::SCC &BCallC = *CG.lookupSCC(B); 940 EXPECT_NE(&BCallC, &CallC); 941 EXPECT_EQ(&BCallC, CG.lookupSCC(C)); 942 auto J = RC.find(CallC); 943 EXPECT_EQ(&CallC, &*J); 944 --J; 945 EXPECT_EQ(&BCallC, &*J); 946 EXPECT_EQ(RC.begin(), J); 947 948 // Remove the edge from c -> b, which should leave 'b' in the original SCC 949 // and form a new SCC for 'c'. It shouldn't change 'a's SCC. 950 RC.switchInternalEdgeToRef(C, B); 951 EXPECT_EQ(3, RC.size()); 952 EXPECT_EQ(&CallC, CG.lookupSCC(A)); 953 EXPECT_EQ(&BCallC, CG.lookupSCC(B)); 954 LazyCallGraph::SCC &CCallC = *CG.lookupSCC(C); 955 EXPECT_NE(&CCallC, &CallC); 956 EXPECT_NE(&CCallC, &BCallC); 957 J = RC.find(CallC); 958 EXPECT_EQ(&CallC, &*J); 959 --J; 960 EXPECT_EQ(&BCallC, &*J); 961 --J; 962 EXPECT_EQ(&CCallC, &*J); 963 EXPECT_EQ(RC.begin(), J); 964 } 965 966 TEST(LazyCallGraphTest, InternalRefEdgeToCall) { 967 // Basic tests for making a ref edge a call. This hits the basics of the 968 // process only. 969 std::unique_ptr<Module> M = parseAssembly( 970 "define void @a() {\n" 971 "entry:\n" 972 " call void @b()\n" 973 " call void @c()\n" 974 " store void()* @d, void()** undef\n" 975 " ret void\n" 976 "}\n" 977 "define void @b() {\n" 978 "entry:\n" 979 " store void()* @c, void()** undef\n" 980 " call void @d()\n" 981 " ret void\n" 982 "}\n" 983 "define void @c() {\n" 984 "entry:\n" 985 " store void()* @b, void()** undef\n" 986 " call void @d()\n" 987 " ret void\n" 988 "}\n" 989 "define void @d() {\n" 990 "entry:\n" 991 " store void()* @a, void()** undef\n" 992 " ret void\n" 993 "}\n"); 994 LazyCallGraph CG(*M); 995 996 // Force the graph to be fully expanded. 997 auto I = CG.postorder_ref_scc_begin(); 998 LazyCallGraph::RefSCC &RC = *I++; 999 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 1000 1001 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 1002 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 1003 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 1004 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); 1005 LazyCallGraph::SCC &AC = *CG.lookupSCC(A); 1006 LazyCallGraph::SCC &BC = *CG.lookupSCC(B); 1007 LazyCallGraph::SCC &CC = *CG.lookupSCC(C); 1008 LazyCallGraph::SCC &DC = *CG.lookupSCC(D); 1009 1010 // Check the initial post-order. Note that B and C could be flipped here (and 1011 // in our mutation) without changing the nature of this test. 1012 ASSERT_EQ(4, RC.size()); 1013 EXPECT_EQ(&DC, &RC[0]); 1014 EXPECT_EQ(&BC, &RC[1]); 1015 EXPECT_EQ(&CC, &RC[2]); 1016 EXPECT_EQ(&AC, &RC[3]); 1017 1018 // Switch the ref edge from A -> D to a call edge. This should have no 1019 // effect as it is already in postorder and no new cycles are formed. 1020 auto MergedCs = RC.switchInternalEdgeToCall(A, D); 1021 EXPECT_EQ(0u, MergedCs.size()); 1022 ASSERT_EQ(4, RC.size()); 1023 EXPECT_EQ(&DC, &RC[0]); 1024 EXPECT_EQ(&BC, &RC[1]); 1025 EXPECT_EQ(&CC, &RC[2]); 1026 EXPECT_EQ(&AC, &RC[3]); 1027 1028 // Switch B -> C to a call edge. This doesn't form any new cycles but does 1029 // require reordering the SCCs. 1030 MergedCs = RC.switchInternalEdgeToCall(B, C); 1031 EXPECT_EQ(0u, MergedCs.size()); 1032 ASSERT_EQ(4, RC.size()); 1033 EXPECT_EQ(&DC, &RC[0]); 1034 EXPECT_EQ(&CC, &RC[1]); 1035 EXPECT_EQ(&BC, &RC[2]); 1036 EXPECT_EQ(&AC, &RC[3]); 1037 1038 // Switch C -> B to a call edge. This forms a cycle and forces merging SCCs. 1039 MergedCs = RC.switchInternalEdgeToCall(C, B); 1040 ASSERT_EQ(1u, MergedCs.size()); 1041 EXPECT_EQ(&CC, MergedCs[0]); 1042 ASSERT_EQ(3, RC.size()); 1043 EXPECT_EQ(&DC, &RC[0]); 1044 EXPECT_EQ(&BC, &RC[1]); 1045 EXPECT_EQ(&AC, &RC[2]); 1046 EXPECT_EQ(2, BC.size()); 1047 EXPECT_EQ(&BC, CG.lookupSCC(B)); 1048 EXPECT_EQ(&BC, CG.lookupSCC(C)); 1049 } 1050 1051 TEST(LazyCallGraphTest, InternalRefEdgeToCallNoCycleInterleaved) { 1052 // Test for having a post-order prior to changing a ref edge to a call edge 1053 // with SCCs connecting to the source and connecting to the target, but not 1054 // connecting to both, interleaved between the source and target. This 1055 // ensures we correctly partition the range rather than simply moving one or 1056 // the other. 1057 std::unique_ptr<Module> M = parseAssembly( 1058 "define void @a() {\n" 1059 "entry:\n" 1060 " call void @b1()\n" 1061 " call void @c1()\n" 1062 " ret void\n" 1063 "}\n" 1064 "define void @b1() {\n" 1065 "entry:\n" 1066 " call void @c1()\n" 1067 " call void @b2()\n" 1068 " ret void\n" 1069 "}\n" 1070 "define void @c1() {\n" 1071 "entry:\n" 1072 " call void @b2()\n" 1073 " call void @c2()\n" 1074 " ret void\n" 1075 "}\n" 1076 "define void @b2() {\n" 1077 "entry:\n" 1078 " call void @c2()\n" 1079 " call void @b3()\n" 1080 " ret void\n" 1081 "}\n" 1082 "define void @c2() {\n" 1083 "entry:\n" 1084 " call void @b3()\n" 1085 " call void @c3()\n" 1086 " ret void\n" 1087 "}\n" 1088 "define void @b3() {\n" 1089 "entry:\n" 1090 " call void @c3()\n" 1091 " call void @d()\n" 1092 " ret void\n" 1093 "}\n" 1094 "define void @c3() {\n" 1095 "entry:\n" 1096 " store void()* @b1, void()** undef\n" 1097 " call void @d()\n" 1098 " ret void\n" 1099 "}\n" 1100 "define void @d() {\n" 1101 "entry:\n" 1102 " store void()* @a, void()** undef\n" 1103 " ret void\n" 1104 "}\n"); 1105 LazyCallGraph CG(*M); 1106 1107 // Force the graph to be fully expanded. 1108 auto I = CG.postorder_ref_scc_begin(); 1109 LazyCallGraph::RefSCC &RC = *I++; 1110 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 1111 1112 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 1113 LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1")); 1114 LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2")); 1115 LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3")); 1116 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1")); 1117 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2")); 1118 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3")); 1119 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); 1120 LazyCallGraph::SCC &AC = *CG.lookupSCC(A); 1121 LazyCallGraph::SCC &B1C = *CG.lookupSCC(B1); 1122 LazyCallGraph::SCC &B2C = *CG.lookupSCC(B2); 1123 LazyCallGraph::SCC &B3C = *CG.lookupSCC(B3); 1124 LazyCallGraph::SCC &C1C = *CG.lookupSCC(C1); 1125 LazyCallGraph::SCC &C2C = *CG.lookupSCC(C2); 1126 LazyCallGraph::SCC &C3C = *CG.lookupSCC(C3); 1127 LazyCallGraph::SCC &DC = *CG.lookupSCC(D); 1128 1129 // Several call edges are initially present to force a particual post-order. 1130 // Remove them now, leaving an interleaved post-order pattern. 1131 RC.switchInternalEdgeToRef(B3, C3); 1132 RC.switchInternalEdgeToRef(C2, B3); 1133 RC.switchInternalEdgeToRef(B2, C2); 1134 RC.switchInternalEdgeToRef(C1, B2); 1135 RC.switchInternalEdgeToRef(B1, C1); 1136 1137 // Check the initial post-order. We ensure this order with the extra edges 1138 // that are nuked above. 1139 ASSERT_EQ(8, RC.size()); 1140 EXPECT_EQ(&DC, &RC[0]); 1141 EXPECT_EQ(&C3C, &RC[1]); 1142 EXPECT_EQ(&B3C, &RC[2]); 1143 EXPECT_EQ(&C2C, &RC[3]); 1144 EXPECT_EQ(&B2C, &RC[4]); 1145 EXPECT_EQ(&C1C, &RC[5]); 1146 EXPECT_EQ(&B1C, &RC[6]); 1147 EXPECT_EQ(&AC, &RC[7]); 1148 1149 // Switch C3 -> B1 to a call edge. This doesn't form any new cycles but does 1150 // require reordering the SCCs in the face of tricky internal node 1151 // structures. 1152 auto MergedCs = RC.switchInternalEdgeToCall(C3, B1); 1153 EXPECT_EQ(0u, MergedCs.size()); 1154 ASSERT_EQ(8, RC.size()); 1155 EXPECT_EQ(&DC, &RC[0]); 1156 EXPECT_EQ(&B3C, &RC[1]); 1157 EXPECT_EQ(&B2C, &RC[2]); 1158 EXPECT_EQ(&B1C, &RC[3]); 1159 EXPECT_EQ(&C3C, &RC[4]); 1160 EXPECT_EQ(&C2C, &RC[5]); 1161 EXPECT_EQ(&C1C, &RC[6]); 1162 EXPECT_EQ(&AC, &RC[7]); 1163 } 1164 1165 TEST(LazyCallGraphTest, InternalRefEdgeToCallBothPartitionAndMerge) { 1166 // Test for having a postorder where between the source and target are all 1167 // three kinds of other SCCs: 1168 // 1) One connected to the target only that have to be shifted below the 1169 // source. 1170 // 2) One connected to the source only that have to be shifted below the 1171 // target. 1172 // 3) One connected to both source and target that has to remain and get 1173 // merged away. 1174 // 1175 // To achieve this we construct a heavily connected graph to force 1176 // a particular post-order. Then we remove the forcing edges and connect 1177 // a cycle. 1178 // 1179 // Diagram for the graph we want on the left and the graph we use to force 1180 // the ordering on the right. Edges ponit down or right. 1181 // 1182 // A | A | 1183 // / \ | / \ | 1184 // B E | B \ | 1185 // |\ | | |\ | | 1186 // | D | | C-D-E | 1187 // | \| | | \| | 1188 // C F | \ F | 1189 // \ / | \ / | 1190 // G | G | 1191 // 1192 // And we form a cycle by connecting F to B. 1193 std::unique_ptr<Module> M = parseAssembly( 1194 "define void @a() {\n" 1195 "entry:\n" 1196 " call void @b()\n" 1197 " call void @e()\n" 1198 " ret void\n" 1199 "}\n" 1200 "define void @b() {\n" 1201 "entry:\n" 1202 " call void @c()\n" 1203 " call void @d()\n" 1204 " ret void\n" 1205 "}\n" 1206 "define void @c() {\n" 1207 "entry:\n" 1208 " call void @d()\n" 1209 " call void @g()\n" 1210 " ret void\n" 1211 "}\n" 1212 "define void @d() {\n" 1213 "entry:\n" 1214 " call void @e()\n" 1215 " call void @f()\n" 1216 " ret void\n" 1217 "}\n" 1218 "define void @e() {\n" 1219 "entry:\n" 1220 " call void @f()\n" 1221 " ret void\n" 1222 "}\n" 1223 "define void @f() {\n" 1224 "entry:\n" 1225 " store void()* @b, void()** undef\n" 1226 " call void @g()\n" 1227 " ret void\n" 1228 "}\n" 1229 "define void @g() {\n" 1230 "entry:\n" 1231 " store void()* @a, void()** undef\n" 1232 " ret void\n" 1233 "}\n"); 1234 LazyCallGraph CG(*M); 1235 1236 // Force the graph to be fully expanded. 1237 auto I = CG.postorder_ref_scc_begin(); 1238 LazyCallGraph::RefSCC &RC = *I++; 1239 EXPECT_EQ(CG.postorder_ref_scc_end(), I); 1240 1241 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); 1242 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); 1243 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); 1244 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); 1245 LazyCallGraph::Node &E = *CG.lookup(lookupFunction(*M, "e")); 1246 LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f")); 1247 LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g")); 1248 LazyCallGraph::SCC &AC = *CG.lookupSCC(A); 1249 LazyCallGraph::SCC &BC = *CG.lookupSCC(B); 1250 LazyCallGraph::SCC &CC = *CG.lookupSCC(C); 1251 LazyCallGraph::SCC &DC = *CG.lookupSCC(D); 1252 LazyCallGraph::SCC &EC = *CG.lookupSCC(E); 1253 LazyCallGraph::SCC &FC = *CG.lookupSCC(F); 1254 LazyCallGraph::SCC &GC = *CG.lookupSCC(G); 1255 1256 // Remove the extra edges that were used to force a particular post-order. 1257 RC.switchInternalEdgeToRef(C, D); 1258 RC.switchInternalEdgeToRef(D, E); 1259 1260 // Check the initial post-order. We ensure this order with the extra edges 1261 // that are nuked above. 1262 ASSERT_EQ(7, RC.size()); 1263 EXPECT_EQ(&GC, &RC[0]); 1264 EXPECT_EQ(&FC, &RC[1]); 1265 EXPECT_EQ(&EC, &RC[2]); 1266 EXPECT_EQ(&DC, &RC[3]); 1267 EXPECT_EQ(&CC, &RC[4]); 1268 EXPECT_EQ(&BC, &RC[5]); 1269 EXPECT_EQ(&AC, &RC[6]); 1270 1271 // Switch F -> B to a call edge. This merges B, D, and F into a single SCC, 1272 // and has to place the C and E SCCs on either side of it: 1273 // A A | 1274 // / \ / \ | 1275 // B E | E | 1276 // |\ | \ / | 1277 // | D | -> B | 1278 // | \| / \ | 1279 // C F C | | 1280 // \ / \ / | 1281 // G G | 1282 auto MergedCs = RC.switchInternalEdgeToCall(F, B); 1283 ASSERT_EQ(2u, MergedCs.size()); 1284 EXPECT_EQ(&FC, MergedCs[0]); 1285 EXPECT_EQ(&DC, MergedCs[1]); 1286 EXPECT_EQ(3, BC.size()); 1287 1288 // And make sure the postorder was updated. 1289 ASSERT_EQ(5, RC.size()); 1290 EXPECT_EQ(&GC, &RC[0]); 1291 EXPECT_EQ(&CC, &RC[1]); 1292 EXPECT_EQ(&BC, &RC[2]); 1293 EXPECT_EQ(&EC, &RC[3]); 1294 EXPECT_EQ(&AC, &RC[4]); 1295 } 1296 1297 } 1298