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