clang/lib/StaticAnalyzer/Core/WorkList.cpp

   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 }