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