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