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