CoreEngine.cpp revision 327952
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 Loc.getAs<LoopExit>()); 279 HandlePostStmt(WU.getBlock(), WU.getIndex(), Pred); 280 break; 281 } 282} 283 284bool 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 296void 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 // Get return statement.. 314 const ReturnStmt *RS = nullptr; 315 if (!L.getSrc()->empty()) { 316 if (Optional<CFGStmt> LastStmt = L.getSrc()->back().getAs<CFGStmt>()) { 317 if ((RS = dyn_cast<ReturnStmt>(LastStmt->getStmt()))) { 318 if (!RS->getRetValue()) 319 RS = nullptr; 320 } 321 } 322 } 323 324 // Process the final state transition. 325 SubEng.processEndOfFunction(BuilderCtx, Pred, RS); 326 327 // This path is done. Don't enqueue any more nodes. 328 return; 329 } 330 331 // Call into the SubEngine to process entering the CFGBlock. 332 ExplodedNodeSet dstNodes; 333 BlockEntrance BE(Blk, Pred->getLocationContext()); 334 NodeBuilderWithSinks nodeBuilder(Pred, dstNodes, BuilderCtx, BE); 335 SubEng.processCFGBlockEntrance(L, nodeBuilder, Pred); 336 337 // Auto-generate a node. 338 if (!nodeBuilder.hasGeneratedNodes()) { 339 nodeBuilder.generateNode(Pred->State, Pred); 340 } 341 342 // Enqueue nodes onto the worklist. 343 enqueue(dstNodes); 344} 345 346void CoreEngine::HandleBlockEntrance(const BlockEntrance &L, 347 ExplodedNode *Pred) { 348 349 // Increment the block counter. 350 const LocationContext *LC = Pred->getLocationContext(); 351 unsigned BlockId = L.getBlock()->getBlockID(); 352 BlockCounter Counter = WList->getBlockCounter(); 353 Counter = BCounterFactory.IncrementCount(Counter, LC->getCurrentStackFrame(), 354 BlockId); 355 WList->setBlockCounter(Counter); 356 357 // Process the entrance of the block. 358 if (Optional<CFGElement> E = L.getFirstElement()) { 359 NodeBuilderContext Ctx(*this, L.getBlock(), Pred); 360 SubEng.processCFGElement(*E, Pred, 0, &Ctx); 361 } 362 else 363 HandleBlockExit(L.getBlock(), Pred); 364} 365 366void CoreEngine::HandleBlockExit(const CFGBlock * B, ExplodedNode *Pred) { 367 368 if (const Stmt *Term = B->getTerminator()) { 369 switch (Term->getStmtClass()) { 370 default: 371 llvm_unreachable("Analysis for this terminator not implemented."); 372 373 case Stmt::CXXBindTemporaryExprClass: 374 HandleCleanupTemporaryBranch( 375 cast<CXXBindTemporaryExpr>(B->getTerminator().getStmt()), B, Pred); 376 return; 377 378 // Model static initializers. 379 case Stmt::DeclStmtClass: 380 HandleStaticInit(cast<DeclStmt>(Term), B, Pred); 381 return; 382 383 case Stmt::BinaryOperatorClass: // '&&' and '||' 384 HandleBranch(cast<BinaryOperator>(Term)->getLHS(), Term, B, Pred); 385 return; 386 387 case Stmt::BinaryConditionalOperatorClass: 388 case Stmt::ConditionalOperatorClass: 389 HandleBranch(cast<AbstractConditionalOperator>(Term)->getCond(), 390 Term, B, Pred); 391 return; 392 393 // FIXME: Use constant-folding in CFG construction to simplify this 394 // case. 395 396 case Stmt::ChooseExprClass: 397 HandleBranch(cast<ChooseExpr>(Term)->getCond(), Term, B, Pred); 398 return; 399 400 case Stmt::CXXTryStmtClass: { 401 // Generate a node for each of the successors. 402 // Our logic for EH analysis can certainly be improved. 403 for (CFGBlock::const_succ_iterator it = B->succ_begin(), 404 et = B->succ_end(); it != et; ++it) { 405 if (const CFGBlock *succ = *it) { 406 generateNode(BlockEdge(B, succ, Pred->getLocationContext()), 407 Pred->State, Pred); 408 } 409 } 410 return; 411 } 412 413 case Stmt::DoStmtClass: 414 HandleBranch(cast<DoStmt>(Term)->getCond(), Term, B, Pred); 415 return; 416 417 case Stmt::CXXForRangeStmtClass: 418 HandleBranch(cast<CXXForRangeStmt>(Term)->getCond(), Term, B, Pred); 419 return; 420 421 case Stmt::ForStmtClass: 422 HandleBranch(cast<ForStmt>(Term)->getCond(), Term, B, Pred); 423 return; 424 425 case Stmt::ContinueStmtClass: 426 case Stmt::BreakStmtClass: 427 case Stmt::GotoStmtClass: 428 break; 429 430 case Stmt::IfStmtClass: 431 HandleBranch(cast<IfStmt>(Term)->getCond(), Term, B, Pred); 432 return; 433 434 case Stmt::IndirectGotoStmtClass: { 435 // Only 1 successor: the indirect goto dispatch block. 436 assert (B->succ_size() == 1); 437 438 IndirectGotoNodeBuilder 439 builder(Pred, B, cast<IndirectGotoStmt>(Term)->getTarget(), 440 *(B->succ_begin()), this); 441 442 SubEng.processIndirectGoto(builder); 443 return; 444 } 445 446 case Stmt::ObjCForCollectionStmtClass: { 447 // In the case of ObjCForCollectionStmt, it appears twice in a CFG: 448 // 449 // (1) inside a basic block, which represents the binding of the 450 // 'element' variable to a value. 451 // (2) in a terminator, which represents the branch. 452 // 453 // For (1), subengines will bind a value (i.e., 0 or 1) indicating 454 // whether or not collection contains any more elements. We cannot 455 // just test to see if the element is nil because a container can 456 // contain nil elements. 457 HandleBranch(Term, Term, B, Pred); 458 return; 459 } 460 461 case Stmt::SwitchStmtClass: { 462 SwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(), 463 this); 464 465 SubEng.processSwitch(builder); 466 return; 467 } 468 469 case Stmt::WhileStmtClass: 470 HandleBranch(cast<WhileStmt>(Term)->getCond(), Term, B, Pred); 471 return; 472 } 473 } 474 475 assert (B->succ_size() == 1 && 476 "Blocks with no terminator should have at most 1 successor."); 477 478 generateNode(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()), 479 Pred->State, Pred); 480} 481 482void CoreEngine::HandleCallEnter(const CallEnter &CE, ExplodedNode *Pred) { 483 NodeBuilderContext BuilderCtx(*this, CE.getEntry(), Pred); 484 SubEng.processCallEnter(BuilderCtx, CE, Pred); 485} 486 487void CoreEngine::HandleBranch(const Stmt *Cond, const Stmt *Term, 488 const CFGBlock * B, ExplodedNode *Pred) { 489 assert(B->succ_size() == 2); 490 NodeBuilderContext Ctx(*this, B, Pred); 491 ExplodedNodeSet Dst; 492 SubEng.processBranch(Cond, Term, Ctx, Pred, Dst, 493 *(B->succ_begin()), *(B->succ_begin()+1)); 494 // Enqueue the new frontier onto the worklist. 495 enqueue(Dst); 496} 497 498void CoreEngine::HandleCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE, 499 const CFGBlock *B, 500 ExplodedNode *Pred) { 501 assert(B->succ_size() == 2); 502 NodeBuilderContext Ctx(*this, B, Pred); 503 ExplodedNodeSet Dst; 504 SubEng.processCleanupTemporaryBranch(BTE, Ctx, Pred, Dst, *(B->succ_begin()), 505 *(B->succ_begin() + 1)); 506 // Enqueue the new frontier onto the worklist. 507 enqueue(Dst); 508} 509 510void CoreEngine::HandleStaticInit(const DeclStmt *DS, const CFGBlock *B, 511 ExplodedNode *Pred) { 512 assert(B->succ_size() == 2); 513 NodeBuilderContext Ctx(*this, B, Pred); 514 ExplodedNodeSet Dst; 515 SubEng.processStaticInitializer(DS, Ctx, Pred, Dst, 516 *(B->succ_begin()), *(B->succ_begin()+1)); 517 // Enqueue the new frontier onto the worklist. 518 enqueue(Dst); 519} 520 521 522void CoreEngine::HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, 523 ExplodedNode *Pred) { 524 assert(B); 525 assert(!B->empty()); 526 527 if (StmtIdx == B->size()) 528 HandleBlockExit(B, Pred); 529 else { 530 NodeBuilderContext Ctx(*this, B, Pred); 531 SubEng.processCFGElement((*B)[StmtIdx], Pred, StmtIdx, &Ctx); 532 } 533} 534 535/// generateNode - Utility method to generate nodes, hook up successors, 536/// and add nodes to the worklist. 537void CoreEngine::generateNode(const ProgramPoint &Loc, 538 ProgramStateRef State, 539 ExplodedNode *Pred) { 540 541 bool IsNew; 542 ExplodedNode *Node = G.getNode(Loc, State, false, &IsNew); 543 544 if (Pred) 545 Node->addPredecessor(Pred, G); // Link 'Node' with its predecessor. 546 else { 547 assert (IsNew); 548 G.addRoot(Node); // 'Node' has no predecessor. Make it a root. 549 } 550 551 // Only add 'Node' to the worklist if it was freshly generated. 552 if (IsNew) WList->enqueue(Node); 553} 554 555void CoreEngine::enqueueStmtNode(ExplodedNode *N, 556 const CFGBlock *Block, unsigned Idx) { 557 assert(Block); 558 assert (!N->isSink()); 559 560 // Check if this node entered a callee. 561 if (N->getLocation().getAs<CallEnter>()) { 562 // Still use the index of the CallExpr. It's needed to create the callee 563 // StackFrameContext. 564 WList->enqueue(N, Block, Idx); 565 return; 566 } 567 568 // Do not create extra nodes. Move to the next CFG element. 569 if (N->getLocation().getAs<PostInitializer>() || 570 N->getLocation().getAs<PostImplicitCall>()|| 571 N->getLocation().getAs<LoopExit>()) { 572 WList->enqueue(N, Block, Idx+1); 573 return; 574 } 575 576 if (N->getLocation().getAs<EpsilonPoint>()) { 577 WList->enqueue(N, Block, Idx); 578 return; 579 } 580 581 if ((*Block)[Idx].getKind() == CFGElement::NewAllocator) { 582 WList->enqueue(N, Block, Idx+1); 583 return; 584 } 585 586 // At this point, we know we're processing a normal statement. 587 CFGStmt CS = (*Block)[Idx].castAs<CFGStmt>(); 588 PostStmt Loc(CS.getStmt(), N->getLocationContext()); 589 590 if (Loc == N->getLocation().withTag(nullptr)) { 591 // Note: 'N' should be a fresh node because otherwise it shouldn't be 592 // a member of Deferred. 593 WList->enqueue(N, Block, Idx+1); 594 return; 595 } 596 597 bool IsNew; 598 ExplodedNode *Succ = G.getNode(Loc, N->getState(), false, &IsNew); 599 Succ->addPredecessor(N, G); 600 601 if (IsNew) 602 WList->enqueue(Succ, Block, Idx+1); 603} 604 605ExplodedNode *CoreEngine::generateCallExitBeginNode(ExplodedNode *N, 606 const ReturnStmt *RS) { 607 // Create a CallExitBegin node and enqueue it. 608 const StackFrameContext *LocCtx 609 = cast<StackFrameContext>(N->getLocationContext()); 610 611 // Use the callee location context. 612 CallExitBegin Loc(LocCtx, RS); 613 614 bool isNew; 615 ExplodedNode *Node = G.getNode(Loc, N->getState(), false, &isNew); 616 Node->addPredecessor(N, G); 617 return isNew ? Node : nullptr; 618} 619 620 621void CoreEngine::enqueue(ExplodedNodeSet &Set) { 622 for (ExplodedNodeSet::iterator I = Set.begin(), 623 E = Set.end(); I != E; ++I) { 624 WList->enqueue(*I); 625 } 626} 627 628void CoreEngine::enqueue(ExplodedNodeSet &Set, 629 const CFGBlock *Block, unsigned Idx) { 630 for (ExplodedNodeSet::iterator I = Set.begin(), 631 E = Set.end(); I != E; ++I) { 632 enqueueStmtNode(*I, Block, Idx); 633 } 634} 635 636void CoreEngine::enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS) { 637 for (ExplodedNodeSet::iterator I = Set.begin(), E = Set.end(); I != E; ++I) { 638 ExplodedNode *N = *I; 639 // If we are in an inlined call, generate CallExitBegin node. 640 if (N->getLocationContext()->getParent()) { 641 N = generateCallExitBeginNode(N, RS); 642 if (N) 643 WList->enqueue(N); 644 } else { 645 // TODO: We should run remove dead bindings here. 646 G.addEndOfPath(N); 647 NumPathsExplored++; 648 } 649 } 650} 651 652 653void NodeBuilder::anchor() { } 654 655ExplodedNode* NodeBuilder::generateNodeImpl(const ProgramPoint &Loc, 656 ProgramStateRef State, 657 ExplodedNode *FromN, 658 bool MarkAsSink) { 659 HasGeneratedNodes = true; 660 bool IsNew; 661 ExplodedNode *N = C.Eng.G.getNode(Loc, State, MarkAsSink, &IsNew); 662 N->addPredecessor(FromN, C.Eng.G); 663 Frontier.erase(FromN); 664 665 if (!IsNew) 666 return nullptr; 667 668 if (!MarkAsSink) 669 Frontier.Add(N); 670 671 return N; 672} 673 674void NodeBuilderWithSinks::anchor() { } 675 676StmtNodeBuilder::~StmtNodeBuilder() { 677 if (EnclosingBldr) 678 for (ExplodedNodeSet::iterator I = Frontier.begin(), 679 E = Frontier.end(); I != E; ++I ) 680 EnclosingBldr->addNodes(*I); 681} 682 683void BranchNodeBuilder::anchor() { } 684 685ExplodedNode *BranchNodeBuilder::generateNode(ProgramStateRef State, 686 bool branch, 687 ExplodedNode *NodePred) { 688 // If the branch has been marked infeasible we should not generate a node. 689 if (!isFeasible(branch)) 690 return nullptr; 691 692 ProgramPoint Loc = BlockEdge(C.Block, branch ? DstT:DstF, 693 NodePred->getLocationContext()); 694 ExplodedNode *Succ = generateNodeImpl(Loc, State, NodePred); 695 return Succ; 696} 697 698ExplodedNode* 699IndirectGotoNodeBuilder::generateNode(const iterator &I, 700 ProgramStateRef St, 701 bool IsSink) { 702 bool IsNew; 703 ExplodedNode *Succ = 704 Eng.G.getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()), 705 St, IsSink, &IsNew); 706 Succ->addPredecessor(Pred, Eng.G); 707 708 if (!IsNew) 709 return nullptr; 710 711 if (!IsSink) 712 Eng.WList->enqueue(Succ); 713 714 return Succ; 715} 716 717 718ExplodedNode* 719SwitchNodeBuilder::generateCaseStmtNode(const iterator &I, 720 ProgramStateRef St) { 721 722 bool IsNew; 723 ExplodedNode *Succ = 724 Eng.G.getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()), 725 St, false, &IsNew); 726 Succ->addPredecessor(Pred, Eng.G); 727 if (!IsNew) 728 return nullptr; 729 730 Eng.WList->enqueue(Succ); 731 return Succ; 732} 733 734 735ExplodedNode* 736SwitchNodeBuilder::generateDefaultCaseNode(ProgramStateRef St, 737 bool IsSink) { 738 // Get the block for the default case. 739 assert(Src->succ_rbegin() != Src->succ_rend()); 740 CFGBlock *DefaultBlock = *Src->succ_rbegin(); 741 742 // Sanity check for default blocks that are unreachable and not caught 743 // by earlier stages. 744 if (!DefaultBlock) 745 return nullptr; 746 747 bool IsNew; 748 ExplodedNode *Succ = 749 Eng.G.getNode(BlockEdge(Src, DefaultBlock, Pred->getLocationContext()), 750 St, IsSink, &IsNew); 751 Succ->addPredecessor(Pred, Eng.G); 752 753 if (!IsNew) 754 return nullptr; 755 756 if (!IsSink) 757 Eng.WList->enqueue(Succ); 758 759 return Succ; 760} 761