Home | History | Annotate | Download | only in PathSensitive
      1 //==- CoreEngine.h - Path-Sensitive Dataflow Engine ----------------*- 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 a generic engine for intraprocedural, path-sensitive,
     11 //  dataflow analysis via graph reachability.
     12 //
     13 //===----------------------------------------------------------------------===//
     14 
     15 #ifndef LLVM_CLANG_GR_COREENGINE
     16 #define LLVM_CLANG_GR_COREENGINE
     17 
     18 #include "clang/AST/Expr.h"
     19 #include "clang/Analysis/AnalysisContext.h"
     20 #include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h"
     21 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
     22 #include "clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h"
     23 #include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h"
     24 #include "llvm/ADT/OwningPtr.h"
     25 
     26 namespace clang {
     27 
     28 class ProgramPointTag;
     29 
     30 namespace ento {
     31 
     32 class NodeBuilder;
     33 
     34 //===----------------------------------------------------------------------===//
     35 /// CoreEngine - Implements the core logic of the graph-reachability
     36 ///   analysis. It traverses the CFG and generates the ExplodedGraph.
     37 ///   Program "states" are treated as opaque void pointers.
     38 ///   The template class CoreEngine (which subclasses CoreEngine)
     39 ///   provides the matching component to the engine that knows the actual types
     40 ///   for states.  Note that this engine only dispatches to transfer functions
     41 ///   at the statement and block-level.  The analyses themselves must implement
     42 ///   any transfer function logic and the sub-expression level (if any).
     43 class CoreEngine {
     44   friend struct NodeBuilderContext;
     45   friend class NodeBuilder;
     46   friend class ExprEngine;
     47   friend class CommonNodeBuilder;
     48   friend class IndirectGotoNodeBuilder;
     49   friend class SwitchNodeBuilder;
     50   friend class EndOfFunctionNodeBuilder;
     51 public:
     52   typedef std::vector<std::pair<BlockEdge, const ExplodedNode*> >
     53             BlocksExhausted;
     54 
     55   typedef std::vector<std::pair<const CFGBlock*, const ExplodedNode*> >
     56             BlocksAborted;
     57 
     58 private:
     59 
     60   SubEngine& SubEng;
     61 
     62   /// G - The simulation graph.  Each node is a (location,state) pair.
     63   OwningPtr<ExplodedGraph> G;
     64 
     65   /// WList - A set of queued nodes that need to be processed by the
     66   ///  worklist algorithm.  It is up to the implementation of WList to decide
     67   ///  the order that nodes are processed.
     68   OwningPtr<WorkList> WList;
     69 
     70   /// BCounterFactory - A factory object for created BlockCounter objects.
     71   ///   These are used to record for key nodes in the ExplodedGraph the
     72   ///   number of times different CFGBlocks have been visited along a path.
     73   BlockCounter::Factory BCounterFactory;
     74 
     75   /// The locations where we stopped doing work because we visited a location
     76   ///  too many times.
     77   BlocksExhausted blocksExhausted;
     78 
     79   /// The locations where we stopped because the engine aborted analysis,
     80   /// usually because it could not reason about something.
     81   BlocksAborted blocksAborted;
     82 
     83   /// The information about functions shared by the whole translation unit.
     84   /// (This data is owned by AnalysisConsumer.)
     85   FunctionSummariesTy *FunctionSummaries;
     86 
     87   void generateNode(const ProgramPoint &Loc,
     88                     ProgramStateRef State,
     89                     ExplodedNode *Pred);
     90 
     91   void HandleBlockEdge(const BlockEdge &E, ExplodedNode *Pred);
     92   void HandleBlockEntrance(const BlockEntrance &E, ExplodedNode *Pred);
     93   void HandleBlockExit(const CFGBlock *B, ExplodedNode *Pred);
     94   void HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, ExplodedNode *Pred);
     95 
     96   void HandleBranch(const Stmt *Cond, const Stmt *Term, const CFGBlock *B,
     97                     ExplodedNode *Pred);
     98 
     99   /// Handle conditional logic for running static initializers.
    100   void HandleStaticInit(const DeclStmt *DS, const CFGBlock *B,
    101                         ExplodedNode *Pred);
    102 
    103 private:
    104   CoreEngine(const CoreEngine &) LLVM_DELETED_FUNCTION;
    105   void operator=(const CoreEngine &) LLVM_DELETED_FUNCTION;
    106 
    107   ExplodedNode *generateCallExitBeginNode(ExplodedNode *N);
    108 
    109 public:
    110   /// Construct a CoreEngine object to analyze the provided CFG.
    111   CoreEngine(SubEngine& subengine,
    112              FunctionSummariesTy *FS)
    113     : SubEng(subengine), G(new ExplodedGraph()),
    114       WList(WorkList::makeDFS()),
    115       BCounterFactory(G->getAllocator()),
    116       FunctionSummaries(FS){}
    117 
    118   /// getGraph - Returns the exploded graph.
    119   ExplodedGraph& getGraph() { return *G.get(); }
    120 
    121   /// takeGraph - Returns the exploded graph.  Ownership of the graph is
    122   ///  transferred to the caller.
    123   ExplodedGraph* takeGraph() { return G.take(); }
    124 
    125   /// ExecuteWorkList - Run the worklist algorithm for a maximum number of
    126   ///  steps.  Returns true if there is still simulation state on the worklist.
    127   bool ExecuteWorkList(const LocationContext *L, unsigned Steps,
    128                        ProgramStateRef InitState);
    129   /// Returns true if there is still simulation state on the worklist.
    130   bool ExecuteWorkListWithInitialState(const LocationContext *L,
    131                                        unsigned Steps,
    132                                        ProgramStateRef InitState,
    133                                        ExplodedNodeSet &Dst);
    134 
    135   /// Dispatch the work list item based on the given location information.
    136   /// Use Pred parameter as the predecessor state.
    137   void dispatchWorkItem(ExplodedNode* Pred, ProgramPoint Loc,
    138                         const WorkListUnit& WU);
    139 
    140   // Functions for external checking of whether we have unfinished work
    141   bool wasBlockAborted() const { return !blocksAborted.empty(); }
    142   bool wasBlocksExhausted() const { return !blocksExhausted.empty(); }
    143   bool hasWorkRemaining() const { return wasBlocksExhausted() ||
    144                                          WList->hasWork() ||
    145                                          wasBlockAborted(); }
    146 
    147   /// Inform the CoreEngine that a basic block was aborted because
    148   /// it could not be completely analyzed.
    149   void addAbortedBlock(const ExplodedNode *node, const CFGBlock *block) {
    150     blocksAborted.push_back(std::make_pair(block, node));
    151   }
    152 
    153   WorkList *getWorkList() const { return WList.get(); }
    154 
    155   BlocksExhausted::const_iterator blocks_exhausted_begin() const {
    156     return blocksExhausted.begin();
    157   }
    158   BlocksExhausted::const_iterator blocks_exhausted_end() const {
    159     return blocksExhausted.end();
    160   }
    161   BlocksAborted::const_iterator blocks_aborted_begin() const {
    162     return blocksAborted.begin();
    163   }
    164   BlocksAborted::const_iterator blocks_aborted_end() const {
    165     return blocksAborted.end();
    166   }
    167 
    168   /// \brief Enqueue the given set of nodes onto the work list.
    169   void enqueue(ExplodedNodeSet &Set);
    170 
    171   /// \brief Enqueue nodes that were created as a result of processing
    172   /// a statement onto the work list.
    173   void enqueue(ExplodedNodeSet &Set, const CFGBlock *Block, unsigned Idx);
    174 
    175   /// \brief enqueue the nodes corresponding to the end of function onto the
    176   /// end of path / work list.
    177   void enqueueEndOfFunction(ExplodedNodeSet &Set);
    178 
    179   /// \brief Enqueue a single node created as a result of statement processing.
    180   void enqueueStmtNode(ExplodedNode *N, const CFGBlock *Block, unsigned Idx);
    181 };
    182 
    183 // TODO: Turn into a calss.
    184 struct NodeBuilderContext {
    185   const CoreEngine &Eng;
    186   const CFGBlock *Block;
    187   const LocationContext *LC;
    188   NodeBuilderContext(const CoreEngine &E, const CFGBlock *B, ExplodedNode *N)
    189     : Eng(E), Block(B), LC(N->getLocationContext()) { assert(B); }
    190 
    191   /// \brief Return the CFGBlock associated with this builder.
    192   const CFGBlock *getBlock() const { return Block; }
    193 
    194   /// \brief Returns the number of times the current basic block has been
    195   /// visited on the exploded graph path.
    196   unsigned blockCount() const {
    197     return Eng.WList->getBlockCounter().getNumVisited(
    198                     LC->getCurrentStackFrame(),
    199                     Block->getBlockID());
    200   }
    201 };
    202 
    203 /// \class NodeBuilder
    204 /// \brief This is the simplest builder which generates nodes in the
    205 /// ExplodedGraph.
    206 ///
    207 /// The main benefit of the builder is that it automatically tracks the
    208 /// frontier nodes (or destination set). This is the set of nodes which should
    209 /// be propagated to the next step / builder. They are the nodes which have been
    210 /// added to the builder (either as the input node set or as the newly
    211 /// constructed nodes) but did not have any outgoing transitions added.
    212 class NodeBuilder {
    213   virtual void anchor();
    214 protected:
    215   const NodeBuilderContext &C;
    216 
    217   /// Specifies if the builder results have been finalized. For example, if it
    218   /// is set to false, autotransitions are yet to be generated.
    219   bool Finalized;
    220   bool HasGeneratedNodes;
    221   /// \brief The frontier set - a set of nodes which need to be propagated after
    222   /// the builder dies.
    223   ExplodedNodeSet &Frontier;
    224 
    225   /// Checkes if the results are ready.
    226   virtual bool checkResults() {
    227     if (!Finalized)
    228       return false;
    229     return true;
    230   }
    231 
    232   bool hasNoSinksInFrontier() {
    233     for (iterator I = Frontier.begin(), E = Frontier.end(); I != E; ++I) {
    234       if ((*I)->isSink())
    235         return false;
    236     }
    237     return true;
    238   }
    239 
    240   /// Allow subclasses to finalize results before result_begin() is executed.
    241   virtual void finalizeResults() {}
    242 
    243   ExplodedNode *generateNodeImpl(const ProgramPoint &PP,
    244                                  ProgramStateRef State,
    245                                  ExplodedNode *Pred,
    246                                  bool MarkAsSink = false);
    247 
    248 public:
    249   NodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet,
    250               const NodeBuilderContext &Ctx, bool F = true)
    251     : C(Ctx), Finalized(F), HasGeneratedNodes(false), Frontier(DstSet) {
    252     Frontier.Add(SrcNode);
    253   }
    254 
    255   NodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet,
    256               const NodeBuilderContext &Ctx, bool F = true)
    257     : C(Ctx), Finalized(F), HasGeneratedNodes(false), Frontier(DstSet) {
    258     Frontier.insert(SrcSet);
    259     assert(hasNoSinksInFrontier());
    260   }
    261 
    262   virtual ~NodeBuilder() {}
    263 
    264   /// \brief Generates a node in the ExplodedGraph.
    265   ExplodedNode *generateNode(const ProgramPoint &PP,
    266                              ProgramStateRef State,
    267                              ExplodedNode *Pred) {
    268     return generateNodeImpl(PP, State, Pred, false);
    269   }
    270 
    271   /// \brief Generates a sink in the ExplodedGraph.
    272   ///
    273   /// When a node is marked as sink, the exploration from the node is stopped -
    274   /// the node becomes the last node on the path and certain kinds of bugs are
    275   /// suppressed.
    276   ExplodedNode *generateSink(const ProgramPoint &PP,
    277                              ProgramStateRef State,
    278                              ExplodedNode *Pred) {
    279     return generateNodeImpl(PP, State, Pred, true);
    280   }
    281 
    282   const ExplodedNodeSet &getResults() {
    283     finalizeResults();
    284     assert(checkResults());
    285     return Frontier;
    286   }
    287 
    288   typedef ExplodedNodeSet::iterator iterator;
    289   /// \brief Iterators through the results frontier.
    290   inline iterator begin() {
    291     finalizeResults();
    292     assert(checkResults());
    293     return Frontier.begin();
    294   }
    295   inline iterator end() {
    296     finalizeResults();
    297     return Frontier.end();
    298   }
    299 
    300   const NodeBuilderContext &getContext() { return C; }
    301   bool hasGeneratedNodes() { return HasGeneratedNodes; }
    302 
    303   void takeNodes(const ExplodedNodeSet &S) {
    304     for (ExplodedNodeSet::iterator I = S.begin(), E = S.end(); I != E; ++I )
    305       Frontier.erase(*I);
    306   }
    307   void takeNodes(ExplodedNode *N) { Frontier.erase(N); }
    308   void addNodes(const ExplodedNodeSet &S) { Frontier.insert(S); }
    309   void addNodes(ExplodedNode *N) { Frontier.Add(N); }
    310 };
    311 
    312 /// \class NodeBuilderWithSinks
    313 /// \brief This node builder keeps track of the generated sink nodes.
    314 class NodeBuilderWithSinks: public NodeBuilder {
    315   virtual void anchor();
    316 protected:
    317   SmallVector<ExplodedNode*, 2> sinksGenerated;
    318   ProgramPoint &Location;
    319 
    320 public:
    321   NodeBuilderWithSinks(ExplodedNode *Pred, ExplodedNodeSet &DstSet,
    322                        const NodeBuilderContext &Ctx, ProgramPoint &L)
    323     : NodeBuilder(Pred, DstSet, Ctx), Location(L) {}
    324 
    325   ExplodedNode *generateNode(ProgramStateRef State,
    326                              ExplodedNode *Pred,
    327                              const ProgramPointTag *Tag = 0) {
    328     const ProgramPoint &LocalLoc = (Tag ? Location.withTag(Tag) : Location);
    329     return NodeBuilder::generateNode(LocalLoc, State, Pred);
    330   }
    331 
    332   ExplodedNode *generateSink(ProgramStateRef State, ExplodedNode *Pred,
    333                              const ProgramPointTag *Tag = 0) {
    334     const ProgramPoint &LocalLoc = (Tag ? Location.withTag(Tag) : Location);
    335     ExplodedNode *N = NodeBuilder::generateSink(LocalLoc, State, Pred);
    336     if (N && N->isSink())
    337       sinksGenerated.push_back(N);
    338     return N;
    339   }
    340 
    341   const SmallVectorImpl<ExplodedNode*> &getSinks() const {
    342     return sinksGenerated;
    343   }
    344 };
    345 
    346 /// \class StmtNodeBuilder
    347 /// \brief This builder class is useful for generating nodes that resulted from
    348 /// visiting a statement. The main difference from its parent NodeBuilder is
    349 /// that it creates a statement specific ProgramPoint.
    350 class StmtNodeBuilder: public NodeBuilder {
    351   NodeBuilder *EnclosingBldr;
    352 public:
    353 
    354   /// \brief Constructs a StmtNodeBuilder. If the builder is going to process
    355   /// nodes currently owned by another builder(with larger scope), use
    356   /// Enclosing builder to transfer ownership.
    357   StmtNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet,
    358                       const NodeBuilderContext &Ctx, NodeBuilder *Enclosing = 0)
    359     : NodeBuilder(SrcNode, DstSet, Ctx), EnclosingBldr(Enclosing) {
    360     if (EnclosingBldr)
    361       EnclosingBldr->takeNodes(SrcNode);
    362   }
    363 
    364   StmtNodeBuilder(ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet,
    365                       const NodeBuilderContext &Ctx, NodeBuilder *Enclosing = 0)
    366     : NodeBuilder(SrcSet, DstSet, Ctx), EnclosingBldr(Enclosing) {
    367     if (EnclosingBldr)
    368       for (ExplodedNodeSet::iterator I = SrcSet.begin(),
    369                                      E = SrcSet.end(); I != E; ++I )
    370         EnclosingBldr->takeNodes(*I);
    371   }
    372 
    373   virtual ~StmtNodeBuilder();
    374 
    375   using NodeBuilder::generateNode;
    376   using NodeBuilder::generateSink;
    377 
    378   ExplodedNode *generateNode(const Stmt *S,
    379                              ExplodedNode *Pred,
    380                              ProgramStateRef St,
    381                              const ProgramPointTag *tag = 0,
    382                              ProgramPoint::Kind K = ProgramPoint::PostStmtKind){
    383     const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K,
    384                                   Pred->getLocationContext(), tag);
    385     return NodeBuilder::generateNode(L, St, Pred);
    386   }
    387 
    388   ExplodedNode *generateSink(const Stmt *S,
    389                              ExplodedNode *Pred,
    390                              ProgramStateRef St,
    391                              const ProgramPointTag *tag = 0,
    392                              ProgramPoint::Kind K = ProgramPoint::PostStmtKind){
    393     const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K,
    394                                   Pred->getLocationContext(), tag);
    395     return NodeBuilder::generateSink(L, St, Pred);
    396   }
    397 };
    398 
    399 /// \brief BranchNodeBuilder is responsible for constructing the nodes
    400 /// corresponding to the two branches of the if statement - true and false.
    401 class BranchNodeBuilder: public NodeBuilder {
    402   virtual void anchor();
    403   const CFGBlock *DstT;
    404   const CFGBlock *DstF;
    405 
    406   bool InFeasibleTrue;
    407   bool InFeasibleFalse;
    408 
    409 public:
    410   BranchNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet,
    411                     const NodeBuilderContext &C,
    412                     const CFGBlock *dstT, const CFGBlock *dstF)
    413   : NodeBuilder(SrcNode, DstSet, C), DstT(dstT), DstF(dstF),
    414     InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {
    415     // The branch node builder does not generate autotransitions.
    416     // If there are no successors it means that both branches are infeasible.
    417     takeNodes(SrcNode);
    418   }
    419 
    420   BranchNodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet,
    421                     const NodeBuilderContext &C,
    422                     const CFGBlock *dstT, const CFGBlock *dstF)
    423   : NodeBuilder(SrcSet, DstSet, C), DstT(dstT), DstF(dstF),
    424     InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {
    425     takeNodes(SrcSet);
    426   }
    427 
    428   ExplodedNode *generateNode(ProgramStateRef State, bool branch,
    429                              ExplodedNode *Pred);
    430 
    431   const CFGBlock *getTargetBlock(bool branch) const {
    432     return branch ? DstT : DstF;
    433   }
    434 
    435   void markInfeasible(bool branch) {
    436     if (branch)
    437       InFeasibleTrue = true;
    438     else
    439       InFeasibleFalse = true;
    440   }
    441 
    442   bool isFeasible(bool branch) {
    443     return branch ? !InFeasibleTrue : !InFeasibleFalse;
    444   }
    445 };
    446 
    447 class IndirectGotoNodeBuilder {
    448   CoreEngine& Eng;
    449   const CFGBlock *Src;
    450   const CFGBlock &DispatchBlock;
    451   const Expr *E;
    452   ExplodedNode *Pred;
    453 
    454 public:
    455   IndirectGotoNodeBuilder(ExplodedNode *pred, const CFGBlock *src,
    456                     const Expr *e, const CFGBlock *dispatch, CoreEngine* eng)
    457     : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {}
    458 
    459   class iterator {
    460     CFGBlock::const_succ_iterator I;
    461 
    462     friend class IndirectGotoNodeBuilder;
    463     iterator(CFGBlock::const_succ_iterator i) : I(i) {}
    464   public:
    465 
    466     iterator &operator++() { ++I; return *this; }
    467     bool operator!=(const iterator &X) const { return I != X.I; }
    468 
    469     const LabelDecl *getLabel() const {
    470       return cast<LabelStmt>((*I)->getLabel())->getDecl();
    471     }
    472 
    473     const CFGBlock *getBlock() const {
    474       return *I;
    475     }
    476   };
    477 
    478   iterator begin() { return iterator(DispatchBlock.succ_begin()); }
    479   iterator end() { return iterator(DispatchBlock.succ_end()); }
    480 
    481   ExplodedNode *generateNode(const iterator &I,
    482                              ProgramStateRef State,
    483                              bool isSink = false);
    484 
    485   const Expr *getTarget() const { return E; }
    486 
    487   ProgramStateRef getState() const { return Pred->State; }
    488 
    489   const LocationContext *getLocationContext() const {
    490     return Pred->getLocationContext();
    491   }
    492 };
    493 
    494 class SwitchNodeBuilder {
    495   CoreEngine& Eng;
    496   const CFGBlock *Src;
    497   const Expr *Condition;
    498   ExplodedNode *Pred;
    499 
    500 public:
    501   SwitchNodeBuilder(ExplodedNode *pred, const CFGBlock *src,
    502                     const Expr *condition, CoreEngine* eng)
    503   : Eng(*eng), Src(src), Condition(condition), Pred(pred) {}
    504 
    505   class iterator {
    506     CFGBlock::const_succ_reverse_iterator I;
    507 
    508     friend class SwitchNodeBuilder;
    509     iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {}
    510 
    511   public:
    512     iterator &operator++() { ++I; return *this; }
    513     bool operator!=(const iterator &X) const { return I != X.I; }
    514     bool operator==(const iterator &X) const { return I == X.I; }
    515 
    516     const CaseStmt *getCase() const {
    517       return cast<CaseStmt>((*I)->getLabel());
    518     }
    519 
    520     const CFGBlock *getBlock() const {
    521       return *I;
    522     }
    523   };
    524 
    525   iterator begin() { return iterator(Src->succ_rbegin()+1); }
    526   iterator end() { return iterator(Src->succ_rend()); }
    527 
    528   const SwitchStmt *getSwitch() const {
    529     return cast<SwitchStmt>(Src->getTerminator());
    530   }
    531 
    532   ExplodedNode *generateCaseStmtNode(const iterator &I,
    533                                      ProgramStateRef State);
    534 
    535   ExplodedNode *generateDefaultCaseNode(ProgramStateRef State,
    536                                         bool isSink = false);
    537 
    538   const Expr *getCondition() const { return Condition; }
    539 
    540   ProgramStateRef getState() const { return Pred->State; }
    541 
    542   const LocationContext *getLocationContext() const {
    543     return Pred->getLocationContext();
    544   }
    545 };
    546 
    547 } // end ento namespace
    548 } // end clang namespace
    549 
    550 #endif
    551