[InstCombine] Remove nusw handling in ptrtoint of gep fold (NFCI) (#118804)
[llvm-project.git] / clang / lib / StaticAnalyzer / Core / WorkList.cpp
blob7042a9020837a49ebd609d34f81a9b923b0a7e7a
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.
11 //===----------------------------------------------------------------------===//
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>
22 using namespace clang;
23 using namespace ento;
25 #define DEBUG_TYPE "WorkList"
27 STATISTIC(MaxQueueSize, "Maximum size of the worklist");
28 STATISTIC(MaxReachableSize, "Maximum size of auxiliary worklist set");
30 //===----------------------------------------------------------------------===//
31 // Worklist classes for exploration of reachable states.
32 //===----------------------------------------------------------------------===//
34 namespace {
36 class DFS : public WorkList {
37 SmallVector<WorkListUnit, 20> Stack;
39 public:
40 bool hasWork() const override {
41 return !Stack.empty();
44 void enqueue(const WorkListUnit& U) override {
45 Stack.push_back(U);
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;
56 class BFS : public WorkList {
57 std::deque<WorkListUnit> Queue;
59 public:
60 bool hasWork() const override {
61 return !Queue.empty();
64 void enqueue(const WorkListUnit& U) override {
65 Queue.push_back(U);
68 WorkListUnit dequeue() override {
69 WorkListUnit U = Queue.front();
70 Queue.pop_front();
71 return U;
75 } // namespace
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;
81 std::unique_ptr<WorkList> WorkList::makeDFS() {
82 return std::make_unique<DFS>();
85 std::unique_ptr<WorkList> WorkList::makeBFS() {
86 return std::make_unique<BFS>();
89 namespace {
91 class BFSBlockDFSContents : public WorkList {
92 std::deque<WorkListUnit> Queue;
93 SmallVector<WorkListUnit, 20> Stack;
95 public:
96 bool hasWork() const override {
97 return !Queue.empty() || !Stack.empty();
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);
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;
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;
124 } // namespace
126 std::unique_ptr<WorkList> WorkList::makeBFSBlockDFSContents() {
127 return std::make_unique<BFSBlockDFSContents>();
130 namespace {
132 class UnexploredFirstStack : public WorkList {
133 /// Stack of nodes known to have statements we have not traversed yet.
134 SmallVector<WorkListUnit, 20> StackUnexplored;
136 /// Stack of all other nodes.
137 SmallVector<WorkListUnit, 20> StackOthers;
139 using BlockID = unsigned;
140 using LocIdentifier = std::pair<BlockID, const StackFrameContext *>;
142 llvm::DenseSet<LocIdentifier> Reachable;
144 public:
145 bool hasWork() const override {
146 return !(StackUnexplored.empty() && StackOthers.empty());
149 void enqueue(const WorkListUnit &U) override {
150 const ExplodedNode *N = U.getNode();
151 auto BE = N->getLocation().getAs<BlockEntrance>();
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);
163 if (InsertInfo.second) {
164 StackUnexplored.push_back(U);
165 } else {
166 StackOthers.push_back(U);
169 MaxReachableSize.updateMax(Reachable.size());
170 MaxQueueSize.updateMax(StackUnexplored.size() + StackOthers.size());
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;
186 } // namespace
188 std::unique_ptr<WorkList> WorkList::makeUnexploredFirst() {
189 return std::make_unique<UnexploredFirstStack>();
192 namespace {
193 class UnexploredFirstPriorityQueue : public WorkList {
194 using BlockID = unsigned;
195 using LocIdentifier = std::pair<BlockID, const StackFrameContext *>;
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>;
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>;
208 // Number of inserted nodes, used to emulate DFS ordering in the priority
209 // queue when insertions are equal.
210 unsigned long Counter = 0;
212 // Number of times a current location was reached.
213 VisitedTimesMap NumReached;
215 // The top item is the largest one.
216 llvm::PriorityQueue<QueueItem, std::vector<QueueItem>, llvm::less_second>
217 queue;
219 public:
220 bool hasWork() const override {
221 return !queue.empty();
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 BE->getBlock()->getBlockID(),
230 N->getLocationContext()->getStackFrame());
231 NumVisited = NumReached[LocId]++;
234 queue.push(std::make_pair(U, std::make_pair(-NumVisited, ++Counter)));
237 WorkListUnit dequeue() override {
238 QueueItem U = queue.top();
239 queue.pop();
240 return U.first;
243 } // namespace
245 std::unique_ptr<WorkList> WorkList::makeUnexploredFirstPriorityQueue() {
246 return std::make_unique<UnexploredFirstPriorityQueue>();
249 namespace {
250 class UnexploredFirstPriorityLocationQueue : public WorkList {
251 using LocIdentifier = const CFGBlock *;
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>;
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>;
264 // Number of inserted nodes, used to emulate DFS ordering in the priority
265 // queue when insertions are equal.
266 unsigned long Counter = 0;
268 // Number of times a current location was reached.
269 VisitedTimesMap NumReached;
271 // The top item is the largest one.
272 llvm::PriorityQueue<QueueItem, std::vector<QueueItem>, llvm::less_second>
273 queue;
275 public:
276 bool hasWork() const override {
277 return !queue.empty();
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()]++;
286 queue.push(std::make_pair(U, std::make_pair(-NumVisited, ++Counter)));
289 WorkListUnit dequeue() override {
290 QueueItem U = queue.top();
291 queue.pop();
292 return U.first;
299 std::unique_ptr<WorkList> WorkList::makeUnexploredFirstPriorityLocationQueue() {
300 return std::make_unique<UnexploredFirstPriorityLocationQueue>();