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 16234353Sdim#define DEBUG_TYPE "ExprEngine" 17234353Sdim 18221339Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 19263508Sdim#include "PrettyStackTraceLocationContext.h" 20221339Sdim#include "clang/AST/CharUnits.h" 21221339Sdim#include "clang/AST/ParentMap.h" 22249423Sdim#include "clang/AST/StmtCXX.h" 23221339Sdim#include "clang/AST/StmtObjC.h" 24221339Sdim#include "clang/Basic/Builtins.h" 25249423Sdim#include "clang/Basic/PrettyStackTrace.h" 26221339Sdim#include "clang/Basic/SourceManager.h" 27249423Sdim#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 28249423Sdim#include "clang/StaticAnalyzer/Core/CheckerManager.h" 29249423Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" 30249423Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 31221339Sdim#include "llvm/ADT/ImmutableList.h" 32234353Sdim#include "llvm/ADT/Statistic.h" 33249423Sdim#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 43234353SdimSTATISTIC(NumRemoveDeadBindings, 44234353Sdim "The # of times RemoveDeadBindings is called"); 45234353SdimSTATISTIC(NumMaxBlockCountReached, 46234353Sdim "The # of aborted paths due to reaching the maximum block count in " 47234353Sdim "a top level function"); 48234353SdimSTATISTIC(NumMaxBlockCountReachedInInlined, 49234353Sdim "The # of aborted paths due to reaching the maximum block count in " 50234353Sdim "an inlined function"); 51234353SdimSTATISTIC(NumTimesRetriedWithoutInlining, 52234353Sdim "The # of times we re-evaluated a call without inlining"); 53234353Sdim 54221339Sdim//===----------------------------------------------------------------------===// 55221339Sdim// Engine construction and deletion. 56221339Sdim//===----------------------------------------------------------------------===// 57221339Sdim 58234353SdimExprEngine::ExprEngine(AnalysisManager &mgr, bool gcEnabled, 59243830Sdim SetOfConstDecls *VisitedCalleesIn, 60249423Sdim FunctionSummariesTy *FS, 61249423Sdim InliningModes HowToInlineIn) 62221339Sdim : AMgr(mgr), 63234353Sdim AnalysisDeclContexts(mgr.getAnalysisDeclContextManager()), 64243830Sdim Engine(*this, FS), 65221339Sdim G(Engine.getGraph()), 66221339Sdim StateMgr(getContext(), mgr.getStoreManagerCreator(), 67221339Sdim mgr.getConstraintManagerCreator(), G.getAllocator(), 68243830Sdim this), 69221339Sdim SymMgr(StateMgr.getSymbolManager()), 70221339Sdim svalBuilder(StateMgr.getSValBuilder()), 71249423Sdim currStmtIdx(0), currBldrCtx(0), 72243830Sdim ObjCNoRet(mgr.getASTContext()), 73243830Sdim ObjCGCEnabled(gcEnabled), BR(mgr, *this), 74249423Sdim VisitedCallees(VisitedCalleesIn), 75249423Sdim HowToInline(HowToInlineIn) 76243830Sdim{ 77243830Sdim unsigned TrimInterval = mgr.options.getGraphTrimInterval(); 78243830Sdim if (TrimInterval != 0) { 79243830Sdim // Enable eager node reclaimation when constructing the ExplodedGraph. 80243830Sdim G.enableNodeReclamation(TrimInterval); 81221339Sdim } 82221339Sdim} 83221339Sdim 84221339SdimExprEngine::~ExprEngine() { 85221339Sdim BR.FlushReports(); 86221339Sdim} 87221339Sdim 88221339Sdim//===----------------------------------------------------------------------===// 89221339Sdim// Utility methods. 90221339Sdim//===----------------------------------------------------------------------===// 91221339Sdim 92234353SdimProgramStateRef ExprEngine::getInitialState(const LocationContext *InitLoc) { 93234353Sdim ProgramStateRef state = StateMgr.getInitialState(InitLoc); 94234353Sdim 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 { 100234353Sdim 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(); 110251662Sdim const BuiltinType *BT = dyn_cast<BuiltinType>(T); 111251662Sdim 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 123249423Sdim Optional<DefinedOrUnknownSVal> Constraint = 124249423Sdim Constraint_untested.getAs<DefinedOrUnknownSVal>(); 125221339Sdim 126221339Sdim if (!Constraint) 127221339Sdim break; 128221339Sdim 129234353Sdim if (ProgramStateRef newState = state->assume(*Constraint, true)) 130221339Sdim state = newState; 131221339Sdim } 132234353Sdim break; 133234353Sdim } 134234353Sdim while (0); 135221339Sdim 136234353Sdim if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) { 137234353Sdim // Precondition: 'self' is always non-null upon entry to an Objective-C 138234353Sdim // method. 139234353Sdim const ImplicitParamDecl *SelfD = MD->getSelfDecl(); 140234353Sdim const MemRegion *R = state->getRegion(SelfD, InitLoc); 141234353Sdim SVal V = state->getSVal(loc::MemRegionVal(R)); 142221339Sdim 143249423Sdim if (Optional<Loc> LV = V.getAs<Loc>()) { 144234353Sdim // Assume that the pointer value in 'self' is non-null. 145234353Sdim state = state->assume(*LV, true); 146234353Sdim assert(state && "'self' cannot be null"); 147221339Sdim } 148234353Sdim } 149221339Sdim 150234353Sdim if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(D)) { 151234353Sdim if (!MD->isStatic()) { 152234353Sdim // Precondition: 'this' is always non-null upon entry to the 153234353Sdim // top-level function. This is our starting assumption for 154234353Sdim // analyzing an "open" program. 155234353Sdim const StackFrameContext *SFC = InitLoc->getCurrentStackFrame(); 156234353Sdim if (SFC->getParent() == 0) { 157239462Sdim loc::MemRegionVal L = svalBuilder.getCXXThis(MD, SFC); 158234353Sdim SVal V = state->getSVal(L); 159249423Sdim if (Optional<Loc> LV = V.getAs<Loc>()) { 160234353Sdim state = state->assume(*LV, true); 161234353Sdim assert(state && "'this' cannot be null"); 162234353Sdim } 163223017Sdim } 164223017Sdim } 165223017Sdim } 166234353Sdim 167234353Sdim return state; 168223017Sdim} 169223017Sdim 170249423SdimProgramStateRef 171249423SdimExprEngine::createTemporaryRegionIfNeeded(ProgramStateRef State, 172249423Sdim const LocationContext *LC, 173249423Sdim const Expr *Ex, 174249423Sdim const Expr *Result) { 175249423Sdim SVal V = State->getSVal(Ex, LC); 176249423Sdim if (!Result) { 177249423Sdim // If we don't have an explicit result expression, we're in "if needed" 178249423Sdim // mode. Only create a region if the current value is a NonLoc. 179249423Sdim if (!V.getAs<NonLoc>()) 180249423Sdim return State; 181249423Sdim Result = Ex; 182249423Sdim } else { 183249423Sdim // We need to create a region no matter what. For sanity, make sure we don't 184249423Sdim // try to stuff a Loc into a non-pointer temporary region. 185251662Sdim assert(!V.getAs<Loc>() || Loc::isLocType(Result->getType()) || 186251662Sdim Result->getType()->isMemberPointerType()); 187249423Sdim } 188243830Sdim 189249423Sdim ProgramStateManager &StateMgr = State->getStateManager(); 190249423Sdim MemRegionManager &MRMgr = StateMgr.getRegionManager(); 191249423Sdim StoreManager &StoreMgr = StateMgr.getStoreManager(); 192249423Sdim 193249423Sdim // We need to be careful about treating a derived type's value as 194249423Sdim // bindings for a base type. Unless we're creating a temporary pointer region, 195249423Sdim // start by stripping and recording base casts. 196249423Sdim SmallVector<const CastExpr *, 4> Casts; 197249423Sdim const Expr *Inner = Ex->IgnoreParens(); 198249423Sdim if (!Loc::isLocType(Result->getType())) { 199249423Sdim while (const CastExpr *CE = dyn_cast<CastExpr>(Inner)) { 200249423Sdim if (CE->getCastKind() == CK_DerivedToBase || 201249423Sdim CE->getCastKind() == CK_UncheckedDerivedToBase) 202249423Sdim Casts.push_back(CE); 203249423Sdim else if (CE->getCastKind() != CK_NoOp) 204249423Sdim break; 205249423Sdim 206249423Sdim Inner = CE->getSubExpr()->IgnoreParens(); 207249423Sdim } 208243830Sdim } 209243830Sdim 210249423Sdim // Create a temporary object region for the inner expression (which may have 211249423Sdim // a more derived type) and bind the value into it. 212263508Sdim const TypedValueRegion *TR = NULL; 213263508Sdim if (const MaterializeTemporaryExpr *MT = 214263508Sdim dyn_cast<MaterializeTemporaryExpr>(Result)) { 215263508Sdim StorageDuration SD = MT->getStorageDuration(); 216263508Sdim // If this object is bound to a reference with static storage duration, we 217263508Sdim // put it in a different region to prevent "address leakage" warnings. 218263508Sdim if (SD == SD_Static || SD == SD_Thread) 219263508Sdim TR = MRMgr.getCXXStaticTempObjectRegion(Inner); 220263508Sdim } 221263508Sdim if (!TR) 222263508Sdim TR = MRMgr.getCXXTempObjectRegion(Inner, LC); 223263508Sdim 224249423Sdim SVal Reg = loc::MemRegionVal(TR); 225249423Sdim 226249423Sdim if (V.isUnknown()) 227249423Sdim V = getSValBuilder().conjureSymbolVal(Result, LC, TR->getValueType(), 228249423Sdim currBldrCtx->blockCount()); 229249423Sdim State = State->bindLoc(Reg, V); 230249423Sdim 231249423Sdim // Re-apply the casts (from innermost to outermost) for type sanity. 232249423Sdim for (SmallVectorImpl<const CastExpr *>::reverse_iterator I = Casts.rbegin(), 233249423Sdim E = Casts.rend(); 234249423Sdim I != E; ++I) { 235249423Sdim Reg = StoreMgr.evalDerivedToBase(Reg, *I); 236249423Sdim } 237249423Sdim 238249423Sdim State = State->BindExpr(Result, LC, Reg); 239243830Sdim return State; 240243830Sdim} 241243830Sdim 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. 248234353SdimProgramStateRef ExprEngine::processAssume(ProgramStateRef state, 249226633Sdim SVal cond, bool assumption) { 250226633Sdim return getCheckerManager().runCheckersForEvalAssume(state, cond, assumption); 251221339Sdim} 252221339Sdim 253234353Sdimbool ExprEngine::wantsRegionChangeUpdate(ProgramStateRef state) { 254221339Sdim return getCheckerManager().wantsRegionChangeUpdate(state); 255221339Sdim} 256221339Sdim 257234353SdimProgramStateRef 258234353SdimExprEngine::processRegionChanges(ProgramStateRef state, 259249423Sdim const InvalidatedSymbols *invalidated, 260226633Sdim ArrayRef<const MemRegion *> Explicits, 261234353Sdim ArrayRef<const MemRegion *> Regions, 262239462Sdim const CallEvent *Call) { 263223017Sdim return getCheckerManager().runCheckersForRegionChanges(state, invalidated, 264234353Sdim Explicits, Regions, Call); 265221339Sdim} 266221339Sdim 267234353Sdimvoid ExprEngine::printState(raw_ostream &Out, ProgramStateRef State, 268226633Sdim const char *NL, const char *Sep) { 269226633Sdim getCheckerManager().runCheckersForPrintState(Out, State, NL, Sep); 270226633Sdim} 271226633Sdim 272221339Sdimvoid ExprEngine::processEndWorklist(bool hasWorkRemaining) { 273221339Sdim getCheckerManager().runCheckersForEndAnalysis(G, BR, *this); 274221339Sdim} 275221339Sdim 276234353Sdimvoid ExprEngine::processCFGElement(const CFGElement E, ExplodedNode *Pred, 277234353Sdim unsigned StmtIdx, NodeBuilderContext *Ctx) { 278263508Sdim PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext()); 279243830Sdim currStmtIdx = StmtIdx; 280243830Sdim currBldrCtx = Ctx; 281234353Sdim 282221339Sdim switch (E.getKind()) { 283221339Sdim case CFGElement::Statement: 284249423Sdim ProcessStmt(const_cast<Stmt*>(E.castAs<CFGStmt>().getStmt()), Pred); 285221339Sdim return; 286221339Sdim case CFGElement::Initializer: 287249423Sdim ProcessInitializer(E.castAs<CFGInitializer>().getInitializer(), Pred); 288221339Sdim return; 289221339Sdim case CFGElement::AutomaticObjectDtor: 290263508Sdim case CFGElement::DeleteDtor: 291221339Sdim case CFGElement::BaseDtor: 292221339Sdim case CFGElement::MemberDtor: 293221339Sdim case CFGElement::TemporaryDtor: 294249423Sdim ProcessImplicitDtor(E.castAs<CFGImplicitDtor>(), Pred); 295221339Sdim return; 296221339Sdim } 297221339Sdim} 298221339Sdim 299234353Sdimstatic bool shouldRemoveDeadBindings(AnalysisManager &AMgr, 300234353Sdim const CFGStmt S, 301234353Sdim const ExplodedNode *Pred, 302234353Sdim const LocationContext *LC) { 303234353Sdim 304234353Sdim // Are we never purging state values? 305243830Sdim if (AMgr.options.AnalysisPurgeOpt == PurgeNone) 306234353Sdim return false; 307226633Sdim 308234353Sdim // Is this the beginning of a basic block? 309249423Sdim if (Pred->getLocation().getAs<BlockEntrance>()) 310234353Sdim return true; 311234353Sdim 312234353Sdim // Is this on a non-expression? 313234353Sdim if (!isa<Expr>(S.getStmt())) 314234353Sdim return true; 315234353Sdim 316234353Sdim // Run before processing a call. 317243830Sdim if (CallEvent::isCallStmt(S.getStmt())) 318234353Sdim return true; 319234353Sdim 320234353Sdim // Is this an expression that is consumed by another expression? If so, 321234353Sdim // postpone cleaning out the state. 322234353Sdim ParentMap &PM = LC->getAnalysisDeclContext()->getParentMap(); 323234353Sdim return !PM.isConsumedExpr(cast<Expr>(S.getStmt())); 324234353Sdim} 325234353Sdim 326239462Sdimvoid ExprEngine::removeDead(ExplodedNode *Pred, ExplodedNodeSet &Out, 327239462Sdim const Stmt *ReferenceStmt, 328249423Sdim const LocationContext *LC, 329239462Sdim const Stmt *DiagnosticStmt, 330239462Sdim ProgramPoint::Kind K) { 331239462Sdim assert((K == ProgramPoint::PreStmtPurgeDeadSymbolsKind || 332249423Sdim ReferenceStmt == 0 || isa<ReturnStmt>(ReferenceStmt)) 333243830Sdim && "PostStmt is not generally supported by the SymbolReaper yet"); 334249423Sdim assert(LC && "Must pass the current (or expiring) LocationContext"); 335249423Sdim 336249423Sdim if (!DiagnosticStmt) { 337249423Sdim DiagnosticStmt = ReferenceStmt; 338249423Sdim assert(DiagnosticStmt && "Required for clearing a LocationContext"); 339249423Sdim } 340249423Sdim 341239462Sdim NumRemoveDeadBindings++; 342249423Sdim ProgramStateRef CleanedState = Pred->getState(); 343221339Sdim 344249423Sdim // LC is the location context being destroyed, but SymbolReaper wants a 345249423Sdim // location context that is still live. (If this is the top-level stack 346249423Sdim // frame, this will be null.) 347249423Sdim if (!ReferenceStmt) { 348249423Sdim assert(K == ProgramPoint::PostStmtPurgeDeadSymbolsKind && 349249423Sdim "Use PostStmtPurgeDeadSymbolsKind for clearing a LocationContext"); 350249423Sdim LC = LC->getParent(); 351249423Sdim } 352249423Sdim 353249423Sdim const StackFrameContext *SFC = LC ? LC->getCurrentStackFrame() : 0; 354249423Sdim SymbolReaper SymReaper(SFC, ReferenceStmt, SymMgr, getStoreManager()); 355249423Sdim 356239462Sdim getCheckerManager().runCheckersForLiveSymbols(CleanedState, SymReaper); 357221339Sdim 358239462Sdim // Create a state in which dead bindings are removed from the environment 359239462Sdim // and the store. TODO: The function should just return new env and store, 360239462Sdim // not a new state. 361239462Sdim CleanedState = StateMgr.removeDeadBindings(CleanedState, SFC, SymReaper); 362226633Sdim 363221339Sdim // Process any special transfer function for dead symbols. 364234353Sdim // A tag to track convenience transitions, which can be removed at cleanup. 365234353Sdim static SimpleProgramPointTag cleanupTag("ExprEngine : Clean Node"); 366226633Sdim if (!SymReaper.hasDeadSymbols()) { 367226633Sdim // Generate a CleanedNode that has the environment and store cleaned 368226633Sdim // up. Since no symbols are dead, we can optimize and not clean out 369226633Sdim // the constraint manager. 370243830Sdim StmtNodeBuilder Bldr(Pred, Out, *currBldrCtx); 371243830Sdim Bldr.generateNode(DiagnosticStmt, Pred, CleanedState, &cleanupTag, K); 372221339Sdim 373226633Sdim } else { 374226633Sdim // Call checkers with the non-cleaned state so that they could query the 375226633Sdim // values of the soon to be dead symbols. 376226633Sdim ExplodedNodeSet CheckedSet; 377239462Sdim getCheckerManager().runCheckersForDeadSymbols(CheckedSet, Pred, SymReaper, 378239462Sdim DiagnosticStmt, *this, K); 379221339Sdim 380226633Sdim // For each node in CheckedSet, generate CleanedNodes that have the 381226633Sdim // environment, the store, and the constraints cleaned up but have the 382226633Sdim // user-supplied states as the predecessors. 383243830Sdim StmtNodeBuilder Bldr(CheckedSet, Out, *currBldrCtx); 384226633Sdim for (ExplodedNodeSet::const_iterator 385226633Sdim I = CheckedSet.begin(), E = CheckedSet.end(); I != E; ++I) { 386234353Sdim ProgramStateRef CheckerState = (*I)->getState(); 387226633Sdim 388226633Sdim // The constraint manager has not been cleaned up yet, so clean up now. 389226633Sdim CheckerState = getConstraintManager().removeDeadBindings(CheckerState, 390226633Sdim SymReaper); 391226633Sdim 392239462Sdim assert(StateMgr.haveEqualEnvironments(CheckerState, Pred->getState()) && 393226633Sdim "Checkers are not allowed to modify the Environment as a part of " 394226633Sdim "checkDeadSymbols processing."); 395239462Sdim assert(StateMgr.haveEqualStores(CheckerState, Pred->getState()) && 396226633Sdim "Checkers are not allowed to modify the Store as a part of " 397226633Sdim "checkDeadSymbols processing."); 398226633Sdim 399226633Sdim // Create a state based on CleanedState with CheckerState GDM and 400226633Sdim // generate a transition to that state. 401234353Sdim ProgramStateRef CleanedCheckerSt = 402226633Sdim StateMgr.getPersistentStateWithGDM(CleanedState, CheckerState); 403243830Sdim Bldr.generateNode(DiagnosticStmt, *I, CleanedCheckerSt, &cleanupTag, K); 404226633Sdim } 405221339Sdim } 406239462Sdim} 407221339Sdim 408239462Sdimvoid ExprEngine::ProcessStmt(const CFGStmt S, 409239462Sdim ExplodedNode *Pred) { 410239462Sdim // Reclaim any unnecessary nodes in the ExplodedGraph. 411239462Sdim G.reclaimRecentlyAllocatedNodes(); 412239462Sdim 413249423Sdim const Stmt *currStmt = S.getStmt(); 414239462Sdim PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 415243830Sdim currStmt->getLocStart(), 416239462Sdim "Error evaluating statement"); 417239462Sdim 418239462Sdim // Remove dead bindings and symbols. 419239462Sdim ExplodedNodeSet CleanedStates; 420249423Sdim if (shouldRemoveDeadBindings(AMgr, S, Pred, Pred->getLocationContext())){ 421249423Sdim removeDead(Pred, CleanedStates, currStmt, Pred->getLocationContext()); 422239462Sdim } else 423249423Sdim CleanedStates.Add(Pred); 424239462Sdim 425239462Sdim // Visit the statement. 426234353Sdim ExplodedNodeSet Dst; 427239462Sdim for (ExplodedNodeSet::iterator I = CleanedStates.begin(), 428239462Sdim E = CleanedStates.end(); I != E; ++I) { 429234353Sdim ExplodedNodeSet DstI; 430221339Sdim // Visit the statement. 431243830Sdim Visit(currStmt, *I, DstI); 432234353Sdim Dst.insert(DstI); 433221339Sdim } 434221339Sdim 435234353Sdim // Enqueue the new nodes onto the work list. 436243830Sdim Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx); 437221339Sdim} 438221339Sdim 439221339Sdimvoid ExprEngine::ProcessInitializer(const CFGInitializer Init, 440234353Sdim ExplodedNode *Pred) { 441239462Sdim const CXXCtorInitializer *BMI = Init.getInitializer(); 442239462Sdim 443239462Sdim PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 444239462Sdim BMI->getSourceLocation(), 445239462Sdim "Error evaluating initializer"); 446239462Sdim 447249423Sdim // We don't clean up dead bindings here. 448234353Sdim const StackFrameContext *stackFrame = 449234353Sdim cast<StackFrameContext>(Pred->getLocationContext()); 450234353Sdim const CXXConstructorDecl *decl = 451234353Sdim cast<CXXConstructorDecl>(stackFrame->getDecl()); 452243830Sdim 453243830Sdim ProgramStateRef State = Pred->getState(); 454239462Sdim SVal thisVal = State->getSVal(svalBuilder.getCXXThis(decl, stackFrame)); 455221339Sdim 456243830Sdim ExplodedNodeSet Tmp(Pred); 457249423Sdim SVal FieldLoc; 458243830Sdim 459239462Sdim // Evaluate the initializer, if necessary 460221339Sdim if (BMI->isAnyMemberInitializer()) { 461239462Sdim // Constructors build the object directly in the field, 462239462Sdim // but non-objects must be copied in from the initializer. 463249423Sdim const Expr *Init = BMI->getInit()->IgnoreImplicit(); 464243830Sdim if (!isa<CXXConstructExpr>(Init)) { 465249423Sdim const ValueDecl *Field; 466249423Sdim if (BMI->isIndirectMemberInitializer()) { 467249423Sdim Field = BMI->getIndirectMember(); 468239462Sdim FieldLoc = State->getLValue(BMI->getIndirectMember(), thisVal); 469249423Sdim } else { 470249423Sdim Field = BMI->getMember(); 471239462Sdim FieldLoc = State->getLValue(BMI->getMember(), thisVal); 472249423Sdim } 473221339Sdim 474249423Sdim SVal InitVal; 475249423Sdim if (BMI->getNumArrayIndices() > 0) { 476249423Sdim // Handle arrays of trivial type. We can represent this with a 477249423Sdim // primitive load/copy from the base array region. 478249423Sdim const ArraySubscriptExpr *ASE; 479249423Sdim while ((ASE = dyn_cast<ArraySubscriptExpr>(Init))) 480249423Sdim Init = ASE->getBase()->IgnoreImplicit(); 481243830Sdim 482249423Sdim SVal LValue = State->getSVal(Init, stackFrame); 483249423Sdim if (Optional<Loc> LValueLoc = LValue.getAs<Loc>()) 484249423Sdim InitVal = State->getSVal(*LValueLoc); 485249423Sdim 486249423Sdim // If we fail to get the value for some reason, use a symbolic value. 487249423Sdim if (InitVal.isUnknownOrUndef()) { 488249423Sdim SValBuilder &SVB = getSValBuilder(); 489249423Sdim InitVal = SVB.conjureSymbolVal(BMI->getInit(), stackFrame, 490249423Sdim Field->getType(), 491249423Sdim currBldrCtx->blockCount()); 492249423Sdim } 493249423Sdim } else { 494249423Sdim InitVal = State->getSVal(BMI->getInit(), stackFrame); 495249423Sdim } 496249423Sdim 497249423Sdim assert(Tmp.size() == 1 && "have not generated any new nodes yet"); 498249423Sdim assert(*Tmp.begin() == Pred && "have not generated any new nodes yet"); 499243830Sdim Tmp.clear(); 500249423Sdim 501249423Sdim PostInitializer PP(BMI, FieldLoc.getAsRegion(), stackFrame); 502243830Sdim evalBind(Tmp, Init, Pred, FieldLoc, InitVal, /*isInit=*/true, &PP); 503239462Sdim } 504234353Sdim } else { 505239462Sdim assert(BMI->isBaseInitializer() || BMI->isDelegatingInitializer()); 506239462Sdim // We already did all the work when visiting the CXXConstructExpr. 507239462Sdim } 508221339Sdim 509243830Sdim // Construct PostInitializer nodes whether the state changed or not, 510239462Sdim // so that the diagnostics don't get confused. 511249423Sdim PostInitializer PP(BMI, FieldLoc.getAsRegion(), stackFrame); 512243830Sdim ExplodedNodeSet Dst; 513243830Sdim NodeBuilder Bldr(Tmp, Dst, *currBldrCtx); 514243830Sdim for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I != E; ++I) { 515243830Sdim ExplodedNode *N = *I; 516243830Sdim Bldr.generateNode(PP, N->getState(), N); 517243830Sdim } 518221339Sdim 519234353Sdim // Enqueue the new nodes onto the work list. 520243830Sdim Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx); 521221339Sdim} 522221339Sdim 523221339Sdimvoid ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D, 524234353Sdim ExplodedNode *Pred) { 525234353Sdim ExplodedNodeSet Dst; 526221339Sdim switch (D.getKind()) { 527221339Sdim case CFGElement::AutomaticObjectDtor: 528249423Sdim ProcessAutomaticObjDtor(D.castAs<CFGAutomaticObjDtor>(), Pred, Dst); 529221339Sdim break; 530221339Sdim case CFGElement::BaseDtor: 531249423Sdim ProcessBaseDtor(D.castAs<CFGBaseDtor>(), Pred, Dst); 532221339Sdim break; 533221339Sdim case CFGElement::MemberDtor: 534249423Sdim ProcessMemberDtor(D.castAs<CFGMemberDtor>(), Pred, Dst); 535221339Sdim break; 536221339Sdim case CFGElement::TemporaryDtor: 537249423Sdim ProcessTemporaryDtor(D.castAs<CFGTemporaryDtor>(), Pred, Dst); 538221339Sdim break; 539263508Sdim case CFGElement::DeleteDtor: 540263508Sdim ProcessDeleteDtor(D.castAs<CFGDeleteDtor>(), Pred, Dst); 541263508Sdim break; 542221339Sdim default: 543221339Sdim llvm_unreachable("Unexpected dtor kind."); 544221339Sdim } 545234353Sdim 546234353Sdim // Enqueue the new nodes onto the work list. 547243830Sdim Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx); 548221339Sdim} 549221339Sdim 550234353Sdimvoid ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor Dtor, 551234353Sdim ExplodedNode *Pred, 552234353Sdim ExplodedNodeSet &Dst) { 553234353Sdim const VarDecl *varDecl = Dtor.getVarDecl(); 554221339Sdim QualType varType = varDecl->getType(); 555221339Sdim 556249423Sdim ProgramStateRef state = Pred->getState(); 557249423Sdim SVal dest = state->getLValue(varDecl, Pred->getLocationContext()); 558249423Sdim const MemRegion *Region = dest.castAs<loc::MemRegionVal>().getRegion(); 559249423Sdim 560249423Sdim if (const ReferenceType *refType = varType->getAs<ReferenceType>()) { 561221339Sdim varType = refType->getPointeeType(); 562249423Sdim Region = state->getSVal(Region).getAsRegion(); 563249423Sdim } 564221339Sdim 565249423Sdim VisitCXXDestructor(varType, Region, Dtor.getTriggerStmt(), /*IsBase=*/ false, 566249423Sdim Pred, Dst); 567221339Sdim} 568221339Sdim 569263508Sdimvoid ExprEngine::ProcessDeleteDtor(const CFGDeleteDtor Dtor, 570263508Sdim ExplodedNode *Pred, 571263508Sdim ExplodedNodeSet &Dst) { 572263508Sdim ProgramStateRef State = Pred->getState(); 573263508Sdim const LocationContext *LCtx = Pred->getLocationContext(); 574263508Sdim const CXXDeleteExpr *DE = Dtor.getDeleteExpr(); 575263508Sdim const Stmt *Arg = DE->getArgument(); 576263508Sdim SVal ArgVal = State->getSVal(Arg, LCtx); 577263508Sdim 578263508Sdim // If the argument to delete is known to be a null value, 579263508Sdim // don't run destructor. 580263508Sdim if (State->isNull(ArgVal).isConstrainedTrue()) { 581263508Sdim QualType DTy = DE->getDestroyedType(); 582263508Sdim QualType BTy = getContext().getBaseElementType(DTy); 583263508Sdim const CXXRecordDecl *RD = BTy->getAsCXXRecordDecl(); 584263508Sdim const CXXDestructorDecl *Dtor = RD->getDestructor(); 585263508Sdim 586263508Sdim PostImplicitCall PP(Dtor, DE->getLocStart(), LCtx); 587263508Sdim NodeBuilder Bldr(Pred, Dst, *currBldrCtx); 588263508Sdim Bldr.generateNode(PP, Pred->getState(), Pred); 589263508Sdim return; 590263508Sdim } 591263508Sdim 592263508Sdim VisitCXXDestructor(DE->getDestroyedType(), 593263508Sdim ArgVal.getAsRegion(), 594263508Sdim DE, /*IsBase=*/ false, 595263508Sdim Pred, Dst); 596263508Sdim} 597263508Sdim 598221339Sdimvoid ExprEngine::ProcessBaseDtor(const CFGBaseDtor D, 599239462Sdim ExplodedNode *Pred, ExplodedNodeSet &Dst) { 600239462Sdim const LocationContext *LCtx = Pred->getLocationContext(); 601239462Sdim ProgramStateRef State = Pred->getState(); 602221339Sdim 603239462Sdim const CXXDestructorDecl *CurDtor = cast<CXXDestructorDecl>(LCtx->getDecl()); 604239462Sdim Loc ThisPtr = getSValBuilder().getCXXThis(CurDtor, 605239462Sdim LCtx->getCurrentStackFrame()); 606239462Sdim SVal ThisVal = Pred->getState()->getSVal(ThisPtr); 607239462Sdim 608239462Sdim // Create the base object region. 609249423Sdim const CXXBaseSpecifier *Base = D.getBaseSpecifier(); 610249423Sdim QualType BaseTy = Base->getType(); 611249423Sdim SVal BaseVal = getStoreManager().evalDerivedToBase(ThisVal, BaseTy, 612249423Sdim Base->isVirtual()); 613239462Sdim 614249423Sdim VisitCXXDestructor(BaseTy, BaseVal.castAs<loc::MemRegionVal>().getRegion(), 615249423Sdim CurDtor->getBody(), /*IsBase=*/ true, Pred, Dst); 616239462Sdim} 617239462Sdim 618221339Sdimvoid ExprEngine::ProcessMemberDtor(const CFGMemberDtor D, 619239462Sdim ExplodedNode *Pred, ExplodedNodeSet &Dst) { 620239462Sdim const FieldDecl *Member = D.getFieldDecl(); 621239462Sdim ProgramStateRef State = Pred->getState(); 622239462Sdim const LocationContext *LCtx = Pred->getLocationContext(); 623221339Sdim 624239462Sdim const CXXDestructorDecl *CurDtor = cast<CXXDestructorDecl>(LCtx->getDecl()); 625239462Sdim Loc ThisVal = getSValBuilder().getCXXThis(CurDtor, 626239462Sdim LCtx->getCurrentStackFrame()); 627249423Sdim SVal FieldVal = 628249423Sdim State->getLValue(Member, State->getSVal(ThisVal).castAs<Loc>()); 629239462Sdim 630239462Sdim VisitCXXDestructor(Member->getType(), 631249423Sdim FieldVal.castAs<loc::MemRegionVal>().getRegion(), 632243830Sdim CurDtor->getBody(), /*IsBase=*/false, Pred, Dst); 633239462Sdim} 634239462Sdim 635221339Sdimvoid ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D, 636234353Sdim ExplodedNode *Pred, 637263508Sdim ExplodedNodeSet &Dst) { 638221339Sdim 639263508Sdim QualType varType = D.getBindTemporaryExpr()->getSubExpr()->getType(); 640263508Sdim 641263508Sdim // FIXME: Inlining of temporary destructors is not supported yet anyway, so we 642263508Sdim // just put a NULL region for now. This will need to be changed later. 643263508Sdim VisitCXXDestructor(varType, NULL, D.getBindTemporaryExpr(), 644263508Sdim /*IsBase=*/ false, Pred, Dst); 645263508Sdim} 646263508Sdim 647239462Sdimvoid ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, 648234353Sdim ExplodedNodeSet &DstTop) { 649221339Sdim PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 650221339Sdim S->getLocStart(), 651221339Sdim "Error evaluating statement"); 652234353Sdim ExplodedNodeSet Dst; 653243830Sdim StmtNodeBuilder Bldr(Pred, DstTop, *currBldrCtx); 654221339Sdim 655249423Sdim 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: 664251662Sdim case Stmt::MSPropertyRefExprClass: 665221339Sdim case Stmt::CXXUnresolvedConstructExprClass: 666221339Sdim case Stmt::DependentScopeDeclRefExprClass: 667221339Sdim case Stmt::UnaryTypeTraitExprClass: 668221339Sdim case Stmt::BinaryTypeTraitExprClass: 669234353Sdim 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: 677243830Sdim case Stmt::FunctionParmPackExprClass: 678221339Sdim case Stmt::SEHTryStmtClass: 679221339Sdim case Stmt::SEHExceptStmtClass: 680234353Sdim case Stmt::LambdaExprClass: 681234353Sdim case Stmt::SEHFinallyStmtClass: { 682243830Sdim const ExplodedNode *node = Bldr.generateSink(S, Pred, Pred->getState()); 683243830Sdim 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: 697226633Sdim 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: 709234353Sdim case Expr::MSDependentExistsStmtClass: 710251662Sdim case Stmt::CapturedStmtClass: 711263508Sdim case Stmt::OMPParallelDirectiveClass: 712221339Sdim llvm_unreachable("Stmt should not be in analyzer evaluation loop"); 713221339Sdim 714239462Sdim case Stmt::ObjCSubscriptRefExprClass: 715239462Sdim case Stmt::ObjCPropertyRefExprClass: 716239462Sdim llvm_unreachable("These are handled by PseudoObjectExpr"); 717239462Sdim 718221339Sdim case Stmt::GNUNullExprClass: { 719224145Sdim // GNU __null is a pointer-width integer, not an actual pointer. 720234353Sdim ProgramStateRef state = Pred->getState(); 721234353Sdim state = state->BindExpr(S, Pred->getLocationContext(), 722234353Sdim svalBuilder.makeIntValWithPtrWidth(0, false)); 723234353Sdim Bldr.generateNode(S, Pred, state); 724221339Sdim break; 725221339Sdim } 726221339Sdim 727221339Sdim case Stmt::ObjCAtSynchronizedStmtClass: 728234353Sdim Bldr.takeNodes(Pred); 729221339Sdim VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S), Pred, Dst); 730234353Sdim Bldr.addNodes(Dst); 731221339Sdim break; 732221339Sdim 733234353Sdim case Stmt::ExprWithCleanupsClass: 734234353Sdim // 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: 752263508Sdim case Stmt::ConvertVectorExprClass: 753221339Sdim case Stmt::VAArgExprClass: 754221339Sdim case Stmt::CUDAKernelCallExprClass: 755221339Sdim case Stmt::OpaqueValueExprClass: 756223017Sdim case Stmt::AsTypeExprClass: 757226633Sdim case Stmt::AtomicExprClass: 758234353Sdim // Fall through. 759221339Sdim 760221339Sdim // Cases we intentionally don't evaluate, since they don't need 761221339Sdim // to be explicitly evaluated. 762221339Sdim case Stmt::AddrLabelExprClass: 763263508Sdim case Stmt::AttributedStmtClass: 764221339Sdim case Stmt::IntegerLiteralClass: 765221339Sdim case Stmt::CharacterLiteralClass: 766239462Sdim case Stmt::ImplicitValueInitExprClass: 767239462Sdim case Stmt::CXXScalarValueInitExprClass: 768221339Sdim case Stmt::CXXBoolLiteralExprClass: 769234353Sdim case Stmt::ObjCBoolLiteralExprClass: 770221339Sdim case Stmt::FloatingLiteralClass: 771221339Sdim case Stmt::SizeOfPackExprClass: 772234353Sdim case Stmt::StringLiteralClass: 773234353Sdim case Stmt::ObjCStringLiteralClass: 774234353Sdim case Stmt::CXXBindTemporaryExprClass: 775263508Sdim case Stmt::CXXPseudoDestructorExprClass: 776239462Sdim case Stmt::SubstNonTypeTemplateParmExprClass: 777234353Sdim case Stmt::CXXNullPtrLiteralExprClass: { 778234353Sdim Bldr.takeNodes(Pred); 779234353Sdim ExplodedNodeSet preVisit; 780234353Sdim getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this); 781234353Sdim getCheckerManager().runCheckersForPostStmt(Dst, preVisit, S, *this); 782234353Sdim Bldr.addNodes(Dst); 783221339Sdim break; 784234353Sdim } 785221339Sdim 786263508Sdim case Stmt::CXXDefaultArgExprClass: 787263508Sdim case Stmt::CXXDefaultInitExprClass: { 788249423Sdim Bldr.takeNodes(Pred); 789249423Sdim ExplodedNodeSet PreVisit; 790249423Sdim getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this); 791249423Sdim 792249423Sdim ExplodedNodeSet Tmp; 793249423Sdim StmtNodeBuilder Bldr2(PreVisit, Tmp, *currBldrCtx); 794249423Sdim 795263508Sdim const Expr *ArgE; 796263508Sdim if (const CXXDefaultArgExpr *DefE = dyn_cast<CXXDefaultArgExpr>(S)) 797263508Sdim ArgE = DefE->getExpr(); 798263508Sdim else if (const CXXDefaultInitExpr *DefE = dyn_cast<CXXDefaultInitExpr>(S)) 799263508Sdim ArgE = DefE->getExpr(); 800263508Sdim else 801263508Sdim llvm_unreachable("unknown constant wrapper kind"); 802249423Sdim 803251662Sdim bool IsTemporary = false; 804251662Sdim if (const MaterializeTemporaryExpr *MTE = 805251662Sdim dyn_cast<MaterializeTemporaryExpr>(ArgE)) { 806251662Sdim ArgE = MTE->GetTemporaryExpr(); 807251662Sdim IsTemporary = true; 808251662Sdim } 809249423Sdim 810251662Sdim Optional<SVal> ConstantVal = svalBuilder.getConstantVal(ArgE); 811251662Sdim if (!ConstantVal) 812251662Sdim ConstantVal = UnknownVal(); 813251662Sdim 814263508Sdim const LocationContext *LCtx = Pred->getLocationContext(); 815249423Sdim for (ExplodedNodeSet::iterator I = PreVisit.begin(), E = PreVisit.end(); 816249423Sdim I != E; ++I) { 817249423Sdim ProgramStateRef State = (*I)->getState(); 818263508Sdim State = State->BindExpr(S, LCtx, *ConstantVal); 819251662Sdim if (IsTemporary) 820263508Sdim State = createTemporaryRegionIfNeeded(State, LCtx, 821263508Sdim cast<Expr>(S), 822263508Sdim cast<Expr>(S)); 823249423Sdim Bldr2.generateNode(S, *I, State); 824249423Sdim } 825249423Sdim 826249423Sdim getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this); 827249423Sdim Bldr.addNodes(Dst); 828249423Sdim break; 829249423Sdim } 830249423Sdim 831263508Sdim // Cases we evaluate as opaque expressions, conjuring a symbol. 832263508Sdim case Stmt::CXXStdInitializerListExprClass: 833234353Sdim case Expr::ObjCArrayLiteralClass: 834239462Sdim case Expr::ObjCDictionaryLiteralClass: 835239462Sdim case Expr::ObjCBoxedExprClass: { 836234353Sdim Bldr.takeNodes(Pred); 837234353Sdim 838234353Sdim ExplodedNodeSet preVisit; 839234353Sdim getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this); 840234353Sdim 841234353Sdim ExplodedNodeSet Tmp; 842243830Sdim StmtNodeBuilder Bldr2(preVisit, Tmp, *currBldrCtx); 843234353Sdim 844239462Sdim const Expr *Ex = cast<Expr>(S); 845239462Sdim QualType resultType = Ex->getType(); 846239462Sdim 847234353Sdim for (ExplodedNodeSet::iterator it = preVisit.begin(), et = preVisit.end(); 848234353Sdim it != et; ++it) { 849234353Sdim ExplodedNode *N = *it; 850234353Sdim const LocationContext *LCtx = N->getLocationContext(); 851243830Sdim SVal result = svalBuilder.conjureSymbolVal(0, Ex, LCtx, resultType, 852243830Sdim currBldrCtx->blockCount()); 853234353Sdim ProgramStateRef state = N->getState()->BindExpr(Ex, LCtx, result); 854234353Sdim Bldr2.generateNode(S, N, state); 855234353Sdim } 856234353Sdim 857234353Sdim getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this); 858234353Sdim Bldr.addNodes(Dst); 859234353Sdim break; 860234353Sdim } 861234353Sdim 862221339Sdim case Stmt::ArraySubscriptExprClass: 863234353Sdim Bldr.takeNodes(Pred); 864221339Sdim VisitLvalArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Pred, Dst); 865234353Sdim Bldr.addNodes(Dst); 866221339Sdim break; 867221339Sdim 868243830Sdim case Stmt::GCCAsmStmtClass: 869234353Sdim Bldr.takeNodes(Pred); 870243830Sdim VisitGCCAsmStmt(cast<GCCAsmStmt>(S), Pred, Dst); 871234353Sdim Bldr.addNodes(Dst); 872221339Sdim break; 873221339Sdim 874239462Sdim case Stmt::MSAsmStmtClass: 875239462Sdim Bldr.takeNodes(Pred); 876239462Sdim VisitMSAsmStmt(cast<MSAsmStmt>(S), Pred, Dst); 877239462Sdim Bldr.addNodes(Dst); 878239462Sdim break; 879239462Sdim 880221339Sdim case Stmt::BlockExprClass: 881234353Sdim Bldr.takeNodes(Pred); 882221339Sdim VisitBlockExpr(cast<BlockExpr>(S), Pred, Dst); 883234353Sdim Bldr.addNodes(Dst); 884221339Sdim break; 885221339Sdim 886221339Sdim case Stmt::BinaryOperatorClass: { 887221339Sdim const BinaryOperator* B = cast<BinaryOperator>(S); 888221339Sdim if (B->isLogicalOp()) { 889234353Sdim Bldr.takeNodes(Pred); 890221339Sdim VisitLogicalExpr(B, Pred, Dst); 891234353Sdim Bldr.addNodes(Dst); 892221339Sdim break; 893221339Sdim } 894221339Sdim else if (B->getOpcode() == BO_Comma) { 895234353Sdim ProgramStateRef state = Pred->getState(); 896234353Sdim Bldr.generateNode(B, Pred, 897234353Sdim state->BindExpr(B, Pred->getLocationContext(), 898234353Sdim state->getSVal(B->getRHS(), 899234353Sdim Pred->getLocationContext()))); 900221339Sdim break; 901221339Sdim } 902221339Sdim 903234353Sdim Bldr.takeNodes(Pred); 904234353Sdim 905243830Sdim if (AMgr.options.eagerlyAssumeBinOpBifurcation && 906221339Sdim (B->isRelationalOp() || B->isEqualityOp())) { 907221339Sdim ExplodedNodeSet Tmp; 908221339Sdim VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Tmp); 909243830Sdim evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, cast<Expr>(S)); 910221339Sdim } 911221339Sdim else 912221339Sdim VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst); 913221339Sdim 914234353Sdim Bldr.addNodes(Dst); 915221339Sdim break; 916221339Sdim } 917221339Sdim 918243830Sdim case Stmt::CXXOperatorCallExprClass: { 919243830Sdim const CXXOperatorCallExpr *OCE = cast<CXXOperatorCallExpr>(S); 920243830Sdim 921243830Sdim // For instance method operators, make sure the 'this' argument has a 922243830Sdim // valid region. 923243830Sdim const Decl *Callee = OCE->getCalleeDecl(); 924243830Sdim if (const CXXMethodDecl *MD = dyn_cast_or_null<CXXMethodDecl>(Callee)) { 925243830Sdim if (MD->isInstance()) { 926243830Sdim ProgramStateRef State = Pred->getState(); 927243830Sdim const LocationContext *LCtx = Pred->getLocationContext(); 928243830Sdim ProgramStateRef NewState = 929243830Sdim createTemporaryRegionIfNeeded(State, LCtx, OCE->getArg(0)); 930251662Sdim if (NewState != State) { 931243830Sdim Pred = Bldr.generateNode(OCE, Pred, NewState, /*Tag=*/0, 932243830Sdim ProgramPoint::PreStmtKind); 933251662Sdim // Did we cache out? 934251662Sdim if (!Pred) 935251662Sdim break; 936251662Sdim } 937243830Sdim } 938243830Sdim } 939243830Sdim // FALLTHROUGH 940243830Sdim } 941221339Sdim case Stmt::CallExprClass: 942234353Sdim case Stmt::CXXMemberCallExprClass: 943234353Sdim case Stmt::UserDefinedLiteralClass: { 944234353Sdim Bldr.takeNodes(Pred); 945221339Sdim VisitCallExpr(cast<CallExpr>(S), Pred, Dst); 946234353Sdim Bldr.addNodes(Dst); 947221339Sdim break; 948221339Sdim } 949234353Sdim 950234353Sdim case Stmt::CXXCatchStmtClass: { 951234353Sdim Bldr.takeNodes(Pred); 952234353Sdim VisitCXXCatchStmt(cast<CXXCatchStmt>(S), Pred, Dst); 953234353Sdim Bldr.addNodes(Dst); 954234353Sdim break; 955234353Sdim } 956221339Sdim 957226633Sdim case Stmt::CXXTemporaryObjectExprClass: 958239462Sdim case Stmt::CXXConstructExprClass: { 959234353Sdim Bldr.takeNodes(Pred); 960239462Sdim VisitCXXConstructExpr(cast<CXXConstructExpr>(S), Pred, Dst); 961234353Sdim Bldr.addNodes(Dst); 962221339Sdim break; 963221339Sdim } 964221339Sdim 965221339Sdim case Stmt::CXXNewExprClass: { 966234353Sdim Bldr.takeNodes(Pred); 967249423Sdim ExplodedNodeSet PostVisit; 968249423Sdim VisitCXXNewExpr(cast<CXXNewExpr>(S), Pred, PostVisit); 969249423Sdim getCheckerManager().runCheckersForPostStmt(Dst, PostVisit, S, *this); 970234353Sdim Bldr.addNodes(Dst); 971221339Sdim break; 972221339Sdim } 973221339Sdim 974221339Sdim case Stmt::CXXDeleteExprClass: { 975234353Sdim Bldr.takeNodes(Pred); 976249423Sdim ExplodedNodeSet PreVisit; 977221339Sdim const CXXDeleteExpr *CDE = cast<CXXDeleteExpr>(S); 978249423Sdim getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this); 979249423Sdim 980249423Sdim for (ExplodedNodeSet::iterator i = PreVisit.begin(), 981249423Sdim e = PreVisit.end(); i != e ; ++i) 982249423Sdim VisitCXXDeleteExpr(CDE, *i, Dst); 983249423Sdim 984234353Sdim 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 991234353Sdim Bldr.takeNodes(Pred); 992226633Sdim const ChooseExpr *C = cast<ChooseExpr>(S); 993221339Sdim VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst); 994234353Sdim Bldr.addNodes(Dst); 995221339Sdim break; 996221339Sdim } 997221339Sdim 998221339Sdim case Stmt::CompoundAssignOperatorClass: 999234353Sdim Bldr.takeNodes(Pred); 1000221339Sdim VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst); 1001234353Sdim Bldr.addNodes(Dst); 1002221339Sdim break; 1003221339Sdim 1004221339Sdim case Stmt::CompoundLiteralExprClass: 1005234353Sdim Bldr.takeNodes(Pred); 1006221339Sdim VisitCompoundLiteralExpr(cast<CompoundLiteralExpr>(S), Pred, Dst); 1007234353Sdim Bldr.addNodes(Dst); 1008221339Sdim break; 1009221339Sdim 1010221339Sdim case Stmt::BinaryConditionalOperatorClass: 1011221339Sdim case Stmt::ConditionalOperatorClass: { // '?' operator 1012234353Sdim Bldr.takeNodes(Pred); 1013221339Sdim const AbstractConditionalOperator *C 1014221339Sdim = cast<AbstractConditionalOperator>(S); 1015221339Sdim VisitGuardedExpr(C, C->getTrueExpr(), C->getFalseExpr(), Pred, Dst); 1016234353Sdim Bldr.addNodes(Dst); 1017221339Sdim break; 1018221339Sdim } 1019221339Sdim 1020221339Sdim case Stmt::CXXThisExprClass: 1021234353Sdim Bldr.takeNodes(Pred); 1022221339Sdim VisitCXXThisExpr(cast<CXXThisExpr>(S), Pred, Dst); 1023234353Sdim Bldr.addNodes(Dst); 1024221339Sdim break; 1025221339Sdim 1026221339Sdim case Stmt::DeclRefExprClass: { 1027234353Sdim Bldr.takeNodes(Pred); 1028221339Sdim const DeclRefExpr *DE = cast<DeclRefExpr>(S); 1029221339Sdim VisitCommonDeclRefExpr(DE, DE->getDecl(), Pred, Dst); 1030234353Sdim Bldr.addNodes(Dst); 1031221339Sdim break; 1032221339Sdim } 1033221339Sdim 1034221339Sdim case Stmt::DeclStmtClass: 1035234353Sdim Bldr.takeNodes(Pred); 1036221339Sdim VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst); 1037234353Sdim 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: { 1048234353Sdim Bldr.takeNodes(Pred); 1049226633Sdim 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); 1063234353Sdim Bldr.addNodes(Dst); 1064221339Sdim break; 1065221339Sdim } 1066221339Sdim 1067224145Sdim case Expr::MaterializeTemporaryExprClass: { 1068234353Sdim Bldr.takeNodes(Pred); 1069243830Sdim const MaterializeTemporaryExpr *MTE = cast<MaterializeTemporaryExpr>(S); 1070243830Sdim CreateCXXTemporaryObject(MTE, Pred, Dst); 1071234353Sdim Bldr.addNodes(Dst); 1072224145Sdim break; 1073224145Sdim } 1074224145Sdim 1075221339Sdim case Stmt::InitListExprClass: 1076234353Sdim Bldr.takeNodes(Pred); 1077221339Sdim VisitInitListExpr(cast<InitListExpr>(S), Pred, Dst); 1078234353Sdim Bldr.addNodes(Dst); 1079221339Sdim break; 1080221339Sdim 1081221339Sdim case Stmt::MemberExprClass: 1082234353Sdim Bldr.takeNodes(Pred); 1083221339Sdim VisitMemberExpr(cast<MemberExpr>(S), Pred, Dst); 1084234353Sdim Bldr.addNodes(Dst); 1085221339Sdim break; 1086234353Sdim 1087221339Sdim case Stmt::ObjCIvarRefExprClass: 1088234353Sdim Bldr.takeNodes(Pred); 1089221339Sdim VisitLvalObjCIvarRefExpr(cast<ObjCIvarRefExpr>(S), Pred, Dst); 1090234353Sdim Bldr.addNodes(Dst); 1091221339Sdim break; 1092221339Sdim 1093221339Sdim case Stmt::ObjCForCollectionStmtClass: 1094234353Sdim Bldr.takeNodes(Pred); 1095221339Sdim VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S), Pred, Dst); 1096234353Sdim Bldr.addNodes(Dst); 1097221339Sdim break; 1098221339Sdim 1099239462Sdim case Stmt::ObjCMessageExprClass: 1100234353Sdim Bldr.takeNodes(Pred); 1101239462Sdim VisitObjCMessage(cast<ObjCMessageExpr>(S), Pred, Dst); 1102234353Sdim Bldr.addNodes(Dst); 1103221339Sdim break; 1104221339Sdim 1105243830Sdim case Stmt::ObjCAtThrowStmtClass: 1106243830Sdim case Stmt::CXXThrowExprClass: 1107221339Sdim // FIXME: This is not complete. We basically treat @throw as 1108221339Sdim // an abort. 1109243830Sdim Bldr.generateSink(S, Pred, Pred->getState()); 1110221339Sdim break; 1111221339Sdim 1112221339Sdim case Stmt::ReturnStmtClass: 1113234353Sdim Bldr.takeNodes(Pred); 1114221339Sdim VisitReturnStmt(cast<ReturnStmt>(S), Pred, Dst); 1115234353Sdim Bldr.addNodes(Dst); 1116221339Sdim break; 1117221339Sdim 1118221339Sdim case Stmt::OffsetOfExprClass: 1119234353Sdim Bldr.takeNodes(Pred); 1120221339Sdim VisitOffsetOfExpr(cast<OffsetOfExpr>(S), Pred, Dst); 1121234353Sdim Bldr.addNodes(Dst); 1122221339Sdim break; 1123221339Sdim 1124221339Sdim case Stmt::UnaryExprOrTypeTraitExprClass: 1125234353Sdim Bldr.takeNodes(Pred); 1126221339Sdim VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S), 1127221339Sdim Pred, Dst); 1128234353Sdim Bldr.addNodes(Dst); 1129221339Sdim break; 1130221339Sdim 1131221339Sdim case Stmt::StmtExprClass: { 1132226633Sdim 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 1141226633Sdim if (Expr *LastExpr = dyn_cast<Expr>(*SE->getSubStmt()->body_rbegin())) { 1142234353Sdim ProgramStateRef state = Pred->getState(); 1143234353Sdim Bldr.generateNode(SE, Pred, 1144234353Sdim state->BindExpr(SE, Pred->getLocationContext(), 1145234353Sdim state->getSVal(LastExpr, 1146234353Sdim Pred->getLocationContext()))); 1147221339Sdim } 1148221339Sdim break; 1149221339Sdim } 1150221339Sdim 1151221339Sdim case Stmt::UnaryOperatorClass: { 1152234353Sdim Bldr.takeNodes(Pred); 1153221339Sdim const UnaryOperator *U = cast<UnaryOperator>(S); 1154243830Sdim if (AMgr.options.eagerlyAssumeBinOpBifurcation && (U->getOpcode() == UO_LNot)) { 1155221339Sdim ExplodedNodeSet Tmp; 1156221339Sdim VisitUnaryOperator(U, Pred, Tmp); 1157243830Sdim evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, U); 1158221339Sdim } 1159221339Sdim else 1160221339Sdim VisitUnaryOperator(U, Pred, Dst); 1161234353Sdim Bldr.addNodes(Dst); 1162221339Sdim break; 1163221339Sdim } 1164234353Sdim 1165234353Sdim case Stmt::PseudoObjectExprClass: { 1166234353Sdim Bldr.takeNodes(Pred); 1167234353Sdim ProgramStateRef state = Pred->getState(); 1168234353Sdim const PseudoObjectExpr *PE = cast<PseudoObjectExpr>(S); 1169234353Sdim if (const Expr *Result = PE->getResultExpr()) { 1170234353Sdim SVal V = state->getSVal(Result, Pred->getLocationContext()); 1171234353Sdim Bldr.generateNode(S, Pred, 1172234353Sdim state->BindExpr(S, Pred->getLocationContext(), V)); 1173234353Sdim } 1174234353Sdim else 1175234353Sdim Bldr.generateNode(S, Pred, 1176234353Sdim state->BindExpr(S, Pred->getLocationContext(), 1177234353Sdim UnknownVal())); 1178234353Sdim 1179234353Sdim Bldr.addNodes(Dst); 1180234353Sdim break; 1181234353Sdim } 1182221339Sdim } 1183221339Sdim} 1184221339Sdim 1185234353Sdimbool ExprEngine::replayWithoutInlining(ExplodedNode *N, 1186234353Sdim const LocationContext *CalleeLC) { 1187234353Sdim const StackFrameContext *CalleeSF = CalleeLC->getCurrentStackFrame(); 1188234353Sdim const StackFrameContext *CallerSF = CalleeSF->getParent()->getCurrentStackFrame(); 1189234353Sdim assert(CalleeSF && CallerSF); 1190234353Sdim ExplodedNode *BeforeProcessingCall = 0; 1191239462Sdim const Stmt *CE = CalleeSF->getCallSite(); 1192221339Sdim 1193234353Sdim // Find the first node before we started processing the call expression. 1194234353Sdim while (N) { 1195234353Sdim ProgramPoint L = N->getLocation(); 1196234353Sdim BeforeProcessingCall = N; 1197234353Sdim N = N->pred_empty() ? NULL : *(N->pred_begin()); 1198234353Sdim 1199234353Sdim // Skip the nodes corresponding to the inlined code. 1200234353Sdim if (L.getLocationContext()->getCurrentStackFrame() != CallerSF) 1201234353Sdim continue; 1202234353Sdim // We reached the caller. Find the node right before we started 1203239462Sdim // processing the call. 1204239462Sdim if (L.isPurgeKind()) 1205234353Sdim continue; 1206249423Sdim if (L.getAs<PreImplicitCall>()) 1207239462Sdim continue; 1208249423Sdim if (L.getAs<CallEnter>()) 1209239462Sdim continue; 1210249423Sdim if (Optional<StmtPoint> SP = L.getAs<StmtPoint>()) 1211239462Sdim if (SP->getStmt() == CE) 1212234353Sdim continue; 1213234353Sdim break; 1214234353Sdim } 1215234353Sdim 1216234353Sdim if (!BeforeProcessingCall) 1217234353Sdim return false; 1218234353Sdim 1219234353Sdim // TODO: Clean up the unneeded nodes. 1220234353Sdim 1221234353Sdim // Build an Epsilon node from which we will restart the analyzes. 1222239462Sdim // Note that CE is permitted to be NULL! 1223234353Sdim ProgramPoint NewNodeLoc = 1224234353Sdim EpsilonPoint(BeforeProcessingCall->getLocationContext(), CE); 1225234353Sdim // Add the special flag to GDM to signal retrying with no inlining. 1226234353Sdim // Note, changing the state ensures that we are not going to cache out. 1227234353Sdim ProgramStateRef NewNodeState = BeforeProcessingCall->getState(); 1228249423Sdim NewNodeState = 1229249423Sdim NewNodeState->set<ReplayWithoutInlining>(const_cast<Stmt *>(CE)); 1230234353Sdim 1231234353Sdim // Make the new node a successor of BeforeProcessingCall. 1232234353Sdim bool IsNew = false; 1233234353Sdim ExplodedNode *NewNode = G.getNode(NewNodeLoc, NewNodeState, false, &IsNew); 1234234353Sdim // We cached out at this point. Caching out is common due to us backtracking 1235234353Sdim // from the inlined function, which might spawn several paths. 1236234353Sdim if (!IsNew) 1237234353Sdim return true; 1238234353Sdim 1239234353Sdim NewNode->addPredecessor(BeforeProcessingCall, G); 1240234353Sdim 1241234353Sdim // Add the new node to the work list. 1242234353Sdim Engine.enqueueStmtNode(NewNode, CalleeSF->getCallSiteBlock(), 1243234353Sdim CalleeSF->getIndex()); 1244234353Sdim NumTimesRetriedWithoutInlining++; 1245234353Sdim return true; 1246234353Sdim} 1247234353Sdim 1248234353Sdim/// Block entrance. (Update counters). 1249234353Sdimvoid ExprEngine::processCFGBlockEntrance(const BlockEdge &L, 1250243830Sdim NodeBuilderWithSinks &nodeBuilder, 1251243830Sdim ExplodedNode *Pred) { 1252263508Sdim PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext()); 1253263508Sdim 1254221339Sdim // FIXME: Refactor this into a checker. 1255243830Sdim if (nodeBuilder.getContext().blockCount() >= AMgr.options.maxBlockVisitOnPath) { 1256226633Sdim static SimpleProgramPointTag tag("ExprEngine : Block count exceeded"); 1257234353Sdim const ExplodedNode *Sink = 1258243830Sdim nodeBuilder.generateSink(Pred->getState(), Pred, &tag); 1259221339Sdim 1260234353Sdim // Check if we stopped at the top level function or not. 1261234353Sdim // Root node should have the location context of the top most function. 1262243830Sdim const LocationContext *CalleeLC = Pred->getLocation().getLocationContext(); 1263234353Sdim const LocationContext *CalleeSF = CalleeLC->getCurrentStackFrame(); 1264234353Sdim const LocationContext *RootLC = 1265234353Sdim (*G.roots_begin())->getLocation().getLocationContext(); 1266234353Sdim if (RootLC->getCurrentStackFrame() != CalleeSF) { 1267234353Sdim Engine.FunctionSummaries->markReachedMaxBlockCount(CalleeSF->getDecl()); 1268221339Sdim 1269234353Sdim // Re-run the call evaluation without inlining it, by storing the 1270234353Sdim // no-inlining policy in the state and enqueuing the new work item on 1271234353Sdim // the list. Replay should almost never fail. Use the stats to catch it 1272234353Sdim // if it does. 1273243830Sdim if ((!AMgr.options.NoRetryExhausted && 1274243830Sdim replayWithoutInlining(Pred, CalleeLC))) 1275234353Sdim return; 1276234353Sdim NumMaxBlockCountReachedInInlined++; 1277234353Sdim } else 1278234353Sdim NumMaxBlockCountReached++; 1279234353Sdim 1280234353Sdim // Make sink nodes as exhausted(for stats) only if retry failed. 1281234353Sdim Engine.blocksExhausted.push_back(std::make_pair(L, Sink)); 1282234353Sdim } 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. 1294226633Sdimstatic SVal RecoverCastedSymbol(ProgramStateManager& StateMgr, 1295234353Sdim ProgramStateRef state, 1296226633Sdim const Stmt *Condition, 1297234353Sdim const LocationContext *LCtx, 1298226633Sdim 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 1310251662Sdim 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 1325251662Sdim if (!bitsInit || !T->isIntegralOrEnumerationType() || 1326251662Sdim Ctx.getTypeSize(T) > bits) 1327221339Sdim return UnknownVal(); 1328221339Sdim 1329234353Sdim return state->getSVal(Ex, LCtx); 1330221339Sdim} 1331221339Sdim 1332239462Sdimstatic const Stmt *ResolveCondition(const Stmt *Condition, 1333239462Sdim const CFGBlock *B) { 1334239462Sdim if (const Expr *Ex = dyn_cast<Expr>(Condition)) 1335239462Sdim Condition = Ex->IgnoreParens(); 1336239462Sdim 1337239462Sdim const BinaryOperator *BO = dyn_cast<BinaryOperator>(Condition); 1338239462Sdim if (!BO || !BO->isLogicalOp()) 1339239462Sdim return Condition; 1340239462Sdim 1341239462Sdim // For logical operations, we still have the case where some branches 1342239462Sdim // use the traditional "merge" approach and others sink the branch 1343239462Sdim // directly into the basic blocks representing the logical operation. 1344239462Sdim // We need to distinguish between those two cases here. 1345239462Sdim 1346239462Sdim // The invariants are still shifting, but it is possible that the 1347239462Sdim // last element in a CFGBlock is not a CFGStmt. Look for the last 1348239462Sdim // CFGStmt as the value of the condition. 1349239462Sdim CFGBlock::const_reverse_iterator I = B->rbegin(), E = B->rend(); 1350239462Sdim for (; I != E; ++I) { 1351239462Sdim CFGElement Elem = *I; 1352249423Sdim Optional<CFGStmt> CS = Elem.getAs<CFGStmt>(); 1353239462Sdim if (!CS) 1354239462Sdim continue; 1355239462Sdim if (CS->getStmt() != Condition) 1356239462Sdim break; 1357239462Sdim return Condition; 1358239462Sdim } 1359239462Sdim 1360239462Sdim assert(I != E); 1361239462Sdim 1362239462Sdim while (Condition) { 1363239462Sdim BO = dyn_cast<BinaryOperator>(Condition); 1364239462Sdim if (!BO || !BO->isLogicalOp()) 1365239462Sdim return Condition; 1366239462Sdim Condition = BO->getRHS()->IgnoreParens(); 1367239462Sdim } 1368239462Sdim llvm_unreachable("could not resolve condition"); 1369239462Sdim} 1370239462Sdim 1371226633Sdimvoid ExprEngine::processBranch(const Stmt *Condition, const Stmt *Term, 1372234353Sdim NodeBuilderContext& BldCtx, 1373234353Sdim ExplodedNode *Pred, 1374234353Sdim ExplodedNodeSet &Dst, 1375234353Sdim const CFGBlock *DstT, 1376234353Sdim const CFGBlock *DstF) { 1377263508Sdim const LocationContext *LCtx = Pred->getLocationContext(); 1378263508Sdim PrettyStackTraceLocationContext StackCrashInfo(LCtx); 1379243830Sdim currBldrCtx = &BldCtx; 1380221339Sdim 1381221339Sdim // Check for NULL conditions; e.g. "for(;;)" 1382221339Sdim if (!Condition) { 1383234353Sdim BranchNodeBuilder NullCondBldr(Pred, Dst, BldCtx, DstT, DstF); 1384234353Sdim NullCondBldr.markInfeasible(false); 1385234353Sdim NullCondBldr.generateNode(Pred->getState(), true, Pred); 1386221339Sdim return; 1387221339Sdim } 1388221339Sdim 1389239462Sdim 1390239462Sdim if (const Expr *Ex = dyn_cast<Expr>(Condition)) 1391239462Sdim Condition = Ex->IgnoreParens(); 1392239462Sdim 1393239462Sdim Condition = ResolveCondition(Condition, BldCtx.getBlock()); 1394221339Sdim PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 1395221339Sdim Condition->getLocStart(), 1396221339Sdim "Error evaluating branch"); 1397221339Sdim 1398234353Sdim ExplodedNodeSet CheckersOutSet; 1399234353Sdim getCheckerManager().runCheckersForBranchCondition(Condition, CheckersOutSet, 1400234353Sdim Pred, *this); 1401234353Sdim // We generated only sinks. 1402234353Sdim if (CheckersOutSet.empty()) 1403221339Sdim return; 1404221339Sdim 1405234353Sdim BranchNodeBuilder builder(CheckersOutSet, Dst, BldCtx, DstT, DstF); 1406234353Sdim for (NodeBuilder::iterator I = CheckersOutSet.begin(), 1407234353Sdim E = CheckersOutSet.end(); E != I; ++I) { 1408234353Sdim ExplodedNode *PredI = *I; 1409221339Sdim 1410234353Sdim if (PredI->isSink()) 1411234353Sdim continue; 1412221339Sdim 1413249423Sdim ProgramStateRef PrevState = PredI->getState(); 1414249423Sdim SVal X = PrevState->getSVal(Condition, PredI->getLocationContext()); 1415234353Sdim 1416234353Sdim if (X.isUnknownOrUndef()) { 1417234353Sdim // Give it a chance to recover from unknown. 1418234353Sdim if (const Expr *Ex = dyn_cast<Expr>(Condition)) { 1419251662Sdim if (Ex->getType()->isIntegralOrEnumerationType()) { 1420234353Sdim // Try to recover some path-sensitivity. Right now casts of symbolic 1421234353Sdim // integers that promote their values are currently not tracked well. 1422234353Sdim // If 'Condition' is such an expression, try and recover the 1423234353Sdim // underlying value and use that instead. 1424234353Sdim SVal recovered = RecoverCastedSymbol(getStateManager(), 1425234353Sdim PrevState, Condition, 1426249423Sdim PredI->getLocationContext(), 1427234353Sdim getContext()); 1428234353Sdim 1429234353Sdim if (!recovered.isUnknown()) { 1430234353Sdim X = recovered; 1431234353Sdim } 1432221339Sdim } 1433221339Sdim } 1434221339Sdim } 1435234353Sdim 1436221339Sdim // If the condition is still unknown, give up. 1437221339Sdim if (X.isUnknownOrUndef()) { 1438239462Sdim builder.generateNode(PrevState, true, PredI); 1439239462Sdim builder.generateNode(PrevState, false, PredI); 1440234353Sdim continue; 1441221339Sdim } 1442221339Sdim 1443249423Sdim DefinedSVal V = X.castAs<DefinedSVal>(); 1444221339Sdim 1445249423Sdim ProgramStateRef StTrue, StFalse; 1446249423Sdim tie(StTrue, StFalse) = PrevState->assume(V); 1447249423Sdim 1448234353Sdim // Process the true branch. 1449234353Sdim if (builder.isFeasible(true)) { 1450249423Sdim if (StTrue) 1451249423Sdim builder.generateNode(StTrue, true, PredI); 1452234353Sdim else 1453234353Sdim builder.markInfeasible(true); 1454234353Sdim } 1455221339Sdim 1456234353Sdim // Process the false branch. 1457234353Sdim if (builder.isFeasible(false)) { 1458249423Sdim if (StFalse) 1459249423Sdim builder.generateNode(StFalse, false, PredI); 1460234353Sdim else 1461234353Sdim builder.markInfeasible(false); 1462234353Sdim } 1463221339Sdim } 1464243830Sdim currBldrCtx = 0; 1465221339Sdim} 1466221339Sdim 1467249423Sdim/// The GDM component containing the set of global variables which have been 1468249423Sdim/// previously initialized with explicit initializers. 1469249423SdimREGISTER_TRAIT_WITH_PROGRAMSTATE(InitializedGlobalsSet, 1470249423Sdim llvm::ImmutableSet<const VarDecl *>) 1471249423Sdim 1472249423Sdimvoid ExprEngine::processStaticInitializer(const DeclStmt *DS, 1473249423Sdim NodeBuilderContext &BuilderCtx, 1474249423Sdim ExplodedNode *Pred, 1475249423Sdim clang::ento::ExplodedNodeSet &Dst, 1476249423Sdim const CFGBlock *DstT, 1477249423Sdim const CFGBlock *DstF) { 1478263508Sdim PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext()); 1479249423Sdim currBldrCtx = &BuilderCtx; 1480249423Sdim 1481249423Sdim const VarDecl *VD = cast<VarDecl>(DS->getSingleDecl()); 1482249423Sdim ProgramStateRef state = Pred->getState(); 1483249423Sdim bool initHasRun = state->contains<InitializedGlobalsSet>(VD); 1484249423Sdim BranchNodeBuilder builder(Pred, Dst, BuilderCtx, DstT, DstF); 1485249423Sdim 1486249423Sdim if (!initHasRun) { 1487249423Sdim state = state->add<InitializedGlobalsSet>(VD); 1488249423Sdim } 1489249423Sdim 1490249423Sdim builder.generateNode(state, initHasRun, Pred); 1491249423Sdim builder.markInfeasible(!initHasRun); 1492249423Sdim 1493249423Sdim currBldrCtx = 0; 1494249423Sdim} 1495249423Sdim 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 1500234353Sdim ProgramStateRef state = builder.getState(); 1501234353Sdim 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 1512249423Sdim if (Optional<loc::GotoLabel> LV = V.getAs<loc::GotoLabel>()) { 1513249423Sdim 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 1522226633Sdim llvm_unreachable("No block with label."); 1523221339Sdim } 1524221339Sdim 1525249423Sdim 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. 1542243830Sdimvoid ExprEngine::processEndOfFunction(NodeBuilderContext& BC, 1543243830Sdim ExplodedNode *Pred) { 1544263508Sdim PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext()); 1545243830Sdim StateMgr.EndPath(Pred->getState()); 1546243830Sdim 1547234353Sdim ExplodedNodeSet Dst; 1548243830Sdim if (Pred->getLocationContext()->inTopFrame()) { 1549243830Sdim // Remove dead symbols. 1550243830Sdim ExplodedNodeSet AfterRemovedDead; 1551243830Sdim removeDeadOnEndOfFunction(BC, Pred, AfterRemovedDead); 1552243830Sdim 1553243830Sdim // Notify checkers. 1554243830Sdim for (ExplodedNodeSet::iterator I = AfterRemovedDead.begin(), 1555243830Sdim E = AfterRemovedDead.end(); I != E; ++I) { 1556249423Sdim getCheckerManager().runCheckersForEndFunction(BC, Dst, *I, *this); 1557243830Sdim } 1558243830Sdim } else { 1559249423Sdim getCheckerManager().runCheckersForEndFunction(BC, Dst, Pred, *this); 1560243830Sdim } 1561243830Sdim 1562234353Sdim 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; 1569234353Sdim ProgramStateRef state = builder.getState(); 1570226633Sdim const Expr *CondE = builder.getCondition(); 1571234353Sdim 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 } 1580249423Sdim DefinedOrUnknownSVal CondV = CondV_untested.castAs<DefinedOrUnknownSVal>(); 1581221339Sdim 1582234353Sdim 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 1592226633Sdim const CaseStmt *Case = I.getCase(); 1593221339Sdim 1594221339Sdim // Evaluate the LHS of the case value. 1595226633Sdim llvm::APSInt V1 = Case->getLHS()->EvaluateKnownConstInt(getContext()); 1596226633Sdim assert(V1.getBitWidth() == getContext().getTypeSize(CondE->getType())); 1597221339Sdim 1598221339Sdim // Get the RHS of the case, if it exists. 1599226633Sdim llvm::APSInt V2; 1600226633Sdim if (const Expr *E = Case->getRHS()) 1601226633Sdim 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 { 1610226633Sdim 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. 1615234353Sdim 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. 1621249423Sdim 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) { 1628234353Sdim 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. 1639226633Sdim if (V1 == V2) 1640221339Sdim break; 1641221339Sdim 1642226633Sdim ++V1; 1643226633Sdim 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) { 1675243830Sdim StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); 1676221339Sdim 1677234353Sdim ProgramStateRef state = Pred->getState(); 1678234353Sdim const LocationContext *LCtx = Pred->getLocationContext(); 1679234353Sdim 1680226633Sdim if (const VarDecl *VD = dyn_cast<VarDecl>(D)) { 1681263508Sdim // C permits "extern void v", and if you cast the address to a valid type, 1682263508Sdim // you can even do things with it. We simply pretend 1683263508Sdim 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 1695243830Sdim Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), 0, 1696234353Sdim ProgramPoint::PostLValueKind); 1697221339Sdim return; 1698221339Sdim } 1699226633Sdim if (const EnumConstantDecl *ED = dyn_cast<EnumConstantDecl>(D)) { 1700239462Sdim assert(!Ex->isGLValue()); 1701221339Sdim SVal V = svalBuilder.makeIntVal(ED->getInitVal()); 1702234353Sdim Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V)); 1703221339Sdim return; 1704221339Sdim } 1705226633Sdim if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 1706221339Sdim SVal V = svalBuilder.getFunctionPointer(FD); 1707243830Sdim Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), 0, 1708234353Sdim ProgramPoint::PostLValueKind); 1709221339Sdim return; 1710221339Sdim } 1711234353Sdim if (isa<FieldDecl>(D)) { 1712243830Sdim // FIXME: Compute lvalue of field pointers-to-member. 1713243830Sdim // Right now we just use a non-null void pointer, so that it gives proper 1714243830Sdim // results in boolean contexts. 1715243830Sdim SVal V = svalBuilder.conjureSymbolVal(Ex, LCtx, getContext().VoidPtrTy, 1716243830Sdim currBldrCtx->blockCount()); 1717249423Sdim state = state->assume(V.castAs<DefinedOrUnknownSVal>(), true); 1718243830Sdim Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), 0, 1719243830Sdim ProgramPoint::PostLValueKind); 1720234353Sdim return; 1721234353Sdim } 1722234353Sdim 1723243830Sdim llvm_unreachable("Support for this Decl not implemented."); 1724221339Sdim} 1725221339Sdim 1726221339Sdim/// VisitArraySubscriptExpr - Transfer function for array accesses 1727226633Sdimvoid ExprEngine::VisitLvalArraySubscriptExpr(const ArraySubscriptExpr *A, 1728226633Sdim ExplodedNode *Pred, 1729226633Sdim ExplodedNodeSet &Dst){ 1730221339Sdim 1731226633Sdim const Expr *Base = A->getBase()->IgnoreParens(); 1732226633Sdim const Expr *Idx = A->getIdx()->IgnoreParens(); 1733221339Sdim 1734221339Sdim 1735226633Sdim ExplodedNodeSet checkerPreStmt; 1736226633Sdim getCheckerManager().runCheckersForPreStmt(checkerPreStmt, Pred, A, *this); 1737221339Sdim 1738243830Sdim StmtNodeBuilder Bldr(checkerPreStmt, Dst, *currBldrCtx); 1739234353Sdim 1740226633Sdim for (ExplodedNodeSet::iterator it = checkerPreStmt.begin(), 1741226633Sdim ei = checkerPreStmt.end(); it != ei; ++it) { 1742234353Sdim const LocationContext *LCtx = (*it)->getLocationContext(); 1743234353Sdim ProgramStateRef state = (*it)->getState(); 1744234353Sdim SVal V = state->getLValue(A->getType(), 1745234353Sdim state->getSVal(Idx, LCtx), 1746234353Sdim state->getSVal(Base, LCtx)); 1747239462Sdim assert(A->isGLValue()); 1748243830Sdim Bldr.generateNode(A, *it, state->BindExpr(A, LCtx, V), 0, 1749243830Sdim ProgramPoint::PostLValueKind); 1750221339Sdim } 1751221339Sdim} 1752221339Sdim 1753221339Sdim/// VisitMemberExpr - Transfer function for member expressions. 1754226633Sdimvoid ExprEngine::VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred, 1755234353Sdim ExplodedNodeSet &TopDst) { 1756221339Sdim 1757243830Sdim StmtNodeBuilder Bldr(Pred, TopDst, *currBldrCtx); 1758234353Sdim ExplodedNodeSet Dst; 1759243830Sdim ValueDecl *Member = M->getMemberDecl(); 1760239462Sdim 1761243830Sdim // Handle static member variables and enum constants accessed via 1762243830Sdim // member syntax. 1763243830Sdim if (isa<VarDecl>(Member) || isa<EnumConstantDecl>(Member)) { 1764234353Sdim Bldr.takeNodes(Pred); 1765243830Sdim VisitCommonDeclRefExpr(M, Member, Pred, Dst); 1766234353Sdim Bldr.addNodes(Dst); 1767226633Sdim return; 1768226633Sdim } 1769239462Sdim 1770243830Sdim ProgramStateRef state = Pred->getState(); 1771243830Sdim const LocationContext *LCtx = Pred->getLocationContext(); 1772243830Sdim Expr *BaseExpr = M->getBase(); 1773243830Sdim 1774239462Sdim // Handle C++ method calls. 1775243830Sdim if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(Member)) { 1776243830Sdim if (MD->isInstance()) 1777243830Sdim state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr); 1778243830Sdim 1779239462Sdim SVal MDVal = svalBuilder.getFunctionPointer(MD); 1780243830Sdim state = state->BindExpr(M, LCtx, MDVal); 1781243830Sdim 1782239462Sdim Bldr.generateNode(M, Pred, state); 1783239462Sdim return; 1784239462Sdim } 1785239462Sdim 1786243830Sdim // Handle regular struct fields / member variables. 1787243830Sdim state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr); 1788243830Sdim SVal baseExprVal = state->getSVal(BaseExpr, LCtx); 1789239462Sdim 1790243830Sdim FieldDecl *field = cast<FieldDecl>(Member); 1791226633Sdim SVal L = state->getLValue(field, baseExprVal); 1792263508Sdim 1793263508Sdim if (M->isGLValue() || M->getType()->isArrayType()) { 1794263508Sdim 1795263508Sdim // We special case rvalue of array type because the analyzer cannot reason 1796263508Sdim // about it, since we expect all regions to be wrapped in Locs. So we will 1797263508Sdim // treat these as lvalues assuming that they will decay to pointers as soon 1798263508Sdim // as they are used. 1799263508Sdim if (!M->isGLValue()) { 1800263508Sdim assert(M->getType()->isArrayType()); 1801263508Sdim const ImplicitCastExpr *PE = 1802263508Sdim dyn_cast<ImplicitCastExpr>(Pred->getParentMap().getParent(M)); 1803263508Sdim if (!PE || PE->getCastKind() != CK_ArrayToPointerDecay) { 1804263508Sdim assert(false && 1805263508Sdim "We assume that array is always wrapped in ArrayToPointerDecay"); 1806263508Sdim L = UnknownVal(); 1807263508Sdim } 1808263508Sdim } 1809263508Sdim 1810239462Sdim if (field->getType()->isReferenceType()) { 1811239462Sdim if (const MemRegion *R = L.getAsRegion()) 1812239462Sdim L = state->getSVal(R); 1813239462Sdim else 1814239462Sdim L = UnknownVal(); 1815239462Sdim } 1816239462Sdim 1817243830Sdim Bldr.generateNode(M, Pred, state->BindExpr(M, LCtx, L), 0, 1818234353Sdim ProgramPoint::PostLValueKind); 1819239462Sdim } else { 1820234353Sdim Bldr.takeNodes(Pred); 1821234353Sdim evalLoad(Dst, M, M, Pred, state, L); 1822234353Sdim Bldr.addNodes(Dst); 1823234353Sdim } 1824221339Sdim} 1825221339Sdim 1826249423Sdimnamespace { 1827249423Sdimclass CollectReachableSymbolsCallback : public SymbolVisitor { 1828249423Sdim InvalidatedSymbols Symbols; 1829249423Sdimpublic: 1830249423Sdim CollectReachableSymbolsCallback(ProgramStateRef State) {} 1831249423Sdim const InvalidatedSymbols &getSymbols() const { return Symbols; } 1832249423Sdim 1833249423Sdim bool VisitSymbol(SymbolRef Sym) { 1834249423Sdim Symbols.insert(Sym); 1835249423Sdim return true; 1836249423Sdim } 1837249423Sdim}; 1838249423Sdim} // end anonymous namespace 1839249423Sdim 1840249423Sdim// A value escapes in three possible cases: 1841249423Sdim// (1) We are binding to something that is not a memory region. 1842249423Sdim// (2) We are binding to a MemrRegion that does not have stack storage. 1843249423Sdim// (3) We are binding to a MemRegion with stack storage that the store 1844249423Sdim// does not understand. 1845249423SdimProgramStateRef ExprEngine::processPointerEscapedOnBind(ProgramStateRef State, 1846249423Sdim SVal Loc, SVal Val) { 1847249423Sdim // Are we storing to something that causes the value to "escape"? 1848249423Sdim bool escapes = true; 1849249423Sdim 1850249423Sdim // TODO: Move to StoreManager. 1851249423Sdim if (Optional<loc::MemRegionVal> regionLoc = Loc.getAs<loc::MemRegionVal>()) { 1852249423Sdim escapes = !regionLoc->getRegion()->hasStackStorage(); 1853249423Sdim 1854249423Sdim if (!escapes) { 1855249423Sdim // To test (3), generate a new state with the binding added. If it is 1856249423Sdim // the same state, then it escapes (since the store cannot represent 1857249423Sdim // the binding). 1858249423Sdim // Do this only if we know that the store is not supposed to generate the 1859249423Sdim // same state. 1860249423Sdim SVal StoredVal = State->getSVal(regionLoc->getRegion()); 1861249423Sdim if (StoredVal != Val) 1862249423Sdim escapes = (State == (State->bindLoc(*regionLoc, Val))); 1863249423Sdim } 1864249423Sdim } 1865249423Sdim 1866249423Sdim // If our store can represent the binding and we aren't storing to something 1867249423Sdim // that doesn't have local storage then just return and have the simulation 1868249423Sdim // state continue as is. 1869249423Sdim if (!escapes) 1870249423Sdim return State; 1871249423Sdim 1872249423Sdim // Otherwise, find all symbols referenced by 'val' that we are tracking 1873249423Sdim // and stop tracking them. 1874249423Sdim CollectReachableSymbolsCallback Scanner = 1875249423Sdim State->scanReachableSymbols<CollectReachableSymbolsCallback>(Val); 1876249423Sdim const InvalidatedSymbols &EscapedSymbols = Scanner.getSymbols(); 1877249423Sdim State = getCheckerManager().runCheckersForPointerEscape(State, 1878249423Sdim EscapedSymbols, 1879249423Sdim /*CallEvent*/ 0, 1880263508Sdim PSK_EscapeOnBind, 1881263508Sdim 0); 1882249423Sdim 1883249423Sdim return State; 1884249423Sdim} 1885249423Sdim 1886249423SdimProgramStateRef 1887249423SdimExprEngine::notifyCheckersOfPointerEscape(ProgramStateRef State, 1888249423Sdim const InvalidatedSymbols *Invalidated, 1889249423Sdim ArrayRef<const MemRegion *> ExplicitRegions, 1890249423Sdim ArrayRef<const MemRegion *> Regions, 1891249423Sdim const CallEvent *Call, 1892263508Sdim RegionAndSymbolInvalidationTraits &ITraits) { 1893249423Sdim 1894249423Sdim if (!Invalidated || Invalidated->empty()) 1895249423Sdim return State; 1896249423Sdim 1897249423Sdim if (!Call) 1898249423Sdim return getCheckerManager().runCheckersForPointerEscape(State, 1899249423Sdim *Invalidated, 1900249423Sdim 0, 1901251662Sdim PSK_EscapeOther, 1902263508Sdim &ITraits); 1903249423Sdim 1904249423Sdim // If the symbols were invalidated by a call, we want to find out which ones 1905249423Sdim // were invalidated directly due to being arguments to the call. 1906249423Sdim InvalidatedSymbols SymbolsDirectlyInvalidated; 1907249423Sdim for (ArrayRef<const MemRegion *>::iterator I = ExplicitRegions.begin(), 1908249423Sdim E = ExplicitRegions.end(); I != E; ++I) { 1909249423Sdim if (const SymbolicRegion *R = (*I)->StripCasts()->getAs<SymbolicRegion>()) 1910249423Sdim SymbolsDirectlyInvalidated.insert(R->getSymbol()); 1911249423Sdim } 1912249423Sdim 1913249423Sdim InvalidatedSymbols SymbolsIndirectlyInvalidated; 1914249423Sdim for (InvalidatedSymbols::const_iterator I=Invalidated->begin(), 1915249423Sdim E = Invalidated->end(); I!=E; ++I) { 1916249423Sdim SymbolRef sym = *I; 1917249423Sdim if (SymbolsDirectlyInvalidated.count(sym)) 1918249423Sdim continue; 1919249423Sdim SymbolsIndirectlyInvalidated.insert(sym); 1920249423Sdim } 1921249423Sdim 1922249423Sdim if (!SymbolsDirectlyInvalidated.empty()) 1923249423Sdim State = getCheckerManager().runCheckersForPointerEscape(State, 1924263508Sdim SymbolsDirectlyInvalidated, Call, PSK_DirectEscapeOnCall, &ITraits); 1925249423Sdim 1926249423Sdim // Notify about the symbols that get indirectly invalidated by the call. 1927249423Sdim if (!SymbolsIndirectlyInvalidated.empty()) 1928249423Sdim State = getCheckerManager().runCheckersForPointerEscape(State, 1929263508Sdim SymbolsIndirectlyInvalidated, Call, PSK_IndirectEscapeOnCall, &ITraits); 1930249423Sdim 1931249423Sdim return State; 1932249423Sdim} 1933249423Sdim 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. 1936226633Sdimvoid ExprEngine::evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE, 1937226633Sdim ExplodedNode *Pred, 1938243830Sdim SVal location, SVal Val, 1939243830Sdim bool atDeclInit, const ProgramPoint *PP) { 1940221339Sdim 1941243830Sdim const LocationContext *LC = Pred->getLocationContext(); 1942243830Sdim PostStmt PS(StoreE, LC); 1943243830Sdim if (!PP) 1944243830Sdim PP = &PS; 1945243830Sdim 1946221339Sdim // Do a previsit of the bind. 1947226633Sdim ExplodedNodeSet CheckedSet; 1948226633Sdim getCheckerManager().runCheckersForBind(CheckedSet, Pred, location, Val, 1949243830Sdim StoreE, *this, *PP); 1950221339Sdim 1951249423Sdim 1952249423Sdim StmtNodeBuilder Bldr(CheckedSet, Dst, *currBldrCtx); 1953249423Sdim 1954243830Sdim // If the location is not a 'Loc', it will already be handled by 1955243830Sdim // the checkers. There is nothing left to do. 1956249423Sdim if (!location.getAs<Loc>()) { 1957249423Sdim const ProgramPoint L = PostStore(StoreE, LC, /*Loc*/0, /*tag*/0); 1958249423Sdim ProgramStateRef state = Pred->getState(); 1959249423Sdim state = processPointerEscapedOnBind(state, location, Val); 1960249423Sdim Bldr.generateNode(L, state, Pred); 1961243830Sdim return; 1962243830Sdim } 1963243830Sdim 1964234353Sdim 1965221339Sdim for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end(); 1966221339Sdim I!=E; ++I) { 1967234353Sdim ExplodedNode *PredI = *I; 1968234353Sdim ProgramStateRef state = PredI->getState(); 1969243830Sdim 1970249423Sdim state = processPointerEscapedOnBind(state, location, Val); 1971249423Sdim 1972243830Sdim // When binding the value, pass on the hint that this is a initialization. 1973243830Sdim // For initializations, we do not need to inform clients of region 1974243830Sdim // changes. 1975249423Sdim state = state->bindLoc(location.castAs<Loc>(), 1976243830Sdim Val, /* notifyChanges = */ !atDeclInit); 1977249423Sdim 1978234353Sdim const MemRegion *LocReg = 0; 1979249423Sdim if (Optional<loc::MemRegionVal> LocRegVal = 1980249423Sdim location.getAs<loc::MemRegionVal>()) { 1981234353Sdim LocReg = LocRegVal->getRegion(); 1982243830Sdim } 1983243830Sdim 1984234353Sdim const ProgramPoint L = PostStore(StoreE, LC, LocReg, 0); 1985243830Sdim 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 1991239462Sdim/// @param AssignE The assignment expression if the store happens in an 1992221339Sdim/// assignment. 1993239462Sdim/// @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 1997226633Sdimvoid ExprEngine::evalStore(ExplodedNodeSet &Dst, const Expr *AssignE, 1998226633Sdim const Expr *LocationE, 1999226633Sdim ExplodedNode *Pred, 2000234353Sdim ProgramStateRef state, SVal location, SVal Val, 2001226633Sdim 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; 2008234353Sdim 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) 2017234353Sdim evalBind(Dst, StoreE, *NI, location, Val, false); 2018221339Sdim} 2019221339Sdim 2020234353Sdimvoid ExprEngine::evalLoad(ExplodedNodeSet &Dst, 2021234353Sdim const Expr *NodeEx, 2022234353Sdim const Expr *BoundEx, 2023234353Sdim ExplodedNode *Pred, 2024234353Sdim ProgramStateRef state, 2025234353Sdim SVal location, 2026234353Sdim const ProgramPointTag *tag, 2027234353Sdim QualType LoadTy) 2028234353Sdim{ 2029249423Sdim 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. 2034226633Sdim if (const TypedValueRegion *TR = 2035226633Sdim dyn_cast_or_null<TypedValueRegion>(location.getAsRegion())) { 2036221339Sdim 2037221339Sdim QualType ValTy = TR->getValueType(); 2038221339Sdim if (const ReferenceType *RT = ValTy->getAs<ReferenceType>()) { 2039226633Sdim static SimpleProgramPointTag 2040226633Sdim loadReferenceTag("ExprEngine : Load Reference"); 2041221339Sdim ExplodedNodeSet Tmp; 2042234353Sdim evalLoadCommon(Tmp, NodeEx, BoundEx, Pred, state, 2043234353Sdim 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) { 2048226633Sdim state = (*I)->getState(); 2049234353Sdim location = state->getSVal(BoundEx, (*I)->getLocationContext()); 2050234353Sdim evalLoadCommon(Dst, NodeEx, BoundEx, *I, state, location, tag, LoadTy); 2051221339Sdim } 2052221339Sdim return; 2053221339Sdim } 2054221339Sdim } 2055221339Sdim 2056234353Sdim evalLoadCommon(Dst, NodeEx, BoundEx, Pred, state, location, tag, LoadTy); 2057221339Sdim} 2058221339Sdim 2059234353Sdimvoid ExprEngine::evalLoadCommon(ExplodedNodeSet &Dst, 2060234353Sdim const Expr *NodeEx, 2061234353Sdim const Expr *BoundEx, 2062234353Sdim ExplodedNode *Pred, 2063234353Sdim ProgramStateRef state, 2064234353Sdim SVal location, 2065234353Sdim const ProgramPointTag *tag, 2066234353Sdim QualType LoadTy) { 2067234353Sdim assert(NodeEx); 2068234353Sdim assert(BoundEx); 2069221339Sdim // Evaluate the location (checks for bad dereferences). 2070221339Sdim ExplodedNodeSet Tmp; 2071234353Sdim evalLocation(Tmp, NodeEx, BoundEx, Pred, state, location, tag, true); 2072221339Sdim if (Tmp.empty()) 2073221339Sdim return; 2074221339Sdim 2075243830Sdim 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) { 2081226633Sdim state = (*NI)->getState(); 2082234353Sdim const LocationContext *LCtx = (*NI)->getLocationContext(); 2083221339Sdim 2084249423Sdim SVal V = UnknownVal(); 2085249423Sdim if (location.isValid()) { 2086221339Sdim if (LoadTy.isNull()) 2087234353Sdim LoadTy = BoundEx->getType(); 2088249423Sdim V = state->getSVal(location.castAs<Loc>(), LoadTy); 2089221339Sdim } 2090249423Sdim 2091249423Sdim Bldr.generateNode(NodeEx, *NI, state->BindExpr(BoundEx, LCtx, V), tag, 2092249423Sdim ProgramPoint::PostLoadKind); 2093221339Sdim } 2094221339Sdim} 2095221339Sdim 2096234353Sdimvoid ExprEngine::evalLocation(ExplodedNodeSet &Dst, 2097234353Sdim const Stmt *NodeEx, 2098234353Sdim const Stmt *BoundEx, 2099234353Sdim ExplodedNode *Pred, 2100234353Sdim ProgramStateRef state, 2101234353Sdim SVal location, 2102234353Sdim const ProgramPointTag *tag, 2103234353Sdim bool isLoad) { 2104243830Sdim StmtNodeBuilder BldrTop(Pred, Dst, *currBldrCtx); 2105221339Sdim // Early checks for performance reason. 2106221339Sdim if (location.isUnknown()) { 2107221339Sdim return; 2108221339Sdim } 2109221339Sdim 2110221339Sdim ExplodedNodeSet Src; 2111234353Sdim BldrTop.takeNodes(Pred); 2112243830Sdim StmtNodeBuilder Bldr(Pred, Src, *currBldrCtx); 2113234353Sdim 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" 2122226633Sdim 2123243830Sdim static SimpleProgramPointTag tag("ExprEngine: Location"); 2124243830Sdim Bldr.generateNode(NodeEx, Pred, state, &tag); 2125221339Sdim } 2126234353Sdim ExplodedNodeSet Tmp; 2127234353Sdim getCheckerManager().runCheckersForLocation(Tmp, Src, location, isLoad, 2128234353Sdim NodeEx, BoundEx, *this); 2129234353Sdim BldrTop.addNodes(Tmp); 2130221339Sdim} 2131221339Sdim 2132226633Sdimstd::pair<const ProgramPointTag *, const ProgramPointTag*> 2133243830SdimExprEngine::geteagerlyAssumeBinOpBifurcationTags() { 2134226633Sdim static SimpleProgramPointTag 2135243830Sdim eagerlyAssumeBinOpBifurcationTrue("ExprEngine : Eagerly Assume True"), 2136243830Sdim eagerlyAssumeBinOpBifurcationFalse("ExprEngine : Eagerly Assume False"); 2137243830Sdim return std::make_pair(&eagerlyAssumeBinOpBifurcationTrue, 2138243830Sdim &eagerlyAssumeBinOpBifurcationFalse); 2139221339Sdim} 2140221339Sdim 2141243830Sdimvoid ExprEngine::evalEagerlyAssumeBinOpBifurcation(ExplodedNodeSet &Dst, 2142243830Sdim ExplodedNodeSet &Src, 2143243830Sdim const Expr *Ex) { 2144243830Sdim StmtNodeBuilder Bldr(Src, Dst, *currBldrCtx); 2145226633Sdim 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(); 2152249423Sdim if (!P.getAs<PostStmt>() || P.castAs<PostStmt>().getStmt() != Ex) { 2153221339Sdim continue; 2154221339Sdim } 2155221339Sdim 2156234353Sdim ProgramStateRef state = Pred->getState(); 2157234353Sdim SVal V = state->getSVal(Ex, Pred->getLocationContext()); 2158249423Sdim Optional<nonloc::SymbolVal> SEV = V.getAs<nonloc::SymbolVal>(); 2159234353Sdim if (SEV && SEV->isExpression()) { 2160226633Sdim const std::pair<const ProgramPointTag *, const ProgramPointTag*> &tags = 2161243830Sdim geteagerlyAssumeBinOpBifurcationTags(); 2162226633Sdim 2163249423Sdim ProgramStateRef StateTrue, StateFalse; 2164249423Sdim tie(StateTrue, StateFalse) = state->assume(*SEV); 2165249423Sdim 2166221339Sdim // First assume that the condition is true. 2167249423Sdim if (StateTrue) { 2168226633Sdim SVal Val = svalBuilder.makeIntVal(1U, Ex->getType()); 2169234353Sdim StateTrue = StateTrue->BindExpr(Ex, Pred->getLocationContext(), Val); 2170243830Sdim Bldr.generateNode(Ex, Pred, StateTrue, tags.first); 2171221339Sdim } 2172221339Sdim 2173221339Sdim // Next, assume that the condition is false. 2174249423Sdim if (StateFalse) { 2175226633Sdim SVal Val = svalBuilder.makeIntVal(0U, Ex->getType()); 2176234353Sdim StateFalse = StateFalse->BindExpr(Ex, Pred->getLocationContext(), Val); 2177243830Sdim Bldr.generateNode(Ex, Pred, StateFalse, tags.second); 2178221339Sdim } 2179221339Sdim } 2180221339Sdim } 2181221339Sdim} 2182221339Sdim 2183243830Sdimvoid ExprEngine::VisitGCCAsmStmt(const GCCAsmStmt *A, ExplodedNode *Pred, 2184243830Sdim ExplodedNodeSet &Dst) { 2185243830Sdim StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); 2186234353Sdim // We have processed both the inputs and the outputs. All of the outputs 2187234353Sdim // should evaluate to Locs. Nuke all of their values. 2188221339Sdim 2189234353Sdim // FIXME: Some day in the future it would be nice to allow a "plug-in" 2190234353Sdim // which interprets the inline asm and stores proper results in the 2191234353Sdim // outputs. 2192221339Sdim 2193234353Sdim ProgramStateRef state = Pred->getState(); 2194221339Sdim 2195243830Sdim for (GCCAsmStmt::const_outputs_iterator OI = A->begin_outputs(), 2196234353Sdim OE = A->end_outputs(); OI != OE; ++OI) { 2197234353Sdim SVal X = state->getSVal(*OI, Pred->getLocationContext()); 2198249423Sdim assert (!X.getAs<NonLoc>()); // Should be an Lval, or unknown, undef. 2199221339Sdim 2200249423Sdim if (Optional<Loc> LV = X.getAs<Loc>()) 2201249423Sdim state = state->bindLoc(*LV, UnknownVal()); 2202221339Sdim } 2203221339Sdim 2204234353Sdim Bldr.generateNode(A, Pred, state); 2205221339Sdim} 2206221339Sdim 2207239462Sdimvoid ExprEngine::VisitMSAsmStmt(const MSAsmStmt *A, ExplodedNode *Pred, 2208239462Sdim ExplodedNodeSet &Dst) { 2209243830Sdim StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); 2210239462Sdim Bldr.generateNode(A, Pred, Pred->getState()); 2211239462Sdim} 2212239462Sdim 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. 2230226633Sdim 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 2251249423Sdim static void printLocation(raw_ostream &Out, SourceLocation SLoc) { 2252239462Sdim if (SLoc.isFileID()) { 2253239462Sdim Out << "\\lline=" 2254239462Sdim << GraphPrintSourceManager->getExpansionLineNumber(SLoc) 2255239462Sdim << " col=" 2256239462Sdim << GraphPrintSourceManager->getExpansionColumnNumber(SLoc) 2257239462Sdim << "\\l"; 2258239462Sdim } 2259239462Sdim } 2260239462Sdim 2261226633Sdim 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()) { 2270239462Sdim case ProgramPoint::BlockEntranceKind: { 2271221339Sdim Out << "Block Entrance: B" 2272249423Sdim << Loc.castAs<BlockEntrance>().getBlock()->getBlockID(); 2273239462Sdim if (const NamedDecl *ND = 2274239462Sdim dyn_cast<NamedDecl>(Loc.getLocationContext()->getDecl())) { 2275239462Sdim Out << " ("; 2276239462Sdim ND->printName(Out); 2277239462Sdim Out << ")"; 2278239462Sdim } 2279221339Sdim break; 2280239462Sdim } 2281221339Sdim 2282221339Sdim case ProgramPoint::BlockExitKind: 2283221339Sdim assert (false); 2284221339Sdim break; 2285221339Sdim 2286221339Sdim case ProgramPoint::CallEnterKind: 2287221339Sdim Out << "CallEnter"; 2288221339Sdim break; 2289221339Sdim 2290239462Sdim case ProgramPoint::CallExitBeginKind: 2291239462Sdim Out << "CallExitBegin"; 2292221339Sdim break; 2293221339Sdim 2294239462Sdim case ProgramPoint::CallExitEndKind: 2295239462Sdim Out << "CallExitEnd"; 2296239462Sdim break; 2297239462Sdim 2298239462Sdim case ProgramPoint::PostStmtPurgeDeadSymbolsKind: 2299239462Sdim Out << "PostStmtPurgeDeadSymbols"; 2300239462Sdim break; 2301239462Sdim 2302239462Sdim case ProgramPoint::PreStmtPurgeDeadSymbolsKind: 2303239462Sdim Out << "PreStmtPurgeDeadSymbols"; 2304239462Sdim break; 2305239462Sdim 2306234353Sdim case ProgramPoint::EpsilonKind: 2307234353Sdim Out << "Epsilon Point"; 2308234353Sdim break; 2309234353Sdim 2310239462Sdim case ProgramPoint::PreImplicitCallKind: { 2311249423Sdim ImplicitCallPoint PC = Loc.castAs<ImplicitCallPoint>(); 2312239462Sdim Out << "PreCall: "; 2313239462Sdim 2314239462Sdim // FIXME: Get proper printing options. 2315249423Sdim PC.getDecl()->print(Out, LangOptions()); 2316249423Sdim printLocation(Out, PC.getLocation()); 2317239462Sdim break; 2318239462Sdim } 2319239462Sdim 2320239462Sdim case ProgramPoint::PostImplicitCallKind: { 2321249423Sdim ImplicitCallPoint PC = Loc.castAs<ImplicitCallPoint>(); 2322239462Sdim Out << "PostCall: "; 2323239462Sdim 2324239462Sdim // FIXME: Get proper printing options. 2325249423Sdim PC.getDecl()->print(Out, LangOptions()); 2326249423Sdim printLocation(Out, PC.getLocation()); 2327239462Sdim break; 2328239462Sdim } 2329239462Sdim 2330249423Sdim case ProgramPoint::PostInitializerKind: { 2331249423Sdim Out << "PostInitializer: "; 2332249423Sdim const CXXCtorInitializer *Init = 2333249423Sdim Loc.castAs<PostInitializer>().getInitializer(); 2334249423Sdim if (const FieldDecl *FD = Init->getAnyMember()) 2335249423Sdim Out << *FD; 2336249423Sdim else { 2337249423Sdim QualType Ty = Init->getTypeSourceInfo()->getType(); 2338249423Sdim Ty = Ty.getLocalUnqualifiedType(); 2339221339Sdim LangOptions LO; // FIXME. 2340249423Sdim Ty.print(Out, LO); 2341221339Sdim } 2342249423Sdim break; 2343249423Sdim } 2344221339Sdim 2345249423Sdim case ProgramPoint::BlockEdgeKind: { 2346249423Sdim const BlockEdge &E = Loc.castAs<BlockEdge>(); 2347221339Sdim Out << "Edge: (B" << E.getSrc()->getBlockID() << ", B" 2348221339Sdim << E.getDst()->getBlockID() << ')'; 2349221339Sdim 2350226633Sdim 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=" 2359226633Sdim << GraphPrintSourceManager->getExpansionLineNumber(SLoc) 2360221339Sdim << " col=" 2361226633Sdim << GraphPrintSourceManager->getExpansionColumnNumber(SLoc); 2362221339Sdim } 2363221339Sdim 2364221339Sdim if (isa<SwitchStmt>(T)) { 2365226633Sdim const Stmt *Label = E.getDst()->getLabel(); 2366221339Sdim 2367221339Sdim if (Label) { 2368226633Sdim if (const CaseStmt *C = dyn_cast<CaseStmt>(Label)) { 2369221339Sdim Out << "\\lcase "; 2370221339Sdim LangOptions LO; // FIXME. 2371221339Sdim C->getLHS()->printPretty(Out, 0, PrintingPolicy(LO)); 2372221339Sdim 2373226633Sdim 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 2409249423Sdim break; 2410221339Sdim } 2411249423Sdim 2412249423Sdim default: { 2413249423Sdim const Stmt *S = Loc.castAs<StmtPoint>().getStmt(); 2414249423Sdim 2415249423Sdim Out << S->getStmtClassName() << ' ' << (const void*) S << ' '; 2416249423Sdim LangOptions LO; // FIXME. 2417249423Sdim S->printPretty(Out, 0, PrintingPolicy(LO)); 2418249423Sdim printLocation(Out, S->getLocStart()); 2419249423Sdim 2420249423Sdim if (Loc.getAs<PreStmt>()) 2421249423Sdim Out << "\\lPreStmt\\l;"; 2422249423Sdim else if (Loc.getAs<PostLoad>()) 2423249423Sdim Out << "\\lPostLoad\\l;"; 2424249423Sdim else if (Loc.getAs<PostStore>()) 2425249423Sdim Out << "\\lPostStore\\l"; 2426249423Sdim else if (Loc.getAs<PostLValue>()) 2427249423Sdim Out << "\\lPostLValue\\l"; 2428249423Sdim 2429249423Sdim#if 0 2430249423Sdim // FIXME: Replace with a general scheme to determine 2431249423Sdim // the name of the check. 2432249423Sdim if (GraphPrintCheckerState->isImplicitNullDeref(N)) 2433249423Sdim Out << "\\|Implicit-Null Dereference.\\l"; 2434249423Sdim else if (GraphPrintCheckerState->isExplicitNullDeref(N)) 2435249423Sdim Out << "\\|Explicit-Null Dereference.\\l"; 2436249423Sdim else if (GraphPrintCheckerState->isUndefDeref(N)) 2437249423Sdim Out << "\\|Dereference of undefialied value.\\l"; 2438249423Sdim else if (GraphPrintCheckerState->isUndefStore(N)) 2439249423Sdim Out << "\\|Store to Undefined Loc."; 2440249423Sdim else if (GraphPrintCheckerState->isUndefResult(N)) 2441249423Sdim Out << "\\|Result of operation is undefined."; 2442249423Sdim else if (GraphPrintCheckerState->isNoReturnCall(N)) 2443249423Sdim Out << "\\|Call to function marked \"noreturn\"."; 2444249423Sdim else if (GraphPrintCheckerState->isBadCall(N)) 2445249423Sdim Out << "\\|Call to NULL/Undefined."; 2446249423Sdim else if (GraphPrintCheckerState->isUndefArg(N)) 2447249423Sdim Out << "\\|Argument in call is undefined"; 2448249423Sdim#endif 2449249423Sdim 2450249423Sdim break; 2451249423Sdim } 2452221339Sdim } 2453221339Sdim 2454234353Sdim ProgramStateRef state = N->getState(); 2455243830Sdim Out << "\\|StateID: " << (const void*) state.getPtr() 2456243830Sdim << " NodeID: " << (const void*) N << "\\|"; 2457234353Sdim state->printDOT(Out); 2458226633Sdim 2459226633Sdim Out << "\\l"; 2460226633Sdim 2461226633Sdim if (const ProgramPointTag *tag = Loc.getTag()) { 2462226633Sdim Out << "\\|Tag: " << tag->getTagDescription(); 2463226633Sdim Out << "\\l"; 2464226633Sdim } 2465221339Sdim return Out.str(); 2466221339Sdim } 2467221339Sdim}; 2468221339Sdim} // end llvm namespace 2469221339Sdim#endif 2470221339Sdim 2471221339Sdim#ifndef NDEBUG 2472221339Sdimtemplate <typename ITERATOR> 2473226633SdimExplodedNode *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) { 2485249423Sdim 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) { 2495234353Sdim ExplodedNode *N = const_cast<ExplodedNode*>(EI->begin()->getErrorNode()); 2496221339Sdim if (N) Src.push_back(N); 2497221339Sdim } 2498221339Sdim 2499249423Sdim 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 2513249423Sdimvoid ExprEngine::ViewGraph(ArrayRef<const ExplodedNode*> Nodes) { 2514221339Sdim#ifndef NDEBUG 2515221339Sdim GraphPrintCheckerState = this; 2516221339Sdim GraphPrintSourceManager = &getContext().getSourceManager(); 2517221339Sdim 2518249423Sdim 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