1139749Simp//=-- ExplodedGraph.h - Local, Path-Sens. "Exploded Graph" -*- C++ -*-------==// 265205Scg// 365205Scg// The LLVM Compiler Infrastructure 465205Scg// 565205Scg// This file is distributed under the University of Illinois Open Source 665205Scg// License. See LICENSE.TXT for details. 765205Scg// 865205Scg//===----------------------------------------------------------------------===// 965205Scg// 1065205Scg// This file defines the template classes ExplodedNode and ExplodedGraph, 1165205Scg// which represent a path-sensitive, intra-procedural "exploded graph." 1265205Scg// See "Precise interprocedural dataflow analysis via graph reachability" 1365205Scg// by Reps, Horwitz, and Sagiv 1465205Scg// (http://portal.acm.org/citation.cfm?id=199462) for the definition of an 1565205Scg// exploded graph. 1665205Scg// 1765205Scg//===----------------------------------------------------------------------===// 1865205Scg 1965205Scg#ifndef LLVM_CLANG_GR_EXPLODEDGRAPH 2065205Scg#define LLVM_CLANG_GR_EXPLODEDGRAPH 2165205Scg 2265205Scg#include "clang/AST/Decl.h" 2365205Scg#include "clang/Analysis/AnalysisContext.h" 2465205Scg#include "clang/Analysis/ProgramPoint.h" 2565205Scg#include "clang/Analysis/Support/BumpVector.h" 2665205Scg#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 27193640Sariff#include "llvm/ADT/DepthFirstIterator.h" 28193640Sariff#include "llvm/ADT/FoldingSet.h" 29193640Sariff#include "llvm/ADT/GraphTraits.h" 30193640Sariff#include "llvm/ADT/OwningPtr.h" 3165205Scg#include "llvm/ADT/SmallPtrSet.h" 3265205Scg#include "llvm/ADT/SmallVector.h" 33119287Simp#include "llvm/Support/Allocator.h" 34119287Simp#include "llvm/Support/Casting.h" 3565205Scg#include <vector> 3682180Scg 3782180Scgnamespace clang { 3865205Scg 39169762Sjoelclass CFG; 40169762Sjoel 4165205Scgnamespace ento { 4265205Scg 4365205Scgclass ExplodedGraph; 4465205Scg 4565205Scg//===----------------------------------------------------------------------===// 4665205Scg// ExplodedGraph "implementation" classes. These classes are not typed to 4765205Scg// contain a specific kind of state. Typed-specialized versions are defined 4865205Scg// on top of these classes. 4965205Scg//===----------------------------------------------------------------------===// 5065205Scg 5165205Scg// ExplodedNode is not constified all over the engine because we need to add 5265205Scg// successors to it at any time after creating it. 5365205Scg 5465205Scgclass ExplodedNode : public llvm::FoldingSetNode { 5565205Scg friend class ExplodedGraph; 5665205Scg friend class CoreEngine; 5765205Scg friend class NodeBuilder; 5865205Scg friend class BranchNodeBuilder; 5965205Scg friend class IndirectGotoNodeBuilder; 6065205Scg friend class SwitchNodeBuilder; 6165205Scg friend class EndOfFunctionNodeBuilder; 6265205Scg 6365205Scg /// Efficiently stores a list of ExplodedNodes, or an optional flag. 6465205Scg /// 6565205Scg /// NodeGroup provides opaque storage for a list of ExplodedNodes, optimizing 6665205Scg /// for the case when there is only one node in the group. This is a fairly 6765205Scg /// common case in an ExplodedGraph, where most nodes have only one 6865205Scg /// predecessor and many have only one successor. It can also be used to 6965205Scg /// store a flag rather than a node list, which ExplodedNode uses to mark 7065205Scg /// whether a node is a sink. If the flag is set, the group is implicitly 7165205Scg /// empty and no nodes may be added. 7265205Scg class NodeGroup { 7365205Scg // Conceptually a discriminated union. If the low bit is set, the node is 7465205Scg // a sink. If the low bit is not set, the pointer refers to the storage 7565205Scg // for the nodes in the group. 7665205Scg // This is not a PointerIntPair in order to keep the storage type opaque. 7765205Scg uintptr_t P; 7865205Scg 7965205Scg public: 8065205Scg NodeGroup(bool Flag = false) : P(Flag) { 8165205Scg assert(getFlag() == Flag); 8265205Scg } 8365205Scg 8465205Scg ExplodedNode * const *begin() const; 8565205Scg 8665205Scg ExplodedNode * const *end() const; 8765205Scg 8865205Scg unsigned size() const; 8965205Scg 9065205Scg bool empty() const { return P == 0 || getFlag() != 0; } 9165205Scg 9265205Scg /// Adds a node to the list. 9365205Scg /// 9465205Scg /// The group must not have been created with its flag set. 9565205Scg void addNode(ExplodedNode *N, ExplodedGraph &G); 9665205Scg 9765205Scg /// Replaces the single node in this group with a new node. 9865205Scg /// 9965205Scg /// Note that this should only be used when you know the group was not 10065205Scg /// created with its flag set, and that the group is empty or contains 10165205Scg /// only a single node. 10265205Scg void replaceNode(ExplodedNode *node); 10384658Scg 10465205Scg /// Returns whether this group was created with its flag set. 10565205Scg bool getFlag() const { 10665205Scg return (P & 1); 10765205Scg } 10865205Scg }; 10974763Scg 11065205Scg /// Location - The program location (within a function body) associated 11165205Scg /// with this node. 11265205Scg const ProgramPoint Location; 113193640Sariff 114193640Sariff /// State - The state associated with this node. 115193640Sariff ProgramStateRef State; 116193640Sariff 11765205Scg /// Preds - The predecessors of this node. 11865205Scg NodeGroup Preds; 11965205Scg 12074763Scg /// Succs - The successors of this node. 121154127Sariff NodeGroup Succs; 12265205Scg 12365205Scgpublic: 12465205Scg 12565205Scg explicit ExplodedNode(const ProgramPoint &loc, ProgramStateRef state, 12665205Scg bool IsSink) 12765205Scg : Location(loc), State(state), Succs(IsSink) { 128102620Ssobomax assert(isSink() == IsSink); 129102620Ssobomax } 130102620Ssobomax 131102620Ssobomax ~ExplodedNode() {} 13265205Scg 13365205Scg /// getLocation - Returns the edge associated with the given node. 13465205Scg ProgramPoint getLocation() const { return Location; } 13565205Scg 136102620Ssobomax const LocationContext *getLocationContext() const { 137102620Ssobomax return getLocation().getLocationContext(); 138102620Ssobomax } 139102620Ssobomax 14065205Scg const StackFrameContext *getStackFrame() const { 141102620Ssobomax return getLocationContext()->getCurrentStackFrame(); 142102620Ssobomax } 143102620Ssobomax 14465205Scg const Decl &getCodeDecl() const { return *getLocationContext()->getDecl(); } 145102620Ssobomax 146102620Ssobomax CFG &getCFG() const { return *getLocationContext()->getCFG(); } 147102620Ssobomax 14865205Scg ParentMap &getParentMap() const {return getLocationContext()->getParentMap();} 14965205Scg 15065205Scg template <typename T> 15165205Scg T &getAnalysis() const { 15265205Scg return *getLocationContext()->getAnalysis<T>(); 15365205Scg } 15465205Scg 15565205Scg const ProgramStateRef &getState() const { return State; } 15665205Scg 15765205Scg template <typename T> 15865205Scg Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION { 15965205Scg return Location.getAs<T>(); 16065205Scg } 16165205Scg 16265205Scg static void Profile(llvm::FoldingSetNodeID &ID, 16365205Scg const ProgramPoint &Loc, 16465205Scg const ProgramStateRef &state, 165102620Ssobomax bool IsSink) { 16684658Scg ID.Add(Loc); 167102620Ssobomax ID.AddPointer(state.getPtr()); 168102889Ssobomax ID.AddBoolean(IsSink); 169102889Ssobomax } 17065205Scg 17165205Scg void Profile(llvm::FoldingSetNodeID& ID) const { 17265205Scg // We avoid copy constructors by not using accessors. 17365205Scg Profile(ID, Location, State, isSink()); 17465205Scg } 17565205Scg 17665205Scg /// addPredeccessor - Adds a predecessor to the current node, and 17765205Scg /// in tandem add this node as a successor of the other node. 17865205Scg void addPredecessor(ExplodedNode *V, ExplodedGraph &G); 17965205Scg 18065205Scg unsigned succ_size() const { return Succs.size(); } 18165205Scg unsigned pred_size() const { return Preds.size(); } 18265205Scg bool succ_empty() const { return Succs.empty(); } 18365205Scg bool pred_empty() const { return Preds.empty(); } 18465205Scg 18565205Scg bool isSink() const { return Succs.getFlag(); } 18665205Scg 18765205Scg bool hasSinglePred() const { 18865205Scg return (pred_size() == 1); 18965205Scg } 19065205Scg 191108064Ssemenu ExplodedNode *getFirstPred() { 19265205Scg return pred_empty() ? NULL : *(pred_begin()); 19365205Scg } 194108064Ssemenu 195108064Ssemenu const ExplodedNode *getFirstPred() const { 19665205Scg return const_cast<ExplodedNode*>(this)->getFirstPred(); 197108064Ssemenu } 198108064Ssemenu 19965205Scg const ExplodedNode *getFirstSucc() const { 200108064Ssemenu return succ_empty() ? NULL : *(succ_begin()); 201108064Ssemenu } 20265205Scg 20365205Scg // Iterators over successor and predecessor vertices. 20465205Scg typedef ExplodedNode* const * succ_iterator; 20570134Scg typedef const ExplodedNode* const * const_succ_iterator; 20665205Scg typedef ExplodedNode* const * pred_iterator; 20765205Scg typedef const ExplodedNode* const * const_pred_iterator; 20865205Scg 20965205Scg pred_iterator pred_begin() { return Preds.begin(); } 21070134Scg pred_iterator pred_end() { return Preds.end(); } 21170134Scg 21265205Scg const_pred_iterator pred_begin() const { 21365205Scg return const_cast<ExplodedNode*>(this)->pred_begin(); 21465205Scg } 21565340Scg const_pred_iterator pred_end() const { 21665205Scg return const_cast<ExplodedNode*>(this)->pred_end(); 21765205Scg } 21865205Scg 21965205Scg succ_iterator succ_begin() { return Succs.begin(); } 22065205Scg succ_iterator succ_end() { return Succs.end(); } 22165205Scg 22265205Scg const_succ_iterator succ_begin() const { 22365205Scg return const_cast<ExplodedNode*>(this)->succ_begin(); 22465340Scg } 22565205Scg const_succ_iterator succ_end() const { 22665205Scg return const_cast<ExplodedNode*>(this)->succ_end(); 22765205Scg } 22865205Scg 22965205Scg // For debugging. 23065205Scg 23165205Scgpublic: 23265205Scg 23365205Scg class Auditor { 234102889Ssobomax public: 23565205Scg virtual ~Auditor(); 23665340Scg virtual void AddEdge(ExplodedNode *Src, ExplodedNode *Dst) = 0; 23765205Scg }; 23865205Scg 23965205Scg static void SetAuditor(Auditor* A); 24070134Scg 24170134Scgprivate: 24265205Scg void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); } 24365205Scg void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); } 24465205Scg}; 24565340Scg 24665205Scgtypedef llvm::DenseMap<const ExplodedNode *, const ExplodedNode *> 24765340Scg InterExplodedGraphMap; 24865205Scg 24965340Scgclass ExplodedGraph { 25065205Scgprotected: 25165205Scg friend class CoreEngine; 25265205Scg 25365205Scg // Type definitions. 25465205Scg typedef std::vector<ExplodedNode *> NodeVector; 25565205Scg 25665205Scg /// The roots of the simulation graph. Usually there will be only 25770134Scg /// one, but clients are free to establish multiple subgraphs within a single 25865205Scg /// SimulGraph. Moreover, these subgraphs can often merge when paths from 25965340Scg /// different roots reach the same state at the same program location. 26065205Scg NodeVector Roots; 26165205Scg 26265340Scg /// The nodes in the simulation graph which have been 26365205Scg /// specially marked as the endpoint of an abstract simulation path. 26465205Scg NodeVector EndNodes; 26565205Scg 26665205Scg /// Nodes - The nodes in the graph. 26765205Scg llvm::FoldingSet<ExplodedNode> Nodes; 26865205Scg 26965205Scg /// BVC - Allocator and context for allocating nodes and their predecessor 27070134Scg /// and successor groups. 27165205Scg BumpVectorContext BVC; 27265205Scg 27370134Scg /// NumNodes - The number of nodes in the graph. 27465205Scg unsigned NumNodes; 27565205Scg 27670134Scg /// A list of recently allocated nodes that can potentially be recycled. 27770134Scg NodeVector ChangedNodes; 27870134Scg 279227843Smarius /// A list of nodes that can be reused. 28070134Scg NodeVector FreeNodes; 28170134Scg 28270134Scg /// Determines how often nodes are reclaimed. 28370134Scg /// 28470134Scg /// If this is 0, nodes will never be reclaimed. 28565340Scg unsigned ReclaimNodeInterval; 28665340Scg 28765205Scg /// Counter to determine when to reclaim nodes. 28865205Scg unsigned ReclaimCounter; 28965205Scg 29065205Scgpublic: 29165205Scg 29265205Scg /// \brief Retrieve the node associated with a (Location,State) pair, 29365340Scg /// where the 'Location' is a ProgramPoint in the CFG. If no node for 29465205Scg /// this pair exists, it is created. IsNew is set to true if 29565340Scg /// the node was freshly created. 29665205Scg ExplodedNode *getNode(const ProgramPoint &L, ProgramStateRef State, 29765205Scg bool IsSink = false, 29865205Scg bool* IsNew = 0); 29965205Scg 30065205Scg ExplodedGraph* MakeEmptyGraph() const { 30165205Scg return new ExplodedGraph(); 30265205Scg } 30365205Scg 30465340Scg /// addRoot - Add an untyped node to the set of roots. 30565205Scg ExplodedNode *addRoot(ExplodedNode *V) { 30665205Scg Roots.push_back(V); 30765205Scg return V; 30865205Scg } 30965205Scg 31065205Scg /// addEndOfPath - Add an untyped node to the set of EOP nodes. 31165205Scg ExplodedNode *addEndOfPath(ExplodedNode *V) { 31265205Scg EndNodes.push_back(V); 31365340Scg return V; 31465205Scg } 31565205Scg 31665205Scg ExplodedGraph(); 31765205Scg 31865340Scg ~ExplodedGraph(); 31965205Scg 32065205Scg unsigned num_roots() const { return Roots.size(); } 32165205Scg unsigned num_eops() const { return EndNodes.size(); } 32265205Scg 32365340Scg bool empty() const { return NumNodes == 0; } 32465205Scg unsigned size() const { return NumNodes; } 32565205Scg 32665205Scg // Iterators. 32765205Scg typedef ExplodedNode NodeTy; 32870134Scg typedef llvm::FoldingSet<ExplodedNode> AllNodesTy; 32965205Scg typedef NodeVector::iterator roots_iterator; 33065205Scg typedef NodeVector::const_iterator const_roots_iterator; 33174763Scg typedef NodeVector::iterator eop_iterator; 33265205Scg typedef NodeVector::const_iterator const_eop_iterator; 33365205Scg typedef AllNodesTy::iterator node_iterator; 33465205Scg typedef AllNodesTy::const_iterator const_node_iterator; 33565340Scg 33665205Scg node_iterator nodes_begin() { return Nodes.begin(); } 33765205Scg 33865205Scg node_iterator nodes_end() { return Nodes.end(); } 33965205Scg 34065205Scg const_node_iterator nodes_begin() const { return Nodes.begin(); } 341168847Sariff 342136469Syongari const_node_iterator nodes_end() const { return Nodes.end(); } 34365205Scg 34465205Scg roots_iterator roots_begin() { return Roots.begin(); } 34565205Scg 34665205Scg roots_iterator roots_end() { return Roots.end(); } 34770134Scg 34865205Scg const_roots_iterator roots_begin() const { return Roots.begin(); } 34965205Scg 35065205Scg const_roots_iterator roots_end() const { return Roots.end(); } 35165340Scg 35265205Scg eop_iterator eop_begin() { return EndNodes.begin(); } 353193640Sariff 354193640Sariff eop_iterator eop_end() { return EndNodes.end(); } 35565205Scg 35665205Scg const_eop_iterator eop_begin() const { return EndNodes.begin(); } 35765340Scg 35865205Scg const_eop_iterator eop_end() const { return EndNodes.end(); } 359193640Sariff 360193640Sariff llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); } 36165205Scg BumpVectorContext &getNodeAllocator() { return BVC; } 36265205Scg 36365205Scg typedef llvm::DenseMap<const ExplodedNode*, ExplodedNode*> NodeMap; 36465340Scg 36565205Scg /// Creates a trimmed version of the graph that only contains paths leading 366193640Sariff /// to the given nodes. 36765205Scg /// 36865205Scg /// \param Nodes The nodes which must appear in the final graph. Presumably 36965205Scg /// these are end-of-path nodes (i.e. they have no successors). 37065340Scg /// \param[out] ForwardMap A optional map from nodes in this graph to nodes in 37165205Scg /// the returned graph. 37265205Scg /// \param[out] InverseMap An optional map from nodes in the returned graph to 37365205Scg /// nodes in this graph. 37465205Scg /// \returns The trimmed graph 375193640Sariff ExplodedGraph *trim(ArrayRef<const NodeTy *> Nodes, 376193640Sariff InterExplodedGraphMap *ForwardMap = 0, 37765205Scg InterExplodedGraphMap *InverseMap = 0) const; 37865340Scg 37965340Scg /// Enable tracking of recently allocated nodes for potential reclamation 38065340Scg /// when calling reclaimRecentlyAllocatedNodes(). 38165340Scg void enableNodeReclamation(unsigned Interval) { 38265340Scg ReclaimCounter = ReclaimNodeInterval = Interval; 38365340Scg } 38465340Scg 38565340Scg /// Reclaim "uninteresting" nodes created since the last time this method 38665340Scg /// was called. 38765340Scg void reclaimRecentlyAllocatedNodes(); 38865340Scg 38965205Scg /// \brief Returns true if nodes for the given expression kind are always 39065205Scg /// kept around. 39165205Scg static bool isInterestingLValueExpr(const Expr *Ex); 392193640Sariff 39370134Scgprivate: 39465205Scg bool shouldCollect(const ExplodedNode *node); 39565205Scg void collectNode(ExplodedNode *node); 39665205Scg}; 39765205Scg 39865340Scgclass ExplodedNodeSet { 39965340Scg typedef llvm::SmallPtrSet<ExplodedNode*,5> ImplTy; 40065205Scg ImplTy Impl; 40165340Scg 40265205Scgpublic: 40365205Scg ExplodedNodeSet(ExplodedNode *N) { 40465205Scg assert (N && !static_cast<ExplodedNode*>(N)->isSink()); 40565205Scg Impl.insert(N); 40665205Scg } 40765340Scg 40865205Scg ExplodedNodeSet() {} 40965205Scg 41065205Scg inline void Add(ExplodedNode *N) { 41165205Scg if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N); 41265205Scg } 41365340Scg 41465205Scg typedef ImplTy::iterator iterator; 41565340Scg typedef ImplTy::const_iterator const_iterator; 41665205Scg 41765205Scg unsigned size() const { return Impl.size(); } 41865205Scg bool empty() const { return Impl.empty(); } 419193640Sariff bool erase(ExplodedNode *N) { return Impl.erase(N); } 42070134Scg 42165205Scg void clear() { Impl.clear(); } 42265205Scg void insert(const ExplodedNodeSet &S) { 42365205Scg assert(&S != this); 42465340Scg if (empty()) 425169762Sjoel Impl = S.Impl; 426169762Sjoel else 427169762Sjoel Impl.insert(S.begin(), S.end()); 428169762Sjoel } 429169762Sjoel 430169762Sjoel inline iterator begin() { return Impl.begin(); } 43165205Scg inline iterator end() { return Impl.end(); } 43265340Scg 433169762Sjoel inline const_iterator begin() const { return Impl.begin(); } 43465205Scg inline const_iterator end() const { return Impl.end(); } 43565340Scg}; 43665205Scg 43765205Scg} // end GR namespace 43865205Scg 43965205Scg} // end clang namespace 44065205Scg 44165205Scg// GraphTraits 44270134Scg 44365205Scgnamespace llvm { 44465205Scg template<> struct GraphTraits<clang::ento::ExplodedNode*> { 44565205Scg typedef clang::ento::ExplodedNode NodeType; 446111183Scognet typedef NodeType::succ_iterator ChildIteratorType; 44765205Scg typedef llvm::df_iterator<NodeType*> nodes_iterator; 44865340Scg 44965205Scg static inline NodeType* getEntryNode(NodeType* N) { 45065340Scg return N; 451170521Sariff } 45265205Scg 45365340Scg static inline ChildIteratorType child_begin(NodeType* N) { 45465205Scg return N->succ_begin(); 45565205Scg } 45665340Scg 45765205Scg static inline ChildIteratorType child_end(NodeType* N) { 45865205Scg return N->succ_end(); 45965205Scg } 46065205Scg 46165205Scg static inline nodes_iterator nodes_begin(NodeType* N) { 46265205Scg return df_begin(N); 46365205Scg } 46465340Scg 46565205Scg static inline nodes_iterator nodes_end(NodeType* N) { 46665205Scg return df_end(N); 46765205Scg } 46865205Scg }; 46965205Scg 47065205Scg template<> struct GraphTraits<const clang::ento::ExplodedNode*> { 47165205Scg typedef const clang::ento::ExplodedNode NodeType; 47265205Scg typedef NodeType::const_succ_iterator ChildIteratorType; 47365205Scg typedef llvm::df_iterator<NodeType*> nodes_iterator; 47465205Scg 47565205Scg static inline NodeType* getEntryNode(NodeType* N) { 47665205Scg return N; 47765205Scg } 47865205Scg 47965205Scg static inline ChildIteratorType child_begin(NodeType* N) { 48065205Scg return N->succ_begin(); 48165340Scg } 48265340Scg 48365205Scg static inline ChildIteratorType child_end(NodeType* N) { 48465205Scg return N->succ_end(); 48565205Scg } 48665205Scg 48765205Scg static inline nodes_iterator nodes_begin(NodeType* N) { 48865205Scg return df_begin(N); 48965205Scg } 49065205Scg 49165205Scg static inline nodes_iterator nodes_end(NodeType* N) { 49265340Scg return df_end(N); 49365205Scg } 49465205Scg }; 49565205Scg 49665205Scg} // end llvm namespace 497193640Sariff 49870134Scg#endif 49965205Scg