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