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