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 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 std::make_unique<DFS>(); 83 } 84 85 std::unique_ptr<WorkList> WorkList::makeBFS() { 86 return std::make_unique<BFS>(); 87 } 88 89 namespace { 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 126 std::unique_ptr<WorkList> WorkList::makeBFSBlockDFSContents() { 127 return std::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 142 llvm::DenseSet<LocIdentifier> Reachable; 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(), 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 188 std::unique_ptr<WorkList> WorkList::makeUnexploredFirst() { 189 return std::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 // 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 219 public: 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 245 std::unique_ptr<WorkList> WorkList::makeUnexploredFirstPriorityQueue() { 246 return std::make_unique<UnexploredFirstPriorityQueue>(); 247 } 248 249 namespace { 250 class 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 275 public: 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 299 std::unique_ptr<WorkList> WorkList::makeUnexploredFirstPriorityLocationQueue() { 300 return std::make_unique<UnexploredFirstPriorityLocationQueue>(); 301 } 302