clang  10.0.0svn
CoreEngine.cpp
Go to the documentation of this file.
1 //===- CoreEngine.cpp - Path-Sensitive Dataflow Engine --------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines a generic engine for intraprocedural, path-sensitive,
10 // dataflow analysis via graph reachability engine.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "clang/AST/Expr.h"
16 #include "clang/AST/ExprCXX.h"
17 #include "clang/AST/Stmt.h"
18 #include "clang/AST/StmtCXX.h"
20 #include "clang/Analysis/CFG.h"
22 #include "clang/Basic/LLVM.h"
29 #include "llvm/ADT/Optional.h"
30 #include "llvm/ADT/STLExtras.h"
31 #include "llvm/ADT/Statistic.h"
32 #include "llvm/Support/Casting.h"
33 #include "llvm/Support/ErrorHandling.h"
34 #include <algorithm>
35 #include <cassert>
36 #include <memory>
37 #include <utility>
38 
39 using namespace clang;
40 using namespace ento;
41 
42 #define DEBUG_TYPE "CoreEngine"
43 
44 STATISTIC(NumSteps,
45  "The # of steps executed.");
46 STATISTIC(NumReachedMaxSteps,
47  "The # of times we reached the max number of steps.");
48 STATISTIC(NumPathsExplored,
49  "The # of paths explored by the analyzer.");
50 
51 //===----------------------------------------------------------------------===//
52 // Core analysis engine.
53 //===----------------------------------------------------------------------===//
54 
55 static std::unique_ptr<WorkList> generateWorkList(AnalyzerOptions &Opts,
56  SubEngine &subengine) {
57  switch (Opts.getExplorationStrategy()) {
59  return WorkList::makeDFS();
61  return WorkList::makeBFS();
70  }
71  llvm_unreachable("Unknown AnalyzerOptions::ExplorationStrategyKind");
72 }
73 
75  AnalyzerOptions &Opts)
76  : SubEng(subengine), WList(generateWorkList(Opts, subengine)),
77  BCounterFactory(G.getAllocator()), FunctionSummaries(FS) {}
78 
79 /// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps.
80 bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps,
81  ProgramStateRef InitState) {
82  if (G.num_roots() == 0) { // Initialize the analysis by constructing
83  // the root if none exists.
84 
85  const CFGBlock *Entry = &(L->getCFG()->getEntry());
86 
87  assert(Entry->empty() && "Entry block must be empty.");
88 
89  assert(Entry->succ_size() == 1 && "Entry block must have 1 successor.");
90 
91  // Mark the entry block as visited.
92  FunctionSummaries->markVisitedBasicBlock(Entry->getBlockID(),
93  L->getDecl(),
94  L->getCFG()->getNumBlockIDs());
95 
96  // Get the solitary successor.
97  const CFGBlock *Succ = *(Entry->succ_begin());
98 
99  // Construct an edge representing the
100  // starting location in the function.
101  BlockEdge StartLoc(Entry, Succ, L);
102 
103  // Set the current block counter to being empty.
104  WList->setBlockCounter(BCounterFactory.GetEmptyCounter());
105 
106  if (!InitState)
107  InitState = SubEng.getInitialState(L);
108 
109  bool IsNew;
110  ExplodedNode *Node = G.getNode(StartLoc, InitState, false, &IsNew);
111  assert(IsNew);
112  G.addRoot(Node);
113 
114  NodeBuilderContext BuilderCtx(*this, StartLoc.getDst(), Node);
115  ExplodedNodeSet DstBegin;
116  SubEng.processBeginOfFunction(BuilderCtx, Node, DstBegin, StartLoc);
117 
118  enqueue(DstBegin);
119  }
120 
121  // Check if we have a steps limit
122  bool UnlimitedSteps = Steps == 0;
123  // Cap our pre-reservation in the event that the user specifies
124  // a very large number of maximum steps.
125  const unsigned PreReservationCap = 4000000;
126  if(!UnlimitedSteps)
127  G.reserve(std::min(Steps,PreReservationCap));
128 
129  while (WList->hasWork()) {
130  if (!UnlimitedSteps) {
131  if (Steps == 0) {
132  NumReachedMaxSteps++;
133  break;
134  }
135  --Steps;
136  }
137 
138  NumSteps++;
139 
140  const WorkListUnit& WU = WList->dequeue();
141 
142  // Set the current block counter.
143  WList->setBlockCounter(WU.getBlockCounter());
144 
145  // Retrieve the node.
146  ExplodedNode *Node = WU.getNode();
147 
148  dispatchWorkItem(Node, Node->getLocation(), WU);
149  }
150  SubEng.processEndWorklist();
151  return WList->hasWork();
152 }
153 
155  const WorkListUnit& WU) {
156  // Dispatch on the location type.
157  switch (Loc.getKind()) {
159  HandleBlockEdge(Loc.castAs<BlockEdge>(), Pred);
160  break;
161 
163  HandleBlockEntrance(Loc.castAs<BlockEntrance>(), Pred);
164  break;
165 
167  assert(false && "BlockExit location never occur in forward analysis.");
168  break;
169 
171  HandleCallEnter(Loc.castAs<CallEnter>(), Pred);
172  break;
173 
175  SubEng.processCallExit(Pred);
176  break;
177 
179  assert(Pred->hasSinglePred() &&
180  "Assume epsilon has exactly one predecessor by construction");
181  ExplodedNode *PNode = Pred->getFirstPred();
182  dispatchWorkItem(Pred, PNode->getLocation(), WU);
183  break;
184  }
185  default:
186  assert(Loc.getAs<PostStmt>() ||
187  Loc.getAs<PostInitializer>() ||
188  Loc.getAs<PostImplicitCall>() ||
189  Loc.getAs<CallExitEnd>() ||
190  Loc.getAs<LoopExit>() ||
191  Loc.getAs<PostAllocatorCall>());
192  HandlePostStmt(WU.getBlock(), WU.getIndex(), Pred);
193  break;
194  }
195 }
196 
198  unsigned Steps,
199  ProgramStateRef InitState,
200  ExplodedNodeSet &Dst) {
201  bool DidNotFinish = ExecuteWorkList(L, Steps, InitState);
202  for (ExplodedGraph::eop_iterator I = G.eop_begin(), E = G.eop_end(); I != E;
203  ++I) {
204  Dst.Add(*I);
205  }
206  return DidNotFinish;
207 }
208 
209 void CoreEngine::HandleBlockEdge(const BlockEdge &L, ExplodedNode *Pred) {
210  const CFGBlock *Blk = L.getDst();
211  NodeBuilderContext BuilderCtx(*this, Blk, Pred);
212 
213  // Mark this block as visited.
214  const LocationContext *LC = Pred->getLocationContext();
215  FunctionSummaries->markVisitedBasicBlock(Blk->getBlockID(),
216  LC->getDecl(),
217  LC->getCFG()->getNumBlockIDs());
218 
219  // Display a prunable path note to the user if it's a virtual bases branch
220  // and we're taking the path that skips virtual base constructors.
222  L.getDst() == *L.getSrc()->succ_begin()) {
223  ProgramPoint P = L.withTag(getNoteTags().makeNoteTag(
224  [](BugReporterContext &, BugReport &) -> std::string {
225  // TODO: Just call out the name of the most derived class
226  // when we know it.
227  return "Virtual base initialization skipped because "
228  "it has already been handled by the most derived class";
229  }, /*IsPrunable=*/true));
230  // Perform the transition.
231  ExplodedNodeSet Dst;
232  NodeBuilder Bldr(Pred, Dst, BuilderCtx);
233  Pred = Bldr.generateNode(P, Pred->getState(), Pred);
234  if (!Pred)
235  return;
236  }
237 
238  // Check if we are entering the EXIT block.
239  if (Blk == &(L.getLocationContext()->getCFG()->getExit())) {
240  assert(L.getLocationContext()->getCFG()->getExit().empty() &&
241  "EXIT block cannot contain Stmts.");
242 
243  // Get return statement..
244  const ReturnStmt *RS = nullptr;
245  if (!L.getSrc()->empty()) {
246  CFGElement LastElement = L.getSrc()->back();
247  if (Optional<CFGStmt> LastStmt = LastElement.getAs<CFGStmt>()) {
248  RS = dyn_cast<ReturnStmt>(LastStmt->getStmt());
249  } else if (Optional<CFGAutomaticObjDtor> AutoDtor =
250  LastElement.getAs<CFGAutomaticObjDtor>()) {
251  RS = dyn_cast<ReturnStmt>(AutoDtor->getTriggerStmt());
252  }
253  }
254 
255  // Process the final state transition.
256  SubEng.processEndOfFunction(BuilderCtx, Pred, RS);
257 
258  // This path is done. Don't enqueue any more nodes.
259  return;
260  }
261 
262  // Call into the SubEngine to process entering the CFGBlock.
263  ExplodedNodeSet dstNodes;
264  BlockEntrance BE(Blk, Pred->getLocationContext());
265  NodeBuilderWithSinks nodeBuilder(Pred, dstNodes, BuilderCtx, BE);
266  SubEng.processCFGBlockEntrance(L, nodeBuilder, Pred);
267 
268  // Auto-generate a node.
269  if (!nodeBuilder.hasGeneratedNodes()) {
270  nodeBuilder.generateNode(Pred->State, Pred);
271  }
272 
273  // Enqueue nodes onto the worklist.
274  enqueue(dstNodes);
275 }
276 
277 void CoreEngine::HandleBlockEntrance(const BlockEntrance &L,
278  ExplodedNode *Pred) {
279  // Increment the block counter.
280  const LocationContext *LC = Pred->getLocationContext();
281  unsigned BlockId = L.getBlock()->getBlockID();
282  BlockCounter Counter = WList->getBlockCounter();
283  Counter = BCounterFactory.IncrementCount(Counter, LC->getStackFrame(),
284  BlockId);
285  WList->setBlockCounter(Counter);
286 
287  // Process the entrance of the block.
289  NodeBuilderContext Ctx(*this, L.getBlock(), Pred);
290  SubEng.processCFGElement(*E, Pred, 0, &Ctx);
291  }
292  else
293  HandleBlockExit(L.getBlock(), Pred);
294 }
295 
296 void CoreEngine::HandleBlockExit(const CFGBlock * B, ExplodedNode *Pred) {
297  if (const Stmt *Term = B->getTerminatorStmt()) {
298  switch (Term->getStmtClass()) {
299  default:
300  llvm_unreachable("Analysis for this terminator not implemented.");
301 
302  case Stmt::CXXBindTemporaryExprClass:
303  HandleCleanupTemporaryBranch(
304  cast<CXXBindTemporaryExpr>(Term), B, Pred);
305  return;
306 
307  // Model static initializers.
308  case Stmt::DeclStmtClass:
309  HandleStaticInit(cast<DeclStmt>(Term), B, Pred);
310  return;
311 
312  case Stmt::BinaryOperatorClass: // '&&' and '||'
313  HandleBranch(cast<BinaryOperator>(Term)->getLHS(), Term, B, Pred);
314  return;
315 
316  case Stmt::BinaryConditionalOperatorClass:
317  case Stmt::ConditionalOperatorClass:
318  HandleBranch(cast<AbstractConditionalOperator>(Term)->getCond(),
319  Term, B, Pred);
320  return;
321 
322  // FIXME: Use constant-folding in CFG construction to simplify this
323  // case.
324 
325  case Stmt::ChooseExprClass:
326  HandleBranch(cast<ChooseExpr>(Term)->getCond(), Term, B, Pred);
327  return;
328 
329  case Stmt::CXXTryStmtClass:
330  // Generate a node for each of the successors.
331  // Our logic for EH analysis can certainly be improved.
333  et = B->succ_end(); it != et; ++it) {
334  if (const CFGBlock *succ = *it) {
335  generateNode(BlockEdge(B, succ, Pred->getLocationContext()),
336  Pred->State, Pred);
337  }
338  }
339  return;
340 
341  case Stmt::DoStmtClass:
342  HandleBranch(cast<DoStmt>(Term)->getCond(), Term, B, Pred);
343  return;
344 
345  case Stmt::CXXForRangeStmtClass:
346  HandleBranch(cast<CXXForRangeStmt>(Term)->getCond(), Term, B, Pred);
347  return;
348 
349  case Stmt::ForStmtClass:
350  HandleBranch(cast<ForStmt>(Term)->getCond(), Term, B, Pred);
351  return;
352 
353  case Stmt::ContinueStmtClass:
354  case Stmt::BreakStmtClass:
355  case Stmt::GotoStmtClass:
356  break;
357 
358  case Stmt::IfStmtClass:
359  HandleBranch(cast<IfStmt>(Term)->getCond(), Term, B, Pred);
360  return;
361 
362  case Stmt::IndirectGotoStmtClass: {
363  // Only 1 successor: the indirect goto dispatch block.
364  assert(B->succ_size() == 1);
365 
367  builder(Pred, B, cast<IndirectGotoStmt>(Term)->getTarget(),
368  *(B->succ_begin()), this);
369 
370  SubEng.processIndirectGoto(builder);
371  return;
372  }
373 
374  case Stmt::ObjCForCollectionStmtClass:
375  // In the case of ObjCForCollectionStmt, it appears twice in a CFG:
376  //
377  // (1) inside a basic block, which represents the binding of the
378  // 'element' variable to a value.
379  // (2) in a terminator, which represents the branch.
380  //
381  // For (1), subengines will bind a value (i.e., 0 or 1) indicating
382  // whether or not collection contains any more elements. We cannot
383  // just test to see if the element is nil because a container can
384  // contain nil elements.
385  HandleBranch(Term, Term, B, Pred);
386  return;
387 
388  case Stmt::SwitchStmtClass: {
389  SwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(),
390  this);
391 
392  SubEng.processSwitch(builder);
393  return;
394  }
395 
396  case Stmt::WhileStmtClass:
397  HandleBranch(cast<WhileStmt>(Term)->getCond(), Term, B, Pred);
398  return;
399 
400  case Stmt::GCCAsmStmtClass:
401  assert(cast<GCCAsmStmt>(Term)->isAsmGoto() && "Encountered GCCAsmStmt without labels");
402  // TODO: Handle jumping to labels
403  return;
404  }
405  }
406 
407  if (B->getTerminator().isVirtualBaseBranch()) {
408  HandleVirtualBaseBranch(B, Pred);
409  return;
410  }
411 
412  assert(B->succ_size() == 1 &&
413  "Blocks with no terminator should have at most 1 successor.");
414 
415  generateNode(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()),
416  Pred->State, Pred);
417 }
418 
419 void CoreEngine::HandleCallEnter(const CallEnter &CE, ExplodedNode *Pred) {
420  NodeBuilderContext BuilderCtx(*this, CE.getEntry(), Pred);
421  SubEng.processCallEnter(BuilderCtx, CE, Pred);
422 }
423 
424 void CoreEngine::HandleBranch(const Stmt *Cond, const Stmt *Term,
425  const CFGBlock * B, ExplodedNode *Pred) {
426  assert(B->succ_size() == 2);
427  NodeBuilderContext Ctx(*this, B, Pred);
428  ExplodedNodeSet Dst;
429  SubEng.processBranch(Cond, Ctx, Pred, Dst, *(B->succ_begin()),
430  *(B->succ_begin() + 1));
431  // Enqueue the new frontier onto the worklist.
432  enqueue(Dst);
433 }
434 
435 void CoreEngine::HandleCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE,
436  const CFGBlock *B,
437  ExplodedNode *Pred) {
438  assert(B->succ_size() == 2);
439  NodeBuilderContext Ctx(*this, B, Pred);
440  ExplodedNodeSet Dst;
441  SubEng.processCleanupTemporaryBranch(BTE, Ctx, Pred, Dst, *(B->succ_begin()),
442  *(B->succ_begin() + 1));
443  // Enqueue the new frontier onto the worklist.
444  enqueue(Dst);
445 }
446 
447 void CoreEngine::HandleStaticInit(const DeclStmt *DS, const CFGBlock *B,
448  ExplodedNode *Pred) {
449  assert(B->succ_size() == 2);
450  NodeBuilderContext Ctx(*this, B, Pred);
451  ExplodedNodeSet Dst;
452  SubEng.processStaticInitializer(DS, Ctx, Pred, Dst,
453  *(B->succ_begin()), *(B->succ_begin()+1));
454  // Enqueue the new frontier onto the worklist.
455  enqueue(Dst);
456 }
457 
458 void CoreEngine::HandlePostStmt(const CFGBlock *B, unsigned StmtIdx,
459  ExplodedNode *Pred) {
460  assert(B);
461  assert(!B->empty());
462 
463  if (StmtIdx == B->size())
464  HandleBlockExit(B, Pred);
465  else {
466  NodeBuilderContext Ctx(*this, B, Pred);
467  SubEng.processCFGElement((*B)[StmtIdx], Pred, StmtIdx, &Ctx);
468  }
469 }
470 
471 void CoreEngine::HandleVirtualBaseBranch(const CFGBlock *B,
472  ExplodedNode *Pred) {
473  const LocationContext *LCtx = Pred->getLocationContext();
474  if (const auto *CallerCtor = dyn_cast_or_null<CXXConstructExpr>(
475  LCtx->getStackFrame()->getCallSite())) {
476  switch (CallerCtor->getConstructionKind()) {
479  BlockEdge Loc(B, *B->succ_begin(), LCtx);
480  HandleBlockEdge(Loc, Pred);
481  return;
482  }
483  default:
484  break;
485  }
486  }
487 
488  // We either don't see a parent stack frame because we're in the top frame,
489  // or the parent stack frame doesn't initialize our virtual bases.
490  BlockEdge Loc(B, *(B->succ_begin() + 1), LCtx);
491  HandleBlockEdge(Loc, Pred);
492 }
493 
494 /// generateNode - Utility method to generate nodes, hook up successors,
495 /// and add nodes to the worklist.
496 void CoreEngine::generateNode(const ProgramPoint &Loc,
498  ExplodedNode *Pred) {
499  bool IsNew;
500  ExplodedNode *Node = G.getNode(Loc, State, false, &IsNew);
501 
502  if (Pred)
503  Node->addPredecessor(Pred, G); // Link 'Node' with its predecessor.
504  else {
505  assert(IsNew);
506  G.addRoot(Node); // 'Node' has no predecessor. Make it a root.
507  }
508 
509  // Only add 'Node' to the worklist if it was freshly generated.
510  if (IsNew) WList->enqueue(Node);
511 }
512 
514  const CFGBlock *Block, unsigned Idx) {
515  assert(Block);
516  assert(!N->isSink());
517 
518  // Check if this node entered a callee.
519  if (N->getLocation().getAs<CallEnter>()) {
520  // Still use the index of the CallExpr. It's needed to create the callee
521  // StackFrameContext.
522  WList->enqueue(N, Block, Idx);
523  return;
524  }
525 
526  // Do not create extra nodes. Move to the next CFG element.
527  if (N->getLocation().getAs<PostInitializer>() ||
529  N->getLocation().getAs<LoopExit>()) {
530  WList->enqueue(N, Block, Idx+1);
531  return;
532  }
533 
534  if (N->getLocation().getAs<EpsilonPoint>()) {
535  WList->enqueue(N, Block, Idx);
536  return;
537  }
538 
539  if ((*Block)[Idx].getKind() == CFGElement::NewAllocator) {
540  WList->enqueue(N, Block, Idx+1);
541  return;
542  }
543 
544  // At this point, we know we're processing a normal statement.
545  CFGStmt CS = (*Block)[Idx].castAs<CFGStmt>();
546  PostStmt Loc(CS.getStmt(), N->getLocationContext());
547 
548  if (Loc == N->getLocation().withTag(nullptr)) {
549  // Note: 'N' should be a fresh node because otherwise it shouldn't be
550  // a member of Deferred.
551  WList->enqueue(N, Block, Idx+1);
552  return;
553  }
554 
555  bool IsNew;
556  ExplodedNode *Succ = G.getNode(Loc, N->getState(), false, &IsNew);
557  Succ->addPredecessor(N, G);
558 
559  if (IsNew)
560  WList->enqueue(Succ, Block, Idx+1);
561 }
562 
563 ExplodedNode *CoreEngine::generateCallExitBeginNode(ExplodedNode *N,
564  const ReturnStmt *RS) {
565  // Create a CallExitBegin node and enqueue it.
566  const auto *LocCtx = cast<StackFrameContext>(N->getLocationContext());
567 
568  // Use the callee location context.
569  CallExitBegin Loc(LocCtx, RS);
570 
571  bool isNew;
572  ExplodedNode *Node = G.getNode(Loc, N->getState(), false, &isNew);
573  Node->addPredecessor(N, G);
574  return isNew ? Node : nullptr;
575 }
576 
578  for (const auto I : Set)
579  WList->enqueue(I);
580 }
581 
583  const CFGBlock *Block, unsigned Idx) {
584  for (const auto I : Set)
585  enqueueStmtNode(I, Block, Idx);
586 }
587 
589  for (auto I : Set) {
590  // If we are in an inlined call, generate CallExitBegin node.
591  if (I->getLocationContext()->getParent()) {
592  I = generateCallExitBeginNode(I, RS);
593  if (I)
594  WList->enqueue(I);
595  } else {
596  // TODO: We should run remove dead bindings here.
597  G.addEndOfPath(I);
598  NumPathsExplored++;
599  }
600  }
601 }
602 
603 void NodeBuilder::anchor() {}
604 
606  ProgramStateRef State,
607  ExplodedNode *FromN,
608  bool MarkAsSink) {
609  HasGeneratedNodes = true;
610  bool IsNew;
611  ExplodedNode *N = C.Eng.G.getNode(Loc, State, MarkAsSink, &IsNew);
612  N->addPredecessor(FromN, C.Eng.G);
613  Frontier.erase(FromN);
614 
615  if (!IsNew)
616  return nullptr;
617 
618  if (!MarkAsSink)
619  Frontier.Add(N);
620 
621  return N;
622 }
623 
624 void NodeBuilderWithSinks::anchor() {}
625 
627  if (EnclosingBldr)
628  for (const auto I : Frontier)
629  EnclosingBldr->addNodes(I);
630 }
631 
632 void BranchNodeBuilder::anchor() {}
633 
635  bool branch,
636  ExplodedNode *NodePred) {
637  // If the branch has been marked infeasible we should not generate a node.
638  if (!isFeasible(branch))
639  return nullptr;
640 
641  ProgramPoint Loc = BlockEdge(C.Block, branch ? DstT:DstF,
642  NodePred->getLocationContext());
643  ExplodedNode *Succ = generateNodeImpl(Loc, State, NodePred);
644  return Succ;
645 }
646 
649  ProgramStateRef St,
650  bool IsSink) {
651  bool IsNew;
652  ExplodedNode *Succ =
653  Eng.G.getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()),
654  St, IsSink, &IsNew);
655  Succ->addPredecessor(Pred, Eng.G);
656 
657  if (!IsNew)
658  return nullptr;
659 
660  if (!IsSink)
661  Eng.WList->enqueue(Succ);
662 
663  return Succ;
664 }
665 
668  ProgramStateRef St) {
669  bool IsNew;
670  ExplodedNode *Succ =
671  Eng.G.getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()),
672  St, false, &IsNew);
673  Succ->addPredecessor(Pred, Eng.G);
674  if (!IsNew)
675  return nullptr;
676 
677  Eng.WList->enqueue(Succ);
678  return Succ;
679 }
680 
683  bool IsSink) {
684  // Get the block for the default case.
685  assert(Src->succ_rbegin() != Src->succ_rend());
686  CFGBlock *DefaultBlock = *Src->succ_rbegin();
687 
688  // Sanity check for default blocks that are unreachable and not caught
689  // by earlier stages.
690  if (!DefaultBlock)
691  return nullptr;
692 
693  bool IsNew;
694  ExplodedNode *Succ =
695  Eng.G.getNode(BlockEdge(Src, DefaultBlock, Pred->getLocationContext()),
696  St, IsSink, &IsNew);
697  Succ->addPredecessor(Pred, Eng.G);
698 
699  if (!IsNew)
700  return nullptr;
701 
702  if (!IsSink)
703  Eng.WList->enqueue(Succ);
704 
705  return Succ;
706 }
succ_reverse_iterator succ_rbegin()
Definition: CFG.h:961
bool empty() const
Definition: CFG.h:919
const Stmt * getStmt() const
Definition: CFG.h:138
succ_iterator succ_begin()
Definition: CFG.h:956
bool ExecuteWorkList(const LocationContext *L, unsigned Steps, ProgramStateRef InitState)
ExecuteWorkList - Run the worklist algorithm for a maximum number of steps.
Definition: CoreEngine.cpp:80
Stmt - This represents one statement.
Definition: Stmt.h:66
CFGBlock & getEntry()
Definition: CFG.h:1317
unsigned getBlockID() const
Definition: CFG.h:1075
const CFGBlock * getSrc() const
Definition: ProgramPoint.h:511
Represents a point when we begin processing an inlined call.
Definition: ProgramPoint.h:630
StringRef P
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
virtual ProgramStateRef getInitialState(const LocationContext *InitLoc)=0
NoteTag::Factory & getNoteTags()
Definition: CoreEngine.h:203
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:98
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:29
static std::unique_ptr< WorkList > makeUnexploredFirstPriorityQueue()
Definition: WorkList.cpp:251
virtual void processBranch(const Stmt *Condition, NodeBuilderContext &BuilderCtx, ExplodedNode *Pred, ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF)=0
Called by CoreEngine.
Optional< CFGElement > getFirstElement() const
Definition: ProgramPoint.h:237
Represents a point when we exit a loop.
Definition: ProgramPoint.h:713
unsigned succ_size() const
Definition: CFG.h:974
virtual void processCFGElement(const CFGElement E, ExplodedNode *Pred, unsigned StmtIdx, NodeBuilderContext *Ctx)=0
Called by CoreEngine.
void enqueue(ExplodedNodeSet &Set)
Enqueue the given set of nodes onto the work list.
Definition: CoreEngine.cpp:577
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:197
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:645
LineState State
static std::unique_ptr< WorkList > makeDFS()
Definition: WorkList.cpp:81
Represents C++ object destructor implicitly generated for automatic object or temporary bound to cons...
Definition: CFG.h:389
CoreEngine(SubEngine &subengine, FunctionSummariesTy *FS, AnalyzerOptions &Opts)
Construct a CoreEngine object to analyze the provided CFG.
Definition: CoreEngine.cpp:74
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:668
AdjacentBlocks::const_iterator const_succ_iterator
Definition: CFG.h:932
This is a meta program point, which should be skipped by all the diagnostic reasoning etc...
Definition: ProgramPoint.h:732
ExplodedNode * generateNodeImpl(const ProgramPoint &PP, ProgramStateRef State, ExplodedNode *Pred, bool MarkAsSink=false)
Definition: CoreEngine.cpp:605
virtual void processIndirectGoto(IndirectGotoNodeBuilder &builder)=0
Called by CoreEngine.
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified...
const LocationContext * getLocationContext() const
ExplodedNode * generateCaseStmtNode(const iterator &I, ProgramStateRef State)
Definition: CoreEngine.cpp:667
const CFGBlock * getBlock() const
Definition: CoreEngine.h:552
BlockCounter getBlockCounter() const
Returns the block counter map associated with the worklist unit.
Definition: WorkList.h:51
unsigned size() const
Definition: CFG.h:918
virtual void processCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE, NodeBuilderContext &BldCtx, ExplodedNode *Pred, ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF)=0
Called by CoreEngine.
Represents binding an expression to a temporary.
Definition: ExprCXX.h:1373
ExplodedNode * getFirstPred()
static std::unique_ptr< WorkList > makeBFS()
Definition: WorkList.cpp:85
const Stmt * getCallSite() const
Represents a single basic block in a source-level CFG.
Definition: CFG.h:576
Represents a point when we finish the call exit sequence (for inlined call).
Definition: ProgramPoint.h:688
const CFGBlock * getBlock() const
Definition: ProgramPoint.h:233
virtual void processSwitch(SwitchNodeBuilder &builder)=0
Called by CoreEngine.
unsigned getIndex() const
Return the index within the CFGBlock for the worklist unit.
Definition: WorkList.h:57
Kind getKind() const
Definition: ProgramPoint.h:160
This is the simplest builder which generates nodes in the ExplodedGraph.
Definition: CoreEngine.h:236
void Add(ExplodedNode *N)
unsigned num_roots() const
const CFGBlock * getDst() const
Definition: ProgramPoint.h:515
void enqueueStmtNode(ExplodedNode *N, const CFGBlock *Block, unsigned Idx)
Enqueue a single node created as a result of statement processing.
Definition: CoreEngine.cpp:513
virtual void processStaticInitializer(const DeclStmt *DS, NodeBuilderContext &BuilderCtx, ExplodedNode *Pred, ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF)=0
Called by CoreEngine.
ReturnStmt - This represents a return, optionally of an expression: return; return 4;...
Definition: Stmt.h:2620
ExplodedNode * getNode(const ProgramPoint &L, ProgramStateRef State, bool IsSink=false, bool *IsNew=nullptr)
Retrieve the node associated with a (Location,State) pair, where the &#39;Location&#39; is a ProgramPoint in ...
CFGElement back() const
Definition: CFG.h:874
ExplodedNode * getNode() const
Returns the node associated with the worklist unit.
Definition: WorkList.h:48
ExplodedNode * generateNode(const iterator &I, ProgramStateRef State, bool isSink=false)
Definition: CoreEngine.cpp:648
static std::unique_ptr< WorkList > makeUnexploredFirstPriorityLocationQueue()
Definition: WorkList.cpp:311
T castAs() const
Convert to the specified ProgramPoint type, asserting that this ProgramPoint is of the desired type...
Definition: ProgramPoint.h:140
DeclStmt - Adaptor class for mixing declarations with statements and expressions. ...
Definition: Stmt.h:1213
void dispatchWorkItem(ExplodedNode *Pred, ProgramPoint Loc, const WorkListUnit &WU)
Dispatch the work list item based on the given location information.
Definition: CoreEngine.cpp:154
ProgramPoint getLocation() const
getLocation - Returns the edge associated with the given node.
NodeVector::iterator eop_iterator
unsigned getNumBlockIDs() const
Returns the total number of BlockIDs allocated (which start at 0).
Definition: CFG.h:1393
static std::unique_ptr< WorkList > makeBFSBlockDFSContents()
Definition: WorkList.cpp:126
virtual void processCallExit(ExplodedNode *Pred)=0
succ_iterator succ_end()
Definition: CFG.h:957
Optional< T > getAs() const
Convert to the specified CFGElement type, returning None if this CFGElement is not of the desired typ...
Definition: CFG.h:109
ast_type_traits::DynTypedNode Node
ExplorationStrategyKind getExplorationStrategy() const
Dataflow Directional Tag Classes.
ExplodedNode * generateDefaultCaseNode(ProgramStateRef State, bool isSink=false)
Definition: CoreEngine.cpp:682
Represents a program point just after an implicit call event.
Definition: ProgramPoint.h:600
This node builder keeps track of the generated sink nodes.
Definition: CoreEngine.h:341
bool isVirtualBaseBranch() const
Definition: CFG.h:545
Stmt * getTerminatorStmt()
Definition: CFG.h:1051
virtual void processCallEnter(NodeBuilderContext &BC, CallEnter CE, ExplodedNode *Pred)=0
const CFGBlock * getBlock() const
Returns the CFGblock associated with the worklist unit.
Definition: WorkList.h:54
const Decl * getDecl() const
void reserve(unsigned NodeCount)
virtual void processEndWorklist()=0
Called by CoreEngine when the analysis worklist is either empty or the.
const LocationContext * getLocationContext() const
Definition: ProgramPoint.h:179
virtual void processBeginOfFunction(NodeBuilderContext &BC, ExplodedNode *Pred, ExplodedNodeSet &Dst, const BlockEdge &L)=0
Called by CoreEngine.
const StackFrameContext * getStackFrame() const
Stores options for the analyzer from the command line.
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:588
ExplodedNode * generateNode(const ProgramPoint &PP, ProgramStateRef State, ExplodedNode *Pred)
Generates a node in the ExplodedGraph.
Definition: CoreEngine.h:289
ExplodedNode * generateNode(ProgramStateRef State, bool branch, ExplodedNode *Pred)
Definition: CoreEngine.cpp:634
Represents a top-level expression in a basic block.
Definition: CFG.h:55
BlockCounter IncrementCount(BlockCounter BC, const StackFrameContext *CallSite, unsigned BlockID)
virtual void processEndOfFunction(NodeBuilderContext &BC, ExplodedNode *Pred, const ReturnStmt *RS=nullptr)=0
Called by CoreEngine.
__DEVICE__ int min(int __a, int __b)
ExplodedNode * addEndOfPath(ExplodedNode *V)
addEndOfPath - Add an untyped node to the set of EOP nodes.
static Decl::Kind getKind(const Decl *D)
Definition: DeclBase.cpp:945
static std::unique_ptr< WorkList > makeUnexploredFirst()
Definition: WorkList.cpp:188
virtual void processCFGBlockEntrance(const BlockEdge &L, NodeBuilderWithSinks &nodeBuilder, ExplodedNode *Pred)=0
Called by CoreEngine when it starts processing a CFGBlock.
Optional< T > getAs() const
Convert to the specified ProgramPoint type, returning None if this ProgramPoint is not of the desired...
Definition: ProgramPoint.h:151
This class provides an interface through which checkers can create individual bug reports...
Definition: BugReporter.h:119
CFGTerminator getTerminator() const
Definition: CFG.h:1049
ExplodedNode * addRoot(ExplodedNode *V)
addRoot - Add an untyped node to the set of roots.
void markVisitedBasicBlock(unsigned ID, const Decl *D, unsigned TotalIDs)
static std::unique_ptr< WorkList > generateWorkList(AnalyzerOptions &Opts, SubEngine &subengine)
Definition: CoreEngine.cpp:55
CFGBlock & getExit()
Definition: CFG.h:1319