[analyzer] Exploration strategy prioritizing unexplored coverage first

[george.karpenkov]

Summary

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

[george.karpenkov]

Switching to CFGBlocks made # of bug reports / % coverage slightly worse compared to the version using Stmt *, I am still confused as to why.
Removing StackFrameContext* from location identifier makes everything considerably worse.

@NoQ I think this version can go in.

[NoQ]

I think you should add a test with foo() in else-branch as well, which has always passed, just to demonstrate that regardless of accidental if-branch analysis order we're doing the right thing.

[NoQ]

More minor nits, but yeah, this is great :)

lib/StaticAnalyzer/Core/CoreEngine.cpp

137

Does this invariant keep holding after we put the node here? Like, what if it wasn't traversed when we were putting it here, but while it's in the stack we've traversed it on a different path?

Suggests: NormalPriorityStack, LowPriorityStack. Explaining that the latter contains beginnings of paths that were down-prioritized because they lead into blocks that we've already visited in this function.

145

Capitalize?

157

Essentially we assume that we made the right choice on the block edge and the node is now being explored for a good reason, and now that we went down this path, there's no need to downprioritize other elements in this block.

[george.karpenkov]

lib/StaticAnalyzer/Core/CoreEngine.cpp

137

Like, what if it wasn't traversed when we were putting it here, but while it's in the stack we've traversed it on a different path?

Surprisingly, it does: the key here is that we check exploration at the push-time, not at the pop-time. That is, the block is added to "reachable" not when we explore it, but when we put the corresponding node into queue.
Thus it's not possible for the node in stackUnexplored to become explored via some other path.

[NoQ]

All right, so for now it is under the flag (-analyzer-config exploration_strategy=unexplored_first), it already makes a huge lot of sense, and it has tests, so i think we should land it now and flip the flag when we're ready.

It'd be great to have more direct tests for the exploration order, not just for the bugs. Probably dump CFG blocks in the traversal order, or even dump whole worklist snapshots for every analysis step - the latter seemed very useful while understanding the issue (we did it on the whiteboard, but i've no idea how huge would it be in practice, even if we still dump only CFG blocks of worklist units), because, as the original issue has demonstrated, even our simple DFS exploration may be completely counter-intuitive sometimes.

[george.karpenkov]

@NoQ

but i've no idea how huge would it be in practice

It's actually pretty small if we only do it for BlockEntrance edges.
Do you have any concrete ideas on how such dumping could be done? I could debug it by printing to llvm::errs(), but that's obviously not optimal.
I could use DEBUG(), but that's hacky, fragile, and would not even work in release builds.
I don't think I have good ideas left.

include/clang/StaticAnalyzer/Core/AnalyzerOptions.h

public:
   unsigned InlineMaxStackDepth;
   
   /// \brief The mode of function selection used during inlining.
   AnalysisInliningMode InliningMode;
 
   enum class ExplorationStrategyKind {
     DFS,
     BFS,
+    UnexploredFirst,
     BFSBlockDFSContents,
     NotSet
   };
 
 private:
 
   ExplorationStrategyKind ExplorationStrategy;
 

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

public:
   virtual WorkListUnit dequeue() = 0;
 
   void setBlockCounter(BlockCounter C) { CurrentCounter = C; }
   BlockCounter getBlockCounter() const { return CurrentCounter; }
 
   static std::unique_ptr<WorkList> makeDFS();
   static std::unique_ptr<WorkList> makeBFS();
   static std::unique_ptr<WorkList> makeBFSBlockDFSContents();
+  static std::unique_ptr<WorkList> makeUnexploredFirst();
 };
 
 } // end GR namespace
 
 } // end clang namespace
 
 #endif

lib/StaticAnalyzer/Core/AnalyzerOptions.cpp

if (UserMode == 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)
+    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("bfs_block_dfs_contents", ExplorationStrategyKind::BFSBlockDFSContents)
+            .Case("unexplored_first",
+                  ExplorationStrategyKind::UnexploredFirst)
+            .Case("bfs_block_dfs_contents",
+                  ExplorationStrategyKind::BFSBlockDFSContents)
             .Default(ExplorationStrategyKind::NotSet);
-    assert(ExplorationStrategy != ExplorationStrategyKind::NotSet
-        && "User mode is invalid.");
+    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

 
 #include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/ExprCXX.h"
 #include "clang/AST/StmtCXX.h"
 #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;
 using namespace ento;
 
 #define DEBUG_TYPE "CoreEngine"
 
 STATISTIC(NumSteps,
             "The # of steps executed.");
 STATISTIC(NumReachedMaxSteps,
             "The # of times we reached the max number of steps.");
 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.
 //===----------------------------------------------------------------------===//
 
 namespace {
 class DFS : public WorkList {
   SmallVector<WorkListUnit,20> Stack;
 public:
public:
     }
   };
 } // end anonymous namespace
 
 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.
 //===----------------------------------------------------------------------===//
 
 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::UnexploredFirst:
+      return WorkList::makeUnexploredFirst();
     default:
       llvm_unreachable("Unexpected case");
   }
 }
 
 CoreEngine::CoreEngine(SubEngine &subengine,
     FunctionSummariesTy *FS,
     AnalyzerOptions &Opts) : SubEng(subengine),

test/Analysis/exploration_order/prefer_unexplored.cc

+// RUN: %clang_analyze_cc1 -w -analyzer-checker=core -analyzer-config exploration_strategy=unexplored_first -analyzer-output=text -verify %s | FileCheck %s
+
+extern int coin();
+
+int foo() {
+    int *x = 0; // expected-note {{'x' initialized to a null pointer value}}
+    while (coin()) { // expected-note{{Loop condition is true}}
+        if (coin())  // expected-note {{Taking true branch}}
+            return *x; // expected-warning{{Dereference of null pointer (loaded from variable 'x')}}
+                       // expected-note@-1{{Dereference of null pointer (loaded from variable 'x')}}
+    }
+    return 0;
+}
+
+void bar() {
+    while(coin()) // expected-note{{Loop condition is true}}
+        if (coin()) // expected-note {{Assuming the condition is true}}
+            foo(); // expected-note{{Calling 'foo'}}
+}
+
+int foo2() {
+    int *x = 0; // expected-note {{'x' initialized to a null pointer value}}
+    while (coin()) { // expected-note{{Loop condition is true}}
+        if (coin())  // expected-note {{Taking false branch}}
+            return false;
+        else
+            return *x; // expected-warning{{Dereference of null pointer (loaded from variable 'x')}}
+                       // expected-note@-1{{Dereference of null pointer (loaded from variable 'x')}}
+    }
+    return 0;
+}
+
+void bar2() {
+    while(coin()) // expected-note{{Loop condition is true}}
+        if (coin()) // expected-note {{Assuming the condition is false}}
+          return false;
+        else
+            foo(); // expected-note{{Calling 'foo'}}
+}