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

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