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 std::make_unique<DFS>();
83 }
84 
85 std::unique_ptr<WorkList> WorkList::makeBFS() {
86   return std::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 std::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 std::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   // 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 
219 public:
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           BE->getBlock()->getBlockID(),
230           N->getLocationContext()->getStackFrame());
231       NumVisited = NumReached[LocId]++;
232     }
233 
234     queue.push(std::make_pair(U, std::make_pair(-NumVisited, ++Counter)));
235   }
236 
237   WorkListUnit dequeue() override {
238     QueueItem U = queue.top();
239     queue.pop();
240     return U.first;
241   }
242 };
243 } // namespace
244 
245 std::unique_ptr<WorkList> WorkList::makeUnexploredFirstPriorityQueue() {
246   return std::make_unique<UnexploredFirstPriorityQueue>();
247 }
248 
249 namespace {
250 class 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 
275 public:
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(std::make_pair(U, std::make_pair(-NumVisited, ++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 
299 std::unique_ptr<WorkList> WorkList::makeUnexploredFirstPriorityLocationQueue() {
300   return std::make_unique<UnexploredFirstPriorityLocationQueue>();
301 }
302