1//===- WorkList.cpp - Analyzer work-list implementation--------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// Defines different worklist implementations for the static analyzer.
10//
11//===----------------------------------------------------------------------===//
12
13#include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h"
14#include "clang/StaticAnalyzer/Core/PathSensitive/EntryPointStats.h"
15#include "llvm/ADT/DenseMap.h"
16#include "llvm/ADT/DenseSet.h"
17#include "llvm/ADT/PriorityQueue.h"
18#include "llvm/ADT/STLExtras.h"
19#include <deque>
20#include <vector>
21
22using namespace clang;
23using namespace ento;
24
25#define DEBUG_TYPE "WorkList"
26
27STAT_MAX(MaxQueueSize, "Maximum size of the worklist");
28STAT_MAX(MaxReachableSize, "Maximum size of auxiliary worklist set");
29
30//===----------------------------------------------------------------------===//
31// Worklist classes for exploration of reachable states.
32//===----------------------------------------------------------------------===//
33
34namespace {
35
36class DFS : public WorkList {
37 SmallVector<WorkListUnit, 20> Stack;
38
39public:
40 bool hasWork() const override {
41 return !Stack.empty();
42 }
43
44 void enqueue(const WorkListUnit& U) override {
45 Stack.push_back(Elt: U);
46 }
47
48 WorkListUnit dequeue() override {
49 assert(!Stack.empty());
50 const WorkListUnit& U = Stack.back();
51 Stack.pop_back(); // This technically "invalidates" U, but we are fine.
52 return U;
53 }
54};
55
56class BFS : public WorkList {
57 std::deque<WorkListUnit> Queue;
58
59public:
60 bool hasWork() const override {
61 return !Queue.empty();
62 }
63
64 void enqueue(const WorkListUnit& U) override {
65 Queue.push_back(x: U);
66 }
67
68 WorkListUnit dequeue() override {
69 WorkListUnit U = Queue.front();
70 Queue.pop_front();
71 return U;
72 }
73};
74
75} // namespace
76
77// Place the dstor for WorkList here because it contains virtual member
78// functions, and we the code for the dstor generated in one compilation unit.
79WorkList::~WorkList() = default;
80
81std::unique_ptr<WorkList> WorkList::makeDFS() {
82 return std::make_unique<DFS>();
83}
84
85std::unique_ptr<WorkList> WorkList::makeBFS() {
86 return std::make_unique<BFS>();
87}
88
89namespace {
90
91 class BFSBlockDFSContents : public WorkList {
92 std::deque<WorkListUnit> Queue;
93 SmallVector<WorkListUnit, 20> Stack;
94
95 public:
96 bool hasWork() const override {
97 return !Queue.empty() || !Stack.empty();
98 }
99
100 void enqueue(const WorkListUnit& U) override {
101 if (U.getNode()->getLocation().getAs<BlockEntrance>())
102 Queue.push_front(x: U);
103 else
104 Stack.push_back(Elt: U);
105 }
106
107 WorkListUnit dequeue() override {
108 // Process all basic blocks to completion.
109 if (!Stack.empty()) {
110 const WorkListUnit& U = Stack.back();
111 Stack.pop_back(); // This technically "invalidates" U, but we are fine.
112 return U;
113 }
114
115 assert(!Queue.empty());
116 // Don't use const reference. The subsequent pop_back() might make it
117 // unsafe.
118 WorkListUnit U = Queue.front();
119 Queue.pop_front();
120 return U;
121 }
122 };
123
124} // namespace
125
126std::unique_ptr<WorkList> WorkList::makeBFSBlockDFSContents() {
127 return std::make_unique<BFSBlockDFSContents>();
128}
129
130namespace {
131
132class UnexploredFirstStack : public WorkList {
133 /// Stack of nodes known to have statements we have not traversed yet.
134 SmallVector<WorkListUnit, 20> StackUnexplored;
135
136 /// Stack of all other nodes.
137 SmallVector<WorkListUnit, 20> StackOthers;
138
139 using BlockID = unsigned;
140 using LocIdentifier = std::pair<BlockID, const StackFrame *>;
141
142 llvm::DenseSet<LocIdentifier> Reachable;
143
144public:
145 bool hasWork() const override {
146 return !(StackUnexplored.empty() && StackOthers.empty());
147 }
148
149 void enqueue(const WorkListUnit &U) override {
150 const ExplodedNode *N = U.getNode();
151 auto BE = N->getLocation().getAs<BlockEntrance>();
152
153 if (!BE) {
154 // Assume the choice of the order of the preceding block entrance was
155 // correct.
156 StackUnexplored.push_back(Elt: U);
157 } else {
158 LocIdentifier LocId =
159 std::make_pair(x: BE->getBlock()->getBlockID(), y: N->getStackFrame());
160 auto InsertInfo = Reachable.insert(V: LocId);
161
162 if (InsertInfo.second) {
163 StackUnexplored.push_back(Elt: U);
164 } else {
165 StackOthers.push_back(Elt: U);
166 }
167 }
168 MaxReachableSize.updateMax(Value: Reachable.size());
169 MaxQueueSize.updateMax(Value: StackUnexplored.size() + StackOthers.size());
170 }
171
172 WorkListUnit dequeue() override {
173 if (!StackUnexplored.empty()) {
174 WorkListUnit &U = StackUnexplored.back();
175 StackUnexplored.pop_back();
176 return U;
177 } else {
178 WorkListUnit &U = StackOthers.back();
179 StackOthers.pop_back();
180 return U;
181 }
182 }
183};
184
185} // namespace
186
187std::unique_ptr<WorkList> WorkList::makeUnexploredFirst() {
188 return std::make_unique<UnexploredFirstStack>();
189}
190
191namespace {
192class UnexploredFirstPriorityQueue : public WorkList {
193 using BlockID = unsigned;
194 using LocIdentifier = std::pair<BlockID, const StackFrame *>;
195
196 // How many times each location was visited.
197 // Is signed because we negate it later in order to have a reversed
198 // comparison.
199 using VisitedTimesMap = llvm::DenseMap<LocIdentifier, int>;
200
201 // Compare by number of times the location was visited first (negated
202 // to prefer less often visited locations), then by insertion time (prefer
203 // expanding nodes inserted sooner first).
204 using QueuePriority = std::pair<int, unsigned long>;
205 using QueueItem = std::pair<WorkListUnit, QueuePriority>;
206
207 // Number of inserted nodes, used to emulate DFS ordering in the priority
208 // queue when insertions are equal.
209 unsigned long Counter = 0;
210
211 // Number of times a current location was reached.
212 VisitedTimesMap NumReached;
213
214 // The top item is the largest one.
215 llvm::PriorityQueue<QueueItem, std::vector<QueueItem>, llvm::less_second>
216 queue;
217
218public:
219 bool hasWork() const override {
220 return !queue.empty();
221 }
222
223 void enqueue(const WorkListUnit &U) override {
224 const ExplodedNode *N = U.getNode();
225 unsigned NumVisited = 0;
226 if (auto BE = N->getLocation().getAs<BlockEntrance>()) {
227 LocIdentifier LocId =
228 std::make_pair(x: BE->getBlock()->getBlockID(), y: N->getStackFrame());
229 NumVisited = NumReached[LocId]++;
230 }
231
232 queue.push(x: std::make_pair(x: U, y: std::make_pair(x: -NumVisited, y&: ++Counter)));
233 }
234
235 WorkListUnit dequeue() override {
236 QueueItem U = queue.top();
237 queue.pop();
238 return U.first;
239 }
240};
241} // namespace
242
243std::unique_ptr<WorkList> WorkList::makeUnexploredFirstPriorityQueue() {
244 return std::make_unique<UnexploredFirstPriorityQueue>();
245}
246
247namespace {
248class UnexploredFirstPriorityLocationQueue : public WorkList {
249 using LocIdentifier = const CFGBlock *;
250
251 // How many times each location was visited.
252 // Is signed because we negate it later in order to have a reversed
253 // comparison.
254 using VisitedTimesMap = llvm::DenseMap<LocIdentifier, int>;
255
256 // Compare by number of times the location was visited first (negated
257 // to prefer less often visited locations), then by insertion time (prefer
258 // expanding nodes inserted sooner first).
259 using QueuePriority = std::pair<int, unsigned long>;
260 using QueueItem = std::pair<WorkListUnit, QueuePriority>;
261
262 // Number of inserted nodes, used to emulate DFS ordering in the priority
263 // queue when insertions are equal.
264 unsigned long Counter = 0;
265
266 // Number of times a current location was reached.
267 VisitedTimesMap NumReached;
268
269 // The top item is the largest one.
270 llvm::PriorityQueue<QueueItem, std::vector<QueueItem>, llvm::less_second>
271 queue;
272
273public:
274 bool hasWork() const override {
275 return !queue.empty();
276 }
277
278 void enqueue(const WorkListUnit &U) override {
279 const ExplodedNode *N = U.getNode();
280 unsigned NumVisited = 0;
281 if (auto BE = N->getLocation().getAs<BlockEntrance>())
282 NumVisited = NumReached[BE->getBlock()]++;
283
284 queue.push(x: std::make_pair(x: U, y: std::make_pair(x: -NumVisited, y&: ++Counter)));
285 }
286
287 WorkListUnit dequeue() override {
288 QueueItem U = queue.top();
289 queue.pop();
290 return U.first;
291 }
292
293};
294
295}
296
297std::unique_ptr<WorkList> WorkList::makeUnexploredFirstPriorityLocationQueue() {
298 return std::make_unique<UnexploredFirstPriorityLocationQueue>();
299}
300