[LCG] Add a unittest for the LazyCallGraph. I had a weak moment and

resisted this for too long. Just with the basic testing here I was able
to exercise the analysis in more detail and sift out both type signature
bugs in the API and a bug in the DFS numbering. All of these are fixed
here as well.

The unittests will be much more important for the mutation support where
it is necessary to craft minimal mutations and then inspect the state of
the graph. There is just no way to do that with a standard FileCheck
test. However, unittesting these kinds of analyses is really quite easy,
especially as they're designed with the new pass manager where there is
essentially no infrastructure required to rig up the core logic and
exercise it at an API level.

As a minor aside about the DFS numbering bug, the DFS numbering used in
LCG is a bit unusual. Rather than numbering from 0, we number from 1,
and use 0 as the sentinel "unvisited" state. Other implementations often
use '-1' for this, but I find it easier to deal with 0 and it shouldn't
make any real difference provided someone doesn't write silly bugs like
forgetting to actually initialize the DFS numbering. Oops. ;]

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206954 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/include/llvm/Analysis/LazyCallGraph.h b/include/llvm/Analysis/LazyCallGraph.h
index 26eac3180d36b4348c1fd32920ba4f08b345d1f8..ecb2f1530e08e2e7531428a2218e1248d8716b16 100644 (file)
--- a/include/llvm/Analysis/LazyCallGraph.h
+++ b/include/llvm/Analysis/LazyCallGraph.h
@@ -134,8 +134,8 @@ public:
         : G(&G), NI(Nodes.end()) {}
 
   public:
