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