contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/WorkList.cpp

   1 //===- WorkList.cpp - Analyzer work-list implementation--------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Defines different worklist implementations for the static analyzer.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h"
  15 #include "llvm/ADT/PriorityQueue.h"
  16 #include "llvm/ADT/DenseSet.h"
  17 #include "llvm/ADT/DenseMap.h"
  18 #include "llvm/ADT/STLExtras.h"
  19 #include "llvm/ADT/Statistic.h"
  20 #include <deque>
  21 #include <vector>
  22
  23 using namespace clang;
  24 using namespace ento;
  25
  26 #define DEBUG_TYPE "WorkList"
  27
  28 STATISTIC(MaxQueueSize, "Maximum size of the worklist");
  29 STATISTIC(MaxReachableSize, "Maximum size of auxiliary worklist set");
  30
  31 //===----------------------------------------------------------------------===//
  32 // Worklist classes for exploration of reachable states.
  33 //===----------------------------------------------------------------------===//
  34
  35 namespace {
  36
  37 class DFS : public WorkList {
  38   SmallVector<WorkListUnit, 20> Stack;
  39
  40 public:
  41   bool hasWork() const override {
  42     return !Stack.empty();
  43   }
  44
  45   void enqueue(const WorkListUnit& U) override {
  46     Stack.push_back(U);
  47   }
  48
  49   WorkListUnit dequeue() override {
  50     assert(!Stack.empty());
  51     const WorkListUnit& U = Stack.back();
  52     Stack.pop_back(); // This technically "invalidates" U, but we are fine.
  53     return U;
  54   }
  55 };
  56
  57 class BFS : public WorkList {
  58   std::deque<WorkListUnit> Queue;
  59
  60 public:
  61   bool hasWork() const override {
  62     return !Queue.empty();
  63   }
  64
  65   void enqueue(const WorkListUnit& U) override {
  66     Queue.push_back(U);
  67   }
  68
  69   WorkListUnit dequeue() override {
  70     WorkListUnit U = Queue.front();
  71     Queue.pop_front();
  72     return U;
  73   }
  74 };
  75
  76 } // namespace
  77
  78 // Place the dstor for WorkList here because it contains virtual member
  79 // functions, and we the code for the dstor generated in one compilation unit.
  80 WorkList::~WorkList() = default;
  81
  82 std::unique_ptr<WorkList> WorkList::makeDFS() {
  83   return llvm::make_unique<DFS>();
  84 }
  85
  86 std::unique_ptr<WorkList> WorkList::makeBFS() {
  87   return llvm::make_unique<BFS>();
  88 }
  89
  90 namespace {
  91
  92   class BFSBlockDFSContents : public WorkList {
  93     std::deque<WorkListUnit> Queue;
  94     SmallVector<WorkListUnit, 20> Stack;
  95
  96   public:
  97     bool hasWork() const override {
  98       return !Queue.empty() || !Stack.empty();
  99     }
 100
 101     void enqueue(const WorkListUnit& U) override {
 102       if (U.getNode()->getLocation().getAs<BlockEntrance>())
 103         Queue.push_front(U);
 104       else
 105         Stack.push_back(U);
 106     }
 107
 108     WorkListUnit dequeue() override {
 109       // Process all basic blocks to completion.
 110       if (!Stack.empty()) {
 111         const WorkListUnit& U = Stack.back();
 112         Stack.pop_back(); // This technically "invalidates" U, but we are fine.
 113         return U;
 114       }
 115
 116       assert(!Queue.empty());
 117       // Don't use const reference.  The subsequent pop_back() might make it
 118       // unsafe.
 119       WorkListUnit U = Queue.front();
 120       Queue.pop_front();
 121       return U;
 122     }
 123   };
 124
 125 } // namespace
 126
 127 std::unique_ptr<WorkList> WorkList::makeBFSBlockDFSContents() {
 128   return llvm::make_unique<BFSBlockDFSContents>();
 129 }
 130
 131 namespace {
 132
 133 class UnexploredFirstStack : public WorkList {
 134   /// Stack of nodes known to have statements we have not traversed yet.
 135   SmallVector<WorkListUnit, 20> StackUnexplored;
 136
 137   /// Stack of all other nodes.
 138   SmallVector<WorkListUnit, 20> StackOthers;
 139
 140   using BlockID = unsigned;
 141   using LocIdentifier = std::pair<BlockID, const StackFrameContext *>;
 142
 143   llvm::DenseSet<LocIdentifier> Reachable;
 144
 145 public:
 146   bool hasWork() const override {
 147     return !(StackUnexplored.empty() && StackOthers.empty());
 148   }
 149
 150   void enqueue(const WorkListUnit &U) override {
 151     const ExplodedNode *N = U.getNode();
 152     auto BE = N->getLocation().getAs<BlockEntrance>();
 153
 154     if (!BE) {
 155       // Assume the choice of the order of the preceeding block entrance was
 156       // correct.
 157       StackUnexplored.push_back(U);
 158     } else {
 159       LocIdentifier LocId = std::make_pair(
 160           BE->getBlock()->getBlockID(),
 161           N->getLocationContext()->getStackFrame());
 162       auto InsertInfo = Reachable.insert(LocId);
 163
 164       if (InsertInfo.second) {
 165         StackUnexplored.push_back(U);
 166       } else {
 167         StackOthers.push_back(U);
 168       }
 169     }
 170     MaxReachableSize.updateMax(Reachable.size());
 171     MaxQueueSize.updateMax(StackUnexplored.size() + StackOthers.size());
 172   }
 173
 174   WorkListUnit dequeue() override {
 175     if (!StackUnexplored.empty()) {
 176       WorkListUnit &U = StackUnexplored.back();
 177       StackUnexplored.pop_back();
 178       return U;
 179     } else {
 180       WorkListUnit &U = StackOthers.back();
 181       StackOthers.pop_back();
 182       return U;
 183     }
 184   }
 185 };
 186
 187 } // namespace
 188
 189 std::unique_ptr<WorkList> WorkList::makeUnexploredFirst() {
 190   return llvm::make_unique<UnexploredFirstStack>();
 191 }
 192
 193 namespace {
 194 class UnexploredFirstPriorityQueue : public WorkList {
 195   using BlockID = unsigned;
 196   using LocIdentifier = std::pair<BlockID, const StackFrameContext *>;
 197
 198   // How many times each location was visited.
 199   // Is signed because we negate it later in order to have a reversed
 200   // comparison.
 201   using VisitedTimesMap = llvm::DenseMap<LocIdentifier, int>;
 202
 203   // Compare by number of times the location was visited first (negated
 204   // to prefer less often visited locations), then by insertion time (prefer
 205   // expanding nodes inserted sooner first).
 206   using QueuePriority = std::pair<int, unsigned long>;
 207   using QueueItem = std::pair<WorkListUnit, QueuePriority>;
 208
 209   struct ExplorationComparator {
 210     bool operator() (const QueueItem &LHS, const QueueItem &RHS) {
 211       return LHS.second < RHS.second;
 212     }
 213   };
 214
 215   // Number of inserted nodes, used to emulate DFS ordering in the priority
 216   // queue when insertions are equal.
 217   unsigned long Counter = 0;
 218
 219   // Number of times a current location was reached.
 220   VisitedTimesMap NumReached;
 221
 222   // The top item is the largest one.
 223   llvm::PriorityQueue<QueueItem, std::vector<QueueItem>, ExplorationComparator>
 224       queue;
 225
 226 public:
 227   bool hasWork() const override {
 228     return !queue.empty();
 229   }
 230
 231   void enqueue(const WorkListUnit &U) override {
 232     const ExplodedNode *N = U.getNode();
 233     unsigned NumVisited = 0;
 234     if (auto BE = N->getLocation().getAs<BlockEntrance>()) {
 235       LocIdentifier LocId = std::make_pair(
 236           BE->getBlock()->getBlockID(),
 237           N->getLocationContext()->getStackFrame());
 238       NumVisited = NumReached[LocId]++;
 239     }
 240
 241     queue.push(std::make_pair(U, std::make_pair(-NumVisited, ++Counter)));
 242   }
 243
 244   WorkListUnit dequeue() override {
 245     QueueItem U = queue.top();
 246     queue.pop();
 247     return U.first;
 248   }
 249 };
 250 } // namespace
 251
 252 std::unique_ptr<WorkList> WorkList::makeUnexploredFirstPriorityQueue() {
 253   return llvm::make_unique<UnexploredFirstPriorityQueue>();
 254 }