ExplodedGraph.h revision 314564
1//=-- ExplodedGraph.h - 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// See "Precise interprocedural dataflow analysis via graph reachability" 13// by Reps, Horwitz, and Sagiv 14// (http://portal.acm.org/citation.cfm?id=199462) for the definition of an 15// exploded graph. 16// 17//===----------------------------------------------------------------------===// 18 19#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H 20#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H 21 22#include "clang/AST/Decl.h" 23#include "clang/Analysis/AnalysisContext.h" 24#include "clang/Analysis/ProgramPoint.h" 25#include "clang/Analysis/Support/BumpVector.h" 26#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 27#include "llvm/ADT/DepthFirstIterator.h" 28#include "llvm/ADT/FoldingSet.h" 29#include "llvm/ADT/GraphTraits.h" 30#include "llvm/ADT/SmallPtrSet.h" 31#include "llvm/Support/Allocator.h" 32#include "llvm/Support/Casting.h" 33#include <memory> 34#include <utility> 35#include <vector> 36 37namespace clang { 38 39class CFG; 40 41namespace ento { 42 43class ExplodedGraph; 44 45//===----------------------------------------------------------------------===// 46// ExplodedGraph "implementation" classes. These classes are not typed to 47// contain a specific kind of state. Typed-specialized versions are defined 48// on top of these classes. 49//===----------------------------------------------------------------------===// 50 51// ExplodedNode is not constified all over the engine because we need to add 52// successors to it at any time after creating it. 53 54class ExplodedNode : public llvm::FoldingSetNode { 55 friend class ExplodedGraph; 56 friend class CoreEngine; 57 friend class NodeBuilder; 58 friend class BranchNodeBuilder; 59 friend class IndirectGotoNodeBuilder; 60 friend class SwitchNodeBuilder; 61 friend class EndOfFunctionNodeBuilder; 62 63 /// Efficiently stores a list of ExplodedNodes, or an optional flag. 64 /// 65 /// NodeGroup provides opaque storage for a list of ExplodedNodes, optimizing 66 /// for the case when there is only one node in the group. This is a fairly 67 /// common case in an ExplodedGraph, where most nodes have only one 68 /// predecessor and many have only one successor. It can also be used to 69 /// store a flag rather than a node list, which ExplodedNode uses to mark 70 /// whether a node is a sink. If the flag is set, the group is implicitly 71 /// empty and no nodes may be added. 72 class NodeGroup { 73 // Conceptually a discriminated union. If the low bit is set, the node is 74 // a sink. If the low bit is not set, the pointer refers to the storage 75 // for the nodes in the group. 76 // This is not a PointerIntPair in order to keep the storage type opaque. 77 uintptr_t P; 78 79 public: 80 NodeGroup(bool Flag = false) : P(Flag) { 81 assert(getFlag() == Flag); 82 } 83 84 ExplodedNode * const *begin() const; 85 86 ExplodedNode * const *end() const; 87 88 unsigned size() const; 89 90 bool empty() const { return P == 0 || getFlag() != 0; } 91 92 /// Adds a node to the list. 93 /// 94 /// The group must not have been created with its flag set. 95 void addNode(ExplodedNode *N, ExplodedGraph &G); 96 97 /// Replaces the single node in this group with a new node. 98 /// 99 /// Note that this should only be used when you know the group was not 100 /// created with its flag set, and that the group is empty or contains 101 /// only a single node. 102 void replaceNode(ExplodedNode *node); 103 104 /// Returns whether this group was created with its flag set. 105 bool getFlag() const { 106 return (P & 1); 107 } 108 }; 109 110 /// Location - The program location (within a function body) associated 111 /// with this node. 112 const ProgramPoint Location; 113 114 /// State - The state associated with this node. 115 ProgramStateRef State; 116 117 /// Preds - The predecessors of this node. 118 NodeGroup Preds; 119 120 /// Succs - The successors of this node. 121 NodeGroup Succs; 122 123public: 124 explicit ExplodedNode(const ProgramPoint &loc, ProgramStateRef state, 125 bool IsSink) 126 : Location(loc), State(std::move(state)), Succs(IsSink) { 127 assert(isSink() == IsSink); 128 } 129 130 /// getLocation - Returns the edge associated with the given node. 131 ProgramPoint getLocation() const { return Location; } 132 133 const LocationContext *getLocationContext() const { 134 return getLocation().getLocationContext(); 135 } 136 137 const StackFrameContext *getStackFrame() const { 138 return getLocationContext()->getCurrentStackFrame(); 139 } 140 141 const Decl &getCodeDecl() const { return *getLocationContext()->getDecl(); } 142 143 CFG &getCFG() const { return *getLocationContext()->getCFG(); } 144 145 ParentMap &getParentMap() const {return getLocationContext()->getParentMap();} 146 147 template <typename T> 148 T &getAnalysis() const { 149 return *getLocationContext()->getAnalysis<T>(); 150 } 151 152 const ProgramStateRef &getState() const { return State; } 153 154 template <typename T> 155 Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION { 156 return Location.getAs<T>(); 157 } 158 159 static void Profile(llvm::FoldingSetNodeID &ID, 160 const ProgramPoint &Loc, 161 const ProgramStateRef &state, 162 bool IsSink) { 163 ID.Add(Loc); 164 ID.AddPointer(state.get()); 165 ID.AddBoolean(IsSink); 166 } 167 168 void Profile(llvm::FoldingSetNodeID& ID) const { 169 // We avoid copy constructors by not using accessors. 170 Profile(ID, Location, State, isSink()); 171 } 172 173 /// addPredeccessor - Adds a predecessor to the current node, and 174 /// in tandem add this node as a successor of the other node. 175 void addPredecessor(ExplodedNode *V, ExplodedGraph &G); 176 177 unsigned succ_size() const { return Succs.size(); } 178 unsigned pred_size() const { return Preds.size(); } 179 bool succ_empty() const { return Succs.empty(); } 180 bool pred_empty() const { return Preds.empty(); } 181 182 bool isSink() const { return Succs.getFlag(); } 183 184 bool hasSinglePred() const { 185 return (pred_size() == 1); 186 } 187 188 ExplodedNode *getFirstPred() { 189 return pred_empty() ? nullptr : *(pred_begin()); 190 } 191 192 const ExplodedNode *getFirstPred() const { 193 return const_cast<ExplodedNode*>(this)->getFirstPred(); 194 } 195 196 const ExplodedNode *getFirstSucc() const { 197 return succ_empty() ? nullptr : *(succ_begin()); 198 } 199 200 // Iterators over successor and predecessor vertices. 201 typedef ExplodedNode* const * succ_iterator; 202 typedef const ExplodedNode* const * const_succ_iterator; 203 typedef ExplodedNode* const * pred_iterator; 204 typedef const ExplodedNode* const * const_pred_iterator; 205 206 pred_iterator pred_begin() { return Preds.begin(); } 207 pred_iterator pred_end() { return Preds.end(); } 208 209 const_pred_iterator pred_begin() const { 210 return const_cast<ExplodedNode*>(this)->pred_begin(); 211 } 212 const_pred_iterator pred_end() const { 213 return const_cast<ExplodedNode*>(this)->pred_end(); 214 } 215 216 succ_iterator succ_begin() { return Succs.begin(); } 217 succ_iterator succ_end() { return Succs.end(); } 218 219 const_succ_iterator succ_begin() const { 220 return const_cast<ExplodedNode*>(this)->succ_begin(); 221 } 222 const_succ_iterator succ_end() const { 223 return const_cast<ExplodedNode*>(this)->succ_end(); 224 } 225 226 // For debugging. 227 228public: 229 230 class Auditor { 231 public: 232 virtual ~Auditor(); 233 virtual void AddEdge(ExplodedNode *Src, ExplodedNode *Dst) = 0; 234 }; 235 236 static void SetAuditor(Auditor* A); 237 238private: 239 void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); } 240 void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); } 241}; 242 243typedef llvm::DenseMap<const ExplodedNode *, const ExplodedNode *> 244 InterExplodedGraphMap; 245 246class ExplodedGraph { 247protected: 248 friend class CoreEngine; 249 250 // Type definitions. 251 typedef std::vector<ExplodedNode *> NodeVector; 252 253 /// The roots of the simulation graph. Usually there will be only 254 /// one, but clients are free to establish multiple subgraphs within a single 255 /// SimulGraph. Moreover, these subgraphs can often merge when paths from 256 /// different roots reach the same state at the same program location. 257 NodeVector Roots; 258 259 /// The nodes in the simulation graph which have been 260 /// specially marked as the endpoint of an abstract simulation path. 261 NodeVector EndNodes; 262 263 /// Nodes - The nodes in the graph. 264 llvm::FoldingSet<ExplodedNode> Nodes; 265 266 /// BVC - Allocator and context for allocating nodes and their predecessor 267 /// and successor groups. 268 BumpVectorContext BVC; 269 270 /// NumNodes - The number of nodes in the graph. 271 unsigned NumNodes; 272 273 /// A list of recently allocated nodes that can potentially be recycled. 274 NodeVector ChangedNodes; 275 276 /// A list of nodes that can be reused. 277 NodeVector FreeNodes; 278 279 /// Determines how often nodes are reclaimed. 280 /// 281 /// If this is 0, nodes will never be reclaimed. 282 unsigned ReclaimNodeInterval; 283 284 /// Counter to determine when to reclaim nodes. 285 unsigned ReclaimCounter; 286 287public: 288 289 /// \brief Retrieve the node associated with a (Location,State) pair, 290 /// where the 'Location' is a ProgramPoint in the CFG. If no node for 291 /// this pair exists, it is created. IsNew is set to true if 292 /// the node was freshly created. 293 ExplodedNode *getNode(const ProgramPoint &L, ProgramStateRef State, 294 bool IsSink = false, 295 bool* IsNew = nullptr); 296 297 /// \brief Create a node for a (Location, State) pair, 298 /// but don't store it for deduplication later. This 299 /// is useful when copying an already completed 300 /// ExplodedGraph for further processing. 301 ExplodedNode *createUncachedNode(const ProgramPoint &L, 302 ProgramStateRef State, 303 bool IsSink = false); 304 305 std::unique_ptr<ExplodedGraph> MakeEmptyGraph() const { 306 return llvm::make_unique<ExplodedGraph>(); 307 } 308 309 /// addRoot - Add an untyped node to the set of roots. 310 ExplodedNode *addRoot(ExplodedNode *V) { 311 Roots.push_back(V); 312 return V; 313 } 314 315 /// addEndOfPath - Add an untyped node to the set of EOP nodes. 316 ExplodedNode *addEndOfPath(ExplodedNode *V) { 317 EndNodes.push_back(V); 318 return V; 319 } 320 321 ExplodedGraph(); 322 323 ~ExplodedGraph(); 324 325 unsigned num_roots() const { return Roots.size(); } 326 unsigned num_eops() const { return EndNodes.size(); } 327 328 bool empty() const { return NumNodes == 0; } 329 unsigned size() const { return NumNodes; } 330 331 void reserve(unsigned NodeCount) { Nodes.reserve(NodeCount); } 332 333 // Iterators. 334 typedef ExplodedNode NodeTy; 335 typedef llvm::FoldingSet<ExplodedNode> AllNodesTy; 336 typedef NodeVector::iterator roots_iterator; 337 typedef NodeVector::const_iterator const_roots_iterator; 338 typedef NodeVector::iterator eop_iterator; 339 typedef NodeVector::const_iterator const_eop_iterator; 340 typedef AllNodesTy::iterator node_iterator; 341 typedef AllNodesTy::const_iterator const_node_iterator; 342 343 node_iterator nodes_begin() { return Nodes.begin(); } 344 345 node_iterator nodes_end() { return Nodes.end(); } 346 347 const_node_iterator nodes_begin() const { return Nodes.begin(); } 348 349 const_node_iterator nodes_end() const { return Nodes.end(); } 350 351 roots_iterator roots_begin() { return Roots.begin(); } 352 353 roots_iterator roots_end() { return Roots.end(); } 354 355 const_roots_iterator roots_begin() const { return Roots.begin(); } 356 357 const_roots_iterator roots_end() const { return Roots.end(); } 358 359 eop_iterator eop_begin() { return EndNodes.begin(); } 360 361 eop_iterator eop_end() { return EndNodes.end(); } 362 363 const_eop_iterator eop_begin() const { return EndNodes.begin(); } 364 365 const_eop_iterator eop_end() const { return EndNodes.end(); } 366 367 llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); } 368 BumpVectorContext &getNodeAllocator() { return BVC; } 369 370 typedef llvm::DenseMap<const ExplodedNode*, ExplodedNode*> NodeMap; 371 372 /// Creates a trimmed version of the graph that only contains paths leading 373 /// to the given nodes. 374 /// 375 /// \param Nodes The nodes which must appear in the final graph. Presumably 376 /// these are end-of-path nodes (i.e. they have no successors). 377 /// \param[out] ForwardMap A optional map from nodes in this graph to nodes in 378 /// the returned graph. 379 /// \param[out] InverseMap An optional map from nodes in the returned graph to 380 /// nodes in this graph. 381 /// \returns The trimmed graph 382 std::unique_ptr<ExplodedGraph> 383 trim(ArrayRef<const NodeTy *> Nodes, 384 InterExplodedGraphMap *ForwardMap = nullptr, 385 InterExplodedGraphMap *InverseMap = nullptr) const; 386 387 /// Enable tracking of recently allocated nodes for potential reclamation 388 /// when calling reclaimRecentlyAllocatedNodes(). 389 void enableNodeReclamation(unsigned Interval) { 390 ReclaimCounter = ReclaimNodeInterval = Interval; 391 } 392 393 /// Reclaim "uninteresting" nodes created since the last time this method 394 /// was called. 395 void reclaimRecentlyAllocatedNodes(); 396 397 /// \brief Returns true if nodes for the given expression kind are always 398 /// kept around. 399 static bool isInterestingLValueExpr(const Expr *Ex); 400 401private: 402 bool shouldCollect(const ExplodedNode *node); 403 void collectNode(ExplodedNode *node); 404}; 405 406class ExplodedNodeSet { 407 typedef llvm::SmallPtrSet<ExplodedNode*,5> ImplTy; 408 ImplTy Impl; 409 410public: 411 ExplodedNodeSet(ExplodedNode *N) { 412 assert (N && !static_cast<ExplodedNode*>(N)->isSink()); 413 Impl.insert(N); 414 } 415 416 ExplodedNodeSet() {} 417 418 inline void Add(ExplodedNode *N) { 419 if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N); 420 } 421 422 typedef ImplTy::iterator iterator; 423 typedef ImplTy::const_iterator const_iterator; 424 425 unsigned size() const { return Impl.size(); } 426 bool empty() const { return Impl.empty(); } 427 bool erase(ExplodedNode *N) { return Impl.erase(N); } 428 429 void clear() { Impl.clear(); } 430 void insert(const ExplodedNodeSet &S) { 431 assert(&S != this); 432 if (empty()) 433 Impl = S.Impl; 434 else 435 Impl.insert(S.begin(), S.end()); 436 } 437 438 inline iterator begin() { return Impl.begin(); } 439 inline iterator end() { return Impl.end(); } 440 441 inline const_iterator begin() const { return Impl.begin(); } 442 inline const_iterator end() const { return Impl.end(); } 443}; 444 445} // end GR namespace 446 447} // end clang namespace 448 449// GraphTraits 450 451namespace llvm { 452 template<> struct GraphTraits<clang::ento::ExplodedNode*> { 453 typedef clang::ento::ExplodedNode *NodeRef; 454 typedef clang::ento::ExplodedNode::succ_iterator ChildIteratorType; 455 typedef llvm::df_iterator<NodeRef> nodes_iterator; 456 457 static NodeRef getEntryNode(NodeRef N) { return N; } 458 459 static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); } 460 461 static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); } 462 463 static nodes_iterator nodes_begin(NodeRef N) { return df_begin(N); } 464 465 static nodes_iterator nodes_end(NodeRef N) { return df_end(N); } 466 }; 467 468 template<> struct GraphTraits<const clang::ento::ExplodedNode*> { 469 typedef const clang::ento::ExplodedNode *NodeRef; 470 typedef clang::ento::ExplodedNode::const_succ_iterator ChildIteratorType; 471 typedef llvm::df_iterator<NodeRef> nodes_iterator; 472 473 static NodeRef getEntryNode(NodeRef N) { return N; } 474 475 static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); } 476 477 static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); } 478 479 static nodes_iterator nodes_begin(NodeRef N) { return df_begin(N); } 480 481 static nodes_iterator nodes_end(NodeRef N) { return df_end(N); } 482 }; 483 484} // end llvm namespace 485 486#endif 487