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