[analyzer] Exploration strategy prioritizing unexplored coverage first

See reviews.llvm.org/M1 for evaluation, and
lists.llvm.org/pipermail/cfe-dev/2018-January/056718.html for
discussion.

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

llvm-svn: 324956

1 files changed, 64 insertions, 0 deletions

diff --git a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp
index 115b5a1c29b..4b57419fd8c 100644
--- a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp
+++ b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp
@@ -19,6 +19,7 @@
 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/Support/Casting.h"
 
 using namespace clang;
@@ -33,6 +34,9 @@ STATISTIC(NumReachedMaxSteps,
 STATISTIC(NumPathsExplored,
             "The # of paths explored by the analyzer.");
 
+STATISTIC(MaxQueueSize, "Maximum size of the worklist");
+STATISTIC(MaxReachableSize, "Maximum size of auxiliary worklist set");
+
 //===----------------------------------------------------------------------===//
 // Worklist classes for exploration of reachable states.
 //===----------------------------------------------------------------------===//
@@ -128,6 +132,64 @@ std::unique_ptr<WorkList> WorkList::makeBFSBlockDFSContents() {
   return llvm::make_unique<BFSBlockDFSContents>();
 }
 
+class UnexploredFirstStack : public WorkList {
+
+  /// Stack of nodes known to have statements we have not traversed yet.
+  SmallVector<WorkListUnit, 20> StackUnexplored;
+
+  /// Stack of all other nodes.
+  SmallVector<WorkListUnit, 20> StackOthers;
+
+  typedef unsigned BlockID;
+  typedef std::pair<BlockID, const StackFrameContext *> LocIdentifier;
+  llvm::DenseSet<LocIdentifier> Reachable;
+
+public:
+  bool hasWork() const override {
+    return !(StackUnexplored.empty() && StackOthers.empty());
+  }
+
+  void enqueue(const WorkListUnit &U) override {
+    const ExplodedNode *N = U.getNode();
+    auto BE = N->getLocation().getAs<BlockEntrance>();
+
+    if (!BE) {
+
+      // Assume the choice of the order of the preceeding block entrance was
+      // correct.
+      StackUnexplored.push_back(U);
+    } else {
+      LocIdentifier LocId = std::make_pair(
+          BE->getBlock()->getBlockID(), N->getStackFrame());
+      auto InsertInfo = Reachable.insert(LocId);
+
+      if (InsertInfo.second) {
+        StackUnexplored.push_back(U);
+      } else {
+        StackOthers.push_back(U);
+      }
+    }
+    MaxReachableSize.updateMax(Reachable.size());
+    MaxQueueSize.updateMax(StackUnexplored.size() + StackOthers.size());
+  }
+
+  WorkListUnit dequeue() override {
+    if (!StackUnexplored.empty()) {
+      WorkListUnit &U = StackUnexplored.back();
+      StackUnexplored.pop_back();
+      return U;
+    } else {
+      WorkListUnit &U = StackOthers.back();
+      StackOthers.pop_back();
+      return U;
+    }
+  }
+};
+
+std::unique_ptr<WorkList> WorkList::makeUnexploredFirst() {
+  return llvm::make_unique<UnexploredFirstStack>();
+}
+
 //===----------------------------------------------------------------------===//
 // Core analysis engine.
 //===----------------------------------------------------------------------===//
@@ -140,6 +202,8 @@ static std::unique_ptr<WorkList> generateWorkList(AnalyzerOptions &Opts) {
       return WorkList::makeBFS();
     case AnalyzerOptions::ExplorationStrategyKind::BFSBlockDFSContents:
       return WorkList::makeBFSBlockDFSContents();
+    case AnalyzerOptions::ExplorationStrategyKind::UnexploredFirst:
+      return WorkList::makeUnexploredFirst();
     default:
       llvm_unreachable("Unexpected case");
   }