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 SwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Val: Term)->getCond(),
453 this);
454
455 ExprEng.processSwitch(builder);
456 return;
457 }
458
459 case Stmt::WhileStmtClass:
460 HandleBranch(Cond: cast<WhileStmt>(Val: Term)->getCond(), Term, B, Pred);
461 return;
462
463 case Stmt::GCCAsmStmtClass:
464 assert(cast<GCCAsmStmt>(Term)->isAsmGoto() && "Encountered GCCAsmStmt without labels");
465 // TODO: Handle jumping to labels
466 return;
467 }
468 }
469
470 if (B->getTerminator().isVirtualBaseBranch()) {
471 HandleVirtualBaseBranch(B, Pred);
472 return;
473 }
474
475 assert(B->succ_size() == 1 &&
476 "Blocks with no terminator should have at most 1 successor.");
477
478 generateNode(Loc: BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()),
479 State: Pred->State, Pred);
480}
481
482void CoreEngine::HandleCallEnter(const CallEnter &CE, ExplodedNode *Pred) {
483 NodeBuilderContext BuilderCtx(*this, CE.getEntry(), Pred);
484 ExprEng.processCallEnter(BC&: BuilderCtx, CE, Pred);
485}
486
487void CoreEngine::HandleBranch(const Stmt *Cond, const Stmt *Term,
488 const CFGBlock * B, ExplodedNode *Pred) {
489 assert(B->succ_size() == 2);
490 NodeBuilderContext Ctx(*this, B, Pred);
491 ExplodedNodeSet Dst;
492 ExprEng.processBranch(Condition: Cond, BuilderCtx&: Ctx, Pred, Dst, DstT: *(B->succ_begin()),
493 DstF: *(B->succ_begin() + 1),
494 IterationsCompletedInLoop: getCompletedIterationCount(B, Pred));
495 // Enqueue the new frontier onto the worklist.
496 enqueue(Set&: Dst);
497}
498
499void CoreEngine::HandleCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE,
500 const CFGBlock *B,
501 ExplodedNode *Pred) {
502 assert(B->succ_size() == 2);
503 NodeBuilderContext Ctx(*this, B, Pred);
504 ExplodedNodeSet Dst;
505 ExprEng.processCleanupTemporaryBranch(BTE, BldCtx&: Ctx, Pred, Dst, DstT: *(B->succ_begin()),
506 DstF: *(B->succ_begin() + 1));
507 // Enqueue the new frontier onto the worklist.
508 enqueue(Set&: Dst);
509}
510
511void CoreEngine::HandleStaticInit(const DeclStmt *DS, const CFGBlock *B,
512 ExplodedNode *Pred) {
513 assert(B->succ_size() == 2);
514 NodeBuilderContext Ctx(*this, B, Pred);
515 ExplodedNodeSet Dst;
516 ExprEng.processStaticInitializer(DS, BuilderCtx&: Ctx, Pred, Dst,
517 DstT: *(B->succ_begin()), DstF: *(B->succ_begin()+1));
518 // Enqueue the new frontier onto the worklist.
519 enqueue(Set&: Dst);
520}
521
522void CoreEngine::HandlePostStmt(const CFGBlock *B, unsigned StmtIdx,
523 ExplodedNode *Pred) {
524 assert(B);
525 assert(!B->empty());
526
527 if (StmtIdx == B->size())
528 HandleBlockExit(B, Pred);
529 else {
530 NodeBuilderContext Ctx(*this, B, Pred);
531 ExprEng.processCFGElement(E: (*B)[StmtIdx], Pred, StmtIdx, Ctx: &Ctx);
532 }
533}
534
535void CoreEngine::HandleVirtualBaseBranch(const CFGBlock *B,
536 ExplodedNode *Pred) {
537 const LocationContext *LCtx = Pred->getLocationContext();
538 if (const auto *CallerCtor = dyn_cast_or_null<CXXConstructExpr>(
539 Val: LCtx->getStackFrame()->getCallSite())) {
540 switch (CallerCtor->getConstructionKind()) {
541 case CXXConstructionKind::NonVirtualBase:
542 case CXXConstructionKind::VirtualBase: {
543 BlockEdge Loc(B, *B->succ_begin(), LCtx);
544 HandleBlockEdge(L: Loc, Pred);
545 return;
546 }
547 default:
548 break;
549 }
550 }
551
552 // We either don't see a parent stack frame because we're in the top frame,
553 // or the parent stack frame doesn't initialize our virtual bases.
554 BlockEdge Loc(B, *(B->succ_begin() + 1), LCtx);
555 HandleBlockEdge(L: Loc, Pred);
556}
557
558/// generateNode - Utility method to generate nodes, hook up successors,
559/// and add nodes to the worklist.
560void CoreEngine::generateNode(const ProgramPoint &Loc,
561 ProgramStateRef State,
562 ExplodedNode *Pred) {
563 assert(Pred);
564 bool IsNew;
565 ExplodedNode *Node = G.getNode(L: Loc, State, IsSink: false, IsNew: &IsNew);
566
567 Node->addPredecessor(V: Pred, G); // Link 'Node' with its predecessor.
568
569 // Only add 'Node' to the worklist if it was freshly generated.
570 if (IsNew) WList->enqueue(N: Node);
571}
572
573void CoreEngine::enqueueStmtNode(ExplodedNode *N,
574 const CFGBlock *Block, unsigned Idx) {
575 assert(Block);
576 assert(!N->isSink());
577
578 // Check if this node entered a callee.
579 if (N->getLocation().getAs<CallEnter>()) {
580 // Still use the index of the CallExpr. It's needed to create the callee
581 // StackFrameContext.
582 WList->enqueue(N, B: Block, idx: Idx);
583 return;
584 }
585
586 // Do not create extra nodes. Move to the next CFG element.
587 if (N->getLocation().getAs<PostInitializer>() ||
588 N->getLocation().getAs<PostImplicitCall>()||
589 N->getLocation().getAs<LoopExit>()) {
590 WList->enqueue(N, B: Block, idx: Idx+1);
591 return;
592 }
593
594 if (N->getLocation().getAs<EpsilonPoint>()) {
595 WList->enqueue(N, B: Block, idx: Idx);
596 return;
597 }
598
599 if ((*Block)[Idx].getKind() == CFGElement::NewAllocator) {
600 WList->enqueue(N, B: Block, idx: Idx+1);
601 return;
602 }
603
604 // At this point, we know we're processing a normal statement.
605 CFGStmt CS = (*Block)[Idx].castAs<CFGStmt>();
606 PostStmt Loc(CS.getStmt(), N->getLocationContext());
607
608 if (Loc == N->getLocation().withTag(tag: nullptr)) {
609 // Note: 'N' should be a fresh node because otherwise it shouldn't be
610 // a member of Deferred.
611 WList->enqueue(N, B: Block, idx: Idx+1);
612 return;
613 }
614
615 bool IsNew;
616 ExplodedNode *Succ = G.getNode(L: Loc, State: N->getState(), IsSink: false, IsNew: &IsNew);
617 Succ->addPredecessor(V: N, G);
618
619 if (IsNew)
620 WList->enqueue(N: Succ, B: Block, idx: Idx+1);
621}
622
623ExplodedNode *CoreEngine::generateCallExitBeginNode(ExplodedNode *N,
624 const ReturnStmt *RS) {
625 // Create a CallExitBegin node and enqueue it.
626 const auto *LocCtx = cast<StackFrameContext>(Val: N->getLocationContext());
627
628 // Use the callee location context.
629 CallExitBegin Loc(LocCtx, RS);
630
631 bool isNew;
632 ExplodedNode *Node = G.getNode(L: Loc, State: N->getState(), IsSink: false, IsNew: &isNew);
633 Node->addPredecessor(V: N, G);
634 return isNew ? Node : nullptr;
635}
636
637std::optional<unsigned>
638CoreEngine::getCompletedIterationCount(const CFGBlock *B,
639 ExplodedNode *Pred) const {
640 const LocationContext *LC = Pred->getLocationContext();
641 BlockCounter Counter = WList->getBlockCounter();
642 unsigned BlockCount =
643 Counter.getNumVisited(CallSite: LC->getStackFrame(), BlockID: B->getBlockID());
644
645 const Stmt *Term = B->getTerminatorStmt();
646 if (isa<ForStmt, WhileStmt, CXXForRangeStmt>(Val: Term)) {
647 assert(BlockCount >= 1 &&
648 "Block count of currently analyzed block must be >= 1");
649 return BlockCount - 1;
650 }
651 if (isa<DoStmt>(Val: Term)) {
652 // In a do-while loop one iteration happens before the first evaluation of
653 // the loop condition, so we don't subtract one.
654 return BlockCount;
655 }
656 // ObjCForCollectionStmt is skipped intentionally because the current
657 // application of the iteration counts is not relevant for it.
658 return std::nullopt;
659}
660
661void CoreEngine::enqueue(ExplodedNodeSet &Set) {
662 for (const auto I : Set)
663 WList->enqueue(N: I);
664}
665
666void CoreEngine::enqueue(ExplodedNodeSet &Set,
667 const CFGBlock *Block, unsigned Idx) {
668 for (const auto I : Set)
669 enqueueStmtNode(N: I, Block, Idx);
670}
671
672void CoreEngine::enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS) {
673 for (auto *I : Set) {
674 // If we are in an inlined call, generate CallExitBegin node.
675 if (I->getLocationContext()->getParent()) {
676 I = generateCallExitBeginNode(N: I, RS);
677 if (I)
678 WList->enqueue(N: I);
679 } else {
680 // TODO: We should run remove dead bindings here.
681 G.addEndOfPath(V: I);
682 NumPathsExplored++;
683 }
684 }
685}
686
687void NodeBuilder::anchor() {}
688
689ExplodedNode* NodeBuilder::generateNodeImpl(const ProgramPoint &Loc,
690 ProgramStateRef State,
691 ExplodedNode *FromN,
692 bool MarkAsSink) {
693 HasGeneratedNodes = true;
694 bool IsNew;
695 ExplodedNode *N = C.getEngine().G.getNode(L: Loc, State, IsSink: MarkAsSink, IsNew: &IsNew);
696 N->addPredecessor(V: FromN, G&: C.getEngine().G);
697 Frontier.erase(N: FromN);
698
699 if (!IsNew)
700 return nullptr;
701
702 if (!MarkAsSink)
703 Frontier.Add(N);
704
705 return N;
706}
707
708void NodeBuilderWithSinks::anchor() {}
709
710StmtNodeBuilder::~StmtNodeBuilder() {
711 if (EnclosingBldr)
712 for (const auto I : Frontier)
713 EnclosingBldr->addNodes(N: I);
714}
715
716void BranchNodeBuilder::anchor() {}
717
718ExplodedNode *BranchNodeBuilder::generateNode(ProgramStateRef State,
719 bool Branch,
720 ExplodedNode *NodePred) {
721 const CFGBlock *Dst = Branch ? DstT : DstF;
722
723 if (!Dst)
724 return nullptr;
725
726 ProgramPoint Loc =
727 BlockEdge(C.getBlock(), Dst, NodePred->getLocationContext());
728 ExplodedNode *Succ = generateNodeImpl(Loc, State, FromN: NodePred);
729 return Succ;
730}
731
732ExplodedNode*
733IndirectGotoNodeBuilder::generateNode(const iterator &I,
734 ProgramStateRef St,
735 bool IsSink) {
736 bool IsNew;
737 ExplodedNode *Succ =
738 Eng.G.getNode(L: BlockEdge(Src, I.getBlock(), Pred->getLocationContext()),
739 State: St, IsSink, IsNew: &IsNew);
740 Succ->addPredecessor(V: Pred, G&: Eng.G);
741
742 if (!IsNew)
743 return nullptr;
744
745 if (!IsSink)
746 Eng.WList->enqueue(N: Succ);
747
748 return Succ;
749}
750
751ExplodedNode*
752SwitchNodeBuilder::generateCaseStmtNode(const iterator &I,
753 ProgramStateRef St) {
754 bool IsNew;
755 ExplodedNode *Succ =
756 Eng.G.getNode(L: BlockEdge(Src, I.getBlock(), Pred->getLocationContext()),
757 State: St, IsSink: false, IsNew: &IsNew);
758 Succ->addPredecessor(V: Pred, G&: Eng.G);
759 if (!IsNew)
760 return nullptr;
761
762 Eng.WList->enqueue(N: Succ);
763 return Succ;
764}
765
766ExplodedNode*
767SwitchNodeBuilder::generateDefaultCaseNode(ProgramStateRef St,
768 bool IsSink) {
769 // Get the block for the default case.
770 assert(Src->succ_rbegin() != Src->succ_rend());
771 CFGBlock *DefaultBlock = *Src->succ_rbegin();
772
773 // Basic correctness check for default blocks that are unreachable and not
774 // caught by earlier stages.
775 if (!DefaultBlock)
776 return nullptr;
777
778 bool IsNew;
779 ExplodedNode *Succ =
780 Eng.G.getNode(L: BlockEdge(Src, DefaultBlock, Pred->getLocationContext()),
781 State: St, IsSink, IsNew: &IsNew);
782 Succ->addPredecessor(V: Pred, G&: Eng.G);
783
784 if (!IsNew)
785 return nullptr;
786
787 if (!IsSink)
788 Eng.WList->enqueue(N: Succ);
789
790 return Succ;
791}
792