1218887Sdim//=-- ExplodedGraph.cpp - Local, Path-Sens. "Exploded Graph" -*- C++ -*------=// 2218887Sdim// 3218887Sdim// The LLVM Compiler Infrastructure 4218887Sdim// 5218887Sdim// This file is distributed under the University of Illinois Open Source 6218887Sdim// License. See LICENSE.TXT for details. 7218887Sdim// 8218887Sdim//===----------------------------------------------------------------------===// 9218887Sdim// 10218887Sdim// This file defines the template classes ExplodedNode and ExplodedGraph, 11218887Sdim// which represent a path-sensitive, intra-procedural "exploded graph." 12218887Sdim// 13218887Sdim//===----------------------------------------------------------------------===// 14218887Sdim 15218887Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" 16249423Sdim#include "clang/AST/ParentMap.h" 17249423Sdim#include "clang/AST/Stmt.h" 18239462Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 19226633Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 20249423Sdim#include "llvm/ADT/DenseMap.h" 21218887Sdim#include "llvm/ADT/DenseSet.h" 22218887Sdim#include "llvm/ADT/SmallVector.h" 23239462Sdim#include "llvm/ADT/Statistic.h" 24218887Sdim#include <vector> 25218887Sdim 26218887Sdimusing namespace clang; 27218887Sdimusing namespace ento; 28218887Sdim 29218887Sdim//===----------------------------------------------------------------------===// 30218887Sdim// Node auditing. 31218887Sdim//===----------------------------------------------------------------------===// 32218887Sdim 33218887Sdim// An out of line virtual method to provide a home for the class vtable. 34218887SdimExplodedNode::Auditor::~Auditor() {} 35218887Sdim 36218887Sdim#ifndef NDEBUG 37218887Sdimstatic ExplodedNode::Auditor* NodeAuditor = 0; 38218887Sdim#endif 39218887Sdim 40218887Sdimvoid ExplodedNode::SetAuditor(ExplodedNode::Auditor* A) { 41218887Sdim#ifndef NDEBUG 42218887Sdim NodeAuditor = A; 43218887Sdim#endif 44218887Sdim} 45218887Sdim 46218887Sdim//===----------------------------------------------------------------------===// 47218887Sdim// Cleanup. 48218887Sdim//===----------------------------------------------------------------------===// 49218887Sdim 50234353SdimExplodedGraph::ExplodedGraph() 51243830Sdim : NumNodes(0), ReclaimNodeInterval(0) {} 52218887Sdim 53234353SdimExplodedGraph::~ExplodedGraph() {} 54234353Sdim 55218887Sdim//===----------------------------------------------------------------------===// 56218887Sdim// Node reclamation. 57218887Sdim//===----------------------------------------------------------------------===// 58218887Sdim 59249423Sdimbool ExplodedGraph::isInterestingLValueExpr(const Expr *Ex) { 60249423Sdim if (!Ex->isLValue()) 61249423Sdim return false; 62249423Sdim return isa<DeclRefExpr>(Ex) || 63249423Sdim isa<MemberExpr>(Ex) || 64249423Sdim isa<ObjCIvarRefExpr>(Ex); 65249423Sdim} 66249423Sdim 67234353Sdimbool ExplodedGraph::shouldCollect(const ExplodedNode *node) { 68249423Sdim // First, we only consider nodes for reclamation of the following 69249423Sdim // conditions apply: 70218887Sdim // 71218887Sdim // (1) 1 predecessor (that has one successor) 72218887Sdim // (2) 1 successor (that has one predecessor) 73249423Sdim // 74249423Sdim // If a node has no successor it is on the "frontier", while a node 75249423Sdim // with no predecessor is a root. 76249423Sdim // 77249423Sdim // After these prerequisites, we discard all "filler" nodes that 78249423Sdim // are used only for intermediate processing, and are not essential 79249423Sdim // for analyzer history: 80249423Sdim // 81249423Sdim // (a) PreStmtPurgeDeadSymbols 82249423Sdim // 83249423Sdim // We then discard all other nodes where *all* of the following conditions 84249423Sdim // apply: 85249423Sdim // 86243830Sdim // (3) The ProgramPoint is for a PostStmt, but not a PostStore. 87218887Sdim // (4) There is no 'tag' for the ProgramPoint. 88218887Sdim // (5) The 'store' is the same as the predecessor. 89218887Sdim // (6) The 'GDM' is the same as the predecessor. 90218887Sdim // (7) The LocationContext is the same as the predecessor. 91249423Sdim // (8) Expressions that are *not* lvalue expressions. 92249423Sdim // (9) The PostStmt isn't for a non-consumed Stmt or Expr. 93249423Sdim // (10) The successor is not a CallExpr StmtPoint (so that we would 94249423Sdim // be able to find it when retrying a call with no inlining). 95239462Sdim // FIXME: It may be safe to reclaim PreCall and PostCall nodes as well. 96234353Sdim 97234353Sdim // Conditions 1 and 2. 98234353Sdim if (node->pred_size() != 1 || node->succ_size() != 1) 99234353Sdim return false; 100234353Sdim 101234353Sdim const ExplodedNode *pred = *(node->pred_begin()); 102234353Sdim if (pred->succ_size() != 1) 103234353Sdim return false; 104218887Sdim 105234353Sdim const ExplodedNode *succ = *(node->succ_begin()); 106234353Sdim if (succ->pred_size() != 1) 107234353Sdim return false; 108218887Sdim 109249423Sdim // Now reclaim any nodes that are (by definition) not essential to 110249423Sdim // analysis history and are not consulted by any client code. 111249423Sdim ProgramPoint progPoint = node->getLocation(); 112249423Sdim if (progPoint.getAs<PreStmtPurgeDeadSymbols>()) 113249423Sdim return !progPoint.getTag(); 114249423Sdim 115234353Sdim // Condition 3. 116249423Sdim if (!progPoint.getAs<PostStmt>() || progPoint.getAs<PostStore>()) 117234353Sdim return false; 118218887Sdim 119234353Sdim // Condition 4. 120249423Sdim if (progPoint.getTag()) 121234353Sdim return false; 122218887Sdim 123234353Sdim // Conditions 5, 6, and 7. 124234353Sdim ProgramStateRef state = node->getState(); 125234353Sdim ProgramStateRef pred_state = pred->getState(); 126234353Sdim if (state->store != pred_state->store || state->GDM != pred_state->GDM || 127234353Sdim progPoint.getLocationContext() != pred->getLocationContext()) 128234353Sdim return false; 129249423Sdim 130249423Sdim // All further checks require expressions. As per #3, we know that we have 131249423Sdim // a PostStmt. 132249423Sdim const Expr *Ex = dyn_cast<Expr>(progPoint.castAs<PostStmt>().getStmt()); 133249423Sdim if (!Ex) 134249423Sdim return false; 135249423Sdim 136234353Sdim // Condition 8. 137249423Sdim // Do not collect nodes for "interesting" lvalue expressions since they are 138249423Sdim // used extensively for generating path diagnostics. 139249423Sdim if (isInterestingLValueExpr(Ex)) 140249423Sdim return false; 141249423Sdim 142249423Sdim // Condition 9. 143243830Sdim // Do not collect nodes for non-consumed Stmt or Expr to ensure precise 144243830Sdim // diagnostic generation; specifically, so that we could anchor arrows 145243830Sdim // pointing to the beginning of statements (as written in code). 146249423Sdim ParentMap &PM = progPoint.getLocationContext()->getParentMap(); 147249423Sdim if (!PM.isConsumedExpr(Ex)) 148243830Sdim return false; 149249423Sdim 150249423Sdim // Condition 10. 151239462Sdim const ProgramPoint SuccLoc = succ->getLocation(); 152249423Sdim if (Optional<StmtPoint> SP = SuccLoc.getAs<StmtPoint>()) 153243830Sdim if (CallEvent::isCallStmt(SP->getStmt())) 154239462Sdim return false; 155239462Sdim 156239462Sdim return true; 157234353Sdim} 158218887Sdim 159234353Sdimvoid ExplodedGraph::collectNode(ExplodedNode *node) { 160234353Sdim // Removing a node means: 161234353Sdim // (a) changing the predecessors successor to the successor of this node 162234353Sdim // (b) changing the successors predecessor to the predecessor of this node 163234353Sdim // (c) Putting 'node' onto freeNodes. 164234353Sdim assert(node->pred_size() == 1 || node->succ_size() == 1); 165234353Sdim ExplodedNode *pred = *(node->pred_begin()); 166234353Sdim ExplodedNode *succ = *(node->succ_begin()); 167234353Sdim pred->replaceSuccessor(succ); 168234353Sdim succ->replacePredecessor(pred); 169234353Sdim FreeNodes.push_back(node); 170234353Sdim Nodes.RemoveNode(node); 171234353Sdim --NumNodes; 172234353Sdim node->~ExplodedNode(); 173234353Sdim} 174218887Sdim 175234353Sdimvoid ExplodedGraph::reclaimRecentlyAllocatedNodes() { 176234353Sdim if (ChangedNodes.empty()) 177234353Sdim return; 178218887Sdim 179243830Sdim // Only periodically reclaim nodes so that we can build up a set of 180234353Sdim // nodes that meet the reclamation criteria. Freshly created nodes 181234353Sdim // by definition have no successor, and thus cannot be reclaimed (see below). 182243830Sdim assert(ReclaimCounter > 0); 183243830Sdim if (--ReclaimCounter != 0) 184234353Sdim return; 185243830Sdim ReclaimCounter = ReclaimNodeInterval; 186234353Sdim 187234353Sdim for (NodeVector::iterator it = ChangedNodes.begin(), et = ChangedNodes.end(); 188234353Sdim it != et; ++it) { 189234353Sdim ExplodedNode *node = *it; 190234353Sdim if (shouldCollect(node)) 191234353Sdim collectNode(node); 192218887Sdim } 193234353Sdim ChangedNodes.clear(); 194218887Sdim} 195218887Sdim 196218887Sdim//===----------------------------------------------------------------------===// 197218887Sdim// ExplodedNode. 198218887Sdim//===----------------------------------------------------------------------===// 199218887Sdim 200243830Sdim// An NodeGroup's storage type is actually very much like a TinyPtrVector: 201243830Sdim// it can be either a pointer to a single ExplodedNode, or a pointer to a 202243830Sdim// BumpVector allocated with the ExplodedGraph's allocator. This allows the 203243830Sdim// common case of single-node NodeGroups to be implemented with no extra memory. 204243830Sdim// 205243830Sdim// Consequently, each of the NodeGroup methods have up to four cases to handle: 206243830Sdim// 1. The flag is set and this group does not actually contain any nodes. 207243830Sdim// 2. The group is empty, in which case the storage value is null. 208243830Sdim// 3. The group contains a single node. 209243830Sdim// 4. The group contains more than one node. 210243830Sdimtypedef BumpVector<ExplodedNode *> ExplodedNodeVector; 211243830Sdimtypedef llvm::PointerUnion<ExplodedNode *, ExplodedNodeVector *> GroupStorage; 212218887Sdim 213226633Sdimvoid ExplodedNode::addPredecessor(ExplodedNode *V, ExplodedGraph &G) { 214218887Sdim assert (!V->isSink()); 215218887Sdim Preds.addNode(V, G); 216218887Sdim V->Succs.addNode(this, G); 217218887Sdim#ifndef NDEBUG 218218887Sdim if (NodeAuditor) NodeAuditor->AddEdge(V, this); 219218887Sdim#endif 220218887Sdim} 221218887Sdim 222218887Sdimvoid ExplodedNode::NodeGroup::replaceNode(ExplodedNode *node) { 223243830Sdim assert(!getFlag()); 224243830Sdim 225243830Sdim GroupStorage &Storage = reinterpret_cast<GroupStorage&>(P); 226243830Sdim assert(Storage.is<ExplodedNode *>()); 227243830Sdim Storage = node; 228243830Sdim assert(Storage.is<ExplodedNode *>()); 229218887Sdim} 230218887Sdim 231226633Sdimvoid ExplodedNode::NodeGroup::addNode(ExplodedNode *N, ExplodedGraph &G) { 232218887Sdim assert(!getFlag()); 233218887Sdim 234243830Sdim GroupStorage &Storage = reinterpret_cast<GroupStorage&>(P); 235243830Sdim if (Storage.isNull()) { 236243830Sdim Storage = N; 237243830Sdim assert(Storage.is<ExplodedNode *>()); 238243830Sdim return; 239218887Sdim } 240243830Sdim 241243830Sdim ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>(); 242243830Sdim 243243830Sdim if (!V) { 244243830Sdim // Switch from single-node to multi-node representation. 245243830Sdim ExplodedNode *Old = Storage.get<ExplodedNode *>(); 246243830Sdim 247243830Sdim BumpVectorContext &Ctx = G.getNodeAllocator(); 248243830Sdim V = G.getAllocator().Allocate<ExplodedNodeVector>(); 249243830Sdim new (V) ExplodedNodeVector(Ctx, 4); 250243830Sdim V->push_back(Old, Ctx); 251243830Sdim 252243830Sdim Storage = V; 253243830Sdim assert(!getFlag()); 254243830Sdim assert(Storage.is<ExplodedNodeVector *>()); 255218887Sdim } 256243830Sdim 257243830Sdim V->push_back(N, G.getNodeAllocator()); 258218887Sdim} 259218887Sdim 260218887Sdimunsigned ExplodedNode::NodeGroup::size() const { 261218887Sdim if (getFlag()) 262218887Sdim return 0; 263218887Sdim 264243830Sdim const GroupStorage &Storage = reinterpret_cast<const GroupStorage &>(P); 265243830Sdim if (Storage.isNull()) 266243830Sdim return 0; 267243830Sdim if (ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>()) 268243830Sdim return V->size(); 269243830Sdim return 1; 270218887Sdim} 271218887Sdim 272243830SdimExplodedNode * const *ExplodedNode::NodeGroup::begin() const { 273218887Sdim if (getFlag()) 274243830Sdim return 0; 275218887Sdim 276243830Sdim const GroupStorage &Storage = reinterpret_cast<const GroupStorage &>(P); 277243830Sdim if (Storage.isNull()) 278243830Sdim return 0; 279243830Sdim if (ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>()) 280243830Sdim return V->begin(); 281243830Sdim return Storage.getAddrOfPtr1(); 282218887Sdim} 283218887Sdim 284243830SdimExplodedNode * const *ExplodedNode::NodeGroup::end() const { 285218887Sdim if (getFlag()) 286243830Sdim return 0; 287218887Sdim 288243830Sdim const GroupStorage &Storage = reinterpret_cast<const GroupStorage &>(P); 289243830Sdim if (Storage.isNull()) 290243830Sdim return 0; 291243830Sdim if (ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>()) 292243830Sdim return V->end(); 293243830Sdim return Storage.getAddrOfPtr1() + 1; 294218887Sdim} 295218887Sdim 296226633SdimExplodedNode *ExplodedGraph::getNode(const ProgramPoint &L, 297234353Sdim ProgramStateRef State, 298234353Sdim bool IsSink, 299234353Sdim bool* IsNew) { 300218887Sdim // Profile 'State' to determine if we already have an existing node. 301218887Sdim llvm::FoldingSetNodeID profile; 302226633Sdim void *InsertPos = 0; 303218887Sdim 304234353Sdim NodeTy::Profile(profile, L, State, IsSink); 305218887Sdim NodeTy* V = Nodes.FindNodeOrInsertPos(profile, InsertPos); 306218887Sdim 307218887Sdim if (!V) { 308234353Sdim if (!FreeNodes.empty()) { 309234353Sdim V = FreeNodes.back(); 310234353Sdim FreeNodes.pop_back(); 311218887Sdim } 312218887Sdim else { 313218887Sdim // Allocate a new node. 314218887Sdim V = (NodeTy*) getAllocator().Allocate<NodeTy>(); 315218887Sdim } 316218887Sdim 317234353Sdim new (V) NodeTy(L, State, IsSink); 318218887Sdim 319243830Sdim if (ReclaimNodeInterval) 320234353Sdim ChangedNodes.push_back(V); 321218887Sdim 322218887Sdim // Insert the node into the node set and return it. 323218887Sdim Nodes.InsertNode(V, InsertPos); 324218887Sdim ++NumNodes; 325218887Sdim 326218887Sdim if (IsNew) *IsNew = true; 327218887Sdim } 328218887Sdim else 329218887Sdim if (IsNew) *IsNew = false; 330218887Sdim 331218887Sdim return V; 332218887Sdim} 333218887Sdim 334249423SdimExplodedGraph * 335249423SdimExplodedGraph::trim(ArrayRef<const NodeTy *> Sinks, 336249423Sdim InterExplodedGraphMap *ForwardMap, 337249423Sdim InterExplodedGraphMap *InverseMap) const{ 338218887Sdim 339249423Sdim if (Nodes.empty()) 340249423Sdim return 0; 341218887Sdim 342218887Sdim typedef llvm::DenseSet<const ExplodedNode*> Pass1Ty; 343218887Sdim Pass1Ty Pass1; 344218887Sdim 345249423Sdim typedef InterExplodedGraphMap Pass2Ty; 346249423Sdim InterExplodedGraphMap Pass2Scratch; 347249423Sdim Pass2Ty &Pass2 = ForwardMap ? *ForwardMap : Pass2Scratch; 348218887Sdim 349226633Sdim SmallVector<const ExplodedNode*, 10> WL1, WL2; 350218887Sdim 351218887Sdim // ===- Pass 1 (reverse DFS) -=== 352249423Sdim for (ArrayRef<const NodeTy *>::iterator I = Sinks.begin(), E = Sinks.end(); 353249423Sdim I != E; ++I) { 354243830Sdim if (*I) 355243830Sdim WL1.push_back(*I); 356218887Sdim } 357218887Sdim 358249423Sdim // Process the first worklist until it is empty. 359218887Sdim while (!WL1.empty()) { 360263508Sdim const ExplodedNode *N = WL1.pop_back_val(); 361218887Sdim 362218887Sdim // Have we already visited this node? If so, continue to the next one. 363218887Sdim if (Pass1.count(N)) 364218887Sdim continue; 365218887Sdim 366218887Sdim // Otherwise, mark this node as visited. 367218887Sdim Pass1.insert(N); 368218887Sdim 369218887Sdim // If this is a root enqueue it to the second worklist. 370218887Sdim if (N->Preds.empty()) { 371218887Sdim WL2.push_back(N); 372218887Sdim continue; 373218887Sdim } 374218887Sdim 375218887Sdim // Visit our predecessors and enqueue them. 376243830Sdim for (ExplodedNode::pred_iterator I = N->Preds.begin(), E = N->Preds.end(); 377243830Sdim I != E; ++I) 378218887Sdim WL1.push_back(*I); 379218887Sdim } 380218887Sdim 381218887Sdim // We didn't hit a root? Return with a null pointer for the new graph. 382218887Sdim if (WL2.empty()) 383218887Sdim return 0; 384218887Sdim 385218887Sdim // Create an empty graph. 386218887Sdim ExplodedGraph* G = MakeEmptyGraph(); 387218887Sdim 388218887Sdim // ===- Pass 2 (forward DFS to construct the new graph) -=== 389218887Sdim while (!WL2.empty()) { 390263508Sdim const ExplodedNode *N = WL2.pop_back_val(); 391218887Sdim 392218887Sdim // Skip this node if we have already processed it. 393218887Sdim if (Pass2.find(N) != Pass2.end()) 394218887Sdim continue; 395218887Sdim 396218887Sdim // Create the corresponding node in the new graph and record the mapping 397218887Sdim // from the old node to the new node. 398234353Sdim ExplodedNode *NewN = G->getNode(N->getLocation(), N->State, N->isSink(), 0); 399218887Sdim Pass2[N] = NewN; 400218887Sdim 401218887Sdim // Also record the reverse mapping from the new node to the old node. 402218887Sdim if (InverseMap) (*InverseMap)[NewN] = N; 403218887Sdim 404218887Sdim // If this node is a root, designate it as such in the graph. 405218887Sdim if (N->Preds.empty()) 406218887Sdim G->addRoot(NewN); 407218887Sdim 408218887Sdim // In the case that some of the intended predecessors of NewN have already 409218887Sdim // been created, we should hook them up as predecessors. 410218887Sdim 411218887Sdim // Walk through the predecessors of 'N' and hook up their corresponding 412218887Sdim // nodes in the new graph (if any) to the freshly created node. 413243830Sdim for (ExplodedNode::pred_iterator I = N->Preds.begin(), E = N->Preds.end(); 414243830Sdim I != E; ++I) { 415218887Sdim Pass2Ty::iterator PI = Pass2.find(*I); 416218887Sdim if (PI == Pass2.end()) 417218887Sdim continue; 418218887Sdim 419249423Sdim NewN->addPredecessor(const_cast<ExplodedNode *>(PI->second), *G); 420218887Sdim } 421218887Sdim 422218887Sdim // In the case that some of the intended successors of NewN have already 423218887Sdim // been created, we should hook them up as successors. Otherwise, enqueue 424218887Sdim // the new nodes from the original graph that should have nodes created 425218887Sdim // in the new graph. 426243830Sdim for (ExplodedNode::succ_iterator I = N->Succs.begin(), E = N->Succs.end(); 427243830Sdim I != E; ++I) { 428218887Sdim Pass2Ty::iterator PI = Pass2.find(*I); 429218887Sdim if (PI != Pass2.end()) { 430249423Sdim const_cast<ExplodedNode *>(PI->second)->addPredecessor(NewN, *G); 431218887Sdim continue; 432218887Sdim } 433218887Sdim 434218887Sdim // Enqueue nodes to the worklist that were marked during pass 1. 435218887Sdim if (Pass1.count(*I)) 436218887Sdim WL2.push_back(*I); 437218887Sdim } 438218887Sdim } 439218887Sdim 440218887Sdim return G; 441218887Sdim} 442218887Sdim 443