CoreEngine.cpp revision 3fd5f370a28552976c52e76c3035d79012d78dda
11a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com//==- CoreEngine.cpp - Path-Sensitive Dataflow Engine ------------*- C++ -*-// 21a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com// 31a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com// The LLVM Compiler Infrastructure 41a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com// 51a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com// This file is distributed under the University of Illinois Open Source 61a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com// License. See LICENSE.TXT for details. 71a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com// 81a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com//===----------------------------------------------------------------------===// 91a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com// 101a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com// This file defines a generic engine for intraprocedural, path-sensitive, 111a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com// dataflow analysis via graph reachability engine. 121a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com// 131a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com//===----------------------------------------------------------------------===// 141a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com 151a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" 161a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com#include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h" 171a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 181a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com#include "clang/Index/TranslationUnit.h" 191a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com#include "clang/AST/Expr.h" 201a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com#include "clang/AST/StmtCXX.h" 211a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com#include "llvm/Support/Casting.h" 221a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com#include "llvm/ADT/DenseMap.h" 231a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.comusing namespace clang; 241a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.comusing namespace ento; 251a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com 261a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com//===----------------------------------------------------------------------===// 27f539318f0d3dba743ec1886d5d9df0fb1be628a1tfarina// Worklist classes for exploration of reachable states. 281a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com//===----------------------------------------------------------------------===// 291a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com 301a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.comWorkList::Visitor::~Visitor() {} 311a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com 321a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.comnamespace { 331a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.comclass DFS : public WorkList { 341a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com SmallVector<WorkListUnit,20> Stack; 351a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.compublic: 361a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com virtual bool hasWork() const { 371a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com return !Stack.empty(); 381a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com } 391a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com 401a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com virtual void enqueue(const WorkListUnit& U) { 411a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com Stack.push_back(U); 4257b1935dbc6f8b8857d430fdf244dbe2c2e1ae5breed@google.com } 431313086ef4d901176e569d1f4b6362250ac02cd7caryclark@google.com 440e51577a14f903ffeafa117a75954baeb173ffb9humper@google.com virtual WorkListUnit dequeue() { 451a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com assert (!Stack.empty()); 461a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com const WorkListUnit& U = Stack.back(); 471a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com Stack.pop_back(); // This technically "invalidates" U, but we are fine. 481a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com return U; 491a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com } 501a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com 511a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com virtual bool visitItemsInWorkList(Visitor &V) { 521a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com for (SmallVectorImpl<WorkListUnit>::iterator 531a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com I = Stack.begin(), E = Stack.end(); I != E; ++I) { 541a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com if (V.visit(*I)) 551a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com return true; 561a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com } 571a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com return false; 581a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com } 591a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com}; 601a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com 611a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.comclass BFS : public WorkList { 62eb9a46cbbb475e862a084aa2224ec18d4ac5e95breed@google.com std::deque<WorkListUnit> Queue; 631a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.compublic: 641a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com virtual bool hasWork() const { 651a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com return !Queue.empty(); 661a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com } 671a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com 681a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com virtual void enqueue(const WorkListUnit& U) { 691a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com Queue.push_front(U); 701a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com } 711a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com 721a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com virtual WorkListUnit dequeue() { 739c9005a347e9996f357bd79591bd34f74f8bbc66commit-bot@chromium.org WorkListUnit U = Queue.front(); 749c9005a347e9996f357bd79591bd34f74f8bbc66commit-bot@chromium.org Queue.pop_front(); 759c9005a347e9996f357bd79591bd34f74f8bbc66commit-bot@chromium.org return U; 769c9005a347e9996f357bd79591bd34f74f8bbc66commit-bot@chromium.org } 779c9005a347e9996f357bd79591bd34f74f8bbc66commit-bot@chromium.org 781a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com virtual bool visitItemsInWorkList(Visitor &V) { 791a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com for (std::deque<WorkListUnit>::iterator 804469938e92d779dff05e745559e67907bbf21e78reed@google.com I = Queue.begin(), E = Queue.end(); I != E; ++I) { 811a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com if (V.visit(*I)) 821a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com return true; 831a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com } 841a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com return false; 851a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com } 861a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com}; 871a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com 881a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com} // end anonymous namespace 891a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com 901a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com// Place the dstor for WorkList here because it contains virtual member 911a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com// functions, and we the code for the dstor generated in one compilation unit. 921a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.comWorkList::~WorkList() {} 931a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.com 941a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.comWorkList *WorkList::makeDFS() { return new DFS(); } 951a38d5508f7a0e2c186d3aa8ea807045a46b663dbsalomon@google.comWorkList *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 CallEnter CEnter = cast<CallEnter>(Node->getLocation()); 219 if (AnalyzedCallees) 220 if (const CallExpr* CE = 221 dyn_cast_or_null<CallExpr>(CEnter.getCallExpr())) 222 if (const Decl *CD = CE->getCalleeDecl()) 223 AnalyzedCallees->insert(CD); 224 SubEng.processCallEnter(CEnter, Node); 225 break; 226 } 227 228 case ProgramPoint::CallExitKind: 229 SubEng.processCallExit(Node); 230 break; 231 232 default: 233 assert(isa<PostStmt>(Node->getLocation()) || 234 isa<PostInitializer>(Node->getLocation())); 235 HandlePostStmt(WU.getBlock(), WU.getIndex(), Node); 236 break; 237 } 238 } 239 240 SubEng.processEndWorklist(hasWorkRemaining()); 241 return WList->hasWork(); 242} 243 244void CoreEngine::ExecuteWorkListWithInitialState(const LocationContext *L, 245 unsigned Steps, 246 ProgramStateRef InitState, 247 ExplodedNodeSet &Dst) { 248 ExecuteWorkList(L, Steps, InitState); 249 for (ExplodedGraph::eop_iterator I = G->eop_begin(), 250 E = G->eop_end(); I != E; ++I) { 251 Dst.Add(*I); 252 } 253} 254 255void CoreEngine::HandleBlockEdge(const BlockEdge &L, ExplodedNode *Pred) { 256 257 const CFGBlock *Blk = L.getDst(); 258 NodeBuilderContext BuilderCtx(*this, Blk, Pred); 259 260 // Check if we are entering the EXIT block. 261 if (Blk == &(L.getLocationContext()->getCFG()->getExit())) { 262 263 assert (L.getLocationContext()->getCFG()->getExit().size() == 0 264 && "EXIT block cannot contain Stmts."); 265 266 // Process the final state transition. 267 SubEng.processEndOfFunction(BuilderCtx); 268 269 // This path is done. Don't enqueue any more nodes. 270 return; 271 } 272 273 // Call into the SubEngine to process entering the CFGBlock. 274 ExplodedNodeSet dstNodes; 275 BlockEntrance BE(Blk, Pred->getLocationContext()); 276 NodeBuilderWithSinks nodeBuilder(Pred, dstNodes, BuilderCtx, BE); 277 SubEng.processCFGBlockEntrance(nodeBuilder); 278 279 // Auto-generate a node. 280 if (!nodeBuilder.hasGeneratedNodes()) { 281 nodeBuilder.generateNode(Pred->State, Pred); 282 } 283 284 // Enqueue nodes onto the worklist. 285 enqueue(dstNodes); 286 287 // Make sink nodes as exhausted. 288 const SmallVectorImpl<ExplodedNode*> &Sinks = nodeBuilder.getSinks(); 289 for (SmallVectorImpl<ExplodedNode*>::const_iterator 290 I =Sinks.begin(), E = Sinks.end(); I != E; ++I) { 291 blocksExhausted.push_back(std::make_pair(L, *I)); 292 } 293} 294 295void CoreEngine::HandleBlockEntrance(const BlockEntrance &L, 296 ExplodedNode *Pred) { 297 298 // Increment the block counter. 299 BlockCounter Counter = WList->getBlockCounter(); 300 Counter = BCounterFactory.IncrementCount(Counter, 301 Pred->getLocationContext()->getCurrentStackFrame(), 302 L.getBlock()->getBlockID()); 303 WList->setBlockCounter(Counter); 304 305 // Process the entrance of the block. 306 if (CFGElement E = L.getFirstElement()) { 307 NodeBuilderContext Ctx(*this, L.getBlock(), Pred); 308 SubEng.processCFGElement(E, Pred, 0, &Ctx); 309 } 310 else 311 HandleBlockExit(L.getBlock(), Pred); 312} 313 314void CoreEngine::HandleBlockExit(const CFGBlock * B, ExplodedNode *Pred) { 315 316 if (const Stmt *Term = B->getTerminator()) { 317 switch (Term->getStmtClass()) { 318 default: 319 llvm_unreachable("Analysis for this terminator not implemented."); 320 321 case Stmt::BinaryOperatorClass: // '&&' and '||' 322 HandleBranch(cast<BinaryOperator>(Term)->getLHS(), Term, B, Pred); 323 return; 324 325 case Stmt::BinaryConditionalOperatorClass: 326 case Stmt::ConditionalOperatorClass: 327 HandleBranch(cast<AbstractConditionalOperator>(Term)->getCond(), 328 Term, B, Pred); 329 return; 330 331 // FIXME: Use constant-folding in CFG construction to simplify this 332 // case. 333 334 case Stmt::ChooseExprClass: 335 HandleBranch(cast<ChooseExpr>(Term)->getCond(), Term, B, Pred); 336 return; 337 338 case Stmt::DoStmtClass: 339 HandleBranch(cast<DoStmt>(Term)->getCond(), Term, B, Pred); 340 return; 341 342 case Stmt::CXXForRangeStmtClass: 343 HandleBranch(cast<CXXForRangeStmt>(Term)->getCond(), Term, B, Pred); 344 return; 345 346 case Stmt::ForStmtClass: 347 HandleBranch(cast<ForStmt>(Term)->getCond(), Term, B, Pred); 348 return; 349 350 case Stmt::ContinueStmtClass: 351 case Stmt::BreakStmtClass: 352 case Stmt::GotoStmtClass: 353 break; 354 355 case Stmt::IfStmtClass: 356 HandleBranch(cast<IfStmt>(Term)->getCond(), Term, B, Pred); 357 return; 358 359 case Stmt::IndirectGotoStmtClass: { 360 // Only 1 successor: the indirect goto dispatch block. 361 assert (B->succ_size() == 1); 362 363 IndirectGotoNodeBuilder 364 builder(Pred, B, cast<IndirectGotoStmt>(Term)->getTarget(), 365 *(B->succ_begin()), this); 366 367 SubEng.processIndirectGoto(builder); 368 return; 369 } 370 371 case Stmt::ObjCForCollectionStmtClass: { 372 // In the case of ObjCForCollectionStmt, it appears twice in a CFG: 373 // 374 // (1) inside a basic block, which represents the binding of the 375 // 'element' variable to a value. 376 // (2) in a terminator, which represents the branch. 377 // 378 // For (1), subengines will bind a value (i.e., 0 or 1) indicating 379 // whether or not collection contains any more elements. We cannot 380 // just test to see if the element is nil because a container can 381 // contain nil elements. 382 HandleBranch(Term, Term, B, Pred); 383 return; 384 } 385 386 case Stmt::SwitchStmtClass: { 387 SwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(), 388 this); 389 390 SubEng.processSwitch(builder); 391 return; 392 } 393 394 case Stmt::WhileStmtClass: 395 HandleBranch(cast<WhileStmt>(Term)->getCond(), Term, B, Pred); 396 return; 397 } 398 } 399 400 assert (B->succ_size() == 1 && 401 "Blocks with no terminator should have at most 1 successor."); 402 403 generateNode(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()), 404 Pred->State, Pred); 405} 406 407void CoreEngine::HandleBranch(const Stmt *Cond, const Stmt *Term, 408 const CFGBlock * B, ExplodedNode *Pred) { 409 assert(B->succ_size() == 2); 410 NodeBuilderContext Ctx(*this, B, Pred); 411 ExplodedNodeSet Dst; 412 SubEng.processBranch(Cond, Term, Ctx, Pred, Dst, 413 *(B->succ_begin()), *(B->succ_begin()+1)); 414 // Enqueue the new frontier onto the worklist. 415 enqueue(Dst); 416} 417 418void CoreEngine::HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, 419 ExplodedNode *Pred) { 420 assert(B); 421 assert(!B->empty()); 422 423 if (StmtIdx == B->size()) 424 HandleBlockExit(B, Pred); 425 else { 426 NodeBuilderContext Ctx(*this, B, Pred); 427 SubEng.processCFGElement((*B)[StmtIdx], Pred, StmtIdx, &Ctx); 428 } 429} 430 431/// generateNode - Utility method to generate nodes, hook up successors, 432/// and add nodes to the worklist. 433void CoreEngine::generateNode(const ProgramPoint &Loc, 434 ProgramStateRef State, 435 ExplodedNode *Pred) { 436 437 bool IsNew; 438 ExplodedNode *Node = G->getNode(Loc, State, false, &IsNew); 439 440 if (Pred) 441 Node->addPredecessor(Pred, *G); // Link 'Node' with its predecessor. 442 else { 443 assert (IsNew); 444 G->addRoot(Node); // 'Node' has no predecessor. Make it a root. 445 } 446 447 // Only add 'Node' to the worklist if it was freshly generated. 448 if (IsNew) WList->enqueue(Node); 449} 450 451void CoreEngine::enqueueStmtNode(ExplodedNode *N, 452 const CFGBlock *Block, unsigned Idx) { 453 assert(Block); 454 assert (!N->isSink()); 455 456 // Check if this node entered a callee. 457 if (isa<CallEnter>(N->getLocation())) { 458 // Still use the index of the CallExpr. It's needed to create the callee 459 // StackFrameContext. 460 WList->enqueue(N, Block, Idx); 461 return; 462 } 463 464 // Do not create extra nodes. Move to the next CFG element. 465 if (isa<PostInitializer>(N->getLocation())) { 466 WList->enqueue(N, Block, Idx+1); 467 return; 468 } 469 470 const CFGStmt *CS = (*Block)[Idx].getAs<CFGStmt>(); 471 const Stmt *St = CS ? CS->getStmt() : 0; 472 PostStmt Loc(St, N->getLocationContext()); 473 474 if (Loc == N->getLocation()) { 475 // Note: 'N' should be a fresh node because otherwise it shouldn't be 476 // a member of Deferred. 477 WList->enqueue(N, Block, Idx+1); 478 return; 479 } 480 481 bool IsNew; 482 ExplodedNode *Succ = G->getNode(Loc, N->getState(), false, &IsNew); 483 Succ->addPredecessor(N, *G); 484 485 if (IsNew) 486 WList->enqueue(Succ, Block, Idx+1); 487} 488 489ExplodedNode *CoreEngine::generateCallExitNode(ExplodedNode *N) { 490 // Create a CallExit node and enqueue it. 491 const StackFrameContext *LocCtx 492 = cast<StackFrameContext>(N->getLocationContext()); 493 const Stmt *CE = LocCtx->getCallSite(); 494 495 // Use the the callee location context. 496 CallExit Loc(CE, LocCtx); 497 498 bool isNew; 499 ExplodedNode *Node = G->getNode(Loc, N->getState(), false, &isNew); 500 Node->addPredecessor(N, *G); 501 return isNew ? Node : 0; 502} 503 504 505void CoreEngine::enqueue(ExplodedNodeSet &Set) { 506 for (ExplodedNodeSet::iterator I = Set.begin(), 507 E = Set.end(); I != E; ++I) { 508 WList->enqueue(*I); 509 } 510} 511 512void CoreEngine::enqueue(ExplodedNodeSet &Set, 513 const CFGBlock *Block, unsigned Idx) { 514 for (ExplodedNodeSet::iterator I = Set.begin(), 515 E = Set.end(); I != E; ++I) { 516 enqueueStmtNode(*I, Block, Idx); 517 } 518} 519 520void CoreEngine::enqueueEndOfFunction(ExplodedNodeSet &Set) { 521 for (ExplodedNodeSet::iterator I = Set.begin(), E = Set.end(); I != E; ++I) { 522 ExplodedNode *N = *I; 523 // If we are in an inlined call, generate CallExit node. 524 if (N->getLocationContext()->getParent()) { 525 N = generateCallExitNode(N); 526 if (N) 527 WList->enqueue(N); 528 } else 529 G->addEndOfPath(N); 530 } 531} 532 533 534void NodeBuilder::anchor() { } 535 536ExplodedNode* NodeBuilder::generateNodeImpl(const ProgramPoint &Loc, 537 ProgramStateRef State, 538 ExplodedNode *FromN, 539 bool MarkAsSink) { 540 HasGeneratedNodes = true; 541 bool IsNew; 542 ExplodedNode *N = C.Eng.G->getNode(Loc, State, MarkAsSink, &IsNew); 543 N->addPredecessor(FromN, *C.Eng.G); 544 Frontier.erase(FromN); 545 546 if (!IsNew) 547 return 0; 548 549 if (!MarkAsSink) 550 Frontier.Add(N); 551 552 return N; 553} 554 555void NodeBuilderWithSinks::anchor() { } 556 557StmtNodeBuilder::~StmtNodeBuilder() { 558 if (EnclosingBldr) 559 for (ExplodedNodeSet::iterator I = Frontier.begin(), 560 E = Frontier.end(); I != E; ++I ) 561 EnclosingBldr->addNodes(*I); 562} 563 564void BranchNodeBuilder::anchor() { } 565 566ExplodedNode *BranchNodeBuilder::generateNode(ProgramStateRef State, 567 bool branch, 568 ExplodedNode *NodePred) { 569 // If the branch has been marked infeasible we should not generate a node. 570 if (!isFeasible(branch)) 571 return NULL; 572 573 ProgramPoint Loc = BlockEdge(C.Block, branch ? DstT:DstF, 574 NodePred->getLocationContext()); 575 ExplodedNode *Succ = generateNodeImpl(Loc, State, NodePred); 576 return Succ; 577} 578 579ExplodedNode* 580IndirectGotoNodeBuilder::generateNode(const iterator &I, 581 ProgramStateRef St, 582 bool IsSink) { 583 bool IsNew; 584 ExplodedNode *Succ = Eng.G->getNode(BlockEdge(Src, I.getBlock(), 585 Pred->getLocationContext()), St, 586 IsSink, &IsNew); 587 Succ->addPredecessor(Pred, *Eng.G); 588 589 if (!IsNew) 590 return 0; 591 592 if (!IsSink) 593 Eng.WList->enqueue(Succ); 594 595 return Succ; 596} 597 598 599ExplodedNode* 600SwitchNodeBuilder::generateCaseStmtNode(const iterator &I, 601 ProgramStateRef St) { 602 603 bool IsNew; 604 ExplodedNode *Succ = Eng.G->getNode(BlockEdge(Src, I.getBlock(), 605 Pred->getLocationContext()), St, 606 false, &IsNew); 607 Succ->addPredecessor(Pred, *Eng.G); 608 if (!IsNew) 609 return 0; 610 611 Eng.WList->enqueue(Succ); 612 return Succ; 613} 614 615 616ExplodedNode* 617SwitchNodeBuilder::generateDefaultCaseNode(ProgramStateRef St, 618 bool IsSink) { 619 // Get the block for the default case. 620 assert(Src->succ_rbegin() != Src->succ_rend()); 621 CFGBlock *DefaultBlock = *Src->succ_rbegin(); 622 623 // Sanity check for default blocks that are unreachable and not caught 624 // by earlier stages. 625 if (!DefaultBlock) 626 return NULL; 627 628 bool IsNew; 629 ExplodedNode *Succ = Eng.G->getNode(BlockEdge(Src, DefaultBlock, 630 Pred->getLocationContext()), St, 631 IsSink, &IsNew); 632 Succ->addPredecessor(Pred, *Eng.G); 633 634 if (!IsNew) 635 return 0; 636 637 if (!IsSink) 638 Eng.WList->enqueue(Succ); 639 640 return Succ; 641} 642