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