[analyzer] Experiment with an iteration order only based on location, and not using the stack frame

[george.karpenkov]

Summary

This commit is mostly for experimentation purposes so far.
If the new iteration order is more successful, it would replace the previous one.

[Szelethus]

I remember when I joined the project how my team used to analyze projects with every iteration order to which is the best, so I think this patch will be appreciated.

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

61 ↗

(On Diff #168933)

Completely unrelated to this revision, but this class needs some doc desperately IMO :/

clang/lib/StaticAnalyzer/Core/WorkList.cpp

258 ↗

(On Diff #168933)

CFGBlock::getBlockID returns with an unsigned int, did you mean this to be signed? I don't mean to be a living and breathing clang-tidy, but you explicitly mentioned using signed integer in the comment below.

272 ↗

(On Diff #168933)

I believe some bots like to complain if you don't make operator() const.

299 ↗

(On Diff #168933)

How about queue.push({U, {-NumVisited, ++Counter}});?

[NoQ]

Let's see how it goes!

That's a lot of code duplication, i guess it might make sense to refactor later.

clang/lib/StaticAnalyzer/Core/WorkList.cpp

258 ↗

(On Diff #168933)

No, it doesn't need to be int; the comment below is about the other int.

[NoQ]

A few post-commit thoughts.

cfe/trunk/lib/StaticAnalyzer/Core/WorkList.cpp

284

I usually imagine queue as a horizontal thing, so it's unclear to me whether "top" is "left" or "right".

297

Does this mean that Block 1 in foo() and Block 1 in bar() will always have the same NumReached value?

[george.karpenkov]

cfe/trunk/lib/StaticAnalyzer/Core/WorkList.cpp

297

That's a great point. Pushing an update.

cfe/trunk/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h

public:
   /// The mode of function selection used during inlining.
   AnalysisInliningMode InliningMode = NoRedundancy;
 
   enum class ExplorationStrategyKind {
     DFS,
     BFS,
     UnexploredFirst,
     UnexploredFirstQueue,
+    UnexploredFirstLocationQueue,
     BFSBlockDFSContents,
     NotSet
   };
 
 private:
   ExplorationStrategyKind ExplorationStrategy = ExplorationStrategyKind::NotSet;
 
   /// Describes the kinds for high-level analyzer mode.

cfe/trunk/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();
+  static std::unique_ptr<WorkList> makeUnexploredFirstPriorityLocationQueue();
 };
 
 } // end ento namespace
 
 } // end clang namespace
 
 #endif

cfe/trunk/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp

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

cfe/trunk/lib/StaticAnalyzer/Core/CoreEngine.cpp

STATISTIC(NumReachedMaxSteps,
             "The # of times we reached the max number of steps.");
 STATISTIC(NumPathsExplored,
             "The # of paths explored by the analyzer.");
 
 //===----------------------------------------------------------------------===//
 // Core analysis engine.
 //===----------------------------------------------------------------------===//
 
-static std::unique_ptr<WorkList> generateWorkList(AnalyzerOptions &Opts) {
+static std::unique_ptr<WorkList> generateWorkList(AnalyzerOptions &Opts,
+                                                  SubEngine &subengine) {
   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();
+    case AnalyzerOptions::ExplorationStrategyKind::UnexploredFirstLocationQueue:
+      return WorkList::makeUnexploredFirstPriorityLocationQueue();
     default:
       llvm_unreachable("Unexpected case");
   }
 }
 
 CoreEngine::CoreEngine(SubEngine &subengine, FunctionSummariesTy *FS,
                        AnalyzerOptions &Opts)
-    : SubEng(subengine), WList(generateWorkList(Opts)),
+    : SubEng(subengine), WList(generateWorkList(Opts, subengine)),
       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.
 

cfe/trunk/lib/StaticAnalyzer/Core/WorkList.cpp

WorkListUnit dequeue() override {
     return U.first;
   }
 };
 } // namespace
 
 std::unique_ptr<WorkList> WorkList::makeUnexploredFirstPriorityQueue() {
   return llvm::make_unique<UnexploredFirstPriorityQueue>();
 }
+
+namespace {
+class UnexploredFirstPriorityLocationQueue : public WorkList {
+  using LocIdentifier = int;
+
+  // How many times each location was visited.
+  // Is signed because we negate it later in order to have a reversed
+  // comparison.
+  using VisitedTimesMap = llvm::DenseMap<LocIdentifier, int>;
+
+  // 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).
+  using QueuePriority = std::pair<int, unsigned long>;
+  using QueueItem = std::pair<WorkListUnit, QueuePriority>;
+
+  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>())
+      NumVisited = NumReached[BE->getBlock()->getBlockID()]++;
+
+    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::makeUnexploredFirstPriorityLocationQueue() {
+  return llvm::make_unique<UnexploredFirstPriorityLocationQueue>();
+}