Coverage Report

Created: 2020-11-24 06:42

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/StaticAnalyzer/Core/WorkList.cpp
Line
Count
Source (jump to first uncovered line)
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
138k
  bool hasWork() const override {
41
138k
    return !Stack.empty();
42
138k
  }
43
44
137k
  void enqueue(const WorkListUnit& U) override {
45
137k
    Stack.push_back(U);
46
137k
  }
47
48
137k
  WorkListUnit dequeue() override {
49
137k
    assert(!Stack.empty());
50
137k
    const WorkListUnit& U = Stack.back();
51
137k
    Stack.pop_back(); // This technically "invalidates" U, but we are fine.
52
137k
    return U;
53
137k
  }
54
};
55
56
class BFS : public WorkList {
57
  std::deque<WorkListUnit> Queue;
58
59
public:
60
0
  bool hasWork() const override {
61
0
    return !Queue.empty();
62
0
  }
63
64
0
  void enqueue(const WorkListUnit& U) override {
65
0
    Queue.push_back(U);
66
0
  }
67
68
0
  WorkListUnit dequeue() override {
69
0
    WorkListUnit U = Queue.front();
70
0
    Queue.pop_front();
71
0
    return U;
72
0
  }
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
13.7k
WorkList::~WorkList() = default;
80
81
311
std::unique_ptr<WorkList> WorkList::makeDFS() {
82
311
  return std::make_unique<DFS>();
83
311
}
84
85
0
std::unique_ptr<WorkList> WorkList::makeBFS() {
86
0
  return std::make_unique<BFS>();
87
0
}
88
89
namespace {
90
91
  class BFSBlockDFSContents : public WorkList {
92
    std::deque<WorkListUnit> Queue;
93
    SmallVector<WorkListUnit, 20> Stack;
94
95
  public:
96
0
    bool hasWork() const override {
97
0
      return !Queue.empty() || !Stack.empty();
98
0
    }
99
100
0
    void enqueue(const WorkListUnit& U) override {
101
0
      if (U.getNode()->getLocation().getAs<BlockEntrance>())
102
0
        Queue.push_front(U);
103
0
      else
104
0
        Stack.push_back(U);
105
0
    }
106
107
0
    WorkListUnit dequeue() override {
108
      // Process all basic blocks to completion.
109
0
      if (!Stack.empty()) {
110
0
        const WorkListUnit& U = Stack.back();
111
0
        Stack.pop_back(); // This technically "invalidates" U, but we are fine.
112
0
        return U;
113
0
      }
114
115
0
      assert(!Queue.empty());
116
      // Don't use const reference.  The subsequent pop_back() might make it
117
      // unsafe.
118
0
      WorkListUnit U = Queue.front();
119
0
      Queue.pop_front();
120
0
      return U;
121
0
    }
122
  };
123
124
} // namespace
125
126
0
std::unique_ptr<WorkList> WorkList::makeBFSBlockDFSContents() {
127
0
  return std::make_unique<BFSBlockDFSContents>();
128
0
}
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
448
  bool hasWork() const override {
146
448
    return !(StackUnexplored.empty() && 
StackOthers.empty()69
);
147
448
  }
148
149
440
  void enqueue(const WorkListUnit &U) override {
150
440
    const ExplodedNode *N = U.getNode();
151
440
    auto BE = N->getLocation().getAs<BlockEntrance>();
152
153
440
    if (!BE) {
154
      // Assume the choice of the order of the preceding block entrance was
155
      // correct.
156
348
      StackUnexplored.push_back(U);
157
92
    } else {
158
92
      LocIdentifier LocId = std::make_pair(
159
92
          BE->getBlock()->getBlockID(),
160
92
          N->getLocationContext()->getStackFrame());
161
92
      auto InsertInfo = Reachable.insert(LocId);
162
163
92
      if (InsertInfo.second) {
164
31
        StackUnexplored.push_back(U);
165
61
      } else {
166
61
        StackOthers.push_back(U);
167
61
      }
168
92
    }
169
440
    MaxReachableSize.updateMax(Reachable.size());
170
440
    MaxQueueSize.updateMax(StackUnexplored.size() + StackOthers.size());
171
440
  }
172
173
440
  WorkListUnit dequeue() override {
174
440
    if (!StackUnexplored.empty()) {
175
379
      WorkListUnit &U = StackUnexplored.back();
176
379
      StackUnexplored.pop_back();
177
379
      return U;
178
61
    } else {
179
61
      WorkListUnit &U = StackOthers.back();
180
61
      StackOthers.pop_back();
181
61
      return U;
182
61
    }
183
440
  }
184
};
185
186
} // namespace
187
188
4
std::unique_ptr<WorkList> WorkList::makeUnexploredFirst() {
189
4
  return std::make_unique<UnexploredFirstStack>();
190
4
}
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
16.2M
    bool operator() (const QueueItem &LHS, const QueueItem &RHS) {
210
16.2M
      return LHS.second < RHS.second;
211
16.2M
    }
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
1.26M
  bool hasWork() const override {
227
1.26M
    return !queue.empty();
228
1.26M
  }
229
230
1.25M
  void enqueue(const WorkListUnit &U) override {
231
1.25M
    const ExplodedNode *N = U.getNode();
232
1.25M
    unsigned NumVisited = 0;
233
1.25M
    if (auto BE = N->getLocation().getAs<BlockEntrance>()) {
234
122k
      LocIdentifier LocId = std::make_pair(
235
122k
          BE->getBlock()->getBlockID(),
236
122k
          N->getLocationContext()->getStackFrame());
237
122k
      NumVisited = NumReached[LocId]++;
238
122k
    }
239
240
1.25M
    queue.push(std::make_pair(U, std::make_pair(-NumVisited, ++Counter)));
241
1.25M
  }
242
243
1.23M
  WorkListUnit dequeue() override {
244
1.23M
    QueueItem U = queue.top();
245
1.23M
    queue.pop();
246
1.23M
    return U.first;
247
1.23M
  }
248
};
249
} // namespace
250
251
13.3k
std::unique_ptr<WorkList> WorkList::makeUnexploredFirstPriorityQueue() {
252
13.3k
  return std::make_unique<UnexploredFirstPriorityQueue>();
253
13.3k
}
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
0
    bool operator() (const QueueItem &LHS, const QueueItem &RHS) {
272
0
      return LHS.second < RHS.second;
273
0
    }
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
0
  bool hasWork() const override {
289
0
    return !queue.empty();
290
0
  }
291
292
0
  void enqueue(const WorkListUnit &U) override {
293
0
    const ExplodedNode *N = U.getNode();
294
0
    unsigned NumVisited = 0;
295
0
    if (auto BE = N->getLocation().getAs<BlockEntrance>())
296
0
      NumVisited = NumReached[BE->getBlock()]++;
297
298
0
    queue.push(std::make_pair(U, std::make_pair(-NumVisited, ++Counter)));
299
0
  }
300
301
0
  WorkListUnit dequeue() override {
302
0
    QueueItem U = queue.top();
303
0
    queue.pop();
304
0
    return U.first;
305
0
  }
306
307
};
308
309
}
310
311
0
std::unique_ptr<WorkList> WorkList::makeUnexploredFirstPriorityLocationQueue() {
312
0
  return std::make_unique<UnexploredFirstPriorityLocationQueue>();
313
0
}