[analyzer][Dominators][NFC] Add unit tests

Differential Revision: https://reviews.llvm.org/D62611

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

4 files changed, 174 insertions, 51 deletions

diff --git a/unittests/Analysis/CFGBuildResult.h b/unittests/Analysis/CFGBuildResult.h
new file mode 100644
index 0000000000..17511dcd46
--- /dev/null
+++ b/unittests/Analysis/CFGBuildResult.h
@@ -0,0 +1,69 @@
+//===- unittests/Analysis/CFGBuildResult.h - CFG tests --------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/CFG.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/Tooling/Tooling.h"
+
+namespace clang {
+namespace analysis {
+
+class BuildResult {
+public:
+  enum Status {
+    ToolFailed,
+    ToolRan,
+    SawFunctionBody,
+    BuiltCFG,
+  };
+
+  BuildResult(Status S, std::unique_ptr<CFG> Cfg = nullptr)
+      : S(S), Cfg(std::move(Cfg)) {}
+
+  Status getStatus() const { return S; }
+  CFG *getCFG() const { return Cfg.get(); }
+
+private:
+  Status S;
+  std::unique_ptr<CFG> Cfg;
+};
+
+class CFGCallback : public ast_matchers::MatchFinder::MatchCallback {
+public:
+  BuildResult TheBuildResult = BuildResult::ToolRan;
+
+  void run(const ast_matchers::MatchFinder::MatchResult &Result) override {
+    const auto *Func = Result.Nodes.getNodeAs<FunctionDecl>("func");
+    Stmt *Body = Func->getBody();
+    if (!Body)
+      return;
+    TheBuildResult = BuildResult::SawFunctionBody;
+    CFG::BuildOptions Options;
+    Options.AddImplicitDtors = true;
+    if (std::unique_ptr<CFG> Cfg =
+            CFG::buildCFG(nullptr, Body, Result.Context, Options))
+      TheBuildResult = {BuildResult::BuiltCFG, std::move(Cfg)};
+  }
+};
+
+inline BuildResult BuildCFG(const char *Code) {
+  CFGCallback Callback;
+
+  ast_matchers::MatchFinder Finder;
+  Finder.addMatcher(ast_matchers::functionDecl().bind("func"), &Callback);
+  std::unique_ptr<tooling::FrontendActionFactory> Factory(
+      tooling::newFrontendActionFactory(&Finder));
+  std::vector<std::string> Args = {"-std=c++11",
+                                   "-fno-delayed-template-parsing"};
+  if (!tooling::runToolOnCodeWithArgs(Factory->create(), Code, Args))
+    return BuildResult::ToolFailed;
+  return std::move(Callback.TheBuildResult);
+}
+
+} // namespace analysis
+} // namespace clang
diff --git a/unittests/Analysis/CFGDominatorTree.cpp b/unittests/Analysis/CFGDominatorTree.cpp
new file mode 100644
index 0000000000..1df8c2f7d0
--- /dev/null
+++ b/unittests/Analysis/CFGDominatorTree.cpp
@@ -0,0 +1,103 @@
+//===- unittests/Analysis/CFGDominatorTree.cpp - CFG tests ----------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "CFGBuildResult.h"
+#include "clang/Analysis/Analyses/Dominators.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace analysis {
+namespace {
+
+TEST(CFGDominatorTree, DomTree) {
+  const char *Code = R"(enum Kind {
+                          A
+                        };
+
+                        void f() {
+                          switch(Kind{}) {
+                          case A:
+                            break;
+                          }
+                        })";
+  BuildResult Result = BuildCFG(Code);
+  EXPECT_EQ(BuildResult::BuiltCFG, Result.getStatus());
+
+  //  [B3 (ENTRY)]  -> [B1] -> [B2] -> [B0 (EXIT)]
+  //                  switch  case A
+
+  CFG *cfg = Result.getCFG();
+
+  // Sanity checks.
+  EXPECT_EQ(cfg->size(), 4u);
+
+  CFGBlock *ExitBlock = *cfg->begin();
+  EXPECT_EQ(ExitBlock, &cfg->getExit());
+
+  CFGBlock *SwitchBlock = *(cfg->begin() + 1);
+
+  CFGBlock *CaseABlock = *(cfg->begin() + 2);
+
+  CFGBlock *EntryBlock = *(cfg->begin() + 3);
+  EXPECT_EQ(EntryBlock, &cfg->getEntry());
+
+  // Test the dominator tree.
+  CFGDomTree Dom;
+  Dom.buildDominatorTree(cfg);
+
+  EXPECT_TRUE(Dom.dominates(ExitBlock, ExitBlock));
+  EXPECT_FALSE(Dom.properlyDominates(ExitBlock, ExitBlock));
+  EXPECT_TRUE(Dom.dominates(CaseABlock, ExitBlock));
+  EXPECT_TRUE(Dom.dominates(SwitchBlock, ExitBlock));
+  EXPECT_TRUE(Dom.dominates(EntryBlock, ExitBlock));
+
+  EXPECT_TRUE(Dom.dominates(CaseABlock, CaseABlock));
+  EXPECT_FALSE(Dom.properlyDominates(CaseABlock, CaseABlock));
+  EXPECT_TRUE(Dom.dominates(SwitchBlock, CaseABlock));
+  EXPECT_TRUE(Dom.dominates(EntryBlock, CaseABlock));
+
+  EXPECT_TRUE(Dom.dominates(SwitchBlock, SwitchBlock));
+  EXPECT_FALSE(Dom.properlyDominates(SwitchBlock, SwitchBlock));
+  EXPECT_TRUE(Dom.dominates(EntryBlock, SwitchBlock));
+
+  EXPECT_TRUE(Dom.dominates(EntryBlock, EntryBlock));
+  EXPECT_FALSE(Dom.properlyDominates(EntryBlock, EntryBlock));
+
+  // Test the post dominator tree.
+
+  CFGPostDomTree PostDom;
+  PostDom.buildDominatorTree(cfg);
+
+  EXPECT_TRUE(PostDom.dominates(ExitBlock, EntryBlock));
+  EXPECT_TRUE(PostDom.dominates(CaseABlock, EntryBlock));
+  EXPECT_TRUE(PostDom.dominates(SwitchBlock, EntryBlock));
+  EXPECT_TRUE(PostDom.dominates(EntryBlock, EntryBlock));
+  EXPECT_FALSE(Dom.properlyDominates(EntryBlock, EntryBlock));
+
+  EXPECT_TRUE(PostDom.dominates(ExitBlock, SwitchBlock));
+  EXPECT_TRUE(PostDom.dominates(CaseABlock, SwitchBlock));
+  EXPECT_TRUE(PostDom.dominates(SwitchBlock, SwitchBlock));
+  EXPECT_FALSE(Dom.properlyDominates(SwitchBlock, SwitchBlock));
+
+  EXPECT_TRUE(PostDom.dominates(ExitBlock, CaseABlock));
+  EXPECT_TRUE(PostDom.dominates(CaseABlock, CaseABlock));
+  EXPECT_FALSE(Dom.properlyDominates(CaseABlock, CaseABlock));
+
+  EXPECT_TRUE(PostDom.dominates(ExitBlock, ExitBlock));
+  EXPECT_FALSE(Dom.properlyDominates(ExitBlock, ExitBlock));
+
+  // Tests for the post dominator tree's virtual root.
+  EXPECT_TRUE(PostDom.dominates(nullptr, EntryBlock));
+  EXPECT_TRUE(PostDom.dominates(nullptr, SwitchBlock));
+  EXPECT_TRUE(PostDom.dominates(nullptr, CaseABlock));
+  EXPECT_TRUE(PostDom.dominates(nullptr, ExitBlock));
+}
+
+} // namespace
+} // namespace analysis
+} // namespace clang
diff --git a/unittests/Analysis/CFGTest.cpp b/unittests/Analysis/CFGTest.cpp
index 69cf78b973..bf0116050a 100644
--- a/unittests/Analysis/CFGTest.cpp
+++ b/unittests/Analysis/CFGTest.cpp
@@ -6,6 +6,7 @@
 //
 //===----------------------------------------------------------------------===//
 
