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

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