[analyzer] Exploration strategy prioritizing unexplored nodes first

[george.karpenkov]

Summary

See D42775 for discussion.
Turns out, just exploring nodes which weren't explored first is not quite enough, as e.g. the first quick traversal resulting in a report can mark everything as "visited", and then subsequent traversals of the same region will get all the pitfalls of DFS.
Priority queue-based approach in comparison shows much greater increase in coverage and even performance, without sacrificing memory.

[NoQ]

Looks great. Do you have any tests to demonstrate the difference?

lib/StaticAnalyzer/Core/CoreEngine.cpp

198

Uhm, this should have been typedef-ed in CFGBlock.

241

Because nobody knows what type -NumVIsited is and if it's going to be properly sign-extended and truncated into int, maybe lets just make all of these ints?

[george.karpenkov]

Do you have any tests to demonstrate the difference?

Not on small files, unfortunately. Differences on large projects in performance, coverage and path lengths are very noticeable though.

[NoQ]

All right, so at least we know that it works. I guess we need a better testing system to test exploration order, and please keep us informed if you manage to reduce an example for us :)

include/clang/StaticAnalyzer/Core/AnalyzerOptions.h

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

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

public:
 
   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();
+  static std::unique_ptr<WorkList> makeUnexploredFirstPriorityQueue();
 };
 
 } // end GR namespace
 
 } // end clang namespace
 
 #endif

lib/StaticAnalyzer/Core/AnalyzerOptions.cpp

StringRef StratStr =
             .insert(std::make_pair("exploration_strategy", "dfs"))
             .first->second;
     ExplorationStrategy =
         llvm::StringSwitch<ExplorationStrategyKind>(StratStr)
             .Case("dfs", ExplorationStrategyKind::DFS)
             .Case("bfs", ExplorationStrategyKind::BFS)
             .Case("unexplored_first",
                   ExplorationStrategyKind::UnexploredFirst)
+            .Case("unexplored_first_queue",
+                  ExplorationStrategyKind::UnexploredFirstQueue)
             .Case("bfs_block_dfs_contents",
                   ExplorationStrategyKind::BFSBlockDFSContents)
             .Default(ExplorationStrategyKind::NotSet);
     assert(ExplorationStrategy != ExplorationStrategyKind::NotSet &&
            "User mode is invalid.");
   }
   return ExplorationStrategy;
 }

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/ADT/DenseMap.h"
 #include "llvm/Support/Casting.h"
+#include "llvm/ADT/PriorityQueue.h"
 
 using namespace clang;
 using namespace ento;
 
 #define DEBUG_TYPE "CoreEngine"
 
 STATISTIC(NumSteps,
             "The # of steps executed.");
public:
   }
 };
 } // end anonymous namespace
 
 std::unique_ptr<WorkList> WorkList::makeUnexploredFirst() {
   return llvm::make_unique<UnexploredFirstStack>();
 }
 
+class UnexploredFirstPriorityQueue : public WorkList {
+  typedef unsigned BlockID;
+  typedef std::pair<BlockID, const StackFrameContext *> LocIdentifier;
+
+  // How many times each location was visited.
+  // Is signed because we negate it later in order to have a reversed
+  // comparison.
+  typedef llvm::DenseMap<LocIdentifier, int> VisitedTimesMap;
+
+  // Compare by number of times the location was visited first (negated
+  // to prefer less often visited locations), then by insertion time (prefer
+  // expanding nodes inserted sooner first).
+  typedef std::pair<int, unsigned long> QueuePriority;
+  typedef std::pair<WorkListUnit, QueuePriority> QueueItem;
+
+  struct ExplorationComparator {
+    bool operator() (const QueueItem &LHS, const QueueItem &RHS) {
+      return LHS.second < RHS.second;
+    }
+  };
+
+  // Number of inserted nodes, used to emulate DFS ordering in the priority
+  // queue when insertions are equal.
+  unsigned long Counter = 0;
+
+  // Number of times a current location was reached.
+  VisitedTimesMap NumReached;
+
+  // The top item is the largest one.
+  llvm::PriorityQueue<QueueItem, std::vector<QueueItem>, ExplorationComparator>
+      queue;
+
+public:
+  bool hasWork() const override {
+    return !queue.empty();
+  }
+
+  void enqueue(const WorkListUnit &U) override {
+    const ExplodedNode *N = U.getNode();
+    unsigned NumVisited = 0;
+    if (auto BE = N->getLocation().getAs<BlockEntrance>()) {
+      LocIdentifier LocId = std::make_pair(
+          BE->getBlock()->getBlockID(), N->getStackFrame());
+      NumVisited = NumReached[LocId]++;
+    }
+
+    queue.push(std::make_pair(U, std::make_pair(-NumVisited, ++Counter)));
+  }
+
+  WorkListUnit dequeue() override {
+    QueueItem U = queue.top();
+    queue.pop();
+    return U.first;
+  }
+};
+
+std::unique_ptr<WorkList> WorkList::makeUnexploredFirstPriorityQueue() {
+  return llvm::make_unique<UnexploredFirstPriorityQueue>();
+}
+
 //===----------------------------------------------------------------------===//
 // 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();
+    case AnalyzerOptions::ExplorationStrategyKind::UnexploredFirstQueue:
+      return WorkList::makeUnexploredFirstPriorityQueue();
     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
+// RUN: %clang_analyze_cc1 -w -analyzer-checker=core -analyzer-config exploration_strategy=unexplored_first_queue -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')}}