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
22using namespace clang;
23using namespace ento;
24
25#define DEBUG_TYPE "WorkList"
26
27STATISTIC(MaxQueueSize, "Maximum size of the worklist");
28STATISTIC(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(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(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(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
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(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
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          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
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(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
299std::unique_ptr<WorkList> WorkList::makeUnexploredFirstPriorityLocationQueue() {
300  return std::make_unique<UnexploredFirstPriorityLocationQueue>();
301}
302