unittests/Analysis/LazyCallGraphTest.cpp

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