clang  14.0.0git
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  switch (Opts.getExplorationStrategy()) {
58  return WorkList::makeDFS();
60  return WorkList::makeBFS();
69  }
70  llvm_unreachable("Unknown AnalyzerOptions::ExplorationStrategyKind");
71 }
72 
74  AnalyzerOptions &Opts)
75  : ExprEng(exprengine), WList(generateWorkList(Opts)),
76  BCounterFactory(G.getAllocator()), FunctionSummaries(FS) {}
77 
78 /// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps.
79 bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps,
80  ProgramStateRef InitState) {
81  if (G.num_roots() == 0) { // Initialize the analysis by constructing
82  // the root if none exists.
83 
84  const CFGBlock *Entry = &(L->getCFG()->getEntry());
85 
86  assert(Entry->empty() && "Entry block must be empty.");
87 
88  assert(Entry->succ_size() == 1 && "Entry block must have 1 successor.");
89 
90  // Mark the entry block as visited.
91  FunctionSummaries->markVisitedBasicBlock(Entry->getBlockID(),
92  L->getDecl(),
93  L->getCFG()->getNumBlockIDs());
94 
95  // Get the solitary successor.
96  const CFGBlock *Succ = *(Entry->succ_begin());
97 
98  // Construct an edge representing the
99  // starting location in the function.
100  BlockEdge StartLoc(Entry, Succ, L);
101 
102  // Set the current block counter to being empty.
103  WList->setBlockCounter(BCounterFactory.GetEmptyCounter());
104 
105  if (!InitState)
106  InitState = ExprEng.getInitialState(L);
107 
108  bool IsNew;
109  ExplodedNode *Node = G.getNode(StartLoc, InitState, false, &IsNew);
110  assert(IsNew);
111  G.addRoot(Node);
112 
113  NodeBuilderContext BuilderCtx(*this, StartLoc.getDst(), Node);
114  ExplodedNodeSet DstBegin;
115  ExprEng.processBeginOfFunction(BuilderCtx, Node, DstBegin, StartLoc);
116 
117  enqueue(DstBegin);
118  }
119 
120  // Check if we have a steps limit
121  bool UnlimitedSteps = Steps == 0;
122  // Cap our pre-reservation in the event that the user specifies
123  // a very large number of maximum steps.
124  const unsigned PreReservationCap = 4000000;
125  if(!UnlimitedSteps)
126  G.reserve(std::min(Steps,PreReservationCap));
127 
128  while (WList->hasWork()) {
129  if (!UnlimitedSteps) {
130  if (Steps == 0) {
131  NumReachedMaxSteps++;
132  break;
133  }
134  --Steps;
135  }
136 
137  NumSteps++;
138 
139  const WorkListUnit& WU = WList->dequeue();
140 
141  // Set the current block counter.
142  WList->setBlockCounter(WU.getBlockCounter());
143 
144  // Retrieve the node.
145  ExplodedNode *Node = WU.getNode();
146 
147  dispatchWorkItem(Node, Node->getLocation(), WU);
148  }
149  ExprEng.processEndWorklist();
150  return WList->hasWork();
151 }
152 
154  const WorkListUnit& WU) {
155  // Dispatch on the location type.
156  switch (Loc.getKind()) {
158  HandleBlockEdge(Loc.castAs<BlockEdge>(), Pred);
159  break;
160 
162  HandleBlockEntrance(Loc.castAs<BlockEntrance>(), Pred);
163  break;
164 
166  assert(false && "BlockExit location never occur in forward analysis.");
167  break;
168 
170  HandleCallEnter(Loc.castAs<CallEnter>(), Pred);
171  break;
172 
174  ExprEng.processCallExit(Pred);
175  break;
176 
178  assert(Pred->hasSinglePred() &&
179  "Assume epsilon has exactly one predecessor by construction");
180  ExplodedNode *PNode = Pred->getFirstPred();
181  dispatchWorkItem(Pred, PNode->getLocation(), WU);
182  break;
183  }
184  default:
185  assert(Loc.getAs<PostStmt>() ||
188  Loc.getAs<CallExitEnd>() ||
189  Loc.getAs<LoopExit>() ||
191  HandlePostStmt(WU.getBlock(), WU.getIndex(), Pred);
192  break;
193  }
194 }
195 
197  unsigned Steps,
198  ProgramStateRef InitState,
199  ExplodedNodeSet &Dst) {
200  bool DidNotFinish = ExecuteWorkList(L, Steps, InitState);
201  for (ExplodedGraph::eop_iterator I = G.eop_begin(), E = G.eop_end(); I != E;
202  ++I) {
203  Dst.Add(*I);
204  }
205  return DidNotFinish;
206 }
207 
208 void CoreEngine::HandleBlockEdge(const BlockEdge &L, ExplodedNode *Pred) {
209  const CFGBlock *Blk = L.getDst();
210  NodeBuilderContext BuilderCtx(*this, Blk, Pred);
211 
212  // Mark this block as visited.
213  const LocationContext *LC = Pred->getLocationContext();
214  FunctionSummaries->markVisitedBasicBlock(Blk->getBlockID(),
215  LC->getDecl(),
216  LC->getCFG()->getNumBlockIDs());
217 
218  // Display a prunable path note to the user if it's a virtual bases branch
219  // and we're taking the path that skips virtual base constructors.
221  L.getDst() == *L.getSrc()->succ_begin()) {
222  ProgramPoint P = L.withTag(getDataTags().make<NoteTag>(
224  // TODO: Just call out the name of the most derived class
225  // when we know it.
226  return "Virtual base initialization skipped because "
227  "it has already been handled by the most derived class";
228  },
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  ExprEng.processEndOfFunction(BuilderCtx, Pred, RS);
257 
258  // This path is done. Don't enqueue any more nodes.
259  return;
260  }
261 
262  // Call into the ExprEngine to process entering the CFGBlock.
263  ExplodedNodeSet dstNodes;
264  BlockEntrance BE(Blk, Pred->getLocationContext());
265  NodeBuilderWithSinks nodeBuilder(Pred, dstNodes, BuilderCtx, BE);
266  ExprEng.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  ExprEng.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::SEHLeaveStmtClass:
354  case Stmt::ContinueStmtClass:
355  case Stmt::BreakStmtClass:
356  case Stmt::GotoStmtClass:
357  break;
358 
359  case Stmt::IfStmtClass:
360  HandleBranch(cast<IfStmt>(Term)->getCond(), Term, B, Pred);
361  return;
362 
363  case Stmt::IndirectGotoStmtClass: {
364  // Only 1 successor: the indirect goto dispatch block.
365  assert(B->succ_size() == 1);
366 
368  builder(Pred, B, cast<IndirectGotoStmt>(Term)->getTarget(),
369  *(B->succ_begin()), this);
370 
371  ExprEng.processIndirectGoto(builder);
372  return;
373  }
374 
375  case Stmt::ObjCForCollectionStmtClass:
376  // In the case of ObjCForCollectionStmt, it appears twice in a CFG:
377  //
378  // (1) inside a basic block, which represents the binding of the
379  // 'element' variable to a value.
380  // (2) in a terminator, which represents the branch.
381  //
382  // For (1), ExprEngine will bind a value (i.e., 0 or 1) indicating
383  // whether or not collection contains any more elements. We cannot
384  // just test to see if the element is nil because a container can
385  // contain nil elements.
386  HandleBranch(Term, Term, B, Pred);
387  return;
388 
389  case Stmt::SwitchStmtClass: {
390  SwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(),
391  this);
392 
393  ExprEng.processSwitch(builder);
394  return;
395  }
396 
397  case Stmt::WhileStmtClass:
398  HandleBranch(cast<WhileStmt>(Term)->getCond(), Term, B, Pred);
399  return;
400 
401  case Stmt::GCCAsmStmtClass:
402  assert(cast<GCCAsmStmt>(Term)->isAsmGoto() && "Encountered GCCAsmStmt without labels");
403  // TODO: Handle jumping to labels
404  return;
405  }
406  }
407 
408  if (B->getTerminator().isVirtualBaseBranch()) {
409  HandleVirtualBaseBranch(B, Pred);
410  return;
411  }
412 
413  assert(B->succ_size() == 1 &&
414  "Blocks with no terminator should have at most 1 successor.");
415 
416  generateNode(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()),
417  Pred->State, Pred);
418 }
419 
420 void CoreEngine::HandleCallEnter(const CallEnter &CE, ExplodedNode *Pred) {
421  NodeBuilderContext BuilderCtx(*this, CE.getEntry(), Pred);
422  ExprEng.processCallEnter(BuilderCtx, CE, Pred);
423 }
424 
425 void CoreEngine::HandleBranch(const Stmt *Cond, const Stmt *Term,
426  const CFGBlock * B, ExplodedNode *Pred) {
427  assert(B->succ_size() == 2);
428  NodeBuilderContext Ctx(*this, B, Pred);
429  ExplodedNodeSet Dst;
430  ExprEng.processBranch(Cond, Ctx, Pred, Dst, *(B->succ_begin()),
431  *(B->succ_begin() + 1));
432  // Enqueue the new frontier onto the worklist.
433  enqueue(Dst);
434 }
435 
436 void CoreEngine::HandleCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE,
437  const CFGBlock *B,
438  ExplodedNode *Pred) {
439  assert(B->succ_size() == 2);
440  NodeBuilderContext Ctx(*this, B, Pred);
441  ExplodedNodeSet Dst;
442  ExprEng.processCleanupTemporaryBranch(BTE, Ctx, Pred, Dst, *(B->succ_begin()),
443  *(B->succ_begin() + 1));
444  // Enqueue the new frontier onto the worklist.
445  enqueue(Dst);
446 }
447 
448 void CoreEngine::HandleStaticInit(const DeclStmt *DS, const CFGBlock *B,
449  ExplodedNode *Pred) {
450  assert(B->succ_size() == 2);
451  NodeBuilderContext Ctx(*this, B, Pred);
452  ExplodedNodeSet Dst;
453  ExprEng.processStaticInitializer(DS, Ctx, Pred, Dst,
454  *(B->succ_begin()), *(B->succ_begin()+1));
455  // Enqueue the new frontier onto the worklist.
456  enqueue(Dst);
457 }
458 
459 void CoreEngine::HandlePostStmt(const CFGBlock *B, unsigned StmtIdx,
460  ExplodedNode *Pred) {
461  assert(B);
462  assert(!B->empty());
463 
464  if (StmtIdx == B->size())
465  HandleBlockExit(B, Pred);
466  else {
467  NodeBuilderContext Ctx(*this, B, Pred);
468  ExprEng.processCFGElement((*B)[StmtIdx], Pred, StmtIdx, &Ctx);
469  }
470 }
471 
472 void CoreEngine::HandleVirtualBaseBranch(const CFGBlock *B,
473  ExplodedNode *Pred) {
474  const LocationContext *LCtx = Pred->getLocationContext();
475  if (const auto *CallerCtor = dyn_cast_or_null<CXXConstructExpr>(
476  LCtx->getStackFrame()->getCallSite())) {
477  switch (CallerCtor->getConstructionKind()) {
480  BlockEdge Loc(B, *B->succ_begin(), LCtx);
481  HandleBlockEdge(Loc, Pred);
482  return;
483  }
484  default:
485  break;
486  }
487  }
488 
489  // We either don't see a parent stack frame because we're in the top frame,
490  // or the parent stack frame doesn't initialize our virtual bases.
491  BlockEdge Loc(B, *(B->succ_begin() + 1), LCtx);
492  HandleBlockEdge(Loc, Pred);
493 }
494 
495 /// generateNode - Utility method to generate nodes, hook up successors,
496 /// and add nodes to the worklist.
497 void CoreEngine::generateNode(const ProgramPoint &Loc,
499  ExplodedNode *Pred) {
500  bool IsNew;
501  ExplodedNode *Node = G.getNode(Loc, State, false, &IsNew);
502 
503  if (Pred)
504  Node->addPredecessor(Pred, G); // Link 'Node' with its predecessor.
505  else {
506  assert(IsNew);
507  G.addRoot(Node); // 'Node' has no predecessor. Make it a root.
508  }
509 
510  // Only add 'Node' to the worklist if it was freshly generated.
511  if (IsNew) WList->enqueue(Node);
512 }
513 
515  const CFGBlock *Block, unsigned Idx) {
516  assert(Block);
517  assert(!N->isSink());
518 
519  // Check if this node entered a callee.
520  if (N->getLocation().getAs<CallEnter>()) {
521  // Still use the index of the CallExpr. It's needed to create the callee
522  // StackFrameContext.
523  WList->enqueue(N, Block, Idx);
524  return;
525  }
526 
527  // Do not create extra nodes. Move to the next CFG element.
528  if (N->getLocation().getAs<PostInitializer>() ||
530  N->getLocation().getAs<LoopExit>()) {
531  WList->enqueue(N, Block, Idx+1);
532  return;
533  }
534 
535  if (N->getLocation().getAs<EpsilonPoint>()) {
536  WList->enqueue(N, Block, Idx);
537  return;
538  }
539 
540  if ((*Block)[Idx].getKind() == CFGElement::NewAllocator) {
541  WList->enqueue(N, Block, Idx+1);
542  return;
543  }
544 
545  // At this point, we know we're processing a normal statement.
546  CFGStmt CS = (*Block)[Idx].castAs<CFGStmt>();
548 
549  if (Loc == N->getLocation().withTag(nullptr)) {
550  // Note: 'N' should be a fresh node because otherwise it shouldn't be
551  // a member of Deferred.
552  WList->enqueue(N, Block, Idx+1);
553  return;
554  }
555 
556  bool IsNew;
557  ExplodedNode *Succ = G.getNode(Loc, N->getState(), false, &IsNew);
558  Succ->addPredecessor(N, G);
559 
560  if (IsNew)
561  WList->enqueue(Succ, Block, Idx+1);
562 }
563 
564 ExplodedNode *CoreEngine::generateCallExitBeginNode(ExplodedNode *N,
565  const ReturnStmt *RS) {
566  // Create a CallExitBegin node and enqueue it.
567  const auto *LocCtx = cast<StackFrameContext>(N->getLocationContext());
568 
569  // Use the callee location context.
570  CallExitBegin Loc(LocCtx, RS);
571 
572  bool isNew;
573  ExplodedNode *Node = G.getNode(Loc, N->getState(), false, &isNew);
574  Node->addPredecessor(N, G);
575  return isNew ? Node : nullptr;
576 }
577 
579  for (const auto I : Set)
580  WList->enqueue(I);
581 }
582 
584  const CFGBlock *Block, unsigned Idx) {
585  for (const auto I : Set)
586  enqueueStmtNode(I, Block, Idx);
587 }
588 
590  for (auto I : Set) {
591  // If we are in an inlined call, generate CallExitBegin node.
592  if (I->getLocationContext()->getParent()) {
593  I = generateCallExitBeginNode(I, RS);
594  if (I)
595  WList->enqueue(I);
596  } else {
597  // TODO: We should run remove dead bindings here.
598  G.addEndOfPath(I);
599  NumPathsExplored++;
600  }
601  }
602 }
603 
604 void NodeBuilder::anchor() {}
605 
608  ExplodedNode *FromN,
609  bool MarkAsSink) {
610  HasGeneratedNodes = true;
611  bool IsNew;
612  ExplodedNode *N = C.Eng.G.getNode(Loc, State, MarkAsSink, &IsNew);
613  N->addPredecessor(FromN, C.Eng.G);
614  Frontier.erase(FromN);
615 
616  if (!IsNew)
617  return nullptr;
618 
619  if (!MarkAsSink)
620  Frontier.Add(N);
621 
622  return N;
623 }
624 
625 void NodeBuilderWithSinks::anchor() {}
626 
628  if (EnclosingBldr)
629  for (const auto I : Frontier)
630  EnclosingBldr->addNodes(I);
631 }
632 
633 void BranchNodeBuilder::anchor() {}
634 
636  bool branch,
637  ExplodedNode *NodePred) {
638  // If the branch has been marked infeasible we should not generate a node.
639  if (!isFeasible(branch))
640  return nullptr;
641 
642  ProgramPoint Loc = BlockEdge(C.Block, branch ? DstT:DstF,
643  NodePred->getLocationContext());
644  ExplodedNode *Succ = generateNodeImpl(Loc, State, NodePred);
645  return Succ;
646 }
647 
650  ProgramStateRef St,
651  bool IsSink) {
652  bool IsNew;
653  ExplodedNode *Succ =
654  Eng.G.getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()),
655  St, IsSink, &IsNew);
656  Succ->addPredecessor(Pred, Eng.G);
657 
658  if (!IsNew)
659  return nullptr;
660 
661  if (!IsSink)
662  Eng.WList->enqueue(Succ);
663 
664  return Succ;
665 }
666 
669  ProgramStateRef St) {
670  bool IsNew;
671  ExplodedNode *Succ =
672  Eng.G.getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()),
673  St, false, &IsNew);
674  Succ->addPredecessor(Pred, Eng.G);
675  if (!IsNew)
676  return nullptr;
677 
678  Eng.WList->enqueue(Succ);
679  return Succ;
680 }
681 
684  bool IsSink) {
685  // Get the block for the default case.
686  assert(Src->succ_rbegin() != Src->succ_rend());
687  CFGBlock *DefaultBlock = *Src->succ_rbegin();
688 
689  // Basic correctness check for default blocks that are unreachable and not
690  // caught by earlier stages.
691  if (!DefaultBlock)
692  return nullptr;
693 
694  bool IsNew;
695  ExplodedNode *Succ =
696  Eng.G.getNode(BlockEdge(Src, DefaultBlock, Pred->getLocationContext()),
697  St, IsSink, &IsNew);
698  Succ->addPredecessor(Pred, Eng.G);
699 
700  if (!IsNew)
701  return nullptr;
702 
703  if (!IsSink)
704  Eng.WList->enqueue(Succ);
705 
706  return Succ;
707 }
clang::ento::ExprEngine::processCallEnter
void processCallEnter(NodeBuilderContext &BC, CallEnter CE, ExplodedNode *Pred)
Generate the entry node of the callee.
Definition: ExprEngineCallAndReturn.cpp:43
clang::CFGBlock::getTerminator
CFGTerminator getTerminator() const
Definition: CFG.h:1048
clang::CallExitBegin
Represents a point when we start the call exit sequence (for inlined call).
Definition: ProgramPoint.h:668
clang::ento::ExplodedGraph::eop_begin
eop_iterator eop_begin()
Definition: ExplodedGraph.h:416
AnalyzerOptions.h
clang::ProgramPoint::withTag
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
clang::ProgramPoint::BlockExitKind
@ BlockExitKind
Definition: ProgramPoint.h:63
clang::ento::BlockCounter::Factory::GetEmptyCounter
BlockCounter GetEmptyCounter()
Definition: BlockCounter.cpp:82
clang::ento::ExplodedNode::getLocationContext
const LocationContext * getLocationContext() const
Definition: ExplodedGraph.h:146
clang::ento::WorkList::makeUnexploredFirstPriorityLocationQueue
static std::unique_ptr< WorkList > makeUnexploredFirstPriorityLocationQueue()
Definition: WorkList.cpp:311
clang::LocationContext
It wraps the AnalysisDeclContext to represent both the call stack with the help of StackFrameContext ...
Definition: AnalysisDeclContext.h:215
clang::LocationContext::getStackFrame
const StackFrameContext * getStackFrame() const
Definition: AnalysisDeclContext.cpp:463
clang::CFGBlock::succ_rbegin
succ_reverse_iterator succ_rbegin()
Definition: CFG.h:960
string
string(SUBSTRING ${CMAKE_CURRENT_BINARY_DIR} 0 ${PATH_LIB_START} PATH_HEAD) string(SUBSTRING $
Definition: CMakeLists.txt:22
clang::CFGBlock::empty
bool empty() const
Definition: CFG.h:918
clang::ento::SVal::castAs
T castAs() const
Convert to the specified SVal type, asserting that this SVal is of the desired type.
Definition: SVals.h:103
clang::CFGBlock::succ_size
unsigned succ_size() const
Definition: CFG.h:973
clang::CFG::getNumBlockIDs
unsigned getNumBlockIDs() const
Returns the total number of BlockIDs allocated (which start at 0).
Definition: CFG.h:1411
clang::CFGBlock::succ_begin
succ_iterator succ_begin()
Definition: CFG.h:955
clang::ento::SwitchNodeBuilder::iterator
Definition: CoreEngine.h:537
AnalysisDeclContext.h
clang::ento::ExplodedGraph::eop_iterator
NodeVector::iterator eop_iterator
Definition: ExplodedGraph.h:395
clang::ExplorationStrategyKind::DFS
@ DFS
clang::CFGElement::NewAllocator
@ NewAllocator
Definition: CFG.h:62
clang::CFGBlock::getBlockID
unsigned getBlockID() const
Definition: CFG.h:1074
clang::ento::WorkList::makeBFSBlockDFSContents
static std::unique_ptr< WorkList > makeBFSBlockDFSContents()
Definition: WorkList.cpp:126
clang::ento::ProgramStateRef
IntrusiveRefCntPtr< const ProgramState > ProgramStateRef
Definition: ProgramState_Fwd.h:37
clang::ento::ExplodedNode
Definition: ExplodedGraph.h:65
clang::ExplorationStrategyKind::UnexploredFirstLocationQueue
@ UnexploredFirstLocationQueue
clang::ento::CoreEngine::CoreEngine
CoreEngine(ExprEngine &exprengine, FunctionSummariesTy *FS, AnalyzerOptions &Opts)
Construct a CoreEngine object to analyze the provided CFG.
Definition: CoreEngine.cpp:73
clang::ento::ExplodedNodeSet::Add
void Add(ExplodedNode *N)
Definition: ExplodedGraph.h:475
clang::ExplorationStrategyKind::BFS
@ BFS
clang::ento::WorkListUnit
Definition: WorkList.h:27
llvm::Optional
Definition: LLVM.h:40
clang::ento::ExprEngine::processCleanupTemporaryBranch
void processCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE, NodeBuilderContext &BldCtx, ExplodedNode *Pred, ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF)
Called by CoreEngine.
Definition: ExprEngine.cpp:1129
clang::ProgramPoint::CallEnterKind
@ CallEnterKind
Definition: ProgramPoint.h:78
clang::EpsilonPoint
This is a meta program point, which should be skipped by all the diagnostic reasoning etc.
Definition: ProgramPoint.h:732
clang::CFGBlock::const_succ_iterator
AdjacentBlocks::const_iterator const_succ_iterator
Definition: CFG.h:931
clang::PostImplicitCall
Represents a program point just after an implicit call event.
Definition: ProgramPoint.h:600
clang::ento::NodeBuilderContext::Block
const CFGBlock * Block
Definition: CoreEngine.h:210
clang::ento::ExprEngine::processCallExit
void processCallExit(ExplodedNode *Pred)
Generate the sequence of nodes that simulate the call exit and the post visit for CallExpr.
Definition: ExprEngineCallAndReturn.cpp:206
clang::ProgramPoint::getLocationContext
const LocationContext * getLocationContext() const
Definition: ProgramPoint.h:179
clang::ento::SVal::getAs
Optional< T > getAs() const
Convert to the specified SVal type, returning None if this SVal is not of the desired type.
Definition: SVals.h:111
clang::ento::ExprEngine::processSwitch
void processSwitch(SwitchNodeBuilder &builder)
ProcessSwitch - Called by CoreEngine.
Definition: ExprEngine.cpp:2445
BlockCounter.h
clang::ento::NodeBuilder::Frontier
ExplodedNodeSet & Frontier
The frontier set - a set of nodes which need to be propagated after the builder dies.
Definition: CoreEngine.h:251
generateWorkList
static std::unique_ptr< WorkList > generateWorkList(AnalyzerOptions &Opts)
Definition: CoreEngine.cpp:55
clang::AnalyzerOptions::getExplorationStrategy
ExplorationStrategyKind getExplorationStrategy() const
Definition: AnalyzerOptions.cpp:65
clang::BlockEdge::getSrc
const CFGBlock * getSrc() const
Definition: ProgramPoint.h:511
clang::LoopExit
Represents a point when we exit a loop.
Definition: ProgramPoint.h:713
clang::CFGBlock
Represents a single basic block in a source-level CFG.
Definition: CFG.h:576
clang::PostAllocatorCall
Definition: ProgramPoint.h:614
clang::ento::WorkListUnit::getIndex
unsigned getIndex() const
Return the index within the CFGBlock for the worklist unit.
Definition: WorkList.h:57
clang::ento::WorkListUnit::getNode
ExplodedNode * getNode() const
Returns the node associated with the worklist unit.
Definition: WorkList.h:48
clang::ento::ExplodedNode::getState
const ProgramStateRef & getState() const
Definition: ExplodedGraph.h:169
ProgramPoint.h
min
__DEVICE__ int min(int __a, int __b)
Definition: __clang_cuda_math.h:197
clang::ento::CoreEngine::dispatchWorkItem
void dispatchWorkItem(ExplodedNode *Pred, ProgramPoint Loc, const WorkListUnit &WU)
Dispatch the work list item based on the given location information.
Definition: CoreEngine.cpp:153
clang::ProgramPoint::BlockEntranceKind
@ BlockEntranceKind
Definition: ProgramPoint.h:62
clang::ento::BranchNodeBuilder::generateNode
ExplodedNode * generateNode(ProgramStateRef State, bool branch, ExplodedNode *Pred)
Definition: CoreEngine.cpp:635
clang::ento::ExplodedGraph::getNode
ExplodedNode * getNode(const ProgramPoint &L, ProgramStateRef State, bool IsSink=false, bool *IsNew=nullptr)
Retrieve the node associated with a (Location,State) pair, where the 'Location' is a ProgramPoint in ...
Definition: ExplodedGraph.cpp:393
Node
DynTypedNode Node
Definition: ASTMatchFinder.cpp:67
clang::CXXBindTemporaryExpr
Represents binding an expression to a temporary.
Definition: ExprCXX.h:1412
clang::ento::CoreEngine::ExecuteWorkListWithInitialState
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:196
clang::ento::ExplodedNode::addPredecessor
void addPredecessor(ExplodedNode *V, ExplodedGraph &G)
addPredeccessor - Adds a predecessor to the current node, and in tandem add this node as a successor ...
Definition: ExplodedGraph.cpp:204
clang::ento::ExplodedNode::hasSinglePred
bool hasSinglePred() const
Definition: ExplodedGraph.h:206
clang::ento::ExplodedNode::isSink
bool isSink() const
Definition: ExplodedGraph.h:204
clang::ProgramPoint::getAs
Optional< T > getAs() const
Convert to the specified ProgramPoint type, returning None if this ProgramPoint is not of the desired...
Definition: ProgramPoint.h:151
clang::ento::WorkList::makeDFS
static std::unique_ptr< WorkList > makeDFS()
Definition: WorkList.cpp:81
clang::CFGBlock::size
unsigned size() const
Definition: CFG.h:917
clang::CallExitEnd
Represents a point when we finish the call exit sequence (for inlined call).
Definition: ProgramPoint.h:688
clang::ento::CoreEngine::enqueueStmtNode
void enqueueStmtNode(ExplodedNode *N, const CFGBlock *Block, unsigned Idx)
Enqueue a single node created as a result of statement processing.
Definition: CoreEngine.cpp:514
clang::ento::WorkList::makeBFS
static std::unique_ptr< WorkList > makeBFS()
Definition: WorkList.cpp:85
clang::CFGAutomaticObjDtor
Represents C++ object destructor implicitly generated for automatic object or temporary bound to cons...
Definition: CFG.h:389
clang::ento::ExprEngine::processBranch
void processBranch(const Stmt *Condition, NodeBuilderContext &BuilderCtx, ExplodedNode *Pred, ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF)
ProcessBranch - Called by CoreEngine.
Definition: ExprEngine.cpp:2216
clang::ento::ExprEngine::processCFGBlockEntrance
void processCFGBlockEntrance(const BlockEdge &L, NodeBuilderWithSinks &nodeBuilder, ExplodedNode *Pred)
Called by CoreEngine when processing the entrance of a CFGBlock.
Definition: ExprEngine.cpp:1962
clang::CFGTerminator::isVirtualBaseBranch
bool isVirtualBaseBranch() const
Definition: CFG.h:545
Expr.h
clang::ento::NodeBuilder::generateNodeImpl
ExplodedNode * generateNodeImpl(const ProgramPoint &PP, ProgramStateRef State, ExplodedNode *Pred, bool MarkAsSink=false)
Definition: CoreEngine.cpp:606
clang::PostInitializer
Definition: ProgramPoint.h:527
clang::ento::BugReporterContext
Definition: BugReporter.h:703
STATISTIC
STATISTIC(NumSteps, "The # of steps executed.")
clang::BlockEdge::getDst
const CFGBlock * getDst() const
Definition: ProgramPoint.h:515
ExprCXX.h
clang::CallEnter::getEntry
const CFGBlock * getEntry() const
Returns the entry block in the CFG for the entered function.
Definition: ProgramPoint.h:645
clang::ento::WorkListUnit::getBlockCounter
BlockCounter getBlockCounter() const
Returns the block counter map associated with the worklist unit.
Definition: WorkList.h:51
clang::CFG::getExit
CFGBlock & getExit()
Definition: CFG.h:1333
clang::ento::IndirectGotoNodeBuilder::iterator::getBlock
const CFGBlock * getBlock() const
Definition: CoreEngine.h:505
getKind
static Decl::Kind getKind(const Decl *D)
Definition: DeclBase.cpp:998
ExplodedGraph.h
clang::ento::Loc
Definition: SVals.h:327
clang::ento::ExprEngine::processEndWorklist
void processEndWorklist()
Called by CoreEngine when the analysis worklist has terminated.
Definition: ExprEngine.cpp:622
clang::ento::BlockCounter::Factory::IncrementCount
BlockCounter IncrementCount(BlockCounter BC, const StackFrameContext *CallSite, unsigned BlockID)
Definition: BlockCounter.cpp:73
FunctionSummary.h
clang::ento::ExprEngine::getInitialState
ProgramStateRef getInitialState(const LocationContext *InitLoc)
getInitialState - Return the initial state used for the root vertex in the ExplodedGraph.
Definition: ExprEngine.cpp:232
clang::BlockEntrance
Definition: ProgramPoint.h:225
clang::PostStmt
Definition: ProgramPoint.h:311
clang::ento::WorkListUnit::getBlock
const CFGBlock * getBlock() const
Returns the CFGblock associated with the worklist unit.
Definition: WorkList.h:54
clang::CFGBlock::back
CFGElement back() const
Definition: CFG.h:873
P
StringRef P
Definition: ASTMatchersInternal.cpp:563
clang::CFGStmt
Definition: CFG.h:132
clang::CFGElement::castAs
T castAs() const
Convert to the specified CFGElement type, asserting that this CFGElement is of the desired type.
Definition: CFG.h:98
clang::ProgramPoint::BlockEdgeKind
@ BlockEdgeKind
Definition: ProgramPoint.h:61
clang::ProgramPoint::CallExitBeginKind
@ CallExitBeginKind
Definition: ProgramPoint.h:79
clang::ento::BranchNodeBuilder::isFeasible
bool isFeasible(bool branch)
Definition: CoreEngine.h:473
clang::ento::StmtNodeBuilder::~StmtNodeBuilder
~StmtNodeBuilder() override
Definition: CoreEngine.cpp:627
clang::CFGElement::getAs
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
clang::CFGBlock::succ_end
succ_iterator succ_end()
Definition: CFG.h:956
clang::ento::NodeBuilder::HasGeneratedNodes
bool HasGeneratedNodes
Definition: CoreEngine.h:247
clang::ento::CoreEngine::enqueueEndOfFunction
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:589
clang::ento::ExprEngine::processEndOfFunction
void processEndOfFunction(NodeBuilderContext &BC, ExplodedNode *Pred, const ReturnStmt *RS=nullptr)
Called by CoreEngine.
Definition: ExprEngine.cpp:2371
clang::ento::ExplodedNode::getFirstPred
ExplodedNode * getFirstPred()
Definition: ExplodedGraph.h:210
clang::ento::FunctionSummariesTy::markVisitedBasicBlock
void markVisitedBasicBlock(unsigned ID, const Decl *D, unsigned TotalIDs)
Definition: FunctionSummary.h:96
clang::BlockEntrance::getFirstElement
Optional< CFGElement > getFirstElement() const
Definition: ProgramPoint.h:237
clang::ento::ExprEngine::processStaticInitializer
void processStaticInitializer(const DeclStmt *DS, NodeBuilderContext &BuilderCtx, ExplodedNode *Pred, ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF)
Called by CoreEngine.
clang::StackFrameContext::getCallSite
const Stmt * getCallSite() const
Definition: AnalysisDeclContext.h:321
clang::ExplorationStrategyKind::BFSBlockDFSContents
@ BFSBlockDFSContents
clang::ento::FunctionSummariesTy
Definition: FunctionSummary.h:33
clang::ento::CoreEngine::IndirectGotoNodeBuilder
friend class IndirectGotoNodeBuilder
Definition: CoreEngine.h:59
LLVM.h
clang::AnalyzerOptions
Stores options for the analyzer from the command line.
Definition: AnalyzerOptions.h:163
clang::CFGBlock::succ_rend
succ_reverse_iterator succ_rend()
Definition: CFG.h:961
clang::CFGStmt::getStmt
const Stmt * getStmt() const
Definition: CFG.h:138
State
LineState State
Definition: UnwrappedLineFormatter.cpp:987
clang::CFG::getEntry
CFGBlock & getEntry()
Definition: CFG.h:1331
clang::ento::ExprEngine::processIndirectGoto
void processIndirectGoto(IndirectGotoNodeBuilder &builder)
processIndirectGoto - Called by CoreEngine.
Definition: ExprEngine.cpp:2320
clang::ento::ExprEngine::processBeginOfFunction
void processBeginOfFunction(NodeBuilderContext &BC, ExplodedNode *Pred, ExplodedNodeSet &Dst, const BlockEdge &L)
Called by CoreEngine.
Definition: ExprEngine.cpp:2361
clang::ExplorationStrategyKind::UnexploredFirstQueue
@ UnexploredFirstQueue
clang::ento::IndirectGotoNodeBuilder::generateNode
ExplodedNode * generateNode(const iterator &I, ProgramStateRef State, bool isSink=false)
Definition: CoreEngine.cpp:649
CoreEngine.h
clang::ExplorationStrategyKind::UnexploredFirst
@ UnexploredFirst
clang::CFGElement
Represents a top-level expression in a basic block.
Definition: CFG.h:55
clang::DeclStmt
DeclStmt - Adaptor class for mixing declarations with statements and expressions.
Definition: Stmt.h:1297
clang::ento::ExprEngine
Definition: ExprEngine.h:127
clang::ento::CoreEngine::enqueue
void enqueue(ExplodedNodeSet &Set)
Enqueue the given set of nodes onto the work list.
Definition: CoreEngine.cpp:578
clang::ento::PathSensitiveBugReport
Definition: BugReporter.h:291
clang::ento::ExplodedGraph::reserve
void reserve(unsigned NodeCount)
Definition: ExplodedGraph.h:388
ExprEngine.h
clang::ento::ExplodedGraph::addEndOfPath
ExplodedNode * addEndOfPath(ExplodedNode *V)
addEndOfPath - Add an untyped node to the set of EOP nodes.
Definition: ExplodedGraph.h:377
clang::ento::NodeBuilder::C
const NodeBuilderContext & C
Definition: CoreEngine.h:241
WorkList.h
clang::CXXConstructExpr::CK_NonVirtualBase
@ CK_NonVirtualBase
Definition: ExprCXX.h:1466
clang::ento::CoreEngine::SwitchNodeBuilder
friend class SwitchNodeBuilder
Definition: CoreEngine.h:62
clang
Definition: CalledOnceCheck.h:17
clang::ento::ExplodedNode::getLocation
ProgramPoint getLocation() const
getLocation - Returns the edge associated with the given node.
Definition: ExplodedGraph.h:144
clang::ProgramPoint::EpsilonKind
@ EpsilonKind
Definition: ProgramPoint.h:87
CFG.h
clang::DeclaratorContext::Block
@ Block
clang::Stmt
Stmt - This represents one statement.
Definition: Stmt.h:69
clang::CXXConstructExpr::CK_VirtualBase
@ CK_VirtualBase
Definition: ExprCXX.h:1467
clang::ento::ExprEngine::processCFGElement
void processCFGElement(const CFGElement E, ExplodedNode *Pred, unsigned StmtIdx, NodeBuilderContext *Ctx)
processCFGElement - Called by CoreEngine.
Definition: ExprEngine.cpp:626
clang::CFGBlock::getTerminatorStmt
Stmt * getTerminatorStmt()
Definition: CFG.h:1050
clang::ento::ExplodedGraph::num_roots
unsigned num_roots() const
Definition: ExplodedGraph.h:382
clang::ento::WorkList::makeUnexploredFirstPriorityQueue
static std::unique_ptr< WorkList > makeUnexploredFirstPriorityQueue()
Definition: WorkList.cpp:251
clang::ento::IndirectGotoNodeBuilder::iterator
Definition: CoreEngine.h:490
clang::ento::WorkList::makeUnexploredFirst
static std::unique_ptr< WorkList > makeUnexploredFirst()
Definition: WorkList.cpp:188
clang::ento::ExplodedNodeSet::erase
bool erase(ExplodedNode *N)
Definition: ExplodedGraph.h:484
clang::ento::NodeBuilderContext
Definition: CoreEngine.h:208
clang::CallEnter
Represents a point when we begin processing an inlined call.
Definition: ProgramPoint.h:630
clang::BlockEdge
Definition: ProgramPoint.h:503
clang::ento::CoreEngine::getDataTags
DataTag::Factory & getDataTags()
Definition: CoreEngine.h:204
clang::LocationContext::getCFG
CFG * getCFG() const
Definition: AnalysisDeclContext.h:249
clang::ento::SwitchNodeBuilder::generateDefaultCaseNode
ExplodedNode * generateDefaultCaseNode(ProgramStateRef State, bool isSink=false)
Definition: CoreEngine.cpp:683
Stmt.h
clang::ento::NodeBuilder::addNodes
void addNodes(const ExplodedNodeSet &S)
Definition: CoreEngine.h:336
clang::BlockEntrance::getBlock
const CFGBlock * getBlock() const
Definition: ProgramPoint.h:233
clang::ento::NodeBuilderContext::Eng
const CoreEngine & Eng
Definition: CoreEngine.h:209
clang::LocationContext::getDecl
const Decl * getDecl() const
Definition: AnalysisDeclContext.h:247
clang::ento::ExplodedNodeSet
Definition: ExplodedGraph.h:463
clang::ento::ExplodedGraph::eop_end
eop_iterator eop_end()
Definition: ExplodedGraph.h:418
clang::ProgramPoint
Definition: ProgramPoint.h:59
clang::ento::CoreEngine::NodeBuilderContext
friend struct NodeBuilderContext
Definition: CoreEngine.h:61
clang::ento::SwitchNodeBuilder::generateCaseStmtNode
ExplodedNode * generateCaseStmtNode(const iterator &I, ProgramStateRef State)
Definition: CoreEngine.cpp:668
clang::ento::CoreEngine::ExecuteWorkList
bool ExecuteWorkList(const LocationContext *L, unsigned Steps, ProgramStateRef InitState)
ExecuteWorkList - Run the worklist algorithm for a maximum number of steps.
Definition: CoreEngine.cpp:79
StmtCXX.h
clang::ento::ExplodedGraph::addRoot
ExplodedNode * addRoot(ExplodedNode *V)
addRoot - Add an untyped node to the set of roots.
Definition: ExplodedGraph.h:371
llvm::IntrusiveRefCntPtr< const ProgramState >
clang::ento::CoreEngine::NodeBuilder
friend class NodeBuilder
Definition: CoreEngine.h:60
clang::ReturnStmt
ReturnStmt - This represents a return, optionally of an expression: return; return 4;.
Definition: Stmt.h:2765
clang::ento::SwitchNodeBuilder::iterator::getBlock
const CFGBlock * getBlock() const
Definition: CoreEngine.h:553