contrib/llvm/tools/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h

   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_GR_EXPLODEDGRAPH
  20 #define LLVM_CLANG_GR_EXPLODEDGRAPH
  21
  22 #include "clang/Analysis/ProgramPoint.h"
  23 #include "clang/Analysis/AnalysisContext.h"
  24 #include "clang/AST/Decl.h"
  25 #include "llvm/ADT/SmallVector.h"
  26 #include "llvm/ADT/FoldingSet.h"
  27 #include "llvm/ADT/SmallPtrSet.h"
  28 #include "llvm/Support/Allocator.h"
  29 #include "llvm/ADT/OwningPtr.h"
  30 #include "llvm/ADT/GraphTraits.h"
  31 #include "llvm/ADT/DepthFirstIterator.h"
  32 #include "llvm/Support/Casting.h"
  33 #include "clang/Analysis/Support/BumpVector.h"
  34 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
  35 #include <vector>
  36
  37 namespace clang {
  38
  39 class CFG;
  40
  41 namespace ento {
  42
  43 class 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
  54 class 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
 123 public:
 124
 125   explicit ExplodedNode(const ProgramPoint &loc, ProgramStateRef state,
 126                         bool IsSink)
 127     : Location(loc), State(state), Succs(IsSink) {
 128     assert(isSink() == IsSink);
 129   }
 130
 131   ~ExplodedNode() {}
 132
 133   /// getLocation - Returns the edge associated with the given node.
 134   ProgramPoint getLocation() const { return Location; }
 135
 136   const LocationContext *getLocationContext() const {
 137     return getLocation().getLocationContext();
 138   }
 139
 140   const StackFrameContext *getStackFrame() const {
 141     return getLocationContext()->getCurrentStackFrame();
 142   }
 143
 144   const Decl &getCodeDecl() const { return *getLocationContext()->getDecl(); }
 145
 146   CFG &getCFG() const { return *getLocationContext()->getCFG(); }
 147
 148   ParentMap &getParentMap() const {return getLocationContext()->getParentMap();}
 149
 150   template <typename T>
 151   T &getAnalysis() const {
 152     return *getLocationContext()->getAnalysis<T>();
 153   }
 154
 155   ProgramStateRef getState() const { return State; }
 156
 157   template <typename T>
 158   const T* getLocationAs() const { return llvm::dyn_cast<T>(&Location); }
 159
 160   static void Profile(llvm::FoldingSetNodeID &ID,
 161                       const ProgramPoint &Loc,
 162                       const ProgramStateRef &state,
 163                       bool IsSink) {
 164     ID.Add(Loc);
 165     ID.AddPointer(state.getPtr());
 166     ID.AddBoolean(IsSink);
 167   }
 168
 169   void Profile(llvm::FoldingSetNodeID& ID) const {
 170     Profile(ID, getLocation(), getState(), 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() ? NULL : *(pred_begin());
 190   }
 191
 192   const ExplodedNode *getFirstPred() const {
 193     return const_cast<ExplodedNode*>(this)->getFirstPred();
 194   }
 195
 196   // Iterators over successor and predecessor vertices.
 197   typedef ExplodedNode*       const *       succ_iterator;
 198   typedef const ExplodedNode* const * const_succ_iterator;
 199   typedef ExplodedNode*       const *       pred_iterator;
 200   typedef const ExplodedNode* const * const_pred_iterator;
 201
 202   pred_iterator pred_begin() { return Preds.begin(); }
 203   pred_iterator pred_end() { return Preds.end(); }
 204
 205   const_pred_iterator pred_begin() const {
 206     return const_cast<ExplodedNode*>(this)->pred_begin();
 207   }
 208   const_pred_iterator pred_end() const {
 209     return const_cast<ExplodedNode*>(this)->pred_end();
 210   }
 211
 212   succ_iterator succ_begin() { return Succs.begin(); }
 213   succ_iterator succ_end() { return Succs.end(); }
 214
 215   const_succ_iterator succ_begin() const {
 216     return const_cast<ExplodedNode*>(this)->succ_begin();
 217   }
 218   const_succ_iterator succ_end() const {
 219     return const_cast<ExplodedNode*>(this)->succ_end();
 220   }
 221
 222   // For debugging.
 223
 224 public:
 225
 226   class Auditor {
 227   public:
 228     virtual ~Auditor();
 229     virtual void AddEdge(ExplodedNode *Src, ExplodedNode *Dst) = 0;
 230   };
 231
 232   static void SetAuditor(Auditor* A);
 233
 234 private:
 235   void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); }
 236   void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); }
 237 };
 238
 239 // FIXME: Is this class necessary?
 240 class InterExplodedGraphMap {
 241   virtual void anchor();
 242   llvm::DenseMap<const ExplodedNode*, ExplodedNode*> M;
 243   friend class ExplodedGraph;
 244
 245 public:
 246   ExplodedNode *getMappedNode(const ExplodedNode *N) const;
 247
 248   InterExplodedGraphMap() {}
 249   virtual ~InterExplodedGraphMap() {}
 250 };
 251
 252 class ExplodedGraph {
 253 protected:
 254   friend class CoreEngine;
 255
 256   // Type definitions.
 257   typedef std::vector<ExplodedNode *> NodeVector;
 258
 259   /// The roots of the simulation graph. Usually there will be only
 260   /// one, but clients are free to establish multiple subgraphs within a single
 261   /// SimulGraph. Moreover, these subgraphs can often merge when paths from
 262   /// different roots reach the same state at the same program location.
 263   NodeVector Roots;
 264
 265   /// The nodes in the simulation graph which have been
 266   /// specially marked as the endpoint of an abstract simulation path.
 267   NodeVector EndNodes;
 268
 269   /// Nodes - The nodes in the graph.
 270   llvm::FoldingSet<ExplodedNode> Nodes;
 271
 272   /// BVC - Allocator and context for allocating nodes and their predecessor
 273   /// and successor groups.
 274   BumpVectorContext BVC;
 275
 276   /// NumNodes - The number of nodes in the graph.
 277   unsigned NumNodes;
 278
 279   /// A list of recently allocated nodes that can potentially be recycled.
 280   NodeVector ChangedNodes;
 281
 282   /// A list of nodes that can be reused.
 283   NodeVector FreeNodes;
 284
 285   /// Determines how often nodes are reclaimed.
 286   ///
 287   /// If this is 0, nodes will never be reclaimed.
 288   unsigned ReclaimNodeInterval;
 289
 290   /// Counter to determine when to reclaim nodes.
 291   unsigned ReclaimCounter;
 292
 293 public:
 294
 295   /// \brief Retrieve the node associated with a (Location,State) pair,
 296   ///  where the 'Location' is a ProgramPoint in the CFG.  If no node for
 297   ///  this pair exists, it is created. IsNew is set to true if
 298   ///  the node was freshly created.
 299   ExplodedNode *getNode(const ProgramPoint &L, ProgramStateRef State,
 300                         bool IsSink = false,
 301                         bool* IsNew = 0);
 302
 303   ExplodedGraph* MakeEmptyGraph() const {
 304     return new ExplodedGraph();
 305   }
 306
 307   /// addRoot - Add an untyped node to the set of roots.
 308   ExplodedNode *addRoot(ExplodedNode *V) {
 309     Roots.push_back(V);
 310     return V;
 311   }
 312
 313   /// addEndOfPath - Add an untyped node to the set of EOP nodes.
 314   ExplodedNode *addEndOfPath(ExplodedNode *V) {
 315     EndNodes.push_back(V);
 316     return V;
 317   }
 318
 319   ExplodedGraph();
 320
 321   ~ExplodedGraph();
 322
 323   unsigned num_roots() const { return Roots.size(); }
 324   unsigned num_eops() const { return EndNodes.size(); }
 325
 326   bool empty() const { return NumNodes == 0; }
 327   unsigned size() const { return NumNodes; }
 328
 329   // Iterators.
 330   typedef ExplodedNode                        NodeTy;
 331   typedef llvm::FoldingSet<ExplodedNode>      AllNodesTy;
 332   typedef NodeVector::iterator                roots_iterator;
 333   typedef NodeVector::const_iterator          const_roots_iterator;
 334   typedef NodeVector::iterator                eop_iterator;
 335   typedef NodeVector::const_iterator          const_eop_iterator;
 336   typedef AllNodesTy::iterator                node_iterator;
 337   typedef AllNodesTy::const_iterator          const_node_iterator;
 338
 339   node_iterator nodes_begin() { return Nodes.begin(); }
 340
 341   node_iterator nodes_end() { return Nodes.end(); }
 342
 343   const_node_iterator nodes_begin() const { return Nodes.begin(); }
 344
 345   const_node_iterator nodes_end() const { return Nodes.end(); }
 346
 347   roots_iterator roots_begin() { return Roots.begin(); }
 348
 349   roots_iterator roots_end() { return Roots.end(); }
 350
 351   const_roots_iterator roots_begin() const { return Roots.begin(); }
 352
 353   const_roots_iterator roots_end() const { return Roots.end(); }
 354
 355   eop_iterator eop_begin() { return EndNodes.begin(); }
 356
 357   eop_iterator eop_end() { return EndNodes.end(); }
 358
 359   const_eop_iterator eop_begin() const { return EndNodes.begin(); }
 360
 361   const_eop_iterator eop_end() const { return EndNodes.end(); }
 362
 363   llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); }
 364   BumpVectorContext &getNodeAllocator() { return BVC; }
 365
 366   typedef llvm::DenseMap<const ExplodedNode*, ExplodedNode*> NodeMap;
 367
 368   std::pair<ExplodedGraph*, InterExplodedGraphMap*>
 369   Trim(const NodeTy* const* NBeg, const NodeTy* const* NEnd,
 370        llvm::DenseMap<const void*, const void*> *InverseMap = 0) const;
 371
 372   ExplodedGraph* TrimInternal(const ExplodedNode* const * NBeg,
 373                               const ExplodedNode* const * NEnd,
 374                               InterExplodedGraphMap *M,
 375                     llvm::DenseMap<const void*, const void*> *InverseMap) const;
 376
 377   /// Enable tracking of recently allocated nodes for potential reclamation
 378   /// when calling reclaimRecentlyAllocatedNodes().
 379   void enableNodeReclamation(unsigned Interval) {
 380     ReclaimCounter = ReclaimNodeInterval = Interval;
 381   }
 382
 383   /// Reclaim "uninteresting" nodes created since the last time this method
 384   /// was called.
 385   void reclaimRecentlyAllocatedNodes();
 386
 387 private:
 388   bool shouldCollect(const ExplodedNode *node);
 389   void collectNode(ExplodedNode *node);
 390 };
 391
 392 class ExplodedNodeSet {
 393   typedef llvm::SmallPtrSet<ExplodedNode*,5> ImplTy;
 394   ImplTy Impl;
 395
 396 public:
 397   ExplodedNodeSet(ExplodedNode *N) {
 398     assert (N && !static_cast<ExplodedNode*>(N)->isSink());
 399     Impl.insert(N);
 400   }
 401
 402   ExplodedNodeSet() {}
 403
 404   inline void Add(ExplodedNode *N) {
 405     if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N);
 406   }
 407
 408   typedef ImplTy::iterator       iterator;
 409   typedef ImplTy::const_iterator const_iterator;
 410
 411   unsigned size() const { return Impl.size();  }
 412   bool empty()    const { return Impl.empty(); }
 413   bool erase(ExplodedNode *N) { return Impl.erase(N); }
 414
 415   void clear() { Impl.clear(); }
 416   void insert(const ExplodedNodeSet &S) {
 417     assert(&S != this);
 418     if (empty())
 419       Impl = S.Impl;
 420     else
 421       Impl.insert(S.begin(), S.end());
 422   }
 423
 424   inline iterator begin() { return Impl.begin(); }
 425   inline iterator end()   { return Impl.end();   }
 426
 427   inline const_iterator begin() const { return Impl.begin(); }
 428   inline const_iterator end()   const { return Impl.end();   }
 429 };
 430
 431 } // end GR namespace
 432
 433 } // end clang namespace
 434
 435 // GraphTraits
 436
 437 namespace llvm {
 438   template<> struct GraphTraits<clang::ento::ExplodedNode*> {
 439     typedef clang::ento::ExplodedNode NodeType;
 440     typedef NodeType::succ_iterator  ChildIteratorType;
 441     typedef llvm::df_iterator<NodeType*>      nodes_iterator;
 442
 443     static inline NodeType* getEntryNode(NodeType* N) {
 444       return N;
 445     }
 446
 447     static inline ChildIteratorType child_begin(NodeType* N) {
 448       return N->succ_begin();
 449     }
 450
 451     static inline ChildIteratorType child_end(NodeType* N) {
 452       return N->succ_end();
 453     }
 454
 455     static inline nodes_iterator nodes_begin(NodeType* N) {
 456       return df_begin(N);
 457     }
 458
 459     static inline nodes_iterator nodes_end(NodeType* N) {
 460       return df_end(N);
 461     }
 462   };
 463
 464   template<> struct GraphTraits<const clang::ento::ExplodedNode*> {
 465     typedef const clang::ento::ExplodedNode NodeType;
 466     typedef NodeType::const_succ_iterator   ChildIteratorType;
 467     typedef llvm::df_iterator<NodeType*>       nodes_iterator;
 468
 469     static inline NodeType* getEntryNode(NodeType* N) {
 470       return N;
 471     }
 472
 473     static inline ChildIteratorType child_begin(NodeType* N) {
 474       return N->succ_begin();
 475     }
 476
 477     static inline ChildIteratorType child_end(NodeType* N) {
 478       return N->succ_end();
 479     }
 480
 481     static inline nodes_iterator nodes_begin(NodeType* N) {
 482       return df_begin(N);
 483     }
 484
 485     static inline nodes_iterator nodes_end(NodeType* N) {
 486       return df_end(N);
 487     }
 488   };
 489
 490 } // end llvm namespace
 491
 492 #endif