clang  9.0.0svn
WorkList.cpp
Go to the documentation of this file.
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 
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 {
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;
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 
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(),
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(),
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 
312  return llvm::make_unique<UnexploredFirstPriorityLocationQueue>();
313 }
bool empty() const
Definition: CFG.h:713
static std::unique_ptr< WorkList > makeUnexploredFirstPriorityQueue()
Definition: WorkList.cpp:251
static std::unique_ptr< WorkList > makeDFS()
Definition: WorkList.cpp:81
const LocationContext * getLocationContext() const
static std::unique_ptr< WorkList > makeBFS()
Definition: WorkList.cpp:85
Represents a single basic block in a source-level CFG.
Definition: CFG.h:551
STATISTIC(MaxQueueSize, "Maximum size of the worklist")
ExplodedNode * getNode() const
Returns the node associated with the worklist unit.
Definition: WorkList.h:48
static std::unique_ptr< WorkList > makeUnexploredFirstPriorityLocationQueue()
Definition: WorkList.cpp:311
ProgramPoint getLocation() const
getLocation - Returns the edge associated with the given node.
static std::unique_ptr< WorkList > makeBFSBlockDFSContents()
Definition: WorkList.cpp:126
Dataflow Directional Tag Classes.
const StackFrameContext * getStackFrame() const
static std::unique_ptr< WorkList > makeUnexploredFirst()
Definition: WorkList.cpp:188
Optional< T > getAs() const
Convert to the specified ProgramPoint type, returning None if this ProgramPoint is not of the desired...
Definition: ProgramPoint.h:151