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 StackFrameContext *>;
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 = std::make_pair(
159 x: BE->getBlock()->getBlockID(),
160 y: N->getLocationContext()->getStackFrame());
161 auto InsertInfo = Reachable.insert(V: LocId);
162
163 if (InsertInfo.second) {
164 StackUnexplored.push_back(Elt: U);
165 } else {
166 StackOthers.push_back(Elt: U);
167 }
168 }
169 MaxReachableSize.updateMax(Value: Reachable.size());
170 MaxQueueSize.updateMax(Value: StackUnexplored.size() + StackOthers.size());
171 }
172
173 WorkListUnit dequeue() override {
174 if (!StackUnexplored.empty()) {
175 WorkListUnit &U = StackUnexplored.back();
176 StackUnexplored.pop_back();
177 return U;
178 } else {
179 WorkListUnit &U = StackOthers.back();
180 StackOthers.pop_back();
181 return U;
182 }
183 }
184};
185
186} // namespace
187
188std::unique_ptr<WorkList> WorkList::makeUnexploredFirst() {
189 return std::make_unique<UnexploredFirstStack>();
190}
191
192namespace {
193class UnexploredFirstPriorityQueue : public WorkList {
194 using BlockID = unsigned;
195 using LocIdentifier = std::pair<BlockID, const StackFrameContext *>;
196
197 // How many times each location was visited.
198 // Is signed because we negate it later in order to have a reversed
199 // comparison.
200 using VisitedTimesMap = llvm::DenseMap<LocIdentifier, int>;
201
202 // Compare by number of times the location was visited first (negated
203 // to prefer less often visited locations), then by insertion time (prefer
204 // expanding nodes inserted sooner first).
205 using QueuePriority = std::pair<int, unsigned long>;
206 using QueueItem = std::pair<WorkListUnit, QueuePriority>;
207
208 // Number of inserted nodes, used to emulate DFS ordering in the priority
209 // queue when insertions are equal.
210 unsigned long Counter = 0;
211
212 // Number of times a current location was reached.
213 VisitedTimesMap NumReached;
214
215 // The top item is the largest one.
216 llvm::PriorityQueue<QueueItem, std::vector<QueueItem>, llvm::less_second>
217 queue;
218
219public:
220 bool hasWork() const override {
221 return !queue.empty();
222 }
223
224 void enqueue(const WorkListUnit &U) override {
225 const ExplodedNode *N = U.getNode();
226 unsigned NumVisited = 0;
227 if (auto BE = N->getLocation().getAs<BlockEntrance>()) {
228 LocIdentifier LocId = std::make_pair(
229 x: BE->getBlock()->getBlockID(),
230 y: N->getLocationContext()->getStackFrame());
231 NumVisited = NumReached[LocId]++;
232 }
233
234 queue.push(x: std::make_pair(x: U, y: std::make_pair(x: -NumVisited, y&: ++Counter)));
235 }
236
237 WorkListUnit dequeue() override {
238 QueueItem U = queue.top();
239 queue.pop();
240 return U.first;
241 }
242};
243} // namespace
244
245std::unique_ptr<WorkList> WorkList::makeUnexploredFirstPriorityQueue() {
246 return std::make_unique<UnexploredFirstPriorityQueue>();
247}
248
249namespace {
250class UnexploredFirstPriorityLocationQueue : public WorkList {
251 using LocIdentifier = const CFGBlock *;
252
253 // How many times each location was visited.
254 // Is signed because we negate it later in order to have a reversed
255 // comparison.
256 using VisitedTimesMap = llvm::DenseMap<LocIdentifier, int>;
257
258 // Compare by number of times the location was visited first (negated
259 // to prefer less often visited locations), then by insertion time (prefer
260 // expanding nodes inserted sooner first).
261 using QueuePriority = std::pair<int, unsigned long>;
262 using QueueItem = std::pair<WorkListUnit, QueuePriority>;
263
264 // Number of inserted nodes, used to emulate DFS ordering in the priority
265 // queue when insertions are equal.
266 unsigned long Counter = 0;
267
268 // Number of times a current location was reached.
269 VisitedTimesMap NumReached;
270
271 // The top item is the largest one.
272 llvm::PriorityQueue<QueueItem, std::vector<QueueItem>, llvm::less_second>
273 queue;
274
275public:
276 bool hasWork() const override {
277 return !queue.empty();
278 }
279
280 void enqueue(const WorkListUnit &U) override {
281 const ExplodedNode *N = U.getNode();
282 unsigned NumVisited = 0;
283 if (auto BE = N->getLocation().getAs<BlockEntrance>())
284 NumVisited = NumReached[BE->getBlock()]++;
285
286 queue.push(x: std::make_pair(x: U, y: std::make_pair(x: -NumVisited, y&: ++Counter)));
287 }
288
289 WorkListUnit dequeue() override {
290 QueueItem U = queue.top();
291 queue.pop();
292 return U.first;
293 }
294
295};
296
297}
298
299std::unique_ptr<WorkList> WorkList::makeUnexploredFirstPriorityLocationQueue() {
300 return std::make_unique<UnexploredFirstPriorityLocationQueue>();
301}
302