WorkList.cpp source code [clang_source_code/lib/StaticAnalyzer/Core/WorkList.cpp]

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 "llvm/ADT/PriorityQueue.h"
15	#include "llvm/ADT/DenseSet.h"
16	#include "llvm/ADT/DenseMap.h"
17	#include "llvm/ADT/STLExtras.h"
18	#include "llvm/ADT/Statistic.h"
19	#include <deque>
20	#include <vector>
21
22	using namespace clang;
23	using namespace ento;
24
25	#define DEBUG_TYPE "WorkList"
26
27	STATISTIC(MaxQueueSize, "Maximum size of the worklist");
28	STATISTIC(MaxReachableSize, "Maximum size of auxiliary worklist set");
29
30	//===----------------------------------------------------------------------===//
31	// Worklist classes for exploration of reachable states.
32	//===----------------------------------------------------------------------===//
33
34	namespace {
35
36	class DFS : public WorkList {
37	SmallVector<WorkListUnit, 20> Stack;
38
39	public:
40	bool hasWork() const override {
41	return !Stack.empty();
42	}
43
44	void enqueue(const WorkListUnit& U) override {
45	Stack.push_back(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
56	class BFS : public WorkList {
57	std::deque<WorkListUnit> Queue;
58
59	public:
60	bool hasWork() const override {
61	return !Queue.empty();
62	}
63
64	void enqueue(const WorkListUnit& U) override {
65	Queue.push_back(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.
79	WorkList::~WorkList() = default;
80
81	std::unique_ptr<WorkList> WorkList::makeDFS() {
82	return llvm::make_unique<DFS>();
83	}
84
85	std::unique_ptr<WorkList> WorkList::makeBFS() {
86	return llvm::make_unique<BFS>();
87	}
88
89	namespace {
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(U);
103	else
104	Stack.push_back(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
126	std::unique_ptr<WorkList> WorkList::makeBFSBlockDFSContents() {
127	return llvm::make_unique<BFSBlockDFSContents>();
128	}
129
130	namespace {
131
132	class 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
144	public:
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(U);
157	} else {
158	LocIdentifier LocId = std::make_pair(
159	BE->getBlock()->getBlockID(),
160	N->getLocationContext()->getStackFrame());
161	auto InsertInfo = Reachable.insert(LocId);
162
163	if (InsertInfo.second) {
164	StackUnexplored.push_back(U);
165	} else {
166	StackOthers.push_back(U);
167	}
168	}
169	MaxReachableSize.updateMax(Reachable.size());
170	MaxQueueSize.updateMax(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
188	std::unique_ptr<WorkList> WorkList::makeUnexploredFirst() {
189	return llvm::make_unique<UnexploredFirstStack>();
190	}
191
192	namespace {
193	class 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	struct ExplorationComparator {
209	bool operator() (const QueueItem &LHS, const QueueItem &RHS) {
210	return LHS.second < RHS.second;
211	}
212	};
213
214	// Number of inserted nodes, used to emulate DFS ordering in the priority
215	// queue when insertions are equal.
216	unsigned long Counter = 0;
217
218	// Number of times a current location was reached.
219	VisitedTimesMap NumReached;
220
221	// The top item is the largest one.
222	llvm::PriorityQueue<QueueItem, std::vector<QueueItem>, ExplorationComparator>
223	queue;
224
225	public:
226	bool hasWork() const override {
227	return !queue.empty();
228	}
229
230	void enqueue(const WorkListUnit &U) override {
231	const ExplodedNode *N = U.getNode();
232	unsigned NumVisited = 0;
233	if (auto BE = N->getLocation().getAs<BlockEntrance>()) {
234	LocIdentifier LocId = std::make_pair(
235	BE->getBlock()->getBlockID(),
236	N->getLocationContext()->getStackFrame());
237	NumVisited = NumReached[LocId]++;
238	}
239
240	queue.push(std::make_pair(U, std::make_pair(-NumVisited, ++Counter)));
241	}
242
243	WorkListUnit dequeue() override {
244	QueueItem U = queue.top();
245	queue.pop();
246	return U.first;
247	}
248	};
249	} // namespace
250
251	std::unique_ptr<WorkList> WorkList::makeUnexploredFirstPriorityQueue() {
252	return llvm::make_unique<UnexploredFirstPriorityQueue>();
253	}
254
255	namespace {
256	class UnexploredFirstPriorityLocationQueue : public WorkList {
257	using LocIdentifier = const CFGBlock *;
258
259	// How many times each location was visited.
260	// Is signed because we negate it later in order to have a reversed
261	// comparison.
262	using VisitedTimesMap = llvm::DenseMap<LocIdentifier, int>;
263
264	// Compare by number of times the location was visited first (negated
265	// to prefer less often visited locations), then by insertion time (prefer
266	// expanding nodes inserted sooner first).
267	using QueuePriority = std::pair<int, unsigned long>;
268	using QueueItem = std::pair<WorkListUnit, QueuePriority>;
269
270	struct ExplorationComparator {
271	bool operator() (const QueueItem &LHS, const QueueItem &RHS) {
272	return LHS.second < RHS.second;
273	}
274	};
275
276	// Number of inserted nodes, used to emulate DFS ordering in the priority
277	// queue when insertions are equal.
278	unsigned long Counter = 0;
279
280	// Number of times a current location was reached.
281	VisitedTimesMap NumReached;
282
283	// The top item is the largest one.
284	llvm::PriorityQueue<QueueItem, std::vector<QueueItem>, ExplorationComparator>
285	queue;
286
287	public:
288	bool hasWork() const override {
289	return !queue.empty();
290	}
291
292	void enqueue(const WorkListUnit &U) override {
293	const ExplodedNode *N = U.getNode();
294	unsigned NumVisited = 0;
295	if (auto BE = N->getLocation().getAs<BlockEntrance>())
296	NumVisited = NumReached[BE->getBlock()]++;
297
298	queue.push(std::make_pair(U, std::make_pair(-NumVisited, ++Counter)));
299	}
300
301	WorkListUnit dequeue() override {
302	QueueItem U = queue.top();
303	queue.pop();
304	return U.first;
305	}
306
307	};
308
309	}
310
311	std::unique_ptr<WorkList> WorkList::makeUnexploredFirstPriorityLocationQueue() {
312	return llvm::make_unique<UnexploredFirstPriorityLocationQueue>();
313	}
314

clang::ento::WorkList::makeDFS

clang::ento::WorkList::makeBFS

clang::ento::WorkList::makeBFSBlockDFSContents

clang::ento::WorkList::makeUnexploredFirst

clang::ento::WorkList::makeUnexploredFirstPriorityQueue

clang::ento::WorkList::makeUnexploredFirstPriorityLocationQueue

Clang Project