1 //===- WorkList.cpp - Analyzer work-list implementation--------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Defines different worklist implementations for the static analyzer.
12 //===----------------------------------------------------------------------===//
14 #include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h"
15 #include "llvm/ADT/PriorityQueue.h"
16 #include "llvm/ADT/DenseSet.h"
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/Statistic.h"
23 using namespace clang;
26 #define DEBUG_TYPE "WorkList"
28 STATISTIC(MaxQueueSize, "Maximum size of the worklist");
29 STATISTIC(MaxReachableSize, "Maximum size of auxiliary worklist set");
31 //===----------------------------------------------------------------------===//
32 // Worklist classes for exploration of reachable states.
33 //===----------------------------------------------------------------------===//
37 class DFS : public WorkList {
38 SmallVector<WorkListUnit, 20> Stack;
41 bool hasWork() const override {
42 return !Stack.empty();
45 void enqueue(const WorkListUnit& U) override {
49 WorkListUnit dequeue() override {
50 assert(!Stack.empty());
51 const WorkListUnit& U = Stack.back();
52 Stack.pop_back(); // This technically "invalidates" U, but we are fine.
57 class BFS : public WorkList {
58 std::deque<WorkListUnit> Queue;
61 bool hasWork() const override {
62 return !Queue.empty();
65 void enqueue(const WorkListUnit& U) override {
69 WorkListUnit dequeue() override {
70 WorkListUnit U = Queue.front();
78 // Place the dstor for WorkList here because it contains virtual member
79 // functions, and we the code for the dstor generated in one compilation unit.
80 WorkList::~WorkList() = default;
82 std::unique_ptr<WorkList> WorkList::makeDFS() {
83 return llvm::make_unique<DFS>();
86 std::unique_ptr<WorkList> WorkList::makeBFS() {
87 return llvm::make_unique<BFS>();
92 class BFSBlockDFSContents : public WorkList {
93 std::deque<WorkListUnit> Queue;
94 SmallVector<WorkListUnit, 20> Stack;
97 bool hasWork() const override {
98 return !Queue.empty() || !Stack.empty();
101 void enqueue(const WorkListUnit& U) override {
102 if (U.getNode()->getLocation().getAs<BlockEntrance>())
108 WorkListUnit dequeue() override {
109 // Process all basic blocks to completion.
110 if (!Stack.empty()) {
111 const WorkListUnit& U = Stack.back();
112 Stack.pop_back(); // This technically "invalidates" U, but we are fine.
116 assert(!Queue.empty());
117 // Don't use const reference. The subsequent pop_back() might make it
119 WorkListUnit U = Queue.front();
127 std::unique_ptr<WorkList> WorkList::makeBFSBlockDFSContents() {
128 return llvm::make_unique<BFSBlockDFSContents>();
133 class UnexploredFirstStack : public WorkList {
134 /// Stack of nodes known to have statements we have not traversed yet.
135 SmallVector<WorkListUnit, 20> StackUnexplored;
137 /// Stack of all other nodes.
138 SmallVector<WorkListUnit, 20> StackOthers;
140 using BlockID = unsigned;
141 using LocIdentifier = std::pair<BlockID, const StackFrameContext *>;
143 llvm::DenseSet<LocIdentifier> Reachable;
146 bool hasWork() const override {
147 return !(StackUnexplored.empty() && StackOthers.empty());
150 void enqueue(const WorkListUnit &U) override {
151 const ExplodedNode *N = U.getNode();
152 auto BE = N->getLocation().getAs<BlockEntrance>();
155 // Assume the choice of the order of the preceding block entrance was
157 StackUnexplored.push_back(U);
159 LocIdentifier LocId = std::make_pair(
160 BE->getBlock()->getBlockID(),
161 N->getLocationContext()->getStackFrame());
162 auto InsertInfo = Reachable.insert(LocId);
164 if (InsertInfo.second) {
165 StackUnexplored.push_back(U);
167 StackOthers.push_back(U);
170 MaxReachableSize.updateMax(Reachable.size());
171 MaxQueueSize.updateMax(StackUnexplored.size() + StackOthers.size());
174 WorkListUnit dequeue() override {
175 if (!StackUnexplored.empty()) {
176 WorkListUnit &U = StackUnexplored.back();
177 StackUnexplored.pop_back();
180 WorkListUnit &U = StackOthers.back();
181 StackOthers.pop_back();
189 std::unique_ptr<WorkList> WorkList::makeUnexploredFirst() {
190 return llvm::make_unique<UnexploredFirstStack>();
194 class UnexploredFirstPriorityQueue : public WorkList {
195 using BlockID = unsigned;
196 using LocIdentifier = std::pair<BlockID, const StackFrameContext *>;
198 // How many times each location was visited.
199 // Is signed because we negate it later in order to have a reversed
201 using VisitedTimesMap = llvm::DenseMap<LocIdentifier, int>;
203 // Compare by number of times the location was visited first (negated
204 // to prefer less often visited locations), then by insertion time (prefer
205 // expanding nodes inserted sooner first).
206 using QueuePriority = std::pair<int, unsigned long>;
207 using QueueItem = std::pair<WorkListUnit, QueuePriority>;
209 struct ExplorationComparator {
210 bool operator() (const QueueItem &LHS, const QueueItem &RHS) {
211 return LHS.second < RHS.second;
215 // Number of inserted nodes, used to emulate DFS ordering in the priority
216 // queue when insertions are equal.
217 unsigned long Counter = 0;
219 // Number of times a current location was reached.
220 VisitedTimesMap NumReached;
222 // The top item is the largest one.
223 llvm::PriorityQueue<QueueItem, std::vector<QueueItem>, ExplorationComparator>
227 bool hasWork() const override {
228 return !queue.empty();
231 void enqueue(const WorkListUnit &U) override {
232 const ExplodedNode *N = U.getNode();
233 unsigned NumVisited = 0;
234 if (auto BE = N->getLocation().getAs<BlockEntrance>()) {
235 LocIdentifier LocId = std::make_pair(
236 BE->getBlock()->getBlockID(),
237 N->getLocationContext()->getStackFrame());
238 NumVisited = NumReached[LocId]++;
241 queue.push(std::make_pair(U, std::make_pair(-NumVisited, ++Counter)));
244 WorkListUnit dequeue() override {
245 QueueItem U = queue.top();
252 std::unique_ptr<WorkList> WorkList::makeUnexploredFirstPriorityQueue() {
253 return llvm::make_unique<UnexploredFirstPriorityQueue>();
257 class UnexploredFirstPriorityLocationQueue : public WorkList {
258 using LocIdentifier = const CFGBlock *;
260 // How many times each location was visited.
261 // Is signed because we negate it later in order to have a reversed
263 using VisitedTimesMap = llvm::DenseMap<LocIdentifier, int>;
265 // Compare by number of times the location was visited first (negated
266 // to prefer less often visited locations), then by insertion time (prefer
267 // expanding nodes inserted sooner first).
268 using QueuePriority = std::pair<int, unsigned long>;
269 using QueueItem = std::pair<WorkListUnit, QueuePriority>;
271 struct ExplorationComparator {
272 bool operator() (const QueueItem &LHS, const QueueItem &RHS) {
273 return LHS.second < RHS.second;
277 // Number of inserted nodes, used to emulate DFS ordering in the priority
278 // queue when insertions are equal.
279 unsigned long Counter = 0;
281 // Number of times a current location was reached.
282 VisitedTimesMap NumReached;
284 // The top item is the largest one.
285 llvm::PriorityQueue<QueueItem, std::vector<QueueItem>, ExplorationComparator>
289 bool hasWork() const override {
290 return !queue.empty();
293 void enqueue(const WorkListUnit &U) override {
294 const ExplodedNode *N = U.getNode();
295 unsigned NumVisited = 0;
296 if (auto BE = N->getLocation().getAs<BlockEntrance>())
297 NumVisited = NumReached[BE->getBlock()]++;
299 queue.push(std::make_pair(U, std::make_pair(-NumVisited, ++Counter)));
302 WorkListUnit dequeue() override {
303 QueueItem U = queue.top();
312 std::unique_ptr<WorkList> WorkList::makeUnexploredFirstPriorityLocationQueue() {
313 return llvm::make_unique<UnexploredFirstPriorityLocationQueue>();