ExplodedGraph.h revision f4cf6b10f863b9bc716a09b2b2a8c497dcc6aa9b
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//=-- ExplodedGraph.h - Local, Path-Sens. "Exploded Graph" -*- C++ -*-------==// 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The LLVM Compiler Infrastructure 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file is distributed under the University of Illinois Open Source 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// License. See LICENSE.TXT for details. 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 95d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// 10a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)// This file defines the template classes ExplodedNode and ExplodedGraph, 115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// which represent a path-sensitive, intra-procedural "exploded graph." 12a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)// See "Precise interprocedural dataflow analysis via graph reachability" 135d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// by Reps, Horwitz, and Sagiv 145d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// (http://portal.acm.org/citation.cfm?id=199462) for the definition of an 155d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// exploded graph. 16cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)// 17d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles)//===----------------------------------------------------------------------===// 18d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) 195d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#ifndef LLVM_CLANG_GR_EXPLODEDGRAPH 20a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#define LLVM_CLANG_GR_EXPLODEDGRAPH 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 22a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#include "clang/AST/Decl.h" 232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "clang/Analysis/AnalysisContext.h" 241320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci#include "clang/Analysis/ProgramPoint.h" 255d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include "clang/Analysis/Support/BumpVector.h" 265d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 27a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#include "llvm/ADT/DepthFirstIterator.h" 285d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include "llvm/ADT/FoldingSet.h" 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/ADT/GraphTraits.h" 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/ADT/OwningPtr.h" 315d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include "llvm/ADT/SmallPtrSet.h" 325d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include "llvm/ADT/SmallVector.h" 335d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include "llvm/Support/Allocator.h" 345c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu#include "llvm/Support/Casting.h" 35a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)#include <vector> 36868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace clang { 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 39a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)class CFG; 405d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 415d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)namespace ento { 425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 43e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdochclass ExplodedGraph; 44e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch 45c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch//===----------------------------------------------------------------------===// 46c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch// ExplodedGraph "implementation" classes. These classes are not typed to 47e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch// contain a specific kind of state. Typed-specialized versions are defined 48e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch// on top of these classes. 49a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)//===----------------------------------------------------------------------===// 50a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ExplodedNode is not constified all over the engine because we need to add 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// successors to it at any time after creating it. 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class ExplodedNode : public llvm::FoldingSetNode { 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) friend class ExplodedGraph; 56effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch friend class CoreEngine; 57effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch friend class NodeBuilder; 58a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) friend class BranchNodeBuilder; 595d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) friend class IndirectGotoNodeBuilder; 605d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) friend class SwitchNodeBuilder; 615d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) friend class EndOfFunctionNodeBuilder; 62a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 635d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) /// Efficiently stores a list of ExplodedNodes, or an optional flag. 64a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) /// 65a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) /// NodeGroup provides opaque storage for a list of ExplodedNodes, optimizing 66cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /// for the case when there is only one node in the group. This is a fairly 67cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /// common case in an ExplodedGraph, where most nodes have only one 68cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /// predecessor and many have only one successor. It can also be used to 69cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /// store a flag rather than a node list, which ExplodedNode uses to mark 70cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /// whether a node is a sink. If the flag is set, the group is implicitly 71cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /// empty and no nodes may be added. 725f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) class NodeGroup { 73cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) // Conceptually a discriminated union. If the low bit is set, the node is 74cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) // a sink. If the low bit is not set, the pointer refers to the storage 75cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) // for the nodes in the group. 76cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) // This is not a PointerIntPair in order to keep the storage type opaque. 77cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) uintptr_t P; 78cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 79effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch public: 80effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch NodeGroup(bool Flag = false) : P(Flag) { 81effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch assert(getFlag() == Flag); 82effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch } 83effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch 84effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch ExplodedNode * const *begin() const; 85effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch 86effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch ExplodedNode * const *end() const; 87effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch 88effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch unsigned size() const; 89effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch 90effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch bool empty() const { return P == 0 || getFlag() != 0; } 91effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch 92effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch /// Adds a node to the list. 93effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch /// 94effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch /// The group must not have been created with its flag set. 95effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch void addNode(ExplodedNode *N, ExplodedGraph &G); 96effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch 97effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch /// Replaces the single node in this group with a new node. 98effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch /// 99effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch /// Note that this should only be used when you know the group was not 100effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch /// created with its flag set, and that the group is empty or contains 101effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch /// only a single node. 102effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch void replaceNode(ExplodedNode *node); 103effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch 104effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch /// Returns whether this group was created with its flag set. 105effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch bool getFlag() const { 106effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch return (P & 1); 107effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch } 108effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch }; 109effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch 110effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch /// Location - The program location (within a function body) associated 111effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch /// with this node. 112effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch const ProgramPoint Location; 113effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch 114effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch /// State - The state associated with this node. 115effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch ProgramStateRef State; 116effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch 117effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch /// Preds - The predecessors of this node. 118effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch NodeGroup Preds; 119effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch 120effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch /// Succs - The successors of this node. 121effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch NodeGroup Succs; 122effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch 123effb81e5f8246d0db0270817048dc992db66e9fbBen Murdochpublic: 124effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch 125effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch explicit ExplodedNode(const ProgramPoint &loc, ProgramStateRef state, 126effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch bool IsSink) 127effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch : Location(loc), State(state), Succs(IsSink) { 128effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch assert(isSink() == IsSink); 129effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch } 130effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch 131effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch ~ExplodedNode() {} 132effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch 133effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch /// getLocation - Returns the edge associated with the given node. 134effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch ProgramPoint getLocation() const { return Location; } 135effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch 136effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch const LocationContext *getLocationContext() const { 137effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch return getLocation().getLocationContext(); 138effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch } 139effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch 140effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch const StackFrameContext *getStackFrame() const { 141effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch return getLocationContext()->getCurrentStackFrame(); 142effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch } 143effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch 144effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch const Decl &getCodeDecl() const { return *getLocationContext()->getDecl(); } 145effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch 146effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch CFG &getCFG() const { return *getLocationContext()->getCFG(); } 147effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch 148effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch ParentMap &getParentMap() const {return getLocationContext()->getParentMap();} 149effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch 150e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch template <typename T> 151cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) T &getAnalysis() const { 152c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch return *getLocationContext()->getAnalysis<T>(); 153e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch } 154e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch 155c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch const ProgramStateRef &getState() const { return State; } 156e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch 157c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch template <typename T> 158e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION { 159c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch return Location.getAs<T>(); 160e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch } 161c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch 162e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch static void Profile(llvm::FoldingSetNodeID &ID, 163c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch const ProgramPoint &Loc, 164c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch const ProgramStateRef &state, 165e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch bool IsSink) { 166c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch ID.Add(Loc); 167c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch ID.AddPointer(state.getPtr()); 168e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch ID.AddBoolean(IsSink); 169c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch } 170e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch 171c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch void Profile(llvm::FoldingSetNodeID& ID) const { 172e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch // We avoid copy constructors by not using accessors. 173c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch Profile(ID, Location, State, isSink()); 174e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch } 175c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch 176e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch /// addPredeccessor - Adds a predecessor to the current node, and 177e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch /// in tandem add this node as a successor of the other node. 178e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch void addPredecessor(ExplodedNode *V, ExplodedGraph &G); 179c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch 180e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch unsigned succ_size() const { return Succs.size(); } 181c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch unsigned pred_size() const { return Preds.size(); } 182e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch bool succ_empty() const { return Succs.empty(); } 183e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch bool pred_empty() const { return Preds.empty(); } 184e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch 185c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch bool isSink() const { return Succs.getFlag(); } 186e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch 187c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch bool hasSinglePred() const { 188c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch return (pred_size() == 1); 189e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch } 190c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch 191e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch ExplodedNode *getFirstPred() { 192c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch return pred_empty() ? NULL : *(pred_begin()); 193c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch } 194c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch 195e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch const ExplodedNode *getFirstPred() const { 196e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch return const_cast<ExplodedNode*>(this)->getFirstPred(); 197c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch } 198c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch 199c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch // Iterators over successor and predecessor vertices. 200e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch typedef ExplodedNode* const * succ_iterator; 201e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch typedef const ExplodedNode* const * const_succ_iterator; 202c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch typedef ExplodedNode* const * pred_iterator; 203e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch typedef const ExplodedNode* const * const_pred_iterator; 204c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch 205e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch pred_iterator pred_begin() { return Preds.begin(); } 206e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch pred_iterator pred_end() { return Preds.end(); } 207e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch 208e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch const_pred_iterator pred_begin() const { 209e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch return const_cast<ExplodedNode*>(this)->pred_begin(); 210e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch } 211c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch const_pred_iterator pred_end() const { 212e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch return const_cast<ExplodedNode*>(this)->pred_end(); 213e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch } 214e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch 215e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch succ_iterator succ_begin() { return Succs.begin(); } 216e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch succ_iterator succ_end() { return Succs.end(); } 217e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch 218c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch const_succ_iterator succ_begin() const { 219e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch return const_cast<ExplodedNode*>(this)->succ_begin(); 220e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch } 221c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch const_succ_iterator succ_end() const { 222e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch return const_cast<ExplodedNode*>(this)->succ_end(); 223e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch } 224c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch 225e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch // For debugging. 226c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch 227e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdochpublic: 228c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch 229c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch class Auditor { 230c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch public: 231e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch virtual ~Auditor(); 232e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch virtual void AddEdge(ExplodedNode *Src, ExplodedNode *Dst) = 0; 233e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch }; 234e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch 235e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch static void SetAuditor(Auditor* A); 236e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)private: 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); } 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); } 24090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)}; 2411320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef llvm::DenseMap<const ExplodedNode *, const ExplodedNode *> 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) InterExplodedGraphMap; 24468043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) 24568043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles)class ExplodedGraph { 24668043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles)protected: 24768043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) friend class CoreEngine; 24868043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) 24968043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) // Type definitions. 25068043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) typedef std::vector<ExplodedNode *> NodeVector; 25168043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) 25268043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) /// The roots of the simulation graph. Usually there will be only 25368043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) /// one, but clients are free to establish multiple subgraphs within a single 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// SimulGraph. Moreover, these subgraphs can often merge when paths from 2555d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) /// different roots reach the same state at the same program location. 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NodeVector Roots; 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// The nodes in the simulation graph which have been 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// specially marked as the endpoint of an abstract simulation path. 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NodeVector EndNodes; 26146d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) 26246d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) /// Nodes - The nodes in the graph. 26346d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) llvm::FoldingSet<ExplodedNode> Nodes; 26446d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) 26546d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) /// BVC - Allocator and context for allocating nodes and their predecessor 26646d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) /// and successor groups. 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BumpVectorContext BVC; 26858537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 269c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch /// NumNodes - The number of nodes in the graph. 2705d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) unsigned NumNodes; 2715d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2725d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) /// A list of recently allocated nodes that can potentially be recycled. 2735d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) NodeVector ChangedNodes; 2745d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2755f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) /// A list of nodes that can be reused. 2765f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) NodeVector FreeNodes; 27758537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 2785d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) /// Determines how often nodes are reclaimed. 2795d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) /// 2805d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) /// If this is 0, nodes will never be reclaimed. 2815d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) unsigned ReclaimNodeInterval; 282868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 283868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) /// Counter to determine when to reclaim nodes. 2845d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) unsigned ReclaimCounter; 285868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 286868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)public: 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// \brief Retrieve the node associated with a (Location,State) pair, 2895d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) /// where the 'Location' is a ProgramPoint in the CFG. If no node for 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// this pair exists, it is created. IsNew is set to true if 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// the node was freshly created. 29290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) ExplodedNode *getNode(const ProgramPoint &L, ProgramStateRef State, 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool IsSink = false, 2945d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bool* IsNew = 0); 2955d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2965d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) ExplodedGraph* MakeEmptyGraph() const { 2975d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return new ExplodedGraph(); 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// addRoot - Add an untyped node to the set of roots. 3015d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) ExplodedNode *addRoot(ExplodedNode *V) { 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Roots.push_back(V); 3035d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return V; 3045d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 3055d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3065d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) /// addEndOfPath - Add an untyped node to the set of EOP nodes. 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExplodedNode *addEndOfPath(ExplodedNode *V) { 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EndNodes.push_back(V); 3095d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return V; 3105d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 3115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3125d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) ExplodedGraph(); 313a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ~ExplodedGraph(); 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3165d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) unsigned num_roots() const { return Roots.size(); } 3175d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) unsigned num_eops() const { return EndNodes.size(); } 3185d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3195d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bool empty() const { return NumNodes == 0; } 3205d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) unsigned size() const { return NumNodes; } 3215d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Iterators. 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef ExplodedNode NodeTy; 3245d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) typedef llvm::FoldingSet<ExplodedNode> AllNodesTy; 3255d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) typedef NodeVector::iterator roots_iterator; 3265d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) typedef NodeVector::const_iterator const_roots_iterator; 3275d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) typedef NodeVector::iterator eop_iterator; 3285d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) typedef NodeVector::const_iterator const_eop_iterator; 3295d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) typedef AllNodesTy::iterator node_iterator; 3302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef AllNodesTy::const_iterator const_node_iterator; 3312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) node_iterator nodes_begin() { return Nodes.begin(); } 3335d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) node_iterator nodes_end() { return Nodes.end(); } 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 336cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) const_node_iterator nodes_begin() const { return Nodes.begin(); } 337cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 338cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) const_node_iterator nodes_end() const { return Nodes.end(); } 339cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) roots_iterator roots_begin() { return Roots.begin(); } 3415d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) roots_iterator roots_end() { return Roots.end(); } 3435d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_roots_iterator roots_begin() const { return Roots.begin(); } 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3465f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) const_roots_iterator roots_end() const { return Roots.end(); } 3475f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 3485f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) eop_iterator eop_begin() { return EndNodes.begin(); } 3495f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 3505f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) eop_iterator eop_end() { return EndNodes.end(); } 3515f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 3525d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) const_eop_iterator eop_begin() const { return EndNodes.begin(); } 3535d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3545d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) const_eop_iterator eop_end() const { return EndNodes.end(); } 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); } 3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BumpVectorContext &getNodeAllocator() { return BVC; } 3585d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef llvm::DenseMap<const ExplodedNode*, ExplodedNode*> NodeMap; 3602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// Creates a trimmed version of the graph that only contains paths leading 3622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// to the given nodes. 3632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// 3642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// \param Nodes The nodes which must appear in the final graph. Presumably 3652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// these are end-of-path nodes (i.e. they have no successors). 3662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// \param BreakCycles Whether or not the trimmed graph should make an effort 3672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// to eliminate cycles. Note that this may result in some 3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// unnecessary nodes being included in the final graph 3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// (i.e. nodes that would have only appeared in a cycle). 3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// \param[out] ForwardMap A optional map from nodes in this graph to nodes in 3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// the returned graph. 3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// \param[out] InverseMap An optional map from nodes in the returned graph to 3735d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) /// nodes in this graph. 3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// \returns The trimmed graph 3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExplodedGraph *trim(ArrayRef<const NodeTy *> Nodes, bool BreakCycles = false, 3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) InterExplodedGraphMap *ForwardMap = 0, 3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) InterExplodedGraphMap *InverseMap = 0) const; 3785d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// Enable tracking of recently allocated nodes for potential reclamation 3805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// when calling reclaimRecentlyAllocatedNodes(). 3812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void enableNodeReclamation(unsigned Interval) { 3822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ReclaimCounter = ReclaimNodeInterval = Interval; 3832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 3842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// Reclaim "uninteresting" nodes created since the last time this method 3862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// was called. 3872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void reclaimRecentlyAllocatedNodes(); 3882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// \brief Returns true if nodes for the given expression kind are always 3905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// kept around. 3915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static bool isInterestingLValueExpr(const Expr *Ex); 3925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3935d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)private: 3945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool shouldCollect(const ExplodedNode *node); 3955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void collectNode(ExplodedNode *node); 3965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 3975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3985d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)class ExplodedNodeSet { 3995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef llvm::SmallPtrSet<ExplodedNode*,5> ImplTy; 4005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ImplTy Impl; 40146d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) 40246d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles)public: 40346d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) ExplodedNodeSet(ExplodedNode *N) { 40446d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) assert (N && !static_cast<ExplodedNode*>(N)->isSink()); 40546d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) Impl.insert(N); 40646d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) } 40746d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) 40846d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) ExplodedNodeSet() {} 40946d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) 41046d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) inline void Add(ExplodedNode *N) { 41146d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N); 41246d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) } 41346d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) 41446d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) typedef ImplTy::iterator iterator; 41546d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) typedef ImplTy::const_iterator const_iterator; 41646d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) 41746d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) unsigned size() const { return Impl.size(); } 41846d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) bool empty() const { return Impl.empty(); } 41946d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) bool erase(ExplodedNode *N) { return Impl.erase(N); } 42046d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) 421116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch void clear() { Impl.clear(); } 422116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch void insert(const ExplodedNodeSet &S) { 423116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch assert(&S != this); 424116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (empty()) 425116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch Impl = S.Impl; 42646d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) else 42746d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) Impl.insert(S.begin(), S.end()); 42846d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) } 42946d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) 43046d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) inline iterator begin() { return Impl.begin(); } 43146d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) inline iterator end() { return Impl.end(); } 43246d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) 43346d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) inline const_iterator begin() const { return Impl.begin(); } 43446d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) inline const_iterator end() const { return Impl.end(); } 43546d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles)}; 43646d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) 43746d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles)} // end GR namespace 43846d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) 43946d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles)} // end clang namespace 44046d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) 44146d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles)// GraphTraits 44246d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) 44346d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles)namespace llvm { 44446d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) template<> struct GraphTraits<clang::ento::ExplodedNode*> { 44546d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) typedef clang::ento::ExplodedNode NodeType; 44646d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) typedef NodeType::succ_iterator ChildIteratorType; 44746d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) typedef llvm::df_iterator<NodeType*> nodes_iterator; 4482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4495d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) static inline NodeType* getEntryNode(NodeType* N) { 4505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return N; 4515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4535d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) static inline ChildIteratorType child_begin(NodeType* N) { 454a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) return N->succ_begin(); 455a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) } 4565d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4575d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) static inline ChildIteratorType child_end(NodeType* N) { 4585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return N->succ_end(); 4595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4605d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4615d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) static inline nodes_iterator nodes_begin(NodeType* N) { 4625d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return df_begin(N); 4635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline nodes_iterator nodes_end(NodeType* N) { 4668bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles) return df_end(N); 4678bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles) } 4688bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles) }; 4698bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles) 4705c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu template<> struct GraphTraits<const clang::ento::ExplodedNode*> { 4715c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu typedef const clang::ento::ExplodedNode NodeType; 4725c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu typedef NodeType::const_succ_iterator ChildIteratorType; 4735c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu typedef llvm::df_iterator<NodeType*> nodes_iterator; 4745c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu 4755c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu static inline NodeType* getEntryNode(NodeType* N) { 4765c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu return N; 4775c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu } 4785d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 479c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch static inline ChildIteratorType child_begin(NodeType* N) { 480c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch return N->succ_begin(); 4815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline ChildIteratorType child_end(NodeType* N) { 4845d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return N->succ_end(); 4855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4875d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) static inline nodes_iterator nodes_begin(NodeType* N) { 4885d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return df_begin(N); 4895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 49158537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) static inline nodes_iterator nodes_end(NodeType* N) { 4925d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return df_end(N); 4935d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 4945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 4955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4965d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} // end llvm namespace 4975d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 4995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)