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   auto M = make_unique<Module>("Module", getGlobalContext());
  26
  27   SMDiagnostic Error;
  28   bool Parsed =
  29       ParseAssemblyString(Assembly, M.get(), Error, M->getContext()) == M.get();
  30
  31   std::string ErrMsg;
  32   raw_string_ostream OS(ErrMsg);
  33   Error.print("", OS);
  34
  35   // A failure here means that the test itself is buggy.
  36   if (!Parsed)
  37     report_fatal_error(OS.str().c_str());
  38
  39   return M;
  40 }
  41
  42 // IR forming a call graph with a diamond of triangle-shaped SCCs:
  43 //
  44 //         d1       |
  45 //        /  \      |
  46 //       d3--d2     |
  47 //      /     \     |
  48 //     b1     c1    |
  49 //   /  \    /  \   |
  50 //  b3--b2  c3--c2  |
  51 //       \  /       |
  52 //        a1        |
  53 //       /  \       |
  54 //      a3--a2      |
  55 //
  56 // All call edges go up between SCCs, and clockwise around the SCC.
  57 static const char DiamondOfTriangles[] =
  58      "define void @a1() {\n"
  59      "entry:\n"
  60      "  call void @a2()\n"
  61      "  call void @b2()\n"
  62      "  call void @c3()\n"
  63      "  ret void\n"
  64      "}\n"
  65      "define void @a2() {\n"
  66      "entry:\n"
  67      "  call void @a3()\n"
  68      "  ret void\n"
  69      "}\n"
  70      "define void @a3() {\n"
  71      "entry:\n"
  72      "  call void @a1()\n"
  73      "  ret void\n"
  74      "}\n"
  75      "define void @b1() {\n"
  76      "entry:\n"
  77      "  call void @b2()\n"
  78      "  call void @d3()\n"
  79      "  ret void\n"
  80      "}\n"
  81      "define void @b2() {\n"
  82      "entry:\n"
  83      "  call void @b3()\n"
  84      "  ret void\n"
  85      "}\n"
  86      "define void @b3() {\n"
  87      "entry:\n"
  88      "  call void @b1()\n"
  89      "  ret void\n"
  90      "}\n"
  91      "define void @c1() {\n"
  92      "entry:\n"
  93      "  call void @c2()\n"
  94      "  call void @d2()\n"
  95      "  ret void\n"
  96      "}\n"
  97      "define void @c2() {\n"
  98      "entry:\n"
  99      "  call void @c3()\n"
 100      "  ret void\n"
 101      "}\n"
 102      "define void @c3() {\n"
 103      "entry:\n"
 104      "  call void @c1()\n"
 105      "  ret void\n"
 106      "}\n"
 107      "define void @d1() {\n"
 108      "entry:\n"
 109      "  call void @d2()\n"
 110      "  ret void\n"
 111      "}\n"
 112      "define void @d2() {\n"
 113      "entry:\n"
 114      "  call void @d3()\n"
 115      "  ret void\n"
 116      "}\n"
 117      "define void @d3() {\n"
 118      "entry:\n"
 119      "  call void @d1()\n"
 120      "  ret void\n"
 121      "}\n";
 122
 123 TEST(LazyCallGraphTest, BasicGraphFormation) {
 124   std::unique_ptr<Module> M = parseAssembly(DiamondOfTriangles);
 125   LazyCallGraph CG(*M);
 126
 127   // The order of the entry nodes should be stable w.r.t. the source order of
 128   // the IR, and everything in our module is an entry node, so just directly
 129   // build variables for each node.
 130   auto I = CG.begin();
 131   LazyCallGraph::Node &A1 = *I++;
 132   EXPECT_EQ("a1", A1.getFunction().getName());
 133   LazyCallGraph::Node &A2 = *I++;
 134   EXPECT_EQ("a2", A2.getFunction().getName());
 135   LazyCallGraph::Node &A3 = *I++;
 136   EXPECT_EQ("a3", A3.getFunction().getName());
 137   LazyCallGraph::Node &B1 = *I++;
 138   EXPECT_EQ("b1", B1.getFunction().getName());
 139   LazyCallGraph::Node &B2 = *I++;
 140   EXPECT_EQ("b2", B2.getFunction().getName());
 141   LazyCallGraph::Node &B3 = *I++;
 142   EXPECT_EQ("b3", B3.getFunction().getName());
 143   LazyCallGraph::Node &C1 = *I++;
 144   EXPECT_EQ("c1", C1.getFunction().getName());
 145   LazyCallGraph::Node &C2 = *I++;
 146   EXPECT_EQ("c2", C2.getFunction().getName());
 147   LazyCallGraph::Node &C3 = *I++;
 148   EXPECT_EQ("c3", C3.getFunction().getName());
 149   LazyCallGraph::Node &D1 = *I++;
 150   EXPECT_EQ("d1", D1.getFunction().getName());
 151   LazyCallGraph::Node &D2 = *I++;
 152   EXPECT_EQ("d2", D2.getFunction().getName());
 153   LazyCallGraph::Node &D3 = *I++;
 154   EXPECT_EQ("d3", D3.getFunction().getName());
 155   EXPECT_EQ(CG.end(), I);
 156
 157   // Build vectors and sort them for the rest of the assertions to make them
 158   // independent of order.
 159   std::vector<std::string> Nodes;
 160
 161   for (LazyCallGraph::Node &N : A1)
 162     Nodes.push_back(N.getFunction().getName());
 163   std::sort(Nodes.begin(), Nodes.end());
 164   EXPECT_EQ("a2", Nodes[0]);
 165   EXPECT_EQ("b2", Nodes[1]);
 166   EXPECT_EQ("c3", Nodes[2]);
 167   Nodes.clear();
 168
 169   EXPECT_EQ(A2.end(), std::next(A2.begin()));
 170   EXPECT_EQ("a3", A2.begin()->getFunction().getName());
 171   EXPECT_EQ(A3.end(), std::next(A3.begin()));
 172   EXPECT_EQ("a1", A3.begin()->getFunction().getName());
 173
 174   for (LazyCallGraph::Node &N : B1)
 175     Nodes.push_back(N.getFunction().getName());
 176   std::sort(Nodes.begin(), Nodes.end());
 177   EXPECT_EQ("b2", Nodes[0]);
 178   EXPECT_EQ("d3", Nodes[1]);
 179   Nodes.clear();
 180
 181   EXPECT_EQ(B2.end(), std::next(B2.begin()));
 182   EXPECT_EQ("b3", B2.begin()->getFunction().getName());
 183   EXPECT_EQ(B3.end(), std::next(B3.begin()));
 184   EXPECT_EQ("b1", B3.begin()->getFunction().getName());
 185
 186   for (LazyCallGraph::Node &N : C1)
 187     Nodes.push_back(N.getFunction().getName());
 188   std::sort(Nodes.begin(), Nodes.end());
 189   EXPECT_EQ("c2", Nodes[0]);
 190   EXPECT_EQ("d2", Nodes[1]);
 191   Nodes.clear();
 192
 193   EXPECT_EQ(C2.end(), std::next(C2.begin()));
 194   EXPECT_EQ("c3", C2.begin()->getFunction().getName());
 195   EXPECT_EQ(C3.end(), std::next(C3.begin()));
 196   EXPECT_EQ("c1", C3.begin()->getFunction().getName());
 197
 198   EXPECT_EQ(D1.end(), std::next(D1.begin()));
 199   EXPECT_EQ("d2", D1.begin()->getFunction().getName());
 200   EXPECT_EQ(D2.end(), std::next(D2.begin()));
 201   EXPECT_EQ("d3", D2.begin()->getFunction().getName());
 202   EXPECT_EQ(D3.end(), std::next(D3.begin()));
 203   EXPECT_EQ("d1", D3.begin()->getFunction().getName());
 204
 205   // Now lets look at the SCCs.
 206   auto SCCI = CG.postorder_scc_begin();
 207
 208   LazyCallGraph::SCC &D = *SCCI++;
 209   for (LazyCallGraph::Node *N : D)
 210     Nodes.push_back(N->getFunction().getName());
 211   std::sort(Nodes.begin(), Nodes.end());
 212   EXPECT_EQ(3u, Nodes.size());
 213   EXPECT_EQ("d1", Nodes[0]);
 214   EXPECT_EQ("d2", Nodes[1]);
 215   EXPECT_EQ("d3", Nodes[2]);
 216   Nodes.clear();
 217
 218   LazyCallGraph::SCC &C = *SCCI++;
 219   for (LazyCallGraph::Node *N : C)
 220     Nodes.push_back(N->getFunction().getName());
 221   std::sort(Nodes.begin(), Nodes.end());
 222   EXPECT_EQ(3u, Nodes.size());
 223   EXPECT_EQ("c1", Nodes[0]);
 224   EXPECT_EQ("c2", Nodes[1]);
 225   EXPECT_EQ("c3", Nodes[2]);
 226   Nodes.clear();
 227
 228   LazyCallGraph::SCC &B = *SCCI++;
 229   for (LazyCallGraph::Node *N : B)
 230     Nodes.push_back(N->getFunction().getName());
 231   std::sort(Nodes.begin(), Nodes.end());
 232   EXPECT_EQ(3u, Nodes.size());
 233   EXPECT_EQ("b1", Nodes[0]);
 234   EXPECT_EQ("b2", Nodes[1]);
 235   EXPECT_EQ("b3", Nodes[2]);
 236   Nodes.clear();
 237
 238   LazyCallGraph::SCC &A = *SCCI++;
 239   for (LazyCallGraph::Node *N : A)
 240     Nodes.push_back(N->getFunction().getName());
 241   std::sort(Nodes.begin(), Nodes.end());
 242   EXPECT_EQ(3u, Nodes.size());
 243   EXPECT_EQ("a1", Nodes[0]);
 244   EXPECT_EQ("a2", Nodes[1]);
 245   EXPECT_EQ("a3", Nodes[2]);
 246   Nodes.clear();
 247
 248   EXPECT_EQ(CG.postorder_scc_end(), SCCI);
 249 }
 250
 251 static Function &lookupFunction(Module &M, StringRef Name) {
 252   for (Function &F : M)
 253     if (F.getName() == Name)
 254       return F;
 255   report_fatal_error("Couldn't find function!");
 256 }
 257
 258 TEST(LazyCallGraphTest, BasicGraphMutation) {
 259   std::unique_ptr<Module> M = parseAssembly(
 260       "define void @a() {\n"
 261       "entry:\n"
 262       "  call void @b()\n"
 263       "  call void @c()\n"
 264       "  ret void\n"
 265       "}\n"
 266       "define void @b() {\n"
 267       "entry:\n"
 268       "  ret void\n"
 269       "}\n"
 270       "define void @c() {\n"
 271       "entry:\n"
 272       "  ret void\n"
 273       "}\n");
 274   LazyCallGraph CG(*M);
 275
 276   LazyCallGraph::Node &A = CG.get(lookupFunction(*M, "a"));
 277   LazyCallGraph::Node &B = CG.get(lookupFunction(*M, "b"));
 278   EXPECT_EQ(2, std::distance(A.begin(), A.end()));
 279   EXPECT_EQ(0, std::distance(B.begin(), B.end()));
 280
 281   CG.insertEdge(B, lookupFunction(*M, "c"));
 282   EXPECT_EQ(1, std::distance(B.begin(), B.end()));
 283   LazyCallGraph::Node &C = *B.begin();
 284   EXPECT_EQ(0, std::distance(C.begin(), C.end()));
 285
 286   CG.insertEdge(C, B.getFunction());
 287   EXPECT_EQ(1, std::distance(C.begin(), C.end()));
 288   EXPECT_EQ(&B, &*C.begin());
 289
 290   CG.insertEdge(C, C.getFunction());
 291   EXPECT_EQ(2, std::distance(C.begin(), C.end()));
 292   EXPECT_EQ(&B, &*C.begin());
 293   EXPECT_EQ(&C, &*std::next(C.begin()));
 294
 295   CG.removeEdge(C, B.getFunction());
 296   EXPECT_EQ(1, std::distance(C.begin(), C.end()));
 297   EXPECT_EQ(&C, &*C.begin());
 298
 299   CG.removeEdge(C, C.getFunction());
 300   EXPECT_EQ(0, std::distance(C.begin(), C.end()));
 301
 302   CG.removeEdge(B, C.getFunction());
 303   EXPECT_EQ(0, std::distance(B.begin(), B.end()));
 304 }
 305
 306 TEST(LazyCallGraphTest, MultiArmSCC) {
 307   // Two interlocking cycles. The really useful thing about this SCC is that it
 308   // will require Tarjan's DFS to backtrack and finish processing all of the
 309   // children of each node in the SCC.
 310   std::unique_ptr<Module> M = parseAssembly(
 311       "define void @a() {\n"
 312       "entry:\n"
 313       "  call void @b()\n"
 314       "  call void @d()\n"
 315       "  ret void\n"
 316       "}\n"
 317       "define void @b() {\n"
 318       "entry:\n"
 319       "  call void @c()\n"
 320       "  ret void\n"
 321       "}\n"
 322       "define void @c() {\n"
 323       "entry:\n"
 324       "  call void @a()\n"
 325       "  ret void\n"
 326       "}\n"
 327       "define void @d() {\n"
 328       "entry:\n"
 329       "  call void @e()\n"
 330       "  ret void\n"
 331       "}\n"
 332       "define void @e() {\n"
 333       "entry:\n"
 334       "  call void @a()\n"
 335       "  ret void\n"
 336       "}\n");
 337   LazyCallGraph CG(*M);
 338
 339   // Force the graph to be fully expanded.
 340   auto SCCI = CG.postorder_scc_begin();
 341   LazyCallGraph::SCC &SCC = *SCCI++;
 342   EXPECT_EQ(CG.postorder_scc_end(), SCCI);
 343
 344   LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
 345   LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
 346   LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
 347   LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
 348   LazyCallGraph::Node &E = *CG.lookup(lookupFunction(*M, "e"));
 349   EXPECT_EQ(&SCC, CG.lookupSCC(A));
 350   EXPECT_EQ(&SCC, CG.lookupSCC(B));
 351   EXPECT_EQ(&SCC, CG.lookupSCC(C));
 352   EXPECT_EQ(&SCC, CG.lookupSCC(D));
 353   EXPECT_EQ(&SCC, CG.lookupSCC(E));
 354 }
 355
 356 TEST(LazyCallGraphTest, InterSCCEdgeRemoval) {
 357   std::unique_ptr<Module> M = parseAssembly(
 358       "define void @a() {\n"
 359       "entry:\n"
 360       "  call void @b()\n"
 361       "  ret void\n"
 362       "}\n"
 363       "define void @b() {\n"
 364       "entry:\n"
 365       "  ret void\n"
 366       "}\n");
 367   LazyCallGraph CG(*M);
 368
 369   // Force the graph to be fully expanded.
 370   for (LazyCallGraph::SCC &C : CG.postorder_sccs())
 371     (void)C;
 372
 373   LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
 374   LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
 375   LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
 376   LazyCallGraph::SCC &BC = *CG.lookupSCC(B);
 377
 378   EXPECT_EQ("b", A.begin()->getFunction().getName());
 379   EXPECT_EQ(B.end(), B.begin());
 380   EXPECT_EQ(&AC, &*BC.parent_begin());
 381
 382   AC.removeInterSCCEdge(A, B);
 383
 384   EXPECT_EQ(A.end(), A.begin());
 385   EXPECT_EQ(B.end(), B.begin());
 386   EXPECT_EQ(BC.parent_end(), BC.parent_begin());
 387 }
 388
 389 TEST(LazyCallGraphTest, IntraSCCEdgeRemoval) {
 390   // A nice fully connected (including self-edges) SCC.
 391   std::unique_ptr<Module> M1 = parseAssembly(
 392       "define void @a() {\n"
 393       "entry:\n"
 394       "  call void @a()\n"
 395       "  call void @b()\n"
 396       "  call void @c()\n"
 397       "  ret void\n"
 398       "}\n"
 399       "define void @b() {\n"
 400       "entry:\n"
 401       "  call void @a()\n"
 402       "  call void @b()\n"
 403       "  call void @c()\n"
 404       "  ret void\n"
 405       "}\n"
 406       "define void @c() {\n"
 407       "entry:\n"
 408       "  call void @a()\n"
 409       "  call void @b()\n"
 410       "  call void @c()\n"
 411       "  ret void\n"
 412       "}\n");
 413   LazyCallGraph CG1(*M1);
 414
 415   // Force the graph to be fully expanded.
 416   auto SCCI = CG1.postorder_scc_begin();
 417   LazyCallGraph::SCC &SCC = *SCCI++;
 418   EXPECT_EQ(CG1.postorder_scc_end(), SCCI);
 419
 420   LazyCallGraph::Node &A = *CG1.lookup(lookupFunction(*M1, "a"));
 421   LazyCallGraph::Node &B = *CG1.lookup(lookupFunction(*M1, "b"));
 422   LazyCallGraph::Node &C = *CG1.lookup(lookupFunction(*M1, "c"));
 423   EXPECT_EQ(&SCC, CG1.lookupSCC(A));
 424   EXPECT_EQ(&SCC, CG1.lookupSCC(B));
 425   EXPECT_EQ(&SCC, CG1.lookupSCC(C));
 426
 427   // Remove the edge from b -> a, which should leave the 3 functions still in
 428   // a single connected component because of a -> b -> c -> a.
 429   SmallVector<LazyCallGraph::SCC *, 1> NewSCCs = SCC.removeIntraSCCEdge(B, A);
 430   EXPECT_EQ(0u, NewSCCs.size());
 431   EXPECT_EQ(&SCC, CG1.lookupSCC(A));
 432   EXPECT_EQ(&SCC, CG1.lookupSCC(B));
 433   EXPECT_EQ(&SCC, CG1.lookupSCC(C));
 434
 435   // Remove the edge from c -> a, which should leave 'a' in the original SCC
 436   // and form a new SCC for 'b' and 'c'.
 437   NewSCCs = SCC.removeIntraSCCEdge(C, A);
 438   EXPECT_EQ(1u, NewSCCs.size());
 439   EXPECT_EQ(&SCC, CG1.lookupSCC(A));
 440   EXPECT_EQ(1, std::distance(SCC.begin(), SCC.end()));
 441   LazyCallGraph::SCC *SCC2 = CG1.lookupSCC(B);
 442   EXPECT_EQ(SCC2, CG1.lookupSCC(C));
 443   EXPECT_EQ(SCC2, NewSCCs[0]);
 444 }
 445
 446 }