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
14#include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h"
15#include "PrettyStackTraceStackFrame.h"
16#include "clang/AST/Expr.h"
17#include "clang/AST/ExprCXX.h"
18#include "clang/AST/Stmt.h"
19#include "clang/AST/StmtCXX.h"
20#include "clang/Analysis/AnalysisDeclContext.h"
21#include "clang/Analysis/CFG.h"
22#include "clang/Analysis/ProgramPoint.h"
23#include "clang/Basic/LLVM.h"
24#include "clang/StaticAnalyzer/Core/AnalyzerOptions.h"
25#include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h"
26#include "clang/StaticAnalyzer/Core/PathSensitive/EntryPointStats.h"
27#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
28#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
29#include "clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h"
30#include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h"
31#include "llvm/Support/ErrorHandling.h"
32#include "llvm/Support/FormatVariadic.h"
33#include "llvm/Support/TimeProfiler.h"
34#include <algorithm>
35#include <cassert>
36#include <memory>
37#include <optional>
38#include <utility>
39
40using namespace clang;
41using namespace ento;
42
43#define DEBUG_TYPE "CoreEngine"
44
45STAT_COUNTER(NumSteps, "The # of steps executed.");
46STAT_COUNTER(NumSTUSteps, "The # of STU steps executed.");
47STAT_COUNTER(NumCTUSteps, "The # of CTU steps executed.");
48ALWAYS_ENABLED_STATISTIC(NumReachedMaxSteps,
49 "The # of times we reached the max number of steps.");
50STAT_COUNTER(NumPathsExplored, "The # of paths explored by the analyzer.");
51
52//===----------------------------------------------------------------------===//
53// Core analysis engine.
54//===----------------------------------------------------------------------===//
55
56static std::unique_ptr<WorkList> generateWorkList(AnalyzerOptions &Opts) {
57 switch (Opts.getExplorationStrategy()) {
58 case ExplorationStrategyKind::DFS:
59 return WorkList::makeDFS();
60 case ExplorationStrategyKind::BFS:
61 return WorkList::makeBFS();
62 case ExplorationStrategyKind::BFSBlockDFSContents:
63 return WorkList::makeBFSBlockDFSContents();
64 case ExplorationStrategyKind::UnexploredFirst:
65 return WorkList::makeUnexploredFirst();
66 case ExplorationStrategyKind::UnexploredFirstQueue:
67 return WorkList::makeUnexploredFirstPriorityQueue();
68 case ExplorationStrategyKind::UnexploredFirstLocationQueue:
69 return WorkList::makeUnexploredFirstPriorityLocationQueue();
70 }
71 llvm_unreachable("Unknown AnalyzerOptions::ExplorationStrategyKind");
72}
73
74CoreEngine::CoreEngine(ExprEngine &exprengine, FunctionSummariesTy *FS,
75 AnalyzerOptions &Opts)
76 : ExprEng(exprengine), WList(generateWorkList(Opts)),
77 CTUWList(Opts.IsNaiveCTUEnabled ? generateWorkList(Opts) : nullptr),
78 BCounterFactory(G.getAllocator()), FunctionSummaries(FS) {}
79
80void CoreEngine::setBlockCounter(BlockCounter C) {
81 WList->setBlockCounter(C);
82 if (CTUWList)
83 CTUWList->setBlockCounter(C);
84}
85
86/// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps.
87bool CoreEngine::ExecuteWorkList(const StackFrame *SF, unsigned MaxSteps,
88 ProgramStateRef InitState) {
89 if (G.empty()) {
90 assert(!G.getRoot() && "empty graph must not have a root node");
91 // Initialize the analysis by constructing the root if there are no nodes.
92
93 const CFGBlock *Entry = &(SF->getCFG()->getEntry());
94
95 assert(Entry->empty() && "Entry block must be empty.");
96
97 assert(Entry->succ_size() == 1 && "Entry block must have 1 successor.");
98
99 // Mark the entry block as visited.
100 FunctionSummaries->markVisitedBasicBlock(ID: Entry->getBlockID(), D: SF->getDecl(),
101 TotalIDs: SF->getCFG()->getNumBlockIDs());
102
103 // Get the solitary successor.
104 const CFGBlock *Succ = *(Entry->succ_begin());
105
106 // Construct an edge representing the
107 // starting location in the function.
108 BlockEdge StartLoc(Entry, Succ, SF);
109
110 // Set the current block counter to being empty.
111 setBlockCounter(BCounterFactory.GetEmptyCounter());
112
113 if (!InitState)
114 InitState = ExprEng.getInitialState(InitSF: SF);
115
116 bool IsNew;
117 ExplodedNode *Node = G.getNode(L: StartLoc, State: InitState, IsSink: false, IsNew: &IsNew);
118 assert(IsNew);
119 G.designateAsRoot(V: Node);
120
121 ExprEng.setCurrStackFrameAndBlock(SF: Node->getStackFrame(), B: Succ);
122
123 ExplodedNodeSet DstBegin;
124 ExprEng.processBeginOfFunction(Pred: Node, Dst&: DstBegin, L: StartLoc);
125
126 enqueue(Set&: DstBegin);
127 }
128
129 // Check if we have a steps limit
130 bool UnlimitedSteps = MaxSteps == 0;
131
132 // Cap our pre-reservation in the event that the user specifies
133 // a very large number of maximum steps.
134 const unsigned PreReservationCap = 4000000;
135 if(!UnlimitedSteps)
136 G.reserve(NodeCount: std::min(a: MaxSteps, b: PreReservationCap));
137
138 auto ProcessWList = [this, UnlimitedSteps](unsigned MaxSteps) {
139 unsigned Steps = MaxSteps;
140 while (WList->hasWork()) {
141 if (!UnlimitedSteps) {
142 if (Steps == 0) {
143 NumReachedMaxSteps++;
144 break;
145 }
146 --Steps;
147 }
148
149 NumSteps++;
150
151 const WorkListUnit &WU = WList->dequeue();
152
153 // Set the current block counter.
154 setBlockCounter(WU.getBlockCounter());
155
156 // Retrieve the node.
157 ExplodedNode *Node = WU.getNode();
158
159 dispatchWorkItem(Pred: Node, Loc: Node->getLocation(), WU);
160 }
161 return MaxSteps - Steps;
162 };
163 const unsigned STUSteps = ProcessWList(MaxSteps);
164
165 if (CTUWList) {
166 NumSTUSteps += STUSteps;
167 const unsigned MinCTUSteps =
168 this->ExprEng.getAnalysisManager().options.CTUMaxNodesMin;
169 const unsigned Pct =
170 this->ExprEng.getAnalysisManager().options.CTUMaxNodesPercentage;
171 unsigned MaxCTUSteps = std::max(a: STUSteps * Pct / 100, b: MinCTUSteps);
172
173 WList = std::move(CTUWList);
174 const unsigned CTUSteps = ProcessWList(MaxCTUSteps);
175 NumCTUSteps += CTUSteps;
176 }
177
178 ExprEng.processEndWorklist();
179 return WList->hasWork();
180}
181
182static std::string timeTraceScopeName(const ProgramPoint &Loc) {
183 if (llvm::timeTraceProfilerEnabled()) {
184 return llvm::formatv(Fmt: "dispatchWorkItem {0}",
185 Vals: ProgramPoint::getProgramPointKindName(K: Loc.getKind()))
186 .str();
187 }
188 return "";
189}
190
191static llvm::TimeTraceMetadata timeTraceMetadata(const ExplodedNode *Pred,
192 const ProgramPoint &Loc) {
193 // If time-trace profiler is not enabled, this function is never called.
194 assert(llvm::timeTraceProfilerEnabled());
195 std::string Detail = "";
196 if (const auto SP = Loc.getAs<StmtPoint>()) {
197 if (const Stmt *S = SP->getStmt())
198 Detail = S->getStmtClassName();
199 }
200 auto SLoc = Loc.getSourceLocation();
201 if (!SLoc)
202 return llvm::TimeTraceMetadata{.Detail: std::move(Detail), .File: ""};
203 const auto &SM = Pred->getStackFrame()
204 ->getAnalysisDeclContext()
205 ->getASTContext()
206 .getSourceManager();
207 auto Line = SM.getPresumedLineNumber(Loc: *SLoc);
208 auto Fname = SM.getFilename(SpellingLoc: *SLoc);
209 return llvm::TimeTraceMetadata{.Detail: std::move(Detail), .File: Fname.str(),
210 .Line: static_cast<int>(Line)};
211}
212
213void CoreEngine::dispatchWorkItem(ExplodedNode *Pred, ProgramPoint Loc,
214 const WorkListUnit &WU) {
215 llvm::TimeTraceScope tcs{timeTraceScopeName(Loc), [Loc, Pred]() {
216 return timeTraceMetadata(Pred, Loc);
217 }};
218 PrettyStackTraceStackFrame CrashInfo(Pred->getStackFrame());
219
220 // This work item is not necessarily related to the previous one, so
221 // the old current StackFrame and Block is no longer relevant.
222 // The new current StackFrame and Block should be set soon, but this
223 // guarantees that buggy access before that will trigger loud crashes instead
224 // of silently using stale data.
225 ExprEng.resetCurrStackFrameAndBlock();
226
227 // Dispatch on the location type.
228 switch (Loc.getKind()) {
229 case ProgramPoint::BlockEdgeKind:
230 HandleBlockEdge(E: Loc.castAs<BlockEdge>(), Pred);
231 break;
232
233 case ProgramPoint::BlockEntranceKind:
234 HandleBlockEntrance(E: Loc.castAs<BlockEntrance>(), Pred);
235 break;
236
237 case ProgramPoint::BlockExitKind:
238 assert(false && "BlockExit location never occur in forward analysis.");
239 break;
240
241 case ProgramPoint::CallEnterKind:
242 HandleCallEnter(CE: Loc.castAs<CallEnter>(), Pred);
243 break;
244
245 case ProgramPoint::CallExitBeginKind:
246 ExprEng.processCallExit(Pred);
247 break;
248
249 case ProgramPoint::EpsilonKind: {
250 assert(Pred->hasSinglePred() &&
251 "Assume epsilon has exactly one predecessor by construction");
252 ExplodedNode *PNode = Pred->getFirstPred();
253 dispatchWorkItem(Pred, Loc: PNode->getLocation(), WU);
254 break;
255 }
256 default:
257 assert(Loc.getAs<PostStmt>() || Loc.getAs<PostInitializer>() ||
258 Loc.getAs<PostImplicitCall>() || Loc.getAs<CallExitEnd>() ||
259 Loc.getAs<LoopExit>() || Loc.getAs<LifetimeEnd>() ||
260 Loc.getAs<PostAllocatorCall>());
261 HandlePostStmt(B: WU.getBlock(), StmtIdx: WU.getIndex(), Pred);
262 break;
263 }
264}
265
266void CoreEngine::HandleBlockEdge(const BlockEdge &L, ExplodedNode *Pred) {
267 const CFGBlock *Blk = L.getDst();
268 ExprEng.setCurrStackFrameAndBlock(SF: Pred->getStackFrame(), B: Blk);
269
270 // Mark this block as visited.
271 const StackFrame *SF = Pred->getStackFrame();
272 FunctionSummaries->markVisitedBasicBlock(ID: Blk->getBlockID(), D: SF->getDecl(),
273 TotalIDs: SF->getCFG()->getNumBlockIDs());
274
275 // Display a prunable path note to the user if it's a virtual bases branch
276 // and we're taking the path that skips virtual base constructors.
277 if (L.getSrc()->getTerminator().isVirtualBaseBranch() &&
278 L.getDst() == *L.getSrc()->succ_begin()) {
279 ProgramPoint P = L.withTag(tag: getDataTags().make<NoteTag>(
280 ConstructorArgs: [](BugReporterContext &, PathSensitiveBugReport &) -> std::string {
281 // TODO: Just call out the name of the most derived class
282 // when we know it.
283 return "Virtual base initialization skipped because "
284 "it has already been handled by the most derived class";
285 },
286 /*IsPrunable=*/ConstructorArgs: true));
287 // Perform the transition.
288 Pred = makeNode(Loc: P, State: Pred->getState(), Pred);
289 if (!Pred)
290 return;
291 }
292
293 // Check if we are entering the EXIT block.
294 const CFGBlock &ExitBlk = L.getStackFrame()->getCFG()->getExit();
295 if (Blk == &ExitBlk) {
296 assert(ExitBlk.empty() && "EXIT block cannot contain Stmts.");
297
298 // Get return statement..
299 const ReturnStmt *RS = nullptr;
300 if (!L.getSrc()->empty()) {
301 CFGElement LastElement = L.getSrc()->back();
302 if (std::optional<CFGStmt> LastStmt = LastElement.getAs<CFGStmt>()) {
303 RS = dyn_cast<ReturnStmt>(Val: LastStmt->getStmt());
304 } else if (std::optional<CFGAutomaticObjDtor> AutoDtor =
305 LastElement.getAs<CFGAutomaticObjDtor>()) {
306 RS = dyn_cast<ReturnStmt>(Val: AutoDtor->getTriggerStmt());
307 } else if (std::optional<CFGScopeMarker> ScopeMarker =
308 LastElement.getAs<CFGScopeMarker>()) {
309 RS = dyn_cast<ReturnStmt>(Val: ScopeMarker->getTriggerStmt());
310 }
311 }
312
313 ExplodedNodeSet CheckerNodes;
314 BlockEntrance BE(L.getSrc(), L.getDst(), Pred->getStackFrame());
315 ExprEng.runCheckersForBlockEntrance(Entrance: BE, Pred, Dst&: CheckerNodes);
316
317 // Process the final state transition.
318 for (ExplodedNode *P : CheckerNodes) {
319 ExprEng.processEndOfFunction(Pred: P, RS);
320 }
321
322 // This path is done. Don't enqueue any more nodes.
323 return;
324 }
325
326 // Call into the ExprEngine to process entering the CFGBlock.
327 BlockEntrance BE(L.getSrc(), L.getDst(), Pred->getStackFrame());
328 ExplodedNodeSet DstNodes;
329 NodeBuilder Builder(Pred, DstNodes, ExprEng.getBuilderContext());
330 ExprEng.processCFGBlockEntrance(L, BE, Builder, Pred);
331
332 // Auto-generate a node.
333 if (!Builder.hasGeneratedNodes()) {
334 Builder.generateNode(PP: BE, State: Pred->State, Pred);
335 }
336
337 ExplodedNodeSet CheckerNodes;
338 for (auto *N : DstNodes) {
339 ExprEng.runCheckersForBlockEntrance(Entrance: BE, Pred: N, Dst&: CheckerNodes);
340 }
341
342 // Enqueue nodes onto the worklist.
343 enqueue(Set&: CheckerNodes);
344}
345
346void CoreEngine::HandleBlockEntrance(const BlockEntrance &L,
347 ExplodedNode *Pred) {
348 // Increment the block counter.
349 const StackFrame *SF = Pred->getStackFrame();
350 unsigned BlockId = L.getBlock()->getBlockID();
351 BlockCounter Counter = WList->getBlockCounter();
352 Counter = BCounterFactory.IncrementCount(BC: Counter, CallSite: SF, BlockID: BlockId);
353 setBlockCounter(Counter);
354
355 // Process the entrance of the block.
356 if (std::optional<CFGElement> E = L.getFirstElement()) {
357 ExprEng.setCurrStackFrameAndBlock(SF: Pred->getStackFrame(), B: L.getBlock());
358 ExprEng.processCFGElement(E: *E, Pred, StmtIdx: 0);
359 } else
360 HandleBlockExit(B: L.getBlock(), Pred);
361}
362
363void CoreEngine::HandleBlockExit(const CFGBlock * B, ExplodedNode *Pred) {
364 if (const Stmt *Term = B->getTerminatorStmt()) {
365 ExprEng.setCurrStackFrameAndBlock(SF: Pred->getStackFrame(), B);
366
367 switch (Term->getStmtClass()) {
368 default:
369 llvm_unreachable("Analysis for this terminator not implemented.");
370
371 case Stmt::CXXBindTemporaryExprClass:
372 HandleCleanupTemporaryBranch(
373 BTE: cast<CXXBindTemporaryExpr>(Val: Term), B, Pred);
374 return;
375
376 // Model static initializers.
377 case Stmt::DeclStmtClass:
378 HandleStaticInit(DS: cast<DeclStmt>(Val: Term), B, Pred);
379 return;
380
381 case Stmt::BinaryOperatorClass: // '&&' and '||'
382 HandleBranch(Cond: cast<BinaryOperator>(Val: Term)->getLHS(), Term, B, Pred);
383 return;
384
385 case Stmt::BinaryConditionalOperatorClass:
386 case Stmt::ConditionalOperatorClass:
387 HandleBranch(Cond: cast<AbstractConditionalOperator>(Val: Term)->getCond(),
388 Term, B, Pred);
389 return;
390
391 // FIXME: Use constant-folding in CFG construction to simplify this
392 // case.
393
394 case Stmt::ChooseExprClass:
395 HandleBranch(Cond: cast<ChooseExpr>(Val: Term)->getCond(), Term, B, Pred);
396 return;
397
398 case Stmt::CXXTryStmtClass:
399 // Generate a node for each of the successors.
400 // Our logic for EH analysis can certainly be improved.
401 for (const CFGBlock *Succ : B->succs()) {
402 if (Succ) {
403 BlockEdge BE(B, Succ, Pred->getStackFrame());
404 if (ExplodedNode *N = makeNode(Loc: BE, State: Pred->State, Pred))
405 WList->enqueue(N);
406 }
407 }
408 return;
409
410 case Stmt::DoStmtClass:
411 HandleBranch(Cond: cast<DoStmt>(Val: Term)->getCond(), Term, B, Pred);
412 return;
413
414 case Stmt::CXXForRangeStmtClass:
415 HandleBranch(Cond: cast<CXXForRangeStmt>(Val: Term)->getCond(), Term, B, Pred);
416 return;
417
418 case Stmt::ForStmtClass:
419 HandleBranch(Cond: cast<ForStmt>(Val: Term)->getCond(), Term, B, Pred);
420 return;
421
422 case Stmt::SEHLeaveStmtClass:
423 case Stmt::ContinueStmtClass:
424 case Stmt::BreakStmtClass:
425 case Stmt::GotoStmtClass:
426 break;
427
428 case Stmt::IfStmtClass:
429 HandleBranch(Cond: cast<IfStmt>(Val: Term)->getCond(), Term, B, Pred);
430 return;
431
432 case Stmt::IndirectGotoStmtClass: {
433 // Only 1 successor: the indirect goto dispatch block.
434 assert(B->succ_size() == 1);
435 ExplodedNodeSet Dst;
436 ExprEng.processIndirectGoto(Dst,
437 Tgt: cast<IndirectGotoStmt>(Val: Term)->getTarget(),
438 Dispatch: *(B->succ_begin()), Pred);
439 enqueue(Set&: Dst);
440 return;
441 }
442
443 case Stmt::ObjCForCollectionStmtClass:
444 // In the case of ObjCForCollectionStmt, it appears twice in a CFG:
445 //
446 // (1) inside a basic block, which represents the binding of the
447 // 'element' variable to a value.
448 // (2) in a terminator, which represents the branch.
449 //
450 // For (1), ExprEngine will bind a value (i.e., 0 or 1) indicating
451 // whether or not collection contains any more elements. We cannot
452 // just test to see if the element is nil because a container can
453 // contain nil elements.
454 HandleBranch(Cond: Term, Term, B, Pred);
455 return;
456
457 case Stmt::SwitchStmtClass: {
458 ExplodedNodeSet Dst;
459 ExprEng.processSwitch(Switch: cast<SwitchStmt>(Val: Term), Pred, Dst);
460 // Enqueue the new frontier onto the worklist.
461 enqueue(Set&: Dst);
462 return;
463 }
464
465 case Stmt::WhileStmtClass:
466 HandleBranch(Cond: cast<WhileStmt>(Val: Term)->getCond(), Term, B, Pred);
467 return;
468
469 case Stmt::GCCAsmStmtClass:
470 assert(cast<GCCAsmStmt>(Term)->isAsmGoto() && "Encountered GCCAsmStmt without labels");
471 // TODO: Handle jumping to labels
472 return;
473 }
474 }
475
476 if (B->getTerminator().isVirtualBaseBranch()) {
477 HandleVirtualBaseBranch(B, Pred);
478 return;
479 }
480
481 assert(B->succ_size() == 1 &&
482 "Blocks with no terminator should have at most 1 successor.");
483
484 BlockEdge BE(B, *(B->succ_begin()), Pred->getStackFrame());
485 if (ExplodedNode *N = makeNode(Loc: BE, State: Pred->State, Pred))
486 WList->enqueue(N);
487}
488
489void CoreEngine::HandleCallEnter(const CallEnter &CE, ExplodedNode *Pred) {
490 ExprEng.setCurrStackFrameAndBlock(SF: Pred->getStackFrame(), B: CE.getEntry());
491 ExprEng.processCallEnter(CE, Pred);
492}
493
494void CoreEngine::HandleBranch(const Stmt *Cond, const Stmt *Term,
495 const CFGBlock * B, ExplodedNode *Pred) {
496 assert(B->succ_size() == 2);
497 ExplodedNodeSet Dst;
498 ExprEng.processBranch(Condition: Cond, Pred, Dst, DstT: *(B->succ_begin()),
499 DstF: *(B->succ_begin() + 1),
500 IterationsCompletedInLoop: getCompletedIterationCount(B, Pred));
501 // Enqueue the new frontier onto the worklist.
502 enqueue(Set&: Dst);
503}
504
505void CoreEngine::HandleCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE,
506 const CFGBlock *B,
507 ExplodedNode *Pred) {
508 assert(B->succ_size() == 2);
509 ExplodedNodeSet Dst;
510 ExprEng.processCleanupTemporaryBranch(BTE, Pred, Dst, DstT: *(B->succ_begin()),
511 DstF: *(B->succ_begin() + 1));
512 // Enqueue the new frontier onto the worklist.
513 enqueue(Set&: Dst);
514}
515
516void CoreEngine::HandleStaticInit(const DeclStmt *DS, const CFGBlock *B,
517 ExplodedNode *Pred) {
518 assert(B->succ_size() == 2);
519 ExplodedNodeSet Dst;
520 ExprEng.processStaticInitializer(DS, Pred, Dst, DstT: *(B->succ_begin()),
521 DstF: *(B->succ_begin() + 1));
522 // Enqueue the new frontier onto the worklist.
523 enqueue(Set&: Dst);
524}
525
526void CoreEngine::HandlePostStmt(const CFGBlock *B, unsigned StmtIdx,
527 ExplodedNode *Pred) {
528 assert(B);
529 assert(!B->empty());
530
531 // We no-op by skipping any FullExprCleanup
532 while (StmtIdx < B->size() &&
533 (*B)[StmtIdx].getKind() == CFGElement::FullExprCleanup) {
534 StmtIdx++;
535 }
536
537 if (StmtIdx == B->size())
538 HandleBlockExit(B, Pred);
539 else {
540 ExprEng.setCurrStackFrameAndBlock(SF: Pred->getStackFrame(), B);
541 ExprEng.processCFGElement(E: (*B)[StmtIdx], Pred, StmtIdx);
542 }
543}
544
545void CoreEngine::HandleVirtualBaseBranch(const CFGBlock *B,
546 ExplodedNode *Pred) {
547 const StackFrame *SF = Pred->getStackFrame();
548 if (const auto *CallerCtor =
549 dyn_cast_or_null<CXXConstructExpr>(Val: SF->getCallSite())) {
550 switch (CallerCtor->getConstructionKind()) {
551 case CXXConstructionKind::NonVirtualBase:
552 case CXXConstructionKind::VirtualBase: {
553 BlockEdge Loc(B, *B->succ_begin(), SF);
554 HandleBlockEdge(L: Loc, Pred);
555 return;
556 }
557 default:
558 break;
559 }
560 }
561
562 // We either don't see a parent stack frame because we're in the top frame,
563 // or the parent stack frame doesn't initialize our virtual bases.
564 BlockEdge Loc(B, *(B->succ_begin() + 1), SF);
565 HandleBlockEdge(L: Loc, Pred);
566}
567
568ExplodedNode *CoreEngine::makeNode(const ProgramPoint &Loc,
569 ProgramStateRef State, ExplodedNode *Pred,
570 bool MarkAsSink) const {
571 MarkAsSink = MarkAsSink || State->isPosteriorlyOverconstrained();
572
573 bool IsNew;
574 ExplodedNode *N = G.getNode(L: Loc, State, IsSink: MarkAsSink, IsNew: &IsNew);
575 N->addPredecessor(V: Pred, G);
576
577 return IsNew ? N : nullptr;
578}
579
580void CoreEngine::enqueueStmtNode(ExplodedNode *N,
581 const CFGBlock *Block, unsigned Idx) {
582 assert(Block);
583 assert(!N->isSink());
584
585 // Check if this node entered a callee.
586 if (N->getLocation().getAs<CallEnter>()) {
587 // Still use the index of the CallExpr. It's needed to create the callee
588 // StackFrame.
589 WList->enqueue(N, B: Block, idx: Idx);
590 return;
591 }
592
593 // Do not create extra nodes. Move to the next CFG element.
594 if (N->getLocation().getAs<PostInitializer>() ||
595 N->getLocation().getAs<PostImplicitCall>() ||
596 N->getLocation().getAs<LoopExit>() ||
597 N->getLocation().getAs<LifetimeEnd>()) {
598 WList->enqueue(N, B: Block, idx: Idx + 1);
599 return;
600 }
601
602 if (N->getLocation().getAs<EpsilonPoint>()) {
603 WList->enqueue(N, B: Block, idx: Idx);
604 return;
605 }
606
607 if ((*Block)[Idx].getKind() == CFGElement::NewAllocator) {
608 WList->enqueue(N, B: Block, idx: Idx+1);
609 return;
610 }
611
612 // At this point, we know we're processing a normal statement.
613 CFGStmt CS = (*Block)[Idx].castAs<CFGStmt>();
614 PostStmt Loc(CS.getStmt(), N->getStackFrame());
615
616 if (Loc == N->getLocation().withTag(tag: nullptr)) {
617 // Note: 'N' should be a fresh node because otherwise it shouldn't be
618 // a member of Deferred.
619 WList->enqueue(N, B: Block, idx: Idx+1);
620 return;
621 }
622
623 ExplodedNode *Succ = makeNode(Loc, State: N->getState(), Pred: N);
624
625 if (Succ)
626 WList->enqueue(N: Succ, B: Block, idx: Idx+1);
627}
628
629std::optional<unsigned>
630CoreEngine::getCompletedIterationCount(const CFGBlock *B,
631 ExplodedNode *Pred) const {
632 const StackFrame *SF = Pred->getStackFrame();
633 BlockCounter Counter = WList->getBlockCounter();
634 unsigned BlockCount = Counter.getNumVisited(CallSite: SF, BlockID: B->getBlockID());
635
636 const Stmt *Term = B->getTerminatorStmt();
637 if (isa<ForStmt, WhileStmt, CXXForRangeStmt>(Val: Term)) {
638 assert(BlockCount >= 1 &&
639 "Block count of currently analyzed block must be >= 1");
640 return BlockCount - 1;
641 }
642 if (isa<DoStmt>(Val: Term)) {
643 // In a do-while loop one iteration happens before the first evaluation of
644 // the loop condition, so we don't subtract one.
645 return BlockCount;
646 }
647 // ObjCForCollectionStmt is skipped intentionally because the current
648 // application of the iteration counts is not relevant for it.
649 return std::nullopt;
650}
651
652void CoreEngine::enqueue(ExplodedNodeSet &Set) {
653 for (const auto I : Set)
654 WList->enqueue(N: I);
655}
656
657void CoreEngine::enqueueStmtNodes(ExplodedNodeSet &Set, const CFGBlock *Block,
658 unsigned Idx) {
659 for (const auto I : Set)
660 enqueueStmtNode(N: I, Block, Idx);
661}
662
663void CoreEngine::enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS) {
664 for (ExplodedNode *Node : Set) {
665 const StackFrame *SF = Node->getStackFrame();
666
667 // If we are in an inlined call, generate CallExitBegin node.
668 if (SF->getParent()) {
669 // Use the callee stack frame.
670 CallExitBegin Loc(SF, RS);
671 if (ExplodedNode *Succ = makeNode(Loc, State: Node->getState(), Pred: Node))
672 WList->enqueue(N: Succ);
673 } else {
674 // TODO: We should run remove dead bindings here.
675 G.addEndOfPath(V: Node);
676 NumPathsExplored++;
677 }
678 }
679}
680
681ExplodedNode *NodeBuilder::generateNode(const ProgramPoint &Loc,
682 ProgramStateRef State,
683 ExplodedNode *FromN, bool MarkAsSink) {
684 HasGeneratedNodes = true;
685 Frontier.erase(N: FromN);
686 ExplodedNode *N = C.getEngine().makeNode(Loc, State, Pred: FromN, MarkAsSink);
687
688 Frontier.insert(N);
689
690 return N;
691}
692