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