[analyzer] Expose exploration strategy through analyzer options.

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

llvm-svn: 324049

8 files changed, 74 insertions, 13 deletions

diff --git a/clang/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h b/clang/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h
index 2f28addb96e..5ddf7d79c8d 100644
--- a/clang/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h
+++ b/clang/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h
@@ -188,7 +188,17 @@ public:
   /// \brief The mode of function selection used during inlining.
   AnalysisInliningMode InliningMode;
 
+  enum class ExplorationStrategyKind {
+    DFS,
+    BFS,
+    BFSBlockDFSContents,
+    NotSet
+  };
+
 private:
+
+  ExplorationStrategyKind ExplorationStrategy;
+
   /// \brief Describes the kinds for high-level analyzer mode.
   enum UserModeKind {
     UMK_NotSet = 0,
@@ -390,6 +400,8 @@ public:
   /// outside of AnalyzerOptions.
   UserModeKind getUserMode();
 
+  ExplorationStrategyKind getExplorationStrategy();
+
   /// \brief Returns the inter-procedural analysis mode.
   IPAKind getIPAMode();
 
@@ -611,6 +623,7 @@ public:
     // Cap the stack depth at 4 calls (5 stack frames, base + 4 calls).
     InlineMaxStackDepth(5),
     InliningMode(NoRedundancy),
+    ExplorationStrategy(ExplorationStrategyKind::NotSet),
     UserMode(UMK_NotSet),
     IPAMode(IPAK_NotSet),
     CXXMemberInliningMode() {}
diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
index 7472a7147fc..2232532e2df 100644
--- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
+++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
@@ -21,6 +21,7 @@
 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h"
+#include "clang/StaticAnalyzer/Core/AnalyzerOptions.h"
 #include <memory>
 
 namespace clang {
@@ -114,9 +115,9 @@ private:
 
 public:
   /// Construct a CoreEngine object to analyze the provided CFG.
-  CoreEngine(SubEngine &subengine, FunctionSummariesTy *FS)
-      : SubEng(subengine), WList(WorkList::makeDFS()),
-        BCounterFactory(G.getAllocator()), FunctionSummaries(FS) {}
+  CoreEngine(SubEngine &subengine,
+             FunctionSummariesTy *FS,
+             AnalyzerOptions &Opts);
 
   /// getGraph - Returns the exploded graph.
   ExplodedGraph &getGraph() { return G; }
diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h
index 2528aa1b316..a8ccb7c3f0b 100644
--- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h
+++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h
@@ -80,9 +80,9 @@ public:
   void setBlockCounter(BlockCounter C) { CurrentCounter = C; }
   BlockCounter getBlockCounter() const { return CurrentCounter; }
 
-  static WorkList *makeDFS();
-  static WorkList *makeBFS();
-  static WorkList *makeBFSBlockDFSContents();
+  static std::unique_ptr<WorkList> makeDFS();
+  static std::unique_ptr<WorkList> makeBFS();
+  static std::unique_ptr<WorkList> makeBFSBlockDFSContents();
 };
 
 } // end GR namespace
diff --git a/clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp b/clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
index 26fea772d0a..372cb2db061 100644
--- a/clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
+++ b/clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
@@ -55,6 +55,26 @@ AnalyzerOptions::UserModeKind AnalyzerOptions::getUserMode() {
   return UserMode;
 }
 
