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_STATICANALYZER_CORE_PATHSENSITIVE_COREENGINE_H
16 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_COREENGINE_H
18 #include "clang/AST/Expr.h"
19 #include "clang/Analysis/AnalysisDeclContext.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"
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 mutable 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.
68 std::unique_ptr<WorkList> WList;
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 information about functions shared by the whole translation unit.
84 /// (This data is owned by AnalysisConsumer.)
85 FunctionSummariesTy *FunctionSummaries;
87 void generateNode(const ProgramPoint &Loc,
88 ProgramStateRef State,
91 void HandleBlockEdge(const BlockEdge &E, ExplodedNode *Pred);
92 void HandleBlockEntrance(const BlockEntrance &E, ExplodedNode *Pred);
93 void HandleBlockExit(const CFGBlock *B, ExplodedNode *Pred);
95 void HandleCallEnter(const CallEnter &CE, ExplodedNode *Pred);
97 void HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, ExplodedNode *Pred);
99 void HandleBranch(const Stmt *Cond, const Stmt *Term, const CFGBlock *B,
101 void HandleCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE,
102 const CFGBlock *B, ExplodedNode *Pred);
104 /// Handle conditional logic for running static initializers.
105 void HandleStaticInit(const DeclStmt *DS, const CFGBlock *B,
109 CoreEngine(const CoreEngine &) = delete;
110 void operator=(const CoreEngine &) = delete;
112 ExplodedNode *generateCallExitBeginNode(ExplodedNode *N,
113 const ReturnStmt *RS);
116 /// Construct a CoreEngine object to analyze the provided CFG.
117 CoreEngine(SubEngine &subengine, FunctionSummariesTy *FS)
118 : SubEng(subengine), WList(WorkList::makeDFS()),
119 BCounterFactory(G.getAllocator()), FunctionSummaries(FS) {}
121 /// getGraph - Returns the exploded graph.
122 ExplodedGraph &getGraph() { return G; }
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 ProgramStateRef InitState);
128 /// Returns true if there is still simulation state on the worklist.
129 bool ExecuteWorkListWithInitialState(const LocationContext *L,
131 ProgramStateRef InitState,
132 ExplodedNodeSet &Dst);
134 /// Dispatch the work list item based on the given location information.
135 /// Use Pred parameter as the predecessor state.
136 void dispatchWorkItem(ExplodedNode* Pred, ProgramPoint Loc,
137 const WorkListUnit& WU);
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() ||
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));
152 WorkList *getWorkList() const { return WList.get(); }
154 BlocksExhausted::const_iterator blocks_exhausted_begin() const {
155 return blocksExhausted.begin();
157 BlocksExhausted::const_iterator blocks_exhausted_end() const {
158 return blocksExhausted.end();
160 BlocksAborted::const_iterator blocks_aborted_begin() const {
161 return blocksAborted.begin();
163 BlocksAborted::const_iterator blocks_aborted_end() const {
164 return blocksAborted.end();
167 /// \brief Enqueue the given set of nodes onto the work list.
168 void enqueue(ExplodedNodeSet &Set);
170 /// \brief Enqueue nodes that were created as a result of processing
171 /// a statement onto the work list.
172 void enqueue(ExplodedNodeSet &Set, const CFGBlock *Block, unsigned Idx);
174 /// \brief enqueue the nodes corresponding to the end of function onto the
175 /// end of path / work list.
176 void enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS);
178 /// \brief Enqueue a single node created as a result of statement processing.
179 void enqueueStmtNode(ExplodedNode *N, const CFGBlock *Block, unsigned Idx);
182 // TODO: Turn into a calss.
183 struct NodeBuilderContext {
184 const CoreEngine &Eng;
185 const CFGBlock *Block;
186 const LocationContext *LC;
187 NodeBuilderContext(const CoreEngine &E, const CFGBlock *B, ExplodedNode *N)
188 : Eng(E), Block(B), LC(N->getLocationContext()) { assert(B); }
190 /// \brief Return the CFGBlock associated with this builder.
191 const CFGBlock *getBlock() const { return Block; }
193 /// \brief Returns the number of times the current basic block has been
194 /// visited on the exploded graph path.
195 unsigned blockCount() const {
196 return Eng.WList->getBlockCounter().getNumVisited(
197 LC->getCurrentStackFrame(),
198 Block->getBlockID());
202 /// \class NodeBuilder
203 /// \brief This is the simplest builder which generates nodes in the
206 /// The main benefit of the builder is that it automatically tracks the
207 /// frontier nodes (or destination set). This is the set of nodes which should
208 /// be propagated to the next step / builder. They are the nodes which have been
209 /// added to the builder (either as the input node set or as the newly
210 /// constructed nodes) but did not have any outgoing transitions added.
212 virtual void anchor();
214 const NodeBuilderContext &C;
216 /// Specifies if the builder results have been finalized. For example, if it
217 /// is set to false, autotransitions are yet to be generated.
219 bool HasGeneratedNodes;
220 /// \brief The frontier set - a set of nodes which need to be propagated after
221 /// the builder dies.
222 ExplodedNodeSet &Frontier;
224 /// Checkes if the results are ready.
225 virtual bool checkResults() {
231 bool hasNoSinksInFrontier() {
232 for (iterator I = Frontier.begin(), E = Frontier.end(); I != E; ++I) {
239 /// Allow subclasses to finalize results before result_begin() is executed.
240 virtual void finalizeResults() {}
242 ExplodedNode *generateNodeImpl(const ProgramPoint &PP,
243 ProgramStateRef State,
245 bool MarkAsSink = false);
248 NodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet,
249 const NodeBuilderContext &Ctx, bool F = true)
250 : C(Ctx), Finalized(F), HasGeneratedNodes(false), Frontier(DstSet) {
251 Frontier.Add(SrcNode);
254 NodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet,
255 const NodeBuilderContext &Ctx, bool F = true)
256 : C(Ctx), Finalized(F), HasGeneratedNodes(false), Frontier(DstSet) {
257 Frontier.insert(SrcSet);
258 assert(hasNoSinksInFrontier());
261 virtual ~NodeBuilder() {}
263 /// \brief Generates a node in the ExplodedGraph.
264 ExplodedNode *generateNode(const ProgramPoint &PP,
265 ProgramStateRef State,
266 ExplodedNode *Pred) {
267 return generateNodeImpl(PP, State, Pred, false);
270 /// \brief Generates a sink in the ExplodedGraph.
272 /// When a node is marked as sink, the exploration from the node is stopped -
273 /// the node becomes the last node on the path and certain kinds of bugs are
275 ExplodedNode *generateSink(const ProgramPoint &PP,
276 ProgramStateRef State,
277 ExplodedNode *Pred) {
278 return generateNodeImpl(PP, State, Pred, true);
281 const ExplodedNodeSet &getResults() {
283 assert(checkResults());
287 typedef ExplodedNodeSet::iterator iterator;
288 /// \brief Iterators through the results frontier.
289 inline iterator begin() {
291 assert(checkResults());
292 return Frontier.begin();
294 inline iterator end() {
296 return Frontier.end();
299 const NodeBuilderContext &getContext() { return C; }
300 bool hasGeneratedNodes() { return HasGeneratedNodes; }
302 void takeNodes(const ExplodedNodeSet &S) {
303 for (ExplodedNodeSet::iterator I = S.begin(), E = S.end(); I != E; ++I )
306 void takeNodes(ExplodedNode *N) { Frontier.erase(N); }
307 void addNodes(const ExplodedNodeSet &S) { Frontier.insert(S); }
308 void addNodes(ExplodedNode *N) { Frontier.Add(N); }
311 /// \class NodeBuilderWithSinks
312 /// \brief This node builder keeps track of the generated sink nodes.
313 class NodeBuilderWithSinks: public NodeBuilder {
314 void anchor() override;
316 SmallVector<ExplodedNode*, 2> sinksGenerated;
317 ProgramPoint &Location;
320 NodeBuilderWithSinks(ExplodedNode *Pred, ExplodedNodeSet &DstSet,
321 const NodeBuilderContext &Ctx, ProgramPoint &L)
322 : NodeBuilder(Pred, DstSet, Ctx), Location(L) {}
324 ExplodedNode *generateNode(ProgramStateRef State,
326 const ProgramPointTag *Tag = nullptr) {
327 const ProgramPoint &LocalLoc = (Tag ? Location.withTag(Tag) : Location);
328 return NodeBuilder::generateNode(LocalLoc, State, Pred);
331 ExplodedNode *generateSink(ProgramStateRef State, ExplodedNode *Pred,
332 const ProgramPointTag *Tag = nullptr) {
333 const ProgramPoint &LocalLoc = (Tag ? Location.withTag(Tag) : Location);
334 ExplodedNode *N = NodeBuilder::generateSink(LocalLoc, State, Pred);
335 if (N && N->isSink())
336 sinksGenerated.push_back(N);
340 const SmallVectorImpl<ExplodedNode*> &getSinks() const {
341 return sinksGenerated;
345 /// \class StmtNodeBuilder
346 /// \brief This builder class is useful for generating nodes that resulted from
347 /// visiting a statement. The main difference from its parent NodeBuilder is
348 /// that it creates a statement specific ProgramPoint.
349 class StmtNodeBuilder: public NodeBuilder {
350 NodeBuilder *EnclosingBldr;
353 /// \brief Constructs a StmtNodeBuilder. If the builder is going to process
354 /// nodes currently owned by another builder(with larger scope), use
355 /// Enclosing builder to transfer ownership.
356 StmtNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet,
357 const NodeBuilderContext &Ctx,
358 NodeBuilder *Enclosing = nullptr)
359 : NodeBuilder(SrcNode, DstSet, Ctx), EnclosingBldr(Enclosing) {
361 EnclosingBldr->takeNodes(SrcNode);
364 StmtNodeBuilder(ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet,
365 const NodeBuilderContext &Ctx,
366 NodeBuilder *Enclosing = nullptr)
367 : NodeBuilder(SrcSet, DstSet, Ctx), EnclosingBldr(Enclosing) {
369 for (ExplodedNodeSet::iterator I = SrcSet.begin(),
370 E = SrcSet.end(); I != E; ++I )
371 EnclosingBldr->takeNodes(*I);
374 ~StmtNodeBuilder() override;
376 using NodeBuilder::generateNode;
377 using NodeBuilder::generateSink;
379 ExplodedNode *generateNode(const Stmt *S,
382 const ProgramPointTag *tag = nullptr,
383 ProgramPoint::Kind K = ProgramPoint::PostStmtKind){
384 const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K,
385 Pred->getLocationContext(), tag);
386 return NodeBuilder::generateNode(L, St, Pred);
389 ExplodedNode *generateSink(const Stmt *S,
392 const ProgramPointTag *tag = nullptr,
393 ProgramPoint::Kind K = ProgramPoint::PostStmtKind){
394 const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K,
395 Pred->getLocationContext(), tag);
396 return NodeBuilder::generateSink(L, St, Pred);
400 /// \brief BranchNodeBuilder is responsible for constructing the nodes
401 /// corresponding to the two branches of the if statement - true and false.
402 class BranchNodeBuilder: public NodeBuilder {
403 void anchor() override;
404 const CFGBlock *DstT;
405 const CFGBlock *DstF;
408 bool InFeasibleFalse;
411 BranchNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet,
412 const NodeBuilderContext &C,
413 const CFGBlock *dstT, const CFGBlock *dstF)
414 : NodeBuilder(SrcNode, DstSet, C), DstT(dstT), DstF(dstF),
415 InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {
416 // The branch node builder does not generate autotransitions.
417 // If there are no successors it means that both branches are infeasible.
421 BranchNodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet,
422 const NodeBuilderContext &C,
423 const CFGBlock *dstT, const CFGBlock *dstF)
424 : NodeBuilder(SrcSet, DstSet, C), DstT(dstT), DstF(dstF),
425 InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {
429 ExplodedNode *generateNode(ProgramStateRef State, bool branch,
432 const CFGBlock *getTargetBlock(bool branch) const {
433 return branch ? DstT : DstF;
436 void markInfeasible(bool branch) {
438 InFeasibleTrue = true;
440 InFeasibleFalse = true;
443 bool isFeasible(bool branch) {
444 return branch ? !InFeasibleTrue : !InFeasibleFalse;
448 class IndirectGotoNodeBuilder {
451 const CFGBlock &DispatchBlock;
456 IndirectGotoNodeBuilder(ExplodedNode *pred, const CFGBlock *src,
457 const Expr *e, const CFGBlock *dispatch, CoreEngine* eng)
458 : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {}
461 CFGBlock::const_succ_iterator I;
463 friend class IndirectGotoNodeBuilder;
464 iterator(CFGBlock::const_succ_iterator i) : I(i) {}
467 iterator &operator++() { ++I; return *this; }
468 bool operator!=(const iterator &X) const { return I != X.I; }
470 const LabelDecl *getLabel() const {
471 return cast<LabelStmt>((*I)->getLabel())->getDecl();
474 const CFGBlock *getBlock() const {
479 iterator begin() { return iterator(DispatchBlock.succ_begin()); }
480 iterator end() { return iterator(DispatchBlock.succ_end()); }
482 ExplodedNode *generateNode(const iterator &I,
483 ProgramStateRef State,
484 bool isSink = false);
486 const Expr *getTarget() const { return E; }
488 ProgramStateRef getState() const { return Pred->State; }
490 const LocationContext *getLocationContext() const {
491 return Pred->getLocationContext();
495 class SwitchNodeBuilder {
498 const Expr *Condition;
502 SwitchNodeBuilder(ExplodedNode *pred, const CFGBlock *src,
503 const Expr *condition, CoreEngine* eng)
504 : Eng(*eng), Src(src), Condition(condition), Pred(pred) {}
507 CFGBlock::const_succ_reverse_iterator I;
509 friend class SwitchNodeBuilder;
510 iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {}
513 iterator &operator++() { ++I; return *this; }
514 bool operator!=(const iterator &X) const { return I != X.I; }
515 bool operator==(const iterator &X) const { return I == X.I; }
517 const CaseStmt *getCase() const {
518 return cast<CaseStmt>((*I)->getLabel());
521 const CFGBlock *getBlock() const {
526 iterator begin() { return iterator(Src->succ_rbegin()+1); }
527 iterator end() { return iterator(Src->succ_rend()); }
529 const SwitchStmt *getSwitch() const {
530 return cast<SwitchStmt>(Src->getTerminator());
533 ExplodedNode *generateCaseStmtNode(const iterator &I,
534 ProgramStateRef State);
536 ExplodedNode *generateDefaultCaseNode(ProgramStateRef State,
537 bool isSink = false);
539 const Expr *getCondition() const { return Condition; }
541 ProgramStateRef getState() const { return Pred->State; }
543 const LocationContext *getLocationContext() const {
544 return Pred->getLocationContext();
548 } // end ento namespace
549 } // end clang namespace