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