+AnalyzerOptions::ExplorationStrategyKind
+AnalyzerOptions::getExplorationStrategy() {
+  if (ExplorationStrategy == ExplorationStrategyKind::NotSet) {
+    StringRef StratStr = Config.insert(
+            std::make_pair("exploration_strategy", "dfs")).first->second;
+    ExplorationStrategy = llvm::StringSwitch<ExplorationStrategyKind>(StratStr)
+      .Case("dfs", ExplorationStrategyKind::DFS)
+      .Case("bfs", ExplorationStrategyKind::BFS)
+      .Case("loopstack_priority", ExplorationStrategyKind::LoopstackPriority)
+      .Case("bfs_block_dfs_contents", ExplorationStrategyKind::BFSBlockDFSContents)
+      .Default(ExplorationStrategyKind::NotSet);
+    assert(ExplorationStrategy != ExplorationStrategyKind::NotSet
+        && "User mode is invalid.");
+  }
+  return ExplorationStrategy;
+
+}
+
+
+
 IPAKind AnalyzerOptions::getIPAMode() {
   if (IPAMode == IPAK_NotSet) {
 
diff --git a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp
index 2fdd310fa31..a06c311590a 100644
--- a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp
+++ b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp
@@ -82,8 +82,13 @@ public:
 // functions, and we the code for the dstor generated in one compilation unit.
 WorkList::~WorkList() {}
 
-WorkList *WorkList::makeDFS() { return new DFS(); }
-WorkList *WorkList::makeBFS() { return new BFS(); }
+std::unique_ptr<WorkList> WorkList::makeDFS() {
+  return llvm::make_unique<DFS>();
+}
+
+std::unique_ptr<WorkList> WorkList::makeBFS() {
+  return llvm::make_unique<BFS>();
+}
 
 namespace {
   class BFSBlockDFSContents : public WorkList {
@@ -119,14 +124,34 @@ namespace {
   };
 } // end anonymous namespace
 
-WorkList* WorkList::makeBFSBlockDFSContents() {
-  return new BFSBlockDFSContents();
+std::unique_ptr<WorkList> WorkList::makeBFSBlockDFSContents() {
+  return llvm::make_unique<BFSBlockDFSContents>();
 }
 
 //===----------------------------------------------------------------------===//
 // Core analysis engine.
 //===----------------------------------------------------------------------===//
 
+static std::unique_ptr<WorkList> generateWorkList(AnalyzerOptions &Opts) {
+  switch (Opts.getExplorationStrategy()) {
+    case AnalyzerOptions::ExplorationStrategyKind::DFS:
+      return WorkList::makeDFS();
+    case AnalyzerOptions::ExplorationStrategyKind::BFS:
+      return WorkList::makeBFS();
+    case AnalyzerOptions::ExplorationStrategyKind::BFSBlockDFSContents:
+      return WorkList::makeBFSBlockDFSContents();
+    default:
+      llvm_unreachable("Unexpected case");
+  }
+}
+
+CoreEngine::CoreEngine(SubEngine &subengine,
+    FunctionSummariesTy *FS,
+    AnalyzerOptions &Opts) : SubEng(subengine),
+                             WList(generateWorkList(Opts)),
+                             BCounterFactory(G.getAllocator()),
+                             FunctionSummaries(FS) {}
+
 /// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps.
 bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps,
                                    ProgramStateRef InitState) {
diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp
index 4a179c5cc46..055152dd52f 100644
--- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp
+++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp
@@ -90,7 +90,7 @@ ExprEngine::ExprEngine(AnalysisManager &mgr, bool gcEnabled,
                        InliningModes HowToInlineIn)
   : AMgr(mgr),
     AnalysisDeclContexts(mgr.getAnalysisDeclContextManager()),
-    Engine(*this, FS),
+    Engine(*this, FS, mgr.getAnalyzerOptions()),
     G(Engine.getGraph()),
     StateMgr(getContext(), mgr.getStoreManagerCreator(),
              mgr.getConstraintManagerCreator(), G.getAllocator(),
diff --git a/clang/test/Analysis/analyzer-config.c b/clang/test/Analysis/analyzer-config.c
index 4daea898ecd..770ff3b404f 100644
--- a/clang/test/Analysis/analyzer-config.c
+++ b/clang/test/Analysis/analyzer-config.c
@@ -16,6 +16,7 @@ void foo() {
 // CHECK-NEXT: cfg-lifetime = false
 // CHECK-NEXT: cfg-loopexit = false
 // CHECK-NEXT: cfg-temporary-dtors = false
+// CHECK-NEXT: exploration_strategy = dfs
 // CHECK-NEXT: faux-bodies = true
 // CHECK-NEXT: graph-trim-interval = 1000
 // CHECK-NEXT: inline-lambdas = true
@@ -31,4 +32,4 @@ void foo() {
 // CHECK-NEXT: unroll-loops = false
 // CHECK-NEXT: widen-loops = false
 // CHECK-NEXT: [stats]
-// CHECK-NEXT: num-entries = 19
+// CHECK-NEXT: num-entries = 20
diff --git a/clang/test/Analysis/analyzer-config.cpp b/clang/test/Analysis/analyzer-config.cpp
index a08e85e53e4..a6e1df87458 100644
--- a/clang/test/Analysis/analyzer-config.cpp
+++ b/clang/test/Analysis/analyzer-config.cpp
@@ -27,6 +27,7 @@ public:
 // CHECK-NEXT: cfg-lifetime = false
 // CHECK-NEXT: cfg-loopexit = false
 // CHECK-NEXT: cfg-temporary-dtors = false
+// CHECK-NEXT: exploration_strategy = dfs
 // CHECK-NEXT: faux-bodies = true
 // CHECK-NEXT: graph-trim-interval = 1000
 // CHECK-NEXT: inline-lambdas = true
@@ -42,4 +43,4 @@ public:
 // CHECK-NEXT: unroll-loops = false
 // CHECK-NEXT: widen-loops = false
 // CHECK-NEXT: [stats]
-// CHECK-NEXT: num-entries = 24
+// CHECK-NEXT: num-entries = 25