+#include "CFGBuildResult.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
 #include "clang/Analysis/CFG.h"
 #include "clang/Tooling/Tooling.h"
@@ -17,57 +18,6 @@ namespace clang {
 namespace analysis {
 namespace {
 
-class BuildResult {
-public:
-  enum Status {
-    ToolFailed,
-    ToolRan,
-    SawFunctionBody,
-    BuiltCFG,
-  };
-
-  BuildResult(Status S, std::unique_ptr<CFG> Cfg = nullptr)
-      : S(S), Cfg(std::move(Cfg)) {}
-
-  Status getStatus() const { return S; }
-  CFG *getCFG() const { return Cfg.get(); }
-
-private:
-  Status S;
-  std::unique_ptr<CFG> Cfg;
-};
-
-class CFGCallback : public ast_matchers::MatchFinder::MatchCallback {
-public:
-  BuildResult TheBuildResult = BuildResult::ToolRan;
-
-  void run(const ast_matchers::MatchFinder::MatchResult &Result) override {
-    const auto *Func = Result.Nodes.getNodeAs<FunctionDecl>("func");
-    Stmt *Body = Func->getBody();
-    if (!Body)
-      return;
-    TheBuildResult = BuildResult::SawFunctionBody;
-    CFG::BuildOptions Options;
-    Options.AddImplicitDtors = true;
-    if (std::unique_ptr<CFG> Cfg =
-            CFG::buildCFG(nullptr, Body, Result.Context, Options))
-      TheBuildResult = {BuildResult::BuiltCFG, std::move(Cfg)};
-  }
-};
-
-BuildResult BuildCFG(const char *Code) {
-  CFGCallback Callback;
-
-  ast_matchers::MatchFinder Finder;
-  Finder.addMatcher(ast_matchers::functionDecl().bind("func"), &Callback);
-  std::unique_ptr<tooling::FrontendActionFactory> Factory(
-      tooling::newFrontendActionFactory(&Finder));
-  std::vector<std::string> Args = {"-std=c++11", "-fno-delayed-template-parsing"};
-  if (!tooling::runToolOnCodeWithArgs(Factory->create(), Code, Args))
-    return BuildResult::ToolFailed;
-  return std::move(Callback.TheBuildResult);
-}
-
 // Constructing a CFG for a range-based for over a dependent type fails (but
 // should not crash).
 TEST(CFG, RangeBasedForOverDependentType) {
diff --git a/unittests/Analysis/CMakeLists.txt b/unittests/Analysis/CMakeLists.txt
index 5575c910da..03716e2e5e 100644
--- a/unittests/Analysis/CMakeLists.txt
+++ b/unittests/Analysis/CMakeLists.txt
@@ -3,6 +3,7 @@ set(LLVM_LINK_COMPONENTS
   )
 
 add_clang_unittest(ClangAnalysisTests
+  CFGDominatorTree.cpp
   CFGTest.cpp
   CloneDetectionTest.cpp
   ExprMutationAnalyzerTest.cpp