clang  6.0.0svn
CoreEngine.cpp
Go to the documentation of this file.
1 //==- CoreEngine.cpp - 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 engine.
12 //
13 //===----------------------------------------------------------------------===//
14 
16 #include "clang/AST/Expr.h"
17 #include "clang/AST/ExprCXX.h"
18 #include "clang/AST/StmtCXX.h"
21 #include "llvm/ADT/Statistic.h"
22 #include "llvm/Support/Casting.h"
23 
24 using namespace clang;
25 using namespace ento;
26 
27 #define DEBUG_TYPE "CoreEngine"
28 
29 STATISTIC(NumSteps,
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.");
35 
36 //===----------------------------------------------------------------------===//
37 // Worklist classes for exploration of reachable states.
38 //===----------------------------------------------------------------------===//
39 
41 
42 namespace {
43 class DFS : public WorkList {
45 public:
46  bool hasWork() const override {
47  return !Stack.empty();
48  }
49 
50  void enqueue(const WorkListUnit& U) override {
51  Stack.push_back(U);
52  }
53 
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.
58  return U;
59  }
60 
61  bool visitItemsInWorkList(Visitor &V) override {
63  I = Stack.begin(), E = Stack.end(); I != E; ++I) {
64  if (V.visit(*I))
65  return true;
66  }
67  return false;
68  }
69 };
70 
71 class BFS : public WorkList {
72  std::deque<WorkListUnit> Queue;
73 public:
74  bool hasWork() const override {
75  return !Queue.empty();
76  }
77 
78  void enqueue(const WorkListUnit& U) override {
79  Queue.push_back(U);
80  }
81 
82  WorkListUnit dequeue() override {
83  WorkListUnit U = Queue.front();
84  Queue.pop_front();
85  return U;
86  }
87 
88  bool visitItemsInWorkList(Visitor &V) override {
89  for (std::deque<WorkListUnit>::iterator
90  I = Queue.begin(), E = Queue.end(); I != E; ++I) {
91  if (V.visit(*I))
92  return true;
93  }
94  return false;
95  }
96 };
97 
98 } // end anonymous namespace
99 
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.
103 
104 WorkList *WorkList::makeDFS() { return new DFS(); }
105 WorkList *WorkList::makeBFS() { return new BFS(); }
106 
107 namespace {
108  class BFSBlockDFSContents : public WorkList {
109  std::deque<WorkListUnit> Queue;
111  public:
112  bool hasWork() const override {
113  return !Queue.empty() || !Stack.empty();
114  }
115 
116  void enqueue(const WorkListUnit& U) override {
117  if (U.getNode()->getLocation().getAs<BlockEntrance>())
118  Queue.push_front(U);
119  else
120  Stack.push_back(U);
121  }
122 
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.
128  return U;
129  }
130 
131  assert(!Queue.empty());
132  // Don't use const reference. The subsequent pop_back() might make it
133  // unsafe.
134  WorkListUnit U = Queue.front();
135  Queue.pop_front();
136  return U;
137  }
138  bool visitItemsInWorkList(Visitor &V) override {
140  I = Stack.begin(), E = Stack.end(); I != E; ++I) {
141  if (V.visit(*I))
142  return true;
143  }
144  for (std::deque<WorkListUnit>::iterator
145  I = Queue.begin(), E = Queue.end(); I != E; ++I) {
146  if (V.visit(*I))
147  return true;
148  }
149  return false;
150  }
151 
152  };
153 } // end anonymous namespace
154 
156  return new BFSBlockDFSContents();
157 }
158 
159 //===----------------------------------------------------------------------===//
160 // Core analysis engine.
161 //===----------------------------------------------------------------------===//
162 
163 /// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps.
164 bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps,
165  ProgramStateRef InitState) {
166 
167  if (G.num_roots() == 0) { // Initialize the analysis by constructing
168  // the root if none exists.
169 
170  const CFGBlock *Entry = &(L->getCFG()->getEntry());
171 
172  assert (Entry->empty() &&
173  "Entry block must be empty.");
174 
175  assert (Entry->succ_size() == 1 &&
176  "Entry block must have 1 successor.");
177 
178  // Mark the entry block as visited.
179  FunctionSummaries->markVisitedBasicBlock(Entry->getBlockID(),
180  L->getDecl(),
181  L->getCFG()->getNumBlockIDs());
182 
183  // Get the solitary successor.
184  const CFGBlock *Succ = *(Entry->succ_begin());
185 
186  // Construct an edge representing the
187  // starting location in the function.
188  BlockEdge StartLoc(Entry, Succ, L);
189 
190  // Set the current block counter to being empty.
191  WList->setBlockCounter(BCounterFactory.GetEmptyCounter());
192 
193  if (!InitState)
194  InitState = SubEng.getInitialState(L);
195 
196  bool IsNew;
197  ExplodedNode *Node = G.getNode(StartLoc, InitState, false, &IsNew);
198  assert (IsNew);
199  G.addRoot(Node);
200 
201  NodeBuilderContext BuilderCtx(*this, StartLoc.getDst(), Node);
202  ExplodedNodeSet DstBegin;
203  SubEng.processBeginOfFunction(BuilderCtx, Node, DstBegin, StartLoc);
204 
205  enqueue(DstBegin);
206  }
207 
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;
213  if(!UnlimitedSteps)
214  G.reserve(std::min(Steps,PreReservationCap));
215 
216  while (WList->hasWork()) {
217  if (!UnlimitedSteps) {
218  if (Steps == 0) {
219  NumReachedMaxSteps++;
220  break;
221  }
222  --Steps;
223  }
224 
225  NumSteps++;
226 
227  const WorkListUnit& WU = WList->dequeue();
228 
229  // Set the current block counter.
230  WList->setBlockCounter(WU.getBlockCounter());
231 
232  // Retrieve the node.
233  ExplodedNode *Node = WU.getNode();
234 
235  dispatchWorkItem(Node, Node->getLocation(), WU);
236  }
237  SubEng.processEndWorklist(hasWorkRemaining());
238  return WList->hasWork();
239 }
240 
242  const WorkListUnit& WU) {
243  // Dispatch on the location type.
244  switch (Loc.getKind()) {
246  HandleBlockEdge(Loc.castAs<BlockEdge>(), Pred);
247  break;
248 
250  HandleBlockEntrance(Loc.castAs<BlockEntrance>(), Pred);
251  break;
252 
254  assert (false && "BlockExit location never occur in forward analysis.");
255  break;
256 
258  HandleCallEnter(Loc.castAs<CallEnter>(), Pred);
259  break;
260  }
261 
263  SubEng.processCallExit(Pred);
264  break;
265 
267  assert(Pred->hasSinglePred() &&
268  "Assume epsilon has exactly one predecessor by construction");
269  ExplodedNode *PNode = Pred->getFirstPred();
270  dispatchWorkItem(Pred, PNode->getLocation(), WU);
271  break;
272  }
273  default:
274  assert(Loc.getAs<PostStmt>() ||
275  Loc.getAs<PostInitializer>() ||
276  Loc.getAs<PostImplicitCall>() ||
277  Loc.getAs<CallExitEnd>() ||
278  Loc.getAs<LoopExit>());
279  HandlePostStmt(WU.getBlock(), WU.getIndex(), Pred);
280  break;
281  }
282 }
283 
285  unsigned Steps,
286  ProgramStateRef InitState,
287  ExplodedNodeSet &Dst) {
288  bool DidNotFinish = ExecuteWorkList(L, Steps, InitState);
289  for (ExplodedGraph::eop_iterator I = G.eop_begin(), E = G.eop_end(); I != E;
290  ++I) {
291  Dst.Add(*I);
292  }
293  return DidNotFinish;
294 }
295 
296 void CoreEngine::HandleBlockEdge(const BlockEdge &L, ExplodedNode *Pred) {
297 
298  const CFGBlock *Blk = L.getDst();
299  NodeBuilderContext BuilderCtx(*this, Blk, Pred);
300 
301  // Mark this block as visited.
302  const LocationContext *LC = Pred->getLocationContext();
303  FunctionSummaries->markVisitedBasicBlock(Blk->getBlockID(),
304  LC->getDecl(),
305  LC->getCFG()->getNumBlockIDs());
306 
307  // Check if we are entering the EXIT block.
308  if (Blk == &(L.getLocationContext()->getCFG()->getExit())) {
309 
310  assert (L.getLocationContext()->getCFG()->getExit().size() == 0
311  && "EXIT block cannot contain Stmts.");
312 
313  // Get return statement..
314  const ReturnStmt *RS = nullptr;
315  if (!L.getSrc()->empty()) {
316  if (Optional<CFGStmt> LastStmt = L.getSrc()->back().getAs<CFGStmt>()) {
317  if ((RS = dyn_cast<ReturnStmt>(LastStmt->getStmt()))) {
318  if (!RS->getRetValue())
319  RS = nullptr;
320  }
321  }
322  }
323 
324  // Process the final state transition.
325  SubEng.processEndOfFunction(BuilderCtx, Pred, RS);
326 
327  // This path is done. Don't enqueue any more nodes.
328  return;
329  }
330 
331  // Call into the SubEngine to process entering the CFGBlock.
332  ExplodedNodeSet dstNodes;
333  BlockEntrance BE(Blk, Pred->getLocationContext());
334  NodeBuilderWithSinks nodeBuilder(Pred, dstNodes, BuilderCtx, BE);
335  SubEng.processCFGBlockEntrance(L, nodeBuilder, Pred);
336 
337  // Auto-generate a node.
338  if (!nodeBuilder.hasGeneratedNodes()) {
339  nodeBuilder.generateNode(Pred->State, Pred);
340  }
341 
342  // Enqueue nodes onto the worklist.
343  enqueue(dstNodes);
344 }
345 
346 void CoreEngine::HandleBlockEntrance(const BlockEntrance &L,
347  ExplodedNode *Pred) {
348 
349  // Increment the block counter.
350  const LocationContext *LC = Pred->getLocationContext();
351  unsigned BlockId = L.getBlock()->getBlockID();
352  BlockCounter Counter = WList->getBlockCounter();
353  Counter = BCounterFactory.IncrementCount(Counter, LC->getCurrentStackFrame(),
354  BlockId);
355  WList->setBlockCounter(Counter);
356 
357  // Process the entrance of the block.
359  NodeBuilderContext Ctx(*this, L.getBlock(), Pred);
360  SubEng.processCFGElement(*E, Pred, 0, &Ctx);
361  }
362  else
363  HandleBlockExit(L.getBlock(), Pred);
364 }
365 
366 void CoreEngine::HandleBlockExit(const CFGBlock * B, ExplodedNode *Pred) {
367 
368  if (const Stmt *Term = B->getTerminator()) {
369  switch (Term->getStmtClass()) {
370  default:
371  llvm_unreachable("Analysis for this terminator not implemented.");
372 
373  case Stmt::CXXBindTemporaryExprClass:
374  HandleCleanupTemporaryBranch(
375  cast<CXXBindTemporaryExpr>(B->getTerminator().getStmt()), B, Pred);
376  return;
377 
378  // Model static initializers.
379  case Stmt::DeclStmtClass:
380  HandleStaticInit(cast<DeclStmt>(Term), B, Pred);
381  return;
382 
383  case Stmt::BinaryOperatorClass: // '&&' and '||'
384  HandleBranch(cast<BinaryOperator>(Term)->getLHS(), Term, B, Pred);
385  return;
386 
387  case Stmt::BinaryConditionalOperatorClass:
388  case Stmt::ConditionalOperatorClass:
389  HandleBranch(cast<AbstractConditionalOperator>(Term)->getCond(),
390  Term, B, Pred);
391  return;
392 
393  // FIXME: Use constant-folding in CFG construction to simplify this
394  // case.
395 
396  case Stmt::ChooseExprClass:
397  HandleBranch(cast<ChooseExpr>(Term)->getCond(), Term, B, Pred);
398  return;
399 
400  case Stmt::CXXTryStmtClass: {
401  // Generate a node for each of the successors.
402  // Our logic for EH analysis can certainly be improved.
404  et = B->succ_end(); it != et; ++it) {
405  if (const CFGBlock *succ = *it) {
406  generateNode(BlockEdge(B, succ, Pred->getLocationContext()),
407  Pred->State, Pred);
408  }
409  }
410  return;
411  }
412 
413  case Stmt::DoStmtClass:
414  HandleBranch(cast<DoStmt>(Term)->getCond(), Term, B, Pred);
415  return;
416 
417  case Stmt::CXXForRangeStmtClass:
418  HandleBranch(cast<CXXForRangeStmt>(Term)->getCond(), Term, B, Pred);
419  return;
420 
421  case Stmt::ForStmtClass:
422  HandleBranch(cast<ForStmt>(Term)->getCond(), Term, B, Pred);
423  return;
424 
425  case Stmt::ContinueStmtClass:
426  case Stmt::BreakStmtClass:
427  case Stmt::GotoStmtClass:
428  break;
429 
430  case Stmt::IfStmtClass:
431  HandleBranch(cast<IfStmt>(Term)->getCond(), Term, B, Pred);
432  return;
433 
434  case Stmt::IndirectGotoStmtClass: {
435  // Only 1 successor: the indirect goto dispatch block.
436  assert (B->succ_size() == 1);
437 
439  builder(Pred, B, cast<IndirectGotoStmt>(Term)->getTarget(),
440  *(B->succ_begin()), this);
441 
442  SubEng.processIndirectGoto(builder);
443  return;
444  }
445 
446  case Stmt::ObjCForCollectionStmtClass: {
447  // In the case of ObjCForCollectionStmt, it appears twice in a CFG:
448  //
449  // (1) inside a basic block, which represents the binding of the
450  // 'element' variable to a value.
451  // (2) in a terminator, which represents the branch.
452  //
453  // For (1), subengines will bind a value (i.e., 0 or 1) indicating
454  // whether or not collection contains any more elements. We cannot
455  // just test to see if the element is nil because a container can
456  // contain nil elements.
457  HandleBranch(Term, Term, B, Pred);
458  return;
459  }
460 
461  case Stmt::SwitchStmtClass: {
462  SwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(),
463  this);
464 
465  SubEng.processSwitch(builder);
466  return;
467  }
468 
469  case Stmt::WhileStmtClass:
470  HandleBranch(cast<WhileStmt>(Term)->getCond(), Term, B, Pred);
471  return;
472  }
473  }
474 
475  assert (B->succ_size() == 1 &&
476  "Blocks with no terminator should have at most 1 successor.");
477 
478  generateNode(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()),
479  Pred->State, Pred);
480 }
481 
482 void CoreEngine::HandleCallEnter(const CallEnter &CE, ExplodedNode *Pred) {
483  NodeBuilderContext BuilderCtx(*this, CE.getEntry(), Pred);
484  SubEng.processCallEnter(BuilderCtx, CE, Pred);
485 }
486 
487 void CoreEngine::HandleBranch(const Stmt *Cond, const Stmt *Term,
488  const CFGBlock * B, ExplodedNode *Pred) {
489  assert(B->succ_size() == 2);
490  NodeBuilderContext Ctx(*this, B, Pred);
491  ExplodedNodeSet Dst;
492  SubEng.processBranch(Cond, Term, Ctx, Pred, Dst,
493  *(B->succ_begin()), *(B->succ_begin()+1));
494  // Enqueue the new frontier onto the worklist.
495  enqueue(Dst);
496 }
497 
498 void CoreEngine::HandleCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE,
499  const CFGBlock *B,
500  ExplodedNode *Pred) {
501  assert(B->succ_size() == 2);
502  NodeBuilderContext Ctx(*this, B, Pred);
503  ExplodedNodeSet Dst;
504  SubEng.processCleanupTemporaryBranch(BTE, Ctx, Pred, Dst, *(B->succ_begin()),
505  *(B->succ_begin() + 1));
506  // Enqueue the new frontier onto the worklist.
507  enqueue(Dst);
508 }
509 
510 void CoreEngine::HandleStaticInit(const DeclStmt *DS, const CFGBlock *B,
511  ExplodedNode *Pred) {
512  assert(B->succ_size() == 2);
513  NodeBuilderContext Ctx(*this, B, Pred);
514  ExplodedNodeSet Dst;
515  SubEng.processStaticInitializer(DS, Ctx, Pred, Dst,
516  *(B->succ_begin()), *(B->succ_begin()+1));
517  // Enqueue the new frontier onto the worklist.
518  enqueue(Dst);
519 }
520 
521 
522 void CoreEngine::HandlePostStmt(const CFGBlock *B, unsigned StmtIdx,
523  ExplodedNode *Pred) {
524  assert(B);
525  assert(!B->empty());
526 
527  if (StmtIdx == B->size())
528  HandleBlockExit(B, Pred);
529  else {
530  NodeBuilderContext Ctx(*this, B, Pred);
531  SubEng.processCFGElement((*B)[StmtIdx], Pred, StmtIdx, &Ctx);
532  }
533 }
534 
535 /// generateNode - Utility method to generate nodes, hook up successors,
536 /// and add nodes to the worklist.
537 void CoreEngine::generateNode(const ProgramPoint &Loc,
539  ExplodedNode *Pred) {
540 
541  bool IsNew;
542  ExplodedNode *Node = G.getNode(Loc, State, false, &IsNew);
543 
544  if (Pred)
545  Node->addPredecessor(Pred, G); // Link 'Node' with its predecessor.
546  else {
547  assert (IsNew);
548  G.addRoot(Node); // 'Node' has no predecessor. Make it a root.
549  }
550 
551  // Only add 'Node' to the worklist if it was freshly generated.
552  if (IsNew) WList->enqueue(Node);
553 }
554 
556  const CFGBlock *Block, unsigned Idx) {
557  assert(Block);
558  assert (!N->isSink());
559 
560  // Check if this node entered a callee.
561  if (N->getLocation().getAs<CallEnter>()) {
562  // Still use the index of the CallExpr. It's needed to create the callee
563  // StackFrameContext.
564  WList->enqueue(N, Block, Idx);
565  return;
566  }
567 
568  // Do not create extra nodes. Move to the next CFG element.
569  if (N->getLocation().getAs<PostInitializer>() ||
571  N->getLocation().getAs<LoopExit>()) {
572  WList->enqueue(N, Block, Idx+1);
573  return;
574  }
575 
576  if (N->getLocation().getAs<EpsilonPoint>()) {
577  WList->enqueue(N, Block, Idx);
578  return;
579  }
580 
581  if ((*Block)[Idx].getKind() == CFGElement::NewAllocator) {
582  WList->enqueue(N, Block, Idx+1);
583  return;
584  }
585 
586  // At this point, we know we're processing a normal statement.
587  CFGStmt CS = (*Block)[Idx].castAs<CFGStmt>();
588  PostStmt Loc(CS.getStmt(), N->getLocationContext());
589 
590  if (Loc == N->getLocation().withTag(nullptr)) {
591  // Note: 'N' should be a fresh node because otherwise it shouldn't be
592  // a member of Deferred.
593  WList->enqueue(N, Block, Idx+1);
594  return;
595  }
596 
597  bool IsNew;
598  ExplodedNode *Succ = G.getNode(Loc, N->getState(), false, &IsNew);
599  Succ->addPredecessor(N, G);
600 
601  if (IsNew)
602  WList->enqueue(Succ, Block, Idx+1);
603 }
604 
605 ExplodedNode *CoreEngine::generateCallExitBeginNode(ExplodedNode *N,
606  const ReturnStmt *RS) {
607  // Create a CallExitBegin node and enqueue it.
608  const StackFrameContext *LocCtx
609  = cast<StackFrameContext>(N->getLocationContext());
610 
611  // Use the callee location context.
612  CallExitBegin Loc(LocCtx, RS);
613 
614  bool isNew;
615  ExplodedNode *Node = G.getNode(Loc, N->getState(), false, &isNew);
616  Node->addPredecessor(N, G);
617  return isNew ? Node : nullptr;
618 }
619 
620 
622  for (ExplodedNodeSet::iterator I = Set.begin(),
623  E = Set.end(); I != E; ++I) {
624  WList->enqueue(*I);
625  }
626 }
627 
629  const CFGBlock *Block, unsigned Idx) {
630  for (ExplodedNodeSet::iterator I = Set.begin(),
631  E = Set.end(); I != E; ++I) {
632  enqueueStmtNode(*I, Block, Idx);
633  }
634 }
635 
637  for (ExplodedNodeSet::iterator I = Set.begin(), E = Set.end(); I != E; ++I) {
638  ExplodedNode *N = *I;
639  // If we are in an inlined call, generate CallExitBegin node.
640  if (N->getLocationContext()->getParent()) {
641  N = generateCallExitBeginNode(N, RS);
642  if (N)
643  WList->enqueue(N);
644  } else {
645  // TODO: We should run remove dead bindings here.
646  G.addEndOfPath(N);
647  NumPathsExplored++;
648  }
649  }
650 }
651 
652 
653 void NodeBuilder::anchor() { }
654 
656  ProgramStateRef State,
657  ExplodedNode *FromN,
658  bool MarkAsSink) {
659  HasGeneratedNodes = true;
660  bool IsNew;
661  ExplodedNode *N = C.Eng.G.getNode(Loc, State, MarkAsSink, &IsNew);
662  N->addPredecessor(FromN, C.Eng.G);
663  Frontier.erase(FromN);
664 
665  if (!IsNew)
666  return nullptr;
667 
668  if (!MarkAsSink)
669  Frontier.Add(N);
670 
671  return N;
672 }
673 
674 void NodeBuilderWithSinks::anchor() { }
675 
677  if (EnclosingBldr)
678  for (ExplodedNodeSet::iterator I = Frontier.begin(),
679  E = Frontier.end(); I != E; ++I )
680  EnclosingBldr->addNodes(*I);
681 }
682 
683 void BranchNodeBuilder::anchor() { }
684 
686  bool branch,
687  ExplodedNode *NodePred) {
688  // If the branch has been marked infeasible we should not generate a node.
689  if (!isFeasible(branch))
690  return nullptr;
691 
692  ProgramPoint Loc = BlockEdge(C.Block, branch ? DstT:DstF,
693  NodePred->getLocationContext());
694  ExplodedNode *Succ = generateNodeImpl(Loc, State, NodePred);
695  return Succ;
696 }
697 
700  ProgramStateRef St,
701  bool IsSink) {
702  bool IsNew;
703  ExplodedNode *Succ =
704  Eng.G.getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()),
705  St, IsSink, &IsNew);
706  Succ->addPredecessor(Pred, Eng.G);
707 
708  if (!IsNew)
709  return nullptr;
710 
711  if (!IsSink)
712  Eng.WList->enqueue(Succ);
713 
714  return Succ;
715 }
716 
717 
720  ProgramStateRef St) {
721 
722  bool IsNew;
723  ExplodedNode *Succ =
724  Eng.G.getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()),
725  St, false, &IsNew);
726  Succ->addPredecessor(Pred, Eng.G);
727  if (!IsNew)
728  return nullptr;
729 
730  Eng.WList->enqueue(Succ);
731  return Succ;
732 }
733 
734 
737  bool IsSink) {
738  // Get the block for the default case.
739  assert(Src->succ_rbegin() != Src->succ_rend());
740  CFGBlock *DefaultBlock = *Src->succ_rbegin();
741 
742  // Sanity check for default blocks that are unreachable and not caught
743  // by earlier stages.
744  if (!DefaultBlock)
745  return nullptr;
746 
747  bool IsNew;
748  ExplodedNode *Succ =
749  Eng.G.getNode(BlockEdge(Src, DefaultBlock, Pred->getLocationContext()),
750  St, IsSink, &IsNew);
751  Succ->addPredecessor(Pred, Eng.G);
752 
753  if (!IsNew)
754  return nullptr;
755 
756  if (!IsSink)
757  Eng.WList->enqueue(Succ);
758 
759  return Succ;
760 }
succ_reverse_iterator succ_rbegin()
Definition: CFG.h:629
bool empty() const
Definition: CFG.h:587
const Stmt * getStmt() const
Definition: CFG.h:122
succ_iterator succ_begin()
Definition: CFG.h:624
bool ExecuteWorkList(const LocationContext *L, unsigned Steps, ProgramStateRef InitState)
ExecuteWorkList - Run the worklist algorithm for a maximum number of steps.
Definition: CoreEngine.cpp:164
Stmt - This represents one statement.
Definition: Stmt.h:66
CFGBlock & getEntry()
Definition: CFG.h:921
unsigned getBlockID() const
Definition: CFG.h:729
const CFGBlock * getSrc() const
Definition: ProgramPoint.h:480
Represents a point when we begin processing an inlined call.
Definition: ProgramPoint.h:585
ProgramPoint withTag(const ProgramPointTag *tag) const
Create a new ProgramPoint object that is the same as the original except for using the specified tag ...
Definition: ProgramPoint.h:132
STATISTIC(NumSteps, "The # of steps executed.")
T castAs() const
Convert to the specified CFGElement type, asserting that this CFGElement is of the desired type...
Definition: CFG.h:90
const ProgramStateRef & getState() const
An abstract data type used to count the number of times a given block has been visited along a path a...
Definition: BlockCounter.h:30
Optional< CFGElement > getFirstElement() const
Definition: ProgramPoint.h:229
Represents a point when we exit a loop.
Definition: ProgramPoint.h:664
unsigned succ_size() const
Definition: CFG.h:642
void enqueue(ExplodedNodeSet &Set)
Enqueue the given set of nodes onto the work list.
Definition: CoreEngine.cpp:621
bool ExecuteWorkListWithInitialState(const LocationContext *L, unsigned Steps, ProgramStateRef InitState, ExplodedNodeSet &Dst)
Returns true if there is still simulation state on the worklist.
Definition: CoreEngine.cpp:284
Defines the clang::Expr interface and subclasses for C++ expressions.
const CFGBlock * getEntry() const
Returns the entry block in the CFG for the entered function.
Definition: ProgramPoint.h:600
LineState State
void addPredecessor(ExplodedNode *V, ExplodedGraph &G)
addPredeccessor - Adds a predecessor to the current node, and in tandem add this node as a successor ...
Represents a point when we start the call exit sequence (for inlined call).
Definition: ProgramPoint.h:623
AdjacentBlocks::const_iterator const_succ_iterator
Definition: CFG.h:600
This is a meta program point, which should be skipped by all the diagnostic reasoning etc...
Definition: ProgramPoint.h:683
ExplodedNode * generateNodeImpl(const ProgramPoint &PP, ProgramStateRef State, ExplodedNode *Pred, bool MarkAsSink=false)
Definition: CoreEngine.cpp:655
const StackFrameContext * getCurrentStackFrame() const
const LocationContext * getLocationContext() const
ExplodedNode * generateCaseStmtNode(const iterator &I, ProgramStateRef State)
Definition: CoreEngine.cpp:719
const CFGBlock * getBlock() const
Definition: CoreEngine.h:521
const LocationContext * getParent() const
BlockCounter getBlockCounter() const
Returns the block counter map associated with the worklist unit.
Definition: WorkList.h:52
unsigned size() const
Definition: CFG.h:586
Represents binding an expression to a temporary.
Definition: ExprCXX.h:1196
ExplodedNode * getFirstPred()
CFGBlock - Represents a single basic block in a source-level CFG.
Definition: CFG.h:422
Represents a point when we finish the call exit sequence (for inlined call).
Definition: ProgramPoint.h:639
const CFGBlock * getBlock() const
Definition: ProgramPoint.h:225
unsigned getIndex() const
Return the index within the CFGBlock for the worklist unit.
Definition: WorkList.h:58
Kind getKind() const
Definition: ProgramPoint.h:160
void Add(ExplodedNode *N)
char __ovld __cnfn min(char x, char y)
Returns y if y < x, otherwise it returns x.
const CFGBlock * getDst() const
Definition: ProgramPoint.h:484
void enqueueStmtNode(ExplodedNode *N, const CFGBlock *Block, unsigned Idx)
Enqueue a single node created as a result of statement processing.
Definition: CoreEngine.cpp:555
ReturnStmt - This represents a return, optionally of an expression: return; return 4;...
Definition: Stmt.h:1413
CFGElement back() const
Definition: CFG.h:574
ExplodedNode * getNode() const
Returns the node associated with the worklist unit.
Definition: WorkList.h:49
ExplodedNode * generateNode(const iterator &I, ProgramStateRef State, bool isSink=false)
Definition: CoreEngine.cpp:699
CFGTerminator getTerminator()
Definition: CFG.h:713
T castAs() const
Convert to the specified ProgramPoint type, asserting that this ProgramPoint is of the desired type...
Definition: ProgramPoint.h:140
virtual bool hasWork() const =0
DeclStmt - Adaptor class for mixing declarations with statements and expressions. ...
Definition: Stmt.h:487
void dispatchWorkItem(ExplodedNode *Pred, ProgramPoint Loc, const WorkListUnit &WU)
Dispatch the work list item based on the given location information.
Definition: CoreEngine.cpp:241
ProgramPoint getLocation() const
getLocation - Returns the edge associated with the given node.
unsigned getNumBlockIDs() const
getNumBlockIDs - Returns the total number of BlockIDs allocated (which start at 0).
Definition: CFG.h:998
virtual WorkListUnit dequeue()=0
succ_iterator succ_end()
Definition: CFG.h:625
static WorkList * makeDFS()
Definition: CoreEngine.cpp:104
Optional< T > getAs() const
Convert to the specified CFGElement type, returning None if this CFGElement is not of the desired typ...
Definition: CFG.h:101
ast_type_traits::DynTypedNode Node
Dataflow Directional Tag Classes.
ExplodedNode * generateDefaultCaseNode(ProgramStateRef State, bool isSink=false)
Definition: CoreEngine.cpp:736
Represents a program point just after an implicit call event.
Definition: ProgramPoint.h:569
virtual bool visitItemsInWorkList(Visitor &V)=0
This node builder keeps track of the generated sink nodes.
Definition: CoreEngine.h:313
static WorkList * makeBFSBlockDFSContents()
Definition: CoreEngine.cpp:155
const CFGBlock * getBlock() const
Returns the CFGblock associated with the worklist unit.
Definition: WorkList.h:55
const Decl * getDecl() const
Stmt * getStmt()
Definition: CFG.h:380
const LocationContext * getLocationContext() const
Definition: ProgramPoint.h:179
NodeVector::iterator eop_iterator
virtual bool visit(const WorkListUnit &U)=0
void enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS)
enqueue the nodes corresponding to the end of function onto the end of path / work list...
Definition: CoreEngine.cpp:636
ExplodedNode * generateNode(ProgramStateRef State, bool branch, ExplodedNode *Pred)
Definition: CoreEngine.cpp:685
static Decl::Kind getKind(const Decl *D)
Definition: DeclBase.cpp:915
virtual void enqueue(const WorkListUnit &U)=0
Optional< T > getAs() const
Convert to the specified ProgramPoint type, returning None if this ProgramPoint is not of the desired...
Definition: ProgramPoint.h:151
static WorkList * makeBFS()
Definition: CoreEngine.cpp:105
CFGBlock & getExit()
Definition: CFG.h:923