1 files changed, 61 insertions, 1 deletions
diff --git a/lib/StaticAnalyzer/Core/WorkList.cpp b/lib/StaticAnalyzer/Core/WorkList.cpp
index 4b227375da9b..e705393cb83a 100644
--- a/lib/StaticAnalyzer/Core/WorkList.cpp
+++ b/lib/StaticAnalyzer/Core/WorkList.cpp
@@ -152,7 +152,7 @@ public:
     auto BE = N->getLocation().getAs<BlockEntrance>();
 
     if (!BE) {
-      // Assume the choice of the order of the preceeding block entrance was
+      // Assume the choice of the order of the preceding block entrance was
       // correct.
       StackUnexplored.push_back(U);
     } else {
@@ -252,3 +252,63 @@ public:
 std::unique_ptr<WorkList> WorkList::makeUnexploredFirstPriorityQueue() {
   return llvm::make_unique<UnexploredFirstPriorityQueue>();
 }
+
+namespace {
+class UnexploredFirstPriorityLocationQueue : public WorkList {
+  using LocIdentifier = const CFGBlock *;
+
+  // 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()]++;
+
+    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>();
+}