1341825Sdim//===- CoreEngine.cpp - Path-Sensitive Dataflow Engine --------------------===// 2218887Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6218887Sdim// 7218887Sdim//===----------------------------------------------------------------------===// 8218887Sdim// 9218887Sdim// This file defines a generic engine for intraprocedural, path-sensitive, 10218887Sdim// dataflow analysis via graph reachability engine. 11218887Sdim// 12218887Sdim//===----------------------------------------------------------------------===// 13218887Sdim 14218887Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h" 15218887Sdim#include "clang/AST/Expr.h" 16280031Sdim#include "clang/AST/ExprCXX.h" 17341825Sdim#include "clang/AST/Stmt.h" 18226633Sdim#include "clang/AST/StmtCXX.h" 19341825Sdim#include "clang/Analysis/AnalysisDeclContext.h" 20341825Sdim#include "clang/Analysis/CFG.h" 21341825Sdim#include "clang/Analysis/ProgramPoint.h" 22341825Sdim#include "clang/Basic/LLVM.h" 23341825Sdim#include "clang/StaticAnalyzer/Core/AnalyzerOptions.h" 24341825Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h" 25341825Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" 26341825Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h" 27341825Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h" 28341825Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h" 29341825Sdim#include "llvm/ADT/Optional.h" 30341825Sdim#include "llvm/ADT/STLExtras.h" 31234353Sdim#include "llvm/ADT/Statistic.h" 32249423Sdim#include "llvm/Support/Casting.h" 33341825Sdim#include "llvm/Support/ErrorHandling.h" 34341825Sdim#include <algorithm> 35341825Sdim#include <cassert> 36341825Sdim#include <memory> 37341825Sdim#include <utility> 38234353Sdim 39218887Sdimusing namespace clang; 40218887Sdimusing namespace ento; 41218887Sdim 42276479Sdim#define DEBUG_TYPE "CoreEngine" 43276479Sdim 44239462SdimSTATISTIC(NumSteps, 45239462Sdim "The # of steps executed."); 46234353SdimSTATISTIC(NumReachedMaxSteps, 47234353Sdim "The # of times we reached the max number of steps."); 48234353SdimSTATISTIC(NumPathsExplored, 49234353Sdim "The # of paths explored by the analyzer."); 50234353Sdim 51218887Sdim//===----------------------------------------------------------------------===// 52341825Sdim// Core analysis engine. 53218887Sdim//===----------------------------------------------------------------------===// 54218887Sdim 55344779Sdimstatic std::unique_ptr<WorkList> generateWorkList(AnalyzerOptions &Opts, 56344779Sdim SubEngine &subengine) { 57341825Sdim switch (Opts.getExplorationStrategy()) { 58344779Sdim case ExplorationStrategyKind::DFS: 59341825Sdim return WorkList::makeDFS(); 60344779Sdim case ExplorationStrategyKind::BFS: 61341825Sdim return WorkList::makeBFS(); 62344779Sdim case ExplorationStrategyKind::BFSBlockDFSContents: 63341825Sdim return WorkList::makeBFSBlockDFSContents(); 64344779Sdim case ExplorationStrategyKind::UnexploredFirst: 65341825Sdim return WorkList::makeUnexploredFirst(); 66344779Sdim case ExplorationStrategyKind::UnexploredFirstQueue: 67341825Sdim return WorkList::makeUnexploredFirstPriorityQueue(); 68344779Sdim case ExplorationStrategyKind::UnexploredFirstLocationQueue: 69344779Sdim return WorkList::makeUnexploredFirstPriorityLocationQueue(); 70218887Sdim } 71344779Sdim llvm_unreachable("Unknown AnalyzerOptions::ExplorationStrategyKind"); 72218887Sdim} 73218887Sdim 74341825SdimCoreEngine::CoreEngine(SubEngine &subengine, FunctionSummariesTy *FS, 75341825Sdim AnalyzerOptions &Opts) 76344779Sdim : SubEng(subengine), WList(generateWorkList(Opts, subengine)), 77341825Sdim BCounterFactory(G.getAllocator()), FunctionSummaries(FS) {} 78218887Sdim 79218887Sdim/// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps. 80218887Sdimbool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps, 81234353Sdim ProgramStateRef InitState) { 82280031Sdim if (G.num_roots() == 0) { // Initialize the analysis by constructing 83218887Sdim // the root if none exists. 84218887Sdim 85226633Sdim const CFGBlock *Entry = &(L->getCFG()->getEntry()); 86218887Sdim 87341825Sdim assert(Entry->empty() && "Entry block must be empty."); 88218887Sdim 89341825Sdim assert(Entry->succ_size() == 1 && "Entry block must have 1 successor."); 90218887Sdim 91234353Sdim // Mark the entry block as visited. 92234353Sdim FunctionSummaries->markVisitedBasicBlock(Entry->getBlockID(), 93234353Sdim L->getDecl(), 94234353Sdim L->getCFG()->getNumBlockIDs()); 95234353Sdim 96218887Sdim // Get the solitary successor. 97226633Sdim const CFGBlock *Succ = *(Entry->succ_begin()); 98218887Sdim 99218887Sdim // Construct an edge representing the 100218887Sdim // starting location in the function. 101218887Sdim BlockEdge StartLoc(Entry, Succ, L); 102218887Sdim 103218887Sdim // Set the current block counter to being empty. 104218887Sdim WList->setBlockCounter(BCounterFactory.GetEmptyCounter()); 105218887Sdim 106218887Sdim if (!InitState) 107309124Sdim InitState = SubEng.getInitialState(L); 108309124Sdim 109309124Sdim bool IsNew; 110309124Sdim ExplodedNode *Node = G.getNode(StartLoc, InitState, false, &IsNew); 111341825Sdim assert(IsNew); 112309124Sdim G.addRoot(Node); 113309124Sdim 114309124Sdim NodeBuilderContext BuilderCtx(*this, StartLoc.getDst(), Node); 115309124Sdim ExplodedNodeSet DstBegin; 116309124Sdim SubEng.processBeginOfFunction(BuilderCtx, Node, DstBegin, StartLoc); 117309124Sdim 118309124Sdim enqueue(DstBegin); 119218887Sdim } 120218887Sdim 121218887Sdim // Check if we have a steps limit 122218887Sdim bool UnlimitedSteps = Steps == 0; 123309124Sdim // Cap our pre-reservation in the event that the user specifies 124309124Sdim // a very large number of maximum steps. 125309124Sdim const unsigned PreReservationCap = 4000000; 126309124Sdim if(!UnlimitedSteps) 127309124Sdim G.reserve(std::min(Steps,PreReservationCap)); 128218887Sdim 129218887Sdim while (WList->hasWork()) { 130218887Sdim if (!UnlimitedSteps) { 131234353Sdim if (Steps == 0) { 132234353Sdim NumReachedMaxSteps++; 133218887Sdim break; 134234353Sdim } 135218887Sdim --Steps; 136218887Sdim } 137218887Sdim 138239462Sdim NumSteps++; 139239462Sdim 140218887Sdim const WorkListUnit& WU = WList->dequeue(); 141218887Sdim 142218887Sdim // Set the current block counter. 143218887Sdim WList->setBlockCounter(WU.getBlockCounter()); 144218887Sdim 145218887Sdim // Retrieve the node. 146226633Sdim ExplodedNode *Node = WU.getNode(); 147218887Sdim 148234353Sdim dispatchWorkItem(Node, Node->getLocation(), WU); 149234353Sdim } 150344779Sdim SubEng.processEndWorklist(); 151234353Sdim return WList->hasWork(); 152234353Sdim} 153218887Sdim 154234353Sdimvoid CoreEngine::dispatchWorkItem(ExplodedNode* Pred, ProgramPoint Loc, 155234353Sdim const WorkListUnit& WU) { 156234353Sdim // Dispatch on the location type. 157234353Sdim switch (Loc.getKind()) { 158234353Sdim case ProgramPoint::BlockEdgeKind: 159249423Sdim HandleBlockEdge(Loc.castAs<BlockEdge>(), Pred); 160234353Sdim break; 161218887Sdim 162234353Sdim case ProgramPoint::BlockEntranceKind: 163249423Sdim HandleBlockEntrance(Loc.castAs<BlockEntrance>(), Pred); 164234353Sdim break; 165218887Sdim 166234353Sdim case ProgramPoint::BlockExitKind: 167341825Sdim assert(false && "BlockExit location never occur in forward analysis."); 168234353Sdim break; 169218887Sdim 170341825Sdim case ProgramPoint::CallEnterKind: 171309124Sdim HandleCallEnter(Loc.castAs<CallEnter>(), Pred); 172234353Sdim break; 173218887Sdim 174239462Sdim case ProgramPoint::CallExitBeginKind: 175234353Sdim SubEng.processCallExit(Pred); 176234353Sdim break; 177234353Sdim 178234353Sdim case ProgramPoint::EpsilonKind: { 179234353Sdim assert(Pred->hasSinglePred() && 180234353Sdim "Assume epsilon has exactly one predecessor by construction"); 181234353Sdim ExplodedNode *PNode = Pred->getFirstPred(); 182234353Sdim dispatchWorkItem(Pred, PNode->getLocation(), WU); 183234353Sdim break; 184218887Sdim } 185234353Sdim default: 186249423Sdim assert(Loc.getAs<PostStmt>() || 187249423Sdim Loc.getAs<PostInitializer>() || 188249423Sdim Loc.getAs<PostImplicitCall>() || 189327952Sdim Loc.getAs<CallExitEnd>() || 190341825Sdim Loc.getAs<LoopExit>() || 191341825Sdim Loc.getAs<PostAllocatorCall>()); 192234353Sdim HandlePostStmt(WU.getBlock(), WU.getIndex(), Pred); 193234353Sdim break; 194218887Sdim } 195218887Sdim} 196218887Sdim 197234353Sdimbool CoreEngine::ExecuteWorkListWithInitialState(const LocationContext *L, 198226633Sdim unsigned Steps, 199296417Sdim ProgramStateRef InitState, 200226633Sdim ExplodedNodeSet &Dst) { 201234353Sdim bool DidNotFinish = ExecuteWorkList(L, Steps, InitState); 202280031Sdim for (ExplodedGraph::eop_iterator I = G.eop_begin(), E = G.eop_end(); I != E; 203280031Sdim ++I) { 204218887Sdim Dst.Add(*I); 205218887Sdim } 206234353Sdim return DidNotFinish; 207218887Sdim} 208218887Sdim 209226633Sdimvoid CoreEngine::HandleBlockEdge(const BlockEdge &L, ExplodedNode *Pred) { 210226633Sdim const CFGBlock *Blk = L.getDst(); 211234353Sdim NodeBuilderContext BuilderCtx(*this, Blk, Pred); 212218887Sdim 213234353Sdim // Mark this block as visited. 214234353Sdim const LocationContext *LC = Pred->getLocationContext(); 215234353Sdim FunctionSummaries->markVisitedBasicBlock(Blk->getBlockID(), 216234353Sdim LC->getDecl(), 217234353Sdim LC->getCFG()->getNumBlockIDs()); 218234353Sdim 219353358Sdim // Display a prunable path note to the user if it's a virtual bases branch 220353358Sdim // and we're taking the path that skips virtual base constructors. 221353358Sdim if (L.getSrc()->getTerminator().isVirtualBaseBranch() && 222353358Sdim L.getDst() == *L.getSrc()->succ_begin()) { 223353358Sdim ProgramPoint P = L.withTag(getNoteTags().makeNoteTag( 224353358Sdim [](BugReporterContext &, BugReport &) -> std::string { 225353358Sdim // TODO: Just call out the name of the most derived class 226353358Sdim // when we know it. 227353358Sdim return "Virtual base initialization skipped because " 228353358Sdim "it has already been handled by the most derived class"; 229353358Sdim }, /*IsPrunable=*/true)); 230353358Sdim // Perform the transition. 231353358Sdim ExplodedNodeSet Dst; 232353358Sdim NodeBuilder Bldr(Pred, Dst, BuilderCtx); 233353358Sdim Pred = Bldr.generateNode(P, Pred->getState(), Pred); 234353358Sdim if (!Pred) 235353358Sdim return; 236353358Sdim } 237353358Sdim 238218887Sdim // Check if we are entering the EXIT block. 239218887Sdim if (Blk == &(L.getLocationContext()->getCFG()->getExit())) { 240341825Sdim assert(L.getLocationContext()->getCFG()->getExit().empty() && 241341825Sdim "EXIT block cannot contain Stmts."); 242218887Sdim 243314564Sdim // Get return statement.. 244314564Sdim const ReturnStmt *RS = nullptr; 245314564Sdim if (!L.getSrc()->empty()) { 246344779Sdim CFGElement LastElement = L.getSrc()->back(); 247344779Sdim if (Optional<CFGStmt> LastStmt = LastElement.getAs<CFGStmt>()) { 248341825Sdim RS = dyn_cast<ReturnStmt>(LastStmt->getStmt()); 249344779Sdim } else if (Optional<CFGAutomaticObjDtor> AutoDtor = 250344779Sdim LastElement.getAs<CFGAutomaticObjDtor>()) { 251344779Sdim RS = dyn_cast<ReturnStmt>(AutoDtor->getTriggerStmt()); 252314564Sdim } 253314564Sdim } 254314564Sdim 255218887Sdim // Process the final state transition. 256314564Sdim SubEng.processEndOfFunction(BuilderCtx, Pred, RS); 257218887Sdim 258218887Sdim // This path is done. Don't enqueue any more nodes. 259218887Sdim return; 260218887Sdim } 261218887Sdim 262234353Sdim // Call into the SubEngine to process entering the CFGBlock. 263218887Sdim ExplodedNodeSet dstNodes; 264218887Sdim BlockEntrance BE(Blk, Pred->getLocationContext()); 265234353Sdim NodeBuilderWithSinks nodeBuilder(Pred, dstNodes, BuilderCtx, BE); 266243830Sdim SubEng.processCFGBlockEntrance(L, nodeBuilder, Pred); 267218887Sdim 268234353Sdim // Auto-generate a node. 269234353Sdim if (!nodeBuilder.hasGeneratedNodes()) { 270234353Sdim nodeBuilder.generateNode(Pred->State, Pred); 271218887Sdim } 272218887Sdim 273234353Sdim // Enqueue nodes onto the worklist. 274234353Sdim enqueue(dstNodes); 275218887Sdim} 276218887Sdim 277226633Sdimvoid CoreEngine::HandleBlockEntrance(const BlockEntrance &L, 278226633Sdim ExplodedNode *Pred) { 279218887Sdim // Increment the block counter. 280234353Sdim const LocationContext *LC = Pred->getLocationContext(); 281234353Sdim unsigned BlockId = L.getBlock()->getBlockID(); 282218887Sdim BlockCounter Counter = WList->getBlockCounter(); 283341825Sdim Counter = BCounterFactory.IncrementCount(Counter, LC->getStackFrame(), 284234353Sdim BlockId); 285218887Sdim WList->setBlockCounter(Counter); 286218887Sdim 287218887Sdim // Process the entrance of the block. 288249423Sdim if (Optional<CFGElement> E = L.getFirstElement()) { 289234353Sdim NodeBuilderContext Ctx(*this, L.getBlock(), Pred); 290249423Sdim SubEng.processCFGElement(*E, Pred, 0, &Ctx); 291218887Sdim } 292218887Sdim else 293218887Sdim HandleBlockExit(L.getBlock(), Pred); 294218887Sdim} 295218887Sdim 296226633Sdimvoid CoreEngine::HandleBlockExit(const CFGBlock * B, ExplodedNode *Pred) { 297353358Sdim if (const Stmt *Term = B->getTerminatorStmt()) { 298218887Sdim switch (Term->getStmtClass()) { 299218887Sdim default: 300226633Sdim llvm_unreachable("Analysis for this terminator not implemented."); 301218887Sdim 302280031Sdim case Stmt::CXXBindTemporaryExprClass: 303280031Sdim HandleCleanupTemporaryBranch( 304353358Sdim cast<CXXBindTemporaryExpr>(Term), B, Pred); 305280031Sdim return; 306280031Sdim 307249423Sdim // Model static initializers. 308249423Sdim case Stmt::DeclStmtClass: 309249423Sdim HandleStaticInit(cast<DeclStmt>(Term), B, Pred); 310249423Sdim return; 311249423Sdim 312218887Sdim case Stmt::BinaryOperatorClass: // '&&' and '||' 313218887Sdim HandleBranch(cast<BinaryOperator>(Term)->getLHS(), Term, B, Pred); 314218887Sdim return; 315218887Sdim 316218887Sdim case Stmt::BinaryConditionalOperatorClass: 317218887Sdim case Stmt::ConditionalOperatorClass: 318218887Sdim HandleBranch(cast<AbstractConditionalOperator>(Term)->getCond(), 319218887Sdim Term, B, Pred); 320218887Sdim return; 321218887Sdim 322218887Sdim // FIXME: Use constant-folding in CFG construction to simplify this 323218887Sdim // case. 324218887Sdim 325218887Sdim case Stmt::ChooseExprClass: 326218887Sdim HandleBranch(cast<ChooseExpr>(Term)->getCond(), Term, B, Pred); 327218887Sdim return; 328218887Sdim 329341825Sdim case Stmt::CXXTryStmtClass: 330234353Sdim // Generate a node for each of the successors. 331234353Sdim // Our logic for EH analysis can certainly be improved. 332234353Sdim for (CFGBlock::const_succ_iterator it = B->succ_begin(), 333234353Sdim et = B->succ_end(); it != et; ++it) { 334234353Sdim if (const CFGBlock *succ = *it) { 335234353Sdim generateNode(BlockEdge(B, succ, Pred->getLocationContext()), 336234353Sdim Pred->State, Pred); 337234353Sdim } 338234353Sdim } 339234353Sdim return; 340296417Sdim 341218887Sdim case Stmt::DoStmtClass: 342218887Sdim HandleBranch(cast<DoStmt>(Term)->getCond(), Term, B, Pred); 343218887Sdim return; 344218887Sdim 345226633Sdim case Stmt::CXXForRangeStmtClass: 346226633Sdim HandleBranch(cast<CXXForRangeStmt>(Term)->getCond(), Term, B, Pred); 347226633Sdim return; 348226633Sdim 349218887Sdim case Stmt::ForStmtClass: 350218887Sdim HandleBranch(cast<ForStmt>(Term)->getCond(), Term, B, Pred); 351218887Sdim return; 352218887Sdim 353218887Sdim case Stmt::ContinueStmtClass: 354218887Sdim case Stmt::BreakStmtClass: 355218887Sdim case Stmt::GotoStmtClass: 356218887Sdim break; 357218887Sdim 358218887Sdim case Stmt::IfStmtClass: 359218887Sdim HandleBranch(cast<IfStmt>(Term)->getCond(), Term, B, Pred); 360218887Sdim return; 361218887Sdim 362218887Sdim case Stmt::IndirectGotoStmtClass: { 363218887Sdim // Only 1 successor: the indirect goto dispatch block. 364341825Sdim assert(B->succ_size() == 1); 365218887Sdim 366218887Sdim IndirectGotoNodeBuilder 367218887Sdim builder(Pred, B, cast<IndirectGotoStmt>(Term)->getTarget(), 368218887Sdim *(B->succ_begin()), this); 369218887Sdim 370218887Sdim SubEng.processIndirectGoto(builder); 371218887Sdim return; 372218887Sdim } 373218887Sdim 374341825Sdim case Stmt::ObjCForCollectionStmtClass: 375218887Sdim // In the case of ObjCForCollectionStmt, it appears twice in a CFG: 376218887Sdim // 377218887Sdim // (1) inside a basic block, which represents the binding of the 378218887Sdim // 'element' variable to a value. 379218887Sdim // (2) in a terminator, which represents the branch. 380218887Sdim // 381218887Sdim // For (1), subengines will bind a value (i.e., 0 or 1) indicating 382218887Sdim // whether or not collection contains any more elements. We cannot 383218887Sdim // just test to see if the element is nil because a container can 384218887Sdim // contain nil elements. 385218887Sdim HandleBranch(Term, Term, B, Pred); 386218887Sdim return; 387218887Sdim 388218887Sdim case Stmt::SwitchStmtClass: { 389218887Sdim SwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(), 390218887Sdim this); 391218887Sdim 392218887Sdim SubEng.processSwitch(builder); 393218887Sdim return; 394218887Sdim } 395218887Sdim 396218887Sdim case Stmt::WhileStmtClass: 397218887Sdim HandleBranch(cast<WhileStmt>(Term)->getCond(), Term, B, Pred); 398218887Sdim return; 399353358Sdim 400353358Sdim case Stmt::GCCAsmStmtClass: 401353358Sdim assert(cast<GCCAsmStmt>(Term)->isAsmGoto() && "Encountered GCCAsmStmt without labels"); 402353358Sdim // TODO: Handle jumping to labels 403353358Sdim return; 404218887Sdim } 405218887Sdim } 406218887Sdim 407353358Sdim if (B->getTerminator().isVirtualBaseBranch()) { 408353358Sdim HandleVirtualBaseBranch(B, Pred); 409353358Sdim return; 410353358Sdim } 411353358Sdim 412341825Sdim assert(B->succ_size() == 1 && 413341825Sdim "Blocks with no terminator should have at most 1 successor."); 414218887Sdim 415218887Sdim generateNode(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()), 416218887Sdim Pred->State, Pred); 417218887Sdim} 418218887Sdim 419309124Sdimvoid CoreEngine::HandleCallEnter(const CallEnter &CE, ExplodedNode *Pred) { 420309124Sdim NodeBuilderContext BuilderCtx(*this, CE.getEntry(), Pred); 421309124Sdim SubEng.processCallEnter(BuilderCtx, CE, Pred); 422309124Sdim} 423309124Sdim 424296417Sdimvoid CoreEngine::HandleBranch(const Stmt *Cond, const Stmt *Term, 425226633Sdim const CFGBlock * B, ExplodedNode *Pred) { 426218887Sdim assert(B->succ_size() == 2); 427234353Sdim NodeBuilderContext Ctx(*this, B, Pred); 428234353Sdim ExplodedNodeSet Dst; 429344779Sdim SubEng.processBranch(Cond, Ctx, Pred, Dst, *(B->succ_begin()), 430344779Sdim *(B->succ_begin() + 1)); 431234353Sdim // Enqueue the new frontier onto the worklist. 432234353Sdim enqueue(Dst); 433218887Sdim} 434218887Sdim 435280031Sdimvoid CoreEngine::HandleCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE, 436280031Sdim const CFGBlock *B, 437280031Sdim ExplodedNode *Pred) { 438280031Sdim assert(B->succ_size() == 2); 439280031Sdim NodeBuilderContext Ctx(*this, B, Pred); 440280031Sdim ExplodedNodeSet Dst; 441280031Sdim SubEng.processCleanupTemporaryBranch(BTE, Ctx, Pred, Dst, *(B->succ_begin()), 442280031Sdim *(B->succ_begin() + 1)); 443280031Sdim // Enqueue the new frontier onto the worklist. 444280031Sdim enqueue(Dst); 445280031Sdim} 446249423Sdim 447249423Sdimvoid CoreEngine::HandleStaticInit(const DeclStmt *DS, const CFGBlock *B, 448249423Sdim ExplodedNode *Pred) { 449249423Sdim assert(B->succ_size() == 2); 450249423Sdim NodeBuilderContext Ctx(*this, B, Pred); 451249423Sdim ExplodedNodeSet Dst; 452249423Sdim SubEng.processStaticInitializer(DS, Ctx, Pred, Dst, 453249423Sdim *(B->succ_begin()), *(B->succ_begin()+1)); 454249423Sdim // Enqueue the new frontier onto the worklist. 455249423Sdim enqueue(Dst); 456249423Sdim} 457249423Sdim 458296417Sdimvoid CoreEngine::HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, 459341825Sdim ExplodedNode *Pred) { 460234353Sdim assert(B); 461234353Sdim assert(!B->empty()); 462218887Sdim 463218887Sdim if (StmtIdx == B->size()) 464218887Sdim HandleBlockExit(B, Pred); 465218887Sdim else { 466234353Sdim NodeBuilderContext Ctx(*this, B, Pred); 467234353Sdim SubEng.processCFGElement((*B)[StmtIdx], Pred, StmtIdx, &Ctx); 468218887Sdim } 469218887Sdim} 470218887Sdim 471353358Sdimvoid CoreEngine::HandleVirtualBaseBranch(const CFGBlock *B, 472353358Sdim ExplodedNode *Pred) { 473353358Sdim const LocationContext *LCtx = Pred->getLocationContext(); 474353358Sdim if (const auto *CallerCtor = dyn_cast_or_null<CXXConstructExpr>( 475353358Sdim LCtx->getStackFrame()->getCallSite())) { 476353358Sdim switch (CallerCtor->getConstructionKind()) { 477353358Sdim case CXXConstructExpr::CK_NonVirtualBase: 478353358Sdim case CXXConstructExpr::CK_VirtualBase: { 479353358Sdim BlockEdge Loc(B, *B->succ_begin(), LCtx); 480353358Sdim HandleBlockEdge(Loc, Pred); 481353358Sdim return; 482353358Sdim } 483353358Sdim default: 484353358Sdim break; 485353358Sdim } 486353358Sdim } 487353358Sdim 488353358Sdim // We either don't see a parent stack frame because we're in the top frame, 489353358Sdim // or the parent stack frame doesn't initialize our virtual bases. 490353358Sdim BlockEdge Loc(B, *(B->succ_begin() + 1), LCtx); 491353358Sdim HandleBlockEdge(Loc, Pred); 492353358Sdim} 493353358Sdim 494218887Sdim/// generateNode - Utility method to generate nodes, hook up successors, 495218887Sdim/// and add nodes to the worklist. 496226633Sdimvoid CoreEngine::generateNode(const ProgramPoint &Loc, 497234353Sdim ProgramStateRef State, 498226633Sdim ExplodedNode *Pred) { 499218887Sdim bool IsNew; 500280031Sdim ExplodedNode *Node = G.getNode(Loc, State, false, &IsNew); 501218887Sdim 502218887Sdim if (Pred) 503280031Sdim Node->addPredecessor(Pred, G); // Link 'Node' with its predecessor. 504218887Sdim else { 505341825Sdim assert(IsNew); 506280031Sdim G.addRoot(Node); // 'Node' has no predecessor. Make it a root. 507218887Sdim } 508218887Sdim 509218887Sdim // Only add 'Node' to the worklist if it was freshly generated. 510218887Sdim if (IsNew) WList->enqueue(Node); 511218887Sdim} 512218887Sdim 513234353Sdimvoid CoreEngine::enqueueStmtNode(ExplodedNode *N, 514234353Sdim const CFGBlock *Block, unsigned Idx) { 515234353Sdim assert(Block); 516341825Sdim assert(!N->isSink()); 517218887Sdim 518218887Sdim // Check if this node entered a callee. 519249423Sdim if (N->getLocation().getAs<CallEnter>()) { 520218887Sdim // Still use the index of the CallExpr. It's needed to create the callee 521218887Sdim // StackFrameContext. 522234353Sdim WList->enqueue(N, Block, Idx); 523218887Sdim return; 524218887Sdim } 525218887Sdim 526218887Sdim // Do not create extra nodes. Move to the next CFG element. 527249423Sdim if (N->getLocation().getAs<PostInitializer>() || 528327952Sdim N->getLocation().getAs<PostImplicitCall>()|| 529327952Sdim N->getLocation().getAs<LoopExit>()) { 530234353Sdim WList->enqueue(N, Block, Idx+1); 531218887Sdim return; 532218887Sdim } 533218887Sdim 534249423Sdim if (N->getLocation().getAs<EpsilonPoint>()) { 535234353Sdim WList->enqueue(N, Block, Idx); 536234353Sdim return; 537234353Sdim } 538218887Sdim 539276479Sdim if ((*Block)[Idx].getKind() == CFGElement::NewAllocator) { 540276479Sdim WList->enqueue(N, Block, Idx+1); 541276479Sdim return; 542276479Sdim } 543276479Sdim 544243830Sdim // At this point, we know we're processing a normal statement. 545249423Sdim CFGStmt CS = (*Block)[Idx].castAs<CFGStmt>(); 546243830Sdim PostStmt Loc(CS.getStmt(), N->getLocationContext()); 547234353Sdim 548276479Sdim if (Loc == N->getLocation().withTag(nullptr)) { 549218887Sdim // Note: 'N' should be a fresh node because otherwise it shouldn't be 550218887Sdim // a member of Deferred. 551234353Sdim WList->enqueue(N, Block, Idx+1); 552218887Sdim return; 553218887Sdim } 554218887Sdim 555218887Sdim bool IsNew; 556280031Sdim ExplodedNode *Succ = G.getNode(Loc, N->getState(), false, &IsNew); 557280031Sdim Succ->addPredecessor(N, G); 558218887Sdim 559218887Sdim if (IsNew) 560234353Sdim WList->enqueue(Succ, Block, Idx+1); 561218887Sdim} 562218887Sdim 563314564SdimExplodedNode *CoreEngine::generateCallExitBeginNode(ExplodedNode *N, 564314564Sdim const ReturnStmt *RS) { 565239462Sdim // Create a CallExitBegin node and enqueue it. 566341825Sdim const auto *LocCtx = cast<StackFrameContext>(N->getLocationContext()); 567218887Sdim 568239462Sdim // Use the callee location context. 569314564Sdim CallExitBegin Loc(LocCtx, RS); 570218887Sdim 571234353Sdim bool isNew; 572280031Sdim ExplodedNode *Node = G.getNode(Loc, N->getState(), false, &isNew); 573280031Sdim Node->addPredecessor(N, G); 574276479Sdim return isNew ? Node : nullptr; 575218887Sdim} 576218887Sdim 577234353Sdimvoid CoreEngine::enqueue(ExplodedNodeSet &Set) { 578341825Sdim for (const auto I : Set) 579341825Sdim WList->enqueue(I); 580218887Sdim} 581218887Sdim 582234353Sdimvoid CoreEngine::enqueue(ExplodedNodeSet &Set, 583234353Sdim const CFGBlock *Block, unsigned Idx) { 584341825Sdim for (const auto I : Set) 585341825Sdim enqueueStmtNode(I, Block, Idx); 586218887Sdim} 587218887Sdim 588314564Sdimvoid CoreEngine::enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS) { 589341825Sdim for (auto I : Set) { 590239462Sdim // If we are in an inlined call, generate CallExitBegin node. 591341825Sdim if (I->getLocationContext()->getParent()) { 592341825Sdim I = generateCallExitBeginNode(I, RS); 593341825Sdim if (I) 594341825Sdim WList->enqueue(I); 595234353Sdim } else { 596239462Sdim // TODO: We should run remove dead bindings here. 597341825Sdim G.addEndOfPath(I); 598234353Sdim NumPathsExplored++; 599234353Sdim } 600234353Sdim } 601221345Sdim} 602221345Sdim 603341825Sdimvoid NodeBuilder::anchor() {} 604218887Sdim 605234353SdimExplodedNode* NodeBuilder::generateNodeImpl(const ProgramPoint &Loc, 606234353Sdim ProgramStateRef State, 607234353Sdim ExplodedNode *FromN, 608234353Sdim bool MarkAsSink) { 609234353Sdim HasGeneratedNodes = true; 610218887Sdim bool IsNew; 611280031Sdim ExplodedNode *N = C.Eng.G.getNode(Loc, State, MarkAsSink, &IsNew); 612280031Sdim N->addPredecessor(FromN, C.Eng.G); 613234353Sdim Frontier.erase(FromN); 614218887Sdim 615234353Sdim if (!IsNew) 616276479Sdim return nullptr; 617218887Sdim 618234353Sdim if (!MarkAsSink) 619234353Sdim Frontier.Add(N); 620218887Sdim 621234353Sdim return N; 622234353Sdim} 623218887Sdim 624341825Sdimvoid NodeBuilderWithSinks::anchor() {} 625218887Sdim 626234353SdimStmtNodeBuilder::~StmtNodeBuilder() { 627234353Sdim if (EnclosingBldr) 628341825Sdim for (const auto I : Frontier) 629341825Sdim EnclosingBldr->addNodes(I); 630218887Sdim} 631218887Sdim 632341825Sdimvoid BranchNodeBuilder::anchor() {} 633218887Sdim 634234353SdimExplodedNode *BranchNodeBuilder::generateNode(ProgramStateRef State, 635234353Sdim bool branch, 636234353Sdim ExplodedNode *NodePred) { 637234353Sdim // If the branch has been marked infeasible we should not generate a node. 638234353Sdim if (!isFeasible(branch)) 639276479Sdim return nullptr; 640234353Sdim 641234353Sdim ProgramPoint Loc = BlockEdge(C.Block, branch ? DstT:DstF, 642234353Sdim NodePred->getLocationContext()); 643234353Sdim ExplodedNode *Succ = generateNodeImpl(Loc, State, NodePred); 644234353Sdim return Succ; 645218887Sdim} 646218887Sdim 647218887SdimExplodedNode* 648226633SdimIndirectGotoNodeBuilder::generateNode(const iterator &I, 649234353Sdim ProgramStateRef St, 650234353Sdim bool IsSink) { 651218887Sdim bool IsNew; 652280031Sdim ExplodedNode *Succ = 653280031Sdim Eng.G.getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()), 654280031Sdim St, IsSink, &IsNew); 655280031Sdim Succ->addPredecessor(Pred, Eng.G); 656218887Sdim 657234353Sdim if (!IsNew) 658276479Sdim return nullptr; 659218887Sdim 660234353Sdim if (!IsSink) 661234353Sdim Eng.WList->enqueue(Succ); 662218887Sdim 663234353Sdim return Succ; 664218887Sdim} 665218887Sdim 666218887SdimExplodedNode* 667226633SdimSwitchNodeBuilder::generateCaseStmtNode(const iterator &I, 668234353Sdim ProgramStateRef St) { 669218887Sdim bool IsNew; 670280031Sdim ExplodedNode *Succ = 671280031Sdim Eng.G.getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()), 672280031Sdim St, false, &IsNew); 673280031Sdim Succ->addPredecessor(Pred, Eng.G); 674234353Sdim if (!IsNew) 675276479Sdim return nullptr; 676234353Sdim 677234353Sdim Eng.WList->enqueue(Succ); 678234353Sdim return Succ; 679218887Sdim} 680218887Sdim 681218887SdimExplodedNode* 682234353SdimSwitchNodeBuilder::generateDefaultCaseNode(ProgramStateRef St, 683234353Sdim bool IsSink) { 684218887Sdim // Get the block for the default case. 685226633Sdim assert(Src->succ_rbegin() != Src->succ_rend()); 686226633Sdim CFGBlock *DefaultBlock = *Src->succ_rbegin(); 687218887Sdim 688226633Sdim // Sanity check for default blocks that are unreachable and not caught 689226633Sdim // by earlier stages. 690226633Sdim if (!DefaultBlock) 691276479Sdim return nullptr; 692276479Sdim 693218887Sdim bool IsNew; 694280031Sdim ExplodedNode *Succ = 695280031Sdim Eng.G.getNode(BlockEdge(Src, DefaultBlock, Pred->getLocationContext()), 696280031Sdim St, IsSink, &IsNew); 697280031Sdim Succ->addPredecessor(Pred, Eng.G); 698218887Sdim 699234353Sdim if (!IsNew) 700276479Sdim return nullptr; 701218887Sdim 702234353Sdim if (!IsSink) 703234353Sdim Eng.WList->enqueue(Succ); 704218887Sdim 705234353Sdim return Succ; 706218887Sdim} 707