[analyzer] Expose setting exploration strategy through an analyzer option

[NoQ]

I wonder how many of these options crash in no-asserts mode, and if it contradicts the purpose of -analyzer-config to avoid crashes when incompatible flags are passed.

[george.karpenkov]

@NoQ

I wonder how many of these options crash in no-asserts mode, and if it contradicts the purpose of -analyzer-config to avoid crashes when incompatible flags are passed.

Unless the analyzer has other bugs, it should not crash under any exploration order... A good stress-test would be even running all tests under all possible exploration orders.

[NoQ]

I mean, say, you add a new exploration order, then an external tool tells clang to use the new order, then this tool is used in combination with an old clang that doesn't have the mode yet, then the mode remains unset, goes through llvm_unreachable, and what not.

[george.karpenkov]

@NoQ argh. I suppose we could print an error message and resort back to DFS? I do not think such an approach is good in any way, but if never-crashing is an absolute must here...

[NoQ]

For now all other options are broken in a similar manner and nobody complained, just a thought.

[george.karpenkov]

@NoQ @dcoughlin I think I know what we should do: we should have different behavior depending on whether the analyzer is compiled with assertions, which is a very strong indicator that the user does want to have crashing error messages on bad options, as with other asserts.
If assertions are in, we should crash in such cases. Otherwise, do whatever is a sensible thing (e.g. switch to DFS).
I think this will also solve the problem of analyzer silently ignoring misspelled configuration options.

include/clang/StaticAnalyzer/Core/AnalyzerOptions.h

public:
   unsigned NoRetryExhausted : 1;
   
   /// \brief The inlining stack depth limit.
   unsigned InlineMaxStackDepth;
   
   /// \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,
     /// Perform shallow but fast analyzes.
     UMK_Shallow = 1,
     /// Perform deep analyzes.
     UMK_Deep = 2
   };
StringRef getOptionAsString(StringRef Name, StringRef DefaultVal,
                               const ento::CheckerBase *C = nullptr,
                               bool SearchInParents = false);
 
   /// \brief Retrieves and sets the UserMode. This is a high-level option,
   /// which is used to set other low-level options. It is not accessible
   /// outside of AnalyzerOptions.
   UserModeKind getUserMode();
 
+  ExplorationStrategyKind getExplorationStrategy();
+
   /// \brief Returns the inter-procedural analysis mode.
   IPAKind getIPAMode();
 
   /// Returns the option controlling which C++ member functions will be
   /// considered for inlining.
   ///
   /// This is controlled by the 'c++-inlining' config option.
   ///
AnalyzerOptions() :
     visualizeExplodedGraphWithGraphViz(0),
     visualizeExplodedGraphWithUbiGraph(0),
     UnoptimizedCFG(0),
     PrintStats(0),
     NoRetryExhausted(0),
     // 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() {}
 
 };
   
 typedef IntrusiveRefCntPtr<AnalyzerOptions> AnalyzerOptionsRef;
   
 }
 
 #endif

include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h

 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_COREENGINE_H
 
 #include "clang/AST/Expr.h"
 #include "clang/Analysis/AnalysisDeclContext.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h"
 #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 {
 
 class ProgramPointTag;
   
 namespace ento {
 
private:
   CoreEngine(const CoreEngine &) = delete;
   void operator=(const CoreEngine &) = delete;
 
   ExplodedNode *generateCallExitBeginNode(ExplodedNode *N,
                                           const ReturnStmt *RS);
 
 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; }
 
   /// ExecuteWorkList - Run the worklist algorithm for a maximum number of
   ///  steps.  Returns true if there is still simulation state on the worklist.
   bool ExecuteWorkList(const LocationContext *L, unsigned Steps,
                        ProgramStateRef InitState);

include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h

void enqueue(ExplodedNode *N) {
     enqueue(WorkListUnit(N, CurrentCounter));
   }
 
   virtual WorkListUnit dequeue() = 0;
 
   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
 
 } // end clang namespace
 
 #endif

lib/StaticAnalyzer/Core/AnalyzerOptions.cpp

