This revision was automatically updated to reflect the committed changes.
Closed by commit rC326136: [analyzer] Exploration strategy prioritizing
unexplored nodes first (authored by george.karpenkov, committed by ).
Herald added a subscriber: cfe-commits.
Repository:
rC Clang
https://reviews.llvm.org/D43354
Files:
include/clang/StaticAnalyzer/Core/AnalyzerOptions.h
include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h
lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
lib/StaticAnalyzer/Core/CoreEngine.cpp
test/Analysis/exploration_order/prefer_unexplored.cc
Index: include/clang/StaticAnalyzer/Core/AnalyzerOptions.h
===================================================================
--- include/clang/StaticAnalyzer/Core/AnalyzerOptions.h
+++ include/clang/StaticAnalyzer/Core/AnalyzerOptions.h
@@ -192,6 +192,7 @@
DFS,
BFS,
UnexploredFirst,
+ UnexploredFirstQueue,
BFSBlockDFSContents,
NotSet
};
Index: include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h
===================================================================
--- include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h
+++ include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h
@@ -84,6 +84,7 @@
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
Index: test/Analysis/exploration_order/prefer_unexplored.cc
===================================================================
--- test/Analysis/exploration_order/prefer_unexplored.cc
+++ test/Analysis/exploration_order/prefer_unexplored.cc
@@ -1,4 +1,5 @@
// 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();
Index: lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
===================================================================
--- lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
+++ lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
@@ -68,6 +68,8 @@
.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);
Index: lib/StaticAnalyzer/Core/CoreEngine.cpp
===================================================================
--- lib/StaticAnalyzer/Core/CoreEngine.cpp
+++ lib/StaticAnalyzer/Core/CoreEngine.cpp
@@ -20,7 +20,9 @@
#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;
@@ -192,6 +194,66 @@
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.
//===----------------------------------------------------------------------===//
@@ -206,6 +268,8 @@
return WorkList::makeBFSBlockDFSContents();
case AnalyzerOptions::ExplorationStrategyKind::UnexploredFirst:
return WorkList::makeUnexploredFirst();
+ case AnalyzerOptions::ExplorationStrategyKind::UnexploredFirstQueue:
+ return WorkList::makeUnexploredFirstPriorityQueue();
default:
llvm_unreachable("Unexpected case");
}
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
