include/clang/Checker/PathSensitive/GRCoreEngine.h

   1 //==- GRCoreEngine.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_ANALYSIS_GRENGINE
  16 #define LLVM_CLANG_ANALYSIS_GRENGINE
  17
  18 #include "clang/AST/Expr.h"
  19 #include "clang/Checker/PathSensitive/ExplodedGraph.h"
  20 #include "clang/Checker/PathSensitive/GRWorkList.h"
  21 #include "clang/Checker/PathSensitive/GRBlockCounter.h"
  22 #include "clang/Checker/PathSensitive/GRSubEngine.h"
  23 #include "llvm/ADT/OwningPtr.h"
  24
  25 namespace clang {
  26
  27 //===----------------------------------------------------------------------===//
  28 /// GRCoreEngine - Implements the core logic of the graph-reachability
  29 ///   analysis. It traverses the CFG and generates the ExplodedGraph.
  30 ///   Program "states" are treated as opaque void pointers.
  31 ///   The template class GRCoreEngine (which subclasses GRCoreEngine)
  32 ///   provides the matching component to the engine that knows the actual types
  33 ///   for states.  Note that this engine only dispatches to transfer functions
  34 ///   at the statement and block-level.  The analyses themselves must implement
  35 ///   any transfer function logic and the sub-expression level (if any).
  36 class GRCoreEngine {
  37   friend class GRStmtNodeBuilder;
  38   friend class GRBranchNodeBuilder;
  39   friend class GRIndirectGotoNodeBuilder;
  40   friend class GRSwitchNodeBuilder;
  41   friend class GREndPathNodeBuilder;
  42   friend class GRCallEnterNodeBuilder;
  43   friend class GRCallExitNodeBuilder;
  44
  45 public:
  46   typedef std::vector<std::pair<BlockEdge, const ExplodedNode*> >
  47             BlocksAborted;
  48 private:
  49
  50   GRSubEngine& SubEngine;
  51
  52   /// G - The simulation graph.  Each node is a (location,state) pair.
  53   llvm::OwningPtr<ExplodedGraph> G;
  54
  55   /// WList - A set of queued nodes that need to be processed by the
  56   ///  worklist algorithm.  It is up to the implementation of WList to decide
  57   ///  the order that nodes are processed.
  58   GRWorkList* WList;
  59
  60   /// BCounterFactory - A factory object for created GRBlockCounter objects.
  61   ///   These are used to record for key nodes in the ExplodedGraph the
  62   ///   number of times different CFGBlocks have been visited along a path.
  63   GRBlockCounter::Factory BCounterFactory;
  64
  65   /// The locations where we stopped doing work because we visited a location
  66   ///  too many times.
  67   BlocksAborted blocksAborted;
  68
  69   void generateNode(const ProgramPoint& Loc, const GRState* State,
  70                     ExplodedNode* Pred);
  71
  72   void HandleBlockEdge(const BlockEdge& E, ExplodedNode* Pred);
  73   void HandleBlockEntrance(const BlockEntrance& E, ExplodedNode* Pred);
  74   void HandleBlockExit(const CFGBlock* B, ExplodedNode* Pred);
  75   void HandlePostStmt(const CFGBlock* B, unsigned StmtIdx, ExplodedNode *Pred);
  76
  77   void HandleBranch(const Stmt* Cond, const Stmt* Term, const CFGBlock* B,
  78                     ExplodedNode* Pred);
  79   void HandleCallEnter(const CallEnter &L, const CFGBlock *Block,
  80                        unsigned Index, ExplodedNode *Pred);
  81   void HandleCallExit(const CallExit &L, ExplodedNode *Pred);
  82
  83   /// Get the initial state from the subengine.
  84   const GRState* getInitialState(const LocationContext *InitLoc) {
  85     return SubEngine.getInitialState(InitLoc);
  86   }
  87
  88   void ProcessEndPath(GREndPathNodeBuilder& Builder) {
  89     SubEngine.ProcessEndPath(Builder);
  90   }
  91
  92   void ProcessElement(const CFGElement E, GRStmtNodeBuilder& Builder) {
  93     SubEngine.ProcessElement(E, Builder);
  94   }
  95
  96   bool ProcessBlockEntrance(const CFGBlock* Blk, const ExplodedNode *Pred,
  97                             GRBlockCounter BC) {
  98     return SubEngine.ProcessBlockEntrance(Blk, Pred, BC);
  99   }
 100
 101
 102   void ProcessBranch(const Stmt* Condition, const Stmt* Terminator,
 103                      GRBranchNodeBuilder& Builder) {
 104     SubEngine.ProcessBranch(Condition, Terminator, Builder);
 105   }
 106
 107
 108   void ProcessIndirectGoto(GRIndirectGotoNodeBuilder& Builder) {
 109     SubEngine.ProcessIndirectGoto(Builder);
 110   }
 111
 112
 113   void ProcessSwitch(GRSwitchNodeBuilder& Builder) {
 114     SubEngine.ProcessSwitch(Builder);
 115   }
 116
 117   void ProcessCallEnter(GRCallEnterNodeBuilder &Builder) {
 118     SubEngine.ProcessCallEnter(Builder);
 119   }
 120
 121   void ProcessCallExit(GRCallExitNodeBuilder &Builder) {
 122     SubEngine.ProcessCallExit(Builder);
 123   }
 124
 125 private:
 126   GRCoreEngine(const GRCoreEngine&); // Do not implement.
 127   GRCoreEngine& operator=(const GRCoreEngine&);
 128
 129 public:
 130   /// Construct a GRCoreEngine object to analyze the provided CFG using
 131   ///  a DFS exploration of the exploded graph.
 132   GRCoreEngine(GRSubEngine& subengine)
 133     : SubEngine(subengine), G(new ExplodedGraph()),
 134       WList(GRWorkList::MakeBFS()),
 135       BCounterFactory(G->getAllocator()) {}
 136
 137   /// Construct a GRCoreEngine object to analyze the provided CFG and to
 138   ///  use the provided worklist object to execute the worklist algorithm.
 139   ///  The GRCoreEngine object assumes ownership of 'wlist'.
 140   GRCoreEngine(GRWorkList* wlist, GRSubEngine& subengine)
 141     : SubEngine(subengine), G(new ExplodedGraph()), WList(wlist),
 142       BCounterFactory(G->getAllocator()) {}
 143
 144   ~GRCoreEngine() {
 145     delete WList;
 146   }
 147
 148   /// getGraph - Returns the exploded graph.
 149   ExplodedGraph& getGraph() { return *G.get(); }
 150
 151   /// takeGraph - Returns the exploded graph.  Ownership of the graph is
 152   ///  transfered to the caller.
 153   ExplodedGraph* takeGraph() { return G.take(); }
 154
 155   /// ExecuteWorkList - Run the worklist algorithm for a maximum number of
 156   ///  steps.  Returns true if there is still simulation state on the worklist.
 157   bool ExecuteWorkList(const LocationContext *L, unsigned Steps,
 158                        const GRState *InitState);
 159   void ExecuteWorkListWithInitialState(const LocationContext *L, unsigned Steps,
 160                                        const GRState *InitState,
 161                                        ExplodedNodeSet &Dst);
 162
 163   // Functions for external checking of whether we have unfinished work
 164   bool wasBlockAborted() const { return !blocksAborted.empty(); }
 165   bool hasWorkRemaining() const { return wasBlockAborted() || WList->hasWork(); }
 166
 167   GRWorkList *getWorkList() const { return WList; }
 168
 169   BlocksAborted::const_iterator blocks_aborted_begin() const {
 170     return blocksAborted.begin();
 171   }
 172   BlocksAborted::const_iterator blocks_aborted_end() const {
 173     return blocksAborted.end();
 174   }
 175 };
 176
 177 class GRStmtNodeBuilder {
 178   GRCoreEngine& Eng;
 179   const CFGBlock& B;
 180   const unsigned Idx;
 181   ExplodedNode* Pred;
 182   GRStateManager& Mgr;
 183
 184 public:
 185   bool PurgingDeadSymbols;
 186   bool BuildSinks;
 187   bool HasGeneratedNode;
 188   ProgramPoint::Kind PointKind;
 189   const void *Tag;
 190
 191   const GRState* CleanedState;
 192
 193
 194   typedef llvm::SmallPtrSet<ExplodedNode*,5> DeferredTy;
 195   DeferredTy Deferred;
 196
 197   void GenerateAutoTransition(ExplodedNode* N);
 198
 199 public:
 200   GRStmtNodeBuilder(const CFGBlock* b, unsigned idx, ExplodedNode* N,
 201                     GRCoreEngine* e, GRStateManager &mgr);
 202
 203   ~GRStmtNodeBuilder();
 204
 205   ExplodedNode* getBasePredecessor() const { return Pred; }
 206
 207   // FIXME: This should not be exposed.
 208   GRWorkList *getWorkList() { return Eng.WList; }
 209
 210   void SetCleanedState(const GRState* St) {
 211     CleanedState = St;
 212   }
 213
 214   GRBlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();}
 215
 216   unsigned getCurrentBlockCount() const {
 217     return getBlockCounter().getNumVisited(
 218                             Pred->getLocationContext()->getCurrentStackFrame(),
 219                                            B.getBlockID());
 220   }
 221
 222   ExplodedNode* generateNode(PostStmt PP,const GRState* St,ExplodedNode* Pred) {
 223     HasGeneratedNode = true;
 224     return generateNodeInternal(PP, St, Pred);
 225   }
 226
 227   ExplodedNode* generateNode(const Stmt *S, const GRState *St,
 228                              ExplodedNode *Pred, ProgramPoint::Kind K) {
 229     HasGeneratedNode = true;
 230
 231     if (PurgingDeadSymbols)
 232       K = ProgramPoint::PostPurgeDeadSymbolsKind;
 233
 234     return generateNodeInternal(S, St, Pred, K, Tag);
 235   }
 236
 237   ExplodedNode* generateNode(const Stmt *S, const GRState *St,
 238                              ExplodedNode *Pred) {
 239     return generateNode(S, St, Pred, PointKind);
 240   }
 241
 242   ExplodedNode *generateNode(const ProgramPoint &PP, const GRState* State,
 243                              ExplodedNode* Pred) {
 244     HasGeneratedNode = true;
 245     return generateNodeInternal(PP, State, Pred);
 246   }
 247
 248   ExplodedNode*
 249   generateNodeInternal(const ProgramPoint &PP, const GRState* State,
 250                        ExplodedNode* Pred);
 251
 252   ExplodedNode*
 253   generateNodeInternal(const Stmt* S, const GRState* State, ExplodedNode* Pred,
 254                    ProgramPoint::Kind K = ProgramPoint::PostStmtKind,
 255                    const void *tag = 0);
 256
 257   /// getStmt - Return the current block-level expression associated with
 258   ///  this builder.
 259   const Stmt* getStmt() const {
 260     CFGStmt CS = B[Idx].getAs<CFGStmt>();
 261     if (CS)
 262       return CS.getStmt();
 263     else
 264       return 0;
 265   }
 266
 267   /// getBlock - Return the CFGBlock associated with the block-level expression
 268   ///  of this builder.
 269   const CFGBlock* getBlock() const { return &B; }
 270
 271   unsigned getIndex() const { return Idx; }
 272
 273   const GRState* GetState(ExplodedNode* Pred) const {
 274     if (Pred == getBasePredecessor())
 275       return CleanedState;
 276     else
 277       return Pred->getState();
 278   }
 279
 280   ExplodedNode* MakeNode(ExplodedNodeSet& Dst, const Stmt* S,
 281                          ExplodedNode* Pred, const GRState* St) {
 282     return MakeNode(Dst, S, Pred, St, PointKind);
 283   }
 284
 285   ExplodedNode* MakeNode(ExplodedNodeSet& Dst, const Stmt* S,ExplodedNode* Pred,
 286                          const GRState* St, ProgramPoint::Kind K);
 287
 288   ExplodedNode* MakeSinkNode(ExplodedNodeSet& Dst, const Stmt* S,
 289                        ExplodedNode* Pred, const GRState* St) {
 290     bool Tmp = BuildSinks;
 291     BuildSinks = true;
 292     ExplodedNode* N = MakeNode(Dst, S, Pred, St);
 293     BuildSinks = Tmp;
 294     return N;
 295   }
 296 };
 297
 298 class GRBranchNodeBuilder {
 299   GRCoreEngine& Eng;
 300   const CFGBlock* Src;
 301   const CFGBlock* DstT;
 302   const CFGBlock* DstF;
 303   ExplodedNode* Pred;
 304
 305   typedef llvm::SmallVector<ExplodedNode*,3> DeferredTy;
 306   DeferredTy Deferred;
 307
 308   bool GeneratedTrue;
 309   bool GeneratedFalse;
 310   bool InFeasibleTrue;
 311   bool InFeasibleFalse;
 312
 313 public:
 314   GRBranchNodeBuilder(const CFGBlock* src, const CFGBlock* dstT,
 315                       const CFGBlock* dstF, ExplodedNode* pred, GRCoreEngine* e)
 316   : Eng(*e), Src(src), DstT(dstT), DstF(dstF), Pred(pred),
 317     GeneratedTrue(false), GeneratedFalse(false),
 318     InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {}
 319
 320   ~GRBranchNodeBuilder();
 321
 322   ExplodedNode* getPredecessor() const { return Pred; }
 323
 324   const ExplodedGraph& getGraph() const { return *Eng.G; }
 325
 326   GRBlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();}
 327
 328   ExplodedNode* generateNode(const GRState* State, bool branch);
 329
 330   const CFGBlock* getTargetBlock(bool branch) const {
 331     return branch ? DstT : DstF;
 332   }
 333
 334   void markInfeasible(bool branch) {
 335     if (branch)
 336       InFeasibleTrue = GeneratedTrue = true;
 337     else
 338       InFeasibleFalse = GeneratedFalse = true;
 339   }
 340
 341   bool isFeasible(bool branch) {
 342     return branch ? !InFeasibleTrue : !InFeasibleFalse;
 343   }
 344
 345   const GRState* getState() const {
 346     return getPredecessor()->getState();
 347   }
 348 };
 349
 350 class GRIndirectGotoNodeBuilder {
 351   GRCoreEngine& Eng;
 352   const CFGBlock* Src;
 353   const CFGBlock& DispatchBlock;
 354   const Expr* E;
 355   ExplodedNode* Pred;
 356
 357 public:
 358   GRIndirectGotoNodeBuilder(ExplodedNode* pred, const CFGBlock* src,
 359                     const Expr* e, const CFGBlock* dispatch, GRCoreEngine* eng)
 360     : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {}
 361
 362   class iterator {
 363     CFGBlock::const_succ_iterator I;
 364
 365     friend class GRIndirectGotoNodeBuilder;
 366     iterator(CFGBlock::const_succ_iterator i) : I(i) {}
 367   public:
 368
 369     iterator& operator++() { ++I; return *this; }
 370     bool operator!=(const iterator& X) const { return I != X.I; }
 371
 372     const LabelStmt* getLabel() const {
 373       return llvm::cast<LabelStmt>((*I)->getLabel());
 374     }
 375
 376     const CFGBlock*  getBlock() const {
 377       return *I;
 378     }
 379   };
 380
 381   iterator begin() { return iterator(DispatchBlock.succ_begin()); }
 382   iterator end() { return iterator(DispatchBlock.succ_end()); }
 383
 384   ExplodedNode* generateNode(const iterator& I, const GRState* State,
 385                              bool isSink = false);
 386
 387   const Expr* getTarget() const { return E; }
 388
 389   const GRState* getState() const { return Pred->State; }
 390 };
 391
 392 class GRSwitchNodeBuilder {
 393   GRCoreEngine& Eng;
 394   const CFGBlock* Src;
 395   const Expr* Condition;
 396   ExplodedNode* Pred;
 397
 398 public:
 399   GRSwitchNodeBuilder(ExplodedNode* pred, const CFGBlock* src,
 400                       const Expr* condition, GRCoreEngine* eng)
 401   : Eng(*eng), Src(src), Condition(condition), Pred(pred) {}
 402
 403   class iterator {
 404     CFGBlock::const_succ_reverse_iterator I;
 405
 406     friend class GRSwitchNodeBuilder;
 407     iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {}
 408
 409   public:
 410     iterator& operator++() { ++I; return *this; }
 411     bool operator!=(const iterator &X) const { return I != X.I; }
 412     bool operator==(const iterator &X) const { return I == X.I; }
 413
 414     const CaseStmt* getCase() const {
 415       return llvm::cast<CaseStmt>((*I)->getLabel());
 416     }
 417
 418     const CFGBlock* getBlock() const {
 419       return *I;
 420     }
 421   };
 422
 423   iterator begin() { return iterator(Src->succ_rbegin()+1); }
 424   iterator end() { return iterator(Src->succ_rend()); }
 425
 426   const SwitchStmt *getSwitch() const {
 427     return llvm::cast<SwitchStmt>(Src->getTerminator());
 428   }
 429
 430   ExplodedNode* generateCaseStmtNode(const iterator& I, const GRState* State);
 431
 432   ExplodedNode* generateDefaultCaseNode(const GRState* State,
 433                                         bool isSink = false);
 434
 435   const Expr* getCondition() const { return Condition; }
 436
 437   const GRState* getState() const { return Pred->State; }
 438 };
 439
 440 class GREndPathNodeBuilder {
 441   GRCoreEngine &Eng;
 442   const CFGBlock& B;
 443   ExplodedNode* Pred;
 444
 445 public:
 446   bool HasGeneratedNode;
 447
 448 public:
 449   GREndPathNodeBuilder(const CFGBlock* b, ExplodedNode* N, GRCoreEngine* e)
 450     : Eng(*e), B(*b), Pred(N), HasGeneratedNode(false) {}
 451
 452   ~GREndPathNodeBuilder();
 453
 454   GRWorkList &getWorkList() { return *Eng.WList; }
 455
 456   ExplodedNode* getPredecessor() const { return Pred; }
 457
 458   GRBlockCounter getBlockCounter() const {
 459     return Eng.WList->getBlockCounter();
 460   }
 461
 462   unsigned getCurrentBlockCount() const {
 463     return getBlockCounter().getNumVisited(
 464                             Pred->getLocationContext()->getCurrentStackFrame(),
 465                                            B.getBlockID());
 466   }
 467
 468   ExplodedNode* generateNode(const GRState* State, const void *tag = 0,
 469                              ExplodedNode *P = 0);
 470
 471   void GenerateCallExitNode(const GRState *state);
 472
 473   const CFGBlock* getBlock() const { return &B; }
 474
 475   const GRState* getState() const {
 476     return getPredecessor()->getState();
 477   }
 478 };
 479
 480 class GRCallEnterNodeBuilder {
 481   GRCoreEngine &Eng;
 482
 483   const ExplodedNode *Pred;
 484
 485   // The call site. For implicit automatic object dtor, this is the trigger
 486   // statement.
 487   const Stmt *CE;
 488
 489   // The context of the callee.
 490   const StackFrameContext *CalleeCtx;
 491
 492   // The parent block of the CallExpr.
 493   const CFGBlock *Block;
 494
 495   // The CFGBlock index of the CallExpr.
 496   unsigned Index;
 497
 498 public:
 499   GRCallEnterNodeBuilder(GRCoreEngine &eng, const ExplodedNode *pred,
 500                          const Stmt *s, const StackFrameContext *callee,
 501                          const CFGBlock *blk, unsigned idx)
 502     : Eng(eng), Pred(pred), CE(s), CalleeCtx(callee), Block(blk), Index(idx) {}
 503
 504   const GRState *getState() const { return Pred->getState(); }
 505
 506   const LocationContext *getLocationContext() const {
 507     return Pred->getLocationContext();
 508   }
 509
 510   const Stmt *getCallExpr() const { return CE; }
 511
 512   const StackFrameContext *getCalleeContext() const { return CalleeCtx; }
 513
 514   const CFGBlock *getBlock() const { return Block; }
 515
 516   unsigned getIndex() const { return Index; }
 517
 518   void generateNode(const GRState *state);
 519 };
 520
 521 class GRCallExitNodeBuilder {
 522   GRCoreEngine &Eng;
 523   const ExplodedNode *Pred;
 524
 525 public:
 526   GRCallExitNodeBuilder(GRCoreEngine &eng, const ExplodedNode *pred)
 527     : Eng(eng), Pred(pred) {}
 528
 529   const ExplodedNode *getPredecessor() const { return Pred; }
 530
 531   const GRState *getState() const { return Pred->getState(); }
 532
 533   void generateNode(const GRState *state);
 534 };
 535 } // end clang namespace
 536
 537 #endif