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