CoreEngine.cpp revision b219cfc4d75f0a03630b7c4509ef791b7e97b2c8
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/AnalysisManager.h" 16#include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h" 17#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 18#include "clang/Index/TranslationUnit.h" 19#include "clang/AST/Expr.h" 20#include "llvm/Support/Casting.h" 21#include "llvm/ADT/DenseMap.h" 22using namespace clang; 23using namespace ento; 24 25//===----------------------------------------------------------------------===// 26// Worklist classes for exploration of reachable states. 27//===----------------------------------------------------------------------===// 28 29WorkList::Visitor::~Visitor() {} 30 31namespace { 32class DFS : public WorkList { 33 SmallVector<WorkListUnit,20> Stack; 34public: 35 virtual bool hasWork() const { 36 return !Stack.empty(); 37 } 38 39 virtual void enqueue(const WorkListUnit& U) { 40 Stack.push_back(U); 41 } 42 43 virtual WorkListUnit dequeue() { 44 assert (!Stack.empty()); 45 const WorkListUnit& U = Stack.back(); 46 Stack.pop_back(); // This technically "invalidates" U, but we are fine. 47 return U; 48 } 49 50 virtual bool visitItemsInWorkList(Visitor &V) { 51 for (SmallVectorImpl<WorkListUnit>::iterator 52 I = Stack.begin(), E = Stack.end(); I != E; ++I) { 53 if (V.visit(*I)) 54 return true; 55 } 56 return false; 57 } 58}; 59 60class BFS : public WorkList { 61 std::deque<WorkListUnit> Queue; 62public: 63 virtual bool hasWork() const { 64 return !Queue.empty(); 65 } 66 67 virtual void enqueue(const WorkListUnit& U) { 68 Queue.push_front(U); 69 } 70 71 virtual WorkListUnit dequeue() { 72 WorkListUnit U = Queue.front(); 73 Queue.pop_front(); 74 return U; 75 } 76 77 virtual bool visitItemsInWorkList(Visitor &V) { 78 for (std::deque<WorkListUnit>::iterator 79 I = Queue.begin(), E = Queue.end(); I != E; ++I) { 80 if (V.visit(*I)) 81 return true; 82 } 83 return false; 84 } 85}; 86 87} // end anonymous namespace 88 89// Place the dstor for WorkList here because it contains virtual member 90// functions, and we the code for the dstor generated in one compilation unit. 91WorkList::~WorkList() {} 92 93WorkList *WorkList::makeDFS() { return new DFS(); } 94WorkList *WorkList::makeBFS() { return new BFS(); } 95 96namespace { 97 class BFSBlockDFSContents : public WorkList { 98 std::deque<WorkListUnit> Queue; 99 SmallVector<WorkListUnit,20> Stack; 100 public: 101 virtual bool hasWork() const { 102 return !Queue.empty() || !Stack.empty(); 103 } 104 105 virtual void enqueue(const WorkListUnit& U) { 106 if (isa<BlockEntrance>(U.getNode()->getLocation())) 107 Queue.push_front(U); 108 else 109 Stack.push_back(U); 110 } 111 112 virtual WorkListUnit dequeue() { 113 // Process all basic blocks to completion. 114 if (!Stack.empty()) { 115 const WorkListUnit& U = Stack.back(); 116 Stack.pop_back(); // This technically "invalidates" U, but we are fine. 117 return U; 118 } 119 120 assert(!Queue.empty()); 121 // Don't use const reference. The subsequent pop_back() might make it 122 // unsafe. 123 WorkListUnit U = Queue.front(); 124 Queue.pop_front(); 125 return U; 126 } 127 virtual bool visitItemsInWorkList(Visitor &V) { 128 for (SmallVectorImpl<WorkListUnit>::iterator 129 I = Stack.begin(), E = Stack.end(); I != E; ++I) { 130 if (V.visit(*I)) 131 return true; 132 } 133 for (std::deque<WorkListUnit>::iterator 134 I = Queue.begin(), E = Queue.end(); I != E; ++I) { 135 if (V.visit(*I)) 136 return true; 137 } 138 return false; 139 } 140 141 }; 142} // end anonymous namespace 143 144WorkList* WorkList::makeBFSBlockDFSContents() { 145 return new BFSBlockDFSContents(); 146} 147 148//===----------------------------------------------------------------------===// 149// Core analysis engine. 150//===----------------------------------------------------------------------===// 151 152/// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps. 153bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps, 154 const ProgramState *InitState) { 155 156 if (G->num_roots() == 0) { // Initialize the analysis by constructing 157 // the root if none exists. 158 159 const CFGBlock *Entry = &(L->getCFG()->getEntry()); 160 161 assert (Entry->empty() && 162 "Entry block must be empty."); 163 164 assert (Entry->succ_size() == 1 && 165 "Entry block must have 1 successor."); 166 167 // Get the solitary successor. 168 const CFGBlock *Succ = *(Entry->succ_begin()); 169 170 // Construct an edge representing the 171 // starting location in the function. 172 BlockEdge StartLoc(Entry, Succ, L); 173 174 // Set the current block counter to being empty. 175 WList->setBlockCounter(BCounterFactory.GetEmptyCounter()); 176 177 if (!InitState) 178 // Generate the root. 179 generateNode(StartLoc, SubEng.getInitialState(L), 0); 180 else 181 generateNode(StartLoc, InitState, 0); 182 } 183 184 // Check if we have a steps limit 185 bool UnlimitedSteps = Steps == 0; 186 187 while (WList->hasWork()) { 188 if (!UnlimitedSteps) { 189 if (Steps == 0) 190 break; 191 --Steps; 192 } 193 194 const WorkListUnit& WU = WList->dequeue(); 195 196 // Set the current block counter. 197 WList->setBlockCounter(WU.getBlockCounter()); 198 199 // Retrieve the node. 200 ExplodedNode *Node = WU.getNode(); 201 202 // Dispatch on the location type. 203 switch (Node->getLocation().getKind()) { 204 case ProgramPoint::BlockEdgeKind: 205 HandleBlockEdge(cast<BlockEdge>(Node->getLocation()), Node); 206 break; 207 208 case ProgramPoint::BlockEntranceKind: 209 HandleBlockEntrance(cast<BlockEntrance>(Node->getLocation()), Node); 210 break; 211 212 case ProgramPoint::BlockExitKind: 213 assert (false && "BlockExit location never occur in forward analysis."); 214 break; 215 216 case ProgramPoint::CallEnterKind: 217 HandleCallEnter(cast<CallEnter>(Node->getLocation()), WU.getBlock(), 218 WU.getIndex(), Node); 219 break; 220 221 case ProgramPoint::CallExitKind: 222 HandleCallExit(cast<CallExit>(Node->getLocation()), Node); 223 break; 224 225 default: 226 assert(isa<PostStmt>(Node->getLocation()) || 227 isa<PostInitializer>(Node->getLocation())); 228 HandlePostStmt(WU.getBlock(), WU.getIndex(), Node); 229 break; 230 } 231 } 232 233 SubEng.processEndWorklist(hasWorkRemaining()); 234 return WList->hasWork(); 235} 236 237void CoreEngine::ExecuteWorkListWithInitialState(const LocationContext *L, 238 unsigned Steps, 239 const ProgramState *InitState, 240 ExplodedNodeSet &Dst) { 241 ExecuteWorkList(L, Steps, InitState); 242 for (SmallVectorImpl<ExplodedNode*>::iterator I = G->EndNodes.begin(), 243 E = G->EndNodes.end(); I != E; ++I) { 244 Dst.Add(*I); 245 } 246} 247 248void CoreEngine::HandleCallEnter(const CallEnter &L, const CFGBlock *Block, 249 unsigned Index, ExplodedNode *Pred) { 250 CallEnterNodeBuilder Builder(*this, Pred, L.getCallExpr(), 251 L.getCalleeContext(), Block, Index); 252 SubEng.processCallEnter(Builder); 253} 254 255void CoreEngine::HandleCallExit(const CallExit &L, ExplodedNode *Pred) { 256 CallExitNodeBuilder Builder(*this, Pred); 257 SubEng.processCallExit(Builder); 258} 259 260void CoreEngine::HandleBlockEdge(const BlockEdge &L, ExplodedNode *Pred) { 261 262 const CFGBlock *Blk = L.getDst(); 263 264 // Check if we are entering the EXIT block. 265 if (Blk == &(L.getLocationContext()->getCFG()->getExit())) { 266 267 assert (L.getLocationContext()->getCFG()->getExit().size() == 0 268 && "EXIT block cannot contain Stmts."); 269 270 // Process the final state transition. 271 EndOfFunctionNodeBuilder Builder(Blk, Pred, this); 272 SubEng.processEndOfFunction(Builder); 273 274 // This path is done. Don't enqueue any more nodes. 275 return; 276 } 277 278 // Call into the subengine to process entering the CFGBlock. 279 ExplodedNodeSet dstNodes; 280 BlockEntrance BE(Blk, Pred->getLocationContext()); 281 GenericNodeBuilder<BlockEntrance> nodeBuilder(*this, Pred, BE); 282 SubEng.processCFGBlockEntrance(dstNodes, nodeBuilder); 283 284 if (dstNodes.empty()) { 285 if (!nodeBuilder.hasGeneratedNode) { 286 // Auto-generate a node and enqueue it to the worklist. 287 generateNode(BE, Pred->State, Pred); 288 } 289 } 290 else { 291 for (ExplodedNodeSet::iterator I = dstNodes.begin(), E = dstNodes.end(); 292 I != E; ++I) { 293 WList->enqueue(*I); 294 } 295 } 296 297 for (SmallVectorImpl<ExplodedNode*>::const_iterator 298 I = nodeBuilder.sinks().begin(), E = nodeBuilder.sinks().end(); 299 I != E; ++I) { 300 blocksExhausted.push_back(std::make_pair(L, *I)); 301 } 302} 303 304void CoreEngine::HandleBlockEntrance(const BlockEntrance &L, 305 ExplodedNode *Pred) { 306 307 // Increment the block counter. 308 BlockCounter Counter = WList->getBlockCounter(); 309 Counter = BCounterFactory.IncrementCount(Counter, 310 Pred->getLocationContext()->getCurrentStackFrame(), 311 L.getBlock()->getBlockID()); 312 WList->setBlockCounter(Counter); 313 314 // Process the entrance of the block. 315 if (CFGElement E = L.getFirstElement()) { 316 StmtNodeBuilder Builder(L.getBlock(), 0, Pred, this, 317 SubEng.getStateManager()); 318 SubEng.processCFGElement(E, Builder); 319 } 320 else 321 HandleBlockExit(L.getBlock(), Pred); 322} 323 324void CoreEngine::HandleBlockExit(const CFGBlock * B, ExplodedNode *Pred) { 325 326 if (const Stmt *Term = B->getTerminator()) { 327 switch (Term->getStmtClass()) { 328 default: 329 llvm_unreachable("Analysis for this terminator not implemented."); 330 break; 331 332 case Stmt::BinaryOperatorClass: // '&&' and '||' 333 HandleBranch(cast<BinaryOperator>(Term)->getLHS(), Term, B, Pred); 334 return; 335 336 case Stmt::BinaryConditionalOperatorClass: 337 case Stmt::ConditionalOperatorClass: 338 HandleBranch(cast<AbstractConditionalOperator>(Term)->getCond(), 339 Term, B, Pred); 340 return; 341 342 // FIXME: Use constant-folding in CFG construction to simplify this 343 // case. 344 345 case Stmt::ChooseExprClass: 346 HandleBranch(cast<ChooseExpr>(Term)->getCond(), Term, B, Pred); 347 return; 348 349 case Stmt::DoStmtClass: 350 HandleBranch(cast<DoStmt>(Term)->getCond(), Term, B, Pred); 351 return; 352 353 case Stmt::ForStmtClass: 354 HandleBranch(cast<ForStmt>(Term)->getCond(), Term, B, Pred); 355 return; 356 357 case Stmt::ContinueStmtClass: 358 case Stmt::BreakStmtClass: 359 case Stmt::GotoStmtClass: 360 break; 361 362 case Stmt::IfStmtClass: 363 HandleBranch(cast<IfStmt>(Term)->getCond(), Term, B, Pred); 364 return; 365 366 case Stmt::IndirectGotoStmtClass: { 367 // Only 1 successor: the indirect goto dispatch block. 368 assert (B->succ_size() == 1); 369 370 IndirectGotoNodeBuilder 371 builder(Pred, B, cast<IndirectGotoStmt>(Term)->getTarget(), 372 *(B->succ_begin()), this); 373 374 SubEng.processIndirectGoto(builder); 375 return; 376 } 377 378 case Stmt::ObjCForCollectionStmtClass: { 379 // In the case of ObjCForCollectionStmt, it appears twice in a CFG: 380 // 381 // (1) inside a basic block, which represents the binding of the 382 // 'element' variable to a value. 383 // (2) in a terminator, which represents the branch. 384 // 385 // For (1), subengines will bind a value (i.e., 0 or 1) indicating 386 // whether or not collection contains any more elements. We cannot 387 // just test to see if the element is nil because a container can 388 // contain nil elements. 389 HandleBranch(Term, Term, B, Pred); 390 return; 391 } 392 393 case Stmt::SwitchStmtClass: { 394 SwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(), 395 this); 396 397 SubEng.processSwitch(builder); 398 return; 399 } 400 401 case Stmt::WhileStmtClass: 402 HandleBranch(cast<WhileStmt>(Term)->getCond(), Term, B, Pred); 403 return; 404 } 405 } 406 407 assert (B->succ_size() == 1 && 408 "Blocks with no terminator should have at most 1 successor."); 409 410 generateNode(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()), 411 Pred->State, Pred); 412} 413 414void CoreEngine::HandleBranch(const Stmt *Cond, const Stmt *Term, 415 const CFGBlock * B, ExplodedNode *Pred) { 416 assert(B->succ_size() == 2); 417 BranchNodeBuilder Builder(B, *(B->succ_begin()), *(B->succ_begin()+1), 418 Pred, this); 419 SubEng.processBranch(Cond, Term, Builder); 420} 421 422void CoreEngine::HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, 423 ExplodedNode *Pred) { 424 assert (!B->empty()); 425 426 if (StmtIdx == B->size()) 427 HandleBlockExit(B, Pred); 428 else { 429 StmtNodeBuilder Builder(B, StmtIdx, Pred, this, 430 SubEng.getStateManager()); 431 SubEng.processCFGElement((*B)[StmtIdx], Builder); 432 } 433} 434 435/// generateNode - Utility method to generate nodes, hook up successors, 436/// and add nodes to the worklist. 437void CoreEngine::generateNode(const ProgramPoint &Loc, 438 const ProgramState *State, 439 ExplodedNode *Pred) { 440 441 bool IsNew; 442 ExplodedNode *Node = G->getNode(Loc, State, &IsNew); 443 444 if (Pred) 445 Node->addPredecessor(Pred, *G); // Link 'Node' with its predecessor. 446 else { 447 assert (IsNew); 448 G->addRoot(Node); // 'Node' has no predecessor. Make it a root. 449 } 450 451 // Only add 'Node' to the worklist if it was freshly generated. 452 if (IsNew) WList->enqueue(Node); 453} 454 455ExplodedNode * 456GenericNodeBuilderImpl::generateNodeImpl(const ProgramState *state, 457 ExplodedNode *pred, 458 ProgramPoint programPoint, 459 bool asSink) { 460 461 hasGeneratedNode = true; 462 bool isNew; 463 ExplodedNode *node = engine.getGraph().getNode(programPoint, state, &isNew); 464 if (pred) 465 node->addPredecessor(pred, engine.getGraph()); 466 if (isNew) { 467 if (asSink) { 468 node->markAsSink(); 469 sinksGenerated.push_back(node); 470 } 471 return node; 472 } 473 return 0; 474} 475 476StmtNodeBuilder::StmtNodeBuilder(const CFGBlock *b, 477 unsigned idx, 478 ExplodedNode *N, 479 CoreEngine* e, 480 ProgramStateManager &mgr) 481 : Eng(*e), B(*b), Idx(idx), Pred(N), Mgr(mgr), 482 PurgingDeadSymbols(false), BuildSinks(false), hasGeneratedNode(false), 483 PointKind(ProgramPoint::PostStmtKind), Tag(0) { 484 Deferred.insert(N); 485} 486 487StmtNodeBuilder::~StmtNodeBuilder() { 488 for (DeferredTy::iterator I=Deferred.begin(), E=Deferred.end(); I!=E; ++I) 489 if (!(*I)->isSink()) 490 GenerateAutoTransition(*I); 491} 492 493void StmtNodeBuilder::GenerateAutoTransition(ExplodedNode *N) { 494 assert (!N->isSink()); 495 496 // Check if this node entered a callee. 497 if (isa<CallEnter>(N->getLocation())) { 498 // Still use the index of the CallExpr. It's needed to create the callee 499 // StackFrameContext. 500 Eng.WList->enqueue(N, &B, Idx); 501 return; 502 } 503 504 // Do not create extra nodes. Move to the next CFG element. 505 if (isa<PostInitializer>(N->getLocation())) { 506 Eng.WList->enqueue(N, &B, Idx+1); 507 return; 508 } 509 510 PostStmt Loc(getStmt(), N->getLocationContext()); 511 512 if (Loc == N->getLocation()) { 513 // Note: 'N' should be a fresh node because otherwise it shouldn't be 514 // a member of Deferred. 515 Eng.WList->enqueue(N, &B, Idx+1); 516 return; 517 } 518 519 bool IsNew; 520 ExplodedNode *Succ = Eng.G->getNode(Loc, N->State, &IsNew); 521 Succ->addPredecessor(N, *Eng.G); 522 523 if (IsNew) 524 Eng.WList->enqueue(Succ, &B, Idx+1); 525} 526 527ExplodedNode *StmtNodeBuilder::MakeNode(ExplodedNodeSet &Dst, 528 const Stmt *S, 529 ExplodedNode *Pred, 530 const ProgramState *St, 531 ProgramPoint::Kind K) { 532 533 ExplodedNode *N = generateNode(S, St, Pred, K); 534 535 if (N) { 536 if (BuildSinks) 537 N->markAsSink(); 538 else 539 Dst.Add(N); 540 } 541 542 return N; 543} 544 545static ProgramPoint GetProgramPoint(const Stmt *S, ProgramPoint::Kind K, 546 const LocationContext *LC, 547 const ProgramPointTag *tag){ 548 switch (K) { 549 default: 550 llvm_unreachable("Unhandled ProgramPoint kind"); 551 case ProgramPoint::PreStmtKind: 552 return PreStmt(S, LC, tag); 553 case ProgramPoint::PostStmtKind: 554 return PostStmt(S, LC, tag); 555 case ProgramPoint::PreLoadKind: 556 return PreLoad(S, LC, tag); 557 case ProgramPoint::PostLoadKind: 558 return PostLoad(S, LC, tag); 559 case ProgramPoint::PreStoreKind: 560 return PreStore(S, LC, tag); 561 case ProgramPoint::PostStoreKind: 562 return PostStore(S, LC, tag); 563 case ProgramPoint::PostLValueKind: 564 return PostLValue(S, LC, tag); 565 case ProgramPoint::PostPurgeDeadSymbolsKind: 566 return PostPurgeDeadSymbols(S, LC, tag); 567 } 568} 569 570ExplodedNode* 571StmtNodeBuilder::generateNodeInternal(const Stmt *S, 572 const ProgramState *state, 573 ExplodedNode *Pred, 574 ProgramPoint::Kind K, 575 const ProgramPointTag *tag) { 576 577 const ProgramPoint &L = GetProgramPoint(S, K, Pred->getLocationContext(), 578 tag); 579 return generateNodeInternal(L, state, Pred); 580} 581 582ExplodedNode* 583StmtNodeBuilder::generateNodeInternal(const ProgramPoint &Loc, 584 const ProgramState *State, 585 ExplodedNode *Pred) { 586 bool IsNew; 587 ExplodedNode *N = Eng.G->getNode(Loc, State, &IsNew); 588 N->addPredecessor(Pred, *Eng.G); 589 Deferred.erase(Pred); 590 591 if (IsNew) { 592 Deferred.insert(N); 593 return N; 594 } 595 596 return NULL; 597} 598 599// This function generate a new ExplodedNode but not a new branch(block edge). 600ExplodedNode *BranchNodeBuilder::generateNode(const Stmt *Condition, 601 const ProgramState *State) { 602 bool IsNew; 603 604 ExplodedNode *Succ 605 = Eng.G->getNode(PostCondition(Condition, Pred->getLocationContext()), State, 606 &IsNew); 607 608 Succ->addPredecessor(Pred, *Eng.G); 609 610 Pred = Succ; 611 612 if (IsNew) 613 return Succ; 614 615 return NULL; 616} 617 618ExplodedNode *BranchNodeBuilder::generateNode(const ProgramState *State, 619 bool branch) { 620 621 // If the branch has been marked infeasible we should not generate a node. 622 if (!isFeasible(branch)) 623 return NULL; 624 625 bool IsNew; 626 627 ExplodedNode *Succ = 628 Eng.G->getNode(BlockEdge(Src,branch ? DstT:DstF,Pred->getLocationContext()), 629 State, &IsNew); 630 631 Succ->addPredecessor(Pred, *Eng.G); 632 633 if (branch) 634 GeneratedTrue = true; 635 else 636 GeneratedFalse = true; 637 638 if (IsNew) { 639 Deferred.push_back(Succ); 640 return Succ; 641 } 642 643 return NULL; 644} 645 646BranchNodeBuilder::~BranchNodeBuilder() { 647 if (!GeneratedTrue) generateNode(Pred->State, true); 648 if (!GeneratedFalse) generateNode(Pred->State, false); 649 650 for (DeferredTy::iterator I=Deferred.begin(), E=Deferred.end(); I!=E; ++I) 651 if (!(*I)->isSink()) Eng.WList->enqueue(*I); 652} 653 654 655ExplodedNode* 656IndirectGotoNodeBuilder::generateNode(const iterator &I, 657 const ProgramState *St, 658 bool isSink) { 659 bool IsNew; 660 661 ExplodedNode *Succ = Eng.G->getNode(BlockEdge(Src, I.getBlock(), 662 Pred->getLocationContext()), St, &IsNew); 663 664 Succ->addPredecessor(Pred, *Eng.G); 665 666 if (IsNew) { 667 668 if (isSink) 669 Succ->markAsSink(); 670 else 671 Eng.WList->enqueue(Succ); 672 673 return Succ; 674 } 675 676 return NULL; 677} 678 679 680ExplodedNode* 681SwitchNodeBuilder::generateCaseStmtNode(const iterator &I, 682 const ProgramState *St) { 683 684 bool IsNew; 685 ExplodedNode *Succ = Eng.G->getNode(BlockEdge(Src, I.getBlock(), 686 Pred->getLocationContext()), 687 St, &IsNew); 688 Succ->addPredecessor(Pred, *Eng.G); 689 if (IsNew) { 690 Eng.WList->enqueue(Succ); 691 return Succ; 692 } 693 return NULL; 694} 695 696 697ExplodedNode* 698SwitchNodeBuilder::generateDefaultCaseNode(const ProgramState *St, 699 bool isSink) { 700 // Get the block for the default case. 701 assert (Src->succ_rbegin() != Src->succ_rend()); 702 CFGBlock *DefaultBlock = *Src->succ_rbegin(); 703 704 bool IsNew; 705 706 ExplodedNode *Succ = Eng.G->getNode(BlockEdge(Src, DefaultBlock, 707 Pred->getLocationContext()), St, &IsNew); 708 Succ->addPredecessor(Pred, *Eng.G); 709 710 if (IsNew) { 711 if (isSink) 712 Succ->markAsSink(); 713 else 714 Eng.WList->enqueue(Succ); 715 716 return Succ; 717 } 718 719 return NULL; 720} 721 722EndOfFunctionNodeBuilder::~EndOfFunctionNodeBuilder() { 723 // Auto-generate an EOP node if one has not been generated. 724 if (!hasGeneratedNode) { 725 // If we are in an inlined call, generate CallExit node. 726 if (Pred->getLocationContext()->getParent()) 727 GenerateCallExitNode(Pred->State); 728 else 729 generateNode(Pred->State); 730 } 731} 732 733ExplodedNode* 734EndOfFunctionNodeBuilder::generateNode(const ProgramState *State, 735 ExplodedNode *P, 736 const ProgramPointTag *tag) { 737 hasGeneratedNode = true; 738 bool IsNew; 739 740 ExplodedNode *Node = Eng.G->getNode(BlockEntrance(&B, 741 Pred->getLocationContext(), tag ? tag : Tag), 742 State, &IsNew); 743 744 Node->addPredecessor(P ? P : Pred, *Eng.G); 745 746 if (IsNew) { 747 Eng.G->addEndOfPath(Node); 748 return Node; 749 } 750 751 return NULL; 752} 753 754void EndOfFunctionNodeBuilder::GenerateCallExitNode(const ProgramState *state) { 755 hasGeneratedNode = true; 756 // Create a CallExit node and enqueue it. 757 const StackFrameContext *LocCtx 758 = cast<StackFrameContext>(Pred->getLocationContext()); 759 const Stmt *CE = LocCtx->getCallSite(); 760 761 // Use the the callee location context. 762 CallExit Loc(CE, LocCtx); 763 764 bool isNew; 765 ExplodedNode *Node = Eng.G->getNode(Loc, state, &isNew); 766 Node->addPredecessor(Pred, *Eng.G); 767 768 if (isNew) 769 Eng.WList->enqueue(Node); 770} 771 772 773void CallEnterNodeBuilder::generateNode(const ProgramState *state) { 774 // Check if the callee is in the same translation unit. 775 if (CalleeCtx->getTranslationUnit() != 776 Pred->getLocationContext()->getTranslationUnit()) { 777 // Create a new engine. We must be careful that the new engine should not 778 // reference data structures owned by the old engine. 779 780 AnalysisManager &OldMgr = Eng.SubEng.getAnalysisManager(); 781 782 // Get the callee's translation unit. 783 idx::TranslationUnit *TU = CalleeCtx->getTranslationUnit(); 784 785 // Create a new AnalysisManager with components of the callee's 786 // TranslationUnit. 787 // The Diagnostic is actually shared when we create ASTUnits from AST files. 788 AnalysisManager AMgr(TU->getASTContext(), TU->getDiagnostic(), 789 OldMgr.getLangOptions(), 790 OldMgr.getPathDiagnosticClient(), 791 OldMgr.getStoreManagerCreator(), 792 OldMgr.getConstraintManagerCreator(), 793 OldMgr.getCheckerManager(), 794 OldMgr.getIndexer(), 795 OldMgr.getMaxNodes(), OldMgr.getMaxVisit(), 796 OldMgr.shouldVisualizeGraphviz(), 797 OldMgr.shouldVisualizeUbigraph(), 798 OldMgr.shouldPurgeDead(), 799 OldMgr.shouldEagerlyAssume(), 800 OldMgr.shouldTrimGraph(), 801 OldMgr.shouldInlineCall(), 802 OldMgr.getAnalysisContextManager().getUseUnoptimizedCFG(), 803 OldMgr.getAnalysisContextManager(). 804 getCFGBuildOptions().AddImplicitDtors, 805 OldMgr.getAnalysisContextManager(). 806 getCFGBuildOptions().AddInitializers, 807 OldMgr.shouldEagerlyTrimExplodedGraph()); 808 // Create the new engine. 809 // FIXME: This cast isn't really safe. 810 bool GCEnabled = static_cast<ExprEngine&>(Eng.SubEng).isObjCGCEnabled(); 811 ExprEngine NewEng(AMgr, GCEnabled); 812 813 // Create the new LocationContext. 814 AnalysisContext *NewAnaCtx = AMgr.getAnalysisContext(CalleeCtx->getDecl(), 815 CalleeCtx->getTranslationUnit()); 816 const StackFrameContext *OldLocCtx = CalleeCtx; 817 const StackFrameContext *NewLocCtx = AMgr.getStackFrame(NewAnaCtx, 818 OldLocCtx->getParent(), 819 OldLocCtx->getCallSite(), 820 OldLocCtx->getCallSiteBlock(), 821 OldLocCtx->getIndex()); 822 823 // Now create an initial state for the new engine. 824 const ProgramState *NewState = 825 NewEng.getStateManager().MarshalState(state, NewLocCtx); 826 ExplodedNodeSet ReturnNodes; 827 NewEng.ExecuteWorkListWithInitialState(NewLocCtx, AMgr.getMaxNodes(), 828 NewState, ReturnNodes); 829 return; 830 } 831 832 // Get the callee entry block. 833 const CFGBlock *Entry = &(CalleeCtx->getCFG()->getEntry()); 834 assert(Entry->empty()); 835 assert(Entry->succ_size() == 1); 836 837 // Get the solitary successor. 838 const CFGBlock *SuccB = *(Entry->succ_begin()); 839 840 // Construct an edge representing the starting location in the callee. 841 BlockEdge Loc(Entry, SuccB, CalleeCtx); 842 843 bool isNew; 844 ExplodedNode *Node = Eng.G->getNode(Loc, state, &isNew); 845 Node->addPredecessor(const_cast<ExplodedNode*>(Pred), *Eng.G); 846 847 if (isNew) 848 Eng.WList->enqueue(Node); 849} 850 851void CallExitNodeBuilder::generateNode(const ProgramState *state) { 852 // Get the callee's location context. 853 const StackFrameContext *LocCtx 854 = cast<StackFrameContext>(Pred->getLocationContext()); 855 // When exiting an implicit automatic obj dtor call, the callsite is the Stmt 856 // that triggers the dtor. 857 PostStmt Loc(LocCtx->getCallSite(), LocCtx->getParent()); 858 bool isNew; 859 ExplodedNode *Node = Eng.G->getNode(Loc, state, &isNew); 860 Node->addPredecessor(const_cast<ExplodedNode*>(Pred), *Eng.G); 861 if (isNew) 862 Eng.WList->enqueue(Node, LocCtx->getCallSiteBlock(), 863 LocCtx->getIndex() + 1); 864} 865