CoreEngine.cpp revision 314564
1//==- CoreEngine.cpp - Path-Sensitive Dataflow Engine ------------*- C++ -*-// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines a generic engine for intraprocedural, path-sensitive, 11// dataflow analysis via graph reachability engine. 12// 13//===----------------------------------------------------------------------===// 14 15#include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h" 16#include "clang/AST/Expr.h" 17#include "clang/AST/ExprCXX.h" 18#include "clang/AST/StmtCXX.h" 19#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" 20#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 21#include "llvm/ADT/Statistic.h" 22#include "llvm/Support/Casting.h" 23 24using namespace clang; 25using namespace ento; 26 27#define DEBUG_TYPE "CoreEngine" 28 29STATISTIC(NumSteps, 30 "The # of steps executed."); 31STATISTIC(NumReachedMaxSteps, 32 "The # of times we reached the max number of steps."); 33STATISTIC(NumPathsExplored, 34 "The # of paths explored by the analyzer."); 35 36//===----------------------------------------------------------------------===// 37// Worklist classes for exploration of reachable states. 38//===----------------------------------------------------------------------===// 39 40WorkList::Visitor::~Visitor() {} 41 42namespace { 43class DFS : public WorkList { 44 SmallVector<WorkListUnit,20> Stack; 45public: 46 bool hasWork() const override { 47 return !Stack.empty(); 48 } 49 50 void enqueue(const WorkListUnit& U) override { 51 Stack.push_back(U); 52 } 53 54 WorkListUnit dequeue() override { 55 assert (!Stack.empty()); 56 const WorkListUnit& U = Stack.back(); 57 Stack.pop_back(); // This technically "invalidates" U, but we are fine. 58 return U; 59 } 60 61 bool visitItemsInWorkList(Visitor &V) override { 62 for (SmallVectorImpl<WorkListUnit>::iterator 63 I = Stack.begin(), E = Stack.end(); I != E; ++I) { 64 if (V.visit(*I)) 65 return true; 66 } 67 return false; 68 } 69}; 70 71class BFS : public WorkList { 72 std::deque<WorkListUnit> Queue; 73public: 74 bool hasWork() const override { 75 return !Queue.empty(); 76 } 77 78 void enqueue(const WorkListUnit& U) override { 79 Queue.push_back(U); 80 } 81 82 WorkListUnit dequeue() override { 83 WorkListUnit U = Queue.front(); 84 Queue.pop_front(); 85 return U; 86 } 87 88 bool visitItemsInWorkList(Visitor &V) override { 89 for (std::deque<WorkListUnit>::iterator 90 I = Queue.begin(), E = Queue.end(); I != E; ++I) { 91 if (V.visit(*I)) 92 return true; 93 } 94 return false; 95 } 96}; 97 98} // end anonymous namespace 99 100// Place the dstor for WorkList here because it contains virtual member 101// functions, and we the code for the dstor generated in one compilation unit. 102WorkList::~WorkList() {} 103 104WorkList *WorkList::makeDFS() { return new DFS(); } 105WorkList *WorkList::makeBFS() { return new BFS(); } 106 107namespace { 108 class BFSBlockDFSContents : public WorkList { 109 std::deque<WorkListUnit> Queue; 110 SmallVector<WorkListUnit,20> Stack; 111 public: 112 bool hasWork() const override { 113 return !Queue.empty() || !Stack.empty(); 114 } 115 116 void enqueue(const WorkListUnit& U) override { 117 if (U.getNode()->getLocation().getAs<BlockEntrance>()) 118 Queue.push_front(U); 119 else 120 Stack.push_back(U); 121 } 122 123 WorkListUnit dequeue() override { 124 // Process all basic blocks to completion. 125 if (!Stack.empty()) { 126 const WorkListUnit& U = Stack.back(); 127 Stack.pop_back(); // This technically "invalidates" U, but we are fine. 128 return U; 129 } 130 131 assert(!Queue.empty()); 132 // Don't use const reference. The subsequent pop_back() might make it 133 // unsafe. 134 WorkListUnit U = Queue.front(); 135 Queue.pop_front(); 136 return U; 137 } 138 bool visitItemsInWorkList(Visitor &V) override { 139 for (SmallVectorImpl<WorkListUnit>::iterator 140 I = Stack.begin(), E = Stack.end(); I != E; ++I) { 141 if (V.visit(*I)) 142 return true; 143 } 144 for (std::deque<WorkListUnit>::iterator 145 I = Queue.begin(), E = Queue.end(); I != E; ++I) { 146 if (V.visit(*I)) 147 return true; 148 } 149 return false; 150 } 151 152 }; 153} // end anonymous namespace 154 155WorkList* WorkList::makeBFSBlockDFSContents() { 156 return new BFSBlockDFSContents(); 157} 158 159//===----------------------------------------------------------------------===// 160// Core analysis engine. 161//===----------------------------------------------------------------------===// 162 163/// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps. 164bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps, 165 ProgramStateRef InitState) { 166 167 if (G.num_roots() == 0) { // Initialize the analysis by constructing 168 // the root if none exists. 169 170 const CFGBlock *Entry = &(L->getCFG()->getEntry()); 171 172 assert (Entry->empty() && 173 "Entry block must be empty."); 174 175 assert (Entry->succ_size() == 1 && 176 "Entry block must have 1 successor."); 177 178 // Mark the entry block as visited. 179 FunctionSummaries->markVisitedBasicBlock(Entry->getBlockID(), 180 L->getDecl(), 181 L->getCFG()->getNumBlockIDs()); 182 183 // Get the solitary successor. 184 const CFGBlock *Succ = *(Entry->succ_begin()); 185 186 // Construct an edge representing the 187 // starting location in the function. 188 BlockEdge StartLoc(Entry, Succ, L); 189 190 // Set the current block counter to being empty. 191 WList->setBlockCounter(BCounterFactory.GetEmptyCounter()); 192 193 if (!InitState) 194 InitState = SubEng.getInitialState(L); 195 196 bool IsNew; 197 ExplodedNode *Node = G.getNode(StartLoc, InitState, false, &IsNew); 198 assert (IsNew); 199 G.addRoot(Node); 200 201 NodeBuilderContext BuilderCtx(*this, StartLoc.getDst(), Node); 202 ExplodedNodeSet DstBegin; 203 SubEng.processBeginOfFunction(BuilderCtx, Node, DstBegin, StartLoc); 204 205 enqueue(DstBegin); 206 } 207 208 // Check if we have a steps limit 209 bool UnlimitedSteps = Steps == 0; 210 // Cap our pre-reservation in the event that the user specifies 211 // a very large number of maximum steps. 212 const unsigned PreReservationCap = 4000000; 213 if(!UnlimitedSteps) 214 G.reserve(std::min(Steps,PreReservationCap)); 215 216 while (WList->hasWork()) { 217 if (!UnlimitedSteps) { 218 if (Steps == 0) { 219 NumReachedMaxSteps++; 220 break; 221 } 222 --Steps; 223 } 224 225 NumSteps++; 226 227 const WorkListUnit& WU = WList->dequeue(); 228 229 // Set the current block counter. 230 WList->setBlockCounter(WU.getBlockCounter()); 231 232 // Retrieve the node. 233 ExplodedNode *Node = WU.getNode(); 234 235 dispatchWorkItem(Node, Node->getLocation(), WU); 236 } 237 SubEng.processEndWorklist(hasWorkRemaining()); 238 return WList->hasWork(); 239} 240 241void CoreEngine::dispatchWorkItem(ExplodedNode* Pred, ProgramPoint Loc, 242 const WorkListUnit& WU) { 243 // Dispatch on the location type. 244 switch (Loc.getKind()) { 245 case ProgramPoint::BlockEdgeKind: 246 HandleBlockEdge(Loc.castAs<BlockEdge>(), Pred); 247 break; 248 249 case ProgramPoint::BlockEntranceKind: 250 HandleBlockEntrance(Loc.castAs<BlockEntrance>(), Pred); 251 break; 252 253 case ProgramPoint::BlockExitKind: 254 assert (false && "BlockExit location never occur in forward analysis."); 255 break; 256 257 case ProgramPoint::CallEnterKind: { 258 HandleCallEnter(Loc.castAs<CallEnter>(), Pred); 259 break; 260 } 261 262 case ProgramPoint::CallExitBeginKind: 263 SubEng.processCallExit(Pred); 264 break; 265 266 case ProgramPoint::EpsilonKind: { 267 assert(Pred->hasSinglePred() && 268 "Assume epsilon has exactly one predecessor by construction"); 269 ExplodedNode *PNode = Pred->getFirstPred(); 270 dispatchWorkItem(Pred, PNode->getLocation(), WU); 271 break; 272 } 273 default: 274 assert(Loc.getAs<PostStmt>() || 275 Loc.getAs<PostInitializer>() || 276 Loc.getAs<PostImplicitCall>() || 277 Loc.getAs<CallExitEnd>()); 278 HandlePostStmt(WU.getBlock(), WU.getIndex(), Pred); 279 break; 280 } 281} 282 283bool CoreEngine::ExecuteWorkListWithInitialState(const LocationContext *L, 284 unsigned Steps, 285 ProgramStateRef InitState, 286 ExplodedNodeSet &Dst) { 287 bool DidNotFinish = ExecuteWorkList(L, Steps, InitState); 288 for (ExplodedGraph::eop_iterator I = G.eop_begin(), E = G.eop_end(); I != E; 289 ++I) { 290 Dst.Add(*I); 291 } 292 return DidNotFinish; 293} 294 295void CoreEngine::HandleBlockEdge(const BlockEdge &L, ExplodedNode *Pred) { 296 297 const CFGBlock *Blk = L.getDst(); 298 NodeBuilderContext BuilderCtx(*this, Blk, Pred); 299 300 // Mark this block as visited. 301 const LocationContext *LC = Pred->getLocationContext(); 302 FunctionSummaries->markVisitedBasicBlock(Blk->getBlockID(), 303 LC->getDecl(), 304 LC->getCFG()->getNumBlockIDs()); 305 306 // Check if we are entering the EXIT block. 307 if (Blk == &(L.getLocationContext()->getCFG()->getExit())) { 308 309 assert (L.getLocationContext()->getCFG()->getExit().size() == 0 310 && "EXIT block cannot contain Stmts."); 311 312 // Get return statement.. 313 const ReturnStmt *RS = nullptr; 314 if (!L.getSrc()->empty()) { 315 if (Optional<CFGStmt> LastStmt = L.getSrc()->back().getAs<CFGStmt>()) { 316 if ((RS = dyn_cast<ReturnStmt>(LastStmt->getStmt()))) { 317 if (!RS->getRetValue()) 318 RS = nullptr; 319 } 320 } 321 } 322 323 // Process the final state transition. 324 SubEng.processEndOfFunction(BuilderCtx, Pred, RS); 325 326 // This path is done. Don't enqueue any more nodes. 327 return; 328 } 329 330 // Call into the SubEngine to process entering the CFGBlock. 331 ExplodedNodeSet dstNodes; 332 BlockEntrance BE(Blk, Pred->getLocationContext()); 333 NodeBuilderWithSinks nodeBuilder(Pred, dstNodes, BuilderCtx, BE); 334 SubEng.processCFGBlockEntrance(L, nodeBuilder, Pred); 335 336 // Auto-generate a node. 337 if (!nodeBuilder.hasGeneratedNodes()) { 338 nodeBuilder.generateNode(Pred->State, Pred); 339 } 340 341 // Enqueue nodes onto the worklist. 342 enqueue(dstNodes); 343} 344 345void CoreEngine::HandleBlockEntrance(const BlockEntrance &L, 346 ExplodedNode *Pred) { 347 348 // Increment the block counter. 349 const LocationContext *LC = Pred->getLocationContext(); 350 unsigned BlockId = L.getBlock()->getBlockID(); 351 BlockCounter Counter = WList->getBlockCounter(); 352 Counter = BCounterFactory.IncrementCount(Counter, LC->getCurrentStackFrame(), 353 BlockId); 354 WList->setBlockCounter(Counter); 355 356 // Process the entrance of the block. 357 if (Optional<CFGElement> E = L.getFirstElement()) { 358 NodeBuilderContext Ctx(*this, L.getBlock(), Pred); 359 SubEng.processCFGElement(*E, Pred, 0, &Ctx); 360 } 361 else 362 HandleBlockExit(L.getBlock(), Pred); 363} 364 365void CoreEngine::HandleBlockExit(const CFGBlock * B, ExplodedNode *Pred) { 366 367 if (const Stmt *Term = B->getTerminator()) { 368 switch (Term->getStmtClass()) { 369 default: 370 llvm_unreachable("Analysis for this terminator not implemented."); 371 372 case Stmt::CXXBindTemporaryExprClass: 373 HandleCleanupTemporaryBranch( 374 cast<CXXBindTemporaryExpr>(B->getTerminator().getStmt()), B, Pred); 375 return; 376 377 // Model static initializers. 378 case Stmt::DeclStmtClass: 379 HandleStaticInit(cast<DeclStmt>(Term), B, Pred); 380 return; 381 382 case Stmt::BinaryOperatorClass: // '&&' and '||' 383 HandleBranch(cast<BinaryOperator>(Term)->getLHS(), Term, B, Pred); 384 return; 385 386 case Stmt::BinaryConditionalOperatorClass: 387 case Stmt::ConditionalOperatorClass: 388 HandleBranch(cast<AbstractConditionalOperator>(Term)->getCond(), 389 Term, B, Pred); 390 return; 391 392 // FIXME: Use constant-folding in CFG construction to simplify this 393 // case. 394 395 case Stmt::ChooseExprClass: 396 HandleBranch(cast<ChooseExpr>(Term)->getCond(), Term, B, Pred); 397 return; 398 399 case Stmt::CXXTryStmtClass: { 400 // Generate a node for each of the successors. 401 // Our logic for EH analysis can certainly be improved. 402 for (CFGBlock::const_succ_iterator it = B->succ_begin(), 403 et = B->succ_end(); it != et; ++it) { 404 if (const CFGBlock *succ = *it) { 405 generateNode(BlockEdge(B, succ, Pred->getLocationContext()), 406 Pred->State, Pred); 407 } 408 } 409 return; 410 } 411 412 case Stmt::DoStmtClass: 413 HandleBranch(cast<DoStmt>(Term)->getCond(), Term, B, Pred); 414 return; 415 416 case Stmt::CXXForRangeStmtClass: 417 HandleBranch(cast<CXXForRangeStmt>(Term)->getCond(), Term, B, Pred); 418 return; 419 420 case Stmt::ForStmtClass: 421 HandleBranch(cast<ForStmt>(Term)->getCond(), Term, B, Pred); 422 return; 423 424 case Stmt::ContinueStmtClass: 425 case Stmt::BreakStmtClass: 426 case Stmt::GotoStmtClass: 427 break; 428 429 case Stmt::IfStmtClass: 430 HandleBranch(cast<IfStmt>(Term)->getCond(), Term, B, Pred); 431 return; 432 433 case Stmt::IndirectGotoStmtClass: { 434 // Only 1 successor: the indirect goto dispatch block. 435 assert (B->succ_size() == 1); 436 437 IndirectGotoNodeBuilder 438 builder(Pred, B, cast<IndirectGotoStmt>(Term)->getTarget(), 439 *(B->succ_begin()), this); 440 441 SubEng.processIndirectGoto(builder); 442 return; 443 } 444 445 case Stmt::ObjCForCollectionStmtClass: { 446 // In the case of ObjCForCollectionStmt, it appears twice in a CFG: 447 // 448 // (1) inside a basic block, which represents the binding of the 449 // 'element' variable to a value. 450 // (2) in a terminator, which represents the branch. 451 // 452 // For (1), subengines will bind a value (i.e., 0 or 1) indicating 453 // whether or not collection contains any more elements. We cannot 454 // just test to see if the element is nil because a container can 455 // contain nil elements. 456 HandleBranch(Term, Term, B, Pred); 457 return; 458 } 459 460 case Stmt::SwitchStmtClass: { 461 SwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(), 462 this); 463 464 SubEng.processSwitch(builder); 465 return; 466 } 467 468 case Stmt::WhileStmtClass: 469 HandleBranch(cast<WhileStmt>(Term)->getCond(), Term, B, Pred); 470 return; 471 } 472 } 473 474 assert (B->succ_size() == 1 && 475 "Blocks with no terminator should have at most 1 successor."); 476 477 generateNode(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()), 478 Pred->State, Pred); 479} 480 481void CoreEngine::HandleCallEnter(const CallEnter &CE, ExplodedNode *Pred) { 482 NodeBuilderContext BuilderCtx(*this, CE.getEntry(), Pred); 483 SubEng.processCallEnter(BuilderCtx, CE, Pred); 484} 485 486void CoreEngine::HandleBranch(const Stmt *Cond, const Stmt *Term, 487 const CFGBlock * B, ExplodedNode *Pred) { 488 assert(B->succ_size() == 2); 489 NodeBuilderContext Ctx(*this, B, Pred); 490 ExplodedNodeSet Dst; 491 SubEng.processBranch(Cond, Term, Ctx, Pred, Dst, 492 *(B->succ_begin()), *(B->succ_begin()+1)); 493 // Enqueue the new frontier onto the worklist. 494 enqueue(Dst); 495} 496 497void CoreEngine::HandleCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE, 498 const CFGBlock *B, 499 ExplodedNode *Pred) { 500 assert(B->succ_size() == 2); 501 NodeBuilderContext Ctx(*this, B, Pred); 502 ExplodedNodeSet Dst; 503 SubEng.processCleanupTemporaryBranch(BTE, Ctx, Pred, Dst, *(B->succ_begin()), 504 *(B->succ_begin() + 1)); 505 // Enqueue the new frontier onto the worklist. 506 enqueue(Dst); 507} 508 509void CoreEngine::HandleStaticInit(const DeclStmt *DS, const CFGBlock *B, 510 ExplodedNode *Pred) { 511 assert(B->succ_size() == 2); 512 NodeBuilderContext Ctx(*this, B, Pred); 513 ExplodedNodeSet Dst; 514 SubEng.processStaticInitializer(DS, Ctx, Pred, Dst, 515 *(B->succ_begin()), *(B->succ_begin()+1)); 516 // Enqueue the new frontier onto the worklist. 517 enqueue(Dst); 518} 519 520 521void CoreEngine::HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, 522 ExplodedNode *Pred) { 523 assert(B); 524 assert(!B->empty()); 525 526 if (StmtIdx == B->size()) 527 HandleBlockExit(B, Pred); 528 else { 529 NodeBuilderContext Ctx(*this, B, Pred); 530 SubEng.processCFGElement((*B)[StmtIdx], Pred, StmtIdx, &Ctx); 531 } 532} 533 534/// generateNode - Utility method to generate nodes, hook up successors, 535/// and add nodes to the worklist. 536void CoreEngine::generateNode(const ProgramPoint &Loc, 537 ProgramStateRef State, 538 ExplodedNode *Pred) { 539 540 bool IsNew; 541 ExplodedNode *Node = G.getNode(Loc, State, false, &IsNew); 542 543 if (Pred) 544 Node->addPredecessor(Pred, G); // Link 'Node' with its predecessor. 545 else { 546 assert (IsNew); 547 G.addRoot(Node); // 'Node' has no predecessor. Make it a root. 548 } 549 550 // Only add 'Node' to the worklist if it was freshly generated. 551 if (IsNew) WList->enqueue(Node); 552} 553 554void CoreEngine::enqueueStmtNode(ExplodedNode *N, 555 const CFGBlock *Block, unsigned Idx) { 556 assert(Block); 557 assert (!N->isSink()); 558 559 // Check if this node entered a callee. 560 if (N->getLocation().getAs<CallEnter>()) { 561 // Still use the index of the CallExpr. It's needed to create the callee 562 // StackFrameContext. 563 WList->enqueue(N, Block, Idx); 564 return; 565 } 566 567 // Do not create extra nodes. Move to the next CFG element. 568 if (N->getLocation().getAs<PostInitializer>() || 569 N->getLocation().getAs<PostImplicitCall>()) { 570 WList->enqueue(N, Block, Idx+1); 571 return; 572 } 573 574 if (N->getLocation().getAs<EpsilonPoint>()) { 575 WList->enqueue(N, Block, Idx); 576 return; 577 } 578 579 if ((*Block)[Idx].getKind() == CFGElement::NewAllocator) { 580 WList->enqueue(N, Block, Idx+1); 581 return; 582 } 583 584 // At this point, we know we're processing a normal statement. 585 CFGStmt CS = (*Block)[Idx].castAs<CFGStmt>(); 586 PostStmt Loc(CS.getStmt(), N->getLocationContext()); 587 588 if (Loc == N->getLocation().withTag(nullptr)) { 589 // Note: 'N' should be a fresh node because otherwise it shouldn't be 590 // a member of Deferred. 591 WList->enqueue(N, Block, Idx+1); 592 return; 593 } 594 595 bool IsNew; 596 ExplodedNode *Succ = G.getNode(Loc, N->getState(), false, &IsNew); 597 Succ->addPredecessor(N, G); 598 599 if (IsNew) 600 WList->enqueue(Succ, Block, Idx+1); 601} 602 603ExplodedNode *CoreEngine::generateCallExitBeginNode(ExplodedNode *N, 604 const ReturnStmt *RS) { 605 // Create a CallExitBegin node and enqueue it. 606 const StackFrameContext *LocCtx 607 = cast<StackFrameContext>(N->getLocationContext()); 608 609 // Use the callee location context. 610 CallExitBegin Loc(LocCtx, RS); 611 612 bool isNew; 613 ExplodedNode *Node = G.getNode(Loc, N->getState(), false, &isNew); 614 Node->addPredecessor(N, G); 615 return isNew ? Node : nullptr; 616} 617 618 619void CoreEngine::enqueue(ExplodedNodeSet &Set) { 620 for (ExplodedNodeSet::iterator I = Set.begin(), 621 E = Set.end(); I != E; ++I) { 622 WList->enqueue(*I); 623 } 624} 625 626void CoreEngine::enqueue(ExplodedNodeSet &Set, 627 const CFGBlock *Block, unsigned Idx) { 628 for (ExplodedNodeSet::iterator I = Set.begin(), 629 E = Set.end(); I != E; ++I) { 630 enqueueStmtNode(*I, Block, Idx); 631 } 632} 633 634void CoreEngine::enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS) { 635 for (ExplodedNodeSet::iterator I = Set.begin(), E = Set.end(); I != E; ++I) { 636 ExplodedNode *N = *I; 637 // If we are in an inlined call, generate CallExitBegin node. 638 if (N->getLocationContext()->getParent()) { 639 N = generateCallExitBeginNode(N, RS); 640 if (N) 641 WList->enqueue(N); 642 } else { 643 // TODO: We should run remove dead bindings here. 644 G.addEndOfPath(N); 645 NumPathsExplored++; 646 } 647 } 648} 649 650 651void NodeBuilder::anchor() { } 652 653ExplodedNode* NodeBuilder::generateNodeImpl(const ProgramPoint &Loc, 654 ProgramStateRef State, 655 ExplodedNode *FromN, 656 bool MarkAsSink) { 657 HasGeneratedNodes = true; 658 bool IsNew; 659 ExplodedNode *N = C.Eng.G.getNode(Loc, State, MarkAsSink, &IsNew); 660 N->addPredecessor(FromN, C.Eng.G); 661 Frontier.erase(FromN); 662 663 if (!IsNew) 664 return nullptr; 665 666 if (!MarkAsSink) 667 Frontier.Add(N); 668 669 return N; 670} 671 672void NodeBuilderWithSinks::anchor() { } 673 674StmtNodeBuilder::~StmtNodeBuilder() { 675 if (EnclosingBldr) 676 for (ExplodedNodeSet::iterator I = Frontier.begin(), 677 E = Frontier.end(); I != E; ++I ) 678 EnclosingBldr->addNodes(*I); 679} 680 681void BranchNodeBuilder::anchor() { } 682 683ExplodedNode *BranchNodeBuilder::generateNode(ProgramStateRef State, 684 bool branch, 685 ExplodedNode *NodePred) { 686 // If the branch has been marked infeasible we should not generate a node. 687 if (!isFeasible(branch)) 688 return nullptr; 689 690 ProgramPoint Loc = BlockEdge(C.Block, branch ? DstT:DstF, 691 NodePred->getLocationContext()); 692 ExplodedNode *Succ = generateNodeImpl(Loc, State, NodePred); 693 return Succ; 694} 695 696ExplodedNode* 697IndirectGotoNodeBuilder::generateNode(const iterator &I, 698 ProgramStateRef St, 699 bool IsSink) { 700 bool IsNew; 701 ExplodedNode *Succ = 702 Eng.G.getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()), 703 St, IsSink, &IsNew); 704 Succ->addPredecessor(Pred, Eng.G); 705 706 if (!IsNew) 707 return nullptr; 708 709 if (!IsSink) 710 Eng.WList->enqueue(Succ); 711 712 return Succ; 713} 714 715 716ExplodedNode* 717SwitchNodeBuilder::generateCaseStmtNode(const iterator &I, 718 ProgramStateRef St) { 719 720 bool IsNew; 721 ExplodedNode *Succ = 722 Eng.G.getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()), 723 St, false, &IsNew); 724 Succ->addPredecessor(Pred, Eng.G); 725 if (!IsNew) 726 return nullptr; 727 728 Eng.WList->enqueue(Succ); 729 return Succ; 730} 731 732 733ExplodedNode* 734SwitchNodeBuilder::generateDefaultCaseNode(ProgramStateRef St, 735 bool IsSink) { 736 // Get the block for the default case. 737 assert(Src->succ_rbegin() != Src->succ_rend()); 738 CFGBlock *DefaultBlock = *Src->succ_rbegin(); 739 740 // Sanity check for default blocks that are unreachable and not caught 741 // by earlier stages. 742 if (!DefaultBlock) 743 return nullptr; 744 745 bool IsNew; 746 ExplodedNode *Succ = 747 Eng.G.getNode(BlockEdge(Src, DefaultBlock, Pred->getLocationContext()), 748 St, IsSink, &IsNew); 749 Succ->addPredecessor(Pred, Eng.G); 750 751 if (!IsNew) 752 return nullptr; 753 754 if (!IsSink) 755 Eng.WList->enqueue(Succ); 756 757 return Succ; 758} 759