Home | History | Annotate | Download | only in PathSensitive
      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/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/OwningPtr.h"
     31 #include "llvm/ADT/SmallPtrSet.h"
     32 #include "llvm/ADT/SmallVector.h"
     33 #include "llvm/Support/Allocator.h"
     34 #include "llvm/Support/Casting.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   const ProgramStateRef &getState() const { return State; }
    156 
    157   template <typename T>
    158   Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
    159     return Location.getAs<T>();
    160   }
    161 
    162   static void Profile(llvm::FoldingSetNodeID &ID,
    163                       const ProgramPoint &Loc,
    164                       const ProgramStateRef &state,
    165                       bool IsSink) {
    166     ID.Add(Loc);
    167     ID.AddPointer(state.getPtr());
    168     ID.AddBoolean(IsSink);
    169   }
    170 
    171   void Profile(llvm::FoldingSetNodeID& ID) const {
    172     // We avoid copy constructors by not using accessors.
    173     Profile(ID, Location, State, isSink());
    174   }
    175 
    176   /// addPredeccessor - Adds a predecessor to the current node, and
    177   ///  in tandem add this node as a successor of the other node.
    178   void addPredecessor(ExplodedNode *V, ExplodedGraph &G);
    179 
    180   unsigned succ_size() const { return Succs.size(); }
    181   unsigned pred_size() const { return Preds.size(); }
    182   bool succ_empty() const { return Succs.empty(); }
    183   bool pred_empty() const { return Preds.empty(); }
    184 
    185   bool isSink() const { return Succs.getFlag(); }
    186 
    187    bool hasSinglePred() const {
    188     return (pred_size() == 1);
    189   }
    190 
    191   ExplodedNode *getFirstPred() {
    192     return pred_empty() ? NULL : *(pred_begin());
    193   }
    194 
    195   const ExplodedNode *getFirstPred() const {
    196     return const_cast<ExplodedNode*>(this)->getFirstPred();
    197   }
    198 
    199   // Iterators over successor and predecessor vertices.
    200   typedef ExplodedNode*       const *       succ_iterator;
    201   typedef const ExplodedNode* const * const_succ_iterator;
    202   typedef ExplodedNode*       const *       pred_iterator;
    203   typedef const ExplodedNode* const * const_pred_iterator;
    204 
    205   pred_iterator pred_begin() { return Preds.begin(); }
    206   pred_iterator pred_end() { return Preds.end(); }
    207 
    208   const_pred_iterator pred_begin() const {
    209     return const_cast<ExplodedNode*>(this)->pred_begin();
    210   }
    211   const_pred_iterator pred_end() const {
    212     return const_cast<ExplodedNode*>(this)->pred_end();
    213   }
    214 
    215   succ_iterator succ_begin() { return Succs.begin(); }
    216   succ_iterator succ_end() { return Succs.end(); }
    217 
    218   const_succ_iterator succ_begin() const {
    219     return const_cast<ExplodedNode*>(this)->succ_begin();
    220   }
    221   const_succ_iterator succ_end() const {
    222     return const_cast<ExplodedNode*>(this)->succ_end();
    223   }
    224 
    225   // For debugging.
    226 
    227 public:
    228 
    229   class Auditor {
    230   public:
    231     virtual ~Auditor();
    232     virtual void AddEdge(ExplodedNode *Src, ExplodedNode *Dst) = 0;
    233   };
    234 
    235   static void SetAuditor(Auditor* A);
    236 
    237 private:
    238   void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); }
    239   void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); }
    240 };
    241 
    242 typedef llvm::DenseMap<const ExplodedNode *, const ExplodedNode *>
    243         InterExplodedGraphMap;
    244 
    245 class ExplodedGraph {
    246 protected:
    247   friend class CoreEngine;
    248 
    249   // Type definitions.
    250   typedef std::vector<ExplodedNode *> NodeVector;
    251 
    252   /// The roots of the simulation graph. Usually there will be only
    253   /// one, but clients are free to establish multiple subgraphs within a single
    254   /// SimulGraph. Moreover, these subgraphs can often merge when paths from
    255   /// different roots reach the same state at the same program location.
    256   NodeVector Roots;
    257 
    258   /// The nodes in the simulation graph which have been
    259   /// specially marked as the endpoint of an abstract simulation path.
    260   NodeVector EndNodes;
    261 
    262   /// Nodes - The nodes in the graph.
    263   llvm::FoldingSet<ExplodedNode> Nodes;
    264 
    265   /// BVC - Allocator and context for allocating nodes and their predecessor
    266   /// and successor groups.
    267   BumpVectorContext BVC;
    268 
    269   /// NumNodes - The number of nodes in the graph.
    270   unsigned NumNodes;
    271 
    272   /// A list of recently allocated nodes that can potentially be recycled.
    273   NodeVector ChangedNodes;
    274 
    275   /// A list of nodes that can be reused.
    276   NodeVector FreeNodes;
    277 
    278   /// Determines how often nodes are reclaimed.
    279   ///
    280   /// If this is 0, nodes will never be reclaimed.
    281   unsigned ReclaimNodeInterval;
    282 
    283   /// Counter to determine when to reclaim nodes.
    284   unsigned ReclaimCounter;
    285 
    286 public:
    287 
    288   /// \brief Retrieve the node associated with a (Location,State) pair,
    289   ///  where the 'Location' is a ProgramPoint in the CFG.  If no node for
    290   ///  this pair exists, it is created. IsNew is set to true if
    291   ///  the node was freshly created.
    292   ExplodedNode *getNode(const ProgramPoint &L, ProgramStateRef State,
    293                         bool IsSink = false,
    294                         bool* IsNew = 0);
    295 
    296   ExplodedGraph* MakeEmptyGraph() const {
    297     return new ExplodedGraph();
    298   }
    299 
    300   /// addRoot - Add an untyped node to the set of roots.
    301   ExplodedNode *addRoot(ExplodedNode *V) {
    302     Roots.push_back(V);
    303     return V;
    304   }
    305 
    306   /// addEndOfPath - Add an untyped node to the set of EOP nodes.
    307   ExplodedNode *addEndOfPath(ExplodedNode *V) {
    308     EndNodes.push_back(V);
    309     return V;
    310   }
    311 
    312   ExplodedGraph();
    313 
    314   ~ExplodedGraph();
    315 
    316   unsigned num_roots() const { return Roots.size(); }
    317   unsigned num_eops() const { return EndNodes.size(); }
    318 
    319   bool empty() const { return NumNodes == 0; }
    320   unsigned size() const { return NumNodes; }
    321 
    322   // Iterators.
    323   typedef ExplodedNode                        NodeTy;
    324   typedef llvm::FoldingSet<ExplodedNode>      AllNodesTy;
    325   typedef NodeVector::iterator                roots_iterator;
    326   typedef NodeVector::const_iterator          const_roots_iterator;
    327   typedef NodeVector::iterator                eop_iterator;
    328   typedef NodeVector::const_iterator          const_eop_iterator;
    329   typedef AllNodesTy::iterator                node_iterator;
    330   typedef AllNodesTy::const_iterator          const_node_iterator;
    331 
    332   node_iterator nodes_begin() { return Nodes.begin(); }
    333 
    334   node_iterator nodes_end() { return Nodes.end(); }
    335 
    336   const_node_iterator nodes_begin() const { return Nodes.begin(); }
    337 
    338   const_node_iterator nodes_end() const { return Nodes.end(); }
    339 
    340   roots_iterator roots_begin() { return Roots.begin(); }
    341 
    342   roots_iterator roots_end() { return Roots.end(); }
    343 
    344   const_roots_iterator roots_begin() const { return Roots.begin(); }
    345 
    346   const_roots_iterator roots_end() const { return Roots.end(); }
    347 
    348   eop_iterator eop_begin() { return EndNodes.begin(); }
    349 
    350   eop_iterator eop_end() { return EndNodes.end(); }
    351 
    352   const_eop_iterator eop_begin() const { return EndNodes.begin(); }
    353 
    354   const_eop_iterator eop_end() const { return EndNodes.end(); }
    355 
    356   llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); }
    357   BumpVectorContext &getNodeAllocator() { return BVC; }
    358 
    359   typedef llvm::DenseMap<const ExplodedNode*, ExplodedNode*> NodeMap;
    360 
    361   /// Creates a trimmed version of the graph that only contains paths leading
    362   /// to the given nodes.
    363   ///
    364   /// \param Nodes The nodes which must appear in the final graph. Presumably
    365   ///              these are end-of-path nodes (i.e. they have no successors).
    366   /// \param[out] ForwardMap A optional map from nodes in this graph to nodes in
    367   ///                        the returned graph.
    368   /// \param[out] InverseMap An optional map from nodes in the returned graph to
    369   ///                        nodes in this graph.
    370   /// \returns The trimmed graph
    371   ExplodedGraph *trim(ArrayRef<const NodeTy *> Nodes,
    372                       InterExplodedGraphMap *ForwardMap = 0,
    373                       InterExplodedGraphMap *InverseMap = 0) const;
    374 
    375   /// Enable tracking of recently allocated nodes for potential reclamation
    376   /// when calling reclaimRecentlyAllocatedNodes().
    377   void enableNodeReclamation(unsigned Interval) {
    378     ReclaimCounter = ReclaimNodeInterval = Interval;
    379   }
    380 
    381   /// Reclaim "uninteresting" nodes created since the last time this method
    382   /// was called.
    383   void reclaimRecentlyAllocatedNodes();
    384 
    385   /// \brief Returns true if nodes for the given expression kind are always
    386   ///        kept around.
    387   static bool isInterestingLValueExpr(const Expr *Ex);
    388 
    389 private:
    390   bool shouldCollect(const ExplodedNode *node);
    391   void collectNode(ExplodedNode *node);
    392 };
    393 
    394 class ExplodedNodeSet {
    395   typedef llvm::SmallPtrSet<ExplodedNode*,5> ImplTy;
    396   ImplTy Impl;
    397 
    398 public:
    399   ExplodedNodeSet(ExplodedNode *N) {
    400     assert (N && !static_cast<ExplodedNode*>(N)->isSink());
    401     Impl.insert(N);
    402   }
    403 
    404   ExplodedNodeSet() {}
    405 
    406   inline void Add(ExplodedNode *N) {
    407     if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N);
    408   }
    409 
    410   typedef ImplTy::iterator       iterator;
    411   typedef ImplTy::const_iterator const_iterator;
    412 
    413   unsigned size() const { return Impl.size();  }
    414   bool empty()    const { return Impl.empty(); }
    415   bool erase(ExplodedNode *N) { return Impl.erase(N); }
    416 
    417   void clear() { Impl.clear(); }
    418   void insert(const ExplodedNodeSet &S) {
    419     assert(&S != this);
    420     if (empty())
    421       Impl = S.Impl;
    422     else
    423       Impl.insert(S.begin(), S.end());
    424   }
    425 
    426   inline iterator begin() { return Impl.begin(); }
    427   inline iterator end()   { return Impl.end();   }
    428 
    429   inline const_iterator begin() const { return Impl.begin(); }
    430   inline const_iterator end()   const { return Impl.end();   }
    431 };
    432 
    433 } // end GR namespace
    434 
    435 } // end clang namespace
    436 
    437 // GraphTraits
    438 
    439 namespace llvm {
    440   template<> struct GraphTraits<clang::ento::ExplodedNode*> {
    441     typedef clang::ento::ExplodedNode NodeType;
    442     typedef NodeType::succ_iterator  ChildIteratorType;
    443     typedef llvm::df_iterator<NodeType*>      nodes_iterator;
    444 
    445     static inline NodeType* getEntryNode(NodeType* N) {
    446       return N;
    447     }
    448 
    449     static inline ChildIteratorType child_begin(NodeType* N) {
    450       return N->succ_begin();
    451     }
    452 
    453     static inline ChildIteratorType child_end(NodeType* N) {
    454       return N->succ_end();
    455     }
    456 
    457     static inline nodes_iterator nodes_begin(NodeType* N) {
    458       return df_begin(N);
    459     }
    460 
    461     static inline nodes_iterator nodes_end(NodeType* N) {
    462       return df_end(N);
    463     }
    464   };
    465 
    466   template<> struct GraphTraits<const clang::ento::ExplodedNode*> {
    467     typedef const clang::ento::ExplodedNode NodeType;
    468     typedef NodeType::const_succ_iterator   ChildIteratorType;
    469     typedef llvm::df_iterator<NodeType*>       nodes_iterator;
    470 
    471     static inline NodeType* getEntryNode(NodeType* N) {
    472       return N;
    473     }
    474 
    475     static inline ChildIteratorType child_begin(NodeType* N) {
    476       return N->succ_begin();
    477     }
    478 
    479     static inline ChildIteratorType child_end(NodeType* N) {
    480       return N->succ_end();
    481     }
    482 
    483     static inline nodes_iterator nodes_begin(NodeType* N) {
    484       return df_begin(N);
    485     }
    486 
    487     static inline nodes_iterator nodes_end(NodeType* N) {
    488       return df_end(N);
    489     }
    490   };
    491 
    492 } // end llvm namespace
    493 
    494 #endif
    495