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