1 //==- CoreEngine.h - Path-Sensitive Dataflow Engine ----------------*- C++ -*-//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines a generic engine for intraprocedural, path-sensitive,
11 // dataflow analysis via graph reachability.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_CLANG_GR_COREENGINE
16 #define LLVM_CLANG_GR_COREENGINE
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"
28 class ProgramPointTag;
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).
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;
52 typedef std::vector<std::pair<BlockEdge, const ExplodedNode*> >
55 typedef std::vector<std::pair<const CFGBlock*, const ExplodedNode*> >
62 /// G - The simulation graph. Each node is a (location,state) pair.
63 OwningPtr<ExplodedGraph> G;
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.
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;
75 /// The locations where we stopped doing work because we visited a location
77 BlocksExhausted blocksExhausted;
79 /// The locations where we stopped because the engine aborted analysis,
80 /// usually because it could not reason about something.
81 BlocksAborted blocksAborted;
83 /// The functions which have been analyzed through inlining. This is owned by
84 /// AnalysisConsumer. It can be null.
85 SetOfConstDecls *AnalyzedCallees;
87 /// The information about functions shared by the whole translation unit.
88 /// (This data is owned by AnalysisConsumer.)
89 FunctionSummariesTy *FunctionSummaries;
91 void generateNode(const ProgramPoint &Loc,
92 ProgramStateRef State,
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);
100 void HandleBranch(const Stmt *Cond, const Stmt *Term, const CFGBlock *B,
104 CoreEngine(const CoreEngine&); // Do not implement.
105 CoreEngine& operator=(const CoreEngine&);
107 ExplodedNode *generateCallExitNode(ExplodedNode *N);
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){}
124 /// getGraph - Returns the exploded graph.
125 ExplodedGraph& getGraph() { return *G.get(); }
127 /// takeGraph - Returns the exploded graph. Ownership of the graph is
128 /// transferred to the caller.
129 ExplodedGraph* takeGraph() { return G.take(); }
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,
138 ProgramStateRef InitState,
139 ExplodedNodeSet &Dst);
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);
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() ||
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));
159 WorkList *getWorkList() const { return WList; }
161 BlocksExhausted::const_iterator blocks_exhausted_begin() const {
162 return blocksExhausted.begin();
164 BlocksExhausted::const_iterator blocks_exhausted_end() const {
165 return blocksExhausted.end();
167 BlocksAborted::const_iterator blocks_aborted_begin() const {
168 return blocksAborted.begin();
170 BlocksAborted::const_iterator blocks_aborted_end() const {
171 return blocksAborted.end();
174 /// \brief Enqueue the given set of nodes onto the work list.
175 void enqueue(ExplodedNodeSet &Set);
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);
181 /// \brief enqueue the nodes corresponding to the end of function onto the
182 /// end of path / work list.
183 void enqueueEndOfFunction(ExplodedNodeSet &Set);
185 /// \brief Enqueue a single node created as a result of statement processing.
186 void enqueueStmtNode(ExplodedNode *N, const CFGBlock *Block, unsigned Idx);
189 // TODO: Turn into a calss.
190 struct NodeBuilderContext {
192 const CFGBlock *Block;
194 NodeBuilderContext(CoreEngine &E, const CFGBlock *B, ExplodedNode *N)
195 : Eng(E), Block(B), Pred(N) { assert(B); assert(!N->isSink()); }
197 ExplodedNode *getPred() const { return Pred; }
199 /// \brief Return the CFGBlock associated with this builder.
200 const CFGBlock *getBlock() const { return Block; }
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());
211 /// \class NodeBuilder
212 /// \brief This is the simplest builder which generates nodes in the
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.
221 virtual void anchor();
223 const NodeBuilderContext &C;
225 /// Specifies if the builder results have been finalized. For example, if it
226 /// is set to false, autotransitions are yet to be generated.
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;
233 /// Checkes if the results are ready.
234 virtual bool checkResults() {
240 bool hasNoSinksInFrontier() {
241 for (iterator I = Frontier.begin(), E = Frontier.end(); I != E; ++I) {
248 /// Allow subclasses to finalize results before result_begin() is executed.
249 virtual void finalizeResults() {}
251 ExplodedNode *generateNodeImpl(const ProgramPoint &PP,
252 ProgramStateRef State,
254 bool MarkAsSink = false);
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);
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());
270 virtual ~NodeBuilder() {}
272 /// \brief Generates a node in the ExplodedGraph.
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,
279 bool MarkAsSink = false) {
280 return generateNodeImpl(PP, State, Pred, MarkAsSink);
283 const ExplodedNodeSet &getResults() {
285 assert(checkResults());
289 typedef ExplodedNodeSet::iterator iterator;
290 /// \brief Iterators through the results frontier.
291 inline iterator begin() {
293 assert(checkResults());
294 return Frontier.begin();
296 inline iterator end() {
298 return Frontier.end();
301 const NodeBuilderContext &getContext() { return C; }
302 bool hasGeneratedNodes() { return HasGeneratedNodes; }
304 void takeNodes(const ExplodedNodeSet &S) {
305 for (ExplodedNodeSet::iterator I = S.begin(), E = S.end(); I != E; ++I )
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); }
313 /// \class NodeBuilderWithSinks
314 /// \brief This node builder keeps track of the generated sink nodes.
315 class NodeBuilderWithSinks: public NodeBuilder {
316 virtual void anchor();
318 SmallVector<ExplodedNode*, 2> sinksGenerated;
319 ProgramPoint &Location;
322 NodeBuilderWithSinks(ExplodedNode *Pred, ExplodedNodeSet &DstSet,
323 const NodeBuilderContext &Ctx, ProgramPoint &L)
324 : NodeBuilder(Pred, DstSet, Ctx), Location(L) {}
325 ExplodedNode *generateNode(ProgramStateRef State,
327 const ProgramPointTag *Tag = 0,
328 bool MarkAsSink = false) {
329 ProgramPoint LocalLoc = (Tag ? Location.withTag(Tag): Location);
331 ExplodedNode *N = generateNodeImpl(LocalLoc, State, Pred, MarkAsSink);
332 if (N && N->isSink())
333 sinksGenerated.push_back(N);
337 const SmallVectorImpl<ExplodedNode*> &getSinks() const {
338 return sinksGenerated;
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;
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) {
357 EnclosingBldr->takeNodes(SrcNode);
360 StmtNodeBuilder(ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet,
361 const NodeBuilderContext &Ctx, NodeBuilder *Enclosing = 0)
362 : NodeBuilder(SrcSet, DstSet, Ctx), EnclosingBldr(Enclosing) {
364 for (ExplodedNodeSet::iterator I = SrcSet.begin(),
365 E = SrcSet.end(); I != E; ++I )
366 EnclosingBldr->takeNodes(*I);
369 virtual ~StmtNodeBuilder();
371 ExplodedNode *generateNode(const Stmt *S,
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);
382 ExplodedNode *generateNode(const ProgramPoint &PP,
384 ProgramStateRef State,
385 bool MarkAsSink = false) {
386 return generateNodeImpl(PP, State, Pred, MarkAsSink);
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;
398 bool InFeasibleFalse;
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.
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) {
419 ExplodedNode *generateNode(ProgramStateRef State, bool branch,
422 const CFGBlock *getTargetBlock(bool branch) const {
423 return branch ? DstT : DstF;
426 void markInfeasible(bool branch) {
428 InFeasibleTrue = true;
430 InFeasibleFalse = true;
433 bool isFeasible(bool branch) {
434 return branch ? !InFeasibleTrue : !InFeasibleFalse;
438 class IndirectGotoNodeBuilder {
441 const CFGBlock &DispatchBlock;
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) {}
451 CFGBlock::const_succ_iterator I;
453 friend class IndirectGotoNodeBuilder;
454 iterator(CFGBlock::const_succ_iterator i) : I(i) {}
457 iterator &operator++() { ++I; return *this; }
458 bool operator!=(const iterator &X) const { return I != X.I; }
460 const LabelDecl *getLabel() const {
461 return llvm::cast<LabelStmt>((*I)->getLabel())->getDecl();
464 const CFGBlock *getBlock() const {
469 iterator begin() { return iterator(DispatchBlock.succ_begin()); }
470 iterator end() { return iterator(DispatchBlock.succ_end()); }
472 ExplodedNode *generateNode(const iterator &I,
473 ProgramStateRef State,
474 bool isSink = false);
476 const Expr *getTarget() const { return E; }
478 ProgramStateRef getState() const { return Pred->State; }
480 const LocationContext *getLocationContext() const {
481 return Pred->getLocationContext();
485 class SwitchNodeBuilder {
488 const Expr *Condition;
492 SwitchNodeBuilder(ExplodedNode *pred, const CFGBlock *src,
493 const Expr *condition, CoreEngine* eng)
494 : Eng(*eng), Src(src), Condition(condition), Pred(pred) {}
497 CFGBlock::const_succ_reverse_iterator I;
499 friend class SwitchNodeBuilder;
500 iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {}
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; }
507 const CaseStmt *getCase() const {
508 return llvm::cast<CaseStmt>((*I)->getLabel());
511 const CFGBlock *getBlock() const {
516 iterator begin() { return iterator(Src->succ_rbegin()+1); }
517 iterator end() { return iterator(Src->succ_rend()); }
519 const SwitchStmt *getSwitch() const {
520 return llvm::cast<SwitchStmt>(Src->getTerminator());
523 ExplodedNode *generateCaseStmtNode(const iterator &I,
524 ProgramStateRef State);
526 ExplodedNode *generateDefaultCaseNode(ProgramStateRef State,
527 bool isSink = false);
529 const Expr *getCondition() const { return Condition; }
531 ProgramStateRef getState() const { return Pred->State; }
533 const LocationContext *getLocationContext() const {
534 return Pred->getLocationContext();
538 } // end ento namespace
539 } // end clang namespace