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