792 lines · cpp
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-exception6//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(Entry->getBlockID(),101 L->getDecl(),102 L->getCFG()->getNumBlockIDs());103 104 // Get the solitary successor.105 const CFGBlock *Succ = *(Entry->succ_begin());106 107 // Construct an edge representing the108 // 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(L);116 117 bool IsNew;118 ExplodedNode *Node = G.getNode(StartLoc, InitState, false, &IsNew);119 assert(IsNew);120 G.designateAsRoot(Node);121 122 NodeBuilderContext BuilderCtx(*this, StartLoc.getDst(), Node);123 ExplodedNodeSet DstBegin;124 ExprEng.processBeginOfFunction(BuilderCtx, Node, DstBegin, StartLoc);125 126 enqueue(DstBegin);127 }128 129 // Check if we have a steps limit130 bool UnlimitedSteps = MaxSteps == 0;131 132 // Cap our pre-reservation in the event that the user specifies133 // a very large number of maximum steps.134 const unsigned PreReservationCap = 4000000;135 if(!UnlimitedSteps)136 G.reserve(std::min(MaxSteps, 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(Node, 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(STUSteps * Pct / 100, 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("dispatchWorkItem {0}",185 ProgramPoint::getProgramPointKindName(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{std::move(Detail), ""};203 const auto &SM = Pred->getLocationContext()204 ->getAnalysisDeclContext()205 ->getASTContext()206 .getSourceManager();207 auto Line = SM.getPresumedLineNumber(*SLoc);208 auto Fname = SM.getFilename(*SLoc);209 return llvm::TimeTraceMetadata{std::move(Detail), Fname.str(),210 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(Loc.castAs<BlockEdge>(), Pred);223 break;224 225 case ProgramPoint::BlockEntranceKind:226 HandleBlockEntrance(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(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, 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(WU.getBlock(), 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(Blk->getBlockID(),267 LC->getDecl(),268 LC->getCFG()->getNumBlockIDs());269 270 // Display a prunable path note to the user if it's a virtual bases branch271 // 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(getDataTags().make<NoteTag>(275 [](BugReporterContext &, PathSensitiveBugReport &) -> std::string {276 // TODO: Just call out the name of the most derived class277 // 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=*/true));282 // Perform the transition.283 ExplodedNodeSet Dst;284 NodeBuilder Bldr(Pred, Dst, BuilderCtx);285 Pred = Bldr.generateNode(P, 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>(LastStmt->getStmt());301 } else if (std::optional<CFGAutomaticObjDtor> AutoDtor =302 LastElement.getAs<CFGAutomaticObjDtor>()) {303 RS = dyn_cast<ReturnStmt>(AutoDtor->getTriggerStmt());304 }305 }306 307 ExplodedNodeSet CheckerNodes;308 BlockEntrance BE(L.getSrc(), L.getDst(), Pred->getLocationContext());309 ExprEng.runCheckersForBlockEntrance(BuilderCtx, BE, Pred, CheckerNodes);310 311 // Process the final state transition.312 for (ExplodedNode *P : CheckerNodes) {313 ExprEng.processEndOfFunction(BuilderCtx, 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, Pred);325 326 // Auto-generate a node.327 if (!NodeBuilder.hasGeneratedNodes()) {328 NodeBuilder.generateNode(Pred->State, Pred);329 }330 331 ExplodedNodeSet CheckerNodes;332 for (auto *N : DstNodes) {333 ExprEng.runCheckersForBlockEntrance(BuilderCtx, BE, N, CheckerNodes);334 }335 336 // Enqueue nodes onto the worklist.337 enqueue(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(Counter, LC->getStackFrame(),347 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, Pred, 0, &Ctx);354 } else355 HandleBlockExit(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 cast<CXXBindTemporaryExpr>(Term), B, Pred);367 return;368 369 // Model static initializers.370 case Stmt::DeclStmtClass:371 HandleStaticInit(cast<DeclStmt>(Term), B, Pred);372 return;373 374 case Stmt::BinaryOperatorClass: // '&&' and '||'375 HandleBranch(cast<BinaryOperator>(Term)->getLHS(), Term, B, Pred);376 return;377 378 case Stmt::BinaryConditionalOperatorClass:379 case Stmt::ConditionalOperatorClass:380 HandleBranch(cast<AbstractConditionalOperator>(Term)->getCond(),381 Term, B, Pred);382 return;383 384 // FIXME: Use constant-folding in CFG construction to simplify this385 // case.386 387 case Stmt::ChooseExprClass:388 HandleBranch(cast<ChooseExpr>(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(BlockEdge(B, succ, Pred->getLocationContext()),398 Pred->State, Pred);399 }400 }401 return;402 403 case Stmt::DoStmtClass:404 HandleBranch(cast<DoStmt>(Term)->getCond(), Term, B, Pred);405 return;406 407 case Stmt::CXXForRangeStmtClass:408 HandleBranch(cast<CXXForRangeStmt>(Term)->getCond(), Term, B, Pred);409 return;410 411 case Stmt::ForStmtClass:412 HandleBranch(cast<ForStmt>(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(cast<IfStmt>(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 IndirectGotoNodeBuilder430 builder(Pred, B, cast<IndirectGotoStmt>(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 the441 // '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) indicating445 // whether or not collection contains any more elements. We cannot446 // just test to see if the element is nil because a container can447 // contain nil elements.448 HandleBranch(Term, Term, B, Pred);449 return;450 451 case Stmt::SwitchStmtClass: {452 SwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(),453 this);454 455 ExprEng.processSwitch(builder);456 return;457 }458 459 case Stmt::WhileStmtClass:460 HandleBranch(cast<WhileStmt>(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 labels466 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(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()),479 Pred->State, Pred);480}481 482void CoreEngine::HandleCallEnter(const CallEnter &CE, ExplodedNode *Pred) {483 NodeBuilderContext BuilderCtx(*this, CE.getEntry(), Pred);484 ExprEng.processCallEnter(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(Cond, Ctx, Pred, Dst, *(B->succ_begin()),493 *(B->succ_begin() + 1),494 getCompletedIterationCount(B, Pred));495 // Enqueue the new frontier onto the worklist.496 enqueue(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, Ctx, Pred, Dst, *(B->succ_begin()),506 *(B->succ_begin() + 1));507 // Enqueue the new frontier onto the worklist.508 enqueue(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, Ctx, Pred, Dst,517 *(B->succ_begin()), *(B->succ_begin()+1));518 // Enqueue the new frontier onto the worklist.519 enqueue(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((*B)[StmtIdx], Pred, StmtIdx, &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 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(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(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(Loc, State, false, &IsNew);566 567 Node->addPredecessor(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(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 callee581 // StackFrameContext.582 WList->enqueue(N, Block, 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, Block, Idx+1);591 return;592 }593 594 if (N->getLocation().getAs<EpsilonPoint>()) {595 WList->enqueue(N, Block, Idx);596 return;597 }598 599 if ((*Block)[Idx].getKind() == CFGElement::NewAllocator) {600 WList->enqueue(N, Block, 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(nullptr)) {609 // Note: 'N' should be a fresh node because otherwise it shouldn't be610 // a member of Deferred.611 WList->enqueue(N, Block, Idx+1);612 return;613 }614 615 bool IsNew;616 ExplodedNode *Succ = G.getNode(Loc, N->getState(), false, &IsNew);617 Succ->addPredecessor(N, G);618 619 if (IsNew)620 WList->enqueue(Succ, Block, 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>(N->getLocationContext());627 628 // Use the callee location context.629 CallExitBegin Loc(LocCtx, RS);630 631 bool isNew;632 ExplodedNode *Node = G.getNode(Loc, N->getState(), false, &isNew);633 Node->addPredecessor(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(LC->getStackFrame(), B->getBlockID());644 645 const Stmt *Term = B->getTerminatorStmt();646 if (isa<ForStmt, WhileStmt, CXXForRangeStmt>(Term)) {647 assert(BlockCount >= 1 &&648 "Block count of currently analyzed block must be >= 1");649 return BlockCount - 1;650 }651 if (isa<DoStmt>(Term)) {652 // In a do-while loop one iteration happens before the first evaluation of653 // the loop condition, so we don't subtract one.654 return BlockCount;655 }656 // ObjCForCollectionStmt is skipped intentionally because the current657 // 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(I);664}665 666void CoreEngine::enqueue(ExplodedNodeSet &Set,667 const CFGBlock *Block, unsigned Idx) {668 for (const auto I : Set)669 enqueueStmtNode(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(I, RS);677 if (I)678 WList->enqueue(I);679 } else {680 // TODO: We should run remove dead bindings here.681 G.addEndOfPath(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(Loc, State, MarkAsSink, &IsNew);696 N->addPredecessor(FromN, C.getEngine().G);697 Frontier.erase(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(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, 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(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()),739 St, IsSink, &IsNew);740 Succ->addPredecessor(Pred, Eng.G);741 742 if (!IsNew)743 return nullptr;744 745 if (!IsSink)746 Eng.WList->enqueue(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(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()),757 St, false, &IsNew);758 Succ->addPredecessor(Pred, Eng.G);759 if (!IsNew)760 return nullptr;761 762 Eng.WList->enqueue(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 not774 // caught by earlier stages.775 if (!DefaultBlock)776 return nullptr;777 778 bool IsNew;779 ExplodedNode *Succ =780 Eng.G.getNode(BlockEdge(Src, DefaultBlock, Pred->getLocationContext()),781 St, IsSink, &IsNew);782 Succ->addPredecessor(Pred, Eng.G);783 784 if (!IsNew)785 return nullptr;786 787 if (!IsSink)788 Eng.WList->enqueue(Succ);789 790 return Succ;791}792