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