1221339Sdim//=-- ExprEngine.cpp - Path-Sensitive Expression-Level Dataflow ---*- C++ -*-= 2221339Sdim// 3221339Sdim// The LLVM Compiler Infrastructure 4221339Sdim// 5221339Sdim// This file is distributed under the University of Illinois Open Source 6221339Sdim// License. See LICENSE.TXT for details. 7221339Sdim// 8221339Sdim//===----------------------------------------------------------------------===// 9221339Sdim// 10221339Sdim// This file defines a meta-engine for path-sensitive dataflow analysis that 11221339Sdim// is built on GREngine, but provides the boilerplate to execute transfer 12221339Sdim// functions and build the ExplodedGraph at the expression level. 13221339Sdim// 14221339Sdim//===----------------------------------------------------------------------===// 15221339Sdim 16235633Sdim#define DEBUG_TYPE "ExprEngine" 17235633Sdim 18221339Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 19263509Sdim#include "PrettyStackTraceLocationContext.h" 20221339Sdim#include "clang/AST/CharUnits.h" 21221339Sdim#include "clang/AST/ParentMap.h" 22252723Sdim#include "clang/AST/StmtCXX.h" 23221339Sdim#include "clang/AST/StmtObjC.h" 24221339Sdim#include "clang/Basic/Builtins.h" 25252723Sdim#include "clang/Basic/PrettyStackTrace.h" 26221339Sdim#include "clang/Basic/SourceManager.h" 27252723Sdim#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 28252723Sdim#include "clang/StaticAnalyzer/Core/CheckerManager.h" 29252723Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" 30252723Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 31221339Sdim#include "llvm/ADT/ImmutableList.h" 32235633Sdim#include "llvm/ADT/Statistic.h" 33252723Sdim#include "llvm/Support/raw_ostream.h" 34221339Sdim 35221339Sdim#ifndef NDEBUG 36221339Sdim#include "llvm/Support/GraphWriter.h" 37221339Sdim#endif 38221339Sdim 39221339Sdimusing namespace clang; 40221339Sdimusing namespace ento; 41221339Sdimusing llvm::APSInt; 42221339Sdim 43235633SdimSTATISTIC(NumRemoveDeadBindings, 44235633Sdim "The # of times RemoveDeadBindings is called"); 45235633SdimSTATISTIC(NumMaxBlockCountReached, 46235633Sdim "The # of aborted paths due to reaching the maximum block count in " 47235633Sdim "a top level function"); 48235633SdimSTATISTIC(NumMaxBlockCountReachedInInlined, 49235633Sdim "The # of aborted paths due to reaching the maximum block count in " 50235633Sdim "an inlined function"); 51235633SdimSTATISTIC(NumTimesRetriedWithoutInlining, 52235633Sdim "The # of times we re-evaluated a call without inlining"); 53235633Sdim 54221339Sdim//===----------------------------------------------------------------------===// 55221339Sdim// Engine construction and deletion. 56221339Sdim//===----------------------------------------------------------------------===// 57221339Sdim 58235633SdimExprEngine::ExprEngine(AnalysisManager &mgr, bool gcEnabled, 59245431Sdim SetOfConstDecls *VisitedCalleesIn, 60252723Sdim FunctionSummariesTy *FS, 61252723Sdim InliningModes HowToInlineIn) 62221339Sdim : AMgr(mgr), 63235633Sdim AnalysisDeclContexts(mgr.getAnalysisDeclContextManager()), 64245431Sdim Engine(*this, FS), 65221339Sdim G(Engine.getGraph()), 66221339Sdim StateMgr(getContext(), mgr.getStoreManagerCreator(), 67221339Sdim mgr.getConstraintManagerCreator(), G.getAllocator(), 68245431Sdim this), 69221339Sdim SymMgr(StateMgr.getSymbolManager()), 70221339Sdim svalBuilder(StateMgr.getSValBuilder()), 71252723Sdim currStmtIdx(0), currBldrCtx(0), 72245431Sdim ObjCNoRet(mgr.getASTContext()), 73245431Sdim ObjCGCEnabled(gcEnabled), BR(mgr, *this), 74252723Sdim VisitedCallees(VisitedCalleesIn), 75252723Sdim HowToInline(HowToInlineIn) 76245431Sdim{ 77245431Sdim unsigned TrimInterval = mgr.options.getGraphTrimInterval(); 78245431Sdim if (TrimInterval != 0) { 79245431Sdim // Enable eager node reclaimation when constructing the ExplodedGraph. 80245431Sdim G.enableNodeReclamation(TrimInterval); 81221339Sdim } 82221339Sdim} 83221339Sdim 84221339SdimExprEngine::~ExprEngine() { 85221339Sdim BR.FlushReports(); 86221339Sdim} 87221339Sdim 88221339Sdim//===----------------------------------------------------------------------===// 89221339Sdim// Utility methods. 90221339Sdim//===----------------------------------------------------------------------===// 91221339Sdim 92235633SdimProgramStateRef ExprEngine::getInitialState(const LocationContext *InitLoc) { 93235633Sdim ProgramStateRef state = StateMgr.getInitialState(InitLoc); 94235633Sdim const Decl *D = InitLoc->getDecl(); 95221339Sdim 96221339Sdim // Preconditions. 97221339Sdim // FIXME: It would be nice if we had a more general mechanism to add 98221339Sdim // such preconditions. Some day. 99221339Sdim do { 100235633Sdim 101221339Sdim if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 102221339Sdim // Precondition: the first argument of 'main' is an integer guaranteed 103221339Sdim // to be > 0. 104221339Sdim const IdentifierInfo *II = FD->getIdentifier(); 105221339Sdim if (!II || !(II->getName() == "main" && FD->getNumParams() > 0)) 106221339Sdim break; 107221339Sdim 108221339Sdim const ParmVarDecl *PD = FD->getParamDecl(0); 109221339Sdim QualType T = PD->getType(); 110252723Sdim const BuiltinType *BT = dyn_cast<BuiltinType>(T); 111252723Sdim if (!BT || !BT->isInteger()) 112221339Sdim break; 113221339Sdim 114221339Sdim const MemRegion *R = state->getRegion(PD, InitLoc); 115221339Sdim if (!R) 116221339Sdim break; 117221339Sdim 118221339Sdim SVal V = state->getSVal(loc::MemRegionVal(R)); 119221339Sdim SVal Constraint_untested = evalBinOp(state, BO_GT, V, 120221339Sdim svalBuilder.makeZeroVal(T), 121221339Sdim getContext().IntTy); 122221339Sdim 123252723Sdim Optional<DefinedOrUnknownSVal> Constraint = 124252723Sdim Constraint_untested.getAs<DefinedOrUnknownSVal>(); 125221339Sdim 126221339Sdim if (!Constraint) 127221339Sdim break; 128221339Sdim 129235633Sdim if (ProgramStateRef newState = state->assume(*Constraint, true)) 130221339Sdim state = newState; 131221339Sdim } 132235633Sdim break; 133235633Sdim } 134235633Sdim while (0); 135221339Sdim 136235633Sdim if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) { 137235633Sdim // Precondition: 'self' is always non-null upon entry to an Objective-C 138235633Sdim // method. 139235633Sdim const ImplicitParamDecl *SelfD = MD->getSelfDecl(); 140235633Sdim const MemRegion *R = state->getRegion(SelfD, InitLoc); 141235633Sdim SVal V = state->getSVal(loc::MemRegionVal(R)); 142221339Sdim 143252723Sdim if (Optional<Loc> LV = V.getAs<Loc>()) { 144235633Sdim // Assume that the pointer value in 'self' is non-null. 145235633Sdim state = state->assume(*LV, true); 146235633Sdim assert(state && "'self' cannot be null"); 147221339Sdim } 148235633Sdim } 149221339Sdim 150235633Sdim if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(D)) { 151235633Sdim if (!MD->isStatic()) { 152235633Sdim // Precondition: 'this' is always non-null upon entry to the 153235633Sdim // top-level function. This is our starting assumption for 154235633Sdim // analyzing an "open" program. 155235633Sdim const StackFrameContext *SFC = InitLoc->getCurrentStackFrame(); 156235633Sdim if (SFC->getParent() == 0) { 157245431Sdim loc::MemRegionVal L = svalBuilder.getCXXThis(MD, SFC); 158235633Sdim SVal V = state->getSVal(L); 159252723Sdim if (Optional<Loc> LV = V.getAs<Loc>()) { 160235633Sdim state = state->assume(*LV, true); 161235633Sdim assert(state && "'this' cannot be null"); 162235633Sdim } 163223017Sdim } 164223017Sdim } 165223017Sdim } 166235633Sdim 167235633Sdim return state; 168223017Sdim} 169223017Sdim 170252723SdimProgramStateRef 171252723SdimExprEngine::createTemporaryRegionIfNeeded(ProgramStateRef State, 172252723Sdim const LocationContext *LC, 173252723Sdim const Expr *Ex, 174252723Sdim const Expr *Result) { 175252723Sdim SVal V = State->getSVal(Ex, LC); 176252723Sdim if (!Result) { 177252723Sdim // If we don't have an explicit result expression, we're in "if needed" 178252723Sdim // mode. Only create a region if the current value is a NonLoc. 179252723Sdim if (!V.getAs<NonLoc>()) 180252723Sdim return State; 181252723Sdim Result = Ex; 182252723Sdim } else { 183252723Sdim // We need to create a region no matter what. For sanity, make sure we don't 184252723Sdim // try to stuff a Loc into a non-pointer temporary region. 185252723Sdim assert(!V.getAs<Loc>() || Loc::isLocType(Result->getType()) || 186252723Sdim Result->getType()->isMemberPointerType()); 187252723Sdim } 188245431Sdim 189252723Sdim ProgramStateManager &StateMgr = State->getStateManager(); 190252723Sdim MemRegionManager &MRMgr = StateMgr.getRegionManager(); 191252723Sdim StoreManager &StoreMgr = StateMgr.getStoreManager(); 192252723Sdim 193252723Sdim // We need to be careful about treating a derived type's value as 194252723Sdim // bindings for a base type. Unless we're creating a temporary pointer region, 195252723Sdim // start by stripping and recording base casts. 196252723Sdim SmallVector<const CastExpr *, 4> Casts; 197252723Sdim const Expr *Inner = Ex->IgnoreParens(); 198252723Sdim if (!Loc::isLocType(Result->getType())) { 199252723Sdim while (const CastExpr *CE = dyn_cast<CastExpr>(Inner)) { 200252723Sdim if (CE->getCastKind() == CK_DerivedToBase || 201252723Sdim CE->getCastKind() == CK_UncheckedDerivedToBase) 202252723Sdim Casts.push_back(CE); 203252723Sdim else if (CE->getCastKind() != CK_NoOp) 204252723Sdim break; 205252723Sdim 206252723Sdim Inner = CE->getSubExpr()->IgnoreParens(); 207252723Sdim } 208245431Sdim } 209245431Sdim 210252723Sdim // Create a temporary object region for the inner expression (which may have 211252723Sdim // a more derived type) and bind the value into it. 212263509Sdim const TypedValueRegion *TR = NULL; 213263509Sdim if (const MaterializeTemporaryExpr *MT = 214263509Sdim dyn_cast<MaterializeTemporaryExpr>(Result)) { 215263509Sdim StorageDuration SD = MT->getStorageDuration(); 216263509Sdim // If this object is bound to a reference with static storage duration, we 217263509Sdim // put it in a different region to prevent "address leakage" warnings. 218263509Sdim if (SD == SD_Static || SD == SD_Thread) 219263509Sdim TR = MRMgr.getCXXStaticTempObjectRegion(Inner); 220263509Sdim } 221263509Sdim if (!TR) 222263509Sdim TR = MRMgr.getCXXTempObjectRegion(Inner, LC); 223263509Sdim 224252723Sdim SVal Reg = loc::MemRegionVal(TR); 225252723Sdim 226252723Sdim if (V.isUnknown()) 227252723Sdim V = getSValBuilder().conjureSymbolVal(Result, LC, TR->getValueType(), 228252723Sdim currBldrCtx->blockCount()); 229252723Sdim State = State->bindLoc(Reg, V); 230252723Sdim 231252723Sdim // Re-apply the casts (from innermost to outermost) for type sanity. 232252723Sdim for (SmallVectorImpl<const CastExpr *>::reverse_iterator I = Casts.rbegin(), 233252723Sdim E = Casts.rend(); 234252723Sdim I != E; ++I) { 235252723Sdim Reg = StoreMgr.evalDerivedToBase(Reg, *I); 236252723Sdim } 237252723Sdim 238252723Sdim State = State->BindExpr(Result, LC, Reg); 239245431Sdim return State; 240245431Sdim} 241245431Sdim 242221339Sdim//===----------------------------------------------------------------------===// 243221339Sdim// Top-level transfer function logic (Dispatcher). 244221339Sdim//===----------------------------------------------------------------------===// 245221339Sdim 246221339Sdim/// evalAssume - Called by ConstraintManager. Used to call checker-specific 247221339Sdim/// logic for handling assumptions on symbolic values. 248235633SdimProgramStateRef ExprEngine::processAssume(ProgramStateRef state, 249226890Sdim SVal cond, bool assumption) { 250226890Sdim return getCheckerManager().runCheckersForEvalAssume(state, cond, assumption); 251221339Sdim} 252221339Sdim 253235633Sdimbool ExprEngine::wantsRegionChangeUpdate(ProgramStateRef state) { 254221339Sdim return getCheckerManager().wantsRegionChangeUpdate(state); 255221339Sdim} 256221339Sdim 257235633SdimProgramStateRef 258235633SdimExprEngine::processRegionChanges(ProgramStateRef state, 259252723Sdim const InvalidatedSymbols *invalidated, 260226890Sdim ArrayRef<const MemRegion *> Explicits, 261235633Sdim ArrayRef<const MemRegion *> Regions, 262245431Sdim const CallEvent *Call) { 263223017Sdim return getCheckerManager().runCheckersForRegionChanges(state, invalidated, 264235633Sdim Explicits, Regions, Call); 265221339Sdim} 266221339Sdim 267235633Sdimvoid ExprEngine::printState(raw_ostream &Out, ProgramStateRef State, 268226890Sdim const char *NL, const char *Sep) { 269226890Sdim getCheckerManager().runCheckersForPrintState(Out, State, NL, Sep); 270226890Sdim} 271226890Sdim 272221339Sdimvoid ExprEngine::processEndWorklist(bool hasWorkRemaining) { 273221339Sdim getCheckerManager().runCheckersForEndAnalysis(G, BR, *this); 274221339Sdim} 275221339Sdim 276235633Sdimvoid ExprEngine::processCFGElement(const CFGElement E, ExplodedNode *Pred, 277235633Sdim unsigned StmtIdx, NodeBuilderContext *Ctx) { 278263509Sdim PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext()); 279245431Sdim currStmtIdx = StmtIdx; 280245431Sdim currBldrCtx = Ctx; 281235633Sdim 282221339Sdim switch (E.getKind()) { 283221339Sdim case CFGElement::Statement: 284252723Sdim ProcessStmt(const_cast<Stmt*>(E.castAs<CFGStmt>().getStmt()), Pred); 285221339Sdim return; 286221339Sdim case CFGElement::Initializer: 287252723Sdim ProcessInitializer(E.castAs<CFGInitializer>().getInitializer(), Pred); 288221339Sdim return; 289221339Sdim case CFGElement::AutomaticObjectDtor: 290263509Sdim case CFGElement::DeleteDtor: 291221339Sdim case CFGElement::BaseDtor: 292221339Sdim case CFGElement::MemberDtor: 293221339Sdim case CFGElement::TemporaryDtor: 294252723Sdim ProcessImplicitDtor(E.castAs<CFGImplicitDtor>(), Pred); 295221339Sdim return; 296221339Sdim } 297221339Sdim} 298221339Sdim 299235633Sdimstatic bool shouldRemoveDeadBindings(AnalysisManager &AMgr, 300235633Sdim const CFGStmt S, 301235633Sdim const ExplodedNode *Pred, 302235633Sdim const LocationContext *LC) { 303235633Sdim 304235633Sdim // Are we never purging state values? 305245431Sdim if (AMgr.options.AnalysisPurgeOpt == PurgeNone) 306235633Sdim return false; 307226890Sdim 308235633Sdim // Is this the beginning of a basic block? 309252723Sdim if (Pred->getLocation().getAs<BlockEntrance>()) 310235633Sdim return true; 311235633Sdim 312235633Sdim // Is this on a non-expression? 313235633Sdim if (!isa<Expr>(S.getStmt())) 314235633Sdim return true; 315235633Sdim 316235633Sdim // Run before processing a call. 317245431Sdim if (CallEvent::isCallStmt(S.getStmt())) 318235633Sdim return true; 319235633Sdim 320235633Sdim // Is this an expression that is consumed by another expression? If so, 321235633Sdim // postpone cleaning out the state. 322235633Sdim ParentMap &PM = LC->getAnalysisDeclContext()->getParentMap(); 323235633Sdim return !PM.isConsumedExpr(cast<Expr>(S.getStmt())); 324235633Sdim} 325235633Sdim 326245431Sdimvoid ExprEngine::removeDead(ExplodedNode *Pred, ExplodedNodeSet &Out, 327245431Sdim const Stmt *ReferenceStmt, 328252723Sdim const LocationContext *LC, 329245431Sdim const Stmt *DiagnosticStmt, 330245431Sdim ProgramPoint::Kind K) { 331245431Sdim assert((K == ProgramPoint::PreStmtPurgeDeadSymbolsKind || 332252723Sdim ReferenceStmt == 0 || isa<ReturnStmt>(ReferenceStmt)) 333245431Sdim && "PostStmt is not generally supported by the SymbolReaper yet"); 334252723Sdim assert(LC && "Must pass the current (or expiring) LocationContext"); 335252723Sdim 336252723Sdim if (!DiagnosticStmt) { 337252723Sdim DiagnosticStmt = ReferenceStmt; 338252723Sdim assert(DiagnosticStmt && "Required for clearing a LocationContext"); 339252723Sdim } 340252723Sdim 341245431Sdim NumRemoveDeadBindings++; 342252723Sdim ProgramStateRef CleanedState = Pred->getState(); 343221339Sdim 344252723Sdim // LC is the location context being destroyed, but SymbolReaper wants a 345252723Sdim // location context that is still live. (If this is the top-level stack 346252723Sdim // frame, this will be null.) 347252723Sdim if (!ReferenceStmt) { 348252723Sdim assert(K == ProgramPoint::PostStmtPurgeDeadSymbolsKind && 349252723Sdim "Use PostStmtPurgeDeadSymbolsKind for clearing a LocationContext"); 350252723Sdim LC = LC->getParent(); 351252723Sdim } 352252723Sdim 353252723Sdim const StackFrameContext *SFC = LC ? LC->getCurrentStackFrame() : 0; 354252723Sdim SymbolReaper SymReaper(SFC, ReferenceStmt, SymMgr, getStoreManager()); 355252723Sdim 356245431Sdim getCheckerManager().runCheckersForLiveSymbols(CleanedState, SymReaper); 357221339Sdim 358245431Sdim // Create a state in which dead bindings are removed from the environment 359245431Sdim // and the store. TODO: The function should just return new env and store, 360245431Sdim // not a new state. 361245431Sdim CleanedState = StateMgr.removeDeadBindings(CleanedState, SFC, SymReaper); 362226890Sdim 363221339Sdim // Process any special transfer function for dead symbols. 364235633Sdim // A tag to track convenience transitions, which can be removed at cleanup. 365235633Sdim static SimpleProgramPointTag cleanupTag("ExprEngine : Clean Node"); 366226890Sdim if (!SymReaper.hasDeadSymbols()) { 367226890Sdim // Generate a CleanedNode that has the environment and store cleaned 368226890Sdim // up. Since no symbols are dead, we can optimize and not clean out 369226890Sdim // the constraint manager. 370245431Sdim StmtNodeBuilder Bldr(Pred, Out, *currBldrCtx); 371245431Sdim Bldr.generateNode(DiagnosticStmt, Pred, CleanedState, &cleanupTag, K); 372221339Sdim 373226890Sdim } else { 374226890Sdim // Call checkers with the non-cleaned state so that they could query the 375226890Sdim // values of the soon to be dead symbols. 376226890Sdim ExplodedNodeSet CheckedSet; 377245431Sdim getCheckerManager().runCheckersForDeadSymbols(CheckedSet, Pred, SymReaper, 378245431Sdim DiagnosticStmt, *this, K); 379221339Sdim 380226890Sdim // For each node in CheckedSet, generate CleanedNodes that have the 381226890Sdim // environment, the store, and the constraints cleaned up but have the 382226890Sdim // user-supplied states as the predecessors. 383245431Sdim StmtNodeBuilder Bldr(CheckedSet, Out, *currBldrCtx); 384226890Sdim for (ExplodedNodeSet::const_iterator 385226890Sdim I = CheckedSet.begin(), E = CheckedSet.end(); I != E; ++I) { 386235633Sdim ProgramStateRef CheckerState = (*I)->getState(); 387226890Sdim 388226890Sdim // The constraint manager has not been cleaned up yet, so clean up now. 389226890Sdim CheckerState = getConstraintManager().removeDeadBindings(CheckerState, 390226890Sdim SymReaper); 391226890Sdim 392245431Sdim assert(StateMgr.haveEqualEnvironments(CheckerState, Pred->getState()) && 393226890Sdim "Checkers are not allowed to modify the Environment as a part of " 394226890Sdim "checkDeadSymbols processing."); 395245431Sdim assert(StateMgr.haveEqualStores(CheckerState, Pred->getState()) && 396226890Sdim "Checkers are not allowed to modify the Store as a part of " 397226890Sdim "checkDeadSymbols processing."); 398226890Sdim 399226890Sdim // Create a state based on CleanedState with CheckerState GDM and 400226890Sdim // generate a transition to that state. 401235633Sdim ProgramStateRef CleanedCheckerSt = 402226890Sdim StateMgr.getPersistentStateWithGDM(CleanedState, CheckerState); 403245431Sdim Bldr.generateNode(DiagnosticStmt, *I, CleanedCheckerSt, &cleanupTag, K); 404226890Sdim } 405221339Sdim } 406245431Sdim} 407221339Sdim 408245431Sdimvoid ExprEngine::ProcessStmt(const CFGStmt S, 409245431Sdim ExplodedNode *Pred) { 410245431Sdim // Reclaim any unnecessary nodes in the ExplodedGraph. 411245431Sdim G.reclaimRecentlyAllocatedNodes(); 412245431Sdim 413252723Sdim const Stmt *currStmt = S.getStmt(); 414245431Sdim PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 415245431Sdim currStmt->getLocStart(), 416245431Sdim "Error evaluating statement"); 417245431Sdim 418245431Sdim // Remove dead bindings and symbols. 419245431Sdim ExplodedNodeSet CleanedStates; 420252723Sdim if (shouldRemoveDeadBindings(AMgr, S, Pred, Pred->getLocationContext())){ 421252723Sdim removeDead(Pred, CleanedStates, currStmt, Pred->getLocationContext()); 422245431Sdim } else 423252723Sdim CleanedStates.Add(Pred); 424245431Sdim 425245431Sdim // Visit the statement. 426235633Sdim ExplodedNodeSet Dst; 427245431Sdim for (ExplodedNodeSet::iterator I = CleanedStates.begin(), 428245431Sdim E = CleanedStates.end(); I != E; ++I) { 429235633Sdim ExplodedNodeSet DstI; 430221339Sdim // Visit the statement. 431245431Sdim Visit(currStmt, *I, DstI); 432235633Sdim Dst.insert(DstI); 433221339Sdim } 434221339Sdim 435235633Sdim // Enqueue the new nodes onto the work list. 436245431Sdim Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx); 437221339Sdim} 438221339Sdim 439221339Sdimvoid ExprEngine::ProcessInitializer(const CFGInitializer Init, 440235633Sdim ExplodedNode *Pred) { 441245431Sdim const CXXCtorInitializer *BMI = Init.getInitializer(); 442235633Sdim 443245431Sdim PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 444245431Sdim BMI->getSourceLocation(), 445245431Sdim "Error evaluating initializer"); 446245431Sdim 447252723Sdim // We don't clean up dead bindings here. 448235633Sdim const StackFrameContext *stackFrame = 449235633Sdim cast<StackFrameContext>(Pred->getLocationContext()); 450235633Sdim const CXXConstructorDecl *decl = 451235633Sdim cast<CXXConstructorDecl>(stackFrame->getDecl()); 452221339Sdim 453245431Sdim ProgramStateRef State = Pred->getState(); 454245431Sdim SVal thisVal = State->getSVal(svalBuilder.getCXXThis(decl, stackFrame)); 455221339Sdim 456245431Sdim ExplodedNodeSet Tmp(Pred); 457252723Sdim SVal FieldLoc; 458245431Sdim 459245431Sdim // Evaluate the initializer, if necessary 460221339Sdim if (BMI->isAnyMemberInitializer()) { 461245431Sdim // Constructors build the object directly in the field, 462245431Sdim // but non-objects must be copied in from the initializer. 463252723Sdim const Expr *Init = BMI->getInit()->IgnoreImplicit(); 464245431Sdim if (!isa<CXXConstructExpr>(Init)) { 465252723Sdim const ValueDecl *Field; 466252723Sdim if (BMI->isIndirectMemberInitializer()) { 467252723Sdim Field = BMI->getIndirectMember(); 468245431Sdim FieldLoc = State->getLValue(BMI->getIndirectMember(), thisVal); 469252723Sdim } else { 470252723Sdim Field = BMI->getMember(); 471245431Sdim FieldLoc = State->getLValue(BMI->getMember(), thisVal); 472252723Sdim } 473221339Sdim 474252723Sdim SVal InitVal; 475252723Sdim if (BMI->getNumArrayIndices() > 0) { 476252723Sdim // Handle arrays of trivial type. We can represent this with a 477252723Sdim // primitive load/copy from the base array region. 478252723Sdim const ArraySubscriptExpr *ASE; 479252723Sdim while ((ASE = dyn_cast<ArraySubscriptExpr>(Init))) 480252723Sdim Init = ASE->getBase()->IgnoreImplicit(); 481221339Sdim 482252723Sdim SVal LValue = State->getSVal(Init, stackFrame); 483252723Sdim if (Optional<Loc> LValueLoc = LValue.getAs<Loc>()) 484252723Sdim InitVal = State->getSVal(*LValueLoc); 485252723Sdim 486252723Sdim // If we fail to get the value for some reason, use a symbolic value. 487252723Sdim if (InitVal.isUnknownOrUndef()) { 488252723Sdim SValBuilder &SVB = getSValBuilder(); 489252723Sdim InitVal = SVB.conjureSymbolVal(BMI->getInit(), stackFrame, 490252723Sdim Field->getType(), 491252723Sdim currBldrCtx->blockCount()); 492252723Sdim } 493252723Sdim } else { 494252723Sdim InitVal = State->getSVal(BMI->getInit(), stackFrame); 495252723Sdim } 496252723Sdim 497252723Sdim assert(Tmp.size() == 1 && "have not generated any new nodes yet"); 498252723Sdim assert(*Tmp.begin() == Pred && "have not generated any new nodes yet"); 499245431Sdim Tmp.clear(); 500252723Sdim 501252723Sdim PostInitializer PP(BMI, FieldLoc.getAsRegion(), stackFrame); 502245431Sdim evalBind(Tmp, Init, Pred, FieldLoc, InitVal, /*isInit=*/true, &PP); 503245431Sdim } 504235633Sdim } else { 505245431Sdim assert(BMI->isBaseInitializer() || BMI->isDelegatingInitializer()); 506245431Sdim // We already did all the work when visiting the CXXConstructExpr. 507245431Sdim } 508221339Sdim 509245431Sdim // Construct PostInitializer nodes whether the state changed or not, 510245431Sdim // so that the diagnostics don't get confused. 511252723Sdim PostInitializer PP(BMI, FieldLoc.getAsRegion(), stackFrame); 512245431Sdim ExplodedNodeSet Dst; 513245431Sdim NodeBuilder Bldr(Tmp, Dst, *currBldrCtx); 514245431Sdim for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I != E; ++I) { 515245431Sdim ExplodedNode *N = *I; 516245431Sdim Bldr.generateNode(PP, N->getState(), N); 517235633Sdim } 518235633Sdim 519235633Sdim // Enqueue the new nodes onto the work list. 520245431Sdim Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx); 521221339Sdim} 522221339Sdim 523221339Sdimvoid ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D, 524235633Sdim ExplodedNode *Pred) { 525235633Sdim ExplodedNodeSet Dst; 526221339Sdim switch (D.getKind()) { 527221339Sdim case CFGElement::AutomaticObjectDtor: 528252723Sdim ProcessAutomaticObjDtor(D.castAs<CFGAutomaticObjDtor>(), Pred, Dst); 529221339Sdim break; 530221339Sdim case CFGElement::BaseDtor: 531252723Sdim ProcessBaseDtor(D.castAs<CFGBaseDtor>(), Pred, Dst); 532221339Sdim break; 533221339Sdim case CFGElement::MemberDtor: 534252723Sdim ProcessMemberDtor(D.castAs<CFGMemberDtor>(), Pred, Dst); 535221339Sdim break; 536221339Sdim case CFGElement::TemporaryDtor: 537252723Sdim ProcessTemporaryDtor(D.castAs<CFGTemporaryDtor>(), Pred, Dst); 538221339Sdim break; 539263509Sdim case CFGElement::DeleteDtor: 540263509Sdim ProcessDeleteDtor(D.castAs<CFGDeleteDtor>(), Pred, Dst); 541263509Sdim break; 542221339Sdim default: 543221339Sdim llvm_unreachable("Unexpected dtor kind."); 544221339Sdim } 545235633Sdim 546235633Sdim // Enqueue the new nodes onto the work list. 547245431Sdim Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx); 548221339Sdim} 549221339Sdim 550235633Sdimvoid ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor Dtor, 551235633Sdim ExplodedNode *Pred, 552235633Sdim ExplodedNodeSet &Dst) { 553235633Sdim const VarDecl *varDecl = Dtor.getVarDecl(); 554221339Sdim QualType varType = varDecl->getType(); 555221339Sdim 556252723Sdim ProgramStateRef state = Pred->getState(); 557252723Sdim SVal dest = state->getLValue(varDecl, Pred->getLocationContext()); 558252723Sdim const MemRegion *Region = dest.castAs<loc::MemRegionVal>().getRegion(); 559252723Sdim 560252723Sdim if (const ReferenceType *refType = varType->getAs<ReferenceType>()) { 561221339Sdim varType = refType->getPointeeType(); 562252723Sdim Region = state->getSVal(Region).getAsRegion(); 563252723Sdim } 564221339Sdim 565252723Sdim VisitCXXDestructor(varType, Region, Dtor.getTriggerStmt(), /*IsBase=*/ false, 566252723Sdim Pred, Dst); 567221339Sdim} 568221339Sdim 569263509Sdimvoid ExprEngine::ProcessDeleteDtor(const CFGDeleteDtor Dtor, 570263509Sdim ExplodedNode *Pred, 571263509Sdim ExplodedNodeSet &Dst) { 572263509Sdim ProgramStateRef State = Pred->getState(); 573263509Sdim const LocationContext *LCtx = Pred->getLocationContext(); 574263509Sdim const CXXDeleteExpr *DE = Dtor.getDeleteExpr(); 575263509Sdim const Stmt *Arg = DE->getArgument(); 576263509Sdim SVal ArgVal = State->getSVal(Arg, LCtx); 577263509Sdim 578263509Sdim // If the argument to delete is known to be a null value, 579263509Sdim // don't run destructor. 580263509Sdim if (State->isNull(ArgVal).isConstrainedTrue()) { 581263509Sdim QualType DTy = DE->getDestroyedType(); 582263509Sdim QualType BTy = getContext().getBaseElementType(DTy); 583263509Sdim const CXXRecordDecl *RD = BTy->getAsCXXRecordDecl(); 584263509Sdim const CXXDestructorDecl *Dtor = RD->getDestructor(); 585263509Sdim 586263509Sdim PostImplicitCall PP(Dtor, DE->getLocStart(), LCtx); 587263509Sdim NodeBuilder Bldr(Pred, Dst, *currBldrCtx); 588263509Sdim Bldr.generateNode(PP, Pred->getState(), Pred); 589263509Sdim return; 590263509Sdim } 591263509Sdim 592263509Sdim VisitCXXDestructor(DE->getDestroyedType(), 593263509Sdim ArgVal.getAsRegion(), 594263509Sdim DE, /*IsBase=*/ false, 595263509Sdim Pred, Dst); 596263509Sdim} 597263509Sdim 598221339Sdimvoid ExprEngine::ProcessBaseDtor(const CFGBaseDtor D, 599245431Sdim ExplodedNode *Pred, ExplodedNodeSet &Dst) { 600245431Sdim const LocationContext *LCtx = Pred->getLocationContext(); 601245431Sdim ProgramStateRef State = Pred->getState(); 602221339Sdim 603245431Sdim const CXXDestructorDecl *CurDtor = cast<CXXDestructorDecl>(LCtx->getDecl()); 604245431Sdim Loc ThisPtr = getSValBuilder().getCXXThis(CurDtor, 605245431Sdim LCtx->getCurrentStackFrame()); 606245431Sdim SVal ThisVal = Pred->getState()->getSVal(ThisPtr); 607245431Sdim 608245431Sdim // Create the base object region. 609252723Sdim const CXXBaseSpecifier *Base = D.getBaseSpecifier(); 610252723Sdim QualType BaseTy = Base->getType(); 611252723Sdim SVal BaseVal = getStoreManager().evalDerivedToBase(ThisVal, BaseTy, 612252723Sdim Base->isVirtual()); 613245431Sdim 614252723Sdim VisitCXXDestructor(BaseTy, BaseVal.castAs<loc::MemRegionVal>().getRegion(), 615252723Sdim CurDtor->getBody(), /*IsBase=*/ true, Pred, Dst); 616245431Sdim} 617245431Sdim 618221339Sdimvoid ExprEngine::ProcessMemberDtor(const CFGMemberDtor D, 619245431Sdim ExplodedNode *Pred, ExplodedNodeSet &Dst) { 620245431Sdim const FieldDecl *Member = D.getFieldDecl(); 621245431Sdim ProgramStateRef State = Pred->getState(); 622245431Sdim const LocationContext *LCtx = Pred->getLocationContext(); 623221339Sdim 624245431Sdim const CXXDestructorDecl *CurDtor = cast<CXXDestructorDecl>(LCtx->getDecl()); 625245431Sdim Loc ThisVal = getSValBuilder().getCXXThis(CurDtor, 626245431Sdim LCtx->getCurrentStackFrame()); 627252723Sdim SVal FieldVal = 628252723Sdim State->getLValue(Member, State->getSVal(ThisVal).castAs<Loc>()); 629245431Sdim 630245431Sdim VisitCXXDestructor(Member->getType(), 631252723Sdim FieldVal.castAs<loc::MemRegionVal>().getRegion(), 632245431Sdim CurDtor->getBody(), /*IsBase=*/false, Pred, Dst); 633245431Sdim} 634245431Sdim 635221339Sdimvoid ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D, 636235633Sdim ExplodedNode *Pred, 637263509Sdim ExplodedNodeSet &Dst) { 638221339Sdim 639263509Sdim QualType varType = D.getBindTemporaryExpr()->getSubExpr()->getType(); 640263509Sdim 641263509Sdim // FIXME: Inlining of temporary destructors is not supported yet anyway, so we 642263509Sdim // just put a NULL region for now. This will need to be changed later. 643263509Sdim VisitCXXDestructor(varType, NULL, D.getBindTemporaryExpr(), 644263509Sdim /*IsBase=*/ false, Pred, Dst); 645263509Sdim} 646263509Sdim 647245431Sdimvoid ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, 648235633Sdim ExplodedNodeSet &DstTop) { 649221339Sdim PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 650221339Sdim S->getLocStart(), 651221339Sdim "Error evaluating statement"); 652235633Sdim ExplodedNodeSet Dst; 653245431Sdim StmtNodeBuilder Bldr(Pred, DstTop, *currBldrCtx); 654221339Sdim 655252723Sdim assert(!isa<Expr>(S) || S == cast<Expr>(S)->IgnoreParens()); 656221339Sdim 657221339Sdim switch (S->getStmtClass()) { 658224145Sdim // C++ and ARC stuff we don't support yet. 659224145Sdim case Expr::ObjCIndirectCopyRestoreExprClass: 660221339Sdim case Stmt::CXXDependentScopeMemberExprClass: 661221339Sdim case Stmt::CXXTryStmtClass: 662221339Sdim case Stmt::CXXTypeidExprClass: 663221339Sdim case Stmt::CXXUuidofExprClass: 664252723Sdim case Stmt::MSPropertyRefExprClass: 665221339Sdim case Stmt::CXXUnresolvedConstructExprClass: 666221339Sdim case Stmt::DependentScopeDeclRefExprClass: 667221339Sdim case Stmt::UnaryTypeTraitExprClass: 668221339Sdim case Stmt::BinaryTypeTraitExprClass: 669235633Sdim case Stmt::TypeTraitExprClass: 670221339Sdim case Stmt::ArrayTypeTraitExprClass: 671221339Sdim case Stmt::ExpressionTraitExprClass: 672221339Sdim case Stmt::UnresolvedLookupExprClass: 673221339Sdim case Stmt::UnresolvedMemberExprClass: 674221339Sdim case Stmt::CXXNoexceptExprClass: 675221339Sdim case Stmt::PackExpansionExprClass: 676221339Sdim case Stmt::SubstNonTypeTemplateParmPackExprClass: 677245431Sdim case Stmt::FunctionParmPackExprClass: 678221339Sdim case Stmt::SEHTryStmtClass: 679221339Sdim case Stmt::SEHExceptStmtClass: 680235633Sdim case Stmt::LambdaExprClass: 681235633Sdim case Stmt::SEHFinallyStmtClass: { 682245431Sdim const ExplodedNode *node = Bldr.generateSink(S, Pred, Pred->getState()); 683245431Sdim Engine.addAbortedBlock(node, currBldrCtx->getBlock()); 684221339Sdim break; 685221339Sdim } 686221339Sdim 687221339Sdim case Stmt::ParenExprClass: 688221339Sdim llvm_unreachable("ParenExprs already handled."); 689221339Sdim case Stmt::GenericSelectionExprClass: 690221339Sdim llvm_unreachable("GenericSelectionExprs already handled."); 691221339Sdim // Cases that should never be evaluated simply because they shouldn't 692221339Sdim // appear in the CFG. 693221339Sdim case Stmt::BreakStmtClass: 694221339Sdim case Stmt::CaseStmtClass: 695221339Sdim case Stmt::CompoundStmtClass: 696221339Sdim case Stmt::ContinueStmtClass: 697226890Sdim case Stmt::CXXForRangeStmtClass: 698221339Sdim case Stmt::DefaultStmtClass: 699221339Sdim case Stmt::DoStmtClass: 700221339Sdim case Stmt::ForStmtClass: 701221339Sdim case Stmt::GotoStmtClass: 702221339Sdim case Stmt::IfStmtClass: 703221339Sdim case Stmt::IndirectGotoStmtClass: 704221339Sdim case Stmt::LabelStmtClass: 705221339Sdim case Stmt::NoStmtClass: 706221339Sdim case Stmt::NullStmtClass: 707221339Sdim case Stmt::SwitchStmtClass: 708221339Sdim case Stmt::WhileStmtClass: 709235633Sdim case Expr::MSDependentExistsStmtClass: 710252723Sdim case Stmt::CapturedStmtClass: 711263509Sdim case Stmt::OMPParallelDirectiveClass: 712221339Sdim llvm_unreachable("Stmt should not be in analyzer evaluation loop"); 713221339Sdim 714245431Sdim case Stmt::ObjCSubscriptRefExprClass: 715245431Sdim case Stmt::ObjCPropertyRefExprClass: 716245431Sdim llvm_unreachable("These are handled by PseudoObjectExpr"); 717245431Sdim 718221339Sdim case Stmt::GNUNullExprClass: { 719224145Sdim // GNU __null is a pointer-width integer, not an actual pointer. 720235633Sdim ProgramStateRef state = Pred->getState(); 721235633Sdim state = state->BindExpr(S, Pred->getLocationContext(), 722235633Sdim svalBuilder.makeIntValWithPtrWidth(0, false)); 723235633Sdim Bldr.generateNode(S, Pred, state); 724221339Sdim break; 725221339Sdim } 726221339Sdim 727221339Sdim case Stmt::ObjCAtSynchronizedStmtClass: 728235633Sdim Bldr.takeNodes(Pred); 729221339Sdim VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S), Pred, Dst); 730235633Sdim Bldr.addNodes(Dst); 731221339Sdim break; 732221339Sdim 733235633Sdim case Stmt::ExprWithCleanupsClass: 734235633Sdim // Handled due to fully linearised CFG. 735224145Sdim break; 736224145Sdim 737221339Sdim // Cases not handled yet; but will handle some day. 738221339Sdim case Stmt::DesignatedInitExprClass: 739221339Sdim case Stmt::ExtVectorElementExprClass: 740221339Sdim case Stmt::ImaginaryLiteralClass: 741221339Sdim case Stmt::ObjCAtCatchStmtClass: 742221339Sdim case Stmt::ObjCAtFinallyStmtClass: 743221339Sdim case Stmt::ObjCAtTryStmtClass: 744224145Sdim case Stmt::ObjCAutoreleasePoolStmtClass: 745221339Sdim case Stmt::ObjCEncodeExprClass: 746221339Sdim case Stmt::ObjCIsaExprClass: 747221339Sdim case Stmt::ObjCProtocolExprClass: 748221339Sdim case Stmt::ObjCSelectorExprClass: 749221339Sdim case Stmt::ParenListExprClass: 750221339Sdim case Stmt::PredefinedExprClass: 751221339Sdim case Stmt::ShuffleVectorExprClass: 752263509Sdim case Stmt::ConvertVectorExprClass: 753221339Sdim case Stmt::VAArgExprClass: 754221339Sdim case Stmt::CUDAKernelCallExprClass: 755221339Sdim case Stmt::OpaqueValueExprClass: 756223017Sdim case Stmt::AsTypeExprClass: 757226890Sdim case Stmt::AtomicExprClass: 758235633Sdim // Fall through. 759221339Sdim 760221339Sdim // Cases we intentionally don't evaluate, since they don't need 761221339Sdim // to be explicitly evaluated. 762221339Sdim case Stmt::AddrLabelExprClass: 763263509Sdim case Stmt::AttributedStmtClass: 764221339Sdim case Stmt::IntegerLiteralClass: 765221339Sdim case Stmt::CharacterLiteralClass: 766245431Sdim case Stmt::ImplicitValueInitExprClass: 767245431Sdim case Stmt::CXXScalarValueInitExprClass: 768221339Sdim case Stmt::CXXBoolLiteralExprClass: 769235633Sdim case Stmt::ObjCBoolLiteralExprClass: 770221339Sdim case Stmt::FloatingLiteralClass: 771221339Sdim case Stmt::SizeOfPackExprClass: 772235633Sdim case Stmt::StringLiteralClass: 773235633Sdim case Stmt::ObjCStringLiteralClass: 774235633Sdim case Stmt::CXXBindTemporaryExprClass: 775263509Sdim case Stmt::CXXPseudoDestructorExprClass: 776245431Sdim case Stmt::SubstNonTypeTemplateParmExprClass: 777235633Sdim case Stmt::CXXNullPtrLiteralExprClass: { 778235633Sdim Bldr.takeNodes(Pred); 779235633Sdim ExplodedNodeSet preVisit; 780235633Sdim getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this); 781235633Sdim getCheckerManager().runCheckersForPostStmt(Dst, preVisit, S, *this); 782235633Sdim Bldr.addNodes(Dst); 783221339Sdim break; 784235633Sdim } 785221339Sdim 786263509Sdim case Stmt::CXXDefaultArgExprClass: 787263509Sdim case Stmt::CXXDefaultInitExprClass: { 788252723Sdim Bldr.takeNodes(Pred); 789252723Sdim ExplodedNodeSet PreVisit; 790252723Sdim getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this); 791252723Sdim 792252723Sdim ExplodedNodeSet Tmp; 793252723Sdim StmtNodeBuilder Bldr2(PreVisit, Tmp, *currBldrCtx); 794252723Sdim 795263509Sdim const Expr *ArgE; 796263509Sdim if (const CXXDefaultArgExpr *DefE = dyn_cast<CXXDefaultArgExpr>(S)) 797263509Sdim ArgE = DefE->getExpr(); 798263509Sdim else if (const CXXDefaultInitExpr *DefE = dyn_cast<CXXDefaultInitExpr>(S)) 799263509Sdim ArgE = DefE->getExpr(); 800263509Sdim else 801263509Sdim llvm_unreachable("unknown constant wrapper kind"); 802252723Sdim 803252723Sdim bool IsTemporary = false; 804252723Sdim if (const MaterializeTemporaryExpr *MTE = 805252723Sdim dyn_cast<MaterializeTemporaryExpr>(ArgE)) { 806252723Sdim ArgE = MTE->GetTemporaryExpr(); 807252723Sdim IsTemporary = true; 808252723Sdim } 809252723Sdim 810252723Sdim Optional<SVal> ConstantVal = svalBuilder.getConstantVal(ArgE); 811252723Sdim if (!ConstantVal) 812252723Sdim ConstantVal = UnknownVal(); 813252723Sdim 814263509Sdim const LocationContext *LCtx = Pred->getLocationContext(); 815252723Sdim for (ExplodedNodeSet::iterator I = PreVisit.begin(), E = PreVisit.end(); 816252723Sdim I != E; ++I) { 817252723Sdim ProgramStateRef State = (*I)->getState(); 818263509Sdim State = State->BindExpr(S, LCtx, *ConstantVal); 819252723Sdim if (IsTemporary) 820263509Sdim State = createTemporaryRegionIfNeeded(State, LCtx, 821263509Sdim cast<Expr>(S), 822263509Sdim cast<Expr>(S)); 823252723Sdim Bldr2.generateNode(S, *I, State); 824252723Sdim } 825252723Sdim 826252723Sdim getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this); 827252723Sdim Bldr.addNodes(Dst); 828252723Sdim break; 829252723Sdim } 830252723Sdim 831263509Sdim // Cases we evaluate as opaque expressions, conjuring a symbol. 832263509Sdim case Stmt::CXXStdInitializerListExprClass: 833235633Sdim case Expr::ObjCArrayLiteralClass: 834245431Sdim case Expr::ObjCDictionaryLiteralClass: 835245431Sdim case Expr::ObjCBoxedExprClass: { 836235633Sdim Bldr.takeNodes(Pred); 837235633Sdim 838235633Sdim ExplodedNodeSet preVisit; 839235633Sdim getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this); 840235633Sdim 841235633Sdim ExplodedNodeSet Tmp; 842245431Sdim StmtNodeBuilder Bldr2(preVisit, Tmp, *currBldrCtx); 843235633Sdim 844245431Sdim const Expr *Ex = cast<Expr>(S); 845245431Sdim QualType resultType = Ex->getType(); 846245431Sdim 847235633Sdim for (ExplodedNodeSet::iterator it = preVisit.begin(), et = preVisit.end(); 848235633Sdim it != et; ++it) { 849235633Sdim ExplodedNode *N = *it; 850235633Sdim const LocationContext *LCtx = N->getLocationContext(); 851245431Sdim SVal result = svalBuilder.conjureSymbolVal(0, Ex, LCtx, resultType, 852245431Sdim currBldrCtx->blockCount()); 853235633Sdim ProgramStateRef state = N->getState()->BindExpr(Ex, LCtx, result); 854235633Sdim Bldr2.generateNode(S, N, state); 855235633Sdim } 856235633Sdim 857235633Sdim getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this); 858235633Sdim Bldr.addNodes(Dst); 859235633Sdim break; 860235633Sdim } 861235633Sdim 862221339Sdim case Stmt::ArraySubscriptExprClass: 863235633Sdim Bldr.takeNodes(Pred); 864221339Sdim VisitLvalArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Pred, Dst); 865235633Sdim Bldr.addNodes(Dst); 866221339Sdim break; 867221339Sdim 868245431Sdim case Stmt::GCCAsmStmtClass: 869235633Sdim Bldr.takeNodes(Pred); 870245431Sdim VisitGCCAsmStmt(cast<GCCAsmStmt>(S), Pred, Dst); 871235633Sdim Bldr.addNodes(Dst); 872221339Sdim break; 873221339Sdim 874245431Sdim case Stmt::MSAsmStmtClass: 875245431Sdim Bldr.takeNodes(Pred); 876245431Sdim VisitMSAsmStmt(cast<MSAsmStmt>(S), Pred, Dst); 877245431Sdim Bldr.addNodes(Dst); 878245431Sdim break; 879245431Sdim 880221339Sdim case Stmt::BlockExprClass: 881235633Sdim Bldr.takeNodes(Pred); 882221339Sdim VisitBlockExpr(cast<BlockExpr>(S), Pred, Dst); 883235633Sdim Bldr.addNodes(Dst); 884221339Sdim break; 885221339Sdim 886221339Sdim case Stmt::BinaryOperatorClass: { 887221339Sdim const BinaryOperator* B = cast<BinaryOperator>(S); 888221339Sdim if (B->isLogicalOp()) { 889235633Sdim Bldr.takeNodes(Pred); 890221339Sdim VisitLogicalExpr(B, Pred, Dst); 891235633Sdim Bldr.addNodes(Dst); 892221339Sdim break; 893221339Sdim } 894221339Sdim else if (B->getOpcode() == BO_Comma) { 895235633Sdim ProgramStateRef state = Pred->getState(); 896235633Sdim Bldr.generateNode(B, Pred, 897235633Sdim state->BindExpr(B, Pred->getLocationContext(), 898235633Sdim state->getSVal(B->getRHS(), 899235633Sdim Pred->getLocationContext()))); 900221339Sdim break; 901221339Sdim } 902221339Sdim 903235633Sdim Bldr.takeNodes(Pred); 904235633Sdim 905245431Sdim if (AMgr.options.eagerlyAssumeBinOpBifurcation && 906221339Sdim (B->isRelationalOp() || B->isEqualityOp())) { 907221339Sdim ExplodedNodeSet Tmp; 908221339Sdim VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Tmp); 909245431Sdim evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, cast<Expr>(S)); 910221339Sdim } 911221339Sdim else 912221339Sdim VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst); 913221339Sdim 914235633Sdim Bldr.addNodes(Dst); 915221339Sdim break; 916221339Sdim } 917221339Sdim 918245431Sdim case Stmt::CXXOperatorCallExprClass: { 919245431Sdim const CXXOperatorCallExpr *OCE = cast<CXXOperatorCallExpr>(S); 920245431Sdim 921245431Sdim // For instance method operators, make sure the 'this' argument has a 922245431Sdim // valid region. 923245431Sdim const Decl *Callee = OCE->getCalleeDecl(); 924245431Sdim if (const CXXMethodDecl *MD = dyn_cast_or_null<CXXMethodDecl>(Callee)) { 925245431Sdim if (MD->isInstance()) { 926245431Sdim ProgramStateRef State = Pred->getState(); 927245431Sdim const LocationContext *LCtx = Pred->getLocationContext(); 928245431Sdim ProgramStateRef NewState = 929245431Sdim createTemporaryRegionIfNeeded(State, LCtx, OCE->getArg(0)); 930252723Sdim if (NewState != State) { 931245431Sdim Pred = Bldr.generateNode(OCE, Pred, NewState, /*Tag=*/0, 932245431Sdim ProgramPoint::PreStmtKind); 933252723Sdim // Did we cache out? 934252723Sdim if (!Pred) 935252723Sdim break; 936252723Sdim } 937245431Sdim } 938245431Sdim } 939245431Sdim // FALLTHROUGH 940245431Sdim } 941221339Sdim case Stmt::CallExprClass: 942235633Sdim case Stmt::CXXMemberCallExprClass: 943235633Sdim case Stmt::UserDefinedLiteralClass: { 944235633Sdim Bldr.takeNodes(Pred); 945221339Sdim VisitCallExpr(cast<CallExpr>(S), Pred, Dst); 946235633Sdim Bldr.addNodes(Dst); 947221339Sdim break; 948221339Sdim } 949235633Sdim 950235633Sdim case Stmt::CXXCatchStmtClass: { 951235633Sdim Bldr.takeNodes(Pred); 952235633Sdim VisitCXXCatchStmt(cast<CXXCatchStmt>(S), Pred, Dst); 953235633Sdim Bldr.addNodes(Dst); 954235633Sdim break; 955235633Sdim } 956221339Sdim 957226890Sdim case Stmt::CXXTemporaryObjectExprClass: 958245431Sdim case Stmt::CXXConstructExprClass: { 959235633Sdim Bldr.takeNodes(Pred); 960245431Sdim VisitCXXConstructExpr(cast<CXXConstructExpr>(S), Pred, Dst); 961235633Sdim Bldr.addNodes(Dst); 962221339Sdim break; 963221339Sdim } 964221339Sdim 965221339Sdim case Stmt::CXXNewExprClass: { 966235633Sdim Bldr.takeNodes(Pred); 967252723Sdim ExplodedNodeSet PostVisit; 968252723Sdim VisitCXXNewExpr(cast<CXXNewExpr>(S), Pred, PostVisit); 969252723Sdim getCheckerManager().runCheckersForPostStmt(Dst, PostVisit, S, *this); 970235633Sdim Bldr.addNodes(Dst); 971221339Sdim break; 972221339Sdim } 973221339Sdim 974221339Sdim case Stmt::CXXDeleteExprClass: { 975235633Sdim Bldr.takeNodes(Pred); 976252723Sdim ExplodedNodeSet PreVisit; 977221339Sdim const CXXDeleteExpr *CDE = cast<CXXDeleteExpr>(S); 978252723Sdim getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this); 979252723Sdim 980252723Sdim for (ExplodedNodeSet::iterator i = PreVisit.begin(), 981252723Sdim e = PreVisit.end(); i != e ; ++i) 982252723Sdim VisitCXXDeleteExpr(CDE, *i, Dst); 983252723Sdim 984235633Sdim Bldr.addNodes(Dst); 985221339Sdim break; 986221339Sdim } 987221339Sdim // FIXME: ChooseExpr is really a constant. We need to fix 988221339Sdim // the CFG do not model them as explicit control-flow. 989221339Sdim 990221339Sdim case Stmt::ChooseExprClass: { // __builtin_choose_expr 991235633Sdim Bldr.takeNodes(Pred); 992226890Sdim const ChooseExpr *C = cast<ChooseExpr>(S); 993221339Sdim VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst); 994235633Sdim Bldr.addNodes(Dst); 995221339Sdim break; 996221339Sdim } 997221339Sdim 998221339Sdim case Stmt::CompoundAssignOperatorClass: 999235633Sdim Bldr.takeNodes(Pred); 1000221339Sdim VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst); 1001235633Sdim Bldr.addNodes(Dst); 1002221339Sdim break; 1003221339Sdim 1004221339Sdim case Stmt::CompoundLiteralExprClass: 1005235633Sdim Bldr.takeNodes(Pred); 1006221339Sdim VisitCompoundLiteralExpr(cast<CompoundLiteralExpr>(S), Pred, Dst); 1007235633Sdim Bldr.addNodes(Dst); 1008221339Sdim break; 1009221339Sdim 1010221339Sdim case Stmt::BinaryConditionalOperatorClass: 1011221339Sdim case Stmt::ConditionalOperatorClass: { // '?' operator 1012235633Sdim Bldr.takeNodes(Pred); 1013221339Sdim const AbstractConditionalOperator *C 1014221339Sdim = cast<AbstractConditionalOperator>(S); 1015221339Sdim VisitGuardedExpr(C, C->getTrueExpr(), C->getFalseExpr(), Pred, Dst); 1016235633Sdim Bldr.addNodes(Dst); 1017221339Sdim break; 1018221339Sdim } 1019221339Sdim 1020221339Sdim case Stmt::CXXThisExprClass: 1021235633Sdim Bldr.takeNodes(Pred); 1022221339Sdim VisitCXXThisExpr(cast<CXXThisExpr>(S), Pred, Dst); 1023235633Sdim Bldr.addNodes(Dst); 1024221339Sdim break; 1025221339Sdim 1026221339Sdim case Stmt::DeclRefExprClass: { 1027235633Sdim Bldr.takeNodes(Pred); 1028221339Sdim const DeclRefExpr *DE = cast<DeclRefExpr>(S); 1029221339Sdim VisitCommonDeclRefExpr(DE, DE->getDecl(), Pred, Dst); 1030235633Sdim Bldr.addNodes(Dst); 1031221339Sdim break; 1032221339Sdim } 1033221339Sdim 1034221339Sdim case Stmt::DeclStmtClass: 1035235633Sdim Bldr.takeNodes(Pred); 1036221339Sdim VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst); 1037235633Sdim Bldr.addNodes(Dst); 1038221339Sdim break; 1039221339Sdim 1040221339Sdim case Stmt::ImplicitCastExprClass: 1041221339Sdim case Stmt::CStyleCastExprClass: 1042221339Sdim case Stmt::CXXStaticCastExprClass: 1043221339Sdim case Stmt::CXXDynamicCastExprClass: 1044221339Sdim case Stmt::CXXReinterpretCastExprClass: 1045221339Sdim case Stmt::CXXConstCastExprClass: 1046224145Sdim case Stmt::CXXFunctionalCastExprClass: 1047224145Sdim case Stmt::ObjCBridgedCastExprClass: { 1048235633Sdim Bldr.takeNodes(Pred); 1049226890Sdim const CastExpr *C = cast<CastExpr>(S); 1050224145Sdim // Handle the previsit checks. 1051224145Sdim ExplodedNodeSet dstPrevisit; 1052224145Sdim getCheckerManager().runCheckersForPreStmt(dstPrevisit, Pred, C, *this); 1053224145Sdim 1054224145Sdim // Handle the expression itself. 1055224145Sdim ExplodedNodeSet dstExpr; 1056224145Sdim for (ExplodedNodeSet::iterator i = dstPrevisit.begin(), 1057224145Sdim e = dstPrevisit.end(); i != e ; ++i) { 1058224145Sdim VisitCast(C, C->getSubExpr(), *i, dstExpr); 1059224145Sdim } 1060224145Sdim 1061224145Sdim // Handle the postvisit checks. 1062224145Sdim getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, C, *this); 1063235633Sdim Bldr.addNodes(Dst); 1064221339Sdim break; 1065221339Sdim } 1066221339Sdim 1067224145Sdim case Expr::MaterializeTemporaryExprClass: { 1068235633Sdim Bldr.takeNodes(Pred); 1069245431Sdim const MaterializeTemporaryExpr *MTE = cast<MaterializeTemporaryExpr>(S); 1070245431Sdim CreateCXXTemporaryObject(MTE, Pred, Dst); 1071235633Sdim Bldr.addNodes(Dst); 1072224145Sdim break; 1073224145Sdim } 1074224145Sdim 1075221339Sdim case Stmt::InitListExprClass: 1076235633Sdim Bldr.takeNodes(Pred); 1077221339Sdim VisitInitListExpr(cast<InitListExpr>(S), Pred, Dst); 1078235633Sdim Bldr.addNodes(Dst); 1079221339Sdim break; 1080221339Sdim 1081221339Sdim case Stmt::MemberExprClass: 1082235633Sdim Bldr.takeNodes(Pred); 1083221339Sdim VisitMemberExpr(cast<MemberExpr>(S), Pred, Dst); 1084235633Sdim Bldr.addNodes(Dst); 1085221339Sdim break; 1086235633Sdim 1087221339Sdim case Stmt::ObjCIvarRefExprClass: 1088235633Sdim Bldr.takeNodes(Pred); 1089221339Sdim VisitLvalObjCIvarRefExpr(cast<ObjCIvarRefExpr>(S), Pred, Dst); 1090235633Sdim Bldr.addNodes(Dst); 1091221339Sdim break; 1092221339Sdim 1093221339Sdim case Stmt::ObjCForCollectionStmtClass: 1094235633Sdim Bldr.takeNodes(Pred); 1095221339Sdim VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S), Pred, Dst); 1096235633Sdim Bldr.addNodes(Dst); 1097221339Sdim break; 1098221339Sdim 1099245431Sdim case Stmt::ObjCMessageExprClass: 1100235633Sdim Bldr.takeNodes(Pred); 1101245431Sdim VisitObjCMessage(cast<ObjCMessageExpr>(S), Pred, Dst); 1102235633Sdim Bldr.addNodes(Dst); 1103221339Sdim break; 1104221339Sdim 1105245431Sdim case Stmt::ObjCAtThrowStmtClass: 1106245431Sdim case Stmt::CXXThrowExprClass: 1107221339Sdim // FIXME: This is not complete. We basically treat @throw as 1108221339Sdim // an abort. 1109245431Sdim Bldr.generateSink(S, Pred, Pred->getState()); 1110221339Sdim break; 1111221339Sdim 1112221339Sdim case Stmt::ReturnStmtClass: 1113235633Sdim Bldr.takeNodes(Pred); 1114221339Sdim VisitReturnStmt(cast<ReturnStmt>(S), Pred, Dst); 1115235633Sdim Bldr.addNodes(Dst); 1116221339Sdim break; 1117221339Sdim 1118221339Sdim case Stmt::OffsetOfExprClass: 1119235633Sdim Bldr.takeNodes(Pred); 1120221339Sdim VisitOffsetOfExpr(cast<OffsetOfExpr>(S), Pred, Dst); 1121235633Sdim Bldr.addNodes(Dst); 1122221339Sdim break; 1123221339Sdim 1124221339Sdim case Stmt::UnaryExprOrTypeTraitExprClass: 1125235633Sdim Bldr.takeNodes(Pred); 1126221339Sdim VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S), 1127221339Sdim Pred, Dst); 1128235633Sdim Bldr.addNodes(Dst); 1129221339Sdim break; 1130221339Sdim 1131221339Sdim case Stmt::StmtExprClass: { 1132226890Sdim const StmtExpr *SE = cast<StmtExpr>(S); 1133221339Sdim 1134221339Sdim if (SE->getSubStmt()->body_empty()) { 1135221339Sdim // Empty statement expression. 1136221339Sdim assert(SE->getType() == getContext().VoidTy 1137221339Sdim && "Empty statement expression must have void type."); 1138221339Sdim break; 1139221339Sdim } 1140221339Sdim 1141226890Sdim if (Expr *LastExpr = dyn_cast<Expr>(*SE->getSubStmt()->body_rbegin())) { 1142235633Sdim ProgramStateRef state = Pred->getState(); 1143235633Sdim Bldr.generateNode(SE, Pred, 1144235633Sdim state->BindExpr(SE, Pred->getLocationContext(), 1145235633Sdim state->getSVal(LastExpr, 1146235633Sdim Pred->getLocationContext()))); 1147221339Sdim } 1148221339Sdim break; 1149221339Sdim } 1150221339Sdim 1151221339Sdim case Stmt::UnaryOperatorClass: { 1152235633Sdim Bldr.takeNodes(Pred); 1153221339Sdim const UnaryOperator *U = cast<UnaryOperator>(S); 1154245431Sdim if (AMgr.options.eagerlyAssumeBinOpBifurcation && (U->getOpcode() == UO_LNot)) { 1155221339Sdim ExplodedNodeSet Tmp; 1156221339Sdim VisitUnaryOperator(U, Pred, Tmp); 1157245431Sdim evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, U); 1158221339Sdim } 1159221339Sdim else 1160221339Sdim VisitUnaryOperator(U, Pred, Dst); 1161235633Sdim Bldr.addNodes(Dst); 1162221339Sdim break; 1163221339Sdim } 1164235633Sdim 1165235633Sdim case Stmt::PseudoObjectExprClass: { 1166235633Sdim Bldr.takeNodes(Pred); 1167235633Sdim ProgramStateRef state = Pred->getState(); 1168235633Sdim const PseudoObjectExpr *PE = cast<PseudoObjectExpr>(S); 1169235633Sdim if (const Expr *Result = PE->getResultExpr()) { 1170235633Sdim SVal V = state->getSVal(Result, Pred->getLocationContext()); 1171235633Sdim Bldr.generateNode(S, Pred, 1172235633Sdim state->BindExpr(S, Pred->getLocationContext(), V)); 1173235633Sdim } 1174235633Sdim else 1175235633Sdim Bldr.generateNode(S, Pred, 1176235633Sdim state->BindExpr(S, Pred->getLocationContext(), 1177235633Sdim UnknownVal())); 1178235633Sdim 1179235633Sdim Bldr.addNodes(Dst); 1180235633Sdim break; 1181235633Sdim } 1182221339Sdim } 1183221339Sdim} 1184221339Sdim 1185235633Sdimbool ExprEngine::replayWithoutInlining(ExplodedNode *N, 1186235633Sdim const LocationContext *CalleeLC) { 1187235633Sdim const StackFrameContext *CalleeSF = CalleeLC->getCurrentStackFrame(); 1188235633Sdim const StackFrameContext *CallerSF = CalleeSF->getParent()->getCurrentStackFrame(); 1189235633Sdim assert(CalleeSF && CallerSF); 1190235633Sdim ExplodedNode *BeforeProcessingCall = 0; 1191245431Sdim const Stmt *CE = CalleeSF->getCallSite(); 1192221339Sdim 1193235633Sdim // Find the first node before we started processing the call expression. 1194235633Sdim while (N) { 1195235633Sdim ProgramPoint L = N->getLocation(); 1196235633Sdim BeforeProcessingCall = N; 1197235633Sdim N = N->pred_empty() ? NULL : *(N->pred_begin()); 1198235633Sdim 1199235633Sdim // Skip the nodes corresponding to the inlined code. 1200235633Sdim if (L.getLocationContext()->getCurrentStackFrame() != CallerSF) 1201235633Sdim continue; 1202235633Sdim // We reached the caller. Find the node right before we started 1203245431Sdim // processing the call. 1204245431Sdim if (L.isPurgeKind()) 1205235633Sdim continue; 1206252723Sdim if (L.getAs<PreImplicitCall>()) 1207245431Sdim continue; 1208252723Sdim if (L.getAs<CallEnter>()) 1209245431Sdim continue; 1210252723Sdim if (Optional<StmtPoint> SP = L.getAs<StmtPoint>()) 1211245431Sdim if (SP->getStmt() == CE) 1212235633Sdim continue; 1213235633Sdim break; 1214235633Sdim } 1215235633Sdim 1216235633Sdim if (!BeforeProcessingCall) 1217235633Sdim return false; 1218235633Sdim 1219235633Sdim // TODO: Clean up the unneeded nodes. 1220235633Sdim 1221235633Sdim // Build an Epsilon node from which we will restart the analyzes. 1222245431Sdim // Note that CE is permitted to be NULL! 1223235633Sdim ProgramPoint NewNodeLoc = 1224235633Sdim EpsilonPoint(BeforeProcessingCall->getLocationContext(), CE); 1225235633Sdim // Add the special flag to GDM to signal retrying with no inlining. 1226235633Sdim // Note, changing the state ensures that we are not going to cache out. 1227235633Sdim ProgramStateRef NewNodeState = BeforeProcessingCall->getState(); 1228252723Sdim NewNodeState = 1229252723Sdim NewNodeState->set<ReplayWithoutInlining>(const_cast<Stmt *>(CE)); 1230235633Sdim 1231235633Sdim // Make the new node a successor of BeforeProcessingCall. 1232235633Sdim bool IsNew = false; 1233235633Sdim ExplodedNode *NewNode = G.getNode(NewNodeLoc, NewNodeState, false, &IsNew); 1234235633Sdim // We cached out at this point. Caching out is common due to us backtracking 1235235633Sdim // from the inlined function, which might spawn several paths. 1236235633Sdim if (!IsNew) 1237235633Sdim return true; 1238235633Sdim 1239235633Sdim NewNode->addPredecessor(BeforeProcessingCall, G); 1240235633Sdim 1241235633Sdim // Add the new node to the work list. 1242235633Sdim Engine.enqueueStmtNode(NewNode, CalleeSF->getCallSiteBlock(), 1243235633Sdim CalleeSF->getIndex()); 1244235633Sdim NumTimesRetriedWithoutInlining++; 1245235633Sdim return true; 1246235633Sdim} 1247235633Sdim 1248235633Sdim/// Block entrance. (Update counters). 1249235633Sdimvoid ExprEngine::processCFGBlockEntrance(const BlockEdge &L, 1250245431Sdim NodeBuilderWithSinks &nodeBuilder, 1251245431Sdim ExplodedNode *Pred) { 1252263509Sdim PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext()); 1253263509Sdim 1254221339Sdim // FIXME: Refactor this into a checker. 1255245431Sdim if (nodeBuilder.getContext().blockCount() >= AMgr.options.maxBlockVisitOnPath) { 1256226890Sdim static SimpleProgramPointTag tag("ExprEngine : Block count exceeded"); 1257235633Sdim const ExplodedNode *Sink = 1258245431Sdim nodeBuilder.generateSink(Pred->getState(), Pred, &tag); 1259221339Sdim 1260235633Sdim // Check if we stopped at the top level function or not. 1261235633Sdim // Root node should have the location context of the top most function. 1262245431Sdim const LocationContext *CalleeLC = Pred->getLocation().getLocationContext(); 1263235633Sdim const LocationContext *CalleeSF = CalleeLC->getCurrentStackFrame(); 1264235633Sdim const LocationContext *RootLC = 1265235633Sdim (*G.roots_begin())->getLocation().getLocationContext(); 1266235633Sdim if (RootLC->getCurrentStackFrame() != CalleeSF) { 1267235633Sdim Engine.FunctionSummaries->markReachedMaxBlockCount(CalleeSF->getDecl()); 1268221339Sdim 1269235633Sdim // Re-run the call evaluation without inlining it, by storing the 1270235633Sdim // no-inlining policy in the state and enqueuing the new work item on 1271235633Sdim // the list. Replay should almost never fail. Use the stats to catch it 1272235633Sdim // if it does. 1273245431Sdim if ((!AMgr.options.NoRetryExhausted && 1274245431Sdim replayWithoutInlining(Pred, CalleeLC))) 1275235633Sdim return; 1276235633Sdim NumMaxBlockCountReachedInInlined++; 1277235633Sdim } else 1278235633Sdim NumMaxBlockCountReached++; 1279235633Sdim 1280235633Sdim // Make sink nodes as exhausted(for stats) only if retry failed. 1281235633Sdim Engine.blocksExhausted.push_back(std::make_pair(L, Sink)); 1282235633Sdim } 1283221339Sdim} 1284221339Sdim 1285221339Sdim//===----------------------------------------------------------------------===// 1286221339Sdim// Branch processing. 1287221339Sdim//===----------------------------------------------------------------------===// 1288221339Sdim 1289221339Sdim/// RecoverCastedSymbol - A helper function for ProcessBranch that is used 1290221339Sdim/// to try to recover some path-sensitivity for casts of symbolic 1291221339Sdim/// integers that promote their values (which are currently not tracked well). 1292221339Sdim/// This function returns the SVal bound to Condition->IgnoreCasts if all the 1293221339Sdim// cast(s) did was sign-extend the original value. 1294226890Sdimstatic SVal RecoverCastedSymbol(ProgramStateManager& StateMgr, 1295235633Sdim ProgramStateRef state, 1296226890Sdim const Stmt *Condition, 1297235633Sdim const LocationContext *LCtx, 1298226890Sdim ASTContext &Ctx) { 1299221339Sdim 1300221339Sdim const Expr *Ex = dyn_cast<Expr>(Condition); 1301221339Sdim if (!Ex) 1302221339Sdim return UnknownVal(); 1303221339Sdim 1304221339Sdim uint64_t bits = 0; 1305221339Sdim bool bitsInit = false; 1306221339Sdim 1307221339Sdim while (const CastExpr *CE = dyn_cast<CastExpr>(Ex)) { 1308221339Sdim QualType T = CE->getType(); 1309221339Sdim 1310252723Sdim if (!T->isIntegralOrEnumerationType()) 1311221339Sdim return UnknownVal(); 1312221339Sdim 1313221339Sdim uint64_t newBits = Ctx.getTypeSize(T); 1314221339Sdim if (!bitsInit || newBits < bits) { 1315221339Sdim bitsInit = true; 1316221339Sdim bits = newBits; 1317221339Sdim } 1318221339Sdim 1319221339Sdim Ex = CE->getSubExpr(); 1320221339Sdim } 1321221339Sdim 1322221339Sdim // We reached a non-cast. Is it a symbolic value? 1323221339Sdim QualType T = Ex->getType(); 1324221339Sdim 1325252723Sdim if (!bitsInit || !T->isIntegralOrEnumerationType() || 1326252723Sdim Ctx.getTypeSize(T) > bits) 1327221339Sdim return UnknownVal(); 1328221339Sdim 1329235633Sdim return state->getSVal(Ex, LCtx); 1330221339Sdim} 1331221339Sdim 1332245431Sdimstatic const Stmt *ResolveCondition(const Stmt *Condition, 1333245431Sdim const CFGBlock *B) { 1334245431Sdim if (const Expr *Ex = dyn_cast<Expr>(Condition)) 1335245431Sdim Condition = Ex->IgnoreParens(); 1336245431Sdim 1337245431Sdim const BinaryOperator *BO = dyn_cast<BinaryOperator>(Condition); 1338245431Sdim if (!BO || !BO->isLogicalOp()) 1339245431Sdim return Condition; 1340245431Sdim 1341245431Sdim // For logical operations, we still have the case where some branches 1342245431Sdim // use the traditional "merge" approach and others sink the branch 1343245431Sdim // directly into the basic blocks representing the logical operation. 1344245431Sdim // We need to distinguish between those two cases here. 1345245431Sdim 1346245431Sdim // The invariants are still shifting, but it is possible that the 1347245431Sdim // last element in a CFGBlock is not a CFGStmt. Look for the last 1348245431Sdim // CFGStmt as the value of the condition. 1349245431Sdim CFGBlock::const_reverse_iterator I = B->rbegin(), E = B->rend(); 1350245431Sdim for (; I != E; ++I) { 1351245431Sdim CFGElement Elem = *I; 1352252723Sdim Optional<CFGStmt> CS = Elem.getAs<CFGStmt>(); 1353245431Sdim if (!CS) 1354245431Sdim continue; 1355245431Sdim if (CS->getStmt() != Condition) 1356245431Sdim break; 1357245431Sdim return Condition; 1358245431Sdim } 1359245431Sdim 1360245431Sdim assert(I != E); 1361245431Sdim 1362245431Sdim while (Condition) { 1363245431Sdim BO = dyn_cast<BinaryOperator>(Condition); 1364245431Sdim if (!BO || !BO->isLogicalOp()) 1365245431Sdim return Condition; 1366245431Sdim Condition = BO->getRHS()->IgnoreParens(); 1367245431Sdim } 1368245431Sdim llvm_unreachable("could not resolve condition"); 1369245431Sdim} 1370245431Sdim 1371226890Sdimvoid ExprEngine::processBranch(const Stmt *Condition, const Stmt *Term, 1372235633Sdim NodeBuilderContext& BldCtx, 1373235633Sdim ExplodedNode *Pred, 1374235633Sdim ExplodedNodeSet &Dst, 1375235633Sdim const CFGBlock *DstT, 1376235633Sdim const CFGBlock *DstF) { 1377263509Sdim const LocationContext *LCtx = Pred->getLocationContext(); 1378263509Sdim PrettyStackTraceLocationContext StackCrashInfo(LCtx); 1379245431Sdim currBldrCtx = &BldCtx; 1380221339Sdim 1381221339Sdim // Check for NULL conditions; e.g. "for(;;)" 1382221339Sdim if (!Condition) { 1383235633Sdim BranchNodeBuilder NullCondBldr(Pred, Dst, BldCtx, DstT, DstF); 1384235633Sdim NullCondBldr.markInfeasible(false); 1385235633Sdim NullCondBldr.generateNode(Pred->getState(), true, Pred); 1386221339Sdim return; 1387221339Sdim } 1388221339Sdim 1389245431Sdim 1390245431Sdim if (const Expr *Ex = dyn_cast<Expr>(Condition)) 1391245431Sdim Condition = Ex->IgnoreParens(); 1392245431Sdim 1393245431Sdim Condition = ResolveCondition(Condition, BldCtx.getBlock()); 1394221339Sdim PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 1395221339Sdim Condition->getLocStart(), 1396221339Sdim "Error evaluating branch"); 1397221339Sdim 1398235633Sdim ExplodedNodeSet CheckersOutSet; 1399235633Sdim getCheckerManager().runCheckersForBranchCondition(Condition, CheckersOutSet, 1400235633Sdim Pred, *this); 1401235633Sdim // We generated only sinks. 1402235633Sdim if (CheckersOutSet.empty()) 1403221339Sdim return; 1404221339Sdim 1405235633Sdim BranchNodeBuilder builder(CheckersOutSet, Dst, BldCtx, DstT, DstF); 1406235633Sdim for (NodeBuilder::iterator I = CheckersOutSet.begin(), 1407235633Sdim E = CheckersOutSet.end(); E != I; ++I) { 1408235633Sdim ExplodedNode *PredI = *I; 1409221339Sdim 1410235633Sdim if (PredI->isSink()) 1411235633Sdim continue; 1412221339Sdim 1413252723Sdim ProgramStateRef PrevState = PredI->getState(); 1414252723Sdim SVal X = PrevState->getSVal(Condition, PredI->getLocationContext()); 1415235633Sdim 1416235633Sdim if (X.isUnknownOrUndef()) { 1417235633Sdim // Give it a chance to recover from unknown. 1418235633Sdim if (const Expr *Ex = dyn_cast<Expr>(Condition)) { 1419252723Sdim if (Ex->getType()->isIntegralOrEnumerationType()) { 1420235633Sdim // Try to recover some path-sensitivity. Right now casts of symbolic 1421235633Sdim // integers that promote their values are currently not tracked well. 1422235633Sdim // If 'Condition' is such an expression, try and recover the 1423235633Sdim // underlying value and use that instead. 1424235633Sdim SVal recovered = RecoverCastedSymbol(getStateManager(), 1425235633Sdim PrevState, Condition, 1426252723Sdim PredI->getLocationContext(), 1427235633Sdim getContext()); 1428235633Sdim 1429235633Sdim if (!recovered.isUnknown()) { 1430235633Sdim X = recovered; 1431235633Sdim } 1432221339Sdim } 1433221339Sdim } 1434221339Sdim } 1435235633Sdim 1436221339Sdim // If the condition is still unknown, give up. 1437221339Sdim if (X.isUnknownOrUndef()) { 1438245431Sdim builder.generateNode(PrevState, true, PredI); 1439245431Sdim builder.generateNode(PrevState, false, PredI); 1440235633Sdim continue; 1441221339Sdim } 1442221339Sdim 1443252723Sdim DefinedSVal V = X.castAs<DefinedSVal>(); 1444221339Sdim 1445252723Sdim ProgramStateRef StTrue, StFalse; 1446252723Sdim tie(StTrue, StFalse) = PrevState->assume(V); 1447252723Sdim 1448235633Sdim // Process the true branch. 1449235633Sdim if (builder.isFeasible(true)) { 1450252723Sdim if (StTrue) 1451252723Sdim builder.generateNode(StTrue, true, PredI); 1452235633Sdim else 1453235633Sdim builder.markInfeasible(true); 1454235633Sdim } 1455221339Sdim 1456235633Sdim // Process the false branch. 1457235633Sdim if (builder.isFeasible(false)) { 1458252723Sdim if (StFalse) 1459252723Sdim builder.generateNode(StFalse, false, PredI); 1460235633Sdim else 1461235633Sdim builder.markInfeasible(false); 1462235633Sdim } 1463221339Sdim } 1464245431Sdim currBldrCtx = 0; 1465221339Sdim} 1466221339Sdim 1467252723Sdim/// The GDM component containing the set of global variables which have been 1468252723Sdim/// previously initialized with explicit initializers. 1469252723SdimREGISTER_TRAIT_WITH_PROGRAMSTATE(InitializedGlobalsSet, 1470252723Sdim llvm::ImmutableSet<const VarDecl *>) 1471252723Sdim 1472252723Sdimvoid ExprEngine::processStaticInitializer(const DeclStmt *DS, 1473252723Sdim NodeBuilderContext &BuilderCtx, 1474252723Sdim ExplodedNode *Pred, 1475252723Sdim clang::ento::ExplodedNodeSet &Dst, 1476252723Sdim const CFGBlock *DstT, 1477252723Sdim const CFGBlock *DstF) { 1478263509Sdim PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext()); 1479252723Sdim currBldrCtx = &BuilderCtx; 1480252723Sdim 1481252723Sdim const VarDecl *VD = cast<VarDecl>(DS->getSingleDecl()); 1482252723Sdim ProgramStateRef state = Pred->getState(); 1483252723Sdim bool initHasRun = state->contains<InitializedGlobalsSet>(VD); 1484252723Sdim BranchNodeBuilder builder(Pred, Dst, BuilderCtx, DstT, DstF); 1485252723Sdim 1486252723Sdim if (!initHasRun) { 1487252723Sdim state = state->add<InitializedGlobalsSet>(VD); 1488252723Sdim } 1489252723Sdim 1490252723Sdim builder.generateNode(state, initHasRun, Pred); 1491252723Sdim builder.markInfeasible(!initHasRun); 1492252723Sdim 1493252723Sdim currBldrCtx = 0; 1494252723Sdim} 1495252723Sdim 1496221339Sdim/// processIndirectGoto - Called by CoreEngine. Used to generate successor 1497221339Sdim/// nodes by processing the 'effects' of a computed goto jump. 1498221339Sdimvoid ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) { 1499221339Sdim 1500235633Sdim ProgramStateRef state = builder.getState(); 1501235633Sdim SVal V = state->getSVal(builder.getTarget(), builder.getLocationContext()); 1502221339Sdim 1503221339Sdim // Three possibilities: 1504221339Sdim // 1505221339Sdim // (1) We know the computed label. 1506221339Sdim // (2) The label is NULL (or some other constant), or Undefined. 1507221339Sdim // (3) We have no clue about the label. Dispatch to all targets. 1508221339Sdim // 1509221339Sdim 1510221339Sdim typedef IndirectGotoNodeBuilder::iterator iterator; 1511221339Sdim 1512252723Sdim if (Optional<loc::GotoLabel> LV = V.getAs<loc::GotoLabel>()) { 1513252723Sdim const LabelDecl *L = LV->getLabel(); 1514221339Sdim 1515221339Sdim for (iterator I = builder.begin(), E = builder.end(); I != E; ++I) { 1516221339Sdim if (I.getLabel() == L) { 1517221339Sdim builder.generateNode(I, state); 1518221339Sdim return; 1519221339Sdim } 1520221339Sdim } 1521221339Sdim 1522226890Sdim llvm_unreachable("No block with label."); 1523221339Sdim } 1524221339Sdim 1525252723Sdim if (V.getAs<loc::ConcreteInt>() || V.getAs<UndefinedVal>()) { 1526221339Sdim // Dispatch to the first target and mark it as a sink. 1527221339Sdim //ExplodedNode* N = builder.generateNode(builder.begin(), state, true); 1528221339Sdim // FIXME: add checker visit. 1529221339Sdim // UndefBranches.insert(N); 1530221339Sdim return; 1531221339Sdim } 1532221339Sdim 1533221339Sdim // This is really a catch-all. We don't support symbolics yet. 1534221339Sdim // FIXME: Implement dispatch for symbolic pointers. 1535221339Sdim 1536221339Sdim for (iterator I=builder.begin(), E=builder.end(); I != E; ++I) 1537221339Sdim builder.generateNode(I, state); 1538221339Sdim} 1539221339Sdim 1540221339Sdim/// ProcessEndPath - Called by CoreEngine. Used to generate end-of-path 1541221339Sdim/// nodes when the control reaches the end of a function. 1542245431Sdimvoid ExprEngine::processEndOfFunction(NodeBuilderContext& BC, 1543245431Sdim ExplodedNode *Pred) { 1544263509Sdim PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext()); 1545245431Sdim StateMgr.EndPath(Pred->getState()); 1546245431Sdim 1547235633Sdim ExplodedNodeSet Dst; 1548245431Sdim if (Pred->getLocationContext()->inTopFrame()) { 1549245431Sdim // Remove dead symbols. 1550245431Sdim ExplodedNodeSet AfterRemovedDead; 1551245431Sdim removeDeadOnEndOfFunction(BC, Pred, AfterRemovedDead); 1552245431Sdim 1553245431Sdim // Notify checkers. 1554245431Sdim for (ExplodedNodeSet::iterator I = AfterRemovedDead.begin(), 1555245431Sdim E = AfterRemovedDead.end(); I != E; ++I) { 1556252723Sdim getCheckerManager().runCheckersForEndFunction(BC, Dst, *I, *this); 1557245431Sdim } 1558245431Sdim } else { 1559252723Sdim getCheckerManager().runCheckersForEndFunction(BC, Dst, Pred, *this); 1560245431Sdim } 1561245431Sdim 1562235633Sdim Engine.enqueueEndOfFunction(Dst); 1563221339Sdim} 1564221339Sdim 1565221339Sdim/// ProcessSwitch - Called by CoreEngine. Used to generate successor 1566221339Sdim/// nodes by processing the 'effects' of a switch statement. 1567221339Sdimvoid ExprEngine::processSwitch(SwitchNodeBuilder& builder) { 1568221339Sdim typedef SwitchNodeBuilder::iterator iterator; 1569235633Sdim ProgramStateRef state = builder.getState(); 1570226890Sdim const Expr *CondE = builder.getCondition(); 1571235633Sdim SVal CondV_untested = state->getSVal(CondE, builder.getLocationContext()); 1572221339Sdim 1573221339Sdim if (CondV_untested.isUndef()) { 1574221339Sdim //ExplodedNode* N = builder.generateDefaultCaseNode(state, true); 1575221339Sdim // FIXME: add checker 1576221339Sdim //UndefBranches.insert(N); 1577221339Sdim 1578221339Sdim return; 1579221339Sdim } 1580252723Sdim DefinedOrUnknownSVal CondV = CondV_untested.castAs<DefinedOrUnknownSVal>(); 1581221339Sdim 1582235633Sdim ProgramStateRef DefaultSt = state; 1583221339Sdim 1584221339Sdim iterator I = builder.begin(), EI = builder.end(); 1585221339Sdim bool defaultIsFeasible = I == EI; 1586221339Sdim 1587221339Sdim for ( ; I != EI; ++I) { 1588221339Sdim // Successor may be pruned out during CFG construction. 1589221339Sdim if (!I.getBlock()) 1590221339Sdim continue; 1591221339Sdim 1592226890Sdim const CaseStmt *Case = I.getCase(); 1593221339Sdim 1594221339Sdim // Evaluate the LHS of the case value. 1595226890Sdim llvm::APSInt V1 = Case->getLHS()->EvaluateKnownConstInt(getContext()); 1596226890Sdim assert(V1.getBitWidth() == getContext().getTypeSize(CondE->getType())); 1597221339Sdim 1598221339Sdim // Get the RHS of the case, if it exists. 1599226890Sdim llvm::APSInt V2; 1600226890Sdim if (const Expr *E = Case->getRHS()) 1601226890Sdim V2 = E->EvaluateKnownConstInt(getContext()); 1602221339Sdim else 1603221339Sdim V2 = V1; 1604221339Sdim 1605221339Sdim // FIXME: Eventually we should replace the logic below with a range 1606221339Sdim // comparison, rather than concretize the values within the range. 1607221339Sdim // This should be easy once we have "ranges" for NonLVals. 1608221339Sdim 1609221339Sdim do { 1610226890Sdim nonloc::ConcreteInt CaseVal(getBasicVals().getValue(V1)); 1611221339Sdim DefinedOrUnknownSVal Res = svalBuilder.evalEQ(DefaultSt ? DefaultSt : state, 1612221339Sdim CondV, CaseVal); 1613221339Sdim 1614221339Sdim // Now "assume" that the case matches. 1615235633Sdim if (ProgramStateRef stateNew = state->assume(Res, true)) { 1616221339Sdim builder.generateCaseStmtNode(I, stateNew); 1617221339Sdim 1618221339Sdim // If CondV evaluates to a constant, then we know that this 1619221339Sdim // is the *only* case that we can take, so stop evaluating the 1620221339Sdim // others. 1621252723Sdim if (CondV.getAs<nonloc::ConcreteInt>()) 1622221339Sdim return; 1623221339Sdim } 1624221339Sdim 1625221339Sdim // Now "assume" that the case doesn't match. Add this state 1626221339Sdim // to the default state (if it is feasible). 1627221339Sdim if (DefaultSt) { 1628235633Sdim if (ProgramStateRef stateNew = DefaultSt->assume(Res, false)) { 1629221339Sdim defaultIsFeasible = true; 1630221339Sdim DefaultSt = stateNew; 1631221339Sdim } 1632221339Sdim else { 1633221339Sdim defaultIsFeasible = false; 1634221339Sdim DefaultSt = NULL; 1635221339Sdim } 1636221339Sdim } 1637221339Sdim 1638221339Sdim // Concretize the next value in the range. 1639226890Sdim if (V1 == V2) 1640221339Sdim break; 1641221339Sdim 1642226890Sdim ++V1; 1643226890Sdim assert (V1 <= V2); 1644221339Sdim 1645221339Sdim } while (true); 1646221339Sdim } 1647221339Sdim 1648221339Sdim if (!defaultIsFeasible) 1649221339Sdim return; 1650221339Sdim 1651221339Sdim // If we have switch(enum value), the default branch is not 1652221339Sdim // feasible if all of the enum constants not covered by 'case:' statements 1653221339Sdim // are not feasible values for the switch condition. 1654221339Sdim // 1655221339Sdim // Note that this isn't as accurate as it could be. Even if there isn't 1656221339Sdim // a case for a particular enum value as long as that enum value isn't 1657221339Sdim // feasible then it shouldn't be considered for making 'default:' reachable. 1658221339Sdim const SwitchStmt *SS = builder.getSwitch(); 1659221339Sdim const Expr *CondExpr = SS->getCond()->IgnoreParenImpCasts(); 1660221339Sdim if (CondExpr->getType()->getAs<EnumType>()) { 1661221339Sdim if (SS->isAllEnumCasesCovered()) 1662221339Sdim return; 1663221339Sdim } 1664221339Sdim 1665221339Sdim builder.generateDefaultCaseNode(DefaultSt); 1666221339Sdim} 1667221339Sdim 1668221339Sdim//===----------------------------------------------------------------------===// 1669221339Sdim// Transfer functions: Loads and stores. 1670221339Sdim//===----------------------------------------------------------------------===// 1671221339Sdim 1672221339Sdimvoid ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D, 1673221339Sdim ExplodedNode *Pred, 1674221339Sdim ExplodedNodeSet &Dst) { 1675245431Sdim StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); 1676221339Sdim 1677235633Sdim ProgramStateRef state = Pred->getState(); 1678235633Sdim const LocationContext *LCtx = Pred->getLocationContext(); 1679235633Sdim 1680226890Sdim if (const VarDecl *VD = dyn_cast<VarDecl>(D)) { 1681263509Sdim // C permits "extern void v", and if you cast the address to a valid type, 1682263509Sdim // you can even do things with it. We simply pretend 1683263509Sdim assert(Ex->isGLValue() || VD->getType()->isVoidType()); 1684221339Sdim SVal V = state->getLValue(VD, Pred->getLocationContext()); 1685221339Sdim 1686221339Sdim // For references, the 'lvalue' is the pointer address stored in the 1687221339Sdim // reference region. 1688221339Sdim if (VD->getType()->isReferenceType()) { 1689221339Sdim if (const MemRegion *R = V.getAsRegion()) 1690221339Sdim V = state->getSVal(R); 1691221339Sdim else 1692221339Sdim V = UnknownVal(); 1693221339Sdim } 1694221339Sdim 1695245431Sdim Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), 0, 1696235633Sdim ProgramPoint::PostLValueKind); 1697221339Sdim return; 1698221339Sdim } 1699226890Sdim if (const EnumConstantDecl *ED = dyn_cast<EnumConstantDecl>(D)) { 1700245431Sdim assert(!Ex->isGLValue()); 1701221339Sdim SVal V = svalBuilder.makeIntVal(ED->getInitVal()); 1702235633Sdim Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V)); 1703221339Sdim return; 1704221339Sdim } 1705226890Sdim if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 1706221339Sdim SVal V = svalBuilder.getFunctionPointer(FD); 1707245431Sdim Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), 0, 1708235633Sdim ProgramPoint::PostLValueKind); 1709221339Sdim return; 1710221339Sdim } 1711235633Sdim if (isa<FieldDecl>(D)) { 1712245431Sdim // FIXME: Compute lvalue of field pointers-to-member. 1713245431Sdim // Right now we just use a non-null void pointer, so that it gives proper 1714245431Sdim // results in boolean contexts. 1715245431Sdim SVal V = svalBuilder.conjureSymbolVal(Ex, LCtx, getContext().VoidPtrTy, 1716245431Sdim currBldrCtx->blockCount()); 1717252723Sdim state = state->assume(V.castAs<DefinedOrUnknownSVal>(), true); 1718245431Sdim Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), 0, 1719245431Sdim ProgramPoint::PostLValueKind); 1720235633Sdim return; 1721235633Sdim } 1722235633Sdim 1723245431Sdim llvm_unreachable("Support for this Decl not implemented."); 1724221339Sdim} 1725221339Sdim 1726221339Sdim/// VisitArraySubscriptExpr - Transfer function for array accesses 1727226890Sdimvoid ExprEngine::VisitLvalArraySubscriptExpr(const ArraySubscriptExpr *A, 1728226890Sdim ExplodedNode *Pred, 1729226890Sdim ExplodedNodeSet &Dst){ 1730221339Sdim 1731226890Sdim const Expr *Base = A->getBase()->IgnoreParens(); 1732226890Sdim const Expr *Idx = A->getIdx()->IgnoreParens(); 1733221339Sdim 1734221339Sdim 1735226890Sdim ExplodedNodeSet checkerPreStmt; 1736226890Sdim getCheckerManager().runCheckersForPreStmt(checkerPreStmt, Pred, A, *this); 1737221339Sdim 1738245431Sdim StmtNodeBuilder Bldr(checkerPreStmt, Dst, *currBldrCtx); 1739235633Sdim 1740226890Sdim for (ExplodedNodeSet::iterator it = checkerPreStmt.begin(), 1741226890Sdim ei = checkerPreStmt.end(); it != ei; ++it) { 1742235633Sdim const LocationContext *LCtx = (*it)->getLocationContext(); 1743235633Sdim ProgramStateRef state = (*it)->getState(); 1744235633Sdim SVal V = state->getLValue(A->getType(), 1745235633Sdim state->getSVal(Idx, LCtx), 1746235633Sdim state->getSVal(Base, LCtx)); 1747245431Sdim assert(A->isGLValue()); 1748245431Sdim Bldr.generateNode(A, *it, state->BindExpr(A, LCtx, V), 0, 1749245431Sdim ProgramPoint::PostLValueKind); 1750221339Sdim } 1751221339Sdim} 1752221339Sdim 1753221339Sdim/// VisitMemberExpr - Transfer function for member expressions. 1754226890Sdimvoid ExprEngine::VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred, 1755235633Sdim ExplodedNodeSet &TopDst) { 1756221339Sdim 1757245431Sdim StmtNodeBuilder Bldr(Pred, TopDst, *currBldrCtx); 1758235633Sdim ExplodedNodeSet Dst; 1759245431Sdim ValueDecl *Member = M->getMemberDecl(); 1760245431Sdim 1761245431Sdim // Handle static member variables and enum constants accessed via 1762245431Sdim // member syntax. 1763245431Sdim if (isa<VarDecl>(Member) || isa<EnumConstantDecl>(Member)) { 1764235633Sdim Bldr.takeNodes(Pred); 1765245431Sdim VisitCommonDeclRefExpr(M, Member, Pred, Dst); 1766235633Sdim Bldr.addNodes(Dst); 1767226890Sdim return; 1768226890Sdim } 1769221339Sdim 1770235633Sdim ProgramStateRef state = Pred->getState(); 1771235633Sdim const LocationContext *LCtx = Pred->getLocationContext(); 1772245431Sdim Expr *BaseExpr = M->getBase(); 1773245431Sdim 1774245431Sdim // Handle C++ method calls. 1775245431Sdim if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(Member)) { 1776245431Sdim if (MD->isInstance()) 1777245431Sdim state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr); 1778245431Sdim 1779245431Sdim SVal MDVal = svalBuilder.getFunctionPointer(MD); 1780245431Sdim state = state->BindExpr(M, LCtx, MDVal); 1781245431Sdim 1782245431Sdim Bldr.generateNode(M, Pred, state); 1783226890Sdim return; 1784226890Sdim } 1785221339Sdim 1786245431Sdim // Handle regular struct fields / member variables. 1787245431Sdim state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr); 1788245431Sdim SVal baseExprVal = state->getSVal(BaseExpr, LCtx); 1789221339Sdim 1790245431Sdim FieldDecl *field = cast<FieldDecl>(Member); 1791226890Sdim SVal L = state->getLValue(field, baseExprVal); 1792263509Sdim 1793263509Sdim if (M->isGLValue() || M->getType()->isArrayType()) { 1794263509Sdim 1795263509Sdim // We special case rvalue of array type because the analyzer cannot reason 1796263509Sdim // about it, since we expect all regions to be wrapped in Locs. So we will 1797263509Sdim // treat these as lvalues assuming that they will decay to pointers as soon 1798263509Sdim // as they are used. 1799263509Sdim if (!M->isGLValue()) { 1800263509Sdim assert(M->getType()->isArrayType()); 1801263509Sdim const ImplicitCastExpr *PE = 1802263509Sdim dyn_cast<ImplicitCastExpr>(Pred->getParentMap().getParent(M)); 1803263509Sdim if (!PE || PE->getCastKind() != CK_ArrayToPointerDecay) { 1804263509Sdim assert(false && 1805263509Sdim "We assume that array is always wrapped in ArrayToPointerDecay"); 1806263509Sdim L = UnknownVal(); 1807263509Sdim } 1808263509Sdim } 1809263509Sdim 1810245431Sdim if (field->getType()->isReferenceType()) { 1811245431Sdim if (const MemRegion *R = L.getAsRegion()) 1812245431Sdim L = state->getSVal(R); 1813245431Sdim else 1814245431Sdim L = UnknownVal(); 1815245431Sdim } 1816245431Sdim 1817245431Sdim Bldr.generateNode(M, Pred, state->BindExpr(M, LCtx, L), 0, 1818235633Sdim ProgramPoint::PostLValueKind); 1819245431Sdim } else { 1820235633Sdim Bldr.takeNodes(Pred); 1821235633Sdim evalLoad(Dst, M, M, Pred, state, L); 1822235633Sdim Bldr.addNodes(Dst); 1823235633Sdim } 1824221339Sdim} 1825221339Sdim 1826252723Sdimnamespace { 1827252723Sdimclass CollectReachableSymbolsCallback : public SymbolVisitor { 1828252723Sdim InvalidatedSymbols Symbols; 1829252723Sdimpublic: 1830252723Sdim CollectReachableSymbolsCallback(ProgramStateRef State) {} 1831252723Sdim const InvalidatedSymbols &getSymbols() const { return Symbols; } 1832252723Sdim 1833252723Sdim bool VisitSymbol(SymbolRef Sym) { 1834252723Sdim Symbols.insert(Sym); 1835252723Sdim return true; 1836252723Sdim } 1837252723Sdim}; 1838252723Sdim} // end anonymous namespace 1839252723Sdim 1840252723Sdim// A value escapes in three possible cases: 1841252723Sdim// (1) We are binding to something that is not a memory region. 1842252723Sdim// (2) We are binding to a MemrRegion that does not have stack storage. 1843252723Sdim// (3) We are binding to a MemRegion with stack storage that the store 1844252723Sdim// does not understand. 1845252723SdimProgramStateRef ExprEngine::processPointerEscapedOnBind(ProgramStateRef State, 1846252723Sdim SVal Loc, SVal Val) { 1847252723Sdim // Are we storing to something that causes the value to "escape"? 1848252723Sdim bool escapes = true; 1849252723Sdim 1850252723Sdim // TODO: Move to StoreManager. 1851252723Sdim if (Optional<loc::MemRegionVal> regionLoc = Loc.getAs<loc::MemRegionVal>()) { 1852252723Sdim escapes = !regionLoc->getRegion()->hasStackStorage(); 1853252723Sdim 1854252723Sdim if (!escapes) { 1855252723Sdim // To test (3), generate a new state with the binding added. If it is 1856252723Sdim // the same state, then it escapes (since the store cannot represent 1857252723Sdim // the binding). 1858252723Sdim // Do this only if we know that the store is not supposed to generate the 1859252723Sdim // same state. 1860252723Sdim SVal StoredVal = State->getSVal(regionLoc->getRegion()); 1861252723Sdim if (StoredVal != Val) 1862252723Sdim escapes = (State == (State->bindLoc(*regionLoc, Val))); 1863252723Sdim } 1864252723Sdim } 1865252723Sdim 1866252723Sdim // If our store can represent the binding and we aren't storing to something 1867252723Sdim // that doesn't have local storage then just return and have the simulation 1868252723Sdim // state continue as is. 1869252723Sdim if (!escapes) 1870252723Sdim return State; 1871252723Sdim 1872252723Sdim // Otherwise, find all symbols referenced by 'val' that we are tracking 1873252723Sdim // and stop tracking them. 1874252723Sdim CollectReachableSymbolsCallback Scanner = 1875252723Sdim State->scanReachableSymbols<CollectReachableSymbolsCallback>(Val); 1876252723Sdim const InvalidatedSymbols &EscapedSymbols = Scanner.getSymbols(); 1877252723Sdim State = getCheckerManager().runCheckersForPointerEscape(State, 1878252723Sdim EscapedSymbols, 1879252723Sdim /*CallEvent*/ 0, 1880263509Sdim PSK_EscapeOnBind, 1881263509Sdim 0); 1882252723Sdim 1883252723Sdim return State; 1884252723Sdim} 1885252723Sdim 1886252723SdimProgramStateRef 1887252723SdimExprEngine::notifyCheckersOfPointerEscape(ProgramStateRef State, 1888252723Sdim const InvalidatedSymbols *Invalidated, 1889252723Sdim ArrayRef<const MemRegion *> ExplicitRegions, 1890252723Sdim ArrayRef<const MemRegion *> Regions, 1891252723Sdim const CallEvent *Call, 1892263509Sdim RegionAndSymbolInvalidationTraits &ITraits) { 1893252723Sdim 1894252723Sdim if (!Invalidated || Invalidated->empty()) 1895252723Sdim return State; 1896252723Sdim 1897252723Sdim if (!Call) 1898252723Sdim return getCheckerManager().runCheckersForPointerEscape(State, 1899252723Sdim *Invalidated, 1900252723Sdim 0, 1901252723Sdim PSK_EscapeOther, 1902263509Sdim &ITraits); 1903252723Sdim 1904252723Sdim // If the symbols were invalidated by a call, we want to find out which ones 1905252723Sdim // were invalidated directly due to being arguments to the call. 1906252723Sdim InvalidatedSymbols SymbolsDirectlyInvalidated; 1907252723Sdim for (ArrayRef<const MemRegion *>::iterator I = ExplicitRegions.begin(), 1908252723Sdim E = ExplicitRegions.end(); I != E; ++I) { 1909252723Sdim if (const SymbolicRegion *R = (*I)->StripCasts()->getAs<SymbolicRegion>()) 1910252723Sdim SymbolsDirectlyInvalidated.insert(R->getSymbol()); 1911252723Sdim } 1912252723Sdim 1913252723Sdim InvalidatedSymbols SymbolsIndirectlyInvalidated; 1914252723Sdim for (InvalidatedSymbols::const_iterator I=Invalidated->begin(), 1915252723Sdim E = Invalidated->end(); I!=E; ++I) { 1916252723Sdim SymbolRef sym = *I; 1917252723Sdim if (SymbolsDirectlyInvalidated.count(sym)) 1918252723Sdim continue; 1919252723Sdim SymbolsIndirectlyInvalidated.insert(sym); 1920252723Sdim } 1921252723Sdim 1922252723Sdim if (!SymbolsDirectlyInvalidated.empty()) 1923252723Sdim State = getCheckerManager().runCheckersForPointerEscape(State, 1924263509Sdim SymbolsDirectlyInvalidated, Call, PSK_DirectEscapeOnCall, &ITraits); 1925252723Sdim 1926252723Sdim // Notify about the symbols that get indirectly invalidated by the call. 1927252723Sdim if (!SymbolsIndirectlyInvalidated.empty()) 1928252723Sdim State = getCheckerManager().runCheckersForPointerEscape(State, 1929263509Sdim SymbolsIndirectlyInvalidated, Call, PSK_IndirectEscapeOnCall, &ITraits); 1930252723Sdim 1931252723Sdim return State; 1932252723Sdim} 1933252723Sdim 1934221339Sdim/// evalBind - Handle the semantics of binding a value to a specific location. 1935221339Sdim/// This method is used by evalStore and (soon) VisitDeclStmt, and others. 1936226890Sdimvoid ExprEngine::evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE, 1937226890Sdim ExplodedNode *Pred, 1938245431Sdim SVal location, SVal Val, 1939245431Sdim bool atDeclInit, const ProgramPoint *PP) { 1940221339Sdim 1941245431Sdim const LocationContext *LC = Pred->getLocationContext(); 1942245431Sdim PostStmt PS(StoreE, LC); 1943245431Sdim if (!PP) 1944245431Sdim PP = &PS; 1945245431Sdim 1946221339Sdim // Do a previsit of the bind. 1947226890Sdim ExplodedNodeSet CheckedSet; 1948226890Sdim getCheckerManager().runCheckersForBind(CheckedSet, Pred, location, Val, 1949245431Sdim StoreE, *this, *PP); 1950221339Sdim 1951252723Sdim 1952252723Sdim StmtNodeBuilder Bldr(CheckedSet, Dst, *currBldrCtx); 1953252723Sdim 1954245431Sdim // If the location is not a 'Loc', it will already be handled by 1955245431Sdim // the checkers. There is nothing left to do. 1956252723Sdim if (!location.getAs<Loc>()) { 1957252723Sdim const ProgramPoint L = PostStore(StoreE, LC, /*Loc*/0, /*tag*/0); 1958252723Sdim ProgramStateRef state = Pred->getState(); 1959252723Sdim state = processPointerEscapedOnBind(state, location, Val); 1960252723Sdim Bldr.generateNode(L, state, Pred); 1961245431Sdim return; 1962245431Sdim } 1963245431Sdim 1964235633Sdim 1965221339Sdim for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end(); 1966221339Sdim I!=E; ++I) { 1967235633Sdim ExplodedNode *PredI = *I; 1968235633Sdim ProgramStateRef state = PredI->getState(); 1969245431Sdim 1970252723Sdim state = processPointerEscapedOnBind(state, location, Val); 1971252723Sdim 1972245431Sdim // When binding the value, pass on the hint that this is a initialization. 1973245431Sdim // For initializations, we do not need to inform clients of region 1974245431Sdim // changes. 1975252723Sdim state = state->bindLoc(location.castAs<Loc>(), 1976245431Sdim Val, /* notifyChanges = */ !atDeclInit); 1977252723Sdim 1978235633Sdim const MemRegion *LocReg = 0; 1979252723Sdim if (Optional<loc::MemRegionVal> LocRegVal = 1980252723Sdim location.getAs<loc::MemRegionVal>()) { 1981235633Sdim LocReg = LocRegVal->getRegion(); 1982245431Sdim } 1983245431Sdim 1984235633Sdim const ProgramPoint L = PostStore(StoreE, LC, LocReg, 0); 1985245431Sdim Bldr.generateNode(L, state, PredI); 1986221339Sdim } 1987221339Sdim} 1988221339Sdim 1989221339Sdim/// evalStore - Handle the semantics of a store via an assignment. 1990221339Sdim/// @param Dst The node set to store generated state nodes 1991245431Sdim/// @param AssignE The assignment expression if the store happens in an 1992221339Sdim/// assignment. 1993245431Sdim/// @param LocationE The location expression that is stored to. 1994221339Sdim/// @param state The current simulation state 1995221339Sdim/// @param location The location to store the value 1996221339Sdim/// @param Val The value to be stored 1997226890Sdimvoid ExprEngine::evalStore(ExplodedNodeSet &Dst, const Expr *AssignE, 1998226890Sdim const Expr *LocationE, 1999226890Sdim ExplodedNode *Pred, 2000235633Sdim ProgramStateRef state, SVal location, SVal Val, 2001226890Sdim const ProgramPointTag *tag) { 2002221339Sdim // Proceed with the store. We use AssignE as the anchor for the PostStore 2003221339Sdim // ProgramPoint if it is non-NULL, and LocationE otherwise. 2004221339Sdim const Expr *StoreE = AssignE ? AssignE : LocationE; 2005221339Sdim 2006221339Sdim // Evaluate the location (checks for bad dereferences). 2007221339Sdim ExplodedNodeSet Tmp; 2008235633Sdim evalLocation(Tmp, AssignE, LocationE, Pred, state, location, tag, false); 2009221339Sdim 2010221339Sdim if (Tmp.empty()) 2011221339Sdim return; 2012221339Sdim 2013221339Sdim if (location.isUndef()) 2014221339Sdim return; 2015221339Sdim 2016221339Sdim for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) 2017235633Sdim evalBind(Dst, StoreE, *NI, location, Val, false); 2018221339Sdim} 2019221339Sdim 2020235633Sdimvoid ExprEngine::evalLoad(ExplodedNodeSet &Dst, 2021235633Sdim const Expr *NodeEx, 2022235633Sdim const Expr *BoundEx, 2023235633Sdim ExplodedNode *Pred, 2024235633Sdim ProgramStateRef state, 2025235633Sdim SVal location, 2026235633Sdim const ProgramPointTag *tag, 2027235633Sdim QualType LoadTy) 2028235633Sdim{ 2029252723Sdim assert(!location.getAs<NonLoc>() && "location cannot be a NonLoc."); 2030221339Sdim 2031221339Sdim // Are we loading from a region? This actually results in two loads; one 2032221339Sdim // to fetch the address of the referenced value and one to fetch the 2033221339Sdim // referenced value. 2034226890Sdim if (const TypedValueRegion *TR = 2035226890Sdim dyn_cast_or_null<TypedValueRegion>(location.getAsRegion())) { 2036221339Sdim 2037221339Sdim QualType ValTy = TR->getValueType(); 2038221339Sdim if (const ReferenceType *RT = ValTy->getAs<ReferenceType>()) { 2039226890Sdim static SimpleProgramPointTag 2040226890Sdim loadReferenceTag("ExprEngine : Load Reference"); 2041221339Sdim ExplodedNodeSet Tmp; 2042235633Sdim evalLoadCommon(Tmp, NodeEx, BoundEx, Pred, state, 2043235633Sdim location, &loadReferenceTag, 2044221339Sdim getContext().getPointerType(RT->getPointeeType())); 2045221339Sdim 2046221339Sdim // Perform the load from the referenced value. 2047221339Sdim for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end() ; I!=E; ++I) { 2048226890Sdim state = (*I)->getState(); 2049235633Sdim location = state->getSVal(BoundEx, (*I)->getLocationContext()); 2050235633Sdim evalLoadCommon(Dst, NodeEx, BoundEx, *I, state, location, tag, LoadTy); 2051221339Sdim } 2052221339Sdim return; 2053221339Sdim } 2054221339Sdim } 2055221339Sdim 2056235633Sdim evalLoadCommon(Dst, NodeEx, BoundEx, Pred, state, location, tag, LoadTy); 2057221339Sdim} 2058221339Sdim 2059235633Sdimvoid ExprEngine::evalLoadCommon(ExplodedNodeSet &Dst, 2060235633Sdim const Expr *NodeEx, 2061235633Sdim const Expr *BoundEx, 2062235633Sdim ExplodedNode *Pred, 2063235633Sdim ProgramStateRef state, 2064235633Sdim SVal location, 2065235633Sdim const ProgramPointTag *tag, 2066235633Sdim QualType LoadTy) { 2067235633Sdim assert(NodeEx); 2068235633Sdim assert(BoundEx); 2069221339Sdim // Evaluate the location (checks for bad dereferences). 2070221339Sdim ExplodedNodeSet Tmp; 2071235633Sdim evalLocation(Tmp, NodeEx, BoundEx, Pred, state, location, tag, true); 2072221339Sdim if (Tmp.empty()) 2073221339Sdim return; 2074221339Sdim 2075245431Sdim StmtNodeBuilder Bldr(Tmp, Dst, *currBldrCtx); 2076221339Sdim if (location.isUndef()) 2077221339Sdim return; 2078221339Sdim 2079221339Sdim // Proceed with the load. 2080221339Sdim for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) { 2081226890Sdim state = (*NI)->getState(); 2082235633Sdim const LocationContext *LCtx = (*NI)->getLocationContext(); 2083221339Sdim 2084252723Sdim SVal V = UnknownVal(); 2085252723Sdim if (location.isValid()) { 2086221339Sdim if (LoadTy.isNull()) 2087235633Sdim LoadTy = BoundEx->getType(); 2088252723Sdim V = state->getSVal(location.castAs<Loc>(), LoadTy); 2089221339Sdim } 2090252723Sdim 2091252723Sdim Bldr.generateNode(NodeEx, *NI, state->BindExpr(BoundEx, LCtx, V), tag, 2092252723Sdim ProgramPoint::PostLoadKind); 2093221339Sdim } 2094221339Sdim} 2095221339Sdim 2096235633Sdimvoid ExprEngine::evalLocation(ExplodedNodeSet &Dst, 2097235633Sdim const Stmt *NodeEx, 2098235633Sdim const Stmt *BoundEx, 2099235633Sdim ExplodedNode *Pred, 2100235633Sdim ProgramStateRef state, 2101235633Sdim SVal location, 2102235633Sdim const ProgramPointTag *tag, 2103235633Sdim bool isLoad) { 2104245431Sdim StmtNodeBuilder BldrTop(Pred, Dst, *currBldrCtx); 2105221339Sdim // Early checks for performance reason. 2106221339Sdim if (location.isUnknown()) { 2107221339Sdim return; 2108221339Sdim } 2109221339Sdim 2110221339Sdim ExplodedNodeSet Src; 2111235633Sdim BldrTop.takeNodes(Pred); 2112245431Sdim StmtNodeBuilder Bldr(Pred, Src, *currBldrCtx); 2113235633Sdim if (Pred->getState() != state) { 2114221339Sdim // Associate this new state with an ExplodedNode. 2115221339Sdim // FIXME: If I pass null tag, the graph is incorrect, e.g for 2116221339Sdim // int *p; 2117221339Sdim // p = 0; 2118221339Sdim // *p = 0xDEADBEEF; 2119221339Sdim // "p = 0" is not noted as "Null pointer value stored to 'p'" but 2120221339Sdim // instead "int *p" is noted as 2121221339Sdim // "Variable 'p' initialized to a null pointer value" 2122226890Sdim 2123245431Sdim static SimpleProgramPointTag tag("ExprEngine: Location"); 2124245431Sdim Bldr.generateNode(NodeEx, Pred, state, &tag); 2125221339Sdim } 2126235633Sdim ExplodedNodeSet Tmp; 2127235633Sdim getCheckerManager().runCheckersForLocation(Tmp, Src, location, isLoad, 2128235633Sdim NodeEx, BoundEx, *this); 2129235633Sdim BldrTop.addNodes(Tmp); 2130221339Sdim} 2131221339Sdim 2132226890Sdimstd::pair<const ProgramPointTag *, const ProgramPointTag*> 2133245431SdimExprEngine::geteagerlyAssumeBinOpBifurcationTags() { 2134226890Sdim static SimpleProgramPointTag 2135245431Sdim eagerlyAssumeBinOpBifurcationTrue("ExprEngine : Eagerly Assume True"), 2136245431Sdim eagerlyAssumeBinOpBifurcationFalse("ExprEngine : Eagerly Assume False"); 2137245431Sdim return std::make_pair(&eagerlyAssumeBinOpBifurcationTrue, 2138245431Sdim &eagerlyAssumeBinOpBifurcationFalse); 2139221339Sdim} 2140221339Sdim 2141245431Sdimvoid ExprEngine::evalEagerlyAssumeBinOpBifurcation(ExplodedNodeSet &Dst, 2142245431Sdim ExplodedNodeSet &Src, 2143245431Sdim const Expr *Ex) { 2144245431Sdim StmtNodeBuilder Bldr(Src, Dst, *currBldrCtx); 2145226890Sdim 2146221339Sdim for (ExplodedNodeSet::iterator I=Src.begin(), E=Src.end(); I!=E; ++I) { 2147221339Sdim ExplodedNode *Pred = *I; 2148221339Sdim // Test if the previous node was as the same expression. This can happen 2149221339Sdim // when the expression fails to evaluate to anything meaningful and 2150221339Sdim // (as an optimization) we don't generate a node. 2151221339Sdim ProgramPoint P = Pred->getLocation(); 2152252723Sdim if (!P.getAs<PostStmt>() || P.castAs<PostStmt>().getStmt() != Ex) { 2153221339Sdim continue; 2154221339Sdim } 2155221339Sdim 2156235633Sdim ProgramStateRef state = Pred->getState(); 2157235633Sdim SVal V = state->getSVal(Ex, Pred->getLocationContext()); 2158252723Sdim Optional<nonloc::SymbolVal> SEV = V.getAs<nonloc::SymbolVal>(); 2159235633Sdim if (SEV && SEV->isExpression()) { 2160226890Sdim const std::pair<const ProgramPointTag *, const ProgramPointTag*> &tags = 2161245431Sdim geteagerlyAssumeBinOpBifurcationTags(); 2162226890Sdim 2163252723Sdim ProgramStateRef StateTrue, StateFalse; 2164252723Sdim tie(StateTrue, StateFalse) = state->assume(*SEV); 2165252723Sdim 2166221339Sdim // First assume that the condition is true. 2167252723Sdim if (StateTrue) { 2168226890Sdim SVal Val = svalBuilder.makeIntVal(1U, Ex->getType()); 2169235633Sdim StateTrue = StateTrue->BindExpr(Ex, Pred->getLocationContext(), Val); 2170245431Sdim Bldr.generateNode(Ex, Pred, StateTrue, tags.first); 2171221339Sdim } 2172221339Sdim 2173221339Sdim // Next, assume that the condition is false. 2174252723Sdim if (StateFalse) { 2175226890Sdim SVal Val = svalBuilder.makeIntVal(0U, Ex->getType()); 2176235633Sdim StateFalse = StateFalse->BindExpr(Ex, Pred->getLocationContext(), Val); 2177245431Sdim Bldr.generateNode(Ex, Pred, StateFalse, tags.second); 2178221339Sdim } 2179221339Sdim } 2180221339Sdim } 2181221339Sdim} 2182221339Sdim 2183245431Sdimvoid ExprEngine::VisitGCCAsmStmt(const GCCAsmStmt *A, ExplodedNode *Pred, 2184245431Sdim ExplodedNodeSet &Dst) { 2185245431Sdim StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); 2186235633Sdim // We have processed both the inputs and the outputs. All of the outputs 2187235633Sdim // should evaluate to Locs. Nuke all of their values. 2188221339Sdim 2189235633Sdim // FIXME: Some day in the future it would be nice to allow a "plug-in" 2190235633Sdim // which interprets the inline asm and stores proper results in the 2191235633Sdim // outputs. 2192221339Sdim 2193235633Sdim ProgramStateRef state = Pred->getState(); 2194221339Sdim 2195245431Sdim for (GCCAsmStmt::const_outputs_iterator OI = A->begin_outputs(), 2196235633Sdim OE = A->end_outputs(); OI != OE; ++OI) { 2197235633Sdim SVal X = state->getSVal(*OI, Pred->getLocationContext()); 2198252723Sdim assert (!X.getAs<NonLoc>()); // Should be an Lval, or unknown, undef. 2199221339Sdim 2200252723Sdim if (Optional<Loc> LV = X.getAs<Loc>()) 2201252723Sdim state = state->bindLoc(*LV, UnknownVal()); 2202221339Sdim } 2203221339Sdim 2204235633Sdim Bldr.generateNode(A, Pred, state); 2205221339Sdim} 2206221339Sdim 2207245431Sdimvoid ExprEngine::VisitMSAsmStmt(const MSAsmStmt *A, ExplodedNode *Pred, 2208245431Sdim ExplodedNodeSet &Dst) { 2209245431Sdim StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); 2210245431Sdim Bldr.generateNode(A, Pred, Pred->getState()); 2211245431Sdim} 2212245431Sdim 2213221339Sdim//===----------------------------------------------------------------------===// 2214221339Sdim// Visualization. 2215221339Sdim//===----------------------------------------------------------------------===// 2216221339Sdim 2217221339Sdim#ifndef NDEBUG 2218221339Sdimstatic ExprEngine* GraphPrintCheckerState; 2219221339Sdimstatic SourceManager* GraphPrintSourceManager; 2220221339Sdim 2221221339Sdimnamespace llvm { 2222221339Sdimtemplate<> 2223221339Sdimstruct DOTGraphTraits<ExplodedNode*> : 2224221339Sdim public DefaultDOTGraphTraits { 2225221339Sdim 2226221339Sdim DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} 2227221339Sdim 2228221339Sdim // FIXME: Since we do not cache error nodes in ExprEngine now, this does not 2229221339Sdim // work. 2230226890Sdim static std::string getNodeAttributes(const ExplodedNode *N, void*) { 2231221339Sdim 2232221339Sdim#if 0 2233221339Sdim // FIXME: Replace with a general scheme to tell if the node is 2234221339Sdim // an error node. 2235221339Sdim if (GraphPrintCheckerState->isImplicitNullDeref(N) || 2236221339Sdim GraphPrintCheckerState->isExplicitNullDeref(N) || 2237221339Sdim GraphPrintCheckerState->isUndefDeref(N) || 2238221339Sdim GraphPrintCheckerState->isUndefStore(N) || 2239221339Sdim GraphPrintCheckerState->isUndefControlFlow(N) || 2240221339Sdim GraphPrintCheckerState->isUndefResult(N) || 2241221339Sdim GraphPrintCheckerState->isBadCall(N) || 2242221339Sdim GraphPrintCheckerState->isUndefArg(N)) 2243221339Sdim return "color=\"red\",style=\"filled\""; 2244221339Sdim 2245221339Sdim if (GraphPrintCheckerState->isNoReturnCall(N)) 2246221339Sdim return "color=\"blue\",style=\"filled\""; 2247221339Sdim#endif 2248221339Sdim return ""; 2249221339Sdim } 2250221339Sdim 2251252723Sdim static void printLocation(raw_ostream &Out, SourceLocation SLoc) { 2252245431Sdim if (SLoc.isFileID()) { 2253245431Sdim Out << "\\lline=" 2254245431Sdim << GraphPrintSourceManager->getExpansionLineNumber(SLoc) 2255245431Sdim << " col=" 2256245431Sdim << GraphPrintSourceManager->getExpansionColumnNumber(SLoc) 2257245431Sdim << "\\l"; 2258245431Sdim } 2259245431Sdim } 2260245431Sdim 2261226890Sdim static std::string getNodeLabel(const ExplodedNode *N, void*){ 2262221339Sdim 2263221339Sdim std::string sbuf; 2264221339Sdim llvm::raw_string_ostream Out(sbuf); 2265221339Sdim 2266221339Sdim // Program Location. 2267221339Sdim ProgramPoint Loc = N->getLocation(); 2268221339Sdim 2269221339Sdim switch (Loc.getKind()) { 2270245431Sdim case ProgramPoint::BlockEntranceKind: { 2271221339Sdim Out << "Block Entrance: B" 2272252723Sdim << Loc.castAs<BlockEntrance>().getBlock()->getBlockID(); 2273245431Sdim if (const NamedDecl *ND = 2274245431Sdim dyn_cast<NamedDecl>(Loc.getLocationContext()->getDecl())) { 2275245431Sdim Out << " ("; 2276245431Sdim ND->printName(Out); 2277245431Sdim Out << ")"; 2278245431Sdim } 2279221339Sdim break; 2280245431Sdim } 2281221339Sdim 2282221339Sdim case ProgramPoint::BlockExitKind: 2283221339Sdim assert (false); 2284221339Sdim break; 2285221339Sdim 2286221339Sdim case ProgramPoint::CallEnterKind: 2287221339Sdim Out << "CallEnter"; 2288221339Sdim break; 2289221339Sdim 2290245431Sdim case ProgramPoint::CallExitBeginKind: 2291245431Sdim Out << "CallExitBegin"; 2292221339Sdim break; 2293221339Sdim 2294245431Sdim case ProgramPoint::CallExitEndKind: 2295245431Sdim Out << "CallExitEnd"; 2296245431Sdim break; 2297245431Sdim 2298245431Sdim case ProgramPoint::PostStmtPurgeDeadSymbolsKind: 2299245431Sdim Out << "PostStmtPurgeDeadSymbols"; 2300245431Sdim break; 2301245431Sdim 2302245431Sdim case ProgramPoint::PreStmtPurgeDeadSymbolsKind: 2303245431Sdim Out << "PreStmtPurgeDeadSymbols"; 2304245431Sdim break; 2305245431Sdim 2306235633Sdim case ProgramPoint::EpsilonKind: 2307235633Sdim Out << "Epsilon Point"; 2308235633Sdim break; 2309235633Sdim 2310245431Sdim case ProgramPoint::PreImplicitCallKind: { 2311252723Sdim ImplicitCallPoint PC = Loc.castAs<ImplicitCallPoint>(); 2312245431Sdim Out << "PreCall: "; 2313245431Sdim 2314245431Sdim // FIXME: Get proper printing options. 2315252723Sdim PC.getDecl()->print(Out, LangOptions()); 2316252723Sdim printLocation(Out, PC.getLocation()); 2317245431Sdim break; 2318245431Sdim } 2319245431Sdim 2320245431Sdim case ProgramPoint::PostImplicitCallKind: { 2321252723Sdim ImplicitCallPoint PC = Loc.castAs<ImplicitCallPoint>(); 2322245431Sdim Out << "PostCall: "; 2323245431Sdim 2324245431Sdim // FIXME: Get proper printing options. 2325252723Sdim PC.getDecl()->print(Out, LangOptions()); 2326252723Sdim printLocation(Out, PC.getLocation()); 2327245431Sdim break; 2328245431Sdim } 2329245431Sdim 2330252723Sdim case ProgramPoint::PostInitializerKind: { 2331252723Sdim Out << "PostInitializer: "; 2332252723Sdim const CXXCtorInitializer *Init = 2333252723Sdim Loc.castAs<PostInitializer>().getInitializer(); 2334252723Sdim if (const FieldDecl *FD = Init->getAnyMember()) 2335252723Sdim Out << *FD; 2336252723Sdim else { 2337252723Sdim QualType Ty = Init->getTypeSourceInfo()->getType(); 2338252723Sdim Ty = Ty.getLocalUnqualifiedType(); 2339221339Sdim LangOptions LO; // FIXME. 2340252723Sdim Ty.print(Out, LO); 2341221339Sdim } 2342252723Sdim break; 2343252723Sdim } 2344221339Sdim 2345252723Sdim case ProgramPoint::BlockEdgeKind: { 2346252723Sdim const BlockEdge &E = Loc.castAs<BlockEdge>(); 2347221339Sdim Out << "Edge: (B" << E.getSrc()->getBlockID() << ", B" 2348221339Sdim << E.getDst()->getBlockID() << ')'; 2349221339Sdim 2350226890Sdim if (const Stmt *T = E.getSrc()->getTerminator()) { 2351221339Sdim SourceLocation SLoc = T->getLocStart(); 2352221339Sdim 2353221339Sdim Out << "\\|Terminator: "; 2354221339Sdim LangOptions LO; // FIXME. 2355221339Sdim E.getSrc()->printTerminator(Out, LO); 2356221339Sdim 2357221339Sdim if (SLoc.isFileID()) { 2358221339Sdim Out << "\\lline=" 2359226890Sdim << GraphPrintSourceManager->getExpansionLineNumber(SLoc) 2360221339Sdim << " col=" 2361226890Sdim << GraphPrintSourceManager->getExpansionColumnNumber(SLoc); 2362221339Sdim } 2363221339Sdim 2364221339Sdim if (isa<SwitchStmt>(T)) { 2365226890Sdim const Stmt *Label = E.getDst()->getLabel(); 2366221339Sdim 2367221339Sdim if (Label) { 2368226890Sdim if (const CaseStmt *C = dyn_cast<CaseStmt>(Label)) { 2369221339Sdim Out << "\\lcase "; 2370221339Sdim LangOptions LO; // FIXME. 2371221339Sdim C->getLHS()->printPretty(Out, 0, PrintingPolicy(LO)); 2372221339Sdim 2373226890Sdim if (const Stmt *RHS = C->getRHS()) { 2374221339Sdim Out << " .. "; 2375221339Sdim RHS->printPretty(Out, 0, PrintingPolicy(LO)); 2376221339Sdim } 2377221339Sdim 2378221339Sdim Out << ":"; 2379221339Sdim } 2380221339Sdim else { 2381221339Sdim assert (isa<DefaultStmt>(Label)); 2382221339Sdim Out << "\\ldefault:"; 2383221339Sdim } 2384221339Sdim } 2385221339Sdim else 2386221339Sdim Out << "\\l(implicit) default:"; 2387221339Sdim } 2388221339Sdim else if (isa<IndirectGotoStmt>(T)) { 2389221339Sdim // FIXME 2390221339Sdim } 2391221339Sdim else { 2392221339Sdim Out << "\\lCondition: "; 2393221339Sdim if (*E.getSrc()->succ_begin() == E.getDst()) 2394221339Sdim Out << "true"; 2395221339Sdim else 2396221339Sdim Out << "false"; 2397221339Sdim } 2398221339Sdim 2399221339Sdim Out << "\\l"; 2400221339Sdim } 2401221339Sdim 2402221339Sdim#if 0 2403221339Sdim // FIXME: Replace with a general scheme to determine 2404221339Sdim // the name of the check. 2405221339Sdim if (GraphPrintCheckerState->isUndefControlFlow(N)) { 2406221339Sdim Out << "\\|Control-flow based on\\lUndefined value.\\l"; 2407221339Sdim } 2408221339Sdim#endif 2409252723Sdim break; 2410221339Sdim } 2411252723Sdim 2412252723Sdim default: { 2413252723Sdim const Stmt *S = Loc.castAs<StmtPoint>().getStmt(); 2414252723Sdim 2415252723Sdim Out << S->getStmtClassName() << ' ' << (const void*) S << ' '; 2416252723Sdim LangOptions LO; // FIXME. 2417252723Sdim S->printPretty(Out, 0, PrintingPolicy(LO)); 2418252723Sdim printLocation(Out, S->getLocStart()); 2419252723Sdim 2420252723Sdim if (Loc.getAs<PreStmt>()) 2421252723Sdim Out << "\\lPreStmt\\l;"; 2422252723Sdim else if (Loc.getAs<PostLoad>()) 2423252723Sdim Out << "\\lPostLoad\\l;"; 2424252723Sdim else if (Loc.getAs<PostStore>()) 2425252723Sdim Out << "\\lPostStore\\l"; 2426252723Sdim else if (Loc.getAs<PostLValue>()) 2427252723Sdim Out << "\\lPostLValue\\l"; 2428252723Sdim 2429252723Sdim#if 0 2430252723Sdim // FIXME: Replace with a general scheme to determine 2431252723Sdim // the name of the check. 2432252723Sdim if (GraphPrintCheckerState->isImplicitNullDeref(N)) 2433252723Sdim Out << "\\|Implicit-Null Dereference.\\l"; 2434252723Sdim else if (GraphPrintCheckerState->isExplicitNullDeref(N)) 2435252723Sdim Out << "\\|Explicit-Null Dereference.\\l"; 2436252723Sdim else if (GraphPrintCheckerState->isUndefDeref(N)) 2437252723Sdim Out << "\\|Dereference of undefialied value.\\l"; 2438252723Sdim else if (GraphPrintCheckerState->isUndefStore(N)) 2439252723Sdim Out << "\\|Store to Undefined Loc."; 2440252723Sdim else if (GraphPrintCheckerState->isUndefResult(N)) 2441252723Sdim Out << "\\|Result of operation is undefined."; 2442252723Sdim else if (GraphPrintCheckerState->isNoReturnCall(N)) 2443252723Sdim Out << "\\|Call to function marked \"noreturn\"."; 2444252723Sdim else if (GraphPrintCheckerState->isBadCall(N)) 2445252723Sdim Out << "\\|Call to NULL/Undefined."; 2446252723Sdim else if (GraphPrintCheckerState->isUndefArg(N)) 2447252723Sdim Out << "\\|Argument in call is undefined"; 2448252723Sdim#endif 2449252723Sdim 2450252723Sdim break; 2451252723Sdim } 2452221339Sdim } 2453221339Sdim 2454235633Sdim ProgramStateRef state = N->getState(); 2455245431Sdim Out << "\\|StateID: " << (const void*) state.getPtr() 2456245431Sdim << " NodeID: " << (const void*) N << "\\|"; 2457235633Sdim state->printDOT(Out); 2458226890Sdim 2459226890Sdim Out << "\\l"; 2460226890Sdim 2461226890Sdim if (const ProgramPointTag *tag = Loc.getTag()) { 2462226890Sdim Out << "\\|Tag: " << tag->getTagDescription(); 2463226890Sdim Out << "\\l"; 2464226890Sdim } 2465221339Sdim return Out.str(); 2466221339Sdim } 2467221339Sdim}; 2468221339Sdim} // end llvm namespace 2469221339Sdim#endif 2470221339Sdim 2471221339Sdim#ifndef NDEBUG 2472221339Sdimtemplate <typename ITERATOR> 2473226890SdimExplodedNode *GetGraphNode(ITERATOR I) { return *I; } 2474221339Sdim 2475221339Sdimtemplate <> ExplodedNode* 2476221339SdimGetGraphNode<llvm::DenseMap<ExplodedNode*, Expr*>::iterator> 2477221339Sdim (llvm::DenseMap<ExplodedNode*, Expr*>::iterator I) { 2478221339Sdim return I->first; 2479221339Sdim} 2480221339Sdim#endif 2481221339Sdim 2482221339Sdimvoid ExprEngine::ViewGraph(bool trim) { 2483221339Sdim#ifndef NDEBUG 2484221339Sdim if (trim) { 2485252723Sdim std::vector<const ExplodedNode*> Src; 2486221339Sdim 2487221339Sdim // Flush any outstanding reports to make sure we cover all the nodes. 2488221339Sdim // This does not cause them to get displayed. 2489221339Sdim for (BugReporter::iterator I=BR.begin(), E=BR.end(); I!=E; ++I) 2490221339Sdim const_cast<BugType*>(*I)->FlushReports(BR); 2491221339Sdim 2492221339Sdim // Iterate through the reports and get their nodes. 2493221339Sdim for (BugReporter::EQClasses_iterator 2494221339Sdim EI = BR.EQClasses_begin(), EE = BR.EQClasses_end(); EI != EE; ++EI) { 2495235633Sdim ExplodedNode *N = const_cast<ExplodedNode*>(EI->begin()->getErrorNode()); 2496221339Sdim if (N) Src.push_back(N); 2497221339Sdim } 2498221339Sdim 2499252723Sdim ViewGraph(Src); 2500221339Sdim } 2501221339Sdim else { 2502221339Sdim GraphPrintCheckerState = this; 2503221339Sdim GraphPrintSourceManager = &getContext().getSourceManager(); 2504221339Sdim 2505221339Sdim llvm::ViewGraph(*G.roots_begin(), "ExprEngine"); 2506221339Sdim 2507221339Sdim GraphPrintCheckerState = NULL; 2508221339Sdim GraphPrintSourceManager = NULL; 2509221339Sdim } 2510221339Sdim#endif 2511221339Sdim} 2512221339Sdim 2513252723Sdimvoid ExprEngine::ViewGraph(ArrayRef<const ExplodedNode*> Nodes) { 2514221339Sdim#ifndef NDEBUG 2515221339Sdim GraphPrintCheckerState = this; 2516221339Sdim GraphPrintSourceManager = &getContext().getSourceManager(); 2517221339Sdim 2518252723Sdim OwningPtr<ExplodedGraph> TrimmedG(G.trim(Nodes)); 2519221339Sdim 2520221339Sdim if (!TrimmedG.get()) 2521221339Sdim llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n"; 2522221339Sdim else 2523221339Sdim llvm::ViewGraph(*TrimmedG->roots_begin(), "TrimmedExprEngine"); 2524221339Sdim 2525221339Sdim GraphPrintCheckerState = NULL; 2526221339Sdim GraphPrintSourceManager = NULL; 2527221339Sdim#endif 2528221339Sdim} 2529