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