UserMode = llvm::StringSwitch<UserModeKind>(ModeStr)
       .Case("shallow", UMK_Shallow)
       .Case("deep", UMK_Deep)
       .Default(UMK_NotSet);
     assert(UserMode != UMK_NotSet && "User mode is invalid.");
   }
   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) {
 
     // Use the User Mode to set the default IPA value.
     // Note, we have to add the string to the Config map for the ConfigDumper
     // checker to function properly.
     const char *DefaultIPA = nullptr;
     UserModeKind HighLevelMode = getUserMode();

lib/StaticAnalyzer/Core/CoreEngine.cpp

 };
 
 } // end anonymous namespace
 
 // Place the dstor for WorkList here because it contains virtual member
 // 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 {
     std::deque<WorkListUnit> Queue;
     SmallVector<WorkListUnit,20> Stack;
   public:
     bool hasWork() const override {
       return !Queue.empty() || !Stack.empty();
WorkListUnit dequeue() override {
       // unsafe.
       WorkListUnit U = Queue.front();
       Queue.pop_front();
       return U;
     }
   };
 } // 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();
+    case AnalyzerOptions::ExplorationStrategyKind::LoopstackPriority:
+      return WorkList::makePriorityQueue();
+    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) {
 
   if (G.num_roots() == 0) { // Initialize the analysis by constructing
     // the root if none exists.
 
     const CFGBlock *Entry = &(L->getCFG()->getEntry());

lib/StaticAnalyzer/Core/ExprEngine.cpp

 static const char* TagProviderName = "ExprEngine";
 
 ExprEngine::ExprEngine(AnalysisManager &mgr, bool gcEnabled,
                        SetOfConstDecls *VisitedCalleesIn,
                        FunctionSummariesTy *FS,
                        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(),
              this),
     SymMgr(StateMgr.getSymbolManager()),
     svalBuilder(StateMgr.getSValBuilder()),
     currStmtIdx(0), currBldrCtx(nullptr),
     ObjCNoRet(mgr.getASTContext()),

test/Analysis/analyzer-config.c

 }
 
 // CHECK: [config]
 // CHECK-NEXT: cfg-conditional-static-initializers = true
 // CHECK-NEXT: cfg-implicit-dtors = true
 // 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
 // CHECK-NEXT: ipa = dynamic-bifurcate
 // CHECK-NEXT: ipa-always-inline-size = 3
 // CHECK-NEXT: leak-diagnostics-reference-allocation = false
 // CHECK-NEXT: max-inlinable-size = 100
 // CHECK-NEXT: max-nodes = 225000
 // CHECK-NEXT: max-times-inline-large = 32
 // CHECK-NEXT: min-cfg-size-treat-functions-as-large = 14
 // CHECK-NEXT: mode = deep
 // CHECK-NEXT: region-store-small-struct-limit = 2
 // CHECK-NEXT: unroll-loops = false
 // CHECK-NEXT: widen-loops = false
 // CHECK-NEXT: [stats]
-// CHECK-NEXT: num-entries = 19
+// CHECK-NEXT: num-entries = 20

test/Analysis/analyzer-config.cpp

 // CHECK-NEXT: c++-shared_ptr-inlining = false
 // CHECK-NEXT: c++-stdlib-inlining = true
 // CHECK-NEXT: c++-template-inlining = true
 // CHECK-NEXT: cfg-conditional-static-initializers = true
 // CHECK-NEXT: cfg-implicit-dtors = true
 // 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
 // CHECK-NEXT: ipa = dynamic-bifurcate
 // CHECK-NEXT: ipa-always-inline-size = 3
 // CHECK-NEXT: leak-diagnostics-reference-allocation = false
 // CHECK-NEXT: max-inlinable-size = 100
 // CHECK-NEXT: max-nodes = 225000
 // CHECK-NEXT: max-times-inline-large = 32
 // CHECK-NEXT: min-cfg-size-treat-functions-as-large = 14
 // CHECK-NEXT: mode = deep
 // CHECK-NEXT: region-store-small-struct-limit = 2
 // CHECK-NEXT: unroll-loops = false
 // CHECK-NEXT: widen-loops = false
 // CHECK-NEXT: [stats]
-// CHECK-NEXT: num-entries = 24
+// CHECK-NEXT: num-entries = 25