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