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