ExprEngine.cpp revision 0f5c5c60e9806d13f0907cd99d7204ffab0e08f7
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#define DEBUG_TYPE "ExprEngine" 17 18#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 19#include "clang/AST/CharUnits.h" 20#include "clang/AST/ParentMap.h" 21#include "clang/AST/StmtCXX.h" 22#include "clang/AST/StmtObjC.h" 23#include "clang/Basic/Builtins.h" 24#include "clang/Basic/PrettyStackTrace.h" 25#include "clang/Basic/SourceManager.h" 26#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 27#include "clang/StaticAnalyzer/Core/CheckerManager.h" 28#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" 29#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 30#include "llvm/ADT/ImmutableList.h" 31#include "llvm/ADT/Statistic.h" 32#include "llvm/Support/raw_ostream.h" 33 34#ifndef NDEBUG 35#include "llvm/Support/GraphWriter.h" 36#endif 37 38using namespace clang; 39using namespace ento; 40using llvm::APSInt; 41 42STATISTIC(NumRemoveDeadBindings, 43 "The # of times RemoveDeadBindings is called"); 44STATISTIC(NumMaxBlockCountReached, 45 "The # of aborted paths due to reaching the maximum block count in " 46 "a top level function"); 47STATISTIC(NumMaxBlockCountReachedInInlined, 48 "The # of aborted paths due to reaching the maximum block count in " 49 "an inlined function"); 50STATISTIC(NumTimesRetriedWithoutInlining, 51 "The # of times we re-evaluated a call without inlining"); 52 53//===----------------------------------------------------------------------===// 54// Engine construction and deletion. 55//===----------------------------------------------------------------------===// 56 57ExprEngine::ExprEngine(AnalysisManager &mgr, bool gcEnabled, 58 SetOfConstDecls *VisitedCalleesIn, 59 FunctionSummariesTy *FS, 60 InliningModes HowToInlineIn) 61 : AMgr(mgr), 62 AnalysisDeclContexts(mgr.getAnalysisDeclContextManager()), 63 Engine(*this, FS), 64 G(Engine.getGraph()), 65 StateMgr(getContext(), mgr.getStoreManagerCreator(), 66 mgr.getConstraintManagerCreator(), G.getAllocator(), 67 this), 68 SymMgr(StateMgr.getSymbolManager()), 69 svalBuilder(StateMgr.getSValBuilder()), 70 currStmtIdx(0), currBldrCtx(0), 71 ObjCNoRet(mgr.getASTContext()), 72 ObjCGCEnabled(gcEnabled), BR(mgr, *this), 73 VisitedCallees(VisitedCalleesIn), 74 HowToInline(HowToInlineIn) 75{ 76 unsigned TrimInterval = mgr.options.getGraphTrimInterval(); 77 if (TrimInterval != 0) { 78 // Enable eager node reclaimation when constructing the ExplodedGraph. 79 G.enableNodeReclamation(TrimInterval); 80 } 81} 82 83ExprEngine::~ExprEngine() { 84 BR.FlushReports(); 85} 86 87//===----------------------------------------------------------------------===// 88// Utility methods. 89//===----------------------------------------------------------------------===// 90 91ProgramStateRef ExprEngine::getInitialState(const LocationContext *InitLoc) { 92 ProgramStateRef state = StateMgr.getInitialState(InitLoc); 93 const Decl *D = InitLoc->getDecl(); 94 95 // Preconditions. 96 // FIXME: It would be nice if we had a more general mechanism to add 97 // such preconditions. Some day. 98 do { 99 100 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 101 // Precondition: the first argument of 'main' is an integer guaranteed 102 // to be > 0. 103 const IdentifierInfo *II = FD->getIdentifier(); 104 if (!II || !(II->getName() == "main" && FD->getNumParams() > 0)) 105 break; 106 107 const ParmVarDecl *PD = FD->getParamDecl(0); 108 QualType T = PD->getType(); 109 if (!T->isIntegerType()) 110 break; 111 112 const MemRegion *R = state->getRegion(PD, InitLoc); 113 if (!R) 114 break; 115 116 SVal V = state->getSVal(loc::MemRegionVal(R)); 117 SVal Constraint_untested = evalBinOp(state, BO_GT, V, 118 svalBuilder.makeZeroVal(T), 119 getContext().IntTy); 120 121 Optional<DefinedOrUnknownSVal> Constraint = 122 Constraint_untested.getAs<DefinedOrUnknownSVal>(); 123 124 if (!Constraint) 125 break; 126 127 if (ProgramStateRef newState = state->assume(*Constraint, true)) 128 state = newState; 129 } 130 break; 131 } 132 while (0); 133 134 if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) { 135 // Precondition: 'self' is always non-null upon entry to an Objective-C 136 // method. 137 const ImplicitParamDecl *SelfD = MD->getSelfDecl(); 138 const MemRegion *R = state->getRegion(SelfD, InitLoc); 139 SVal V = state->getSVal(loc::MemRegionVal(R)); 140 141 if (Optional<Loc> LV = V.getAs<Loc>()) { 142 // Assume that the pointer value in 'self' is non-null. 143 state = state->assume(*LV, true); 144 assert(state && "'self' cannot be null"); 145 } 146 } 147 148 if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(D)) { 149 if (!MD->isStatic()) { 150 // Precondition: 'this' is always non-null upon entry to the 151 // top-level function. This is our starting assumption for 152 // analyzing an "open" program. 153 const StackFrameContext *SFC = InitLoc->getCurrentStackFrame(); 154 if (SFC->getParent() == 0) { 155 loc::MemRegionVal L = svalBuilder.getCXXThis(MD, SFC); 156 SVal V = state->getSVal(L); 157 if (Optional<Loc> LV = V.getAs<Loc>()) { 158 state = state->assume(*LV, true); 159 assert(state && "'this' cannot be null"); 160 } 161 } 162 } 163 } 164 165 return state; 166} 167 168ProgramStateRef 169ExprEngine::createTemporaryRegionIfNeeded(ProgramStateRef State, 170 const LocationContext *LC, 171 const Expr *Ex, 172 const Expr *Result) { 173 SVal V = State->getSVal(Ex, LC); 174 if (!Result && !V.getAs<NonLoc>()) 175 return State; 176 177 ProgramStateManager &StateMgr = State->getStateManager(); 178 MemRegionManager &MRMgr = StateMgr.getRegionManager(); 179 StoreManager &StoreMgr = StateMgr.getStoreManager(); 180 181 // We need to be careful about treating a derived type's value as 182 // bindings for a base type. Start by stripping and recording base casts. 183 SmallVector<const CastExpr *, 4> Casts; 184 const Expr *Inner = Ex->IgnoreParens(); 185 if (V.getAs<NonLoc>()) { 186 while (const CastExpr *CE = dyn_cast<CastExpr>(Inner)) { 187 if (CE->getCastKind() == CK_DerivedToBase || 188 CE->getCastKind() == CK_UncheckedDerivedToBase) 189 Casts.push_back(CE); 190 else if (CE->getCastKind() != CK_NoOp) 191 break; 192 193 Inner = CE->getSubExpr()->IgnoreParens(); 194 } 195 } 196 197 // Create a temporary object region for the inner expression (which may have 198 // a more derived type) and bind the NonLoc value into it. 199 SVal Reg = loc::MemRegionVal(MRMgr.getCXXTempObjectRegion(Inner, LC)); 200 State = State->bindLoc(Reg, V); 201 202 // Re-apply the casts (from innermost to outermost) for type sanity. 203 for (SmallVectorImpl<const CastExpr *>::reverse_iterator I = Casts.rbegin(), 204 E = Casts.rend(); 205 I != E; ++I) { 206 Reg = StoreMgr.evalDerivedToBase(Reg, *I); 207 } 208 209 State = State->BindExpr(Result ? Result : Ex, LC, Reg); 210 return State; 211} 212 213//===----------------------------------------------------------------------===// 214// Top-level transfer function logic (Dispatcher). 215//===----------------------------------------------------------------------===// 216 217/// evalAssume - Called by ConstraintManager. Used to call checker-specific 218/// logic for handling assumptions on symbolic values. 219ProgramStateRef ExprEngine::processAssume(ProgramStateRef state, 220 SVal cond, bool assumption) { 221 return getCheckerManager().runCheckersForEvalAssume(state, cond, assumption); 222} 223 224bool ExprEngine::wantsRegionChangeUpdate(ProgramStateRef state) { 225 return getCheckerManager().wantsRegionChangeUpdate(state); 226} 227 228ProgramStateRef 229ExprEngine::processRegionChanges(ProgramStateRef state, 230 const InvalidatedSymbols *invalidated, 231 ArrayRef<const MemRegion *> Explicits, 232 ArrayRef<const MemRegion *> Regions, 233 const CallEvent *Call) { 234 return getCheckerManager().runCheckersForRegionChanges(state, invalidated, 235 Explicits, Regions, Call); 236} 237 238void ExprEngine::printState(raw_ostream &Out, ProgramStateRef State, 239 const char *NL, const char *Sep) { 240 getCheckerManager().runCheckersForPrintState(Out, State, NL, Sep); 241} 242 243void ExprEngine::processEndWorklist(bool hasWorkRemaining) { 244 getCheckerManager().runCheckersForEndAnalysis(G, BR, *this); 245} 246 247void ExprEngine::processCFGElement(const CFGElement E, ExplodedNode *Pred, 248 unsigned StmtIdx, NodeBuilderContext *Ctx) { 249 currStmtIdx = StmtIdx; 250 currBldrCtx = Ctx; 251 252 switch (E.getKind()) { 253 case CFGElement::Statement: 254 ProcessStmt(const_cast<Stmt*>(E.castAs<CFGStmt>().getStmt()), Pred); 255 return; 256 case CFGElement::Initializer: 257 ProcessInitializer(E.castAs<CFGInitializer>().getInitializer(), Pred); 258 return; 259 case CFGElement::AutomaticObjectDtor: 260 case CFGElement::BaseDtor: 261 case CFGElement::MemberDtor: 262 case CFGElement::TemporaryDtor: 263 ProcessImplicitDtor(E.castAs<CFGImplicitDtor>(), Pred); 264 return; 265 } 266 currBldrCtx = 0; 267} 268 269static bool shouldRemoveDeadBindings(AnalysisManager &AMgr, 270 const CFGStmt S, 271 const ExplodedNode *Pred, 272 const LocationContext *LC) { 273 274 // Are we never purging state values? 275 if (AMgr.options.AnalysisPurgeOpt == PurgeNone) 276 return false; 277 278 // Is this the beginning of a basic block? 279 if (Pred->getLocation().getAs<BlockEntrance>()) 280 return true; 281 282 // Is this on a non-expression? 283 if (!isa<Expr>(S.getStmt())) 284 return true; 285 286 // Run before processing a call. 287 if (CallEvent::isCallStmt(S.getStmt())) 288 return true; 289 290 // Is this an expression that is consumed by another expression? If so, 291 // postpone cleaning out the state. 292 ParentMap &PM = LC->getAnalysisDeclContext()->getParentMap(); 293 return !PM.isConsumedExpr(cast<Expr>(S.getStmt())); 294} 295 296void ExprEngine::removeDead(ExplodedNode *Pred, ExplodedNodeSet &Out, 297 const Stmt *ReferenceStmt, 298 const LocationContext *LC, 299 const Stmt *DiagnosticStmt, 300 ProgramPoint::Kind K) { 301 assert((K == ProgramPoint::PreStmtPurgeDeadSymbolsKind || 302 ReferenceStmt == 0 || isa<ReturnStmt>(ReferenceStmt)) 303 && "PostStmt is not generally supported by the SymbolReaper yet"); 304 assert(LC && "Must pass the current (or expiring) LocationContext"); 305 306 if (!DiagnosticStmt) { 307 DiagnosticStmt = ReferenceStmt; 308 assert(DiagnosticStmt && "Required for clearing a LocationContext"); 309 } 310 311 NumRemoveDeadBindings++; 312 ProgramStateRef CleanedState = Pred->getState(); 313 314 // LC is the location context being destroyed, but SymbolReaper wants a 315 // location context that is still live. (If this is the top-level stack 316 // frame, this will be null.) 317 if (!ReferenceStmt) { 318 assert(K == ProgramPoint::PostStmtPurgeDeadSymbolsKind && 319 "Use PostStmtPurgeDeadSymbolsKind for clearing a LocationContext"); 320 LC = LC->getParent(); 321 } 322 323 const StackFrameContext *SFC = LC ? LC->getCurrentStackFrame() : 0; 324 SymbolReaper SymReaper(SFC, ReferenceStmt, SymMgr, getStoreManager()); 325 326 getCheckerManager().runCheckersForLiveSymbols(CleanedState, SymReaper); 327 328 // Create a state in which dead bindings are removed from the environment 329 // and the store. TODO: The function should just return new env and store, 330 // not a new state. 331 CleanedState = StateMgr.removeDeadBindings(CleanedState, SFC, SymReaper); 332 333 // Process any special transfer function for dead symbols. 334 // A tag to track convenience transitions, which can be removed at cleanup. 335 static SimpleProgramPointTag cleanupTag("ExprEngine : Clean Node"); 336 if (!SymReaper.hasDeadSymbols()) { 337 // Generate a CleanedNode that has the environment and store cleaned 338 // up. Since no symbols are dead, we can optimize and not clean out 339 // the constraint manager. 340 StmtNodeBuilder Bldr(Pred, Out, *currBldrCtx); 341 Bldr.generateNode(DiagnosticStmt, Pred, CleanedState, &cleanupTag, K); 342 343 } else { 344 // Call checkers with the non-cleaned state so that they could query the 345 // values of the soon to be dead symbols. 346 ExplodedNodeSet CheckedSet; 347 getCheckerManager().runCheckersForDeadSymbols(CheckedSet, Pred, SymReaper, 348 DiagnosticStmt, *this, K); 349 350 // For each node in CheckedSet, generate CleanedNodes that have the 351 // environment, the store, and the constraints cleaned up but have the 352 // user-supplied states as the predecessors. 353 StmtNodeBuilder Bldr(CheckedSet, Out, *currBldrCtx); 354 for (ExplodedNodeSet::const_iterator 355 I = CheckedSet.begin(), E = CheckedSet.end(); I != E; ++I) { 356 ProgramStateRef CheckerState = (*I)->getState(); 357 358 // The constraint manager has not been cleaned up yet, so clean up now. 359 CheckerState = getConstraintManager().removeDeadBindings(CheckerState, 360 SymReaper); 361 362 assert(StateMgr.haveEqualEnvironments(CheckerState, Pred->getState()) && 363 "Checkers are not allowed to modify the Environment as a part of " 364 "checkDeadSymbols processing."); 365 assert(StateMgr.haveEqualStores(CheckerState, Pred->getState()) && 366 "Checkers are not allowed to modify the Store as a part of " 367 "checkDeadSymbols processing."); 368 369 // Create a state based on CleanedState with CheckerState GDM and 370 // generate a transition to that state. 371 ProgramStateRef CleanedCheckerSt = 372 StateMgr.getPersistentStateWithGDM(CleanedState, CheckerState); 373 Bldr.generateNode(DiagnosticStmt, *I, CleanedCheckerSt, &cleanupTag, K); 374 } 375 } 376} 377 378void ExprEngine::ProcessStmt(const CFGStmt S, 379 ExplodedNode *Pred) { 380 // Reclaim any unnecessary nodes in the ExplodedGraph. 381 G.reclaimRecentlyAllocatedNodes(); 382 383 const Stmt *currStmt = S.getStmt(); 384 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 385 currStmt->getLocStart(), 386 "Error evaluating statement"); 387 388 // Remove dead bindings and symbols. 389 ExplodedNodeSet CleanedStates; 390 if (shouldRemoveDeadBindings(AMgr, S, Pred, Pred->getLocationContext())){ 391 removeDead(Pred, CleanedStates, currStmt, Pred->getLocationContext()); 392 } else 393 CleanedStates.Add(Pred); 394 395 // Visit the statement. 396 ExplodedNodeSet Dst; 397 for (ExplodedNodeSet::iterator I = CleanedStates.begin(), 398 E = CleanedStates.end(); I != E; ++I) { 399 ExplodedNodeSet DstI; 400 // Visit the statement. 401 Visit(currStmt, *I, DstI); 402 Dst.insert(DstI); 403 } 404 405 // Enqueue the new nodes onto the work list. 406 Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx); 407} 408 409void ExprEngine::ProcessInitializer(const CFGInitializer Init, 410 ExplodedNode *Pred) { 411 const CXXCtorInitializer *BMI = Init.getInitializer(); 412 413 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 414 BMI->getSourceLocation(), 415 "Error evaluating initializer"); 416 417 // We don't clean up dead bindings here. 418 const StackFrameContext *stackFrame = 419 cast<StackFrameContext>(Pred->getLocationContext()); 420 const CXXConstructorDecl *decl = 421 cast<CXXConstructorDecl>(stackFrame->getDecl()); 422 423 ProgramStateRef State = Pred->getState(); 424 SVal thisVal = State->getSVal(svalBuilder.getCXXThis(decl, stackFrame)); 425 426 PostInitializer PP(BMI, stackFrame); 427 ExplodedNodeSet Tmp(Pred); 428 429 // Evaluate the initializer, if necessary 430 if (BMI->isAnyMemberInitializer()) { 431 // Constructors build the object directly in the field, 432 // but non-objects must be copied in from the initializer. 433 const Expr *Init = BMI->getInit()->IgnoreImplicit(); 434 if (!isa<CXXConstructExpr>(Init)) { 435 SVal FieldLoc; 436 if (BMI->isIndirectMemberInitializer()) 437 FieldLoc = State->getLValue(BMI->getIndirectMember(), thisVal); 438 else 439 FieldLoc = State->getLValue(BMI->getMember(), thisVal); 440 441 SVal InitVal = State->getSVal(BMI->getInit(), stackFrame); 442 443 Tmp.clear(); 444 evalBind(Tmp, Init, Pred, FieldLoc, InitVal, /*isInit=*/true, &PP); 445 } 446 } else { 447 assert(BMI->isBaseInitializer() || BMI->isDelegatingInitializer()); 448 // We already did all the work when visiting the CXXConstructExpr. 449 } 450 451 // Construct PostInitializer nodes whether the state changed or not, 452 // so that the diagnostics don't get confused. 453 ExplodedNodeSet Dst; 454 NodeBuilder Bldr(Tmp, Dst, *currBldrCtx); 455 for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I != E; ++I) { 456 ExplodedNode *N = *I; 457 Bldr.generateNode(PP, N->getState(), N); 458 } 459 460 // Enqueue the new nodes onto the work list. 461 Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx); 462} 463 464void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D, 465 ExplodedNode *Pred) { 466 ExplodedNodeSet Dst; 467 switch (D.getKind()) { 468 case CFGElement::AutomaticObjectDtor: 469 ProcessAutomaticObjDtor(D.castAs<CFGAutomaticObjDtor>(), Pred, Dst); 470 break; 471 case CFGElement::BaseDtor: 472 ProcessBaseDtor(D.castAs<CFGBaseDtor>(), Pred, Dst); 473 break; 474 case CFGElement::MemberDtor: 475 ProcessMemberDtor(D.castAs<CFGMemberDtor>(), Pred, Dst); 476 break; 477 case CFGElement::TemporaryDtor: 478 ProcessTemporaryDtor(D.castAs<CFGTemporaryDtor>(), Pred, Dst); 479 break; 480 default: 481 llvm_unreachable("Unexpected dtor kind."); 482 } 483 484 // Enqueue the new nodes onto the work list. 485 Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx); 486} 487 488void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor Dtor, 489 ExplodedNode *Pred, 490 ExplodedNodeSet &Dst) { 491 ProgramStateRef state = Pred->getState(); 492 const VarDecl *varDecl = Dtor.getVarDecl(); 493 494 QualType varType = varDecl->getType(); 495 496 if (const ReferenceType *refType = varType->getAs<ReferenceType>()) 497 varType = refType->getPointeeType(); 498 499 Loc dest = state->getLValue(varDecl, Pred->getLocationContext()); 500 501 VisitCXXDestructor(varType, dest.castAs<loc::MemRegionVal>().getRegion(), 502 Dtor.getTriggerStmt(), /*IsBase=*/ false, Pred, Dst); 503} 504 505void ExprEngine::ProcessBaseDtor(const CFGBaseDtor D, 506 ExplodedNode *Pred, ExplodedNodeSet &Dst) { 507 const LocationContext *LCtx = Pred->getLocationContext(); 508 ProgramStateRef State = Pred->getState(); 509 510 const CXXDestructorDecl *CurDtor = cast<CXXDestructorDecl>(LCtx->getDecl()); 511 Loc ThisPtr = getSValBuilder().getCXXThis(CurDtor, 512 LCtx->getCurrentStackFrame()); 513 SVal ThisVal = Pred->getState()->getSVal(ThisPtr); 514 515 // Create the base object region. 516 const CXXBaseSpecifier *Base = D.getBaseSpecifier(); 517 QualType BaseTy = Base->getType(); 518 SVal BaseVal = getStoreManager().evalDerivedToBase(ThisVal, BaseTy, 519 Base->isVirtual()); 520 521 VisitCXXDestructor(BaseTy, BaseVal.castAs<loc::MemRegionVal>().getRegion(), 522 CurDtor->getBody(), /*IsBase=*/ true, Pred, Dst); 523} 524 525void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D, 526 ExplodedNode *Pred, ExplodedNodeSet &Dst) { 527 const FieldDecl *Member = D.getFieldDecl(); 528 ProgramStateRef State = Pred->getState(); 529 const LocationContext *LCtx = Pred->getLocationContext(); 530 531 const CXXDestructorDecl *CurDtor = cast<CXXDestructorDecl>(LCtx->getDecl()); 532 Loc ThisVal = getSValBuilder().getCXXThis(CurDtor, 533 LCtx->getCurrentStackFrame()); 534 SVal FieldVal = 535 State->getLValue(Member, State->getSVal(ThisVal).castAs<Loc>()); 536 537 VisitCXXDestructor(Member->getType(), 538 FieldVal.castAs<loc::MemRegionVal>().getRegion(), 539 CurDtor->getBody(), /*IsBase=*/false, Pred, Dst); 540} 541 542void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D, 543 ExplodedNode *Pred, 544 ExplodedNodeSet &Dst) {} 545 546void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, 547 ExplodedNodeSet &DstTop) { 548 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 549 S->getLocStart(), 550 "Error evaluating statement"); 551 ExplodedNodeSet Dst; 552 StmtNodeBuilder Bldr(Pred, DstTop, *currBldrCtx); 553 554 assert(!isa<Expr>(S) || S == cast<Expr>(S)->IgnoreParens()); 555 556 switch (S->getStmtClass()) { 557 // C++ and ARC stuff we don't support yet. 558 case Expr::ObjCIndirectCopyRestoreExprClass: 559 case Stmt::CXXDependentScopeMemberExprClass: 560 case Stmt::CXXPseudoDestructorExprClass: 561 case Stmt::CXXTryStmtClass: 562 case Stmt::CXXTypeidExprClass: 563 case Stmt::CXXUuidofExprClass: 564 case Stmt::CXXUnresolvedConstructExprClass: 565 case Stmt::DependentScopeDeclRefExprClass: 566 case Stmt::UnaryTypeTraitExprClass: 567 case Stmt::BinaryTypeTraitExprClass: 568 case Stmt::TypeTraitExprClass: 569 case Stmt::ArrayTypeTraitExprClass: 570 case Stmt::ExpressionTraitExprClass: 571 case Stmt::UnresolvedLookupExprClass: 572 case Stmt::UnresolvedMemberExprClass: 573 case Stmt::CXXNoexceptExprClass: 574 case Stmt::PackExpansionExprClass: 575 case Stmt::SubstNonTypeTemplateParmPackExprClass: 576 case Stmt::FunctionParmPackExprClass: 577 case Stmt::SEHTryStmtClass: 578 case Stmt::SEHExceptStmtClass: 579 case Stmt::LambdaExprClass: 580 case Stmt::SEHFinallyStmtClass: { 581 const ExplodedNode *node = Bldr.generateSink(S, Pred, Pred->getState()); 582 Engine.addAbortedBlock(node, currBldrCtx->getBlock()); 583 break; 584 } 585 586 case Stmt::ParenExprClass: 587 llvm_unreachable("ParenExprs already handled."); 588 case Stmt::GenericSelectionExprClass: 589 llvm_unreachable("GenericSelectionExprs already handled."); 590 // Cases that should never be evaluated simply because they shouldn't 591 // appear in the CFG. 592 case Stmt::BreakStmtClass: 593 case Stmt::CaseStmtClass: 594 case Stmt::CompoundStmtClass: 595 case Stmt::ContinueStmtClass: 596 case Stmt::CXXForRangeStmtClass: 597 case Stmt::DefaultStmtClass: 598 case Stmt::DoStmtClass: 599 case Stmt::ForStmtClass: 600 case Stmt::GotoStmtClass: 601 case Stmt::IfStmtClass: 602 case Stmt::IndirectGotoStmtClass: 603 case Stmt::LabelStmtClass: 604 case Stmt::AttributedStmtClass: 605 case Stmt::NoStmtClass: 606 case Stmt::NullStmtClass: 607 case Stmt::SwitchStmtClass: 608 case Stmt::WhileStmtClass: 609 case Expr::MSDependentExistsStmtClass: 610 llvm_unreachable("Stmt should not be in analyzer evaluation loop"); 611 612 case Stmt::ObjCSubscriptRefExprClass: 613 case Stmt::ObjCPropertyRefExprClass: 614 llvm_unreachable("These are handled by PseudoObjectExpr"); 615 616 case Stmt::GNUNullExprClass: { 617 // GNU __null is a pointer-width integer, not an actual pointer. 618 ProgramStateRef state = Pred->getState(); 619 state = state->BindExpr(S, Pred->getLocationContext(), 620 svalBuilder.makeIntValWithPtrWidth(0, false)); 621 Bldr.generateNode(S, Pred, state); 622 break; 623 } 624 625 case Stmt::ObjCAtSynchronizedStmtClass: 626 Bldr.takeNodes(Pred); 627 VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S), Pred, Dst); 628 Bldr.addNodes(Dst); 629 break; 630 631 case Stmt::ExprWithCleanupsClass: 632 // Handled due to fully linearised CFG. 633 break; 634 635 // Cases not handled yet; but will handle some day. 636 case Stmt::DesignatedInitExprClass: 637 case Stmt::ExtVectorElementExprClass: 638 case Stmt::ImaginaryLiteralClass: 639 case Stmt::ObjCAtCatchStmtClass: 640 case Stmt::ObjCAtFinallyStmtClass: 641 case Stmt::ObjCAtTryStmtClass: 642 case Stmt::ObjCAutoreleasePoolStmtClass: 643 case Stmt::ObjCEncodeExprClass: 644 case Stmt::ObjCIsaExprClass: 645 case Stmt::ObjCProtocolExprClass: 646 case Stmt::ObjCSelectorExprClass: 647 case Stmt::ParenListExprClass: 648 case Stmt::PredefinedExprClass: 649 case Stmt::ShuffleVectorExprClass: 650 case Stmt::VAArgExprClass: 651 case Stmt::CUDAKernelCallExprClass: 652 case Stmt::OpaqueValueExprClass: 653 case Stmt::AsTypeExprClass: 654 case Stmt::AtomicExprClass: 655 // Fall through. 656 657 // Cases we intentionally don't evaluate, since they don't need 658 // to be explicitly evaluated. 659 case Stmt::AddrLabelExprClass: 660 case Stmt::IntegerLiteralClass: 661 case Stmt::CharacterLiteralClass: 662 case Stmt::ImplicitValueInitExprClass: 663 case Stmt::CXXScalarValueInitExprClass: 664 case Stmt::CXXBoolLiteralExprClass: 665 case Stmt::ObjCBoolLiteralExprClass: 666 case Stmt::FloatingLiteralClass: 667 case Stmt::SizeOfPackExprClass: 668 case Stmt::StringLiteralClass: 669 case Stmt::ObjCStringLiteralClass: 670 case Stmt::CXXBindTemporaryExprClass: 671 case Stmt::SubstNonTypeTemplateParmExprClass: 672 case Stmt::CXXNullPtrLiteralExprClass: { 673 Bldr.takeNodes(Pred); 674 ExplodedNodeSet preVisit; 675 getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this); 676 getCheckerManager().runCheckersForPostStmt(Dst, preVisit, S, *this); 677 Bldr.addNodes(Dst); 678 break; 679 } 680 681 case Stmt::CXXDefaultArgExprClass: { 682 Bldr.takeNodes(Pred); 683 ExplodedNodeSet PreVisit; 684 getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this); 685 686 ExplodedNodeSet Tmp; 687 StmtNodeBuilder Bldr2(PreVisit, Tmp, *currBldrCtx); 688 689 const LocationContext *LCtx = Pred->getLocationContext(); 690 const CXXDefaultArgExpr *DefaultE = cast<CXXDefaultArgExpr>(S); 691 const Expr *ArgE = DefaultE->getExpr(); 692 693 // Avoid creating and destroying a lot of APSInts. 694 SVal V; 695 llvm::APSInt Result; 696 697 for (ExplodedNodeSet::iterator I = PreVisit.begin(), E = PreVisit.end(); 698 I != E; ++I) { 699 ProgramStateRef State = (*I)->getState(); 700 701 if (ArgE->EvaluateAsInt(Result, getContext())) 702 V = svalBuilder.makeIntVal(Result); 703 else 704 V = State->getSVal(ArgE, LCtx); 705 706 State = State->BindExpr(DefaultE, LCtx, V); 707 if (DefaultE->isGLValue()) 708 State = createTemporaryRegionIfNeeded(State, LCtx, DefaultE, 709 DefaultE); 710 Bldr2.generateNode(S, *I, State); 711 } 712 713 getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this); 714 Bldr.addNodes(Dst); 715 break; 716 } 717 718 case Expr::ObjCArrayLiteralClass: 719 case Expr::ObjCDictionaryLiteralClass: 720 // FIXME: explicitly model with a region and the actual contents 721 // of the container. For now, conjure a symbol. 722 case Expr::ObjCBoxedExprClass: { 723 Bldr.takeNodes(Pred); 724 725 ExplodedNodeSet preVisit; 726 getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this); 727 728 ExplodedNodeSet Tmp; 729 StmtNodeBuilder Bldr2(preVisit, Tmp, *currBldrCtx); 730 731 const Expr *Ex = cast<Expr>(S); 732 QualType resultType = Ex->getType(); 733 734 for (ExplodedNodeSet::iterator it = preVisit.begin(), et = preVisit.end(); 735 it != et; ++it) { 736 ExplodedNode *N = *it; 737 const LocationContext *LCtx = N->getLocationContext(); 738 SVal result = svalBuilder.conjureSymbolVal(0, Ex, LCtx, resultType, 739 currBldrCtx->blockCount()); 740 ProgramStateRef state = N->getState()->BindExpr(Ex, LCtx, result); 741 Bldr2.generateNode(S, N, state); 742 } 743 744 getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this); 745 Bldr.addNodes(Dst); 746 break; 747 } 748 749 case Stmt::ArraySubscriptExprClass: 750 Bldr.takeNodes(Pred); 751 VisitLvalArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Pred, Dst); 752 Bldr.addNodes(Dst); 753 break; 754 755 case Stmt::GCCAsmStmtClass: 756 Bldr.takeNodes(Pred); 757 VisitGCCAsmStmt(cast<GCCAsmStmt>(S), Pred, Dst); 758 Bldr.addNodes(Dst); 759 break; 760 761 case Stmt::MSAsmStmtClass: 762 Bldr.takeNodes(Pred); 763 VisitMSAsmStmt(cast<MSAsmStmt>(S), Pred, Dst); 764 Bldr.addNodes(Dst); 765 break; 766 767 case Stmt::BlockExprClass: 768 Bldr.takeNodes(Pred); 769 VisitBlockExpr(cast<BlockExpr>(S), Pred, Dst); 770 Bldr.addNodes(Dst); 771 break; 772 773 case Stmt::BinaryOperatorClass: { 774 const BinaryOperator* B = cast<BinaryOperator>(S); 775 if (B->isLogicalOp()) { 776 Bldr.takeNodes(Pred); 777 VisitLogicalExpr(B, Pred, Dst); 778 Bldr.addNodes(Dst); 779 break; 780 } 781 else if (B->getOpcode() == BO_Comma) { 782 ProgramStateRef state = Pred->getState(); 783 Bldr.generateNode(B, Pred, 784 state->BindExpr(B, Pred->getLocationContext(), 785 state->getSVal(B->getRHS(), 786 Pred->getLocationContext()))); 787 break; 788 } 789 790 Bldr.takeNodes(Pred); 791 792 if (AMgr.options.eagerlyAssumeBinOpBifurcation && 793 (B->isRelationalOp() || B->isEqualityOp())) { 794 ExplodedNodeSet Tmp; 795 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Tmp); 796 evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, cast<Expr>(S)); 797 } 798 else 799 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst); 800 801 Bldr.addNodes(Dst); 802 break; 803 } 804 805 case Stmt::CXXOperatorCallExprClass: { 806 const CXXOperatorCallExpr *OCE = cast<CXXOperatorCallExpr>(S); 807 808 // For instance method operators, make sure the 'this' argument has a 809 // valid region. 810 const Decl *Callee = OCE->getCalleeDecl(); 811 if (const CXXMethodDecl *MD = dyn_cast_or_null<CXXMethodDecl>(Callee)) { 812 if (MD->isInstance()) { 813 ProgramStateRef State = Pred->getState(); 814 const LocationContext *LCtx = Pred->getLocationContext(); 815 ProgramStateRef NewState = 816 createTemporaryRegionIfNeeded(State, LCtx, OCE->getArg(0)); 817 if (NewState != State) 818 Pred = Bldr.generateNode(OCE, Pred, NewState, /*Tag=*/0, 819 ProgramPoint::PreStmtKind); 820 } 821 } 822 // FALLTHROUGH 823 } 824 case Stmt::CallExprClass: 825 case Stmt::CXXMemberCallExprClass: 826 case Stmt::UserDefinedLiteralClass: { 827 Bldr.takeNodes(Pred); 828 VisitCallExpr(cast<CallExpr>(S), Pred, Dst); 829 Bldr.addNodes(Dst); 830 break; 831 } 832 833 case Stmt::CXXCatchStmtClass: { 834 Bldr.takeNodes(Pred); 835 VisitCXXCatchStmt(cast<CXXCatchStmt>(S), Pred, Dst); 836 Bldr.addNodes(Dst); 837 break; 838 } 839 840 case Stmt::CXXTemporaryObjectExprClass: 841 case Stmt::CXXConstructExprClass: { 842 Bldr.takeNodes(Pred); 843 VisitCXXConstructExpr(cast<CXXConstructExpr>(S), Pred, Dst); 844 Bldr.addNodes(Dst); 845 break; 846 } 847 848 case Stmt::CXXNewExprClass: { 849 Bldr.takeNodes(Pred); 850 ExplodedNodeSet PostVisit; 851 VisitCXXNewExpr(cast<CXXNewExpr>(S), Pred, PostVisit); 852 getCheckerManager().runCheckersForPostStmt(Dst, PostVisit, S, *this); 853 Bldr.addNodes(Dst); 854 break; 855 } 856 857 case Stmt::CXXDeleteExprClass: { 858 Bldr.takeNodes(Pred); 859 ExplodedNodeSet PreVisit; 860 const CXXDeleteExpr *CDE = cast<CXXDeleteExpr>(S); 861 getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this); 862 863 for (ExplodedNodeSet::iterator i = PreVisit.begin(), 864 e = PreVisit.end(); i != e ; ++i) 865 VisitCXXDeleteExpr(CDE, *i, Dst); 866 867 Bldr.addNodes(Dst); 868 break; 869 } 870 // FIXME: ChooseExpr is really a constant. We need to fix 871 // the CFG do not model them as explicit control-flow. 872 873 case Stmt::ChooseExprClass: { // __builtin_choose_expr 874 Bldr.takeNodes(Pred); 875 const ChooseExpr *C = cast<ChooseExpr>(S); 876 VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst); 877 Bldr.addNodes(Dst); 878 break; 879 } 880 881 case Stmt::CompoundAssignOperatorClass: 882 Bldr.takeNodes(Pred); 883 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst); 884 Bldr.addNodes(Dst); 885 break; 886 887 case Stmt::CompoundLiteralExprClass: 888 Bldr.takeNodes(Pred); 889 VisitCompoundLiteralExpr(cast<CompoundLiteralExpr>(S), Pred, Dst); 890 Bldr.addNodes(Dst); 891 break; 892 893 case Stmt::BinaryConditionalOperatorClass: 894 case Stmt::ConditionalOperatorClass: { // '?' operator 895 Bldr.takeNodes(Pred); 896 const AbstractConditionalOperator *C 897 = cast<AbstractConditionalOperator>(S); 898 VisitGuardedExpr(C, C->getTrueExpr(), C->getFalseExpr(), Pred, Dst); 899 Bldr.addNodes(Dst); 900 break; 901 } 902 903 case Stmt::CXXThisExprClass: 904 Bldr.takeNodes(Pred); 905 VisitCXXThisExpr(cast<CXXThisExpr>(S), Pred, Dst); 906 Bldr.addNodes(Dst); 907 break; 908 909 case Stmt::DeclRefExprClass: { 910 Bldr.takeNodes(Pred); 911 const DeclRefExpr *DE = cast<DeclRefExpr>(S); 912 VisitCommonDeclRefExpr(DE, DE->getDecl(), Pred, Dst); 913 Bldr.addNodes(Dst); 914 break; 915 } 916 917 case Stmt::DeclStmtClass: 918 Bldr.takeNodes(Pred); 919 VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst); 920 Bldr.addNodes(Dst); 921 break; 922 923 case Stmt::ImplicitCastExprClass: 924 case Stmt::CStyleCastExprClass: 925 case Stmt::CXXStaticCastExprClass: 926 case Stmt::CXXDynamicCastExprClass: 927 case Stmt::CXXReinterpretCastExprClass: 928 case Stmt::CXXConstCastExprClass: 929 case Stmt::CXXFunctionalCastExprClass: 930 case Stmt::ObjCBridgedCastExprClass: { 931 Bldr.takeNodes(Pred); 932 const CastExpr *C = cast<CastExpr>(S); 933 // Handle the previsit checks. 934 ExplodedNodeSet dstPrevisit; 935 getCheckerManager().runCheckersForPreStmt(dstPrevisit, Pred, C, *this); 936 937 // Handle the expression itself. 938 ExplodedNodeSet dstExpr; 939 for (ExplodedNodeSet::iterator i = dstPrevisit.begin(), 940 e = dstPrevisit.end(); i != e ; ++i) { 941 VisitCast(C, C->getSubExpr(), *i, dstExpr); 942 } 943 944 // Handle the postvisit checks. 945 getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, C, *this); 946 Bldr.addNodes(Dst); 947 break; 948 } 949 950 case Expr::MaterializeTemporaryExprClass: { 951 Bldr.takeNodes(Pred); 952 const MaterializeTemporaryExpr *MTE = cast<MaterializeTemporaryExpr>(S); 953 CreateCXXTemporaryObject(MTE, Pred, Dst); 954 Bldr.addNodes(Dst); 955 break; 956 } 957 958 case Stmt::InitListExprClass: 959 Bldr.takeNodes(Pred); 960 VisitInitListExpr(cast<InitListExpr>(S), Pred, Dst); 961 Bldr.addNodes(Dst); 962 break; 963 964 case Stmt::MemberExprClass: 965 Bldr.takeNodes(Pred); 966 VisitMemberExpr(cast<MemberExpr>(S), Pred, Dst); 967 Bldr.addNodes(Dst); 968 break; 969 970 case Stmt::ObjCIvarRefExprClass: 971 Bldr.takeNodes(Pred); 972 VisitLvalObjCIvarRefExpr(cast<ObjCIvarRefExpr>(S), Pred, Dst); 973 Bldr.addNodes(Dst); 974 break; 975 976 case Stmt::ObjCForCollectionStmtClass: 977 Bldr.takeNodes(Pred); 978 VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S), Pred, Dst); 979 Bldr.addNodes(Dst); 980 break; 981 982 case Stmt::ObjCMessageExprClass: 983 Bldr.takeNodes(Pred); 984 VisitObjCMessage(cast<ObjCMessageExpr>(S), Pred, Dst); 985 Bldr.addNodes(Dst); 986 break; 987 988 case Stmt::ObjCAtThrowStmtClass: 989 case Stmt::CXXThrowExprClass: 990 // FIXME: This is not complete. We basically treat @throw as 991 // an abort. 992 Bldr.generateSink(S, Pred, Pred->getState()); 993 break; 994 995 case Stmt::ReturnStmtClass: 996 Bldr.takeNodes(Pred); 997 VisitReturnStmt(cast<ReturnStmt>(S), Pred, Dst); 998 Bldr.addNodes(Dst); 999 break; 1000 1001 case Stmt::OffsetOfExprClass: 1002 Bldr.takeNodes(Pred); 1003 VisitOffsetOfExpr(cast<OffsetOfExpr>(S), Pred, Dst); 1004 Bldr.addNodes(Dst); 1005 break; 1006 1007 case Stmt::UnaryExprOrTypeTraitExprClass: 1008 Bldr.takeNodes(Pred); 1009 VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S), 1010 Pred, Dst); 1011 Bldr.addNodes(Dst); 1012 break; 1013 1014 case Stmt::StmtExprClass: { 1015 const StmtExpr *SE = cast<StmtExpr>(S); 1016 1017 if (SE->getSubStmt()->body_empty()) { 1018 // Empty statement expression. 1019 assert(SE->getType() == getContext().VoidTy 1020 && "Empty statement expression must have void type."); 1021 break; 1022 } 1023 1024 if (Expr *LastExpr = dyn_cast<Expr>(*SE->getSubStmt()->body_rbegin())) { 1025 ProgramStateRef state = Pred->getState(); 1026 Bldr.generateNode(SE, Pred, 1027 state->BindExpr(SE, Pred->getLocationContext(), 1028 state->getSVal(LastExpr, 1029 Pred->getLocationContext()))); 1030 } 1031 break; 1032 } 1033 1034 case Stmt::UnaryOperatorClass: { 1035 Bldr.takeNodes(Pred); 1036 const UnaryOperator *U = cast<UnaryOperator>(S); 1037 if (AMgr.options.eagerlyAssumeBinOpBifurcation && (U->getOpcode() == UO_LNot)) { 1038 ExplodedNodeSet Tmp; 1039 VisitUnaryOperator(U, Pred, Tmp); 1040 evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, U); 1041 } 1042 else 1043 VisitUnaryOperator(U, Pred, Dst); 1044 Bldr.addNodes(Dst); 1045 break; 1046 } 1047 1048 case Stmt::PseudoObjectExprClass: { 1049 Bldr.takeNodes(Pred); 1050 ProgramStateRef state = Pred->getState(); 1051 const PseudoObjectExpr *PE = cast<PseudoObjectExpr>(S); 1052 if (const Expr *Result = PE->getResultExpr()) { 1053 SVal V = state->getSVal(Result, Pred->getLocationContext()); 1054 Bldr.generateNode(S, Pred, 1055 state->BindExpr(S, Pred->getLocationContext(), V)); 1056 } 1057 else 1058 Bldr.generateNode(S, Pred, 1059 state->BindExpr(S, Pred->getLocationContext(), 1060 UnknownVal())); 1061 1062 Bldr.addNodes(Dst); 1063 break; 1064 } 1065 } 1066} 1067 1068bool ExprEngine::replayWithoutInlining(ExplodedNode *N, 1069 const LocationContext *CalleeLC) { 1070 const StackFrameContext *CalleeSF = CalleeLC->getCurrentStackFrame(); 1071 const StackFrameContext *CallerSF = CalleeSF->getParent()->getCurrentStackFrame(); 1072 assert(CalleeSF && CallerSF); 1073 ExplodedNode *BeforeProcessingCall = 0; 1074 const Stmt *CE = CalleeSF->getCallSite(); 1075 1076 // Find the first node before we started processing the call expression. 1077 while (N) { 1078 ProgramPoint L = N->getLocation(); 1079 BeforeProcessingCall = N; 1080 N = N->pred_empty() ? NULL : *(N->pred_begin()); 1081 1082 // Skip the nodes corresponding to the inlined code. 1083 if (L.getLocationContext()->getCurrentStackFrame() != CallerSF) 1084 continue; 1085 // We reached the caller. Find the node right before we started 1086 // processing the call. 1087 if (L.isPurgeKind()) 1088 continue; 1089 if (L.getAs<PreImplicitCall>()) 1090 continue; 1091 if (L.getAs<CallEnter>()) 1092 continue; 1093 if (Optional<StmtPoint> SP = L.getAs<StmtPoint>()) 1094 if (SP->getStmt() == CE) 1095 continue; 1096 break; 1097 } 1098 1099 if (!BeforeProcessingCall) 1100 return false; 1101 1102 // TODO: Clean up the unneeded nodes. 1103 1104 // Build an Epsilon node from which we will restart the analyzes. 1105 // Note that CE is permitted to be NULL! 1106 ProgramPoint NewNodeLoc = 1107 EpsilonPoint(BeforeProcessingCall->getLocationContext(), CE); 1108 // Add the special flag to GDM to signal retrying with no inlining. 1109 // Note, changing the state ensures that we are not going to cache out. 1110 ProgramStateRef NewNodeState = BeforeProcessingCall->getState(); 1111 NewNodeState = 1112 NewNodeState->set<ReplayWithoutInlining>(const_cast<Stmt *>(CE)); 1113 1114 // Make the new node a successor of BeforeProcessingCall. 1115 bool IsNew = false; 1116 ExplodedNode *NewNode = G.getNode(NewNodeLoc, NewNodeState, false, &IsNew); 1117 // We cached out at this point. Caching out is common due to us backtracking 1118 // from the inlined function, which might spawn several paths. 1119 if (!IsNew) 1120 return true; 1121 1122 NewNode->addPredecessor(BeforeProcessingCall, G); 1123 1124 // Add the new node to the work list. 1125 Engine.enqueueStmtNode(NewNode, CalleeSF->getCallSiteBlock(), 1126 CalleeSF->getIndex()); 1127 NumTimesRetriedWithoutInlining++; 1128 return true; 1129} 1130 1131/// Block entrance. (Update counters). 1132void ExprEngine::processCFGBlockEntrance(const BlockEdge &L, 1133 NodeBuilderWithSinks &nodeBuilder, 1134 ExplodedNode *Pred) { 1135 1136 // FIXME: Refactor this into a checker. 1137 if (nodeBuilder.getContext().blockCount() >= AMgr.options.maxBlockVisitOnPath) { 1138 static SimpleProgramPointTag tag("ExprEngine : Block count exceeded"); 1139 const ExplodedNode *Sink = 1140 nodeBuilder.generateSink(Pred->getState(), Pred, &tag); 1141 1142 // Check if we stopped at the top level function or not. 1143 // Root node should have the location context of the top most function. 1144 const LocationContext *CalleeLC = Pred->getLocation().getLocationContext(); 1145 const LocationContext *CalleeSF = CalleeLC->getCurrentStackFrame(); 1146 const LocationContext *RootLC = 1147 (*G.roots_begin())->getLocation().getLocationContext(); 1148 if (RootLC->getCurrentStackFrame() != CalleeSF) { 1149 Engine.FunctionSummaries->markReachedMaxBlockCount(CalleeSF->getDecl()); 1150 1151 // Re-run the call evaluation without inlining it, by storing the 1152 // no-inlining policy in the state and enqueuing the new work item on 1153 // the list. Replay should almost never fail. Use the stats to catch it 1154 // if it does. 1155 if ((!AMgr.options.NoRetryExhausted && 1156 replayWithoutInlining(Pred, CalleeLC))) 1157 return; 1158 NumMaxBlockCountReachedInInlined++; 1159 } else 1160 NumMaxBlockCountReached++; 1161 1162 // Make sink nodes as exhausted(for stats) only if retry failed. 1163 Engine.blocksExhausted.push_back(std::make_pair(L, Sink)); 1164 } 1165} 1166 1167//===----------------------------------------------------------------------===// 1168// Branch processing. 1169//===----------------------------------------------------------------------===// 1170 1171/// RecoverCastedSymbol - A helper function for ProcessBranch that is used 1172/// to try to recover some path-sensitivity for casts of symbolic 1173/// integers that promote their values (which are currently not tracked well). 1174/// This function returns the SVal bound to Condition->IgnoreCasts if all the 1175// cast(s) did was sign-extend the original value. 1176static SVal RecoverCastedSymbol(ProgramStateManager& StateMgr, 1177 ProgramStateRef state, 1178 const Stmt *Condition, 1179 const LocationContext *LCtx, 1180 ASTContext &Ctx) { 1181 1182 const Expr *Ex = dyn_cast<Expr>(Condition); 1183 if (!Ex) 1184 return UnknownVal(); 1185 1186 uint64_t bits = 0; 1187 bool bitsInit = false; 1188 1189 while (const CastExpr *CE = dyn_cast<CastExpr>(Ex)) { 1190 QualType T = CE->getType(); 1191 1192 if (!T->isIntegerType()) 1193 return UnknownVal(); 1194 1195 uint64_t newBits = Ctx.getTypeSize(T); 1196 if (!bitsInit || newBits < bits) { 1197 bitsInit = true; 1198 bits = newBits; 1199 } 1200 1201 Ex = CE->getSubExpr(); 1202 } 1203 1204 // We reached a non-cast. Is it a symbolic value? 1205 QualType T = Ex->getType(); 1206 1207 if (!bitsInit || !T->isIntegerType() || Ctx.getTypeSize(T) > bits) 1208 return UnknownVal(); 1209 1210 return state->getSVal(Ex, LCtx); 1211} 1212 1213static const Stmt *ResolveCondition(const Stmt *Condition, 1214 const CFGBlock *B) { 1215 if (const Expr *Ex = dyn_cast<Expr>(Condition)) 1216 Condition = Ex->IgnoreParens(); 1217 1218 const BinaryOperator *BO = dyn_cast<BinaryOperator>(Condition); 1219 if (!BO || !BO->isLogicalOp()) 1220 return Condition; 1221 1222 // For logical operations, we still have the case where some branches 1223 // use the traditional "merge" approach and others sink the branch 1224 // directly into the basic blocks representing the logical operation. 1225 // We need to distinguish between those two cases here. 1226 1227 // The invariants are still shifting, but it is possible that the 1228 // last element in a CFGBlock is not a CFGStmt. Look for the last 1229 // CFGStmt as the value of the condition. 1230 CFGBlock::const_reverse_iterator I = B->rbegin(), E = B->rend(); 1231 for (; I != E; ++I) { 1232 CFGElement Elem = *I; 1233 Optional<CFGStmt> CS = Elem.getAs<CFGStmt>(); 1234 if (!CS) 1235 continue; 1236 if (CS->getStmt() != Condition) 1237 break; 1238 return Condition; 1239 } 1240 1241 assert(I != E); 1242 1243 while (Condition) { 1244 BO = dyn_cast<BinaryOperator>(Condition); 1245 if (!BO || !BO->isLogicalOp()) 1246 return Condition; 1247 Condition = BO->getRHS()->IgnoreParens(); 1248 } 1249 llvm_unreachable("could not resolve condition"); 1250} 1251 1252void ExprEngine::processBranch(const Stmt *Condition, const Stmt *Term, 1253 NodeBuilderContext& BldCtx, 1254 ExplodedNode *Pred, 1255 ExplodedNodeSet &Dst, 1256 const CFGBlock *DstT, 1257 const CFGBlock *DstF) { 1258 currBldrCtx = &BldCtx; 1259 1260 // Check for NULL conditions; e.g. "for(;;)" 1261 if (!Condition) { 1262 BranchNodeBuilder NullCondBldr(Pred, Dst, BldCtx, DstT, DstF); 1263 NullCondBldr.markInfeasible(false); 1264 NullCondBldr.generateNode(Pred->getState(), true, Pred); 1265 return; 1266 } 1267 1268 1269 // Resolve the condition in the precense of nested '||' and '&&'. 1270 if (const Expr *Ex = dyn_cast<Expr>(Condition)) 1271 Condition = Ex->IgnoreParens(); 1272 1273 Condition = ResolveCondition(Condition, BldCtx.getBlock()); 1274 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 1275 Condition->getLocStart(), 1276 "Error evaluating branch"); 1277 1278 ExplodedNodeSet CheckersOutSet; 1279 getCheckerManager().runCheckersForBranchCondition(Condition, CheckersOutSet, 1280 Pred, *this); 1281 // We generated only sinks. 1282 if (CheckersOutSet.empty()) 1283 return; 1284 1285 BranchNodeBuilder builder(CheckersOutSet, Dst, BldCtx, DstT, DstF); 1286 for (NodeBuilder::iterator I = CheckersOutSet.begin(), 1287 E = CheckersOutSet.end(); E != I; ++I) { 1288 ExplodedNode *PredI = *I; 1289 1290 if (PredI->isSink()) 1291 continue; 1292 1293 ProgramStateRef PrevState = PredI->getState(); 1294 SVal X = PrevState->getSVal(Condition, PredI->getLocationContext()); 1295 1296 if (X.isUnknownOrUndef()) { 1297 // Give it a chance to recover from unknown. 1298 if (const Expr *Ex = dyn_cast<Expr>(Condition)) { 1299 if (Ex->getType()->isIntegerType()) { 1300 // Try to recover some path-sensitivity. Right now casts of symbolic 1301 // integers that promote their values are currently not tracked well. 1302 // If 'Condition' is such an expression, try and recover the 1303 // underlying value and use that instead. 1304 SVal recovered = RecoverCastedSymbol(getStateManager(), 1305 PrevState, Condition, 1306 PredI->getLocationContext(), 1307 getContext()); 1308 1309 if (!recovered.isUnknown()) { 1310 X = recovered; 1311 } 1312 } 1313 } 1314 } 1315 1316 // If the condition is still unknown, give up. 1317 if (X.isUnknownOrUndef()) { 1318 builder.generateNode(PrevState, true, PredI); 1319 builder.generateNode(PrevState, false, PredI); 1320 continue; 1321 } 1322 1323 DefinedSVal V = X.castAs<DefinedSVal>(); 1324 1325 ProgramStateRef StTrue, StFalse; 1326 tie(StTrue, StFalse) = PrevState->assume(V); 1327 1328 // Process the true branch. 1329 if (builder.isFeasible(true)) { 1330 if (StTrue) 1331 builder.generateNode(StTrue, true, PredI); 1332 else 1333 builder.markInfeasible(true); 1334 } 1335 1336 // Process the false branch. 1337 if (builder.isFeasible(false)) { 1338 if (StFalse) 1339 builder.generateNode(StFalse, false, PredI); 1340 else 1341 builder.markInfeasible(false); 1342 } 1343 } 1344 currBldrCtx = 0; 1345} 1346 1347/// The GDM component containing the set of global variables which have been 1348/// previously initialized with explicit initializers. 1349REGISTER_TRAIT_WITH_PROGRAMSTATE(InitializedGlobalsSet, 1350 llvm::ImmutableSet<const VarDecl *>) 1351 1352void ExprEngine::processStaticInitializer(const DeclStmt *DS, 1353 NodeBuilderContext &BuilderCtx, 1354 ExplodedNode *Pred, 1355 clang::ento::ExplodedNodeSet &Dst, 1356 const CFGBlock *DstT, 1357 const CFGBlock *DstF) { 1358 currBldrCtx = &BuilderCtx; 1359 1360 const VarDecl *VD = cast<VarDecl>(DS->getSingleDecl()); 1361 ProgramStateRef state = Pred->getState(); 1362 bool initHasRun = state->contains<InitializedGlobalsSet>(VD); 1363 BranchNodeBuilder builder(Pred, Dst, BuilderCtx, DstT, DstF); 1364 1365 if (!initHasRun) { 1366 state = state->add<InitializedGlobalsSet>(VD); 1367 } 1368 1369 builder.generateNode(state, initHasRun, Pred); 1370 builder.markInfeasible(!initHasRun); 1371 1372 currBldrCtx = 0; 1373} 1374 1375/// processIndirectGoto - Called by CoreEngine. Used to generate successor 1376/// nodes by processing the 'effects' of a computed goto jump. 1377void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) { 1378 1379 ProgramStateRef state = builder.getState(); 1380 SVal V = state->getSVal(builder.getTarget(), builder.getLocationContext()); 1381 1382 // Three possibilities: 1383 // 1384 // (1) We know the computed label. 1385 // (2) The label is NULL (or some other constant), or Undefined. 1386 // (3) We have no clue about the label. Dispatch to all targets. 1387 // 1388 1389 typedef IndirectGotoNodeBuilder::iterator iterator; 1390 1391 if (Optional<loc::GotoLabel> LV = V.getAs<loc::GotoLabel>()) { 1392 const LabelDecl *L = LV->getLabel(); 1393 1394 for (iterator I = builder.begin(), E = builder.end(); I != E; ++I) { 1395 if (I.getLabel() == L) { 1396 builder.generateNode(I, state); 1397 return; 1398 } 1399 } 1400 1401 llvm_unreachable("No block with label."); 1402 } 1403 1404 if (V.getAs<loc::ConcreteInt>() || V.getAs<UndefinedVal>()) { 1405 // Dispatch to the first target and mark it as a sink. 1406 //ExplodedNode* N = builder.generateNode(builder.begin(), state, true); 1407 // FIXME: add checker visit. 1408 // UndefBranches.insert(N); 1409 return; 1410 } 1411 1412 // This is really a catch-all. We don't support symbolics yet. 1413 // FIXME: Implement dispatch for symbolic pointers. 1414 1415 for (iterator I=builder.begin(), E=builder.end(); I != E; ++I) 1416 builder.generateNode(I, state); 1417} 1418 1419/// ProcessEndPath - Called by CoreEngine. Used to generate end-of-path 1420/// nodes when the control reaches the end of a function. 1421void ExprEngine::processEndOfFunction(NodeBuilderContext& BC, 1422 ExplodedNode *Pred) { 1423 StateMgr.EndPath(Pred->getState()); 1424 1425 ExplodedNodeSet Dst; 1426 if (Pred->getLocationContext()->inTopFrame()) { 1427 // Remove dead symbols. 1428 ExplodedNodeSet AfterRemovedDead; 1429 removeDeadOnEndOfFunction(BC, Pred, AfterRemovedDead); 1430 1431 // Notify checkers. 1432 for (ExplodedNodeSet::iterator I = AfterRemovedDead.begin(), 1433 E = AfterRemovedDead.end(); I != E; ++I) { 1434 getCheckerManager().runCheckersForEndFunction(BC, Dst, *I, *this); 1435 } 1436 } else { 1437 getCheckerManager().runCheckersForEndFunction(BC, Dst, Pred, *this); 1438 } 1439 1440 Engine.enqueueEndOfFunction(Dst); 1441} 1442 1443/// ProcessSwitch - Called by CoreEngine. Used to generate successor 1444/// nodes by processing the 'effects' of a switch statement. 1445void ExprEngine::processSwitch(SwitchNodeBuilder& builder) { 1446 typedef SwitchNodeBuilder::iterator iterator; 1447 ProgramStateRef state = builder.getState(); 1448 const Expr *CondE = builder.getCondition(); 1449 SVal CondV_untested = state->getSVal(CondE, builder.getLocationContext()); 1450 1451 if (CondV_untested.isUndef()) { 1452 //ExplodedNode* N = builder.generateDefaultCaseNode(state, true); 1453 // FIXME: add checker 1454 //UndefBranches.insert(N); 1455 1456 return; 1457 } 1458 DefinedOrUnknownSVal CondV = CondV_untested.castAs<DefinedOrUnknownSVal>(); 1459 1460 ProgramStateRef DefaultSt = state; 1461 1462 iterator I = builder.begin(), EI = builder.end(); 1463 bool defaultIsFeasible = I == EI; 1464 1465 for ( ; I != EI; ++I) { 1466 // Successor may be pruned out during CFG construction. 1467 if (!I.getBlock()) 1468 continue; 1469 1470 const CaseStmt *Case = I.getCase(); 1471 1472 // Evaluate the LHS of the case value. 1473 llvm::APSInt V1 = Case->getLHS()->EvaluateKnownConstInt(getContext()); 1474 assert(V1.getBitWidth() == getContext().getTypeSize(CondE->getType())); 1475 1476 // Get the RHS of the case, if it exists. 1477 llvm::APSInt V2; 1478 if (const Expr *E = Case->getRHS()) 1479 V2 = E->EvaluateKnownConstInt(getContext()); 1480 else 1481 V2 = V1; 1482 1483 // FIXME: Eventually we should replace the logic below with a range 1484 // comparison, rather than concretize the values within the range. 1485 // This should be easy once we have "ranges" for NonLVals. 1486 1487 do { 1488 nonloc::ConcreteInt CaseVal(getBasicVals().getValue(V1)); 1489 DefinedOrUnknownSVal Res = svalBuilder.evalEQ(DefaultSt ? DefaultSt : state, 1490 CondV, CaseVal); 1491 1492 // Now "assume" that the case matches. 1493 if (ProgramStateRef stateNew = state->assume(Res, true)) { 1494 builder.generateCaseStmtNode(I, stateNew); 1495 1496 // If CondV evaluates to a constant, then we know that this 1497 // is the *only* case that we can take, so stop evaluating the 1498 // others. 1499 if (CondV.getAs<nonloc::ConcreteInt>()) 1500 return; 1501 } 1502 1503 // Now "assume" that the case doesn't match. Add this state 1504 // to the default state (if it is feasible). 1505 if (DefaultSt) { 1506 if (ProgramStateRef stateNew = DefaultSt->assume(Res, false)) { 1507 defaultIsFeasible = true; 1508 DefaultSt = stateNew; 1509 } 1510 else { 1511 defaultIsFeasible = false; 1512 DefaultSt = NULL; 1513 } 1514 } 1515 1516 // Concretize the next value in the range. 1517 if (V1 == V2) 1518 break; 1519 1520 ++V1; 1521 assert (V1 <= V2); 1522 1523 } while (true); 1524 } 1525 1526 if (!defaultIsFeasible) 1527 return; 1528 1529 // If we have switch(enum value), the default branch is not 1530 // feasible if all of the enum constants not covered by 'case:' statements 1531 // are not feasible values for the switch condition. 1532 // 1533 // Note that this isn't as accurate as it could be. Even if there isn't 1534 // a case for a particular enum value as long as that enum value isn't 1535 // feasible then it shouldn't be considered for making 'default:' reachable. 1536 const SwitchStmt *SS = builder.getSwitch(); 1537 const Expr *CondExpr = SS->getCond()->IgnoreParenImpCasts(); 1538 if (CondExpr->getType()->getAs<EnumType>()) { 1539 if (SS->isAllEnumCasesCovered()) 1540 return; 1541 } 1542 1543 builder.generateDefaultCaseNode(DefaultSt); 1544} 1545 1546//===----------------------------------------------------------------------===// 1547// Transfer functions: Loads and stores. 1548//===----------------------------------------------------------------------===// 1549 1550void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D, 1551 ExplodedNode *Pred, 1552 ExplodedNodeSet &Dst) { 1553 StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); 1554 1555 ProgramStateRef state = Pred->getState(); 1556 const LocationContext *LCtx = Pred->getLocationContext(); 1557 1558 if (const VarDecl *VD = dyn_cast<VarDecl>(D)) { 1559 assert(Ex->isGLValue()); 1560 SVal V = state->getLValue(VD, Pred->getLocationContext()); 1561 1562 // For references, the 'lvalue' is the pointer address stored in the 1563 // reference region. 1564 if (VD->getType()->isReferenceType()) { 1565 if (const MemRegion *R = V.getAsRegion()) 1566 V = state->getSVal(R); 1567 else 1568 V = UnknownVal(); 1569 } 1570 1571 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), 0, 1572 ProgramPoint::PostLValueKind); 1573 return; 1574 } 1575 if (const EnumConstantDecl *ED = dyn_cast<EnumConstantDecl>(D)) { 1576 assert(!Ex->isGLValue()); 1577 SVal V = svalBuilder.makeIntVal(ED->getInitVal()); 1578 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V)); 1579 return; 1580 } 1581 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 1582 SVal V = svalBuilder.getFunctionPointer(FD); 1583 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), 0, 1584 ProgramPoint::PostLValueKind); 1585 return; 1586 } 1587 if (isa<FieldDecl>(D)) { 1588 // FIXME: Compute lvalue of field pointers-to-member. 1589 // Right now we just use a non-null void pointer, so that it gives proper 1590 // results in boolean contexts. 1591 SVal V = svalBuilder.conjureSymbolVal(Ex, LCtx, getContext().VoidPtrTy, 1592 currBldrCtx->blockCount()); 1593 state = state->assume(V.castAs<DefinedOrUnknownSVal>(), true); 1594 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), 0, 1595 ProgramPoint::PostLValueKind); 1596 return; 1597 } 1598 1599 llvm_unreachable("Support for this Decl not implemented."); 1600} 1601 1602/// VisitArraySubscriptExpr - Transfer function for array accesses 1603void ExprEngine::VisitLvalArraySubscriptExpr(const ArraySubscriptExpr *A, 1604 ExplodedNode *Pred, 1605 ExplodedNodeSet &Dst){ 1606 1607 const Expr *Base = A->getBase()->IgnoreParens(); 1608 const Expr *Idx = A->getIdx()->IgnoreParens(); 1609 1610 1611 ExplodedNodeSet checkerPreStmt; 1612 getCheckerManager().runCheckersForPreStmt(checkerPreStmt, Pred, A, *this); 1613 1614 StmtNodeBuilder Bldr(checkerPreStmt, Dst, *currBldrCtx); 1615 1616 for (ExplodedNodeSet::iterator it = checkerPreStmt.begin(), 1617 ei = checkerPreStmt.end(); it != ei; ++it) { 1618 const LocationContext *LCtx = (*it)->getLocationContext(); 1619 ProgramStateRef state = (*it)->getState(); 1620 SVal V = state->getLValue(A->getType(), 1621 state->getSVal(Idx, LCtx), 1622 state->getSVal(Base, LCtx)); 1623 assert(A->isGLValue()); 1624 Bldr.generateNode(A, *it, state->BindExpr(A, LCtx, V), 0, 1625 ProgramPoint::PostLValueKind); 1626 } 1627} 1628 1629/// VisitMemberExpr - Transfer function for member expressions. 1630void ExprEngine::VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred, 1631 ExplodedNodeSet &TopDst) { 1632 1633 StmtNodeBuilder Bldr(Pred, TopDst, *currBldrCtx); 1634 ExplodedNodeSet Dst; 1635 ValueDecl *Member = M->getMemberDecl(); 1636 1637 // Handle static member variables and enum constants accessed via 1638 // member syntax. 1639 if (isa<VarDecl>(Member) || isa<EnumConstantDecl>(Member)) { 1640 Bldr.takeNodes(Pred); 1641 VisitCommonDeclRefExpr(M, Member, Pred, Dst); 1642 Bldr.addNodes(Dst); 1643 return; 1644 } 1645 1646 ProgramStateRef state = Pred->getState(); 1647 const LocationContext *LCtx = Pred->getLocationContext(); 1648 Expr *BaseExpr = M->getBase(); 1649 1650 // Handle C++ method calls. 1651 if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(Member)) { 1652 if (MD->isInstance()) 1653 state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr); 1654 1655 SVal MDVal = svalBuilder.getFunctionPointer(MD); 1656 state = state->BindExpr(M, LCtx, MDVal); 1657 1658 Bldr.generateNode(M, Pred, state); 1659 return; 1660 } 1661 1662 // Handle regular struct fields / member variables. 1663 state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr); 1664 SVal baseExprVal = state->getSVal(BaseExpr, LCtx); 1665 1666 FieldDecl *field = cast<FieldDecl>(Member); 1667 SVal L = state->getLValue(field, baseExprVal); 1668 if (M->isGLValue()) { 1669 if (field->getType()->isReferenceType()) { 1670 if (const MemRegion *R = L.getAsRegion()) 1671 L = state->getSVal(R); 1672 else 1673 L = UnknownVal(); 1674 } 1675 1676 Bldr.generateNode(M, Pred, state->BindExpr(M, LCtx, L), 0, 1677 ProgramPoint::PostLValueKind); 1678 } else { 1679 Bldr.takeNodes(Pred); 1680 evalLoad(Dst, M, M, Pred, state, L); 1681 Bldr.addNodes(Dst); 1682 } 1683} 1684 1685namespace { 1686class CollectReachableSymbolsCallback : public SymbolVisitor { 1687 InvalidatedSymbols Symbols; 1688public: 1689 CollectReachableSymbolsCallback(ProgramStateRef State) {} 1690 const InvalidatedSymbols &getSymbols() const { return Symbols; } 1691 1692 bool VisitSymbol(SymbolRef Sym) { 1693 Symbols.insert(Sym); 1694 return true; 1695 } 1696}; 1697} // end anonymous namespace 1698 1699// A value escapes in three possible cases: 1700// (1) We are binding to something that is not a memory region. 1701// (2) We are binding to a MemrRegion that does not have stack storage. 1702// (3) We are binding to a MemRegion with stack storage that the store 1703// does not understand. 1704ProgramStateRef ExprEngine::processPointerEscapedOnBind(ProgramStateRef State, 1705 SVal Loc, SVal Val) { 1706 // Are we storing to something that causes the value to "escape"? 1707 bool escapes = true; 1708 1709 // TODO: Move to StoreManager. 1710 if (Optional<loc::MemRegionVal> regionLoc = Loc.getAs<loc::MemRegionVal>()) { 1711 escapes = !regionLoc->getRegion()->hasStackStorage(); 1712 1713 if (!escapes) { 1714 // To test (3), generate a new state with the binding added. If it is 1715 // the same state, then it escapes (since the store cannot represent 1716 // the binding). 1717 // Do this only if we know that the store is not supposed to generate the 1718 // same state. 1719 SVal StoredVal = State->getSVal(regionLoc->getRegion()); 1720 if (StoredVal != Val) 1721 escapes = (State == (State->bindLoc(*regionLoc, Val))); 1722 } 1723 } 1724 1725 // If our store can represent the binding and we aren't storing to something 1726 // that doesn't have local storage then just return and have the simulation 1727 // state continue as is. 1728 if (!escapes) 1729 return State; 1730 1731 // Otherwise, find all symbols referenced by 'val' that we are tracking 1732 // and stop tracking them. 1733 CollectReachableSymbolsCallback Scanner = 1734 State->scanReachableSymbols<CollectReachableSymbolsCallback>(Val); 1735 const InvalidatedSymbols &EscapedSymbols = Scanner.getSymbols(); 1736 State = getCheckerManager().runCheckersForPointerEscape(State, 1737 EscapedSymbols, 1738 /*CallEvent*/ 0, 1739 PSK_EscapeOnBind); 1740 1741 return State; 1742} 1743 1744ProgramStateRef 1745ExprEngine::notifyCheckersOfPointerEscape(ProgramStateRef State, 1746 const InvalidatedSymbols *Invalidated, 1747 ArrayRef<const MemRegion *> ExplicitRegions, 1748 ArrayRef<const MemRegion *> Regions, 1749 const CallEvent *Call, 1750 bool IsConst) { 1751 1752 if (!Invalidated || Invalidated->empty()) 1753 return State; 1754 1755 if (!Call) 1756 return getCheckerManager().runCheckersForPointerEscape(State, 1757 *Invalidated, 1758 0, 1759 PSK_EscapeOther); 1760 1761 // Note: Due to current limitations of RegionStore, we only process the top 1762 // level const pointers correctly. The lower level const pointers are 1763 // currently treated as non-const. 1764 if (IsConst) 1765 return getCheckerManager().runCheckersForPointerEscape(State, 1766 *Invalidated, 1767 Call, 1768 PSK_DirectEscapeOnCall, 1769 true); 1770 1771 // If the symbols were invalidated by a call, we want to find out which ones 1772 // were invalidated directly due to being arguments to the call. 1773 InvalidatedSymbols SymbolsDirectlyInvalidated; 1774 for (ArrayRef<const MemRegion *>::iterator I = ExplicitRegions.begin(), 1775 E = ExplicitRegions.end(); I != E; ++I) { 1776 if (const SymbolicRegion *R = (*I)->StripCasts()->getAs<SymbolicRegion>()) 1777 SymbolsDirectlyInvalidated.insert(R->getSymbol()); 1778 } 1779 1780 InvalidatedSymbols SymbolsIndirectlyInvalidated; 1781 for (InvalidatedSymbols::const_iterator I=Invalidated->begin(), 1782 E = Invalidated->end(); I!=E; ++I) { 1783 SymbolRef sym = *I; 1784 if (SymbolsDirectlyInvalidated.count(sym)) 1785 continue; 1786 SymbolsIndirectlyInvalidated.insert(sym); 1787 } 1788 1789 if (!SymbolsDirectlyInvalidated.empty()) 1790 State = getCheckerManager().runCheckersForPointerEscape(State, 1791 SymbolsDirectlyInvalidated, Call, PSK_DirectEscapeOnCall); 1792 1793 // Notify about the symbols that get indirectly invalidated by the call. 1794 if (!SymbolsIndirectlyInvalidated.empty()) 1795 State = getCheckerManager().runCheckersForPointerEscape(State, 1796 SymbolsIndirectlyInvalidated, Call, PSK_IndirectEscapeOnCall); 1797 1798 return State; 1799} 1800 1801/// evalBind - Handle the semantics of binding a value to a specific location. 1802/// This method is used by evalStore and (soon) VisitDeclStmt, and others. 1803void ExprEngine::evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE, 1804 ExplodedNode *Pred, 1805 SVal location, SVal Val, 1806 bool atDeclInit, const ProgramPoint *PP) { 1807 1808 const LocationContext *LC = Pred->getLocationContext(); 1809 PostStmt PS(StoreE, LC); 1810 if (!PP) 1811 PP = &PS; 1812 1813 // Do a previsit of the bind. 1814 ExplodedNodeSet CheckedSet; 1815 getCheckerManager().runCheckersForBind(CheckedSet, Pred, location, Val, 1816 StoreE, *this, *PP); 1817 1818 1819 StmtNodeBuilder Bldr(CheckedSet, Dst, *currBldrCtx); 1820 1821 // If the location is not a 'Loc', it will already be handled by 1822 // the checkers. There is nothing left to do. 1823 if (!location.getAs<Loc>()) { 1824 const ProgramPoint L = PostStore(StoreE, LC, /*Loc*/0, /*tag*/0); 1825 ProgramStateRef state = Pred->getState(); 1826 state = processPointerEscapedOnBind(state, location, Val); 1827 Bldr.generateNode(L, state, Pred); 1828 return; 1829 } 1830 1831 1832 for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end(); 1833 I!=E; ++I) { 1834 ExplodedNode *PredI = *I; 1835 ProgramStateRef state = PredI->getState(); 1836 1837 state = processPointerEscapedOnBind(state, location, Val); 1838 1839 // When binding the value, pass on the hint that this is a initialization. 1840 // For initializations, we do not need to inform clients of region 1841 // changes. 1842 state = state->bindLoc(location.castAs<Loc>(), 1843 Val, /* notifyChanges = */ !atDeclInit); 1844 1845 const MemRegion *LocReg = 0; 1846 if (Optional<loc::MemRegionVal> LocRegVal = 1847 location.getAs<loc::MemRegionVal>()) { 1848 LocReg = LocRegVal->getRegion(); 1849 } 1850 1851 const ProgramPoint L = PostStore(StoreE, LC, LocReg, 0); 1852 Bldr.generateNode(L, state, PredI); 1853 } 1854} 1855 1856/// evalStore - Handle the semantics of a store via an assignment. 1857/// @param Dst The node set to store generated state nodes 1858/// @param AssignE The assignment expression if the store happens in an 1859/// assignment. 1860/// @param LocationE The location expression that is stored to. 1861/// @param state The current simulation state 1862/// @param location The location to store the value 1863/// @param Val The value to be stored 1864void ExprEngine::evalStore(ExplodedNodeSet &Dst, const Expr *AssignE, 1865 const Expr *LocationE, 1866 ExplodedNode *Pred, 1867 ProgramStateRef state, SVal location, SVal Val, 1868 const ProgramPointTag *tag) { 1869 // Proceed with the store. We use AssignE as the anchor for the PostStore 1870 // ProgramPoint if it is non-NULL, and LocationE otherwise. 1871 const Expr *StoreE = AssignE ? AssignE : LocationE; 1872 1873 // Evaluate the location (checks for bad dereferences). 1874 ExplodedNodeSet Tmp; 1875 evalLocation(Tmp, AssignE, LocationE, Pred, state, location, tag, false); 1876 1877 if (Tmp.empty()) 1878 return; 1879 1880 if (location.isUndef()) 1881 return; 1882 1883 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) 1884 evalBind(Dst, StoreE, *NI, location, Val, false); 1885} 1886 1887void ExprEngine::evalLoad(ExplodedNodeSet &Dst, 1888 const Expr *NodeEx, 1889 const Expr *BoundEx, 1890 ExplodedNode *Pred, 1891 ProgramStateRef state, 1892 SVal location, 1893 const ProgramPointTag *tag, 1894 QualType LoadTy) 1895{ 1896 assert(!location.getAs<NonLoc>() && "location cannot be a NonLoc."); 1897 1898 // Are we loading from a region? This actually results in two loads; one 1899 // to fetch the address of the referenced value and one to fetch the 1900 // referenced value. 1901 if (const TypedValueRegion *TR = 1902 dyn_cast_or_null<TypedValueRegion>(location.getAsRegion())) { 1903 1904 QualType ValTy = TR->getValueType(); 1905 if (const ReferenceType *RT = ValTy->getAs<ReferenceType>()) { 1906 static SimpleProgramPointTag 1907 loadReferenceTag("ExprEngine : Load Reference"); 1908 ExplodedNodeSet Tmp; 1909 evalLoadCommon(Tmp, NodeEx, BoundEx, Pred, state, 1910 location, &loadReferenceTag, 1911 getContext().getPointerType(RT->getPointeeType())); 1912 1913 // Perform the load from the referenced value. 1914 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end() ; I!=E; ++I) { 1915 state = (*I)->getState(); 1916 location = state->getSVal(BoundEx, (*I)->getLocationContext()); 1917 evalLoadCommon(Dst, NodeEx, BoundEx, *I, state, location, tag, LoadTy); 1918 } 1919 return; 1920 } 1921 } 1922 1923 evalLoadCommon(Dst, NodeEx, BoundEx, Pred, state, location, tag, LoadTy); 1924} 1925 1926void ExprEngine::evalLoadCommon(ExplodedNodeSet &Dst, 1927 const Expr *NodeEx, 1928 const Expr *BoundEx, 1929 ExplodedNode *Pred, 1930 ProgramStateRef state, 1931 SVal location, 1932 const ProgramPointTag *tag, 1933 QualType LoadTy) { 1934 assert(NodeEx); 1935 assert(BoundEx); 1936 // Evaluate the location (checks for bad dereferences). 1937 ExplodedNodeSet Tmp; 1938 evalLocation(Tmp, NodeEx, BoundEx, Pred, state, location, tag, true); 1939 if (Tmp.empty()) 1940 return; 1941 1942 StmtNodeBuilder Bldr(Tmp, Dst, *currBldrCtx); 1943 if (location.isUndef()) 1944 return; 1945 1946 // Proceed with the load. 1947 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) { 1948 state = (*NI)->getState(); 1949 const LocationContext *LCtx = (*NI)->getLocationContext(); 1950 1951 SVal V = UnknownVal(); 1952 if (location.isValid()) { 1953 if (LoadTy.isNull()) 1954 LoadTy = BoundEx->getType(); 1955 V = state->getSVal(location.castAs<Loc>(), LoadTy); 1956 } 1957 1958 Bldr.generateNode(NodeEx, *NI, state->BindExpr(BoundEx, LCtx, V), tag, 1959 ProgramPoint::PostLoadKind); 1960 } 1961} 1962 1963void ExprEngine::evalLocation(ExplodedNodeSet &Dst, 1964 const Stmt *NodeEx, 1965 const Stmt *BoundEx, 1966 ExplodedNode *Pred, 1967 ProgramStateRef state, 1968 SVal location, 1969 const ProgramPointTag *tag, 1970 bool isLoad) { 1971 StmtNodeBuilder BldrTop(Pred, Dst, *currBldrCtx); 1972 // Early checks for performance reason. 1973 if (location.isUnknown()) { 1974 return; 1975 } 1976 1977 ExplodedNodeSet Src; 1978 BldrTop.takeNodes(Pred); 1979 StmtNodeBuilder Bldr(Pred, Src, *currBldrCtx); 1980 if (Pred->getState() != state) { 1981 // Associate this new state with an ExplodedNode. 1982 // FIXME: If I pass null tag, the graph is incorrect, e.g for 1983 // int *p; 1984 // p = 0; 1985 // *p = 0xDEADBEEF; 1986 // "p = 0" is not noted as "Null pointer value stored to 'p'" but 1987 // instead "int *p" is noted as 1988 // "Variable 'p' initialized to a null pointer value" 1989 1990 static SimpleProgramPointTag tag("ExprEngine: Location"); 1991 Bldr.generateNode(NodeEx, Pred, state, &tag); 1992 } 1993 ExplodedNodeSet Tmp; 1994 getCheckerManager().runCheckersForLocation(Tmp, Src, location, isLoad, 1995 NodeEx, BoundEx, *this); 1996 BldrTop.addNodes(Tmp); 1997} 1998 1999std::pair<const ProgramPointTag *, const ProgramPointTag*> 2000ExprEngine::geteagerlyAssumeBinOpBifurcationTags() { 2001 static SimpleProgramPointTag 2002 eagerlyAssumeBinOpBifurcationTrue("ExprEngine : Eagerly Assume True"), 2003 eagerlyAssumeBinOpBifurcationFalse("ExprEngine : Eagerly Assume False"); 2004 return std::make_pair(&eagerlyAssumeBinOpBifurcationTrue, 2005 &eagerlyAssumeBinOpBifurcationFalse); 2006} 2007 2008void ExprEngine::evalEagerlyAssumeBinOpBifurcation(ExplodedNodeSet &Dst, 2009 ExplodedNodeSet &Src, 2010 const Expr *Ex) { 2011 StmtNodeBuilder Bldr(Src, Dst, *currBldrCtx); 2012 2013 for (ExplodedNodeSet::iterator I=Src.begin(), E=Src.end(); I!=E; ++I) { 2014 ExplodedNode *Pred = *I; 2015 // Test if the previous node was as the same expression. This can happen 2016 // when the expression fails to evaluate to anything meaningful and 2017 // (as an optimization) we don't generate a node. 2018 ProgramPoint P = Pred->getLocation(); 2019 if (!P.getAs<PostStmt>() || P.castAs<PostStmt>().getStmt() != Ex) { 2020 continue; 2021 } 2022 2023 ProgramStateRef state = Pred->getState(); 2024 SVal V = state->getSVal(Ex, Pred->getLocationContext()); 2025 Optional<nonloc::SymbolVal> SEV = V.getAs<nonloc::SymbolVal>(); 2026 if (SEV && SEV->isExpression()) { 2027 const std::pair<const ProgramPointTag *, const ProgramPointTag*> &tags = 2028 geteagerlyAssumeBinOpBifurcationTags(); 2029 2030 ProgramStateRef StateTrue, StateFalse; 2031 tie(StateTrue, StateFalse) = state->assume(*SEV); 2032 2033 // First assume that the condition is true. 2034 if (StateTrue) { 2035 SVal Val = svalBuilder.makeIntVal(1U, Ex->getType()); 2036 StateTrue = StateTrue->BindExpr(Ex, Pred->getLocationContext(), Val); 2037 Bldr.generateNode(Ex, Pred, StateTrue, tags.first); 2038 } 2039 2040 // Next, assume that the condition is false. 2041 if (StateFalse) { 2042 SVal Val = svalBuilder.makeIntVal(0U, Ex->getType()); 2043 StateFalse = StateFalse->BindExpr(Ex, Pred->getLocationContext(), Val); 2044 Bldr.generateNode(Ex, Pred, StateFalse, tags.second); 2045 } 2046 } 2047 } 2048} 2049 2050void ExprEngine::VisitGCCAsmStmt(const GCCAsmStmt *A, ExplodedNode *Pred, 2051 ExplodedNodeSet &Dst) { 2052 StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); 2053 // We have processed both the inputs and the outputs. All of the outputs 2054 // should evaluate to Locs. Nuke all of their values. 2055 2056 // FIXME: Some day in the future it would be nice to allow a "plug-in" 2057 // which interprets the inline asm and stores proper results in the 2058 // outputs. 2059 2060 ProgramStateRef state = Pred->getState(); 2061 2062 for (GCCAsmStmt::const_outputs_iterator OI = A->begin_outputs(), 2063 OE = A->end_outputs(); OI != OE; ++OI) { 2064 SVal X = state->getSVal(*OI, Pred->getLocationContext()); 2065 assert (!X.getAs<NonLoc>()); // Should be an Lval, or unknown, undef. 2066 2067 if (Optional<Loc> LV = X.getAs<Loc>()) 2068 state = state->bindLoc(*LV, UnknownVal()); 2069 } 2070 2071 Bldr.generateNode(A, Pred, state); 2072} 2073 2074void ExprEngine::VisitMSAsmStmt(const MSAsmStmt *A, ExplodedNode *Pred, 2075 ExplodedNodeSet &Dst) { 2076 StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); 2077 Bldr.generateNode(A, Pred, Pred->getState()); 2078} 2079 2080//===----------------------------------------------------------------------===// 2081// Visualization. 2082//===----------------------------------------------------------------------===// 2083 2084#ifndef NDEBUG 2085static ExprEngine* GraphPrintCheckerState; 2086static SourceManager* GraphPrintSourceManager; 2087 2088namespace llvm { 2089template<> 2090struct DOTGraphTraits<ExplodedNode*> : 2091 public DefaultDOTGraphTraits { 2092 2093 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} 2094 2095 // FIXME: Since we do not cache error nodes in ExprEngine now, this does not 2096 // work. 2097 static std::string getNodeAttributes(const ExplodedNode *N, void*) { 2098 2099#if 0 2100 // FIXME: Replace with a general scheme to tell if the node is 2101 // an error node. 2102 if (GraphPrintCheckerState->isImplicitNullDeref(N) || 2103 GraphPrintCheckerState->isExplicitNullDeref(N) || 2104 GraphPrintCheckerState->isUndefDeref(N) || 2105 GraphPrintCheckerState->isUndefStore(N) || 2106 GraphPrintCheckerState->isUndefControlFlow(N) || 2107 GraphPrintCheckerState->isUndefResult(N) || 2108 GraphPrintCheckerState->isBadCall(N) || 2109 GraphPrintCheckerState->isUndefArg(N)) 2110 return "color=\"red\",style=\"filled\""; 2111 2112 if (GraphPrintCheckerState->isNoReturnCall(N)) 2113 return "color=\"blue\",style=\"filled\""; 2114#endif 2115 return ""; 2116 } 2117 2118 static void printLocation(raw_ostream &Out, SourceLocation SLoc) { 2119 if (SLoc.isFileID()) { 2120 Out << "\\lline=" 2121 << GraphPrintSourceManager->getExpansionLineNumber(SLoc) 2122 << " col=" 2123 << GraphPrintSourceManager->getExpansionColumnNumber(SLoc) 2124 << "\\l"; 2125 } 2126 } 2127 2128 static std::string getNodeLabel(const ExplodedNode *N, void*){ 2129 2130 std::string sbuf; 2131 llvm::raw_string_ostream Out(sbuf); 2132 2133 // Program Location. 2134 ProgramPoint Loc = N->getLocation(); 2135 2136 switch (Loc.getKind()) { 2137 case ProgramPoint::BlockEntranceKind: { 2138 Out << "Block Entrance: B" 2139 << Loc.castAs<BlockEntrance>().getBlock()->getBlockID(); 2140 if (const NamedDecl *ND = 2141 dyn_cast<NamedDecl>(Loc.getLocationContext()->getDecl())) { 2142 Out << " ("; 2143 ND->printName(Out); 2144 Out << ")"; 2145 } 2146 break; 2147 } 2148 2149 case ProgramPoint::BlockExitKind: 2150 assert (false); 2151 break; 2152 2153 case ProgramPoint::CallEnterKind: 2154 Out << "CallEnter"; 2155 break; 2156 2157 case ProgramPoint::CallExitBeginKind: 2158 Out << "CallExitBegin"; 2159 break; 2160 2161 case ProgramPoint::CallExitEndKind: 2162 Out << "CallExitEnd"; 2163 break; 2164 2165 case ProgramPoint::PostStmtPurgeDeadSymbolsKind: 2166 Out << "PostStmtPurgeDeadSymbols"; 2167 break; 2168 2169 case ProgramPoint::PreStmtPurgeDeadSymbolsKind: 2170 Out << "PreStmtPurgeDeadSymbols"; 2171 break; 2172 2173 case ProgramPoint::EpsilonKind: 2174 Out << "Epsilon Point"; 2175 break; 2176 2177 case ProgramPoint::PreImplicitCallKind: { 2178 ImplicitCallPoint PC = Loc.castAs<ImplicitCallPoint>(); 2179 Out << "PreCall: "; 2180 2181 // FIXME: Get proper printing options. 2182 PC.getDecl()->print(Out, LangOptions()); 2183 printLocation(Out, PC.getLocation()); 2184 break; 2185 } 2186 2187 case ProgramPoint::PostImplicitCallKind: { 2188 ImplicitCallPoint PC = Loc.castAs<ImplicitCallPoint>(); 2189 Out << "PostCall: "; 2190 2191 // FIXME: Get proper printing options. 2192 PC.getDecl()->print(Out, LangOptions()); 2193 printLocation(Out, PC.getLocation()); 2194 break; 2195 } 2196 2197 case ProgramPoint::PostInitializerKind: { 2198 Out << "PostInitializer: "; 2199 const CXXCtorInitializer *Init = 2200 Loc.castAs<PostInitializer>().getInitializer(); 2201 if (const FieldDecl *FD = Init->getAnyMember()) 2202 Out << *FD; 2203 else { 2204 QualType Ty = Init->getTypeSourceInfo()->getType(); 2205 Ty = Ty.getLocalUnqualifiedType(); 2206 LangOptions LO; // FIXME. 2207 Ty.print(Out, LO); 2208 } 2209 break; 2210 } 2211 2212 case ProgramPoint::BlockEdgeKind: { 2213 const BlockEdge &E = Loc.castAs<BlockEdge>(); 2214 Out << "Edge: (B" << E.getSrc()->getBlockID() << ", B" 2215 << E.getDst()->getBlockID() << ')'; 2216 2217 if (const Stmt *T = E.getSrc()->getTerminator()) { 2218 SourceLocation SLoc = T->getLocStart(); 2219 2220 Out << "\\|Terminator: "; 2221 LangOptions LO; // FIXME. 2222 E.getSrc()->printTerminator(Out, LO); 2223 2224 if (SLoc.isFileID()) { 2225 Out << "\\lline=" 2226 << GraphPrintSourceManager->getExpansionLineNumber(SLoc) 2227 << " col=" 2228 << GraphPrintSourceManager->getExpansionColumnNumber(SLoc); 2229 } 2230 2231 if (isa<SwitchStmt>(T)) { 2232 const Stmt *Label = E.getDst()->getLabel(); 2233 2234 if (Label) { 2235 if (const CaseStmt *C = dyn_cast<CaseStmt>(Label)) { 2236 Out << "\\lcase "; 2237 LangOptions LO; // FIXME. 2238 C->getLHS()->printPretty(Out, 0, PrintingPolicy(LO)); 2239 2240 if (const Stmt *RHS = C->getRHS()) { 2241 Out << " .. "; 2242 RHS->printPretty(Out, 0, PrintingPolicy(LO)); 2243 } 2244 2245 Out << ":"; 2246 } 2247 else { 2248 assert (isa<DefaultStmt>(Label)); 2249 Out << "\\ldefault:"; 2250 } 2251 } 2252 else 2253 Out << "\\l(implicit) default:"; 2254 } 2255 else if (isa<IndirectGotoStmt>(T)) { 2256 // FIXME 2257 } 2258 else { 2259 Out << "\\lCondition: "; 2260 if (*E.getSrc()->succ_begin() == E.getDst()) 2261 Out << "true"; 2262 else 2263 Out << "false"; 2264 } 2265 2266 Out << "\\l"; 2267 } 2268 2269#if 0 2270 // FIXME: Replace with a general scheme to determine 2271 // the name of the check. 2272 if (GraphPrintCheckerState->isUndefControlFlow(N)) { 2273 Out << "\\|Control-flow based on\\lUndefined value.\\l"; 2274 } 2275#endif 2276 break; 2277 } 2278 2279 default: { 2280 const Stmt *S = Loc.castAs<StmtPoint>().getStmt(); 2281 2282 Out << S->getStmtClassName() << ' ' << (const void*) S << ' '; 2283 LangOptions LO; // FIXME. 2284 S->printPretty(Out, 0, PrintingPolicy(LO)); 2285 printLocation(Out, S->getLocStart()); 2286 2287 if (Loc.getAs<PreStmt>()) 2288 Out << "\\lPreStmt\\l;"; 2289 else if (Loc.getAs<PostLoad>()) 2290 Out << "\\lPostLoad\\l;"; 2291 else if (Loc.getAs<PostStore>()) 2292 Out << "\\lPostStore\\l"; 2293 else if (Loc.getAs<PostLValue>()) 2294 Out << "\\lPostLValue\\l"; 2295 2296#if 0 2297 // FIXME: Replace with a general scheme to determine 2298 // the name of the check. 2299 if (GraphPrintCheckerState->isImplicitNullDeref(N)) 2300 Out << "\\|Implicit-Null Dereference.\\l"; 2301 else if (GraphPrintCheckerState->isExplicitNullDeref(N)) 2302 Out << "\\|Explicit-Null Dereference.\\l"; 2303 else if (GraphPrintCheckerState->isUndefDeref(N)) 2304 Out << "\\|Dereference of undefialied value.\\l"; 2305 else if (GraphPrintCheckerState->isUndefStore(N)) 2306 Out << "\\|Store to Undefined Loc."; 2307 else if (GraphPrintCheckerState->isUndefResult(N)) 2308 Out << "\\|Result of operation is undefined."; 2309 else if (GraphPrintCheckerState->isNoReturnCall(N)) 2310 Out << "\\|Call to function marked \"noreturn\"."; 2311 else if (GraphPrintCheckerState->isBadCall(N)) 2312 Out << "\\|Call to NULL/Undefined."; 2313 else if (GraphPrintCheckerState->isUndefArg(N)) 2314 Out << "\\|Argument in call is undefined"; 2315#endif 2316 2317 break; 2318 } 2319 } 2320 2321 ProgramStateRef state = N->getState(); 2322 Out << "\\|StateID: " << (const void*) state.getPtr() 2323 << " NodeID: " << (const void*) N << "\\|"; 2324 state->printDOT(Out); 2325 2326 Out << "\\l"; 2327 2328 if (const ProgramPointTag *tag = Loc.getTag()) { 2329 Out << "\\|Tag: " << tag->getTagDescription(); 2330 Out << "\\l"; 2331 } 2332 return Out.str(); 2333 } 2334}; 2335} // end llvm namespace 2336#endif 2337 2338#ifndef NDEBUG 2339template <typename ITERATOR> 2340ExplodedNode *GetGraphNode(ITERATOR I) { return *I; } 2341 2342template <> ExplodedNode* 2343GetGraphNode<llvm::DenseMap<ExplodedNode*, Expr*>::iterator> 2344 (llvm::DenseMap<ExplodedNode*, Expr*>::iterator I) { 2345 return I->first; 2346} 2347#endif 2348 2349void ExprEngine::ViewGraph(bool trim) { 2350#ifndef NDEBUG 2351 if (trim) { 2352 std::vector<const ExplodedNode*> Src; 2353 2354 // Flush any outstanding reports to make sure we cover all the nodes. 2355 // This does not cause them to get displayed. 2356 for (BugReporter::iterator I=BR.begin(), E=BR.end(); I!=E; ++I) 2357 const_cast<BugType*>(*I)->FlushReports(BR); 2358 2359 // Iterate through the reports and get their nodes. 2360 for (BugReporter::EQClasses_iterator 2361 EI = BR.EQClasses_begin(), EE = BR.EQClasses_end(); EI != EE; ++EI) { 2362 ExplodedNode *N = const_cast<ExplodedNode*>(EI->begin()->getErrorNode()); 2363 if (N) Src.push_back(N); 2364 } 2365 2366 ViewGraph(Src); 2367 } 2368 else { 2369 GraphPrintCheckerState = this; 2370 GraphPrintSourceManager = &getContext().getSourceManager(); 2371 2372 llvm::ViewGraph(*G.roots_begin(), "ExprEngine"); 2373 2374 GraphPrintCheckerState = NULL; 2375 GraphPrintSourceManager = NULL; 2376 } 2377#endif 2378} 2379 2380void ExprEngine::ViewGraph(ArrayRef<const ExplodedNode*> Nodes) { 2381#ifndef NDEBUG 2382 GraphPrintCheckerState = this; 2383 GraphPrintSourceManager = &getContext().getSourceManager(); 2384 2385 OwningPtr<ExplodedGraph> TrimmedG(G.trim(Nodes)); 2386 2387 if (!TrimmedG.get()) 2388 llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n"; 2389 else 2390 llvm::ViewGraph(*TrimmedG->roots_begin(), "TrimmedExprEngine"); 2391 2392 GraphPrintCheckerState = NULL; 2393 GraphPrintSourceManager = NULL; 2394#endif 2395} 2396