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 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 225public: 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(), 236 N->getLocationContext()->getStackFrame()); 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 251std::unique_ptr<WorkList> WorkList::makeUnexploredFirstPriorityQueue() { 252 return std::make_unique<UnexploredFirstPriorityQueue>(); 253} 254 255namespace { 256class 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 287public: 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 311std::unique_ptr<WorkList> WorkList::makeUnexploredFirstPriorityLocationQueue() { 312 return std::make_unique<UnexploredFirstPriorityLocationQueue>(); 313} 314