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