-    bool operator==(const iterator &Arg) { return NI == Arg.NI; }
-    bool operator!=(const iterator &Arg) { return !operator==(Arg); }
+    bool operator==(const iterator &Arg) const { return NI == Arg.NI; }
+    bool operator!=(const iterator &Arg) const { return !operator==(Arg); }
 
     reference operator*() const {
       if (NI->is<Node *>())
@@ -260,10 +260,10 @@ public:
         : G(&G), C(nullptr) {}
 
   public:
-    bool operator==(const postorder_scc_iterator &Arg) {
+    bool operator==(const postorder_scc_iterator &Arg) const {
       return G == Arg.G && C == Arg.C;
     }
-    bool operator!=(const postorder_scc_iterator &Arg) {
+    bool operator!=(const postorder_scc_iterator &Arg) const {
       return !operator==(Arg);
     }
 

diff --git a/lib/Analysis/LazyCallGraph.cpp b/lib/Analysis/LazyCallGraph.cpp
index cb5c052c182ed1abdd58c8b3be09bdf6363a5ef6..0a71b9d275860f73780b68cbe1dec4495cdfdae9 100644 (file)
--- a/lib/Analysis/LazyCallGraph.cpp
+++ b/lib/Analysis/LazyCallGraph.cpp
@@ -203,6 +203,8 @@ LazyCallGraph::SCC *LazyCallGraph::getNextSCCInPostOrder() {
     if (SCCEntryNodes.empty())
       return nullptr;
 
+    // Reset the DFS numbering.
+    NextDFSNumber = 1;
     Node *N = get(*SCCEntryNodes.pop_back_val());
     DFSStack.push_back(std::make_pair(N, N->begin()));
   }

diff --git a/unittests/Analysis/CMakeLists.txt b/unittests/Analysis/CMakeLists.txt
index d9f8c0c1ba699a987bdb6193142dfe7be0d03c20..5cca8e8d214db4d5fbde466c38951ebc0d028e69 100644 (file)
--- a/unittests/Analysis/CMakeLists.txt
+++ b/unittests/Analysis/CMakeLists.txt
@@ -7,5 +7,6 @@ set(LLVM_LINK_COMPONENTS
 
 add_llvm_unittest(AnalysisTests
   CFGTest.cpp
+  LazyCallGraphTest.cpp
   ScalarEvolutionTest.cpp
   )

diff --git a/unittests/Analysis/LazyCallGraphTest.cpp b/unittests/Analysis/LazyCallGraphTest.cpp
new file mode 100644 (file)
index 0000000..c224afb
--- /dev/null
+++ b/unittests/Analysis/LazyCallGraphTest.cpp
@@ -0,0 +1,251 @@
+//===- LazyCallGraphTest.cpp - Unit tests for the lazy CG analysis --------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/LazyCallGraph.h"
+#include "llvm/AsmParser/Parser.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/SourceMgr.h"
+#include "gtest/gtest.h"
+#include <memory>
+
+using namespace llvm;
+
+namespace {
+
+std::unique_ptr<Module> parseAssembly(const char *Assembly) {
+  auto M = make_unique<Module>("Module", getGlobalContext());
+
+  SMDiagnostic Error;
+  bool Parsed =
+      ParseAssemblyString(Assembly, M.get(), Error, M->getContext()) == M.get();
+
+  std::string ErrMsg;
+  raw_string_ostream OS(ErrMsg);
+  Error.print("", OS);
+
+  // A failure here means that the test itself is buggy.
+  if (!Parsed)
+    report_fatal_error(OS.str().c_str());
+
+  return M;
+}
+
+// IR forming a call graph with a diamond of triangle-shaped SCCs:
+//
+//         d1
+//        /  \
+//       d3--d2
+//      /     \
+//     b1     c1
+//   /  \    /  \
+//  b3--b2  c3--c2
+//       \  /
+//        a1
+//       /  \
+//      a3--a2
+//
+// All call edges go up between SCCs, and clockwise around the SCC.
+static const char DiamondOfTriangles[] =
+     "define void @a1() {\n"
+     "entry:\n"
+     "  call void @a2()\n"
+     "  call void @b2()\n"
+     "  call void @c3()\n"
+     "  ret void\n"
+     "}\n"
+     "define void @a2() {\n"
+     "entry:\n"
+     "  call void @a3()\n"
+     "  ret void\n"
+     "}\n"
+     "define void @a3() {\n"
+     "entry:\n"
+     "  call void @a1()\n"
+     "  ret void\n"
+     "}\n"
+     "define void @b1() {\n"
+     "entry:\n"
+     "  call void @b2()\n"
+     "  call void @d3()\n"
+     "  ret void\n"
+     "}\n"
+     "define void @b2() {\n"
+     "entry:\n"
+     "  call void @b3()\n"
+     "  ret void\n"
+     "}\n"
+     "define void @b3() {\n"
+     "entry:\n"
+     "  call void @b1()\n"
+     "  ret void\n"
+     "}\n"
+     "define void @c1() {\n"
+     "entry:\n"
+     "  call void @c2()\n"
+     "  call void @d2()\n"
+     "  ret void\n"
+     "}\n"
+     "define void @c2() {\n"
+     "entry:\n"
+     "  call void @c3()\n"
+     "  ret void\n"
+     "}\n"
+     "define void @c3() {\n"
+     "entry:\n"
+     "  call void @c1()\n"
+     "  ret void\n"
+     "}\n"
+     "define void @d1() {\n"
+     "entry:\n"
+     "  call void @d2()\n"
+     "  ret void\n"
+     "}\n"
+     "define void @d2() {\n"
+     "entry:\n"
+     "  call void @d3()\n"
+     "  ret void\n"
+     "}\n"
+     "define void @d3() {\n"
+     "entry:\n"
+     "  call void @d1()\n"
+     "  ret void\n"
+     "}\n";
+
+TEST(LazyCallGraphTest, BasicGraphFormation) {
+  std::unique_ptr<Module> M = parseAssembly(DiamondOfTriangles);
+  LazyCallGraph CG(*M);
+
+  // The order of the entry nodes should be stable w.r.t. the source order of
+  // the IR, and everything in our module is an entry node, so just directly
+  // build variables for each node.
+  auto I = CG.begin();
+  LazyCallGraph::Node *A1 = *I++;
+  EXPECT_EQ("a1", A1->getFunction().getName());
+  LazyCallGraph::Node *A2 = *I++;
+  EXPECT_EQ("a2", A2->getFunction().getName());
+  LazyCallGraph::Node *A3 = *I++;
+  EXPECT_EQ("a3", A3->getFunction().getName());
+  LazyCallGraph::Node *B1 = *I++;
+  EXPECT_EQ("b1", B1->getFunction().getName());
+  LazyCallGraph::Node *B2 = *I++;
+  EXPECT_EQ("b2", B2->getFunction().getName());
+  LazyCallGraph::Node *B3 = *I++;
+  EXPECT_EQ("b3", B3->getFunction().getName());
+  LazyCallGraph::Node *C1 = *I++;
+  EXPECT_EQ("c1", C1->getFunction().getName());
+  LazyCallGraph::Node *C2 = *I++;
+  EXPECT_EQ("c2", C2->getFunction().getName());
+  LazyCallGraph::Node *C3 = *I++;
+  EXPECT_EQ("c3", C3->getFunction().getName());
+  LazyCallGraph::Node *D1 = *I++;
+  EXPECT_EQ("d1", D1->getFunction().getName());
+  LazyCallGraph::Node *D2 = *I++;
+  EXPECT_EQ("d2", D2->getFunction().getName());
+  LazyCallGraph::Node *D3 = *I++;
+  EXPECT_EQ("d3", D3->getFunction().getName());
+  EXPECT_EQ(CG.end(), I);
+
+  // Build vectors and sort them for the rest of the assertions to make them
+  // independent of order.
+  std::vector<std::string> Nodes;
+
+  for (LazyCallGraph::Node *N : *A1)
+    Nodes.push_back(N->getFunction().getName());
+  std::sort(Nodes.begin(), Nodes.end());
+  EXPECT_EQ("a2", Nodes[0]);
+  EXPECT_EQ("b2", Nodes[1]);
+  EXPECT_EQ("c3", Nodes[2]);
+  Nodes.clear();
+
+  EXPECT_EQ(A2->end(), std::next(A2->begin()));
+  EXPECT_EQ("a3", A2->begin()->getFunction().getName());
+  EXPECT_EQ(A3->end(), std::next(A3->begin()));
+  EXPECT_EQ("a1", A3->begin()->getFunction().getName());
+
+  for (LazyCallGraph::Node *N : *B1)
+    Nodes.push_back(N->getFunction().getName());
+  std::sort(Nodes.begin(), Nodes.end());
+  EXPECT_EQ("b2", Nodes[0]);
+  EXPECT_EQ("d3", Nodes[1]);
+  Nodes.clear();
+
+  EXPECT_EQ(B2->end(), std::next(B2->begin()));
+  EXPECT_EQ("b3", B2->begin()->getFunction().getName());
+  EXPECT_EQ(B3->end(), std::next(B3->begin()));
+  EXPECT_EQ("b1", B3->begin()->getFunction().getName());
+
+  for (LazyCallGraph::Node *N : *C1)
+    Nodes.push_back(N->getFunction().getName());
+  std::sort(Nodes.begin(), Nodes.end());
+  EXPECT_EQ("c2", Nodes[0]);
+  EXPECT_EQ("d2", Nodes[1]);
+  Nodes.clear();
+
+  EXPECT_EQ(C2->end(), std::next(C2->begin()));
+  EXPECT_EQ("c3", C2->begin()->getFunction().getName());
+  EXPECT_EQ(C3->end(), std::next(C3->begin()));
+  EXPECT_EQ("c1", C3->begin()->getFunction().getName());
+
+  EXPECT_EQ(D1->end(), std::next(D1->begin()));
+  EXPECT_EQ("d2", D1->begin()->getFunction().getName());
+  EXPECT_EQ(D2->end(), std::next(D2->begin()));
+  EXPECT_EQ("d3", D2->begin()->getFunction().getName());
+  EXPECT_EQ(D3->end(), std::next(D3->begin()));
+  EXPECT_EQ("d1", D3->begin()->getFunction().getName());
+
+  // Now lets look at the SCCs.
+  auto SCCI = CG.postorder_scc_begin();
+
+  LazyCallGraph::SCC *D = *SCCI++;
+  for (LazyCallGraph::Node *N : *D)
+    Nodes.push_back(N->getFunction().getName());
+  std::sort(Nodes.begin(), Nodes.end());
+  EXPECT_EQ("d1", Nodes[0]);
+  EXPECT_EQ("d2", Nodes[1]);
+  EXPECT_EQ("d3", Nodes[2]);
+  EXPECT_EQ(3u, Nodes.size());
+  Nodes.clear();
+
+  LazyCallGraph::SCC *C = *SCCI++;
+  for (LazyCallGraph::Node *N : *C)
+    Nodes.push_back(N->getFunction().getName());
+  std::sort(Nodes.begin(), Nodes.end());
+  EXPECT_EQ("c1", Nodes[0]);
+  EXPECT_EQ("c2", Nodes[1]);
+  EXPECT_EQ("c3", Nodes[2]);
+  EXPECT_EQ(3u, Nodes.size());
+  Nodes.clear();
+
+  LazyCallGraph::SCC *B = *SCCI++;
+  for (LazyCallGraph::Node *N : *B)
+    Nodes.push_back(N->getFunction().getName());
+  std::sort(Nodes.begin(), Nodes.end());
+  EXPECT_EQ("b1", Nodes[0]);
+  EXPECT_EQ("b2", Nodes[1]);
+  EXPECT_EQ("b3", Nodes[2]);
+  EXPECT_EQ(3u, Nodes.size());
+  Nodes.clear();
+
+  LazyCallGraph::SCC *A = *SCCI++;
+  for (LazyCallGraph::Node *N : *A)
+    Nodes.push_back(N->getFunction().getName());
+  std::sort(Nodes.begin(), Nodes.end());
+  EXPECT_EQ("a1", Nodes[0]);
+  EXPECT_EQ("a2", Nodes[1]);
+  EXPECT_EQ("a3", Nodes[2]);
+  EXPECT_EQ(3u, Nodes.size());
+  Nodes.clear();
+
+  EXPECT_EQ(CG.postorder_scc_end(), SCCI);
+}
+
+}