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

   1 //=-- ExplodedGraph.cpp - Local, Path-Sens. "Exploded Graph" -*- C++ -*------=//
   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 //  This file defines the template classes ExplodedNode and ExplodedGraph,
  11 //  which represent a path-sensitive, intra-procedural "exploded graph."
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
  16 #include "clang/AST/ParentMap.h"
  17 #include "clang/AST/Stmt.h"
  18 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
  19 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
  20 #include "llvm/ADT/DenseMap.h"
  21 #include "llvm/ADT/DenseSet.h"
  22 #include "llvm/ADT/SmallVector.h"
  23 #include "llvm/ADT/Statistic.h"
  24 #include <vector>
  25
  26 using namespace clang;
  27 using namespace ento;
  28
  29 //===----------------------------------------------------------------------===//
  30 // Node auditing.
  31 //===----------------------------------------------------------------------===//
  32
  33 // An out of line virtual method to provide a home for the class vtable.
  34 ExplodedNode::Auditor::~Auditor() {}
  35
  36 #ifndef NDEBUG
  37 static ExplodedNode::Auditor* NodeAuditor = nullptr;
  38 #endif
  39
  40 void ExplodedNode::SetAuditor(ExplodedNode::Auditor* A) {
  41 #ifndef NDEBUG
  42   NodeAuditor = A;
  43 #endif
  44 }
  45
  46 //===----------------------------------------------------------------------===//
  47 // Cleanup.
  48 //===----------------------------------------------------------------------===//
  49
  50 ExplodedGraph::ExplodedGraph()
  51   : NumNodes(0), ReclaimNodeInterval(0) {}
  52
  53 ExplodedGraph::~ExplodedGraph() {}
  54
  55 //===----------------------------------------------------------------------===//
  56 // Node reclamation.
  57 //===----------------------------------------------------------------------===//
  58
  59 bool ExplodedGraph::isInterestingLValueExpr(const Expr *Ex) {
  60   if (!Ex->isLValue())
  61     return false;
  62   return isa<DeclRefExpr>(Ex) ||
  63          isa<MemberExpr>(Ex) ||
  64          isa<ObjCIvarRefExpr>(Ex);
  65 }
  66
  67 bool ExplodedGraph::shouldCollect(const ExplodedNode *node) {
  68   // First, we only consider nodes for reclamation of the following
  69   // conditions apply:
  70   //
  71   // (1) 1 predecessor (that has one successor)
  72   // (2) 1 successor (that has one predecessor)
  73   //
  74   // If a node has no successor it is on the "frontier", while a node
  75   // with no predecessor is a root.
  76   //
  77   // After these prerequisites, we discard all "filler" nodes that
  78   // are used only for intermediate processing, and are not essential
  79   // for analyzer history:
  80   //
  81   // (a) PreStmtPurgeDeadSymbols
  82   //
  83   // We then discard all other nodes where *all* of the following conditions
  84   // apply:
  85   //
  86   // (3) The ProgramPoint is for a PostStmt, but not a PostStore.
  87   // (4) There is no 'tag' for the ProgramPoint.
  88   // (5) The 'store' is the same as the predecessor.
  89   // (6) The 'GDM' is the same as the predecessor.
  90   // (7) The LocationContext is the same as the predecessor.
  91   // (8) Expressions that are *not* lvalue expressions.
  92   // (9) The PostStmt isn't for a non-consumed Stmt or Expr.
  93   // (10) The successor is neither a CallExpr StmtPoint nor a CallEnter or
  94   //      PreImplicitCall (so that we would be able to find it when retrying a
  95   //      call with no inlining).
  96   // FIXME: It may be safe to reclaim PreCall and PostCall nodes as well.
  97
  98   // Conditions 1 and 2.
  99   if (node->pred_size() != 1 || node->succ_size() != 1)
 100     return false;
 101
 102   const ExplodedNode *pred = *(node->pred_begin());
 103   if (pred->succ_size() != 1)
 104     return false;
 105
 106   const ExplodedNode *succ = *(node->succ_begin());
 107   if (succ->pred_size() != 1)
 108     return false;
 109
 110   // Now reclaim any nodes that are (by definition) not essential to
 111   // analysis history and are not consulted by any client code.
 112   ProgramPoint progPoint = node->getLocation();
 113   if (progPoint.getAs<PreStmtPurgeDeadSymbols>())
 114     return !progPoint.getTag();
 115
 116   // Condition 3.
 117   if (!progPoint.getAs<PostStmt>() || progPoint.getAs<PostStore>())
 118     return false;
 119
 120   // Condition 4.
 121   if (progPoint.getTag())
 122     return false;
 123
 124   // Conditions 5, 6, and 7.
 125   ProgramStateRef state = node->getState();
 126   ProgramStateRef pred_state = pred->getState();
 127   if (state->store != pred_state->store || state->GDM != pred_state->GDM ||
 128       progPoint.getLocationContext() != pred->getLocationContext())
 129     return false;
 130
 131   // All further checks require expressions. As per #3, we know that we have
 132   // a PostStmt.
 133   const Expr *Ex = dyn_cast<Expr>(progPoint.castAs<PostStmt>().getStmt());
 134   if (!Ex)
 135     return false;
 136
 137   // Condition 8.
 138   // Do not collect nodes for "interesting" lvalue expressions since they are
 139   // used extensively for generating path diagnostics.
 140   if (isInterestingLValueExpr(Ex))
 141     return false;
 142
 143   // Condition 9.
 144   // Do not collect nodes for non-consumed Stmt or Expr to ensure precise
 145   // diagnostic generation; specifically, so that we could anchor arrows
 146   // pointing to the beginning of statements (as written in code).
 147   ParentMap &PM = progPoint.getLocationContext()->getParentMap();
 148   if (!PM.isConsumedExpr(Ex))
 149     return false;
 150
 151   // Condition 10.
 152   const ProgramPoint SuccLoc = succ->getLocation();
 153   if (Optional<StmtPoint> SP = SuccLoc.getAs<StmtPoint>())
 154     if (CallEvent::isCallStmt(SP->getStmt()))
 155       return false;
 156
 157   // Condition 10, continuation.
 158   if (SuccLoc.getAs<CallEnter>() || SuccLoc.getAs<PreImplicitCall>())
 159     return false;
 160
 161   return true;
 162 }
 163
 164 void ExplodedGraph::collectNode(ExplodedNode *node) {
 165   // Removing a node means:
 166   // (a) changing the predecessors successor to the successor of this node
 167   // (b) changing the successors predecessor to the predecessor of this node
 168   // (c) Putting 'node' onto freeNodes.
 169   assert(node->pred_size() == 1 || node->succ_size() == 1);
 170   ExplodedNode *pred = *(node->pred_begin());
 171   ExplodedNode *succ = *(node->succ_begin());
 172   pred->replaceSuccessor(succ);
 173   succ->replacePredecessor(pred);
 174   FreeNodes.push_back(node);
 175   Nodes.RemoveNode(node);
 176   --NumNodes;
 177   node->~ExplodedNode();
 178 }
 179
 180 void ExplodedGraph::reclaimRecentlyAllocatedNodes() {
 181   if (ChangedNodes.empty())
 182     return;
 183
 184   // Only periodically reclaim nodes so that we can build up a set of
 185   // nodes that meet the reclamation criteria.  Freshly created nodes
 186   // by definition have no successor, and thus cannot be reclaimed (see below).
 187   assert(ReclaimCounter > 0);
 188   if (--ReclaimCounter != 0)
 189     return;
 190   ReclaimCounter = ReclaimNodeInterval;
 191
 192   for (NodeVector::iterator it = ChangedNodes.begin(), et = ChangedNodes.end();
 193        it != et; ++it) {
 194     ExplodedNode *node = *it;
 195     if (shouldCollect(node))
 196       collectNode(node);
 197   }
 198   ChangedNodes.clear();
 199 }
 200
 201 //===----------------------------------------------------------------------===//
 202 // ExplodedNode.
 203 //===----------------------------------------------------------------------===//
 204
 205 // An NodeGroup's storage type is actually very much like a TinyPtrVector:
 206 // it can be either a pointer to a single ExplodedNode, or a pointer to a
 207 // BumpVector allocated with the ExplodedGraph's allocator. This allows the
 208 // common case of single-node NodeGroups to be implemented with no extra memory.
 209 //
 210 // Consequently, each of the NodeGroup methods have up to four cases to handle:
 211 // 1. The flag is set and this group does not actually contain any nodes.
 212 // 2. The group is empty, in which case the storage value is null.
 213 // 3. The group contains a single node.
 214 // 4. The group contains more than one node.
 215 typedef BumpVector<ExplodedNode *> ExplodedNodeVector;
 216 typedef llvm::PointerUnion<ExplodedNode *, ExplodedNodeVector *> GroupStorage;
 217
 218 void ExplodedNode::addPredecessor(ExplodedNode *V, ExplodedGraph &G) {
 219   assert (!V->isSink());
 220   Preds.addNode(V, G);
 221   V->Succs.addNode(this, G);
 222 #ifndef NDEBUG
 223   if (NodeAuditor) NodeAuditor->AddEdge(V, this);
 224 #endif
 225 }
 226
 227 void ExplodedNode::NodeGroup::replaceNode(ExplodedNode *node) {
 228   assert(!getFlag());
 229
 230   GroupStorage &Storage = reinterpret_cast<GroupStorage&>(P);
 231   assert(Storage.is<ExplodedNode *>());
 232   Storage = node;
 233   assert(Storage.is<ExplodedNode *>());
 234 }
 235
 236 void ExplodedNode::NodeGroup::addNode(ExplodedNode *N, ExplodedGraph &G) {
 237   assert(!getFlag());
 238
 239   GroupStorage &Storage = reinterpret_cast<GroupStorage&>(P);
 240   if (Storage.isNull()) {
 241     Storage = N;
 242     assert(Storage.is<ExplodedNode *>());
 243     return;
 244   }
 245
 246   ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>();
 247
 248   if (!V) {
 249     // Switch from single-node to multi-node representation.
 250     ExplodedNode *Old = Storage.get<ExplodedNode *>();
 251
 252     BumpVectorContext &Ctx = G.getNodeAllocator();
 253     V = G.getAllocator().Allocate<ExplodedNodeVector>();
 254     new (V) ExplodedNodeVector(Ctx, 4);
 255     V->push_back(Old, Ctx);
 256
 257     Storage = V;
 258     assert(!getFlag());
 259     assert(Storage.is<ExplodedNodeVector *>());
 260   }
 261
 262   V->push_back(N, G.getNodeAllocator());
 263 }
 264
 265 unsigned ExplodedNode::NodeGroup::size() const {
 266   if (getFlag())
 267     return 0;
 268
 269   const GroupStorage &Storage = reinterpret_cast<const GroupStorage &>(P);
 270   if (Storage.isNull())
 271     return 0;
 272   if (ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>())
 273     return V->size();
 274   return 1;
 275 }
 276
 277 ExplodedNode * const *ExplodedNode::NodeGroup::begin() const {
 278   if (getFlag())
 279     return nullptr;
 280
 281   const GroupStorage &Storage = reinterpret_cast<const GroupStorage &>(P);
 282   if (Storage.isNull())
 283     return nullptr;
 284   if (ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>())
 285     return V->begin();
 286   return Storage.getAddrOfPtr1();
 287 }
 288
 289 ExplodedNode * const *ExplodedNode::NodeGroup::end() const {
 290   if (getFlag())
 291     return nullptr;
 292
 293   const GroupStorage &Storage = reinterpret_cast<const GroupStorage &>(P);
 294   if (Storage.isNull())
 295     return nullptr;
 296   if (ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>())
 297     return V->end();
 298   return Storage.getAddrOfPtr1() + 1;
 299 }
 300
 301 ExplodedNode *ExplodedGraph::getNode(const ProgramPoint &L,
 302                                      ProgramStateRef State,
 303                                      bool IsSink,
 304                                      bool* IsNew) {
 305   // Profile 'State' to determine if we already have an existing node.
 306   llvm::FoldingSetNodeID profile;
 307   void *InsertPos = nullptr;
 308
 309   NodeTy::Profile(profile, L, State, IsSink);
 310   NodeTy* V = Nodes.FindNodeOrInsertPos(profile, InsertPos);
 311
 312   if (!V) {
 313     if (!FreeNodes.empty()) {
 314       V = FreeNodes.back();
 315       FreeNodes.pop_back();
 316     }
 317     else {
 318       // Allocate a new node.
 319       V = (NodeTy*) getAllocator().Allocate<NodeTy>();
 320     }
 321
 322     new (V) NodeTy(L, State, IsSink);
 323
 324     if (ReclaimNodeInterval)
 325       ChangedNodes.push_back(V);
 326
 327     // Insert the node into the node set and return it.
 328     Nodes.InsertNode(V, InsertPos);
 329     ++NumNodes;
 330
 331     if (IsNew) *IsNew = true;
 332   }
 333   else
 334     if (IsNew) *IsNew = false;
 335
 336   return V;
 337 }
 338
 339 std::unique_ptr<ExplodedGraph>
 340 ExplodedGraph::trim(ArrayRef<const NodeTy *> Sinks,
 341                     InterExplodedGraphMap *ForwardMap,
 342                     InterExplodedGraphMap *InverseMap) const {
 343
 344   if (Nodes.empty())
 345     return nullptr;
 346
 347   typedef llvm::DenseSet<const ExplodedNode*> Pass1Ty;
 348   Pass1Ty Pass1;
 349
 350   typedef InterExplodedGraphMap Pass2Ty;
 351   InterExplodedGraphMap Pass2Scratch;
 352   Pass2Ty &Pass2 = ForwardMap ? *ForwardMap : Pass2Scratch;
 353
 354   SmallVector<const ExplodedNode*, 10> WL1, WL2;
 355
 356   // ===- Pass 1 (reverse DFS) -===
 357   for (ArrayRef<const NodeTy *>::iterator I = Sinks.begin(), E = Sinks.end();
 358        I != E; ++I) {
 359     if (*I)
 360       WL1.push_back(*I);
 361   }
 362
 363   // Process the first worklist until it is empty.
 364   while (!WL1.empty()) {
 365     const ExplodedNode *N = WL1.pop_back_val();
 366
 367     // Have we already visited this node?  If so, continue to the next one.
 368     if (!Pass1.insert(N).second)
 369       continue;
 370
 371     // If this is a root enqueue it to the second worklist.
 372     if (N->Preds.empty()) {
 373       WL2.push_back(N);
 374       continue;
 375     }
 376
 377     // Visit our predecessors and enqueue them.
 378     WL1.append(N->Preds.begin(), N->Preds.end());
 379   }
 380
 381   // We didn't hit a root? Return with a null pointer for the new graph.
 382   if (WL2.empty())
 383     return nullptr;
 384
 385   // Create an empty graph.
 386   std::unique_ptr<ExplodedGraph> G = MakeEmptyGraph();
 387
 388   // ===- Pass 2 (forward DFS to construct the new graph) -===
 389   while (!WL2.empty()) {
 390     const ExplodedNode *N = WL2.pop_back_val();
 391
 392     // Skip this node if we have already processed it.
 393     if (Pass2.find(N) != Pass2.end())
 394       continue;
 395
 396     // Create the corresponding node in the new graph and record the mapping
 397     // from the old node to the new node.
 398     ExplodedNode *NewN = G->getNode(N->getLocation(), N->State, N->isSink(),
 399                                     nullptr);
 400     Pass2[N] = NewN;
 401
 402     // Also record the reverse mapping from the new node to the old node.
 403     if (InverseMap) (*InverseMap)[NewN] = N;
 404
 405     // If this node is a root, designate it as such in the graph.
 406     if (N->Preds.empty())
 407       G->addRoot(NewN);
 408
 409     // In the case that some of the intended predecessors of NewN have already
 410     // been created, we should hook them up as predecessors.
 411
 412     // Walk through the predecessors of 'N' and hook up their corresponding
 413     // nodes in the new graph (if any) to the freshly created node.
 414     for (ExplodedNode::pred_iterator I = N->Preds.begin(), E = N->Preds.end();
 415          I != E; ++I) {
 416       Pass2Ty::iterator PI = Pass2.find(*I);
 417       if (PI == Pass2.end())
 418         continue;
 419
 420       NewN->addPredecessor(const_cast<ExplodedNode *>(PI->second), *G);
 421     }
 422
 423     // In the case that some of the intended successors of NewN have already
 424     // been created, we should hook them up as successors.  Otherwise, enqueue
 425     // the new nodes from the original graph that should have nodes created
 426     // in the new graph.
 427     for (ExplodedNode::succ_iterator I = N->Succs.begin(), E = N->Succs.end();
 428          I != E; ++I) {
 429       Pass2Ty::iterator PI = Pass2.find(*I);
 430       if (PI != Pass2.end()) {
 431         const_cast<ExplodedNode *>(PI->second)->addPredecessor(NewN, *G);
 432         continue;
 433       }
 434
 435       // Enqueue nodes to the worklist that were marked during pass 1.
 436       if (Pass1.count(*I))
 437         WL2.push_back(*I);
 438     }
 439   }
 440
 441   return G;
 442 }
 443