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