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 "clang/AST/Expr.h" 16 #include "clang/AST/ExprCXX.h" 17 #include "clang/AST/Stmt.h" 18 #include "clang/AST/StmtCXX.h" 19 #include "clang/Analysis/AnalysisDeclContext.h" 20 #include "clang/Analysis/CFG.h" 21 #include "clang/Analysis/ProgramPoint.h" 22 #include "clang/Basic/LLVM.h" 23 #include "clang/StaticAnalyzer/Core/AnalyzerOptions.h" 24 #include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h" 25 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" 26 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 27 #include "clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h" 28 #include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h" 29 #include "llvm/ADT/Optional.h" 30 #include "llvm/ADT/STLExtras.h" 31 #include "llvm/ADT/Statistic.h" 32 #include "llvm/Support/Casting.h" 33 #include "llvm/Support/ErrorHandling.h" 34 #include <algorithm> 35 #include <cassert> 36 #include <memory> 37 #include <utility> 38 39 using namespace clang; 40 using namespace ento; 41 42 #define DEBUG_TYPE "CoreEngine" 43 44 STATISTIC(NumSteps, 45 "The # of steps executed."); 46 STATISTIC(NumSTUSteps, "The # of STU steps executed."); 47 STATISTIC(NumCTUSteps, "The # of CTU steps executed."); 48 STATISTIC(NumReachedMaxSteps, 49 "The # of times we reached the max number of steps."); 50 STATISTIC(NumPathsExplored, 51 "The # of paths explored by the analyzer."); 52 53 //===----------------------------------------------------------------------===// 54 // Core analysis engine. 55 //===----------------------------------------------------------------------===// 56 57 static std::unique_ptr<WorkList> generateWorkList(AnalyzerOptions &Opts) { 58 switch (Opts.getExplorationStrategy()) { 59 case ExplorationStrategyKind::DFS: 60 return WorkList::makeDFS(); 61 case ExplorationStrategyKind::BFS: 62 return WorkList::makeBFS(); 63 case ExplorationStrategyKind::BFSBlockDFSContents: 64 return WorkList::makeBFSBlockDFSContents(); 65 case ExplorationStrategyKind::UnexploredFirst: 66 return WorkList::makeUnexploredFirst(); 67 case ExplorationStrategyKind::UnexploredFirstQueue: 68 return WorkList::makeUnexploredFirstPriorityQueue(); 69 case ExplorationStrategyKind::UnexploredFirstLocationQueue: 70 return WorkList::makeUnexploredFirstPriorityLocationQueue(); 71 } 72 llvm_unreachable("Unknown AnalyzerOptions::ExplorationStrategyKind"); 73 } 74 75 CoreEngine::CoreEngine(ExprEngine &exprengine, FunctionSummariesTy *FS, 76 AnalyzerOptions &Opts) 77 : ExprEng(exprengine), WList(generateWorkList(Opts)), 78 CTUWList(Opts.IsNaiveCTUEnabled ? generateWorkList(Opts) : nullptr), 79 BCounterFactory(G.getAllocator()), FunctionSummaries(FS) {} 80 81 void CoreEngine::setBlockCounter(BlockCounter C) { 82 WList->setBlockCounter(C); 83 if (CTUWList) 84 CTUWList->setBlockCounter(C); 85 } 86 87 /// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps. 88 bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned MaxSteps, 89 ProgramStateRef InitState) { 90 if (G.num_roots() == 0) { // Initialize the analysis by constructing 91 // the root if none exists. 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 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(L); 116 117 bool IsNew; 118 ExplodedNode *Node = G.getNode(StartLoc, InitState, false, &IsNew); 119 assert(IsNew); 120 G.addRoot(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 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(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 182 void CoreEngine::dispatchWorkItem(ExplodedNode* Pred, ProgramPoint Loc, 183 const WorkListUnit& WU) { 184 // Dispatch on the location type. 185 switch (Loc.getKind()) { 186 case ProgramPoint::BlockEdgeKind: 187 HandleBlockEdge(Loc.castAs<BlockEdge>(), Pred); 188 break; 189 190 case ProgramPoint::BlockEntranceKind: 191 HandleBlockEntrance(Loc.castAs<BlockEntrance>(), Pred); 192 break; 193 194 case ProgramPoint::BlockExitKind: 195 assert(false && "BlockExit location never occur in forward analysis."); 196 break; 197 198 case ProgramPoint::CallEnterKind: 199 HandleCallEnter(Loc.castAs<CallEnter>(), Pred); 200 break; 201 202 case ProgramPoint::CallExitBeginKind: 203 ExprEng.processCallExit(Pred); 204 break; 205 206 case ProgramPoint::EpsilonKind: { 207 assert(Pred->hasSinglePred() && 208 "Assume epsilon has exactly one predecessor by construction"); 209 ExplodedNode *PNode = Pred->getFirstPred(); 210 dispatchWorkItem(Pred, PNode->getLocation(), WU); 211 break; 212 } 213 default: 214 assert(Loc.getAs<PostStmt>() || 215 Loc.getAs<PostInitializer>() || 216 Loc.getAs<PostImplicitCall>() || 217 Loc.getAs<CallExitEnd>() || 218 Loc.getAs<LoopExit>() || 219 Loc.getAs<PostAllocatorCall>()); 220 HandlePostStmt(WU.getBlock(), WU.getIndex(), Pred); 221 break; 222 } 223 } 224 225 bool CoreEngine::ExecuteWorkListWithInitialState(const LocationContext *L, 226 unsigned Steps, 227 ProgramStateRef InitState, 228 ExplodedNodeSet &Dst) { 229 bool DidNotFinish = ExecuteWorkList(L, Steps, InitState); 230 for (ExplodedGraph::eop_iterator I = G.eop_begin(), E = G.eop_end(); I != E; 231 ++I) { 232 Dst.Add(*I); 233 } 234 return DidNotFinish; 235 } 236 237 void CoreEngine::HandleBlockEdge(const BlockEdge &L, ExplodedNode *Pred) { 238 const CFGBlock *Blk = L.getDst(); 239 NodeBuilderContext BuilderCtx(*this, Blk, Pred); 240 241 // Mark this block as visited. 242 const LocationContext *LC = Pred->getLocationContext(); 243 FunctionSummaries->markVisitedBasicBlock(Blk->getBlockID(), 244 LC->getDecl(), 245 LC->getCFG()->getNumBlockIDs()); 246 247 // Display a prunable path note to the user if it's a virtual bases branch 248 // and we're taking the path that skips virtual base constructors. 249 if (L.getSrc()->getTerminator().isVirtualBaseBranch() && 250 L.getDst() == *L.getSrc()->succ_begin()) { 251 ProgramPoint P = L.withTag(getDataTags().make<NoteTag>( 252 [](BugReporterContext &, PathSensitiveBugReport &) -> std::string { 253 // TODO: Just call out the name of the most derived class 254 // when we know it. 255 return "Virtual base initialization skipped because " 256 "it has already been handled by the most derived class"; 257 }, 258 /*IsPrunable=*/true)); 259 // Perform the transition. 260 ExplodedNodeSet Dst; 261 NodeBuilder Bldr(Pred, Dst, BuilderCtx); 262 Pred = Bldr.generateNode(P, Pred->getState(), Pred); 263 if (!Pred) 264 return; 265 } 266 267 // Check if we are entering the EXIT block. 268 if (Blk == &(L.getLocationContext()->getCFG()->getExit())) { 269 assert(L.getLocationContext()->getCFG()->getExit().empty() && 270 "EXIT block cannot contain Stmts."); 271 272 // Get return statement.. 273 const ReturnStmt *RS = nullptr; 274 if (!L.getSrc()->empty()) { 275 CFGElement LastElement = L.getSrc()->back(); 276 if (Optional<CFGStmt> LastStmt = LastElement.getAs<CFGStmt>()) { 277 RS = dyn_cast<ReturnStmt>(LastStmt->getStmt()); 278 } else if (Optional<CFGAutomaticObjDtor> AutoDtor = 279 LastElement.getAs<CFGAutomaticObjDtor>()) { 280 RS = dyn_cast<ReturnStmt>(AutoDtor->getTriggerStmt()); 281 } 282 } 283 284 // Process the final state transition. 285 ExprEng.processEndOfFunction(BuilderCtx, Pred, RS); 286 287 // This path is done. Don't enqueue any more nodes. 288 return; 289 } 290 291 // Call into the ExprEngine to process entering the CFGBlock. 292 ExplodedNodeSet dstNodes; 293 BlockEntrance BE(Blk, Pred->getLocationContext()); 294 NodeBuilderWithSinks nodeBuilder(Pred, dstNodes, BuilderCtx, BE); 295 ExprEng.processCFGBlockEntrance(L, nodeBuilder, Pred); 296 297 // Auto-generate a node. 298 if (!nodeBuilder.hasGeneratedNodes()) { 299 nodeBuilder.generateNode(Pred->State, Pred); 300 } 301 302 // Enqueue nodes onto the worklist. 303 enqueue(dstNodes); 304 } 305 306 void CoreEngine::HandleBlockEntrance(const BlockEntrance &L, 307 ExplodedNode *Pred) { 308 // Increment the block counter. 309 const LocationContext *LC = Pred->getLocationContext(); 310 unsigned BlockId = L.getBlock()->getBlockID(); 311 BlockCounter Counter = WList->getBlockCounter(); 312 Counter = BCounterFactory.IncrementCount(Counter, LC->getStackFrame(), 313 BlockId); 314 setBlockCounter(Counter); 315 316 // Process the entrance of the block. 317 if (Optional<CFGElement> E = L.getFirstElement()) { 318 NodeBuilderContext Ctx(*this, L.getBlock(), Pred); 319 ExprEng.processCFGElement(*E, Pred, 0, &Ctx); 320 } 321 else 322 HandleBlockExit(L.getBlock(), Pred); 323 } 324 325 void CoreEngine::HandleBlockExit(const CFGBlock * B, ExplodedNode *Pred) { 326 if (const Stmt *Term = B->getTerminatorStmt()) { 327 switch (Term->getStmtClass()) { 328 default: 329 llvm_unreachable("Analysis for this terminator not implemented."); 330 331 case Stmt::CXXBindTemporaryExprClass: 332 HandleCleanupTemporaryBranch( 333 cast<CXXBindTemporaryExpr>(Term), B, Pred); 334 return; 335 336 // Model static initializers. 337 case Stmt::DeclStmtClass: 338 HandleStaticInit(cast<DeclStmt>(Term), B, Pred); 339 return; 340 341 case Stmt::BinaryOperatorClass: // '&&' and '||' 342 HandleBranch(cast<BinaryOperator>(Term)->getLHS(), Term, B, Pred); 343 return; 344 345 case Stmt::BinaryConditionalOperatorClass: 346 case Stmt::ConditionalOperatorClass: 347 HandleBranch(cast<AbstractConditionalOperator>(Term)->getCond(), 348 Term, B, Pred); 349 return; 350 351 // FIXME: Use constant-folding in CFG construction to simplify this 352 // case. 353 354 case Stmt::ChooseExprClass: 355 HandleBranch(cast<ChooseExpr>(Term)->getCond(), Term, B, Pred); 356 return; 357 358 case Stmt::CXXTryStmtClass: 359 // Generate a node for each of the successors. 360 // Our logic for EH analysis can certainly be improved. 361 for (CFGBlock::const_succ_iterator it = B->succ_begin(), 362 et = B->succ_end(); it != et; ++it) { 363 if (const CFGBlock *succ = *it) { 364 generateNode(BlockEdge(B, succ, Pred->getLocationContext()), 365 Pred->State, Pred); 366 } 367 } 368 return; 369 370 case Stmt::DoStmtClass: 371 HandleBranch(cast<DoStmt>(Term)->getCond(), Term, B, Pred); 372 return; 373 374 case Stmt::CXXForRangeStmtClass: 375 HandleBranch(cast<CXXForRangeStmt>(Term)->getCond(), Term, B, Pred); 376 return; 377 378 case Stmt::ForStmtClass: 379 HandleBranch(cast<ForStmt>(Term)->getCond(), Term, B, Pred); 380 return; 381 382 case Stmt::SEHLeaveStmtClass: 383 case Stmt::ContinueStmtClass: 384 case Stmt::BreakStmtClass: 385 case Stmt::GotoStmtClass: 386 break; 387 388 case Stmt::IfStmtClass: 389 HandleBranch(cast<IfStmt>(Term)->getCond(), Term, B, Pred); 390 return; 391 392 case Stmt::IndirectGotoStmtClass: { 393 // Only 1 successor: the indirect goto dispatch block. 394 assert(B->succ_size() == 1); 395 396 IndirectGotoNodeBuilder 397 builder(Pred, B, cast<IndirectGotoStmt>(Term)->getTarget(), 398 *(B->succ_begin()), this); 399 400 ExprEng.processIndirectGoto(builder); 401 return; 402 } 403 404 case Stmt::ObjCForCollectionStmtClass: 405 // In the case of ObjCForCollectionStmt, it appears twice in a CFG: 406 // 407 // (1) inside a basic block, which represents the binding of the 408 // 'element' variable to a value. 409 // (2) in a terminator, which represents the branch. 410 // 411 // For (1), ExprEngine will bind a value (i.e., 0 or 1) indicating 412 // whether or not collection contains any more elements. We cannot 413 // just test to see if the element is nil because a container can 414 // contain nil elements. 415 HandleBranch(Term, Term, B, Pred); 416 return; 417 418 case Stmt::SwitchStmtClass: { 419 SwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(), 420 this); 421 422 ExprEng.processSwitch(builder); 423 return; 424 } 425 426 case Stmt::WhileStmtClass: 427 HandleBranch(cast<WhileStmt>(Term)->getCond(), Term, B, Pred); 428 return; 429 430 case Stmt::GCCAsmStmtClass: 431 assert(cast<GCCAsmStmt>(Term)->isAsmGoto() && "Encountered GCCAsmStmt without labels"); 432 // TODO: Handle jumping to labels 433 return; 434 } 435 } 436 437 if (B->getTerminator().isVirtualBaseBranch()) { 438 HandleVirtualBaseBranch(B, Pred); 439 return; 440 } 441 442 assert(B->succ_size() == 1 && 443 "Blocks with no terminator should have at most 1 successor."); 444 445 generateNode(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()), 446 Pred->State, Pred); 447 } 448 449 void CoreEngine::HandleCallEnter(const CallEnter &CE, ExplodedNode *Pred) { 450 NodeBuilderContext BuilderCtx(*this, CE.getEntry(), Pred); 451 ExprEng.processCallEnter(BuilderCtx, CE, Pred); 452 } 453 454 void CoreEngine::HandleBranch(const Stmt *Cond, const Stmt *Term, 455 const CFGBlock * B, ExplodedNode *Pred) { 456 assert(B->succ_size() == 2); 457 NodeBuilderContext Ctx(*this, B, Pred); 458 ExplodedNodeSet Dst; 459 ExprEng.processBranch(Cond, Ctx, Pred, Dst, *(B->succ_begin()), 460 *(B->succ_begin() + 1)); 461 // Enqueue the new frontier onto the worklist. 462 enqueue(Dst); 463 } 464 465 void CoreEngine::HandleCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE, 466 const CFGBlock *B, 467 ExplodedNode *Pred) { 468 assert(B->succ_size() == 2); 469 NodeBuilderContext Ctx(*this, B, Pred); 470 ExplodedNodeSet Dst; 471 ExprEng.processCleanupTemporaryBranch(BTE, Ctx, Pred, Dst, *(B->succ_begin()), 472 *(B->succ_begin() + 1)); 473 // Enqueue the new frontier onto the worklist. 474 enqueue(Dst); 475 } 476 477 void CoreEngine::HandleStaticInit(const DeclStmt *DS, const CFGBlock *B, 478 ExplodedNode *Pred) { 479 assert(B->succ_size() == 2); 480 NodeBuilderContext Ctx(*this, B, Pred); 481 ExplodedNodeSet Dst; 482 ExprEng.processStaticInitializer(DS, Ctx, Pred, Dst, 483 *(B->succ_begin()), *(B->succ_begin()+1)); 484 // Enqueue the new frontier onto the worklist. 485 enqueue(Dst); 486 } 487 488 void CoreEngine::HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, 489 ExplodedNode *Pred) { 490 assert(B); 491 assert(!B->empty()); 492 493 if (StmtIdx == B->size()) 494 HandleBlockExit(B, Pred); 495 else { 496 NodeBuilderContext Ctx(*this, B, Pred); 497 ExprEng.processCFGElement((*B)[StmtIdx], Pred, StmtIdx, &Ctx); 498 } 499 } 500 501 void CoreEngine::HandleVirtualBaseBranch(const CFGBlock *B, 502 ExplodedNode *Pred) { 503 const LocationContext *LCtx = Pred->getLocationContext(); 504 if (const auto *CallerCtor = dyn_cast_or_null<CXXConstructExpr>( 505 LCtx->getStackFrame()->getCallSite())) { 506 switch (CallerCtor->getConstructionKind()) { 507 case CXXConstructExpr::CK_NonVirtualBase: 508 case CXXConstructExpr::CK_VirtualBase: { 509 BlockEdge Loc(B, *B->succ_begin(), LCtx); 510 HandleBlockEdge(Loc, Pred); 511 return; 512 } 513 default: 514 break; 515 } 516 } 517 518 // We either don't see a parent stack frame because we're in the top frame, 519 // or the parent stack frame doesn't initialize our virtual bases. 520 BlockEdge Loc(B, *(B->succ_begin() + 1), LCtx); 521 HandleBlockEdge(Loc, Pred); 522 } 523 524 /// generateNode - Utility method to generate nodes, hook up successors, 525 /// and add nodes to the worklist. 526 void CoreEngine::generateNode(const ProgramPoint &Loc, 527 ProgramStateRef State, 528 ExplodedNode *Pred) { 529 bool IsNew; 530 ExplodedNode *Node = G.getNode(Loc, State, false, &IsNew); 531 532 if (Pred) 533 Node->addPredecessor(Pred, G); // Link 'Node' with its predecessor. 534 else { 535 assert(IsNew); 536 G.addRoot(Node); // 'Node' has no predecessor. Make it a root. 537 } 538 539 // Only add 'Node' to the worklist if it was freshly generated. 540 if (IsNew) WList->enqueue(Node); 541 } 542 543 void CoreEngine::enqueueStmtNode(ExplodedNode *N, 544 const CFGBlock *Block, unsigned Idx) { 545 assert(Block); 546 assert(!N->isSink()); 547 548 // Check if this node entered a callee. 549 if (N->getLocation().getAs<CallEnter>()) { 550 // Still use the index of the CallExpr. It's needed to create the callee 551 // StackFrameContext. 552 WList->enqueue(N, Block, Idx); 553 return; 554 } 555 556 // Do not create extra nodes. Move to the next CFG element. 557 if (N->getLocation().getAs<PostInitializer>() || 558 N->getLocation().getAs<PostImplicitCall>()|| 559 N->getLocation().getAs<LoopExit>()) { 560 WList->enqueue(N, Block, Idx+1); 561 return; 562 } 563 564 if (N->getLocation().getAs<EpsilonPoint>()) { 565 WList->enqueue(N, Block, Idx); 566 return; 567 } 568 569 if ((*Block)[Idx].getKind() == CFGElement::NewAllocator) { 570 WList->enqueue(N, Block, Idx+1); 571 return; 572 } 573 574 // At this point, we know we're processing a normal statement. 575 CFGStmt CS = (*Block)[Idx].castAs<CFGStmt>(); 576 PostStmt Loc(CS.getStmt(), N->getLocationContext()); 577 578 if (Loc == N->getLocation().withTag(nullptr)) { 579 // Note: 'N' should be a fresh node because otherwise it shouldn't be 580 // a member of Deferred. 581 WList->enqueue(N, Block, Idx+1); 582 return; 583 } 584 585 bool IsNew; 586 ExplodedNode *Succ = G.getNode(Loc, N->getState(), false, &IsNew); 587 Succ->addPredecessor(N, G); 588 589 if (IsNew) 590 WList->enqueue(Succ, Block, Idx+1); 591 } 592 593 ExplodedNode *CoreEngine::generateCallExitBeginNode(ExplodedNode *N, 594 const ReturnStmt *RS) { 595 // Create a CallExitBegin node and enqueue it. 596 const auto *LocCtx = cast<StackFrameContext>(N->getLocationContext()); 597 598 // Use the callee location context. 599 CallExitBegin Loc(LocCtx, RS); 600 601 bool isNew; 602 ExplodedNode *Node = G.getNode(Loc, N->getState(), false, &isNew); 603 Node->addPredecessor(N, G); 604 return isNew ? Node : nullptr; 605 } 606 607 void CoreEngine::enqueue(ExplodedNodeSet &Set) { 608 for (const auto I : Set) 609 WList->enqueue(I); 610 } 611 612 void CoreEngine::enqueue(ExplodedNodeSet &Set, 613 const CFGBlock *Block, unsigned Idx) { 614 for (const auto I : Set) 615 enqueueStmtNode(I, Block, Idx); 616 } 617 618 void CoreEngine::enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS) { 619 for (auto I : Set) { 620 // If we are in an inlined call, generate CallExitBegin node. 621 if (I->getLocationContext()->getParent()) { 622 I = generateCallExitBeginNode(I, RS); 623 if (I) 624 WList->enqueue(I); 625 } else { 626 // TODO: We should run remove dead bindings here. 627 G.addEndOfPath(I); 628 NumPathsExplored++; 629 } 630 } 631 } 632 633 void NodeBuilder::anchor() {} 634 635 ExplodedNode* NodeBuilder::generateNodeImpl(const ProgramPoint &Loc, 636 ProgramStateRef State, 637 ExplodedNode *FromN, 638 bool MarkAsSink) { 639 HasGeneratedNodes = true; 640 bool IsNew; 641 ExplodedNode *N = C.Eng.G.getNode(Loc, State, MarkAsSink, &IsNew); 642 N->addPredecessor(FromN, C.Eng.G); 643 Frontier.erase(FromN); 644 645 if (!IsNew) 646 return nullptr; 647 648 if (!MarkAsSink) 649 Frontier.Add(N); 650 651 return N; 652 } 653 654 void NodeBuilderWithSinks::anchor() {} 655 656 StmtNodeBuilder::~StmtNodeBuilder() { 657 if (EnclosingBldr) 658 for (const auto I : Frontier) 659 EnclosingBldr->addNodes(I); 660 } 661 662 void BranchNodeBuilder::anchor() {} 663 664 ExplodedNode *BranchNodeBuilder::generateNode(ProgramStateRef State, 665 bool branch, 666 ExplodedNode *NodePred) { 667 // If the branch has been marked infeasible we should not generate a node. 668 if (!isFeasible(branch)) 669 return nullptr; 670 671 ProgramPoint Loc = BlockEdge(C.Block, branch ? DstT:DstF, 672 NodePred->getLocationContext()); 673 ExplodedNode *Succ = generateNodeImpl(Loc, State, NodePred); 674 return Succ; 675 } 676 677 ExplodedNode* 678 IndirectGotoNodeBuilder::generateNode(const iterator &I, 679 ProgramStateRef St, 680 bool IsSink) { 681 bool IsNew; 682 ExplodedNode *Succ = 683 Eng.G.getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()), 684 St, IsSink, &IsNew); 685 Succ->addPredecessor(Pred, Eng.G); 686 687 if (!IsNew) 688 return nullptr; 689 690 if (!IsSink) 691 Eng.WList->enqueue(Succ); 692 693 return Succ; 694 } 695 696 ExplodedNode* 697 SwitchNodeBuilder::generateCaseStmtNode(const iterator &I, 698 ProgramStateRef St) { 699 bool IsNew; 700 ExplodedNode *Succ = 701 Eng.G.getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()), 702 St, false, &IsNew); 703 Succ->addPredecessor(Pred, Eng.G); 704 if (!IsNew) 705 return nullptr; 706 707 Eng.WList->enqueue(Succ); 708 return Succ; 709 } 710 711 ExplodedNode* 712 SwitchNodeBuilder::generateDefaultCaseNode(ProgramStateRef St, 713 bool IsSink) { 714 // Get the block for the default case. 715 assert(Src->succ_rbegin() != Src->succ_rend()); 716 CFGBlock *DefaultBlock = *Src->succ_rbegin(); 717 718 // Basic correctness check for default blocks that are unreachable and not 719 // caught by earlier stages. 720 if (!DefaultBlock) 721 return nullptr; 722 723 bool IsNew; 724 ExplodedNode *Succ = 725 Eng.G.getNode(BlockEdge(Src, DefaultBlock, Pred->getLocationContext()), 726 St, IsSink, &IsNew); 727 Succ->addPredecessor(Pred, Eng.G); 728 729 if (!IsNew) 730 return nullptr; 731 732 if (!IsSink) 733 Eng.WList->enqueue(Succ); 734 735 return Succ; 736 } 737