1 //==- CoreEngine.cpp - 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 engine.
13 //===----------------------------------------------------------------------===//
15 #include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h"
16 #include "clang/AST/Expr.h"
17 #include "clang/AST/ExprCXX.h"
18 #include "clang/AST/StmtCXX.h"
19 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
20 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
21 #include "llvm/ADT/Statistic.h"
22 #include "llvm/Support/Casting.h"
24 using namespace clang;
27 #define DEBUG_TYPE "CoreEngine"
30 "The # of steps executed.");
31 STATISTIC(NumReachedMaxSteps,
32 "The # of times we reached the max number of steps.");
33 STATISTIC(NumPathsExplored,
34 "The # of paths explored by the analyzer.");
36 //===----------------------------------------------------------------------===//
37 // Worklist classes for exploration of reachable states.
38 //===----------------------------------------------------------------------===//
40 WorkList::Visitor::~Visitor() {}
43 class DFS : public WorkList {
44 SmallVector<WorkListUnit,20> Stack;
46 bool hasWork() const override {
47 return !Stack.empty();
50 void enqueue(const WorkListUnit& U) override {
54 WorkListUnit dequeue() override {
55 assert (!Stack.empty());
56 const WorkListUnit& U = Stack.back();
57 Stack.pop_back(); // This technically "invalidates" U, but we are fine.
61 bool visitItemsInWorkList(Visitor &V) override {
62 for (SmallVectorImpl<WorkListUnit>::iterator
63 I = Stack.begin(), E = Stack.end(); I != E; ++I) {
71 class BFS : public WorkList {
72 std::deque<WorkListUnit> Queue;
74 bool hasWork() const override {
75 return !Queue.empty();
78 void enqueue(const WorkListUnit& U) override {
82 WorkListUnit dequeue() override {
83 WorkListUnit U = Queue.front();
88 bool visitItemsInWorkList(Visitor &V) override {
89 for (std::deque<WorkListUnit>::iterator
90 I = Queue.begin(), E = Queue.end(); I != E; ++I) {
98 } // end anonymous namespace
100 // Place the dstor for WorkList here because it contains virtual member
101 // functions, and we the code for the dstor generated in one compilation unit.
102 WorkList::~WorkList() {}
104 WorkList *WorkList::makeDFS() { return new DFS(); }
105 WorkList *WorkList::makeBFS() { return new BFS(); }
108 class BFSBlockDFSContents : public WorkList {
109 std::deque<WorkListUnit> Queue;
110 SmallVector<WorkListUnit,20> Stack;
112 bool hasWork() const override {
113 return !Queue.empty() || !Stack.empty();
116 void enqueue(const WorkListUnit& U) override {
117 if (U.getNode()->getLocation().getAs<BlockEntrance>())
123 WorkListUnit dequeue() override {
124 // Process all basic blocks to completion.
125 if (!Stack.empty()) {
126 const WorkListUnit& U = Stack.back();
127 Stack.pop_back(); // This technically "invalidates" U, but we are fine.
131 assert(!Queue.empty());
132 // Don't use const reference. The subsequent pop_back() might make it
134 WorkListUnit U = Queue.front();
138 bool visitItemsInWorkList(Visitor &V) override {
139 for (SmallVectorImpl<WorkListUnit>::iterator
140 I = Stack.begin(), E = Stack.end(); I != E; ++I) {
144 for (std::deque<WorkListUnit>::iterator
145 I = Queue.begin(), E = Queue.end(); I != E; ++I) {
153 } // end anonymous namespace
155 WorkList* WorkList::makeBFSBlockDFSContents() {
156 return new BFSBlockDFSContents();
159 //===----------------------------------------------------------------------===//
160 // Core analysis engine.
161 //===----------------------------------------------------------------------===//
163 /// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps.
164 bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps,
165 ProgramStateRef InitState) {
167 if (G.num_roots() == 0) { // Initialize the analysis by constructing
168 // the root if none exists.
170 const CFGBlock *Entry = &(L->getCFG()->getEntry());
172 assert (Entry->empty() &&
173 "Entry block must be empty.");
175 assert (Entry->succ_size() == 1 &&
176 "Entry block must have 1 successor.");
178 // Mark the entry block as visited.
179 FunctionSummaries->markVisitedBasicBlock(Entry->getBlockID(),
181 L->getCFG()->getNumBlockIDs());
183 // Get the solitary successor.
184 const CFGBlock *Succ = *(Entry->succ_begin());
186 // Construct an edge representing the
187 // starting location in the function.
188 BlockEdge StartLoc(Entry, Succ, L);
190 // Set the current block counter to being empty.
191 WList->setBlockCounter(BCounterFactory.GetEmptyCounter());
194 InitState = SubEng.getInitialState(L);
197 ExplodedNode *Node = G.getNode(StartLoc, InitState, false, &IsNew);
201 NodeBuilderContext BuilderCtx(*this, StartLoc.getDst(), Node);
202 ExplodedNodeSet DstBegin;
203 SubEng.processBeginOfFunction(BuilderCtx, Node, DstBegin, StartLoc);
208 // Check if we have a steps limit
209 bool UnlimitedSteps = Steps == 0;
210 // Cap our pre-reservation in the event that the user specifies
211 // a very large number of maximum steps.
212 const unsigned PreReservationCap = 4000000;
214 G.reserve(std::min(Steps,PreReservationCap));
216 while (WList->hasWork()) {
217 if (!UnlimitedSteps) {
219 NumReachedMaxSteps++;
227 const WorkListUnit& WU = WList->dequeue();
229 // Set the current block counter.
230 WList->setBlockCounter(WU.getBlockCounter());
232 // Retrieve the node.
233 ExplodedNode *Node = WU.getNode();
235 dispatchWorkItem(Node, Node->getLocation(), WU);
237 SubEng.processEndWorklist(hasWorkRemaining());
238 return WList->hasWork();
241 void CoreEngine::dispatchWorkItem(ExplodedNode* Pred, ProgramPoint Loc,
242 const WorkListUnit& WU) {
243 // Dispatch on the location type.
244 switch (Loc.getKind()) {
245 case ProgramPoint::BlockEdgeKind:
246 HandleBlockEdge(Loc.castAs<BlockEdge>(), Pred);
249 case ProgramPoint::BlockEntranceKind:
250 HandleBlockEntrance(Loc.castAs<BlockEntrance>(), Pred);
253 case ProgramPoint::BlockExitKind:
254 assert (false && "BlockExit location never occur in forward analysis.");
257 case ProgramPoint::CallEnterKind: {
258 HandleCallEnter(Loc.castAs<CallEnter>(), Pred);
262 case ProgramPoint::CallExitBeginKind:
263 SubEng.processCallExit(Pred);
266 case ProgramPoint::EpsilonKind: {
267 assert(Pred->hasSinglePred() &&
268 "Assume epsilon has exactly one predecessor by construction");
269 ExplodedNode *PNode = Pred->getFirstPred();
270 dispatchWorkItem(Pred, PNode->getLocation(), WU);
274 assert(Loc.getAs<PostStmt>() ||
275 Loc.getAs<PostInitializer>() ||
276 Loc.getAs<PostImplicitCall>() ||
277 Loc.getAs<CallExitEnd>());
278 HandlePostStmt(WU.getBlock(), WU.getIndex(), Pred);
283 bool CoreEngine::ExecuteWorkListWithInitialState(const LocationContext *L,
285 ProgramStateRef InitState,
286 ExplodedNodeSet &Dst) {
287 bool DidNotFinish = ExecuteWorkList(L, Steps, InitState);
288 for (ExplodedGraph::eop_iterator I = G.eop_begin(), E = G.eop_end(); I != E;
295 void CoreEngine::HandleBlockEdge(const BlockEdge &L, ExplodedNode *Pred) {
297 const CFGBlock *Blk = L.getDst();
298 NodeBuilderContext BuilderCtx(*this, Blk, Pred);
300 // Mark this block as visited.
301 const LocationContext *LC = Pred->getLocationContext();
302 FunctionSummaries->markVisitedBasicBlock(Blk->getBlockID(),
304 LC->getCFG()->getNumBlockIDs());
306 // Check if we are entering the EXIT block.
307 if (Blk == &(L.getLocationContext()->getCFG()->getExit())) {
309 assert (L.getLocationContext()->getCFG()->getExit().size() == 0
310 && "EXIT block cannot contain Stmts.");
312 // Get return statement..
313 const ReturnStmt *RS = nullptr;
314 if (!L.getSrc()->empty()) {
315 if (Optional<CFGStmt> LastStmt = L.getSrc()->back().getAs<CFGStmt>()) {
316 if ((RS = dyn_cast<ReturnStmt>(LastStmt->getStmt()))) {
317 if (!RS->getRetValue())
323 // Process the final state transition.
324 SubEng.processEndOfFunction(BuilderCtx, Pred, RS);
326 // This path is done. Don't enqueue any more nodes.
330 // Call into the SubEngine to process entering the CFGBlock.
331 ExplodedNodeSet dstNodes;
332 BlockEntrance BE(Blk, Pred->getLocationContext());
333 NodeBuilderWithSinks nodeBuilder(Pred, dstNodes, BuilderCtx, BE);
334 SubEng.processCFGBlockEntrance(L, nodeBuilder, Pred);
336 // Auto-generate a node.
337 if (!nodeBuilder.hasGeneratedNodes()) {
338 nodeBuilder.generateNode(Pred->State, Pred);
341 // Enqueue nodes onto the worklist.
345 void CoreEngine::HandleBlockEntrance(const BlockEntrance &L,
346 ExplodedNode *Pred) {
348 // Increment the block counter.
349 const LocationContext *LC = Pred->getLocationContext();
350 unsigned BlockId = L.getBlock()->getBlockID();
351 BlockCounter Counter = WList->getBlockCounter();
352 Counter = BCounterFactory.IncrementCount(Counter, LC->getCurrentStackFrame(),
354 WList->setBlockCounter(Counter);
356 // Process the entrance of the block.
357 if (Optional<CFGElement> E = L.getFirstElement()) {
358 NodeBuilderContext Ctx(*this, L.getBlock(), Pred);
359 SubEng.processCFGElement(*E, Pred, 0, &Ctx);
362 HandleBlockExit(L.getBlock(), Pred);
365 void CoreEngine::HandleBlockExit(const CFGBlock * B, ExplodedNode *Pred) {
367 if (const Stmt *Term = B->getTerminator()) {
368 switch (Term->getStmtClass()) {
370 llvm_unreachable("Analysis for this terminator not implemented.");
372 case Stmt::CXXBindTemporaryExprClass:
373 HandleCleanupTemporaryBranch(
374 cast<CXXBindTemporaryExpr>(B->getTerminator().getStmt()), B, Pred);
377 // Model static initializers.
378 case Stmt::DeclStmtClass:
379 HandleStaticInit(cast<DeclStmt>(Term), B, Pred);
382 case Stmt::BinaryOperatorClass: // '&&' and '||'
383 HandleBranch(cast<BinaryOperator>(Term)->getLHS(), Term, B, Pred);
386 case Stmt::BinaryConditionalOperatorClass:
387 case Stmt::ConditionalOperatorClass:
388 HandleBranch(cast<AbstractConditionalOperator>(Term)->getCond(),
392 // FIXME: Use constant-folding in CFG construction to simplify this
395 case Stmt::ChooseExprClass:
396 HandleBranch(cast<ChooseExpr>(Term)->getCond(), Term, B, Pred);
399 case Stmt::CXXTryStmtClass: {
400 // Generate a node for each of the successors.
401 // Our logic for EH analysis can certainly be improved.
402 for (CFGBlock::const_succ_iterator it = B->succ_begin(),
403 et = B->succ_end(); it != et; ++it) {
404 if (const CFGBlock *succ = *it) {
405 generateNode(BlockEdge(B, succ, Pred->getLocationContext()),
412 case Stmt::DoStmtClass:
413 HandleBranch(cast<DoStmt>(Term)->getCond(), Term, B, Pred);
416 case Stmt::CXXForRangeStmtClass:
417 HandleBranch(cast<CXXForRangeStmt>(Term)->getCond(), Term, B, Pred);
420 case Stmt::ForStmtClass:
421 HandleBranch(cast<ForStmt>(Term)->getCond(), Term, B, Pred);
424 case Stmt::ContinueStmtClass:
425 case Stmt::BreakStmtClass:
426 case Stmt::GotoStmtClass:
429 case Stmt::IfStmtClass:
430 HandleBranch(cast<IfStmt>(Term)->getCond(), Term, B, Pred);
433 case Stmt::IndirectGotoStmtClass: {
434 // Only 1 successor: the indirect goto dispatch block.
435 assert (B->succ_size() == 1);
437 IndirectGotoNodeBuilder
438 builder(Pred, B, cast<IndirectGotoStmt>(Term)->getTarget(),
439 *(B->succ_begin()), this);
441 SubEng.processIndirectGoto(builder);
445 case Stmt::ObjCForCollectionStmtClass: {
446 // In the case of ObjCForCollectionStmt, it appears twice in a CFG:
448 // (1) inside a basic block, which represents the binding of the
449 // 'element' variable to a value.
450 // (2) in a terminator, which represents the branch.
452 // For (1), subengines will bind a value (i.e., 0 or 1) indicating
453 // whether or not collection contains any more elements. We cannot
454 // just test to see if the element is nil because a container can
455 // contain nil elements.
456 HandleBranch(Term, Term, B, Pred);
460 case Stmt::SwitchStmtClass: {
461 SwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(),
464 SubEng.processSwitch(builder);
468 case Stmt::WhileStmtClass:
469 HandleBranch(cast<WhileStmt>(Term)->getCond(), Term, B, Pred);
474 assert (B->succ_size() == 1 &&
475 "Blocks with no terminator should have at most 1 successor.");
477 generateNode(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()),
481 void CoreEngine::HandleCallEnter(const CallEnter &CE, ExplodedNode *Pred) {
482 NodeBuilderContext BuilderCtx(*this, CE.getEntry(), Pred);
483 SubEng.processCallEnter(BuilderCtx, CE, Pred);
486 void CoreEngine::HandleBranch(const Stmt *Cond, const Stmt *Term,
487 const CFGBlock * B, ExplodedNode *Pred) {
488 assert(B->succ_size() == 2);
489 NodeBuilderContext Ctx(*this, B, Pred);
491 SubEng.processBranch(Cond, Term, Ctx, Pred, Dst,
492 *(B->succ_begin()), *(B->succ_begin()+1));
493 // Enqueue the new frontier onto the worklist.
497 void CoreEngine::HandleCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE,
499 ExplodedNode *Pred) {
500 assert(B->succ_size() == 2);
501 NodeBuilderContext Ctx(*this, B, Pred);
503 SubEng.processCleanupTemporaryBranch(BTE, Ctx, Pred, Dst, *(B->succ_begin()),
504 *(B->succ_begin() + 1));
505 // Enqueue the new frontier onto the worklist.
509 void CoreEngine::HandleStaticInit(const DeclStmt *DS, const CFGBlock *B,
510 ExplodedNode *Pred) {
511 assert(B->succ_size() == 2);
512 NodeBuilderContext Ctx(*this, B, Pred);
514 SubEng.processStaticInitializer(DS, Ctx, Pred, Dst,
515 *(B->succ_begin()), *(B->succ_begin()+1));
516 // Enqueue the new frontier onto the worklist.
521 void CoreEngine::HandlePostStmt(const CFGBlock *B, unsigned StmtIdx,
522 ExplodedNode *Pred) {
526 if (StmtIdx == B->size())
527 HandleBlockExit(B, Pred);
529 NodeBuilderContext Ctx(*this, B, Pred);
530 SubEng.processCFGElement((*B)[StmtIdx], Pred, StmtIdx, &Ctx);
534 /// generateNode - Utility method to generate nodes, hook up successors,
535 /// and add nodes to the worklist.
536 void CoreEngine::generateNode(const ProgramPoint &Loc,
537 ProgramStateRef State,
538 ExplodedNode *Pred) {
541 ExplodedNode *Node = G.getNode(Loc, State, false, &IsNew);
544 Node->addPredecessor(Pred, G); // Link 'Node' with its predecessor.
547 G.addRoot(Node); // 'Node' has no predecessor. Make it a root.
550 // Only add 'Node' to the worklist if it was freshly generated.
551 if (IsNew) WList->enqueue(Node);
554 void CoreEngine::enqueueStmtNode(ExplodedNode *N,
555 const CFGBlock *Block, unsigned Idx) {
557 assert (!N->isSink());
559 // Check if this node entered a callee.
560 if (N->getLocation().getAs<CallEnter>()) {
561 // Still use the index of the CallExpr. It's needed to create the callee
562 // StackFrameContext.
563 WList->enqueue(N, Block, Idx);
567 // Do not create extra nodes. Move to the next CFG element.
568 if (N->getLocation().getAs<PostInitializer>() ||
569 N->getLocation().getAs<PostImplicitCall>()) {
570 WList->enqueue(N, Block, Idx+1);
574 if (N->getLocation().getAs<EpsilonPoint>()) {
575 WList->enqueue(N, Block, Idx);
579 if ((*Block)[Idx].getKind() == CFGElement::NewAllocator) {
580 WList->enqueue(N, Block, Idx+1);
584 // At this point, we know we're processing a normal statement.
585 CFGStmt CS = (*Block)[Idx].castAs<CFGStmt>();
586 PostStmt Loc(CS.getStmt(), N->getLocationContext());
588 if (Loc == N->getLocation().withTag(nullptr)) {
589 // Note: 'N' should be a fresh node because otherwise it shouldn't be
590 // a member of Deferred.
591 WList->enqueue(N, Block, Idx+1);
596 ExplodedNode *Succ = G.getNode(Loc, N->getState(), false, &IsNew);
597 Succ->addPredecessor(N, G);
600 WList->enqueue(Succ, Block, Idx+1);
603 ExplodedNode *CoreEngine::generateCallExitBeginNode(ExplodedNode *N,
604 const ReturnStmt *RS) {
605 // Create a CallExitBegin node and enqueue it.
606 const StackFrameContext *LocCtx
607 = cast<StackFrameContext>(N->getLocationContext());
609 // Use the callee location context.
610 CallExitBegin Loc(LocCtx, RS);
613 ExplodedNode *Node = G.getNode(Loc, N->getState(), false, &isNew);
614 Node->addPredecessor(N, G);
615 return isNew ? Node : nullptr;
619 void CoreEngine::enqueue(ExplodedNodeSet &Set) {
620 for (ExplodedNodeSet::iterator I = Set.begin(),
621 E = Set.end(); I != E; ++I) {
626 void CoreEngine::enqueue(ExplodedNodeSet &Set,
627 const CFGBlock *Block, unsigned Idx) {
628 for (ExplodedNodeSet::iterator I = Set.begin(),
629 E = Set.end(); I != E; ++I) {
630 enqueueStmtNode(*I, Block, Idx);
634 void CoreEngine::enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS) {
635 for (ExplodedNodeSet::iterator I = Set.begin(), E = Set.end(); I != E; ++I) {
636 ExplodedNode *N = *I;
637 // If we are in an inlined call, generate CallExitBegin node.
638 if (N->getLocationContext()->getParent()) {
639 N = generateCallExitBeginNode(N, RS);
643 // TODO: We should run remove dead bindings here.
651 void NodeBuilder::anchor() { }
653 ExplodedNode* NodeBuilder::generateNodeImpl(const ProgramPoint &Loc,
654 ProgramStateRef State,
657 HasGeneratedNodes = true;
659 ExplodedNode *N = C.Eng.G.getNode(Loc, State, MarkAsSink, &IsNew);
660 N->addPredecessor(FromN, C.Eng.G);
661 Frontier.erase(FromN);
672 void NodeBuilderWithSinks::anchor() { }
674 StmtNodeBuilder::~StmtNodeBuilder() {
676 for (ExplodedNodeSet::iterator I = Frontier.begin(),
677 E = Frontier.end(); I != E; ++I )
678 EnclosingBldr->addNodes(*I);
681 void BranchNodeBuilder::anchor() { }
683 ExplodedNode *BranchNodeBuilder::generateNode(ProgramStateRef State,
685 ExplodedNode *NodePred) {
686 // If the branch has been marked infeasible we should not generate a node.
687 if (!isFeasible(branch))
690 ProgramPoint Loc = BlockEdge(C.Block, branch ? DstT:DstF,
691 NodePred->getLocationContext());
692 ExplodedNode *Succ = generateNodeImpl(Loc, State, NodePred);
697 IndirectGotoNodeBuilder::generateNode(const iterator &I,
702 Eng.G.getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()),
704 Succ->addPredecessor(Pred, Eng.G);
710 Eng.WList->enqueue(Succ);
717 SwitchNodeBuilder::generateCaseStmtNode(const iterator &I,
718 ProgramStateRef St) {
722 Eng.G.getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()),
724 Succ->addPredecessor(Pred, Eng.G);
728 Eng.WList->enqueue(Succ);
734 SwitchNodeBuilder::generateDefaultCaseNode(ProgramStateRef St,
736 // Get the block for the default case.
737 assert(Src->succ_rbegin() != Src->succ_rend());
738 CFGBlock *DefaultBlock = *Src->succ_rbegin();
740 // Sanity check for default blocks that are unreachable and not caught
741 // by earlier stages.
747 Eng.G.getNode(BlockEdge(Src, DefaultBlock, Pred->getLocationContext()),
749 Succ->addPredecessor(Pred, Eng.G);
755 Eng.WList->enqueue(Succ);