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 "PrettyStackTraceLocationContext.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 LocationContext *L, 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 = &(L->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(),
101 D: L->getDecl(),
102 TotalIDs: L->getCFG()->getNumBlockIDs());
103
104 // Get the solitary successor.
105 const CFGBlock *Succ = *(Entry->succ_begin());
106
107 // Construct an edge representing the
108 // starting location in the function.
109 BlockEdge StartLoc(Entry, Succ, L);
110
111 // Set the current block counter to being empty.
112 setBlockCounter(BCounterFactory.GetEmptyCounter());
113
114 if (!InitState)
115 InitState = ExprEng.getInitialState(InitLoc: L);
116
117 bool IsNew;
118 ExplodedNode *Node = G.getNode(L: StartLoc, State: InitState, IsSink: false, IsNew: &IsNew);
119 assert(IsNew);
120 G.designateAsRoot(V: Node);
121
122 NodeBuilderContext BuilderCtx(*this, StartLoc.getDst(), Node);
123 ExplodedNodeSet DstBegin;
124 ExprEng.processBeginOfFunction(BC&: BuilderCtx, 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->getLocationContext()
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 PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
219 // Dispatch on the location type.
220 switch (Loc.getKind()) {
221 case ProgramPoint::BlockEdgeKind:
222 HandleBlockEdge(E: Loc.castAs<BlockEdge>(), Pred);
223 break;
224
225 case ProgramPoint::BlockEntranceKind:
226 HandleBlockEntrance(E: Loc.castAs<BlockEntrance>(), Pred);
227 break;
228
229 case ProgramPoint::BlockExitKind:
230 assert(false && "BlockExit location never occur in forward analysis.");
231 break;
232
233 case ProgramPoint::CallEnterKind:
234 HandleCallEnter(CE: Loc.castAs<CallEnter>(), Pred);
235 break;
236
237 case ProgramPoint::CallExitBeginKind:
238 ExprEng.processCallExit(Pred);
239 break;
240
241 case ProgramPoint::EpsilonKind: {
242 assert(Pred->hasSinglePred() &&
243 "Assume epsilon has exactly one predecessor by construction");
244 ExplodedNode *PNode = Pred->getFirstPred();
245 dispatchWorkItem(Pred, Loc: PNode->getLocation(), WU);
246 break;
247 }
248 default:
249 assert(Loc.getAs<PostStmt>() ||
250 Loc.getAs<PostInitializer>() ||
251 Loc.getAs<PostImplicitCall>() ||
252 Loc.getAs<CallExitEnd>() ||
253 Loc.getAs<LoopExit>() ||
254 Loc.getAs<PostAllocatorCall>());
255 HandlePostStmt(B: WU.getBlock(), StmtIdx: WU.getIndex(), Pred);
256 break;
257 }
258}
259
260void CoreEngine::HandleBlockEdge(const BlockEdge &L, ExplodedNode *Pred) {
261 const CFGBlock *Blk = L.getDst();
262 NodeBuilderContext BuilderCtx(*this, Blk, Pred);
263
264 // Mark this block as visited.
265 const LocationContext *LC = Pred->getLocationContext();
266 FunctionSummaries->markVisitedBasicBlock(ID: Blk->getBlockID(),
267 D: LC->getDecl(),
268 TotalIDs: LC->getCFG()->getNumBlockIDs());
269
270 // Display a prunable path note to the user if it's a virtual bases branch
271 // and we're taking the path that skips virtual base constructors.
272 if (L.getSrc()->getTerminator().isVirtualBaseBranch() &&
273 L.getDst() == *L.getSrc()->succ_begin()) {
274 ProgramPoint P = L.withTag(tag: getDataTags().make<NoteTag>(
275 ConstructorArgs: [](BugReporterContext &, PathSensitiveBugReport &) -> std::string {
276 // TODO: Just call out the name of the most derived class
277 // when we know it.
278 return "Virtual base initialization skipped because "
279 "it has already been handled by the most derived class";
280 },
281 /*IsPrunable=*/ConstructorArgs: true));
282 // Perform the transition.
283 ExplodedNodeSet Dst;
284 NodeBuilder Bldr(Pred, Dst, BuilderCtx);
285 Pred = Bldr.generateNode(PP: P, State: Pred->getState(), Pred);
286 if (!Pred)
287 return;
288 }
289
290 // Check if we are entering the EXIT block.
291 if (Blk == &(L.getLocationContext()->getCFG()->getExit())) {
292 assert(L.getLocationContext()->getCFG()->getExit().empty() &&
293 "EXIT block cannot contain Stmts.");
294
295 // Get return statement..
296 const ReturnStmt *RS = nullptr;
297 if (!L.getSrc()->empty()) {
298 CFGElement LastElement = L.getSrc()->back();
299 if (std::optional<CFGStmt> LastStmt = LastElement.getAs<CFGStmt>()) {
300 RS = dyn_cast<ReturnStmt>(Val: LastStmt->getStmt());
301 } else if (std::optional<CFGAutomaticObjDtor> AutoDtor =
302 LastElement.getAs<CFGAutomaticObjDtor>()) {
303 RS = dyn_cast<ReturnStmt>(Val: AutoDtor->getTriggerStmt());
304 }
305 }
306
307 ExplodedNodeSet CheckerNodes;
308 BlockEntrance BE(L.getSrc(), L.getDst(), Pred->getLocationContext());
309 ExprEng.runCheckersForBlockEntrance(BldCtx: BuilderCtx, Entrance: BE, Pred, Dst&: CheckerNodes);
310
311 // Process the final state transition.
312 for (ExplodedNode *P : CheckerNodes) {
313 ExprEng.processEndOfFunction(BC&: BuilderCtx, Pred: P, RS);
314 }
315
316 // This path is done. Don't enqueue any more nodes.
317 return;
318 }
319
320 // Call into the ExprEngine to process entering the CFGBlock.
321 BlockEntrance BE(L.getSrc(), L.getDst(), Pred->getLocationContext());
322 ExplodedNodeSet DstNodes;
323 NodeBuilderWithSinks NodeBuilder(Pred, DstNodes, BuilderCtx, BE);
324 ExprEng.processCFGBlockEntrance(L, nodeBuilder&: NodeBuilder, Pred);
325
326 // Auto-generate a node.
327 if (!NodeBuilder.hasGeneratedNodes()) {
328 NodeBuilder.generateNode(State: Pred->State, Pred);
329 }
330
331 ExplodedNodeSet CheckerNodes;
332 for (auto *N : DstNodes) {
333 ExprEng.runCheckersForBlockEntrance(BldCtx: BuilderCtx, Entrance: BE, Pred: N, Dst&: CheckerNodes);
334 }
335
336 // Enqueue nodes onto the worklist.
337 enqueue(Set&: CheckerNodes);
338}
339
340void CoreEngine::HandleBlockEntrance(const BlockEntrance &L,
341 ExplodedNode *Pred) {
342 // Increment the block counter.
343 const LocationContext *LC = Pred->getLocationContext();
344 unsigned BlockId = L.getBlock()->getBlockID();
345 BlockCounter Counter = WList->getBlockCounter();
346 Counter = BCounterFactory.IncrementCount(BC: Counter, CallSite: LC->getStackFrame(),
347 BlockID: BlockId);
348 setBlockCounter(Counter);
349
350 // Process the entrance of the block.
351 if (std::optional<CFGElement> E = L.getFirstElement()) {
352 NodeBuilderContext Ctx(*this, L.getBlock(), Pred);
353 ExprEng.processCFGElement(E: *E, Pred, StmtIdx: 0, Ctx: &Ctx);
354 } else
355 HandleBlockExit(B: L.getBlock(), Pred);
356}
357
358void CoreEngine::HandleBlockExit(const CFGBlock * B, ExplodedNode *Pred) {
359 if (const Stmt *Term = B->getTerminatorStmt()) {
360 switch (Term->getStmtClass()) {
361 default:
362 llvm_unreachable("Analysis for this terminator not implemented.");
363
364 case Stmt::CXXBindTemporaryExprClass:
365 HandleCleanupTemporaryBranch(
366 BTE: cast<CXXBindTemporaryExpr>(Val: Term), B, Pred);
367 return;
368
369 // Model static initializers.
370 case Stmt::DeclStmtClass:
371 HandleStaticInit(DS: cast<DeclStmt>(Val: Term), B, Pred);
372 return;
373
374 case Stmt::BinaryOperatorClass: // '&&' and '||'
375 HandleBranch(Cond: cast<BinaryOperator>(Val: Term)->getLHS(), Term, B, Pred);
376 return;
377
378 case Stmt::BinaryConditionalOperatorClass:
379 case Stmt::ConditionalOperatorClass:
380 HandleBranch(Cond: cast<AbstractConditionalOperator>(Val: Term)->getCond(),
381 Term, B, Pred);
382 return;
383
384 // FIXME: Use constant-folding in CFG construction to simplify this
385 // case.
386
387 case Stmt::ChooseExprClass:
388 HandleBranch(Cond: cast<ChooseExpr>(Val: Term)->getCond(), Term, B, Pred);
389 return;
390
391 case Stmt::CXXTryStmtClass:
392 // Generate a node for each of the successors.
393 // Our logic for EH analysis can certainly be improved.
394 for (CFGBlock::const_succ_iterator it = B->succ_begin(),
395 et = B->succ_end(); it != et; ++it) {
396 if (const CFGBlock *succ = *it) {
397 generateNode(Loc: BlockEdge(B, succ, Pred->getLocationContext()),
398 State: Pred->State, Pred);
399 }
400 }
401 return;
402
403 case Stmt::DoStmtClass:
404 HandleBranch(Cond: cast<DoStmt>(Val: Term)->getCond(), Term, B, Pred);
405 return;
406
407 case Stmt::CXXForRangeStmtClass:
408 HandleBranch(Cond: cast<CXXForRangeStmt>(Val: Term)->getCond(), Term, B, Pred);
409 return;
410
411 case Stmt::ForStmtClass:
412 HandleBranch(Cond: cast<ForStmt>(Val: Term)->getCond(), Term, B, Pred);
413 return;
414
415 case Stmt::SEHLeaveStmtClass:
416 case Stmt::ContinueStmtClass:
417 case Stmt::BreakStmtClass:
418 case Stmt::GotoStmtClass:
419 break;
420
421 case Stmt::IfStmtClass:
422 HandleBranch(Cond: cast<IfStmt>(Val: Term)->getCond(), Term, B, Pred);
423 return;
424
425 case Stmt::IndirectGotoStmtClass: {
426 // Only 1 successor: the indirect goto dispatch block.
427 assert(B->succ_size() == 1);
428
429 IndirectGotoNodeBuilder
430 builder(Pred, B, cast<IndirectGotoStmt>(Val: Term)->getTarget(),
431 *(B->succ_begin()), this);
432
433 ExprEng.processIndirectGoto(builder);
434 return;
435 }
436
437 case Stmt::ObjCForCollectionStmtClass:
438 // In the case of ObjCForCollectionStmt, it appears twice in a CFG:
439 //
440 // (1) inside a basic block, which represents the binding of the
441 // 'element' variable to a value.
442 // (2) in a terminator, which represents the branch.
443 //
444 // For (1), ExprEngine will bind a value (i.e., 0 or 1) indicating
445 // whether or not collection contains any more elements. We cannot
446 // just test to see if the element is nil because a container can
447 // contain nil elements.
448 HandleBranch(Cond: Term, Term, B, Pred);
449 return;
450
451 case Stmt::SwitchStmtClass: {
452 ExprEng.processSwitch(Switch: cast<SwitchStmt>(Val: Term), CoreEng&: *this, B, Pred);
453 return;
454 }
455
456 case Stmt::WhileStmtClass:
457 HandleBranch(Cond: cast<WhileStmt>(Val: Term)->getCond(), Term, B, Pred);
458 return;
459
460 case Stmt::GCCAsmStmtClass:
461 assert(cast<GCCAsmStmt>(Term)->isAsmGoto() && "Encountered GCCAsmStmt without labels");
462 // TODO: Handle jumping to labels
463 return;
464 }
465 }
466
467 if (B->getTerminator().isVirtualBaseBranch()) {
468 HandleVirtualBaseBranch(B, Pred);
469 return;
470 }
471
472 assert(B->succ_size() == 1 &&
473 "Blocks with no terminator should have at most 1 successor.");
474
475 generateNode(Loc: BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()),
476 State: Pred->State, Pred);
477}
478
479void CoreEngine::HandleCallEnter(const CallEnter &CE, ExplodedNode *Pred) {
480 NodeBuilderContext BuilderCtx(*this, CE.getEntry(), Pred);
481 ExprEng.processCallEnter(BC&: BuilderCtx, CE, Pred);
482}
483
484void CoreEngine::HandleBranch(const Stmt *Cond, const Stmt *Term,
485 const CFGBlock * B, ExplodedNode *Pred) {
486 assert(B->succ_size() == 2);
487 NodeBuilderContext Ctx(*this, B, Pred);
488 ExplodedNodeSet Dst;
489 ExprEng.processBranch(Condition: Cond, BuilderCtx&: Ctx, Pred, Dst, DstT: *(B->succ_begin()),
490 DstF: *(B->succ_begin() + 1),
491 IterationsCompletedInLoop: getCompletedIterationCount(B, Pred));
492 // Enqueue the new frontier onto the worklist.
493 enqueue(Set&: Dst);
494}
495
496void CoreEngine::HandleCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE,
497 const CFGBlock *B,
498 ExplodedNode *Pred) {
499 assert(B->succ_size() == 2);
500 NodeBuilderContext Ctx(*this, B, Pred);
501 ExplodedNodeSet Dst;
502 ExprEng.processCleanupTemporaryBranch(BTE, BldCtx&: Ctx, Pred, Dst, DstT: *(B->succ_begin()),
503 DstF: *(B->succ_begin() + 1));
504 // Enqueue the new frontier onto the worklist.
505 enqueue(Set&: Dst);
506}
507
508void CoreEngine::HandleStaticInit(const DeclStmt *DS, const CFGBlock *B,
509 ExplodedNode *Pred) {
510 assert(B->succ_size() == 2);
511 NodeBuilderContext Ctx(*this, B, Pred);
512 ExplodedNodeSet Dst;
513 ExprEng.processStaticInitializer(DS, BuilderCtx&: Ctx, Pred, Dst,
514 DstT: *(B->succ_begin()), DstF: *(B->succ_begin()+1));
515 // Enqueue the new frontier onto the worklist.
516 enqueue(Set&: Dst);
517}
518
519void CoreEngine::HandlePostStmt(const CFGBlock *B, unsigned StmtIdx,
520 ExplodedNode *Pred) {
521 assert(B);
522 assert(!B->empty());
523
524 if (StmtIdx == B->size())
525 HandleBlockExit(B, Pred);
526 else {
527 NodeBuilderContext Ctx(*this, B, Pred);
528 ExprEng.processCFGElement(E: (*B)[StmtIdx], Pred, StmtIdx, Ctx: &Ctx);
529 }
530}
531
532void CoreEngine::HandleVirtualBaseBranch(const CFGBlock *B,
533 ExplodedNode *Pred) {
534 const LocationContext *LCtx = Pred->getLocationContext();
535 if (const auto *CallerCtor = dyn_cast_or_null<CXXConstructExpr>(
536 Val: LCtx->getStackFrame()->getCallSite())) {
537 switch (CallerCtor->getConstructionKind()) {
538 case CXXConstructionKind::NonVirtualBase:
539 case CXXConstructionKind::VirtualBase: {
540 BlockEdge Loc(B, *B->succ_begin(), LCtx);
541 HandleBlockEdge(L: Loc, Pred);
542 return;
543 }
544 default:
545 break;
546 }
547 }
548
549 // We either don't see a parent stack frame because we're in the top frame,
550 // or the parent stack frame doesn't initialize our virtual bases.
551 BlockEdge Loc(B, *(B->succ_begin() + 1), LCtx);
552 HandleBlockEdge(L: Loc, Pred);
553}
554
555/// generateNode - Utility method to generate nodes, hook up successors,
556/// and add nodes to the worklist.
557void CoreEngine::generateNode(const ProgramPoint &Loc,
558 ProgramStateRef State,
559 ExplodedNode *Pred) {
560 assert(Pred);
561 bool IsNew;
562 ExplodedNode *Node = G.getNode(L: Loc, State, IsSink: false, IsNew: &IsNew);
563
564 Node->addPredecessor(V: Pred, G); // Link 'Node' with its predecessor.
565
566 // Only add 'Node' to the worklist if it was freshly generated.
567 if (IsNew) WList->enqueue(N: Node);
568}
569
570void CoreEngine::enqueueStmtNode(ExplodedNode *N,
571 const CFGBlock *Block, unsigned Idx) {
572 assert(Block);
573 assert(!N->isSink());
574
575 // Check if this node entered a callee.
576 if (N->getLocation().getAs<CallEnter>()) {
577 // Still use the index of the CallExpr. It's needed to create the callee
578 // StackFrameContext.
579 WList->enqueue(N, B: Block, idx: Idx);
580 return;
581 }
582
583 // Do not create extra nodes. Move to the next CFG element.
584 if (N->getLocation().getAs<PostInitializer>() ||
585 N->getLocation().getAs<PostImplicitCall>()||
586 N->getLocation().getAs<LoopExit>()) {
587 WList->enqueue(N, B: Block, idx: Idx+1);
588 return;
589 }
590
591 if (N->getLocation().getAs<EpsilonPoint>()) {
592 WList->enqueue(N, B: Block, idx: Idx);
593 return;
594 }
595
596 if ((*Block)[Idx].getKind() == CFGElement::NewAllocator) {
597 WList->enqueue(N, B: Block, idx: Idx+1);
598 return;
599 }
600
601 // At this point, we know we're processing a normal statement.
602 CFGStmt CS = (*Block)[Idx].castAs<CFGStmt>();
603 PostStmt Loc(CS.getStmt(), N->getLocationContext());
604
605 if (Loc == N->getLocation().withTag(tag: nullptr)) {
606 // Note: 'N' should be a fresh node because otherwise it shouldn't be
607 // a member of Deferred.
608 WList->enqueue(N, B: Block, idx: Idx+1);
609 return;
610 }
611
612 bool IsNew;
613 ExplodedNode *Succ = G.getNode(L: Loc, State: N->getState(), IsSink: false, IsNew: &IsNew);
614 Succ->addPredecessor(V: N, G);
615
616 if (IsNew)
617 WList->enqueue(N: Succ, B: Block, idx: Idx+1);
618}
619
620ExplodedNode *CoreEngine::generateCallExitBeginNode(ExplodedNode *N,
621 const ReturnStmt *RS) {
622 // Create a CallExitBegin node and enqueue it.
623 const auto *LocCtx = cast<StackFrameContext>(Val: N->getLocationContext());
624
625 // Use the callee location context.
626 CallExitBegin Loc(LocCtx, RS);
627
628 bool isNew;
629 ExplodedNode *Node = G.getNode(L: Loc, State: N->getState(), IsSink: false, IsNew: &isNew);
630 Node->addPredecessor(V: N, G);
631 return isNew ? Node : nullptr;
632}
633
634std::optional<unsigned>
635CoreEngine::getCompletedIterationCount(const CFGBlock *B,
636 ExplodedNode *Pred) const {
637 const LocationContext *LC = Pred->getLocationContext();
638 BlockCounter Counter = WList->getBlockCounter();
639 unsigned BlockCount =
640 Counter.getNumVisited(CallSite: LC->getStackFrame(), BlockID: B->getBlockID());
641
642 const Stmt *Term = B->getTerminatorStmt();
643 if (isa<ForStmt, WhileStmt, CXXForRangeStmt>(Val: Term)) {
644 assert(BlockCount >= 1 &&
645 "Block count of currently analyzed block must be >= 1");
646 return BlockCount - 1;
647 }
648 if (isa<DoStmt>(Val: Term)) {
649 // In a do-while loop one iteration happens before the first evaluation of
650 // the loop condition, so we don't subtract one.
651 return BlockCount;
652 }
653 // ObjCForCollectionStmt is skipped intentionally because the current
654 // application of the iteration counts is not relevant for it.
655 return std::nullopt;
656}
657
658void CoreEngine::enqueue(ExplodedNodeSet &Set) {
659 for (const auto I : Set)
660 WList->enqueue(N: I);
661}
662
663void CoreEngine::enqueue(ExplodedNodeSet &Set,
664 const CFGBlock *Block, unsigned Idx) {
665 for (const auto I : Set)
666 enqueueStmtNode(N: I, Block, Idx);
667}
668
669void CoreEngine::enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS) {
670 for (auto *I : Set) {
671 // If we are in an inlined call, generate CallExitBegin node.
672 if (I->getLocationContext()->getParent()) {
673 I = generateCallExitBeginNode(N: I, RS);
674 if (I)
675 WList->enqueue(N: I);
676 } else {
677 // TODO: We should run remove dead bindings here.
678 G.addEndOfPath(V: I);
679 NumPathsExplored++;
680 }
681 }
682}
683
684void NodeBuilder::anchor() {}
685
686ExplodedNode* NodeBuilder::generateNodeImpl(const ProgramPoint &Loc,
687 ProgramStateRef State,
688 ExplodedNode *FromN,
689 bool MarkAsSink) {
690 HasGeneratedNodes = true;
691 bool IsNew;
692 ExplodedNode *N = C.getEngine().G.getNode(L: Loc, State, IsSink: MarkAsSink, IsNew: &IsNew);
693 N->addPredecessor(V: FromN, G&: C.getEngine().G);
694 Frontier.erase(N: FromN);
695
696 if (!IsNew)
697 return nullptr;
698
699 if (!MarkAsSink)
700 Frontier.Add(N);
701
702 return N;
703}
704
705void NodeBuilderWithSinks::anchor() {}
706
707StmtNodeBuilder::~StmtNodeBuilder() {
708 if (EnclosingBldr)
709 for (const auto I : Frontier)
710 EnclosingBldr->addNodes(N: I);
711}
712
713void BranchNodeBuilder::anchor() {}
714
715ExplodedNode *BranchNodeBuilder::generateNode(ProgramStateRef State,
716 bool Branch,
717 ExplodedNode *NodePred) {
718 const CFGBlock *Dst = Branch ? DstT : DstF;
719
720 if (!Dst)
721 return nullptr;
722
723 ProgramPoint Loc =
724 BlockEdge(C.getBlock(), Dst, NodePred->getLocationContext());
725 ExplodedNode *Succ = generateNodeImpl(Loc, State, FromN: NodePred);
726 return Succ;
727}
728
729ExplodedNode*
730IndirectGotoNodeBuilder::generateNode(const iterator &I,
731 ProgramStateRef St,
732 bool IsSink) {
733 bool IsNew;
734 ExplodedNode *Succ =
735 Eng.G.getNode(L: BlockEdge(Src, I.getBlock(), Pred->getLocationContext()),
736 State: St, IsSink, IsNew: &IsNew);
737 Succ->addPredecessor(V: Pred, G&: Eng.G);
738
739 if (!IsNew)
740 return nullptr;
741
742 if (!IsSink)
743 Eng.WList->enqueue(N: Succ);
744
745 return Succ;
746}
747
748ExplodedNode *SwitchNodeBuilder::generateCaseStmtNode(const CFGBlock *Block,
749 ProgramStateRef St) {
750 bool IsNew;
751 ExplodedNode *Succ = Eng.G.getNode(
752 L: BlockEdge(Src, Block, Pred->getLocationContext()), State: St, IsSink: false, IsNew: &IsNew);
753 Succ->addPredecessor(V: Pred, G&: Eng.G);
754 if (!IsNew)
755 return nullptr;
756
757 Eng.WList->enqueue(N: Succ);
758 return Succ;
759}
760
761ExplodedNode*
762SwitchNodeBuilder::generateDefaultCaseNode(ProgramStateRef St,
763 bool IsSink) {
764 // Get the block for the default case.
765 assert(Src->succ_rbegin() != Src->succ_rend());
766 CFGBlock *DefaultBlock = *Src->succ_rbegin();
767
768 // Basic correctness check for default blocks that are unreachable and not
769 // caught by earlier stages.
770 if (!DefaultBlock)
771 return nullptr;
772
773 bool IsNew;
774 ExplodedNode *Succ =
775 Eng.G.getNode(L: BlockEdge(Src, DefaultBlock, Pred->getLocationContext()),
776 State: St, IsSink, IsNew: &IsNew);
777 Succ->addPredecessor(V: Pred, G&: Eng.G);
778
779 if (!IsNew)
780 return nullptr;
781
782 if (!IsSink)
783 Eng.WList->enqueue(N: Succ);
784
785 return Succ;
786}
787