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