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