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