ExprEngine.cpp revision ff80afcfb2b00ccffcb6cb10528bec565fc59edd
1//=-- ExprEngine.cpp - Path-Sensitive Expression-Level Dataflow ---*- 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 meta-engine for path-sensitive dataflow analysis that 11// is built on GREngine, but provides the boilerplate to execute transfer 12// functions and build the ExplodedGraph at the expression level. 13// 14//===----------------------------------------------------------------------===// 15 16#include "clang/StaticAnalyzer/Core/CheckerManager.h" 17#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 18#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" 19#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 20#include "clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h" 21#include "clang/AST/CharUnits.h" 22#include "clang/AST/ParentMap.h" 23#include "clang/AST/StmtObjC.h" 24#include "clang/AST/DeclCXX.h" 25#include "clang/Basic/Builtins.h" 26#include "clang/Basic/SourceManager.h" 27#include "clang/Basic/PrettyStackTrace.h" 28#include "llvm/Support/raw_ostream.h" 29#include "llvm/ADT/ImmutableList.h" 30 31#ifndef NDEBUG 32#include "llvm/Support/GraphWriter.h" 33#endif 34 35using namespace clang; 36using namespace ento; 37using llvm::APSInt; 38 39//===----------------------------------------------------------------------===// 40// Utility functions. 41//===----------------------------------------------------------------------===// 42 43static inline Selector GetNullarySelector(const char* name, ASTContext &Ctx) { 44 IdentifierInfo* II = &Ctx.Idents.get(name); 45 return Ctx.Selectors.getSelector(0, &II); 46} 47 48//===----------------------------------------------------------------------===// 49// Engine construction and deletion. 50//===----------------------------------------------------------------------===// 51 52ExprEngine::ExprEngine(AnalysisManager &mgr, bool gcEnabled) 53 : AMgr(mgr), 54 AnalysisDeclContexts(mgr.getAnalysisDeclContextManager()), 55 Engine(*this), 56 G(Engine.getGraph()), 57 StateMgr(getContext(), mgr.getStoreManagerCreator(), 58 mgr.getConstraintManagerCreator(), G.getAllocator(), 59 *this), 60 SymMgr(StateMgr.getSymbolManager()), 61 svalBuilder(StateMgr.getSValBuilder()), 62 EntryNode(NULL), 63 currentStmt(NULL), currentStmtIdx(0), currentBuilderContext(0), 64 NSExceptionII(NULL), NSExceptionInstanceRaiseSelectors(NULL), 65 RaiseSel(GetNullarySelector("raise", getContext())), 66 ObjCGCEnabled(gcEnabled), BR(mgr, *this) { 67 68 if (mgr.shouldEagerlyTrimExplodedGraph()) { 69 // Enable eager node reclaimation when constructing the ExplodedGraph. 70 G.enableNodeReclamation(); 71 } 72} 73 74ExprEngine::~ExprEngine() { 75 BR.FlushReports(); 76 delete [] NSExceptionInstanceRaiseSelectors; 77} 78 79//===----------------------------------------------------------------------===// 80// Utility methods. 81//===----------------------------------------------------------------------===// 82 83ProgramStateRef ExprEngine::getInitialState(const LocationContext *InitLoc) { 84 ProgramStateRef state = StateMgr.getInitialState(InitLoc); 85 const Decl *D = InitLoc->getDecl(); 86 87 // Preconditions. 88 // FIXME: It would be nice if we had a more general mechanism to add 89 // such preconditions. Some day. 90 do { 91 92 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 93 // Precondition: the first argument of 'main' is an integer guaranteed 94 // to be > 0. 95 const IdentifierInfo *II = FD->getIdentifier(); 96 if (!II || !(II->getName() == "main" && FD->getNumParams() > 0)) 97 break; 98 99 const ParmVarDecl *PD = FD->getParamDecl(0); 100 QualType T = PD->getType(); 101 if (!T->isIntegerType()) 102 break; 103 104 const MemRegion *R = state->getRegion(PD, InitLoc); 105 if (!R) 106 break; 107 108 SVal V = state->getSVal(loc::MemRegionVal(R)); 109 SVal Constraint_untested = evalBinOp(state, BO_GT, V, 110 svalBuilder.makeZeroVal(T), 111 getContext().IntTy); 112 113 DefinedOrUnknownSVal *Constraint = 114 dyn_cast<DefinedOrUnknownSVal>(&Constraint_untested); 115 116 if (!Constraint) 117 break; 118 119 if (ProgramStateRef newState = state->assume(*Constraint, true)) 120 state = newState; 121 } 122 break; 123 } 124 while (0); 125 126 if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) { 127 // Precondition: 'self' is always non-null upon entry to an Objective-C 128 // method. 129 const ImplicitParamDecl *SelfD = MD->getSelfDecl(); 130 const MemRegion *R = state->getRegion(SelfD, InitLoc); 131 SVal V = state->getSVal(loc::MemRegionVal(R)); 132 133 if (const Loc *LV = dyn_cast<Loc>(&V)) { 134 // Assume that the pointer value in 'self' is non-null. 135 state = state->assume(*LV, true); 136 assert(state && "'self' cannot be null"); 137 } 138 } 139 140 if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(D)) { 141 if (!MD->isStatic()) { 142 // Precondition: 'this' is always non-null upon entry to the 143 // top-level function. This is our starting assumption for 144 // analyzing an "open" program. 145 const StackFrameContext *SFC = InitLoc->getCurrentStackFrame(); 146 if (SFC->getParent() == 0) { 147 loc::MemRegionVal L(getCXXThisRegion(MD, SFC)); 148 SVal V = state->getSVal(L); 149 if (const Loc *LV = dyn_cast<Loc>(&V)) { 150 state = state->assume(*LV, true); 151 assert(state && "'this' cannot be null"); 152 } 153 } 154 } 155 } 156 157 return state; 158} 159 160//===----------------------------------------------------------------------===// 161// Top-level transfer function logic (Dispatcher). 162//===----------------------------------------------------------------------===// 163 164/// evalAssume - Called by ConstraintManager. Used to call checker-specific 165/// logic for handling assumptions on symbolic values. 166ProgramStateRef ExprEngine::processAssume(ProgramStateRef state, 167 SVal cond, bool assumption) { 168 return getCheckerManager().runCheckersForEvalAssume(state, cond, assumption); 169} 170 171bool ExprEngine::wantsRegionChangeUpdate(ProgramStateRef state) { 172 return getCheckerManager().wantsRegionChangeUpdate(state); 173} 174 175ProgramStateRef 176ExprEngine::processRegionChanges(ProgramStateRef state, 177 const StoreManager::InvalidatedSymbols *invalidated, 178 ArrayRef<const MemRegion *> Explicits, 179 ArrayRef<const MemRegion *> Regions, 180 const CallOrObjCMessage *Call) { 181 return getCheckerManager().runCheckersForRegionChanges(state, invalidated, 182 Explicits, Regions, Call); 183} 184 185void ExprEngine::printState(raw_ostream &Out, ProgramStateRef State, 186 const char *NL, const char *Sep) { 187 getCheckerManager().runCheckersForPrintState(Out, State, NL, Sep); 188} 189 190void ExprEngine::processEndWorklist(bool hasWorkRemaining) { 191 getCheckerManager().runCheckersForEndAnalysis(G, BR, *this); 192} 193 194void ExprEngine::processCFGElement(const CFGElement E, ExplodedNode *Pred, 195 unsigned StmtIdx, NodeBuilderContext *Ctx) { 196 currentStmtIdx = StmtIdx; 197 currentBuilderContext = Ctx; 198 199 switch (E.getKind()) { 200 case CFGElement::Invalid: 201 llvm_unreachable("Unexpected CFGElement kind."); 202 case CFGElement::Statement: 203 ProcessStmt(const_cast<Stmt*>(E.getAs<CFGStmt>()->getStmt()), Pred); 204 return; 205 case CFGElement::Initializer: 206 ProcessInitializer(E.getAs<CFGInitializer>()->getInitializer(), Pred); 207 return; 208 case CFGElement::AutomaticObjectDtor: 209 case CFGElement::BaseDtor: 210 case CFGElement::MemberDtor: 211 case CFGElement::TemporaryDtor: 212 ProcessImplicitDtor(*E.getAs<CFGImplicitDtor>(), Pred); 213 return; 214 } 215} 216 217static bool shouldRemoveDeadBindings(AnalysisManager &AMgr, 218 const CFGStmt S, 219 const ExplodedNode *Pred, 220 const LocationContext *LC) { 221 222 // Are we never purging state values? 223 if (AMgr.getPurgeMode() == PurgeNone) 224 return false; 225 226 // Is this the beginning of a basic block? 227 if (isa<BlockEntrance>(Pred->getLocation())) 228 return true; 229 230 // Is this on a non-expression? 231 if (!isa<Expr>(S.getStmt())) 232 return true; 233 234 // Run before processing a call. 235 if (isa<CallExpr>(S.getStmt())) 236 return true; 237 238 // Is this an expression that is consumed by another expression? If so, 239 // postpone cleaning out the state. 240 ParentMap &PM = LC->getAnalysisDeclContext()->getParentMap(); 241 return !PM.isConsumedExpr(cast<Expr>(S.getStmt())); 242} 243 244void ExprEngine::ProcessStmt(const CFGStmt S, 245 ExplodedNode *Pred) { 246 // Reclaim any unnecessary nodes in the ExplodedGraph. 247 G.reclaimRecentlyAllocatedNodes(); 248 249 currentStmt = S.getStmt(); 250 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 251 currentStmt->getLocStart(), 252 "Error evaluating statement"); 253 254 EntryNode = Pred; 255 256 ProgramStateRef EntryState = EntryNode->getState(); 257 CleanedState = EntryState; 258 259 // Create the cleaned state. 260 const LocationContext *LC = EntryNode->getLocationContext(); 261 SymbolReaper SymReaper(LC, currentStmt, SymMgr, getStoreManager()); 262 263 if (shouldRemoveDeadBindings(AMgr, S, Pred, LC)) { 264 getCheckerManager().runCheckersForLiveSymbols(CleanedState, SymReaper); 265 266 const StackFrameContext *SFC = LC->getCurrentStackFrame(); 267 268 // Create a state in which dead bindings are removed from the environment 269 // and the store. TODO: The function should just return new env and store, 270 // not a new state. 271 CleanedState = StateMgr.removeDeadBindings(CleanedState, SFC, SymReaper); 272 } 273 274 // Process any special transfer function for dead symbols. 275 ExplodedNodeSet Tmp; 276 // A tag to track convenience transitions, which can be removed at cleanup. 277 static SimpleProgramPointTag cleanupTag("ExprEngine : Clean Node"); 278 279 if (!SymReaper.hasDeadSymbols()) { 280 // Generate a CleanedNode that has the environment and store cleaned 281 // up. Since no symbols are dead, we can optimize and not clean out 282 // the constraint manager. 283 StmtNodeBuilder Bldr(Pred, Tmp, *currentBuilderContext); 284 Bldr.generateNode(currentStmt, EntryNode, CleanedState, false, &cleanupTag); 285 286 } else { 287 // Call checkers with the non-cleaned state so that they could query the 288 // values of the soon to be dead symbols. 289 ExplodedNodeSet CheckedSet; 290 getCheckerManager().runCheckersForDeadSymbols(CheckedSet, EntryNode, 291 SymReaper, currentStmt, *this); 292 293 // For each node in CheckedSet, generate CleanedNodes that have the 294 // environment, the store, and the constraints cleaned up but have the 295 // user-supplied states as the predecessors. 296 StmtNodeBuilder Bldr(CheckedSet, Tmp, *currentBuilderContext); 297 for (ExplodedNodeSet::const_iterator 298 I = CheckedSet.begin(), E = CheckedSet.end(); I != E; ++I) { 299 ProgramStateRef CheckerState = (*I)->getState(); 300 301 // The constraint manager has not been cleaned up yet, so clean up now. 302 CheckerState = getConstraintManager().removeDeadBindings(CheckerState, 303 SymReaper); 304 305 assert(StateMgr.haveEqualEnvironments(CheckerState, EntryState) && 306 "Checkers are not allowed to modify the Environment as a part of " 307 "checkDeadSymbols processing."); 308 assert(StateMgr.haveEqualStores(CheckerState, EntryState) && 309 "Checkers are not allowed to modify the Store as a part of " 310 "checkDeadSymbols processing."); 311 312 // Create a state based on CleanedState with CheckerState GDM and 313 // generate a transition to that state. 314 ProgramStateRef CleanedCheckerSt = 315 StateMgr.getPersistentStateWithGDM(CleanedState, CheckerState); 316 Bldr.generateNode(currentStmt, *I, CleanedCheckerSt, false, &cleanupTag, 317 ProgramPoint::PostPurgeDeadSymbolsKind); 318 } 319 } 320 321 ExplodedNodeSet Dst; 322 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { 323 ExplodedNodeSet DstI; 324 // Visit the statement. 325 Visit(currentStmt, *I, DstI); 326 Dst.insert(DstI); 327 } 328 329 // Enqueue the new nodes onto the work list. 330 Engine.enqueue(Dst, currentBuilderContext->getBlock(), currentStmtIdx); 331 332 // NULL out these variables to cleanup. 333 CleanedState = NULL; 334 EntryNode = NULL; 335 currentStmt = 0; 336} 337 338void ExprEngine::ProcessInitializer(const CFGInitializer Init, 339 ExplodedNode *Pred) { 340 ExplodedNodeSet Dst; 341 342 // We don't set EntryNode and currentStmt. And we don't clean up state. 343 const CXXCtorInitializer *BMI = Init.getInitializer(); 344 const StackFrameContext *stackFrame = 345 cast<StackFrameContext>(Pred->getLocationContext()); 346 const CXXConstructorDecl *decl = 347 cast<CXXConstructorDecl>(stackFrame->getDecl()); 348 const CXXThisRegion *thisReg = getCXXThisRegion(decl, stackFrame); 349 350 SVal thisVal = Pred->getState()->getSVal(thisReg); 351 352 if (BMI->isAnyMemberInitializer()) { 353 ExplodedNodeSet AfterEval; 354 355 // Evaluate the initializer. 356 Visit(BMI->getInit(), Pred, AfterEval); 357 358 StmtNodeBuilder Bldr(AfterEval, Dst, *currentBuilderContext); 359 for (ExplodedNodeSet::iterator I = AfterEval.begin(), 360 E = AfterEval.end(); I != E; ++I){ 361 ExplodedNode *P = *I; 362 ProgramStateRef state = P->getState(); 363 364 const FieldDecl *FD = BMI->getAnyMember(); 365 366 SVal FieldLoc = state->getLValue(FD, thisVal); 367 SVal InitVal = state->getSVal(BMI->getInit(), Pred->getLocationContext()); 368 state = state->bindLoc(FieldLoc, InitVal); 369 370 // Use a custom node building process. 371 PostInitializer PP(BMI, stackFrame); 372 // Builder automatically add the generated node to the deferred set, 373 // which are processed in the builder's dtor. 374 Bldr.generateNode(PP, P, state); 375 } 376 } else { 377 assert(BMI->isBaseInitializer()); 378 379 // Get the base class declaration. 380 const CXXConstructExpr *ctorExpr = cast<CXXConstructExpr>(BMI->getInit()); 381 382 // Create the base object region. 383 SVal baseVal = 384 getStoreManager().evalDerivedToBase(thisVal, ctorExpr->getType()); 385 const MemRegion *baseReg = baseVal.getAsRegion(); 386 assert(baseReg); 387 388 VisitCXXConstructExpr(ctorExpr, baseReg, Pred, Dst); 389 } 390 391 // Enqueue the new nodes onto the work list. 392 Engine.enqueue(Dst, currentBuilderContext->getBlock(), currentStmtIdx); 393} 394 395void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D, 396 ExplodedNode *Pred) { 397 ExplodedNodeSet Dst; 398 switch (D.getKind()) { 399 case CFGElement::AutomaticObjectDtor: 400 ProcessAutomaticObjDtor(cast<CFGAutomaticObjDtor>(D), Pred, Dst); 401 break; 402 case CFGElement::BaseDtor: 403 ProcessBaseDtor(cast<CFGBaseDtor>(D), Pred, Dst); 404 break; 405 case CFGElement::MemberDtor: 406 ProcessMemberDtor(cast<CFGMemberDtor>(D), Pred, Dst); 407 break; 408 case CFGElement::TemporaryDtor: 409 ProcessTemporaryDtor(cast<CFGTemporaryDtor>(D), Pred, Dst); 410 break; 411 default: 412 llvm_unreachable("Unexpected dtor kind."); 413 } 414 415 // Enqueue the new nodes onto the work list. 416 Engine.enqueue(Dst, currentBuilderContext->getBlock(), currentStmtIdx); 417} 418 419void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor Dtor, 420 ExplodedNode *Pred, 421 ExplodedNodeSet &Dst) { 422 ProgramStateRef state = Pred->getState(); 423 const VarDecl *varDecl = Dtor.getVarDecl(); 424 425 QualType varType = varDecl->getType(); 426 427 if (const ReferenceType *refType = varType->getAs<ReferenceType>()) 428 varType = refType->getPointeeType(); 429 430 const CXXRecordDecl *recordDecl = varType->getAsCXXRecordDecl(); 431 assert(recordDecl && "get CXXRecordDecl fail"); 432 const CXXDestructorDecl *dtorDecl = recordDecl->getDestructor(); 433 434 Loc dest = state->getLValue(varDecl, Pred->getLocationContext()); 435 436 VisitCXXDestructor(dtorDecl, cast<loc::MemRegionVal>(dest).getRegion(), 437 Dtor.getTriggerStmt(), Pred, Dst); 438} 439 440void ExprEngine::ProcessBaseDtor(const CFGBaseDtor D, 441 ExplodedNode *Pred, ExplodedNodeSet &Dst) {} 442 443void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D, 444 ExplodedNode *Pred, ExplodedNodeSet &Dst) {} 445 446void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D, 447 ExplodedNode *Pred, 448 ExplodedNodeSet &Dst) {} 449 450void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, 451 ExplodedNodeSet &DstTop) { 452 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 453 S->getLocStart(), 454 "Error evaluating statement"); 455 ExplodedNodeSet Dst; 456 StmtNodeBuilder Bldr(Pred, DstTop, *currentBuilderContext); 457 458 // Expressions to ignore. 459 if (const Expr *Ex = dyn_cast<Expr>(S)) 460 S = Ex->IgnoreParens(); 461 462 // FIXME: add metadata to the CFG so that we can disable 463 // this check when we KNOW that there is no block-level subexpression. 464 // The motivation is that this check requires a hashtable lookup. 465 466 if (S != currentStmt && Pred->getLocationContext()->getCFG()->isBlkExpr(S)) 467 return; 468 469 switch (S->getStmtClass()) { 470 // C++ and ARC stuff we don't support yet. 471 case Expr::ObjCIndirectCopyRestoreExprClass: 472 case Stmt::CXXBindTemporaryExprClass: 473 case Stmt::CXXCatchStmtClass: 474 case Stmt::CXXDependentScopeMemberExprClass: 475 case Stmt::CXXPseudoDestructorExprClass: 476 case Stmt::CXXThrowExprClass: 477 case Stmt::CXXTryStmtClass: 478 case Stmt::CXXTypeidExprClass: 479 case Stmt::CXXUuidofExprClass: 480 case Stmt::CXXUnresolvedConstructExprClass: 481 case Stmt::CXXScalarValueInitExprClass: 482 case Stmt::DependentScopeDeclRefExprClass: 483 case Stmt::UnaryTypeTraitExprClass: 484 case Stmt::BinaryTypeTraitExprClass: 485 case Stmt::TypeTraitExprClass: 486 case Stmt::ArrayTypeTraitExprClass: 487 case Stmt::ExpressionTraitExprClass: 488 case Stmt::UnresolvedLookupExprClass: 489 case Stmt::UnresolvedMemberExprClass: 490 case Stmt::CXXNoexceptExprClass: 491 case Stmt::PackExpansionExprClass: 492 case Stmt::SubstNonTypeTemplateParmPackExprClass: 493 case Stmt::SEHTryStmtClass: 494 case Stmt::SEHExceptStmtClass: 495 case Stmt::LambdaExprClass: 496 case Stmt::SEHFinallyStmtClass: { 497 const ExplodedNode *node = Bldr.generateNode(S, Pred, Pred->getState()); 498 Engine.addAbortedBlock(node, currentBuilderContext->getBlock()); 499 break; 500 } 501 502 // We don't handle default arguments either yet, but we can fake it 503 // for now by just skipping them. 504 case Stmt::SubstNonTypeTemplateParmExprClass: 505 case Stmt::CXXDefaultArgExprClass: 506 break; 507 508 case Stmt::ParenExprClass: 509 llvm_unreachable("ParenExprs already handled."); 510 case Stmt::GenericSelectionExprClass: 511 llvm_unreachable("GenericSelectionExprs already handled."); 512 // Cases that should never be evaluated simply because they shouldn't 513 // appear in the CFG. 514 case Stmt::BreakStmtClass: 515 case Stmt::CaseStmtClass: 516 case Stmt::CompoundStmtClass: 517 case Stmt::ContinueStmtClass: 518 case Stmt::CXXForRangeStmtClass: 519 case Stmt::DefaultStmtClass: 520 case Stmt::DoStmtClass: 521 case Stmt::ForStmtClass: 522 case Stmt::GotoStmtClass: 523 case Stmt::IfStmtClass: 524 case Stmt::IndirectGotoStmtClass: 525 case Stmt::LabelStmtClass: 526 case Stmt::NoStmtClass: 527 case Stmt::NullStmtClass: 528 case Stmt::SwitchStmtClass: 529 case Stmt::WhileStmtClass: 530 case Expr::MSDependentExistsStmtClass: 531 llvm_unreachable("Stmt should not be in analyzer evaluation loop"); 532 533 case Stmt::GNUNullExprClass: { 534 // GNU __null is a pointer-width integer, not an actual pointer. 535 ProgramStateRef state = Pred->getState(); 536 state = state->BindExpr(S, Pred->getLocationContext(), 537 svalBuilder.makeIntValWithPtrWidth(0, false)); 538 Bldr.generateNode(S, Pred, state); 539 break; 540 } 541 542 case Stmt::ObjCAtSynchronizedStmtClass: 543 Bldr.takeNodes(Pred); 544 VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S), Pred, Dst); 545 Bldr.addNodes(Dst); 546 break; 547 548 case Stmt::ObjCPropertyRefExprClass: 549 // Implicitly handled by Environment::getSVal(). 550 break; 551 552 case Stmt::ImplicitValueInitExprClass: { 553 ProgramStateRef state = Pred->getState(); 554 QualType ty = cast<ImplicitValueInitExpr>(S)->getType(); 555 SVal val = svalBuilder.makeZeroVal(ty); 556 Bldr.generateNode(S, Pred, state->BindExpr(S, Pred->getLocationContext(), 557 val)); 558 break; 559 } 560 561 case Stmt::ExprWithCleanupsClass: 562 Bldr.takeNodes(Pred); 563 Visit(cast<ExprWithCleanups>(S)->getSubExpr(), Pred, Dst); 564 Bldr.addNodes(Dst); 565 break; 566 567 // Cases not handled yet; but will handle some day. 568 case Stmt::DesignatedInitExprClass: 569 case Stmt::ExtVectorElementExprClass: 570 case Stmt::ImaginaryLiteralClass: 571 case Stmt::ObjCAtCatchStmtClass: 572 case Stmt::ObjCAtFinallyStmtClass: 573 case Stmt::ObjCAtTryStmtClass: 574 case Stmt::ObjCAutoreleasePoolStmtClass: 575 case Stmt::ObjCEncodeExprClass: 576 case Stmt::ObjCIsaExprClass: 577 case Stmt::ObjCProtocolExprClass: 578 case Stmt::ObjCSelectorExprClass: 579 case Stmt::ObjCStringLiteralClass: 580 case Stmt::ParenListExprClass: 581 case Stmt::PredefinedExprClass: 582 case Stmt::ShuffleVectorExprClass: 583 case Stmt::VAArgExprClass: 584 case Stmt::CUDAKernelCallExprClass: 585 case Stmt::OpaqueValueExprClass: 586 case Stmt::AsTypeExprClass: 587 case Stmt::AtomicExprClass: 588 // Fall through. 589 590 // Cases we intentionally don't evaluate, since they don't need 591 // to be explicitly evaluated. 592 case Stmt::AddrLabelExprClass: 593 case Stmt::IntegerLiteralClass: 594 case Stmt::CharacterLiteralClass: 595 case Stmt::CXXBoolLiteralExprClass: 596 case Stmt::FloatingLiteralClass: 597 case Stmt::SizeOfPackExprClass: 598 case Stmt::CXXNullPtrLiteralExprClass: { 599 Bldr.takeNodes(Pred); 600 ExplodedNodeSet preVisit; 601 getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this); 602 getCheckerManager().runCheckersForPostStmt(Dst, preVisit, S, *this); 603 Bldr.addNodes(Dst); 604 break; 605 } 606 607 case Stmt::ArraySubscriptExprClass: 608 Bldr.takeNodes(Pred); 609 VisitLvalArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Pred, Dst); 610 Bldr.addNodes(Dst); 611 break; 612 613 case Stmt::AsmStmtClass: 614 Bldr.takeNodes(Pred); 615 VisitAsmStmt(cast<AsmStmt>(S), Pred, Dst); 616 Bldr.addNodes(Dst); 617 break; 618 619 case Stmt::BlockDeclRefExprClass: { 620 Bldr.takeNodes(Pred); 621 const BlockDeclRefExpr *BE = cast<BlockDeclRefExpr>(S); 622 VisitCommonDeclRefExpr(BE, BE->getDecl(), Pred, Dst); 623 Bldr.addNodes(Dst); 624 break; 625 } 626 627 case Stmt::BlockExprClass: 628 Bldr.takeNodes(Pred); 629 VisitBlockExpr(cast<BlockExpr>(S), Pred, Dst); 630 Bldr.addNodes(Dst); 631 break; 632 633 case Stmt::BinaryOperatorClass: { 634 const BinaryOperator* B = cast<BinaryOperator>(S); 635 if (B->isLogicalOp()) { 636 Bldr.takeNodes(Pred); 637 VisitLogicalExpr(B, Pred, Dst); 638 Bldr.addNodes(Dst); 639 break; 640 } 641 else if (B->getOpcode() == BO_Comma) { 642 ProgramStateRef state = Pred->getState(); 643 Bldr.generateNode(B, Pred, 644 state->BindExpr(B, Pred->getLocationContext(), 645 state->getSVal(B->getRHS(), 646 Pred->getLocationContext()))); 647 break; 648 } 649 650 Bldr.takeNodes(Pred); 651 652 if (AMgr.shouldEagerlyAssume() && 653 (B->isRelationalOp() || B->isEqualityOp())) { 654 ExplodedNodeSet Tmp; 655 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Tmp); 656 evalEagerlyAssume(Dst, Tmp, cast<Expr>(S)); 657 } 658 else 659 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst); 660 661 Bldr.addNodes(Dst); 662 break; 663 } 664 665 case Stmt::CallExprClass: 666 case Stmt::CXXOperatorCallExprClass: 667 case Stmt::CXXMemberCallExprClass: { 668 Bldr.takeNodes(Pred); 669 VisitCallExpr(cast<CallExpr>(S), Pred, Dst); 670 Bldr.addNodes(Dst); 671 break; 672 } 673 674 case Stmt::CXXTemporaryObjectExprClass: 675 case Stmt::CXXConstructExprClass: { 676 const CXXConstructExpr *C = cast<CXXConstructExpr>(S); 677 // For block-level CXXConstructExpr, we don't have a destination region. 678 // Let VisitCXXConstructExpr() create one. 679 Bldr.takeNodes(Pred); 680 VisitCXXConstructExpr(C, 0, Pred, Dst); 681 Bldr.addNodes(Dst); 682 break; 683 } 684 685 case Stmt::CXXNewExprClass: { 686 Bldr.takeNodes(Pred); 687 const CXXNewExpr *NE = cast<CXXNewExpr>(S); 688 VisitCXXNewExpr(NE, Pred, Dst); 689 Bldr.addNodes(Dst); 690 break; 691 } 692 693 case Stmt::CXXDeleteExprClass: { 694 Bldr.takeNodes(Pred); 695 const CXXDeleteExpr *CDE = cast<CXXDeleteExpr>(S); 696 VisitCXXDeleteExpr(CDE, Pred, Dst); 697 Bldr.addNodes(Dst); 698 break; 699 } 700 // FIXME: ChooseExpr is really a constant. We need to fix 701 // the CFG do not model them as explicit control-flow. 702 703 case Stmt::ChooseExprClass: { // __builtin_choose_expr 704 Bldr.takeNodes(Pred); 705 const ChooseExpr *C = cast<ChooseExpr>(S); 706 VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst); 707 Bldr.addNodes(Dst); 708 break; 709 } 710 711 case Stmt::CompoundAssignOperatorClass: 712 Bldr.takeNodes(Pred); 713 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst); 714 Bldr.addNodes(Dst); 715 break; 716 717 case Stmt::CompoundLiteralExprClass: 718 Bldr.takeNodes(Pred); 719 VisitCompoundLiteralExpr(cast<CompoundLiteralExpr>(S), Pred, Dst); 720 Bldr.addNodes(Dst); 721 break; 722 723 case Stmt::BinaryConditionalOperatorClass: 724 case Stmt::ConditionalOperatorClass: { // '?' operator 725 Bldr.takeNodes(Pred); 726 const AbstractConditionalOperator *C 727 = cast<AbstractConditionalOperator>(S); 728 VisitGuardedExpr(C, C->getTrueExpr(), C->getFalseExpr(), Pred, Dst); 729 Bldr.addNodes(Dst); 730 break; 731 } 732 733 case Stmt::CXXThisExprClass: 734 Bldr.takeNodes(Pred); 735 VisitCXXThisExpr(cast<CXXThisExpr>(S), Pred, Dst); 736 Bldr.addNodes(Dst); 737 break; 738 739 case Stmt::DeclRefExprClass: { 740 Bldr.takeNodes(Pred); 741 const DeclRefExpr *DE = cast<DeclRefExpr>(S); 742 VisitCommonDeclRefExpr(DE, DE->getDecl(), Pred, Dst); 743 Bldr.addNodes(Dst); 744 break; 745 } 746 747 case Stmt::DeclStmtClass: 748 Bldr.takeNodes(Pred); 749 VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst); 750 Bldr.addNodes(Dst); 751 break; 752 753 case Stmt::ImplicitCastExprClass: 754 case Stmt::CStyleCastExprClass: 755 case Stmt::CXXStaticCastExprClass: 756 case Stmt::CXXDynamicCastExprClass: 757 case Stmt::CXXReinterpretCastExprClass: 758 case Stmt::CXXConstCastExprClass: 759 case Stmt::CXXFunctionalCastExprClass: 760 case Stmt::ObjCBridgedCastExprClass: { 761 Bldr.takeNodes(Pred); 762 const CastExpr *C = cast<CastExpr>(S); 763 // Handle the previsit checks. 764 ExplodedNodeSet dstPrevisit; 765 getCheckerManager().runCheckersForPreStmt(dstPrevisit, Pred, C, *this); 766 767 // Handle the expression itself. 768 ExplodedNodeSet dstExpr; 769 for (ExplodedNodeSet::iterator i = dstPrevisit.begin(), 770 e = dstPrevisit.end(); i != e ; ++i) { 771 VisitCast(C, C->getSubExpr(), *i, dstExpr); 772 } 773 774 // Handle the postvisit checks. 775 getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, C, *this); 776 Bldr.addNodes(Dst); 777 break; 778 } 779 780 case Expr::MaterializeTemporaryExprClass: { 781 Bldr.takeNodes(Pred); 782 const MaterializeTemporaryExpr *Materialize 783 = cast<MaterializeTemporaryExpr>(S); 784 if (!Materialize->getType()->isRecordType()) 785 CreateCXXTemporaryObject(Materialize, Pred, Dst); 786 else 787 Visit(Materialize->GetTemporaryExpr(), Pred, Dst); 788 Bldr.addNodes(Dst); 789 break; 790 } 791 792 case Stmt::InitListExprClass: 793 Bldr.takeNodes(Pred); 794 VisitInitListExpr(cast<InitListExpr>(S), Pred, Dst); 795 Bldr.addNodes(Dst); 796 break; 797 798 case Stmt::MemberExprClass: 799 Bldr.takeNodes(Pred); 800 VisitMemberExpr(cast<MemberExpr>(S), Pred, Dst); 801 Bldr.addNodes(Dst); 802 break; 803 804 case Stmt::ObjCIvarRefExprClass: 805 Bldr.takeNodes(Pred); 806 VisitLvalObjCIvarRefExpr(cast<ObjCIvarRefExpr>(S), Pred, Dst); 807 Bldr.addNodes(Dst); 808 break; 809 810 case Stmt::ObjCForCollectionStmtClass: 811 Bldr.takeNodes(Pred); 812 VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S), Pred, Dst); 813 Bldr.addNodes(Dst); 814 break; 815 816 case Stmt::ObjCMessageExprClass: { 817 Bldr.takeNodes(Pred); 818 // Is this a property access? 819 const ParentMap &PM = Pred->getLocationContext()->getParentMap(); 820 const ObjCMessageExpr *ME = cast<ObjCMessageExpr>(S); 821 bool evaluated = false; 822 823 if (const PseudoObjectExpr *PO = 824 dyn_cast_or_null<PseudoObjectExpr>(PM.getParent(S))) { 825 const Expr *syntactic = PO->getSyntacticForm(); 826 if (const ObjCPropertyRefExpr *PR = 827 dyn_cast<ObjCPropertyRefExpr>(syntactic)) { 828 bool isSetter = ME->getNumArgs() > 0; 829 VisitObjCMessage(ObjCMessage(ME, PR, isSetter), Pred, Dst); 830 evaluated = true; 831 } 832 else if (isa<BinaryOperator>(syntactic)) { 833 VisitObjCMessage(ObjCMessage(ME, 0, true), Pred, Dst); 834 } 835 } 836 837 if (!evaluated) 838 VisitObjCMessage(ME, Pred, Dst); 839 840 Bldr.addNodes(Dst); 841 break; 842 } 843 844 case Stmt::ObjCAtThrowStmtClass: { 845 // FIXME: This is not complete. We basically treat @throw as 846 // an abort. 847 Bldr.generateNode(S, Pred, Pred->getState()); 848 break; 849 } 850 851 case Stmt::ReturnStmtClass: 852 Bldr.takeNodes(Pred); 853 VisitReturnStmt(cast<ReturnStmt>(S), Pred, Dst); 854 Bldr.addNodes(Dst); 855 break; 856 857 case Stmt::OffsetOfExprClass: 858 Bldr.takeNodes(Pred); 859 VisitOffsetOfExpr(cast<OffsetOfExpr>(S), Pred, Dst); 860 Bldr.addNodes(Dst); 861 break; 862 863 case Stmt::UnaryExprOrTypeTraitExprClass: 864 Bldr.takeNodes(Pred); 865 VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S), 866 Pred, Dst); 867 Bldr.addNodes(Dst); 868 break; 869 870 case Stmt::StmtExprClass: { 871 const StmtExpr *SE = cast<StmtExpr>(S); 872 873 if (SE->getSubStmt()->body_empty()) { 874 // Empty statement expression. 875 assert(SE->getType() == getContext().VoidTy 876 && "Empty statement expression must have void type."); 877 break; 878 } 879 880 if (Expr *LastExpr = dyn_cast<Expr>(*SE->getSubStmt()->body_rbegin())) { 881 ProgramStateRef state = Pred->getState(); 882 Bldr.generateNode(SE, Pred, 883 state->BindExpr(SE, Pred->getLocationContext(), 884 state->getSVal(LastExpr, 885 Pred->getLocationContext()))); 886 } 887 break; 888 } 889 890 case Stmt::StringLiteralClass: { 891 ProgramStateRef state = Pred->getState(); 892 SVal V = state->getLValue(cast<StringLiteral>(S)); 893 Bldr.generateNode(S, Pred, state->BindExpr(S, Pred->getLocationContext(), 894 V)); 895 return; 896 } 897 898 case Stmt::UnaryOperatorClass: { 899 Bldr.takeNodes(Pred); 900 const UnaryOperator *U = cast<UnaryOperator>(S); 901 if (AMgr.shouldEagerlyAssume() && (U->getOpcode() == UO_LNot)) { 902 ExplodedNodeSet Tmp; 903 VisitUnaryOperator(U, Pred, Tmp); 904 evalEagerlyAssume(Dst, Tmp, U); 905 } 906 else 907 VisitUnaryOperator(U, Pred, Dst); 908 Bldr.addNodes(Dst); 909 break; 910 } 911 912 case Stmt::PseudoObjectExprClass: { 913 Bldr.takeNodes(Pred); 914 ProgramStateRef state = Pred->getState(); 915 const PseudoObjectExpr *PE = cast<PseudoObjectExpr>(S); 916 if (const Expr *Result = PE->getResultExpr()) { 917 SVal V = state->getSVal(Result, Pred->getLocationContext()); 918 Bldr.generateNode(S, Pred, 919 state->BindExpr(S, Pred->getLocationContext(), V)); 920 } 921 else 922 Bldr.generateNode(S, Pred, 923 state->BindExpr(S, Pred->getLocationContext(), 924 UnknownVal())); 925 926 Bldr.addNodes(Dst); 927 break; 928 } 929 } 930} 931 932/// Block entrance. (Update counters). 933void ExprEngine::processCFGBlockEntrance(NodeBuilderWithSinks &nodeBuilder) { 934 935 // FIXME: Refactor this into a checker. 936 ExplodedNode *pred = nodeBuilder.getContext().getPred(); 937 938 if (nodeBuilder.getContext().getCurrentBlockCount() >= AMgr.getMaxVisit()) { 939 static SimpleProgramPointTag tag("ExprEngine : Block count exceeded"); 940 nodeBuilder.generateNode(pred->getState(), pred, &tag, true); 941 } 942} 943 944//===----------------------------------------------------------------------===// 945// Branch processing. 946//===----------------------------------------------------------------------===// 947 948ProgramStateRef ExprEngine::MarkBranch(ProgramStateRef state, 949 const Stmt *Terminator, 950 const LocationContext *LCtx, 951 bool branchTaken) { 952 953 switch (Terminator->getStmtClass()) { 954 default: 955 return state; 956 957 case Stmt::BinaryOperatorClass: { // '&&' and '||' 958 959 const BinaryOperator* B = cast<BinaryOperator>(Terminator); 960 BinaryOperator::Opcode Op = B->getOpcode(); 961 962 assert (Op == BO_LAnd || Op == BO_LOr); 963 964 // For &&, if we take the true branch, then the value of the whole 965 // expression is that of the RHS expression. 966 // 967 // For ||, if we take the false branch, then the value of the whole 968 // expression is that of the RHS expression. 969 970 const Expr *Ex = (Op == BO_LAnd && branchTaken) || 971 (Op == BO_LOr && !branchTaken) 972 ? B->getRHS() : B->getLHS(); 973 974 return state->BindExpr(B, LCtx, UndefinedVal(Ex)); 975 } 976 977 case Stmt::BinaryConditionalOperatorClass: 978 case Stmt::ConditionalOperatorClass: { // ?: 979 const AbstractConditionalOperator* C 980 = cast<AbstractConditionalOperator>(Terminator); 981 982 // For ?, if branchTaken == true then the value is either the LHS or 983 // the condition itself. (GNU extension). 984 985 const Expr *Ex; 986 987 if (branchTaken) 988 Ex = C->getTrueExpr(); 989 else 990 Ex = C->getFalseExpr(); 991 992 return state->BindExpr(C, LCtx, UndefinedVal(Ex)); 993 } 994 995 case Stmt::ChooseExprClass: { // ?: 996 997 const ChooseExpr *C = cast<ChooseExpr>(Terminator); 998 999 const Expr *Ex = branchTaken ? C->getLHS() : C->getRHS(); 1000 return state->BindExpr(C, LCtx, UndefinedVal(Ex)); 1001 } 1002 } 1003} 1004 1005/// RecoverCastedSymbol - A helper function for ProcessBranch that is used 1006/// to try to recover some path-sensitivity for casts of symbolic 1007/// integers that promote their values (which are currently not tracked well). 1008/// This function returns the SVal bound to Condition->IgnoreCasts if all the 1009// cast(s) did was sign-extend the original value. 1010static SVal RecoverCastedSymbol(ProgramStateManager& StateMgr, 1011 ProgramStateRef state, 1012 const Stmt *Condition, 1013 const LocationContext *LCtx, 1014 ASTContext &Ctx) { 1015 1016 const Expr *Ex = dyn_cast<Expr>(Condition); 1017 if (!Ex) 1018 return UnknownVal(); 1019 1020 uint64_t bits = 0; 1021 bool bitsInit = false; 1022 1023 while (const CastExpr *CE = dyn_cast<CastExpr>(Ex)) { 1024 QualType T = CE->getType(); 1025 1026 if (!T->isIntegerType()) 1027 return UnknownVal(); 1028 1029 uint64_t newBits = Ctx.getTypeSize(T); 1030 if (!bitsInit || newBits < bits) { 1031 bitsInit = true; 1032 bits = newBits; 1033 } 1034 1035 Ex = CE->getSubExpr(); 1036 } 1037 1038 // We reached a non-cast. Is it a symbolic value? 1039 QualType T = Ex->getType(); 1040 1041 if (!bitsInit || !T->isIntegerType() || Ctx.getTypeSize(T) > bits) 1042 return UnknownVal(); 1043 1044 return state->getSVal(Ex, LCtx); 1045} 1046 1047void ExprEngine::processBranch(const Stmt *Condition, const Stmt *Term, 1048 NodeBuilderContext& BldCtx, 1049 ExplodedNode *Pred, 1050 ExplodedNodeSet &Dst, 1051 const CFGBlock *DstT, 1052 const CFGBlock *DstF) { 1053 currentBuilderContext = &BldCtx; 1054 1055 // Check for NULL conditions; e.g. "for(;;)" 1056 if (!Condition) { 1057 BranchNodeBuilder NullCondBldr(Pred, Dst, BldCtx, DstT, DstF); 1058 NullCondBldr.markInfeasible(false); 1059 NullCondBldr.generateNode(Pred->getState(), true, Pred); 1060 return; 1061 } 1062 1063 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 1064 Condition->getLocStart(), 1065 "Error evaluating branch"); 1066 1067 ExplodedNodeSet CheckersOutSet; 1068 getCheckerManager().runCheckersForBranchCondition(Condition, CheckersOutSet, 1069 Pred, *this); 1070 // We generated only sinks. 1071 if (CheckersOutSet.empty()) 1072 return; 1073 1074 BranchNodeBuilder builder(CheckersOutSet, Dst, BldCtx, DstT, DstF); 1075 for (NodeBuilder::iterator I = CheckersOutSet.begin(), 1076 E = CheckersOutSet.end(); E != I; ++I) { 1077 ExplodedNode *PredI = *I; 1078 1079 if (PredI->isSink()) 1080 continue; 1081 1082 ProgramStateRef PrevState = Pred->getState(); 1083 SVal X = PrevState->getSVal(Condition, Pred->getLocationContext()); 1084 1085 if (X.isUnknownOrUndef()) { 1086 // Give it a chance to recover from unknown. 1087 if (const Expr *Ex = dyn_cast<Expr>(Condition)) { 1088 if (Ex->getType()->isIntegerType()) { 1089 // Try to recover some path-sensitivity. Right now casts of symbolic 1090 // integers that promote their values are currently not tracked well. 1091 // If 'Condition' is such an expression, try and recover the 1092 // underlying value and use that instead. 1093 SVal recovered = RecoverCastedSymbol(getStateManager(), 1094 PrevState, Condition, 1095 Pred->getLocationContext(), 1096 getContext()); 1097 1098 if (!recovered.isUnknown()) { 1099 X = recovered; 1100 } 1101 } 1102 } 1103 } 1104 1105 const LocationContext *LCtx = PredI->getLocationContext(); 1106 1107 // If the condition is still unknown, give up. 1108 if (X.isUnknownOrUndef()) { 1109 builder.generateNode(MarkBranch(PrevState, Term, LCtx, true), 1110 true, PredI); 1111 builder.generateNode(MarkBranch(PrevState, Term, LCtx, false), 1112 false, PredI); 1113 continue; 1114 } 1115 1116 DefinedSVal V = cast<DefinedSVal>(X); 1117 1118 // Process the true branch. 1119 if (builder.isFeasible(true)) { 1120 if (ProgramStateRef state = PrevState->assume(V, true)) 1121 builder.generateNode(MarkBranch(state, Term, LCtx, true), 1122 true, PredI); 1123 else 1124 builder.markInfeasible(true); 1125 } 1126 1127 // Process the false branch. 1128 if (builder.isFeasible(false)) { 1129 if (ProgramStateRef state = PrevState->assume(V, false)) 1130 builder.generateNode(MarkBranch(state, Term, LCtx, false), 1131 false, PredI); 1132 else 1133 builder.markInfeasible(false); 1134 } 1135 } 1136 currentBuilderContext = 0; 1137} 1138 1139/// processIndirectGoto - Called by CoreEngine. Used to generate successor 1140/// nodes by processing the 'effects' of a computed goto jump. 1141void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) { 1142 1143 ProgramStateRef state = builder.getState(); 1144 SVal V = state->getSVal(builder.getTarget(), builder.getLocationContext()); 1145 1146 // Three possibilities: 1147 // 1148 // (1) We know the computed label. 1149 // (2) The label is NULL (or some other constant), or Undefined. 1150 // (3) We have no clue about the label. Dispatch to all targets. 1151 // 1152 1153 typedef IndirectGotoNodeBuilder::iterator iterator; 1154 1155 if (isa<loc::GotoLabel>(V)) { 1156 const LabelDecl *L = cast<loc::GotoLabel>(V).getLabel(); 1157 1158 for (iterator I = builder.begin(), E = builder.end(); I != E; ++I) { 1159 if (I.getLabel() == L) { 1160 builder.generateNode(I, state); 1161 return; 1162 } 1163 } 1164 1165 llvm_unreachable("No block with label."); 1166 } 1167 1168 if (isa<loc::ConcreteInt>(V) || isa<UndefinedVal>(V)) { 1169 // Dispatch to the first target and mark it as a sink. 1170 //ExplodedNode* N = builder.generateNode(builder.begin(), state, true); 1171 // FIXME: add checker visit. 1172 // UndefBranches.insert(N); 1173 return; 1174 } 1175 1176 // This is really a catch-all. We don't support symbolics yet. 1177 // FIXME: Implement dispatch for symbolic pointers. 1178 1179 for (iterator I=builder.begin(), E=builder.end(); I != E; ++I) 1180 builder.generateNode(I, state); 1181} 1182 1183/// ProcessEndPath - Called by CoreEngine. Used to generate end-of-path 1184/// nodes when the control reaches the end of a function. 1185void ExprEngine::processEndOfFunction(NodeBuilderContext& BC) { 1186 StateMgr.EndPath(BC.Pred->getState()); 1187 ExplodedNodeSet Dst; 1188 getCheckerManager().runCheckersForEndPath(BC, Dst, *this); 1189 Engine.enqueueEndOfFunction(Dst); 1190} 1191 1192/// ProcessSwitch - Called by CoreEngine. Used to generate successor 1193/// nodes by processing the 'effects' of a switch statement. 1194void ExprEngine::processSwitch(SwitchNodeBuilder& builder) { 1195 typedef SwitchNodeBuilder::iterator iterator; 1196 ProgramStateRef state = builder.getState(); 1197 const Expr *CondE = builder.getCondition(); 1198 SVal CondV_untested = state->getSVal(CondE, builder.getLocationContext()); 1199 1200 if (CondV_untested.isUndef()) { 1201 //ExplodedNode* N = builder.generateDefaultCaseNode(state, true); 1202 // FIXME: add checker 1203 //UndefBranches.insert(N); 1204 1205 return; 1206 } 1207 DefinedOrUnknownSVal CondV = cast<DefinedOrUnknownSVal>(CondV_untested); 1208 1209 ProgramStateRef DefaultSt = state; 1210 1211 iterator I = builder.begin(), EI = builder.end(); 1212 bool defaultIsFeasible = I == EI; 1213 1214 for ( ; I != EI; ++I) { 1215 // Successor may be pruned out during CFG construction. 1216 if (!I.getBlock()) 1217 continue; 1218 1219 const CaseStmt *Case = I.getCase(); 1220 1221 // Evaluate the LHS of the case value. 1222 llvm::APSInt V1 = Case->getLHS()->EvaluateKnownConstInt(getContext()); 1223 assert(V1.getBitWidth() == getContext().getTypeSize(CondE->getType())); 1224 1225 // Get the RHS of the case, if it exists. 1226 llvm::APSInt V2; 1227 if (const Expr *E = Case->getRHS()) 1228 V2 = E->EvaluateKnownConstInt(getContext()); 1229 else 1230 V2 = V1; 1231 1232 // FIXME: Eventually we should replace the logic below with a range 1233 // comparison, rather than concretize the values within the range. 1234 // This should be easy once we have "ranges" for NonLVals. 1235 1236 do { 1237 nonloc::ConcreteInt CaseVal(getBasicVals().getValue(V1)); 1238 DefinedOrUnknownSVal Res = svalBuilder.evalEQ(DefaultSt ? DefaultSt : state, 1239 CondV, CaseVal); 1240 1241 // Now "assume" that the case matches. 1242 if (ProgramStateRef stateNew = state->assume(Res, true)) { 1243 builder.generateCaseStmtNode(I, stateNew); 1244 1245 // If CondV evaluates to a constant, then we know that this 1246 // is the *only* case that we can take, so stop evaluating the 1247 // others. 1248 if (isa<nonloc::ConcreteInt>(CondV)) 1249 return; 1250 } 1251 1252 // Now "assume" that the case doesn't match. Add this state 1253 // to the default state (if it is feasible). 1254 if (DefaultSt) { 1255 if (ProgramStateRef stateNew = DefaultSt->assume(Res, false)) { 1256 defaultIsFeasible = true; 1257 DefaultSt = stateNew; 1258 } 1259 else { 1260 defaultIsFeasible = false; 1261 DefaultSt = NULL; 1262 } 1263 } 1264 1265 // Concretize the next value in the range. 1266 if (V1 == V2) 1267 break; 1268 1269 ++V1; 1270 assert (V1 <= V2); 1271 1272 } while (true); 1273 } 1274 1275 if (!defaultIsFeasible) 1276 return; 1277 1278 // If we have switch(enum value), the default branch is not 1279 // feasible if all of the enum constants not covered by 'case:' statements 1280 // are not feasible values for the switch condition. 1281 // 1282 // Note that this isn't as accurate as it could be. Even if there isn't 1283 // a case for a particular enum value as long as that enum value isn't 1284 // feasible then it shouldn't be considered for making 'default:' reachable. 1285 const SwitchStmt *SS = builder.getSwitch(); 1286 const Expr *CondExpr = SS->getCond()->IgnoreParenImpCasts(); 1287 if (CondExpr->getType()->getAs<EnumType>()) { 1288 if (SS->isAllEnumCasesCovered()) 1289 return; 1290 } 1291 1292 builder.generateDefaultCaseNode(DefaultSt); 1293} 1294 1295//===----------------------------------------------------------------------===// 1296// Transfer functions: Loads and stores. 1297//===----------------------------------------------------------------------===// 1298 1299void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D, 1300 ExplodedNode *Pred, 1301 ExplodedNodeSet &Dst) { 1302 StmtNodeBuilder Bldr(Pred, Dst, *currentBuilderContext); 1303 1304 ProgramStateRef state = Pred->getState(); 1305 const LocationContext *LCtx = Pred->getLocationContext(); 1306 1307 if (const VarDecl *VD = dyn_cast<VarDecl>(D)) { 1308 assert(Ex->isLValue()); 1309 SVal V = state->getLValue(VD, Pred->getLocationContext()); 1310 1311 // For references, the 'lvalue' is the pointer address stored in the 1312 // reference region. 1313 if (VD->getType()->isReferenceType()) { 1314 if (const MemRegion *R = V.getAsRegion()) 1315 V = state->getSVal(R); 1316 else 1317 V = UnknownVal(); 1318 } 1319 1320 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), false, 0, 1321 ProgramPoint::PostLValueKind); 1322 return; 1323 } 1324 if (const EnumConstantDecl *ED = dyn_cast<EnumConstantDecl>(D)) { 1325 assert(!Ex->isLValue()); 1326 SVal V = svalBuilder.makeIntVal(ED->getInitVal()); 1327 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V)); 1328 return; 1329 } 1330 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 1331 SVal V = svalBuilder.getFunctionPointer(FD); 1332 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), false, 0, 1333 ProgramPoint::PostLValueKind); 1334 return; 1335 } 1336 assert (false && 1337 "ValueDecl support for this ValueDecl not implemented."); 1338} 1339 1340/// VisitArraySubscriptExpr - Transfer function for array accesses 1341void ExprEngine::VisitLvalArraySubscriptExpr(const ArraySubscriptExpr *A, 1342 ExplodedNode *Pred, 1343 ExplodedNodeSet &Dst){ 1344 1345 const Expr *Base = A->getBase()->IgnoreParens(); 1346 const Expr *Idx = A->getIdx()->IgnoreParens(); 1347 1348 1349 ExplodedNodeSet checkerPreStmt; 1350 getCheckerManager().runCheckersForPreStmt(checkerPreStmt, Pred, A, *this); 1351 1352 StmtNodeBuilder Bldr(checkerPreStmt, Dst, *currentBuilderContext); 1353 1354 for (ExplodedNodeSet::iterator it = checkerPreStmt.begin(), 1355 ei = checkerPreStmt.end(); it != ei; ++it) { 1356 const LocationContext *LCtx = (*it)->getLocationContext(); 1357 ProgramStateRef state = (*it)->getState(); 1358 SVal V = state->getLValue(A->getType(), 1359 state->getSVal(Idx, LCtx), 1360 state->getSVal(Base, LCtx)); 1361 assert(A->isLValue()); 1362 Bldr.generateNode(A, *it, state->BindExpr(A, LCtx, V), 1363 false, 0, ProgramPoint::PostLValueKind); 1364 } 1365} 1366 1367/// VisitMemberExpr - Transfer function for member expressions. 1368void ExprEngine::VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred, 1369 ExplodedNodeSet &TopDst) { 1370 1371 StmtNodeBuilder Bldr(Pred, TopDst, *currentBuilderContext); 1372 ExplodedNodeSet Dst; 1373 Decl *member = M->getMemberDecl(); 1374 if (VarDecl *VD = dyn_cast<VarDecl>(member)) { 1375 assert(M->isLValue()); 1376 Bldr.takeNodes(Pred); 1377 VisitCommonDeclRefExpr(M, VD, Pred, Dst); 1378 Bldr.addNodes(Dst); 1379 return; 1380 } 1381 1382 FieldDecl *field = dyn_cast<FieldDecl>(member); 1383 if (!field) // FIXME: skipping member expressions for non-fields 1384 return; 1385 1386 Expr *baseExpr = M->getBase()->IgnoreParens(); 1387 ProgramStateRef state = Pred->getState(); 1388 const LocationContext *LCtx = Pred->getLocationContext(); 1389 SVal baseExprVal = state->getSVal(baseExpr, Pred->getLocationContext()); 1390 if (isa<nonloc::LazyCompoundVal>(baseExprVal) || 1391 isa<nonloc::CompoundVal>(baseExprVal) || 1392 // FIXME: This can originate by conjuring a symbol for an unknown 1393 // temporary struct object, see test/Analysis/fields.c: 1394 // (p = getit()).x 1395 isa<nonloc::SymbolVal>(baseExprVal)) { 1396 Bldr.generateNode(M, Pred, state->BindExpr(M, LCtx, UnknownVal())); 1397 return; 1398 } 1399 1400 // FIXME: Should we insert some assumption logic in here to determine 1401 // if "Base" is a valid piece of memory? Before we put this assumption 1402 // later when using FieldOffset lvals (which we no longer have). 1403 1404 // For all other cases, compute an lvalue. 1405 SVal L = state->getLValue(field, baseExprVal); 1406 if (M->isLValue()) 1407 Bldr.generateNode(M, Pred, state->BindExpr(M, LCtx, L), false, 0, 1408 ProgramPoint::PostLValueKind); 1409 else { 1410 Bldr.takeNodes(Pred); 1411 evalLoad(Dst, M, Pred, state, L); 1412 Bldr.addNodes(Dst); 1413 } 1414} 1415 1416/// evalBind - Handle the semantics of binding a value to a specific location. 1417/// This method is used by evalStore and (soon) VisitDeclStmt, and others. 1418void ExprEngine::evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE, 1419 ExplodedNode *Pred, 1420 SVal location, SVal Val, bool atDeclInit, 1421 ProgramPoint::Kind PointKind) { 1422 1423 // Do a previsit of the bind. 1424 ExplodedNodeSet CheckedSet; 1425 getCheckerManager().runCheckersForBind(CheckedSet, Pred, location, Val, 1426 StoreE, *this, PointKind); 1427 1428 // TODO:AZ Remove TmpDst after NB refactoring is done. 1429 ExplodedNodeSet TmpDst; 1430 StmtNodeBuilder Bldr(CheckedSet, TmpDst, *currentBuilderContext); 1431 1432 for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end(); 1433 I!=E; ++I) { 1434 ProgramStateRef state = (*I)->getState(); 1435 1436 if (atDeclInit) { 1437 const VarRegion *VR = 1438 cast<VarRegion>(cast<loc::MemRegionVal>(location).getRegion()); 1439 1440 state = state->bindDecl(VR, Val); 1441 } else { 1442 state = state->bindLoc(location, Val); 1443 } 1444 1445 Bldr.generateNode(StoreE, *I, state, false, 0, PointKind); 1446 } 1447 1448 Dst.insert(TmpDst); 1449} 1450 1451/// evalStore - Handle the semantics of a store via an assignment. 1452/// @param Dst The node set to store generated state nodes 1453/// @param AssignE The assignment expression if the store happens in an 1454/// assignment. 1455/// @param LocatioinE The location expression that is stored to. 1456/// @param state The current simulation state 1457/// @param location The location to store the value 1458/// @param Val The value to be stored 1459void ExprEngine::evalStore(ExplodedNodeSet &Dst, const Expr *AssignE, 1460 const Expr *LocationE, 1461 ExplodedNode *Pred, 1462 ProgramStateRef state, SVal location, SVal Val, 1463 const ProgramPointTag *tag) { 1464 // Proceed with the store. We use AssignE as the anchor for the PostStore 1465 // ProgramPoint if it is non-NULL, and LocationE otherwise. 1466 const Expr *StoreE = AssignE ? AssignE : LocationE; 1467 1468 if (isa<loc::ObjCPropRef>(location)) { 1469 assert(false); 1470 } 1471 1472 // Evaluate the location (checks for bad dereferences). 1473 ExplodedNodeSet Tmp; 1474 evalLocation(Tmp, LocationE, Pred, state, location, tag, false); 1475 1476 if (Tmp.empty()) 1477 return; 1478 1479 if (location.isUndef()) 1480 return; 1481 1482 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) 1483 evalBind(Dst, StoreE, *NI, location, Val, false, 1484 ProgramPoint::PostStoreKind); 1485} 1486 1487void ExprEngine::evalLoad(ExplodedNodeSet &Dst, const Expr *Ex, 1488 ExplodedNode *Pred, 1489 ProgramStateRef state, SVal location, 1490 const ProgramPointTag *tag, QualType LoadTy) { 1491 assert(!isa<NonLoc>(location) && "location cannot be a NonLoc."); 1492 1493 if (isa<loc::ObjCPropRef>(location)) { 1494 assert(false); 1495 } 1496 1497 // Are we loading from a region? This actually results in two loads; one 1498 // to fetch the address of the referenced value and one to fetch the 1499 // referenced value. 1500 if (const TypedValueRegion *TR = 1501 dyn_cast_or_null<TypedValueRegion>(location.getAsRegion())) { 1502 1503 QualType ValTy = TR->getValueType(); 1504 if (const ReferenceType *RT = ValTy->getAs<ReferenceType>()) { 1505 static SimpleProgramPointTag 1506 loadReferenceTag("ExprEngine : Load Reference"); 1507 ExplodedNodeSet Tmp; 1508 evalLoadCommon(Tmp, Ex, Pred, state, location, &loadReferenceTag, 1509 getContext().getPointerType(RT->getPointeeType())); 1510 1511 // Perform the load from the referenced value. 1512 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end() ; I!=E; ++I) { 1513 state = (*I)->getState(); 1514 location = state->getSVal(Ex, (*I)->getLocationContext()); 1515 evalLoadCommon(Dst, Ex, *I, state, location, tag, LoadTy); 1516 } 1517 return; 1518 } 1519 } 1520 1521 evalLoadCommon(Dst, Ex, Pred, state, location, tag, LoadTy); 1522} 1523 1524void ExprEngine::evalLoadCommon(ExplodedNodeSet &Dst, const Expr *Ex, 1525 ExplodedNode *Pred, 1526 ProgramStateRef state, SVal location, 1527 const ProgramPointTag *tag, QualType LoadTy) { 1528 1529 // Evaluate the location (checks for bad dereferences). 1530 ExplodedNodeSet Tmp; 1531 evalLocation(Tmp, Ex, Pred, state, location, tag, true); 1532 if (Tmp.empty()) 1533 return; 1534 1535 StmtNodeBuilder Bldr(Tmp, Dst, *currentBuilderContext); 1536 if (location.isUndef()) 1537 return; 1538 1539 // Proceed with the load. 1540 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) { 1541 state = (*NI)->getState(); 1542 const LocationContext *LCtx = (*NI)->getLocationContext(); 1543 1544 if (location.isUnknown()) { 1545 // This is important. We must nuke the old binding. 1546 Bldr.generateNode(Ex, *NI, state->BindExpr(Ex, LCtx, UnknownVal()), 1547 false, tag, ProgramPoint::PostLoadKind); 1548 } 1549 else { 1550 if (LoadTy.isNull()) 1551 LoadTy = Ex->getType(); 1552 SVal V = state->getSVal(cast<Loc>(location), LoadTy); 1553 Bldr.generateNode(Ex, *NI, state->bindExprAndLocation(Ex, LCtx, 1554 location, V), 1555 false, tag, ProgramPoint::PostLoadKind); 1556 } 1557 } 1558} 1559 1560void ExprEngine::evalLocation(ExplodedNodeSet &Dst, const Stmt *S, 1561 ExplodedNode *Pred, 1562 ProgramStateRef state, SVal location, 1563 const ProgramPointTag *tag, bool isLoad) { 1564 StmtNodeBuilder BldrTop(Pred, Dst, *currentBuilderContext); 1565 // Early checks for performance reason. 1566 if (location.isUnknown()) { 1567 return; 1568 } 1569 1570 ExplodedNodeSet Src; 1571 BldrTop.takeNodes(Pred); 1572 StmtNodeBuilder Bldr(Pred, Src, *currentBuilderContext); 1573 if (Pred->getState() != state) { 1574 // Associate this new state with an ExplodedNode. 1575 // FIXME: If I pass null tag, the graph is incorrect, e.g for 1576 // int *p; 1577 // p = 0; 1578 // *p = 0xDEADBEEF; 1579 // "p = 0" is not noted as "Null pointer value stored to 'p'" but 1580 // instead "int *p" is noted as 1581 // "Variable 'p' initialized to a null pointer value" 1582 1583 // FIXME: why is 'tag' not used instead of etag? 1584 static SimpleProgramPointTag etag("ExprEngine: Location"); 1585 1586 Bldr.generateNode(S, Pred, state, false, &etag); 1587 } 1588 ExplodedNodeSet Tmp; 1589 getCheckerManager().runCheckersForLocation(Tmp, Src, location, isLoad, S, 1590 *this); 1591 BldrTop.addNodes(Tmp); 1592} 1593 1594std::pair<const ProgramPointTag *, const ProgramPointTag*> 1595ExprEngine::getEagerlyAssumeTags() { 1596 static SimpleProgramPointTag 1597 EagerlyAssumeTrue("ExprEngine : Eagerly Assume True"), 1598 EagerlyAssumeFalse("ExprEngine : Eagerly Assume False"); 1599 return std::make_pair(&EagerlyAssumeTrue, &EagerlyAssumeFalse); 1600} 1601 1602void ExprEngine::evalEagerlyAssume(ExplodedNodeSet &Dst, ExplodedNodeSet &Src, 1603 const Expr *Ex) { 1604 StmtNodeBuilder Bldr(Src, Dst, *currentBuilderContext); 1605 1606 for (ExplodedNodeSet::iterator I=Src.begin(), E=Src.end(); I!=E; ++I) { 1607 ExplodedNode *Pred = *I; 1608 // Test if the previous node was as the same expression. This can happen 1609 // when the expression fails to evaluate to anything meaningful and 1610 // (as an optimization) we don't generate a node. 1611 ProgramPoint P = Pred->getLocation(); 1612 if (!isa<PostStmt>(P) || cast<PostStmt>(P).getStmt() != Ex) { 1613 continue; 1614 } 1615 1616 ProgramStateRef state = Pred->getState(); 1617 SVal V = state->getSVal(Ex, Pred->getLocationContext()); 1618 nonloc::SymbolVal *SEV = dyn_cast<nonloc::SymbolVal>(&V); 1619 if (SEV && SEV->isExpression()) { 1620 const std::pair<const ProgramPointTag *, const ProgramPointTag*> &tags = 1621 getEagerlyAssumeTags(); 1622 1623 // First assume that the condition is true. 1624 if (ProgramStateRef StateTrue = state->assume(*SEV, true)) { 1625 SVal Val = svalBuilder.makeIntVal(1U, Ex->getType()); 1626 StateTrue = StateTrue->BindExpr(Ex, Pred->getLocationContext(), Val); 1627 Bldr.generateNode(Ex, Pred, StateTrue, false, tags.first); 1628 } 1629 1630 // Next, assume that the condition is false. 1631 if (ProgramStateRef StateFalse = state->assume(*SEV, false)) { 1632 SVal Val = svalBuilder.makeIntVal(0U, Ex->getType()); 1633 StateFalse = StateFalse->BindExpr(Ex, Pred->getLocationContext(), Val); 1634 Bldr.generateNode(Ex, Pred, StateFalse, false, tags.second); 1635 } 1636 } 1637 } 1638} 1639 1640void ExprEngine::VisitAsmStmt(const AsmStmt *A, ExplodedNode *Pred, 1641 ExplodedNodeSet &Dst) { 1642 VisitAsmStmtHelperOutputs(A, A->begin_outputs(), A->end_outputs(), Pred, Dst); 1643} 1644 1645void ExprEngine::VisitAsmStmtHelperOutputs(const AsmStmt *A, 1646 AsmStmt::const_outputs_iterator I, 1647 AsmStmt::const_outputs_iterator E, 1648 ExplodedNode *Pred, ExplodedNodeSet &Dst) { 1649 if (I == E) { 1650 VisitAsmStmtHelperInputs(A, A->begin_inputs(), A->end_inputs(), Pred, Dst); 1651 return; 1652 } 1653 1654 ExplodedNodeSet Tmp; 1655 Visit(*I, Pred, Tmp); 1656 ++I; 1657 1658 for (ExplodedNodeSet::iterator NI = Tmp.begin(), NE = Tmp.end();NI != NE;++NI) 1659 VisitAsmStmtHelperOutputs(A, I, E, *NI, Dst); 1660} 1661 1662void ExprEngine::VisitAsmStmtHelperInputs(const AsmStmt *A, 1663 AsmStmt::const_inputs_iterator I, 1664 AsmStmt::const_inputs_iterator E, 1665 ExplodedNode *Pred, 1666 ExplodedNodeSet &Dst) { 1667 if (I == E) { 1668 StmtNodeBuilder Bldr(Pred, Dst, *currentBuilderContext); 1669 // We have processed both the inputs and the outputs. All of the outputs 1670 // should evaluate to Locs. Nuke all of their values. 1671 1672 // FIXME: Some day in the future it would be nice to allow a "plug-in" 1673 // which interprets the inline asm and stores proper results in the 1674 // outputs. 1675 1676 ProgramStateRef state = Pred->getState(); 1677 1678 for (AsmStmt::const_outputs_iterator OI = A->begin_outputs(), 1679 OE = A->end_outputs(); OI != OE; ++OI) { 1680 1681 SVal X = state->getSVal(*OI, Pred->getLocationContext()); 1682 assert (!isa<NonLoc>(X)); // Should be an Lval, or unknown, undef. 1683 1684 if (isa<Loc>(X)) 1685 state = state->bindLoc(cast<Loc>(X), UnknownVal()); 1686 } 1687 1688 Bldr.generateNode(A, Pred, state); 1689 return; 1690 } 1691 1692 ExplodedNodeSet Tmp; 1693 Visit(*I, Pred, Tmp); 1694 1695 ++I; 1696 1697 for (ExplodedNodeSet::iterator NI = Tmp.begin(), NE = Tmp.end(); NI!=NE; ++NI) 1698 VisitAsmStmtHelperInputs(A, I, E, *NI, Dst); 1699} 1700 1701 1702//===----------------------------------------------------------------------===// 1703// Visualization. 1704//===----------------------------------------------------------------------===// 1705 1706#ifndef NDEBUG 1707static ExprEngine* GraphPrintCheckerState; 1708static SourceManager* GraphPrintSourceManager; 1709 1710namespace llvm { 1711template<> 1712struct DOTGraphTraits<ExplodedNode*> : 1713 public DefaultDOTGraphTraits { 1714 1715 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} 1716 1717 // FIXME: Since we do not cache error nodes in ExprEngine now, this does not 1718 // work. 1719 static std::string getNodeAttributes(const ExplodedNode *N, void*) { 1720 1721#if 0 1722 // FIXME: Replace with a general scheme to tell if the node is 1723 // an error node. 1724 if (GraphPrintCheckerState->isImplicitNullDeref(N) || 1725 GraphPrintCheckerState->isExplicitNullDeref(N) || 1726 GraphPrintCheckerState->isUndefDeref(N) || 1727 GraphPrintCheckerState->isUndefStore(N) || 1728 GraphPrintCheckerState->isUndefControlFlow(N) || 1729 GraphPrintCheckerState->isUndefResult(N) || 1730 GraphPrintCheckerState->isBadCall(N) || 1731 GraphPrintCheckerState->isUndefArg(N)) 1732 return "color=\"red\",style=\"filled\""; 1733 1734 if (GraphPrintCheckerState->isNoReturnCall(N)) 1735 return "color=\"blue\",style=\"filled\""; 1736#endif 1737 return ""; 1738 } 1739 1740 static std::string getNodeLabel(const ExplodedNode *N, void*){ 1741 1742 std::string sbuf; 1743 llvm::raw_string_ostream Out(sbuf); 1744 1745 // Program Location. 1746 ProgramPoint Loc = N->getLocation(); 1747 1748 switch (Loc.getKind()) { 1749 case ProgramPoint::BlockEntranceKind: 1750 Out << "Block Entrance: B" 1751 << cast<BlockEntrance>(Loc).getBlock()->getBlockID(); 1752 break; 1753 1754 case ProgramPoint::BlockExitKind: 1755 assert (false); 1756 break; 1757 1758 case ProgramPoint::CallEnterKind: 1759 Out << "CallEnter"; 1760 break; 1761 1762 case ProgramPoint::CallExitKind: 1763 Out << "CallExit"; 1764 break; 1765 1766 default: { 1767 if (StmtPoint *L = dyn_cast<StmtPoint>(&Loc)) { 1768 const Stmt *S = L->getStmt(); 1769 SourceLocation SLoc = S->getLocStart(); 1770 1771 Out << S->getStmtClassName() << ' ' << (void*) S << ' '; 1772 LangOptions LO; // FIXME. 1773 S->printPretty(Out, 0, PrintingPolicy(LO)); 1774 1775 if (SLoc.isFileID()) { 1776 Out << "\\lline=" 1777 << GraphPrintSourceManager->getExpansionLineNumber(SLoc) 1778 << " col=" 1779 << GraphPrintSourceManager->getExpansionColumnNumber(SLoc) 1780 << "\\l"; 1781 } 1782 1783 if (isa<PreStmt>(Loc)) 1784 Out << "\\lPreStmt\\l;"; 1785 else if (isa<PostLoad>(Loc)) 1786 Out << "\\lPostLoad\\l;"; 1787 else if (isa<PostStore>(Loc)) 1788 Out << "\\lPostStore\\l"; 1789 else if (isa<PostLValue>(Loc)) 1790 Out << "\\lPostLValue\\l"; 1791 1792#if 0 1793 // FIXME: Replace with a general scheme to determine 1794 // the name of the check. 1795 if (GraphPrintCheckerState->isImplicitNullDeref(N)) 1796 Out << "\\|Implicit-Null Dereference.\\l"; 1797 else if (GraphPrintCheckerState->isExplicitNullDeref(N)) 1798 Out << "\\|Explicit-Null Dereference.\\l"; 1799 else if (GraphPrintCheckerState->isUndefDeref(N)) 1800 Out << "\\|Dereference of undefialied value.\\l"; 1801 else if (GraphPrintCheckerState->isUndefStore(N)) 1802 Out << "\\|Store to Undefined Loc."; 1803 else if (GraphPrintCheckerState->isUndefResult(N)) 1804 Out << "\\|Result of operation is undefined."; 1805 else if (GraphPrintCheckerState->isNoReturnCall(N)) 1806 Out << "\\|Call to function marked \"noreturn\"."; 1807 else if (GraphPrintCheckerState->isBadCall(N)) 1808 Out << "\\|Call to NULL/Undefined."; 1809 else if (GraphPrintCheckerState->isUndefArg(N)) 1810 Out << "\\|Argument in call is undefined"; 1811#endif 1812 1813 break; 1814 } 1815 1816 const BlockEdge &E = cast<BlockEdge>(Loc); 1817 Out << "Edge: (B" << E.getSrc()->getBlockID() << ", B" 1818 << E.getDst()->getBlockID() << ')'; 1819 1820 if (const Stmt *T = E.getSrc()->getTerminator()) { 1821 1822 SourceLocation SLoc = T->getLocStart(); 1823 1824 Out << "\\|Terminator: "; 1825 LangOptions LO; // FIXME. 1826 E.getSrc()->printTerminator(Out, LO); 1827 1828 if (SLoc.isFileID()) { 1829 Out << "\\lline=" 1830 << GraphPrintSourceManager->getExpansionLineNumber(SLoc) 1831 << " col=" 1832 << GraphPrintSourceManager->getExpansionColumnNumber(SLoc); 1833 } 1834 1835 if (isa<SwitchStmt>(T)) { 1836 const Stmt *Label = E.getDst()->getLabel(); 1837 1838 if (Label) { 1839 if (const CaseStmt *C = dyn_cast<CaseStmt>(Label)) { 1840 Out << "\\lcase "; 1841 LangOptions LO; // FIXME. 1842 C->getLHS()->printPretty(Out, 0, PrintingPolicy(LO)); 1843 1844 if (const Stmt *RHS = C->getRHS()) { 1845 Out << " .. "; 1846 RHS->printPretty(Out, 0, PrintingPolicy(LO)); 1847 } 1848 1849 Out << ":"; 1850 } 1851 else { 1852 assert (isa<DefaultStmt>(Label)); 1853 Out << "\\ldefault:"; 1854 } 1855 } 1856 else 1857 Out << "\\l(implicit) default:"; 1858 } 1859 else if (isa<IndirectGotoStmt>(T)) { 1860 // FIXME 1861 } 1862 else { 1863 Out << "\\lCondition: "; 1864 if (*E.getSrc()->succ_begin() == E.getDst()) 1865 Out << "true"; 1866 else 1867 Out << "false"; 1868 } 1869 1870 Out << "\\l"; 1871 } 1872 1873#if 0 1874 // FIXME: Replace with a general scheme to determine 1875 // the name of the check. 1876 if (GraphPrintCheckerState->isUndefControlFlow(N)) { 1877 Out << "\\|Control-flow based on\\lUndefined value.\\l"; 1878 } 1879#endif 1880 } 1881 } 1882 1883 ProgramStateRef state = N->getState(); 1884 Out << "\\|StateID: " << (void*) state.getPtr() 1885 << " NodeID: " << (void*) N << "\\|"; 1886 state->printDOT(Out); 1887 1888 Out << "\\l"; 1889 1890 if (const ProgramPointTag *tag = Loc.getTag()) { 1891 Out << "\\|Tag: " << tag->getTagDescription(); 1892 Out << "\\l"; 1893 } 1894 return Out.str(); 1895 } 1896}; 1897} // end llvm namespace 1898#endif 1899 1900#ifndef NDEBUG 1901template <typename ITERATOR> 1902ExplodedNode *GetGraphNode(ITERATOR I) { return *I; } 1903 1904template <> ExplodedNode* 1905GetGraphNode<llvm::DenseMap<ExplodedNode*, Expr*>::iterator> 1906 (llvm::DenseMap<ExplodedNode*, Expr*>::iterator I) { 1907 return I->first; 1908} 1909#endif 1910 1911void ExprEngine::ViewGraph(bool trim) { 1912#ifndef NDEBUG 1913 if (trim) { 1914 std::vector<ExplodedNode*> Src; 1915 1916 // Flush any outstanding reports to make sure we cover all the nodes. 1917 // This does not cause them to get displayed. 1918 for (BugReporter::iterator I=BR.begin(), E=BR.end(); I!=E; ++I) 1919 const_cast<BugType*>(*I)->FlushReports(BR); 1920 1921 // Iterate through the reports and get their nodes. 1922 for (BugReporter::EQClasses_iterator 1923 EI = BR.EQClasses_begin(), EE = BR.EQClasses_end(); EI != EE; ++EI) { 1924 BugReportEquivClass& EQ = *EI; 1925 const BugReport &R = **EQ.begin(); 1926 ExplodedNode *N = const_cast<ExplodedNode*>(R.getErrorNode()); 1927 if (N) Src.push_back(N); 1928 } 1929 1930 ViewGraph(&Src[0], &Src[0]+Src.size()); 1931 } 1932 else { 1933 GraphPrintCheckerState = this; 1934 GraphPrintSourceManager = &getContext().getSourceManager(); 1935 1936 llvm::ViewGraph(*G.roots_begin(), "ExprEngine"); 1937 1938 GraphPrintCheckerState = NULL; 1939 GraphPrintSourceManager = NULL; 1940 } 1941#endif 1942} 1943 1944void ExprEngine::ViewGraph(ExplodedNode** Beg, ExplodedNode** End) { 1945#ifndef NDEBUG 1946 GraphPrintCheckerState = this; 1947 GraphPrintSourceManager = &getContext().getSourceManager(); 1948 1949 std::auto_ptr<ExplodedGraph> TrimmedG(G.Trim(Beg, End).first); 1950 1951 if (!TrimmedG.get()) 1952 llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n"; 1953 else 1954 llvm::ViewGraph(*TrimmedG->roots_begin(), "TrimmedExprEngine"); 1955 1956 GraphPrintCheckerState = NULL; 1957 GraphPrintSourceManager = NULL; 1958#endif 1959} 1960