ExprEngine.cpp revision 4ca8ac2e61c37ddadf37024af86f3e1019af8532
1e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project//=-- ExprEngine.cpp - Path-Sensitive Expression-Level Dataflow ---*- C++ -*-= 2e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project// 3e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project// The LLVM Compiler Infrastructure 4e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project// 5e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project// This file is distributed under the University of Illinois Open Source 6e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project// License. See LICENSE.TXT for details. 7e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project// 8e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project//===----------------------------------------------------------------------===// 9e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project// 10e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project// This file defines a meta-engine for path-sensitive dataflow analysis that 11e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project// is built on GREngine, but provides the boilerplate to execute transfer 12e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project// functions and build the ExplodedGraph at the expression level. 13e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project// 14e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project//===----------------------------------------------------------------------===// 15e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project 16e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project#include "clang/StaticAnalyzer/Core/CheckerManager.h" 17e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 18e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" 19e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 20e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project#include "clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h" 21e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project#include "clang/AST/CharUnits.h" 22e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project#include "clang/AST/ParentMap.h" 23e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project#include "clang/AST/StmtObjC.h" 24e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project#include "clang/AST/DeclCXX.h" 25e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project#include "clang/Basic/Builtins.h" 26e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project#include "clang/Basic/SourceManager.h" 27e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project#include "clang/Basic/PrettyStackTrace.h" 28e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project#include "llvm/Support/raw_ostream.h" 29e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project#include "llvm/ADT/ImmutableList.h" 30e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project 31e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project#ifndef NDEBUG 32e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project#include "llvm/Support/GraphWriter.h" 33e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project#endif 34e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project 35e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Projectusing namespace clang; 36e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Projectusing namespace ento; 37e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Projectusing llvm::APSInt; 38e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project 39e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project//===----------------------------------------------------------------------===// 40e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project// Utility functions. 41e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project//===----------------------------------------------------------------------===// 42e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project 43e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Projectstatic inline Selector GetNullarySelector(const char* name, ASTContext &Ctx) { 44e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project IdentifierInfo* II = &Ctx.Idents.get(name); 45e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project return Ctx.Selectors.getSelector(0, &II); 46e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project} 47e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project 48e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project//===----------------------------------------------------------------------===// 49e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project// Engine construction and deletion. 50e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project//===----------------------------------------------------------------------===// 51e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project 52e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source ProjectExprEngine::ExprEngine(AnalysisManager &mgr, bool gcEnabled) 53e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project : AMgr(mgr), 54e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project AnalysisDeclContexts(mgr.getAnalysisDeclContextManager()), 55e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project Engine(*this), 56e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project G(Engine.getGraph()), 57e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project StateMgr(getContext(), mgr.getStoreManagerCreator(), 58e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project mgr.getConstraintManagerCreator(), G.getAllocator(), 59e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project *this), 60e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project SymMgr(StateMgr.getSymbolManager()), 61e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project svalBuilder(StateMgr.getSValBuilder()), 62e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project EntryNode(NULL), 63e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project currentStmt(NULL), currentStmtIdx(0), currentBuilderContext(0), 64e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project NSExceptionII(NULL), NSExceptionInstanceRaiseSelectors(NULL), 65e9df6ba5a8fcccf306a80b1670b423be8fe7746The Android Open Source Project RaiseSel(GetNullarySelector("raise", getContext())), 66 ObjCGCEnabled(gcEnabled), BR(mgr, *this) { 67 68 if (mgr.shouldEagerlyTrimExplodedGraph()) { 69 // Enable eager node reclaimation when constructing the ExplodedGraph. 70 G.enableNodeReclamation(); 71 } 72} 73 74ExprEngine::~ExprEngine() { 75 BR.FlushReports(); 76 delete [] NSExceptionInstanceRaiseSelectors; 77} 78 79//===----------------------------------------------------------------------===// 80// Utility methods. 81//===----------------------------------------------------------------------===// 82 83ProgramStateRef ExprEngine::getInitialState(const LocationContext *InitLoc) { 84 ProgramStateRef state = StateMgr.getInitialState(InitLoc); 85 const Decl *D = InitLoc->getDecl(); 86 87 // Preconditions. 88 // FIXME: It would be nice if we had a more general mechanism to add 89 // such preconditions. Some day. 90 do { 91 92 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 93 // Precondition: the first argument of 'main' is an integer guaranteed 94 // to be > 0. 95 const IdentifierInfo *II = FD->getIdentifier(); 96 if (!II || !(II->getName() == "main" && FD->getNumParams() > 0)) 97 break; 98 99 const ParmVarDecl *PD = FD->getParamDecl(0); 100 QualType T = PD->getType(); 101 if (!T->isIntegerType()) 102 break; 103 104 const MemRegion *R = state->getRegion(PD, InitLoc); 105 if (!R) 106 break; 107 108 SVal V = state->getSVal(loc::MemRegionVal(R)); 109 SVal Constraint_untested = evalBinOp(state, BO_GT, V, 110 svalBuilder.makeZeroVal(T), 111 getContext().IntTy); 112 113 DefinedOrUnknownSVal *Constraint = 114 dyn_cast<DefinedOrUnknownSVal>(&Constraint_untested); 115 116 if (!Constraint) 117 break; 118 119 if (ProgramStateRef newState = state->assume(*Constraint, true)) 120 state = newState; 121 } 122 break; 123 } 124 while (0); 125 126 if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) { 127 // Precondition: 'self' is always non-null upon entry to an Objective-C 128 // method. 129 const ImplicitParamDecl *SelfD = MD->getSelfDecl(); 130 const MemRegion *R = state->getRegion(SelfD, InitLoc); 131 SVal V = state->getSVal(loc::MemRegionVal(R)); 132 133 if (const Loc *LV = dyn_cast<Loc>(&V)) { 134 // Assume that the pointer value in 'self' is non-null. 135 state = state->assume(*LV, true); 136 assert(state && "'self' cannot be null"); 137 } 138 } 139 140 if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(D)) { 141 if (!MD->isStatic()) { 142 // Precondition: 'this' is always non-null upon entry to the 143 // top-level function. This is our starting assumption for 144 // analyzing an "open" program. 145 const StackFrameContext *SFC = InitLoc->getCurrentStackFrame(); 146 if (SFC->getParent() == 0) { 147 loc::MemRegionVal L(getCXXThisRegion(MD, SFC)); 148 SVal V = state->getSVal(L); 149 if (const Loc *LV = dyn_cast<Loc>(&V)) { 150 state = state->assume(*LV, true); 151 assert(state && "'this' cannot be null"); 152 } 153 } 154 } 155 } 156 157 return state; 158} 159 160//===----------------------------------------------------------------------===// 161// Top-level transfer function logic (Dispatcher). 162//===----------------------------------------------------------------------===// 163 164/// evalAssume - Called by ConstraintManager. Used to call checker-specific 165/// logic for handling assumptions on symbolic values. 166ProgramStateRef ExprEngine::processAssume(ProgramStateRef state, 167 SVal cond, bool assumption) { 168 return getCheckerManager().runCheckersForEvalAssume(state, cond, assumption); 169} 170 171bool ExprEngine::wantsRegionChangeUpdate(ProgramStateRef state) { 172 return getCheckerManager().wantsRegionChangeUpdate(state); 173} 174 175ProgramStateRef 176ExprEngine::processRegionChanges(ProgramStateRef state, 177 const StoreManager::InvalidatedSymbols *invalidated, 178 ArrayRef<const MemRegion *> Explicits, 179 ArrayRef<const MemRegion *> Regions, 180 const CallOrObjCMessage *Call) { 181 return getCheckerManager().runCheckersForRegionChanges(state, invalidated, 182 Explicits, Regions, Call); 183} 184 185void ExprEngine::printState(raw_ostream &Out, ProgramStateRef State, 186 const char *NL, const char *Sep) { 187 getCheckerManager().runCheckersForPrintState(Out, State, NL, Sep); 188} 189 190void ExprEngine::processEndWorklist(bool hasWorkRemaining) { 191 getCheckerManager().runCheckersForEndAnalysis(G, BR, *this); 192} 193 194void ExprEngine::processCFGElement(const CFGElement E, ExplodedNode *Pred, 195 unsigned StmtIdx, NodeBuilderContext *Ctx) { 196 currentStmtIdx = StmtIdx; 197 currentBuilderContext = Ctx; 198 199 switch (E.getKind()) { 200 case CFGElement::Invalid: 201 llvm_unreachable("Unexpected CFGElement kind."); 202 case CFGElement::Statement: 203 ProcessStmt(const_cast<Stmt*>(E.getAs<CFGStmt>()->getStmt()), Pred); 204 return; 205 case CFGElement::Initializer: 206 ProcessInitializer(E.getAs<CFGInitializer>()->getInitializer(), Pred); 207 return; 208 case CFGElement::AutomaticObjectDtor: 209 case CFGElement::BaseDtor: 210 case CFGElement::MemberDtor: 211 case CFGElement::TemporaryDtor: 212 ProcessImplicitDtor(*E.getAs<CFGImplicitDtor>(), Pred); 213 return; 214 } 215} 216 217static bool shouldRemoveDeadBindings(AnalysisManager &AMgr, 218 const CFGStmt S, 219 const ExplodedNode *Pred, 220 const LocationContext *LC) { 221 222 // Are we never purging state values? 223 if (AMgr.getPurgeMode() == PurgeNone) 224 return false; 225 226 // Is this the beginning of a basic block? 227 if (isa<BlockEntrance>(Pred->getLocation())) 228 return true; 229 230 // Is this on a non-expression? 231 if (!isa<Expr>(S.getStmt())) 232 return true; 233 234 // Is this an expression that is consumed by another expression? If so, 235 // postpone cleaning out the state. 236 ParentMap &PM = LC->getAnalysisDeclContext()->getParentMap(); 237 return !PM.isConsumedExpr(cast<Expr>(S.getStmt())); 238} 239 240void ExprEngine::ProcessStmt(const CFGStmt S, 241 ExplodedNode *Pred) { 242 // Reclaim any unnecessary nodes in the ExplodedGraph. 243 G.reclaimRecentlyAllocatedNodes(); 244 245 currentStmt = S.getStmt(); 246 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 247 currentStmt->getLocStart(), 248 "Error evaluating statement"); 249 250 EntryNode = Pred; 251 252 ProgramStateRef EntryState = EntryNode->getState(); 253 CleanedState = EntryState; 254 255 // Create the cleaned state. 256 const LocationContext *LC = EntryNode->getLocationContext(); 257 SymbolReaper SymReaper(LC, currentStmt, SymMgr, getStoreManager()); 258 259 if (shouldRemoveDeadBindings(AMgr, S, Pred, LC)) { 260 getCheckerManager().runCheckersForLiveSymbols(CleanedState, SymReaper); 261 262 const StackFrameContext *SFC = LC->getCurrentStackFrame(); 263 264 // Create a state in which dead bindings are removed from the environment 265 // and the store. TODO: The function should just return new env and store, 266 // not a new state. 267 CleanedState = StateMgr.removeDeadBindings(CleanedState, SFC, SymReaper); 268 } 269 270 // Process any special transfer function for dead symbols. 271 ExplodedNodeSet Tmp; 272 // A tag to track convenience transitions, which can be removed at cleanup. 273 static SimpleProgramPointTag cleanupTag("ExprEngine : Clean Node"); 274 275 if (!SymReaper.hasDeadSymbols()) { 276 // Generate a CleanedNode that has the environment and store cleaned 277 // up. Since no symbols are dead, we can optimize and not clean out 278 // the constraint manager. 279 StmtNodeBuilder Bldr(Pred, Tmp, *currentBuilderContext); 280 Bldr.generateNode(currentStmt, EntryNode, CleanedState, false, &cleanupTag); 281 282 } else { 283 // Call checkers with the non-cleaned state so that they could query the 284 // values of the soon to be dead symbols. 285 ExplodedNodeSet CheckedSet; 286 getCheckerManager().runCheckersForDeadSymbols(CheckedSet, EntryNode, 287 SymReaper, currentStmt, *this); 288 289 // For each node in CheckedSet, generate CleanedNodes that have the 290 // environment, the store, and the constraints cleaned up but have the 291 // user-supplied states as the predecessors. 292 StmtNodeBuilder Bldr(CheckedSet, Tmp, *currentBuilderContext); 293 for (ExplodedNodeSet::const_iterator 294 I = CheckedSet.begin(), E = CheckedSet.end(); I != E; ++I) { 295 ProgramStateRef CheckerState = (*I)->getState(); 296 297 // The constraint manager has not been cleaned up yet, so clean up now. 298 CheckerState = getConstraintManager().removeDeadBindings(CheckerState, 299 SymReaper); 300 301 assert(StateMgr.haveEqualEnvironments(CheckerState, EntryState) && 302 "Checkers are not allowed to modify the Environment as a part of " 303 "checkDeadSymbols processing."); 304 assert(StateMgr.haveEqualStores(CheckerState, EntryState) && 305 "Checkers are not allowed to modify the Store as a part of " 306 "checkDeadSymbols processing."); 307 308 // Create a state based on CleanedState with CheckerState GDM and 309 // generate a transition to that state. 310 ProgramStateRef CleanedCheckerSt = 311 StateMgr.getPersistentStateWithGDM(CleanedState, CheckerState); 312 Bldr.generateNode(currentStmt, *I, CleanedCheckerSt, false, &cleanupTag, 313 ProgramPoint::PostPurgeDeadSymbolsKind); 314 } 315 } 316 317 ExplodedNodeSet Dst; 318 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { 319 ExplodedNodeSet DstI; 320 // Visit the statement. 321 Visit(currentStmt, *I, DstI); 322 Dst.insert(DstI); 323 } 324 325 // Enqueue the new nodes onto the work list. 326 Engine.enqueue(Dst, currentBuilderContext->getBlock(), currentStmtIdx); 327 328 // NULL out these variables to cleanup. 329 CleanedState = NULL; 330 EntryNode = NULL; 331 currentStmt = 0; 332} 333 334void ExprEngine::ProcessInitializer(const CFGInitializer Init, 335 ExplodedNode *Pred) { 336 ExplodedNodeSet Dst; 337 338 // We don't set EntryNode and currentStmt. And we don't clean up state. 339 const CXXCtorInitializer *BMI = Init.getInitializer(); 340 const StackFrameContext *stackFrame = 341 cast<StackFrameContext>(Pred->getLocationContext()); 342 const CXXConstructorDecl *decl = 343 cast<CXXConstructorDecl>(stackFrame->getDecl()); 344 const CXXThisRegion *thisReg = getCXXThisRegion(decl, stackFrame); 345 346 SVal thisVal = Pred->getState()->getSVal(thisReg); 347 348 if (BMI->isAnyMemberInitializer()) { 349 ExplodedNodeSet AfterEval; 350 351 // Evaluate the initializer. 352 Visit(BMI->getInit(), Pred, AfterEval); 353 354 StmtNodeBuilder Bldr(AfterEval, Dst, *currentBuilderContext); 355 for (ExplodedNodeSet::iterator I = AfterEval.begin(), 356 E = AfterEval.end(); I != E; ++I){ 357 ExplodedNode *P = *I; 358 ProgramStateRef state = P->getState(); 359 360 const FieldDecl *FD = BMI->getAnyMember(); 361 362 SVal FieldLoc = state->getLValue(FD, thisVal); 363 SVal InitVal = state->getSVal(BMI->getInit(), Pred->getLocationContext()); 364 state = state->bindLoc(FieldLoc, InitVal); 365 366 // Use a custom node building process. 367 PostInitializer PP(BMI, stackFrame); 368 // Builder automatically add the generated node to the deferred set, 369 // which are processed in the builder's dtor. 370 Bldr.generateNode(PP, P, state); 371 } 372 } else { 373 assert(BMI->isBaseInitializer()); 374 375 // Get the base class declaration. 376 const CXXConstructExpr *ctorExpr = cast<CXXConstructExpr>(BMI->getInit()); 377 378 // Create the base object region. 379 SVal baseVal = 380 getStoreManager().evalDerivedToBase(thisVal, ctorExpr->getType()); 381 const MemRegion *baseReg = baseVal.getAsRegion(); 382 assert(baseReg); 383 384 VisitCXXConstructExpr(ctorExpr, baseReg, Pred, Dst); 385 } 386 387 // Enqueue the new nodes onto the work list. 388 Engine.enqueue(Dst, currentBuilderContext->getBlock(), currentStmtIdx); 389} 390 391void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D, 392 ExplodedNode *Pred) { 393 ExplodedNodeSet Dst; 394 switch (D.getKind()) { 395 case CFGElement::AutomaticObjectDtor: 396 ProcessAutomaticObjDtor(cast<CFGAutomaticObjDtor>(D), Pred, Dst); 397 break; 398 case CFGElement::BaseDtor: 399 ProcessBaseDtor(cast<CFGBaseDtor>(D), Pred, Dst); 400 break; 401 case CFGElement::MemberDtor: 402 ProcessMemberDtor(cast<CFGMemberDtor>(D), Pred, Dst); 403 break; 404 case CFGElement::TemporaryDtor: 405 ProcessTemporaryDtor(cast<CFGTemporaryDtor>(D), Pred, Dst); 406 break; 407 default: 408 llvm_unreachable("Unexpected dtor kind."); 409 } 410 411 // Enqueue the new nodes onto the work list. 412 Engine.enqueue(Dst, currentBuilderContext->getBlock(), currentStmtIdx); 413} 414 415void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor Dtor, 416 ExplodedNode *Pred, 417 ExplodedNodeSet &Dst) { 418 ProgramStateRef state = Pred->getState(); 419 const VarDecl *varDecl = Dtor.getVarDecl(); 420 421 QualType varType = varDecl->getType(); 422 423 if (const ReferenceType *refType = varType->getAs<ReferenceType>()) 424 varType = refType->getPointeeType(); 425 426 const CXXRecordDecl *recordDecl = varType->getAsCXXRecordDecl(); 427 assert(recordDecl && "get CXXRecordDecl fail"); 428 const CXXDestructorDecl *dtorDecl = recordDecl->getDestructor(); 429 430 Loc dest = state->getLValue(varDecl, Pred->getLocationContext()); 431 432 VisitCXXDestructor(dtorDecl, cast<loc::MemRegionVal>(dest).getRegion(), 433 Dtor.getTriggerStmt(), Pred, Dst); 434} 435 436void ExprEngine::ProcessBaseDtor(const CFGBaseDtor D, 437 ExplodedNode *Pred, ExplodedNodeSet &Dst) {} 438 439void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D, 440 ExplodedNode *Pred, ExplodedNodeSet &Dst) {} 441 442void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D, 443 ExplodedNode *Pred, 444 ExplodedNodeSet &Dst) {} 445 446void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, 447 ExplodedNodeSet &DstTop) { 448 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 449 S->getLocStart(), 450 "Error evaluating statement"); 451 ExplodedNodeSet Dst; 452 StmtNodeBuilder Bldr(Pred, DstTop, *currentBuilderContext); 453 454 // Expressions to ignore. 455 if (const Expr *Ex = dyn_cast<Expr>(S)) 456 S = Ex->IgnoreParens(); 457 458 // FIXME: add metadata to the CFG so that we can disable 459 // this check when we KNOW that there is no block-level subexpression. 460 // The motivation is that this check requires a hashtable lookup. 461 462 if (S != currentStmt && Pred->getLocationContext()->getCFG()->isBlkExpr(S)) 463 return; 464 465 switch (S->getStmtClass()) { 466 // C++ and ARC stuff we don't support yet. 467 case Expr::ObjCIndirectCopyRestoreExprClass: 468 case Stmt::CXXBindTemporaryExprClass: 469 case Stmt::CXXCatchStmtClass: 470 case Stmt::CXXDependentScopeMemberExprClass: 471 case Stmt::CXXPseudoDestructorExprClass: 472 case Stmt::CXXThrowExprClass: 473 case Stmt::CXXTryStmtClass: 474 case Stmt::CXXTypeidExprClass: 475 case Stmt::CXXUuidofExprClass: 476 case Stmt::CXXUnresolvedConstructExprClass: 477 case Stmt::CXXScalarValueInitExprClass: 478 case Stmt::DependentScopeDeclRefExprClass: 479 case Stmt::UnaryTypeTraitExprClass: 480 case Stmt::BinaryTypeTraitExprClass: 481 case Stmt::TypeTraitExprClass: 482 case Stmt::ArrayTypeTraitExprClass: 483 case Stmt::ExpressionTraitExprClass: 484 case Stmt::UnresolvedLookupExprClass: 485 case Stmt::UnresolvedMemberExprClass: 486 case Stmt::CXXNoexceptExprClass: 487 case Stmt::PackExpansionExprClass: 488 case Stmt::SubstNonTypeTemplateParmPackExprClass: 489 case Stmt::SEHTryStmtClass: 490 case Stmt::SEHExceptStmtClass: 491 case Stmt::LambdaExprClass: 492 case Stmt::SEHFinallyStmtClass: { 493 const ExplodedNode *node = Bldr.generateNode(S, Pred, Pred->getState()); 494 Engine.addAbortedBlock(node, currentBuilderContext->getBlock()); 495 break; 496 } 497 498 // We don't handle default arguments either yet, but we can fake it 499 // for now by just skipping them. 500 case Stmt::SubstNonTypeTemplateParmExprClass: 501 case Stmt::CXXDefaultArgExprClass: 502 break; 503 504 case Stmt::ParenExprClass: 505 llvm_unreachable("ParenExprs already handled."); 506 case Stmt::GenericSelectionExprClass: 507 llvm_unreachable("GenericSelectionExprs already handled."); 508 // Cases that should never be evaluated simply because they shouldn't 509 // appear in the CFG. 510 case Stmt::BreakStmtClass: 511 case Stmt::CaseStmtClass: 512 case Stmt::CompoundStmtClass: 513 case Stmt::ContinueStmtClass: 514 case Stmt::CXXForRangeStmtClass: 515 case Stmt::DefaultStmtClass: 516 case Stmt::DoStmtClass: 517 case Stmt::ForStmtClass: 518 case Stmt::GotoStmtClass: 519 case Stmt::IfStmtClass: 520 case Stmt::IndirectGotoStmtClass: 521 case Stmt::LabelStmtClass: 522 case Stmt::NoStmtClass: 523 case Stmt::NullStmtClass: 524 case Stmt::SwitchStmtClass: 525 case Stmt::WhileStmtClass: 526 case Expr::MSDependentExistsStmtClass: 527 llvm_unreachable("Stmt should not be in analyzer evaluation loop"); 528 529 case Stmt::GNUNullExprClass: { 530 // GNU __null is a pointer-width integer, not an actual pointer. 531 ProgramStateRef state = Pred->getState(); 532 state = state->BindExpr(S, Pred->getLocationContext(), 533 svalBuilder.makeIntValWithPtrWidth(0, false)); 534 Bldr.generateNode(S, Pred, state); 535 break; 536 } 537 538 case Stmt::ObjCAtSynchronizedStmtClass: 539 Bldr.takeNodes(Pred); 540 VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S), Pred, Dst); 541 Bldr.addNodes(Dst); 542 break; 543 544 case Stmt::ObjCPropertyRefExprClass: 545 // Implicitly handled by Environment::getSVal(). 546 break; 547 548 case Stmt::ImplicitValueInitExprClass: { 549 ProgramStateRef state = Pred->getState(); 550 QualType ty = cast<ImplicitValueInitExpr>(S)->getType(); 551 SVal val = svalBuilder.makeZeroVal(ty); 552 Bldr.generateNode(S, Pred, state->BindExpr(S, Pred->getLocationContext(), 553 val)); 554 break; 555 } 556 557 case Stmt::ExprWithCleanupsClass: 558 Bldr.takeNodes(Pred); 559 Visit(cast<ExprWithCleanups>(S)->getSubExpr(), Pred, Dst); 560 Bldr.addNodes(Dst); 561 break; 562 563 // Cases not handled yet; but will handle some day. 564 case Stmt::DesignatedInitExprClass: 565 case Stmt::ExtVectorElementExprClass: 566 case Stmt::ImaginaryLiteralClass: 567 case Stmt::ObjCAtCatchStmtClass: 568 case Stmt::ObjCAtFinallyStmtClass: 569 case Stmt::ObjCAtTryStmtClass: 570 case Stmt::ObjCAutoreleasePoolStmtClass: 571 case Stmt::ObjCEncodeExprClass: 572 case Stmt::ObjCIsaExprClass: 573 case Stmt::ObjCProtocolExprClass: 574 case Stmt::ObjCSelectorExprClass: 575 case Stmt::ObjCStringLiteralClass: 576 case Stmt::ParenListExprClass: 577 case Stmt::PredefinedExprClass: 578 case Stmt::ShuffleVectorExprClass: 579 case Stmt::VAArgExprClass: 580 case Stmt::CUDAKernelCallExprClass: 581 case Stmt::OpaqueValueExprClass: 582 case Stmt::AsTypeExprClass: 583 case Stmt::AtomicExprClass: 584 // Fall through. 585 586 // Cases we intentionally don't evaluate, since they don't need 587 // to be explicitly evaluated. 588 case Stmt::AddrLabelExprClass: 589 case Stmt::IntegerLiteralClass: 590 case Stmt::CharacterLiteralClass: 591 case Stmt::CXXBoolLiteralExprClass: 592 case Stmt::FloatingLiteralClass: 593 case Stmt::SizeOfPackExprClass: 594 case Stmt::CXXNullPtrLiteralExprClass: { 595 Bldr.takeNodes(Pred); 596 ExplodedNodeSet preVisit; 597 getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this); 598 getCheckerManager().runCheckersForPostStmt(Dst, preVisit, S, *this); 599 Bldr.addNodes(Dst); 600 break; 601 } 602 603 case Stmt::ArraySubscriptExprClass: 604 Bldr.takeNodes(Pred); 605 VisitLvalArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Pred, Dst); 606 Bldr.addNodes(Dst); 607 break; 608 609 case Stmt::AsmStmtClass: 610 Bldr.takeNodes(Pred); 611 VisitAsmStmt(cast<AsmStmt>(S), Pred, Dst); 612 Bldr.addNodes(Dst); 613 break; 614 615 case Stmt::BlockDeclRefExprClass: { 616 Bldr.takeNodes(Pred); 617 const BlockDeclRefExpr *BE = cast<BlockDeclRefExpr>(S); 618 VisitCommonDeclRefExpr(BE, BE->getDecl(), Pred, Dst); 619 Bldr.addNodes(Dst); 620 break; 621 } 622 623 case Stmt::BlockExprClass: 624 Bldr.takeNodes(Pred); 625 VisitBlockExpr(cast<BlockExpr>(S), Pred, Dst); 626 Bldr.addNodes(Dst); 627 break; 628 629 case Stmt::BinaryOperatorClass: { 630 const BinaryOperator* B = cast<BinaryOperator>(S); 631 if (B->isLogicalOp()) { 632 Bldr.takeNodes(Pred); 633 VisitLogicalExpr(B, Pred, Dst); 634 Bldr.addNodes(Dst); 635 break; 636 } 637 else if (B->getOpcode() == BO_Comma) { 638 ProgramStateRef state = Pred->getState(); 639 Bldr.generateNode(B, Pred, 640 state->BindExpr(B, Pred->getLocationContext(), 641 state->getSVal(B->getRHS(), 642 Pred->getLocationContext()))); 643 break; 644 } 645 646 Bldr.takeNodes(Pred); 647 648 if (AMgr.shouldEagerlyAssume() && 649 (B->isRelationalOp() || B->isEqualityOp())) { 650 ExplodedNodeSet Tmp; 651 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Tmp); 652 evalEagerlyAssume(Dst, Tmp, cast<Expr>(S)); 653 } 654 else 655 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst); 656 657 Bldr.addNodes(Dst); 658 break; 659 } 660 661 case Stmt::CallExprClass: 662 case Stmt::CXXOperatorCallExprClass: 663 case Stmt::CXXMemberCallExprClass: { 664 Bldr.takeNodes(Pred); 665 VisitCallExpr(cast<CallExpr>(S), Pred, Dst); 666 Bldr.addNodes(Dst); 667 break; 668 } 669 670 case Stmt::CXXTemporaryObjectExprClass: 671 case Stmt::CXXConstructExprClass: { 672 const CXXConstructExpr *C = cast<CXXConstructExpr>(S); 673 // For block-level CXXConstructExpr, we don't have a destination region. 674 // Let VisitCXXConstructExpr() create one. 675 Bldr.takeNodes(Pred); 676 VisitCXXConstructExpr(C, 0, Pred, Dst); 677 Bldr.addNodes(Dst); 678 break; 679 } 680 681 case Stmt::CXXNewExprClass: { 682 Bldr.takeNodes(Pred); 683 const CXXNewExpr *NE = cast<CXXNewExpr>(S); 684 VisitCXXNewExpr(NE, Pred, Dst); 685 Bldr.addNodes(Dst); 686 break; 687 } 688 689 case Stmt::CXXDeleteExprClass: { 690 Bldr.takeNodes(Pred); 691 const CXXDeleteExpr *CDE = cast<CXXDeleteExpr>(S); 692 VisitCXXDeleteExpr(CDE, Pred, Dst); 693 Bldr.addNodes(Dst); 694 break; 695 } 696 // FIXME: ChooseExpr is really a constant. We need to fix 697 // the CFG do not model them as explicit control-flow. 698 699 case Stmt::ChooseExprClass: { // __builtin_choose_expr 700 Bldr.takeNodes(Pred); 701 const ChooseExpr *C = cast<ChooseExpr>(S); 702 VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst); 703 Bldr.addNodes(Dst); 704 break; 705 } 706 707 case Stmt::CompoundAssignOperatorClass: 708 Bldr.takeNodes(Pred); 709 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst); 710 Bldr.addNodes(Dst); 711 break; 712 713 case Stmt::CompoundLiteralExprClass: 714 Bldr.takeNodes(Pred); 715 VisitCompoundLiteralExpr(cast<CompoundLiteralExpr>(S), Pred, Dst); 716 Bldr.addNodes(Dst); 717 break; 718 719 case Stmt::BinaryConditionalOperatorClass: 720 case Stmt::ConditionalOperatorClass: { // '?' operator 721 Bldr.takeNodes(Pred); 722 const AbstractConditionalOperator *C 723 = cast<AbstractConditionalOperator>(S); 724 VisitGuardedExpr(C, C->getTrueExpr(), C->getFalseExpr(), Pred, Dst); 725 Bldr.addNodes(Dst); 726 break; 727 } 728 729 case Stmt::CXXThisExprClass: 730 Bldr.takeNodes(Pred); 731 VisitCXXThisExpr(cast<CXXThisExpr>(S), Pred, Dst); 732 Bldr.addNodes(Dst); 733 break; 734 735 case Stmt::DeclRefExprClass: { 736 Bldr.takeNodes(Pred); 737 const DeclRefExpr *DE = cast<DeclRefExpr>(S); 738 VisitCommonDeclRefExpr(DE, DE->getDecl(), Pred, Dst); 739 Bldr.addNodes(Dst); 740 break; 741 } 742 743 case Stmt::DeclStmtClass: 744 Bldr.takeNodes(Pred); 745 VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst); 746 Bldr.addNodes(Dst); 747 break; 748 749 case Stmt::ImplicitCastExprClass: 750 case Stmt::CStyleCastExprClass: 751 case Stmt::CXXStaticCastExprClass: 752 case Stmt::CXXDynamicCastExprClass: 753 case Stmt::CXXReinterpretCastExprClass: 754 case Stmt::CXXConstCastExprClass: 755 case Stmt::CXXFunctionalCastExprClass: 756 case Stmt::ObjCBridgedCastExprClass: { 757 Bldr.takeNodes(Pred); 758 const CastExpr *C = cast<CastExpr>(S); 759 // Handle the previsit checks. 760 ExplodedNodeSet dstPrevisit; 761 getCheckerManager().runCheckersForPreStmt(dstPrevisit, Pred, C, *this); 762 763 // Handle the expression itself. 764 ExplodedNodeSet dstExpr; 765 for (ExplodedNodeSet::iterator i = dstPrevisit.begin(), 766 e = dstPrevisit.end(); i != e ; ++i) { 767 VisitCast(C, C->getSubExpr(), *i, dstExpr); 768 } 769 770 // Handle the postvisit checks. 771 getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, C, *this); 772 Bldr.addNodes(Dst); 773 break; 774 } 775 776 case Expr::MaterializeTemporaryExprClass: { 777 Bldr.takeNodes(Pred); 778 const MaterializeTemporaryExpr *Materialize 779 = cast<MaterializeTemporaryExpr>(S); 780 if (!Materialize->getType()->isRecordType()) 781 CreateCXXTemporaryObject(Materialize, Pred, Dst); 782 else 783 Visit(Materialize->GetTemporaryExpr(), Pred, Dst); 784 Bldr.addNodes(Dst); 785 break; 786 } 787 788 case Stmt::InitListExprClass: 789 Bldr.takeNodes(Pred); 790 VisitInitListExpr(cast<InitListExpr>(S), Pred, Dst); 791 Bldr.addNodes(Dst); 792 break; 793 794 case Stmt::MemberExprClass: 795 Bldr.takeNodes(Pred); 796 VisitMemberExpr(cast<MemberExpr>(S), Pred, Dst); 797 Bldr.addNodes(Dst); 798 break; 799 800 case Stmt::ObjCIvarRefExprClass: 801 Bldr.takeNodes(Pred); 802 VisitLvalObjCIvarRefExpr(cast<ObjCIvarRefExpr>(S), Pred, Dst); 803 Bldr.addNodes(Dst); 804 break; 805 806 case Stmt::ObjCForCollectionStmtClass: 807 Bldr.takeNodes(Pred); 808 VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S), Pred, Dst); 809 Bldr.addNodes(Dst); 810 break; 811 812 case Stmt::ObjCMessageExprClass: { 813 Bldr.takeNodes(Pred); 814 // Is this a property access? 815 const ParentMap &PM = Pred->getLocationContext()->getParentMap(); 816 const ObjCMessageExpr *ME = cast<ObjCMessageExpr>(S); 817 bool evaluated = false; 818 819 if (const PseudoObjectExpr *PO = 820 dyn_cast_or_null<PseudoObjectExpr>(PM.getParent(S))) { 821 const Expr *syntactic = PO->getSyntacticForm(); 822 if (const ObjCPropertyRefExpr *PR = 823 dyn_cast<ObjCPropertyRefExpr>(syntactic)) { 824 bool isSetter = ME->getNumArgs() > 0; 825 VisitObjCMessage(ObjCMessage(ME, PR, isSetter), Pred, Dst); 826 evaluated = true; 827 } 828 else if (isa<BinaryOperator>(syntactic)) { 829 VisitObjCMessage(ObjCMessage(ME, 0, true), Pred, Dst); 830 } 831 } 832 833 if (!evaluated) 834 VisitObjCMessage(ME, Pred, Dst); 835 836 Bldr.addNodes(Dst); 837 break; 838 } 839 840 case Stmt::ObjCAtThrowStmtClass: { 841 // FIXME: This is not complete. We basically treat @throw as 842 // an abort. 843 Bldr.generateNode(S, Pred, Pred->getState()); 844 break; 845 } 846 847 case Stmt::ReturnStmtClass: 848 Bldr.takeNodes(Pred); 849 VisitReturnStmt(cast<ReturnStmt>(S), Pred, Dst); 850 Bldr.addNodes(Dst); 851 break; 852 853 case Stmt::OffsetOfExprClass: 854 Bldr.takeNodes(Pred); 855 VisitOffsetOfExpr(cast<OffsetOfExpr>(S), Pred, Dst); 856 Bldr.addNodes(Dst); 857 break; 858 859 case Stmt::UnaryExprOrTypeTraitExprClass: 860 Bldr.takeNodes(Pred); 861 VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S), 862 Pred, Dst); 863 Bldr.addNodes(Dst); 864 break; 865 866 case Stmt::StmtExprClass: { 867 const StmtExpr *SE = cast<StmtExpr>(S); 868 869 if (SE->getSubStmt()->body_empty()) { 870 // Empty statement expression. 871 assert(SE->getType() == getContext().VoidTy 872 && "Empty statement expression must have void type."); 873 break; 874 } 875 876 if (Expr *LastExpr = dyn_cast<Expr>(*SE->getSubStmt()->body_rbegin())) { 877 ProgramStateRef state = Pred->getState(); 878 Bldr.generateNode(SE, Pred, 879 state->BindExpr(SE, Pred->getLocationContext(), 880 state->getSVal(LastExpr, 881 Pred->getLocationContext()))); 882 } 883 break; 884 } 885 886 case Stmt::StringLiteralClass: { 887 ProgramStateRef state = Pred->getState(); 888 SVal V = state->getLValue(cast<StringLiteral>(S)); 889 Bldr.generateNode(S, Pred, state->BindExpr(S, Pred->getLocationContext(), 890 V)); 891 return; 892 } 893 894 case Stmt::UnaryOperatorClass: { 895 Bldr.takeNodes(Pred); 896 const UnaryOperator *U = cast<UnaryOperator>(S); 897 if (AMgr.shouldEagerlyAssume() && (U->getOpcode() == UO_LNot)) { 898 ExplodedNodeSet Tmp; 899 VisitUnaryOperator(U, Pred, Tmp); 900 evalEagerlyAssume(Dst, Tmp, U); 901 } 902 else 903 VisitUnaryOperator(U, Pred, Dst); 904 Bldr.addNodes(Dst); 905 break; 906 } 907 908 case Stmt::PseudoObjectExprClass: { 909 Bldr.takeNodes(Pred); 910 ProgramStateRef state = Pred->getState(); 911 const PseudoObjectExpr *PE = cast<PseudoObjectExpr>(S); 912 if (const Expr *Result = PE->getResultExpr()) { 913 SVal V = state->getSVal(Result, Pred->getLocationContext()); 914 Bldr.generateNode(S, Pred, 915 state->BindExpr(S, Pred->getLocationContext(), V)); 916 } 917 else 918 Bldr.generateNode(S, Pred, 919 state->BindExpr(S, Pred->getLocationContext(), 920 UnknownVal())); 921 922 Bldr.addNodes(Dst); 923 break; 924 } 925 } 926} 927 928/// Block entrance. (Update counters). 929void ExprEngine::processCFGBlockEntrance(NodeBuilderWithSinks &nodeBuilder) { 930 931 // FIXME: Refactor this into a checker. 932 ExplodedNode *pred = nodeBuilder.getContext().getPred(); 933 934 if (nodeBuilder.getContext().getCurrentBlockCount() >= AMgr.getMaxVisit()) { 935 static SimpleProgramPointTag tag("ExprEngine : Block count exceeded"); 936 nodeBuilder.generateNode(pred->getState(), pred, &tag, true); 937 } 938} 939 940//===----------------------------------------------------------------------===// 941// Branch processing. 942//===----------------------------------------------------------------------===// 943 944ProgramStateRef ExprEngine::MarkBranch(ProgramStateRef state, 945 const Stmt *Terminator, 946 const LocationContext *LCtx, 947 bool branchTaken) { 948 949 switch (Terminator->getStmtClass()) { 950 default: 951 return state; 952 953 case Stmt::BinaryOperatorClass: { // '&&' and '||' 954 955 const BinaryOperator* B = cast<BinaryOperator>(Terminator); 956 BinaryOperator::Opcode Op = B->getOpcode(); 957 958 assert (Op == BO_LAnd || Op == BO_LOr); 959 960 // For &&, if we take the true branch, then the value of the whole 961 // expression is that of the RHS expression. 962 // 963 // For ||, if we take the false branch, then the value of the whole 964 // expression is that of the RHS expression. 965 966 const Expr *Ex = (Op == BO_LAnd && branchTaken) || 967 (Op == BO_LOr && !branchTaken) 968 ? B->getRHS() : B->getLHS(); 969 970 return state->BindExpr(B, LCtx, UndefinedVal(Ex)); 971 } 972 973 case Stmt::BinaryConditionalOperatorClass: 974 case Stmt::ConditionalOperatorClass: { // ?: 975 const AbstractConditionalOperator* C 976 = cast<AbstractConditionalOperator>(Terminator); 977 978 // For ?, if branchTaken == true then the value is either the LHS or 979 // the condition itself. (GNU extension). 980 981 const Expr *Ex; 982 983 if (branchTaken) 984 Ex = C->getTrueExpr(); 985 else 986 Ex = C->getFalseExpr(); 987 988 return state->BindExpr(C, LCtx, UndefinedVal(Ex)); 989 } 990 991 case Stmt::ChooseExprClass: { // ?: 992 993 const ChooseExpr *C = cast<ChooseExpr>(Terminator); 994 995 const Expr *Ex = branchTaken ? C->getLHS() : C->getRHS(); 996 return state->BindExpr(C, LCtx, UndefinedVal(Ex)); 997 } 998 } 999} 1000 1001/// RecoverCastedSymbol - A helper function for ProcessBranch that is used 1002/// to try to recover some path-sensitivity for casts of symbolic 1003/// integers that promote their values (which are currently not tracked well). 1004/// This function returns the SVal bound to Condition->IgnoreCasts if all the 1005// cast(s) did was sign-extend the original value. 1006static SVal RecoverCastedSymbol(ProgramStateManager& StateMgr, 1007 ProgramStateRef state, 1008 const Stmt *Condition, 1009 const LocationContext *LCtx, 1010 ASTContext &Ctx) { 1011 1012 const Expr *Ex = dyn_cast<Expr>(Condition); 1013 if (!Ex) 1014 return UnknownVal(); 1015 1016 uint64_t bits = 0; 1017 bool bitsInit = false; 1018 1019 while (const CastExpr *CE = dyn_cast<CastExpr>(Ex)) { 1020 QualType T = CE->getType(); 1021 1022 if (!T->isIntegerType()) 1023 return UnknownVal(); 1024 1025 uint64_t newBits = Ctx.getTypeSize(T); 1026 if (!bitsInit || newBits < bits) { 1027 bitsInit = true; 1028 bits = newBits; 1029 } 1030 1031 Ex = CE->getSubExpr(); 1032 } 1033 1034 // We reached a non-cast. Is it a symbolic value? 1035 QualType T = Ex->getType(); 1036 1037 if (!bitsInit || !T->isIntegerType() || Ctx.getTypeSize(T) > bits) 1038 return UnknownVal(); 1039 1040 return state->getSVal(Ex, LCtx); 1041} 1042 1043void ExprEngine::processBranch(const Stmt *Condition, const Stmt *Term, 1044 NodeBuilderContext& BldCtx, 1045 ExplodedNode *Pred, 1046 ExplodedNodeSet &Dst, 1047 const CFGBlock *DstT, 1048 const CFGBlock *DstF) { 1049 currentBuilderContext = &BldCtx; 1050 1051 // Check for NULL conditions; e.g. "for(;;)" 1052 if (!Condition) { 1053 BranchNodeBuilder NullCondBldr(Pred, Dst, BldCtx, DstT, DstF); 1054 NullCondBldr.markInfeasible(false); 1055 NullCondBldr.generateNode(Pred->getState(), true, Pred); 1056 return; 1057 } 1058 1059 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 1060 Condition->getLocStart(), 1061 "Error evaluating branch"); 1062 1063 ExplodedNodeSet CheckersOutSet; 1064 getCheckerManager().runCheckersForBranchCondition(Condition, CheckersOutSet, 1065 Pred, *this); 1066 // We generated only sinks. 1067 if (CheckersOutSet.empty()) 1068 return; 1069 1070 BranchNodeBuilder builder(CheckersOutSet, Dst, BldCtx, DstT, DstF); 1071 for (NodeBuilder::iterator I = CheckersOutSet.begin(), 1072 E = CheckersOutSet.end(); E != I; ++I) { 1073 ExplodedNode *PredI = *I; 1074 1075 if (PredI->isSink()) 1076 continue; 1077 1078 ProgramStateRef PrevState = Pred->getState(); 1079 SVal X = PrevState->getSVal(Condition, Pred->getLocationContext()); 1080 1081 if (X.isUnknownOrUndef()) { 1082 // Give it a chance to recover from unknown. 1083 if (const Expr *Ex = dyn_cast<Expr>(Condition)) { 1084 if (Ex->getType()->isIntegerType()) { 1085 // Try to recover some path-sensitivity. Right now casts of symbolic 1086 // integers that promote their values are currently not tracked well. 1087 // If 'Condition' is such an expression, try and recover the 1088 // underlying value and use that instead. 1089 SVal recovered = RecoverCastedSymbol(getStateManager(), 1090 PrevState, Condition, 1091 Pred->getLocationContext(), 1092 getContext()); 1093 1094 if (!recovered.isUnknown()) { 1095 X = recovered; 1096 } 1097 } 1098 } 1099 } 1100 1101 const LocationContext *LCtx = PredI->getLocationContext(); 1102 1103 // If the condition is still unknown, give up. 1104 if (X.isUnknownOrUndef()) { 1105 builder.generateNode(MarkBranch(PrevState, Term, LCtx, true), 1106 true, PredI); 1107 builder.generateNode(MarkBranch(PrevState, Term, LCtx, false), 1108 false, PredI); 1109 continue; 1110 } 1111 1112 DefinedSVal V = cast<DefinedSVal>(X); 1113 1114 // Process the true branch. 1115 if (builder.isFeasible(true)) { 1116 if (ProgramStateRef state = PrevState->assume(V, true)) 1117 builder.generateNode(MarkBranch(state, Term, LCtx, true), 1118 true, PredI); 1119 else 1120 builder.markInfeasible(true); 1121 } 1122 1123 // Process the false branch. 1124 if (builder.isFeasible(false)) { 1125 if (ProgramStateRef state = PrevState->assume(V, false)) 1126 builder.generateNode(MarkBranch(state, Term, LCtx, false), 1127 false, PredI); 1128 else 1129 builder.markInfeasible(false); 1130 } 1131 } 1132 currentBuilderContext = 0; 1133} 1134 1135/// processIndirectGoto - Called by CoreEngine. Used to generate successor 1136/// nodes by processing the 'effects' of a computed goto jump. 1137void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) { 1138 1139 ProgramStateRef state = builder.getState(); 1140 SVal V = state->getSVal(builder.getTarget(), builder.getLocationContext()); 1141 1142 // Three possibilities: 1143 // 1144 // (1) We know the computed label. 1145 // (2) The label is NULL (or some other constant), or Undefined. 1146 // (3) We have no clue about the label. Dispatch to all targets. 1147 // 1148 1149 typedef IndirectGotoNodeBuilder::iterator iterator; 1150 1151 if (isa<loc::GotoLabel>(V)) { 1152 const LabelDecl *L = cast<loc::GotoLabel>(V).getLabel(); 1153 1154 for (iterator I = builder.begin(), E = builder.end(); I != E; ++I) { 1155 if (I.getLabel() == L) { 1156 builder.generateNode(I, state); 1157 return; 1158 } 1159 } 1160 1161 llvm_unreachable("No block with label."); 1162 } 1163 1164 if (isa<loc::ConcreteInt>(V) || isa<UndefinedVal>(V)) { 1165 // Dispatch to the first target and mark it as a sink. 1166 //ExplodedNode* N = builder.generateNode(builder.begin(), state, true); 1167 // FIXME: add checker visit. 1168 // UndefBranches.insert(N); 1169 return; 1170 } 1171 1172 // This is really a catch-all. We don't support symbolics yet. 1173 // FIXME: Implement dispatch for symbolic pointers. 1174 1175 for (iterator I=builder.begin(), E=builder.end(); I != E; ++I) 1176 builder.generateNode(I, state); 1177} 1178 1179/// ProcessEndPath - Called by CoreEngine. Used to generate end-of-path 1180/// nodes when the control reaches the end of a function. 1181void ExprEngine::processEndOfFunction(NodeBuilderContext& BC) { 1182 StateMgr.EndPath(BC.Pred->getState()); 1183 ExplodedNodeSet Dst; 1184 getCheckerManager().runCheckersForEndPath(BC, Dst, *this); 1185 Engine.enqueueEndOfFunction(Dst); 1186} 1187 1188/// ProcessSwitch - Called by CoreEngine. Used to generate successor 1189/// nodes by processing the 'effects' of a switch statement. 1190void ExprEngine::processSwitch(SwitchNodeBuilder& builder) { 1191 typedef SwitchNodeBuilder::iterator iterator; 1192 ProgramStateRef state = builder.getState(); 1193 const Expr *CondE = builder.getCondition(); 1194 SVal CondV_untested = state->getSVal(CondE, builder.getLocationContext()); 1195 1196 if (CondV_untested.isUndef()) { 1197 //ExplodedNode* N = builder.generateDefaultCaseNode(state, true); 1198 // FIXME: add checker 1199 //UndefBranches.insert(N); 1200 1201 return; 1202 } 1203 DefinedOrUnknownSVal CondV = cast<DefinedOrUnknownSVal>(CondV_untested); 1204 1205 ProgramStateRef DefaultSt = state; 1206 1207 iterator I = builder.begin(), EI = builder.end(); 1208 bool defaultIsFeasible = I == EI; 1209 1210 for ( ; I != EI; ++I) { 1211 // Successor may be pruned out during CFG construction. 1212 if (!I.getBlock()) 1213 continue; 1214 1215 const CaseStmt *Case = I.getCase(); 1216 1217 // Evaluate the LHS of the case value. 1218 llvm::APSInt V1 = Case->getLHS()->EvaluateKnownConstInt(getContext()); 1219 assert(V1.getBitWidth() == getContext().getTypeSize(CondE->getType())); 1220 1221 // Get the RHS of the case, if it exists. 1222 llvm::APSInt V2; 1223 if (const Expr *E = Case->getRHS()) 1224 V2 = E->EvaluateKnownConstInt(getContext()); 1225 else 1226 V2 = V1; 1227 1228 // FIXME: Eventually we should replace the logic below with a range 1229 // comparison, rather than concretize the values within the range. 1230 // This should be easy once we have "ranges" for NonLVals. 1231 1232 do { 1233 nonloc::ConcreteInt CaseVal(getBasicVals().getValue(V1)); 1234 DefinedOrUnknownSVal Res = svalBuilder.evalEQ(DefaultSt ? DefaultSt : state, 1235 CondV, CaseVal); 1236 1237 // Now "assume" that the case matches. 1238 if (ProgramStateRef stateNew = state->assume(Res, true)) { 1239 builder.generateCaseStmtNode(I, stateNew); 1240 1241 // If CondV evaluates to a constant, then we know that this 1242 // is the *only* case that we can take, so stop evaluating the 1243 // others. 1244 if (isa<nonloc::ConcreteInt>(CondV)) 1245 return; 1246 } 1247 1248 // Now "assume" that the case doesn't match. Add this state 1249 // to the default state (if it is feasible). 1250 if (DefaultSt) { 1251 if (ProgramStateRef stateNew = DefaultSt->assume(Res, false)) { 1252 defaultIsFeasible = true; 1253 DefaultSt = stateNew; 1254 } 1255 else { 1256 defaultIsFeasible = false; 1257 DefaultSt = NULL; 1258 } 1259 } 1260 1261 // Concretize the next value in the range. 1262 if (V1 == V2) 1263 break; 1264 1265 ++V1; 1266 assert (V1 <= V2); 1267 1268 } while (true); 1269 } 1270 1271 if (!defaultIsFeasible) 1272 return; 1273 1274 // If we have switch(enum value), the default branch is not 1275 // feasible if all of the enum constants not covered by 'case:' statements 1276 // are not feasible values for the switch condition. 1277 // 1278 // Note that this isn't as accurate as it could be. Even if there isn't 1279 // a case for a particular enum value as long as that enum value isn't 1280 // feasible then it shouldn't be considered for making 'default:' reachable. 1281 const SwitchStmt *SS = builder.getSwitch(); 1282 const Expr *CondExpr = SS->getCond()->IgnoreParenImpCasts(); 1283 if (CondExpr->getType()->getAs<EnumType>()) { 1284 if (SS->isAllEnumCasesCovered()) 1285 return; 1286 } 1287 1288 builder.generateDefaultCaseNode(DefaultSt); 1289} 1290 1291//===----------------------------------------------------------------------===// 1292// Transfer functions: Loads and stores. 1293//===----------------------------------------------------------------------===// 1294 1295void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D, 1296 ExplodedNode *Pred, 1297 ExplodedNodeSet &Dst) { 1298 StmtNodeBuilder Bldr(Pred, Dst, *currentBuilderContext); 1299 1300 ProgramStateRef state = Pred->getState(); 1301 const LocationContext *LCtx = Pred->getLocationContext(); 1302 1303 if (const VarDecl *VD = dyn_cast<VarDecl>(D)) { 1304 assert(Ex->isLValue()); 1305 SVal V = state->getLValue(VD, Pred->getLocationContext()); 1306 1307 // For references, the 'lvalue' is the pointer address stored in the 1308 // reference region. 1309 if (VD->getType()->isReferenceType()) { 1310 if (const MemRegion *R = V.getAsRegion()) 1311 V = state->getSVal(R); 1312 else 1313 V = UnknownVal(); 1314 } 1315 1316 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), false, 0, 1317 ProgramPoint::PostLValueKind); 1318 return; 1319 } 1320 if (const EnumConstantDecl *ED = dyn_cast<EnumConstantDecl>(D)) { 1321 assert(!Ex->isLValue()); 1322 SVal V = svalBuilder.makeIntVal(ED->getInitVal()); 1323 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V)); 1324 return; 1325 } 1326 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 1327 SVal V = svalBuilder.getFunctionPointer(FD); 1328 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), false, 0, 1329 ProgramPoint::PostLValueKind); 1330 return; 1331 } 1332 assert (false && 1333 "ValueDecl support for this ValueDecl not implemented."); 1334} 1335 1336/// VisitArraySubscriptExpr - Transfer function for array accesses 1337void ExprEngine::VisitLvalArraySubscriptExpr(const ArraySubscriptExpr *A, 1338 ExplodedNode *Pred, 1339 ExplodedNodeSet &Dst){ 1340 1341 const Expr *Base = A->getBase()->IgnoreParens(); 1342 const Expr *Idx = A->getIdx()->IgnoreParens(); 1343 1344 1345 ExplodedNodeSet checkerPreStmt; 1346 getCheckerManager().runCheckersForPreStmt(checkerPreStmt, Pred, A, *this); 1347 1348 StmtNodeBuilder Bldr(checkerPreStmt, Dst, *currentBuilderContext); 1349 1350 for (ExplodedNodeSet::iterator it = checkerPreStmt.begin(), 1351 ei = checkerPreStmt.end(); it != ei; ++it) { 1352 const LocationContext *LCtx = (*it)->getLocationContext(); 1353 ProgramStateRef state = (*it)->getState(); 1354 SVal V = state->getLValue(A->getType(), 1355 state->getSVal(Idx, LCtx), 1356 state->getSVal(Base, LCtx)); 1357 assert(A->isLValue()); 1358 Bldr.generateNode(A, *it, state->BindExpr(A, LCtx, V), 1359 false, 0, ProgramPoint::PostLValueKind); 1360 } 1361} 1362 1363/// VisitMemberExpr - Transfer function for member expressions. 1364void ExprEngine::VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred, 1365 ExplodedNodeSet &TopDst) { 1366 1367 StmtNodeBuilder Bldr(Pred, TopDst, *currentBuilderContext); 1368 ExplodedNodeSet Dst; 1369 Decl *member = M->getMemberDecl(); 1370 if (VarDecl *VD = dyn_cast<VarDecl>(member)) { 1371 assert(M->isLValue()); 1372 Bldr.takeNodes(Pred); 1373 VisitCommonDeclRefExpr(M, VD, Pred, Dst); 1374 Bldr.addNodes(Dst); 1375 return; 1376 } 1377 1378 FieldDecl *field = dyn_cast<FieldDecl>(member); 1379 if (!field) // FIXME: skipping member expressions for non-fields 1380 return; 1381 1382 Expr *baseExpr = M->getBase()->IgnoreParens(); 1383 ProgramStateRef state = Pred->getState(); 1384 const LocationContext *LCtx = Pred->getLocationContext(); 1385 SVal baseExprVal = state->getSVal(baseExpr, Pred->getLocationContext()); 1386 if (isa<nonloc::LazyCompoundVal>(baseExprVal) || 1387 isa<nonloc::CompoundVal>(baseExprVal) || 1388 // FIXME: This can originate by conjuring a symbol for an unknown 1389 // temporary struct object, see test/Analysis/fields.c: 1390 // (p = getit()).x 1391 isa<nonloc::SymbolVal>(baseExprVal)) { 1392 Bldr.generateNode(M, Pred, state->BindExpr(M, LCtx, UnknownVal())); 1393 return; 1394 } 1395 1396 // FIXME: Should we insert some assumption logic in here to determine 1397 // if "Base" is a valid piece of memory? Before we put this assumption 1398 // later when using FieldOffset lvals (which we no longer have). 1399 1400 // For all other cases, compute an lvalue. 1401 SVal L = state->getLValue(field, baseExprVal); 1402 if (M->isLValue()) 1403 Bldr.generateNode(M, Pred, state->BindExpr(M, LCtx, L), false, 0, 1404 ProgramPoint::PostLValueKind); 1405 else { 1406 Bldr.takeNodes(Pred); 1407 evalLoad(Dst, M, Pred, state, L); 1408 Bldr.addNodes(Dst); 1409 } 1410} 1411 1412/// evalBind - Handle the semantics of binding a value to a specific location. 1413/// This method is used by evalStore and (soon) VisitDeclStmt, and others. 1414void ExprEngine::evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE, 1415 ExplodedNode *Pred, 1416 SVal location, SVal Val, bool atDeclInit, 1417 ProgramPoint::Kind PointKind) { 1418 1419 // Do a previsit of the bind. 1420 ExplodedNodeSet CheckedSet; 1421 getCheckerManager().runCheckersForBind(CheckedSet, Pred, location, Val, 1422 StoreE, *this, PointKind); 1423 1424 // TODO:AZ Remove TmpDst after NB refactoring is done. 1425 ExplodedNodeSet TmpDst; 1426 StmtNodeBuilder Bldr(CheckedSet, TmpDst, *currentBuilderContext); 1427 1428 for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end(); 1429 I!=E; ++I) { 1430 ProgramStateRef state = (*I)->getState(); 1431 1432 if (atDeclInit) { 1433 const VarRegion *VR = 1434 cast<VarRegion>(cast<loc::MemRegionVal>(location).getRegion()); 1435 1436 state = state->bindDecl(VR, Val); 1437 } else { 1438 state = state->bindLoc(location, Val); 1439 } 1440 1441 Bldr.generateNode(StoreE, *I, state, false, 0, PointKind); 1442 } 1443 1444 Dst.insert(TmpDst); 1445} 1446 1447/// evalStore - Handle the semantics of a store via an assignment. 1448/// @param Dst The node set to store generated state nodes 1449/// @param AssignE The assignment expression if the store happens in an 1450/// assignment. 1451/// @param LocatioinE The location expression that is stored to. 1452/// @param state The current simulation state 1453/// @param location The location to store the value 1454/// @param Val The value to be stored 1455void ExprEngine::evalStore(ExplodedNodeSet &Dst, const Expr *AssignE, 1456 const Expr *LocationE, 1457 ExplodedNode *Pred, 1458 ProgramStateRef state, SVal location, SVal Val, 1459 const ProgramPointTag *tag) { 1460 // Proceed with the store. We use AssignE as the anchor for the PostStore 1461 // ProgramPoint if it is non-NULL, and LocationE otherwise. 1462 const Expr *StoreE = AssignE ? AssignE : LocationE; 1463 1464 if (isa<loc::ObjCPropRef>(location)) { 1465 assert(false); 1466 } 1467 1468 // Evaluate the location (checks for bad dereferences). 1469 ExplodedNodeSet Tmp; 1470 evalLocation(Tmp, LocationE, Pred, state, location, tag, false); 1471 1472 if (Tmp.empty()) 1473 return; 1474 1475 if (location.isUndef()) 1476 return; 1477 1478 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) 1479 evalBind(Dst, StoreE, *NI, location, Val, false, 1480 ProgramPoint::PostStoreKind); 1481} 1482 1483void ExprEngine::evalLoad(ExplodedNodeSet &Dst, const Expr *Ex, 1484 ExplodedNode *Pred, 1485 ProgramStateRef state, SVal location, 1486 const ProgramPointTag *tag, QualType LoadTy) { 1487 assert(!isa<NonLoc>(location) && "location cannot be a NonLoc."); 1488 1489 if (isa<loc::ObjCPropRef>(location)) { 1490 assert(false); 1491 } 1492 1493 // Are we loading from a region? This actually results in two loads; one 1494 // to fetch the address of the referenced value and one to fetch the 1495 // referenced value. 1496 if (const TypedValueRegion *TR = 1497 dyn_cast_or_null<TypedValueRegion>(location.getAsRegion())) { 1498 1499 QualType ValTy = TR->getValueType(); 1500 if (const ReferenceType *RT = ValTy->getAs<ReferenceType>()) { 1501 static SimpleProgramPointTag 1502 loadReferenceTag("ExprEngine : Load Reference"); 1503 ExplodedNodeSet Tmp; 1504 evalLoadCommon(Tmp, Ex, Pred, state, location, &loadReferenceTag, 1505 getContext().getPointerType(RT->getPointeeType())); 1506 1507 // Perform the load from the referenced value. 1508 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end() ; I!=E; ++I) { 1509 state = (*I)->getState(); 1510 location = state->getSVal(Ex, (*I)->getLocationContext()); 1511 evalLoadCommon(Dst, Ex, *I, state, location, tag, LoadTy); 1512 } 1513 return; 1514 } 1515 } 1516 1517 evalLoadCommon(Dst, Ex, Pred, state, location, tag, LoadTy); 1518} 1519 1520void ExprEngine::evalLoadCommon(ExplodedNodeSet &Dst, const Expr *Ex, 1521 ExplodedNode *Pred, 1522 ProgramStateRef state, SVal location, 1523 const ProgramPointTag *tag, QualType LoadTy) { 1524 1525 // Evaluate the location (checks for bad dereferences). 1526 ExplodedNodeSet Tmp; 1527 evalLocation(Tmp, Ex, Pred, state, location, tag, true); 1528 if (Tmp.empty()) 1529 return; 1530 1531 StmtNodeBuilder Bldr(Tmp, Dst, *currentBuilderContext); 1532 if (location.isUndef()) 1533 return; 1534 1535 // Proceed with the load. 1536 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) { 1537 state = (*NI)->getState(); 1538 const LocationContext *LCtx = (*NI)->getLocationContext(); 1539 1540 if (location.isUnknown()) { 1541 // This is important. We must nuke the old binding. 1542 Bldr.generateNode(Ex, *NI, state->BindExpr(Ex, LCtx, UnknownVal()), 1543 false, tag, ProgramPoint::PostLoadKind); 1544 } 1545 else { 1546 if (LoadTy.isNull()) 1547 LoadTy = Ex->getType(); 1548 SVal V = state->getSVal(cast<Loc>(location), LoadTy); 1549 Bldr.generateNode(Ex, *NI, state->bindExprAndLocation(Ex, LCtx, 1550 location, V), 1551 false, tag, ProgramPoint::PostLoadKind); 1552 } 1553 } 1554} 1555 1556void ExprEngine::evalLocation(ExplodedNodeSet &Dst, const Stmt *S, 1557 ExplodedNode *Pred, 1558 ProgramStateRef state, SVal location, 1559 const ProgramPointTag *tag, bool isLoad) { 1560 StmtNodeBuilder BldrTop(Pred, Dst, *currentBuilderContext); 1561 // Early checks for performance reason. 1562 if (location.isUnknown()) { 1563 return; 1564 } 1565 1566 ExplodedNodeSet Src; 1567 BldrTop.takeNodes(Pred); 1568 StmtNodeBuilder Bldr(Pred, Src, *currentBuilderContext); 1569 if (Pred->getState() != state) { 1570 // Associate this new state with an ExplodedNode. 1571 // FIXME: If I pass null tag, the graph is incorrect, e.g for 1572 // int *p; 1573 // p = 0; 1574 // *p = 0xDEADBEEF; 1575 // "p = 0" is not noted as "Null pointer value stored to 'p'" but 1576 // instead "int *p" is noted as 1577 // "Variable 'p' initialized to a null pointer value" 1578 1579 // FIXME: why is 'tag' not used instead of etag? 1580 static SimpleProgramPointTag etag("ExprEngine: Location"); 1581 1582 Bldr.generateNode(S, Pred, state, false, &etag); 1583 } 1584 ExplodedNodeSet Tmp; 1585 getCheckerManager().runCheckersForLocation(Tmp, Src, location, isLoad, S, 1586 *this); 1587 BldrTop.addNodes(Tmp); 1588} 1589 1590std::pair<const ProgramPointTag *, const ProgramPointTag*> 1591ExprEngine::getEagerlyAssumeTags() { 1592 static SimpleProgramPointTag 1593 EagerlyAssumeTrue("ExprEngine : Eagerly Assume True"), 1594 EagerlyAssumeFalse("ExprEngine : Eagerly Assume False"); 1595 return std::make_pair(&EagerlyAssumeTrue, &EagerlyAssumeFalse); 1596} 1597 1598void ExprEngine::evalEagerlyAssume(ExplodedNodeSet &Dst, ExplodedNodeSet &Src, 1599 const Expr *Ex) { 1600 StmtNodeBuilder Bldr(Src, Dst, *currentBuilderContext); 1601 1602 for (ExplodedNodeSet::iterator I=Src.begin(), E=Src.end(); I!=E; ++I) { 1603 ExplodedNode *Pred = *I; 1604 // Test if the previous node was as the same expression. This can happen 1605 // when the expression fails to evaluate to anything meaningful and 1606 // (as an optimization) we don't generate a node. 1607 ProgramPoint P = Pred->getLocation(); 1608 if (!isa<PostStmt>(P) || cast<PostStmt>(P).getStmt() != Ex) { 1609 continue; 1610 } 1611 1612 ProgramStateRef state = Pred->getState(); 1613 SVal V = state->getSVal(Ex, Pred->getLocationContext()); 1614 nonloc::SymbolVal *SEV = dyn_cast<nonloc::SymbolVal>(&V); 1615 if (SEV && SEV->isExpression()) { 1616 const std::pair<const ProgramPointTag *, const ProgramPointTag*> &tags = 1617 getEagerlyAssumeTags(); 1618 1619 // First assume that the condition is true. 1620 if (ProgramStateRef StateTrue = state->assume(*SEV, true)) { 1621 SVal Val = svalBuilder.makeIntVal(1U, Ex->getType()); 1622 StateTrue = StateTrue->BindExpr(Ex, Pred->getLocationContext(), Val); 1623 Bldr.generateNode(Ex, Pred, StateTrue, false, tags.first); 1624 } 1625 1626 // Next, assume that the condition is false. 1627 if (ProgramStateRef StateFalse = state->assume(*SEV, false)) { 1628 SVal Val = svalBuilder.makeIntVal(0U, Ex->getType()); 1629 StateFalse = StateFalse->BindExpr(Ex, Pred->getLocationContext(), Val); 1630 Bldr.generateNode(Ex, Pred, StateFalse, false, tags.second); 1631 } 1632 } 1633 } 1634} 1635 1636void ExprEngine::VisitAsmStmt(const AsmStmt *A, ExplodedNode *Pred, 1637 ExplodedNodeSet &Dst) { 1638 VisitAsmStmtHelperOutputs(A, A->begin_outputs(), A->end_outputs(), Pred, Dst); 1639} 1640 1641void ExprEngine::VisitAsmStmtHelperOutputs(const AsmStmt *A, 1642 AsmStmt::const_outputs_iterator I, 1643 AsmStmt::const_outputs_iterator E, 1644 ExplodedNode *Pred, ExplodedNodeSet &Dst) { 1645 if (I == E) { 1646 VisitAsmStmtHelperInputs(A, A->begin_inputs(), A->end_inputs(), Pred, Dst); 1647 return; 1648 } 1649 1650 ExplodedNodeSet Tmp; 1651 Visit(*I, Pred, Tmp); 1652 ++I; 1653 1654 for (ExplodedNodeSet::iterator NI = Tmp.begin(), NE = Tmp.end();NI != NE;++NI) 1655 VisitAsmStmtHelperOutputs(A, I, E, *NI, Dst); 1656} 1657 1658void ExprEngine::VisitAsmStmtHelperInputs(const AsmStmt *A, 1659 AsmStmt::const_inputs_iterator I, 1660 AsmStmt::const_inputs_iterator E, 1661 ExplodedNode *Pred, 1662 ExplodedNodeSet &Dst) { 1663 if (I == E) { 1664 StmtNodeBuilder Bldr(Pred, Dst, *currentBuilderContext); 1665 // We have processed both the inputs and the outputs. All of the outputs 1666 // should evaluate to Locs. Nuke all of their values. 1667 1668 // FIXME: Some day in the future it would be nice to allow a "plug-in" 1669 // which interprets the inline asm and stores proper results in the 1670 // outputs. 1671 1672 ProgramStateRef state = Pred->getState(); 1673 1674 for (AsmStmt::const_outputs_iterator OI = A->begin_outputs(), 1675 OE = A->end_outputs(); OI != OE; ++OI) { 1676 1677 SVal X = state->getSVal(*OI, Pred->getLocationContext()); 1678 assert (!isa<NonLoc>(X)); // Should be an Lval, or unknown, undef. 1679 1680 if (isa<Loc>(X)) 1681 state = state->bindLoc(cast<Loc>(X), UnknownVal()); 1682 } 1683 1684 Bldr.generateNode(A, Pred, state); 1685 return; 1686 } 1687 1688 ExplodedNodeSet Tmp; 1689 Visit(*I, Pred, Tmp); 1690 1691 ++I; 1692 1693 for (ExplodedNodeSet::iterator NI = Tmp.begin(), NE = Tmp.end(); NI!=NE; ++NI) 1694 VisitAsmStmtHelperInputs(A, I, E, *NI, Dst); 1695} 1696 1697 1698//===----------------------------------------------------------------------===// 1699// Visualization. 1700//===----------------------------------------------------------------------===// 1701 1702#ifndef NDEBUG 1703static ExprEngine* GraphPrintCheckerState; 1704static SourceManager* GraphPrintSourceManager; 1705 1706namespace llvm { 1707template<> 1708struct DOTGraphTraits<ExplodedNode*> : 1709 public DefaultDOTGraphTraits { 1710 1711 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} 1712 1713 // FIXME: Since we do not cache error nodes in ExprEngine now, this does not 1714 // work. 1715 static std::string getNodeAttributes(const ExplodedNode *N, void*) { 1716 1717#if 0 1718 // FIXME: Replace with a general scheme to tell if the node is 1719 // an error node. 1720 if (GraphPrintCheckerState->isImplicitNullDeref(N) || 1721 GraphPrintCheckerState->isExplicitNullDeref(N) || 1722 GraphPrintCheckerState->isUndefDeref(N) || 1723 GraphPrintCheckerState->isUndefStore(N) || 1724 GraphPrintCheckerState->isUndefControlFlow(N) || 1725 GraphPrintCheckerState->isUndefResult(N) || 1726 GraphPrintCheckerState->isBadCall(N) || 1727 GraphPrintCheckerState->isUndefArg(N)) 1728 return "color=\"red\",style=\"filled\""; 1729 1730 if (GraphPrintCheckerState->isNoReturnCall(N)) 1731 return "color=\"blue\",style=\"filled\""; 1732#endif 1733 return ""; 1734 } 1735 1736 static std::string getNodeLabel(const ExplodedNode *N, void*){ 1737 1738 std::string sbuf; 1739 llvm::raw_string_ostream Out(sbuf); 1740 1741 // Program Location. 1742 ProgramPoint Loc = N->getLocation(); 1743 1744 switch (Loc.getKind()) { 1745 case ProgramPoint::BlockEntranceKind: 1746 Out << "Block Entrance: B" 1747 << cast<BlockEntrance>(Loc).getBlock()->getBlockID(); 1748 break; 1749 1750 case ProgramPoint::BlockExitKind: 1751 assert (false); 1752 break; 1753 1754 case ProgramPoint::CallEnterKind: 1755 Out << "CallEnter"; 1756 break; 1757 1758 case ProgramPoint::CallExitKind: 1759 Out << "CallExit"; 1760 break; 1761 1762 default: { 1763 if (StmtPoint *L = dyn_cast<StmtPoint>(&Loc)) { 1764 const Stmt *S = L->getStmt(); 1765 SourceLocation SLoc = S->getLocStart(); 1766 1767 Out << S->getStmtClassName() << ' ' << (void*) S << ' '; 1768 LangOptions LO; // FIXME. 1769 S->printPretty(Out, 0, PrintingPolicy(LO)); 1770 1771 if (SLoc.isFileID()) { 1772 Out << "\\lline=" 1773 << GraphPrintSourceManager->getExpansionLineNumber(SLoc) 1774 << " col=" 1775 << GraphPrintSourceManager->getExpansionColumnNumber(SLoc) 1776 << "\\l"; 1777 } 1778 1779 if (isa<PreStmt>(Loc)) 1780 Out << "\\lPreStmt\\l;"; 1781 else if (isa<PostLoad>(Loc)) 1782 Out << "\\lPostLoad\\l;"; 1783 else if (isa<PostStore>(Loc)) 1784 Out << "\\lPostStore\\l"; 1785 else if (isa<PostLValue>(Loc)) 1786 Out << "\\lPostLValue\\l"; 1787 1788#if 0 1789 // FIXME: Replace with a general scheme to determine 1790 // the name of the check. 1791 if (GraphPrintCheckerState->isImplicitNullDeref(N)) 1792 Out << "\\|Implicit-Null Dereference.\\l"; 1793 else if (GraphPrintCheckerState->isExplicitNullDeref(N)) 1794 Out << "\\|Explicit-Null Dereference.\\l"; 1795 else if (GraphPrintCheckerState->isUndefDeref(N)) 1796 Out << "\\|Dereference of undefialied value.\\l"; 1797 else if (GraphPrintCheckerState->isUndefStore(N)) 1798 Out << "\\|Store to Undefined Loc."; 1799 else if (GraphPrintCheckerState->isUndefResult(N)) 1800 Out << "\\|Result of operation is undefined."; 1801 else if (GraphPrintCheckerState->isNoReturnCall(N)) 1802 Out << "\\|Call to function marked \"noreturn\"."; 1803 else if (GraphPrintCheckerState->isBadCall(N)) 1804 Out << "\\|Call to NULL/Undefined."; 1805 else if (GraphPrintCheckerState->isUndefArg(N)) 1806 Out << "\\|Argument in call is undefined"; 1807#endif 1808 1809 break; 1810 } 1811 1812 const BlockEdge &E = cast<BlockEdge>(Loc); 1813 Out << "Edge: (B" << E.getSrc()->getBlockID() << ", B" 1814 << E.getDst()->getBlockID() << ')'; 1815 1816 if (const Stmt *T = E.getSrc()->getTerminator()) { 1817 1818 SourceLocation SLoc = T->getLocStart(); 1819 1820 Out << "\\|Terminator: "; 1821 LangOptions LO; // FIXME. 1822 E.getSrc()->printTerminator(Out, LO); 1823 1824 if (SLoc.isFileID()) { 1825 Out << "\\lline=" 1826 << GraphPrintSourceManager->getExpansionLineNumber(SLoc) 1827 << " col=" 1828 << GraphPrintSourceManager->getExpansionColumnNumber(SLoc); 1829 } 1830 1831 if (isa<SwitchStmt>(T)) { 1832 const Stmt *Label = E.getDst()->getLabel(); 1833 1834 if (Label) { 1835 if (const CaseStmt *C = dyn_cast<CaseStmt>(Label)) { 1836 Out << "\\lcase "; 1837 LangOptions LO; // FIXME. 1838 C->getLHS()->printPretty(Out, 0, PrintingPolicy(LO)); 1839 1840 if (const Stmt *RHS = C->getRHS()) { 1841 Out << " .. "; 1842 RHS->printPretty(Out, 0, PrintingPolicy(LO)); 1843 } 1844 1845 Out << ":"; 1846 } 1847 else { 1848 assert (isa<DefaultStmt>(Label)); 1849 Out << "\\ldefault:"; 1850 } 1851 } 1852 else 1853 Out << "\\l(implicit) default:"; 1854 } 1855 else if (isa<IndirectGotoStmt>(T)) { 1856 // FIXME 1857 } 1858 else { 1859 Out << "\\lCondition: "; 1860 if (*E.getSrc()->succ_begin() == E.getDst()) 1861 Out << "true"; 1862 else 1863 Out << "false"; 1864 } 1865 1866 Out << "\\l"; 1867 } 1868 1869#if 0 1870 // FIXME: Replace with a general scheme to determine 1871 // the name of the check. 1872 if (GraphPrintCheckerState->isUndefControlFlow(N)) { 1873 Out << "\\|Control-flow based on\\lUndefined value.\\l"; 1874 } 1875#endif 1876 } 1877 } 1878 1879 ProgramStateRef state = N->getState(); 1880 Out << "\\|StateID: " << (void*) state.getPtr() 1881 << " NodeID: " << (void*) N << "\\|"; 1882 state->printDOT(Out); 1883 1884 Out << "\\l"; 1885 1886 if (const ProgramPointTag *tag = Loc.getTag()) { 1887 Out << "\\|Tag: " << tag->getTagDescription(); 1888 Out << "\\l"; 1889 } 1890 return Out.str(); 1891 } 1892}; 1893} // end llvm namespace 1894#endif 1895 1896#ifndef NDEBUG 1897template <typename ITERATOR> 1898ExplodedNode *GetGraphNode(ITERATOR I) { return *I; } 1899 1900template <> ExplodedNode* 1901GetGraphNode<llvm::DenseMap<ExplodedNode*, Expr*>::iterator> 1902 (llvm::DenseMap<ExplodedNode*, Expr*>::iterator I) { 1903 return I->first; 1904} 1905#endif 1906 1907void ExprEngine::ViewGraph(bool trim) { 1908#ifndef NDEBUG 1909 if (trim) { 1910 std::vector<ExplodedNode*> Src; 1911 1912 // Flush any outstanding reports to make sure we cover all the nodes. 1913 // This does not cause them to get displayed. 1914 for (BugReporter::iterator I=BR.begin(), E=BR.end(); I!=E; ++I) 1915 const_cast<BugType*>(*I)->FlushReports(BR); 1916 1917 // Iterate through the reports and get their nodes. 1918 for (BugReporter::EQClasses_iterator 1919 EI = BR.EQClasses_begin(), EE = BR.EQClasses_end(); EI != EE; ++EI) { 1920 BugReportEquivClass& EQ = *EI; 1921 const BugReport &R = **EQ.begin(); 1922 ExplodedNode *N = const_cast<ExplodedNode*>(R.getErrorNode()); 1923 if (N) Src.push_back(N); 1924 } 1925 1926 ViewGraph(&Src[0], &Src[0]+Src.size()); 1927 } 1928 else { 1929 GraphPrintCheckerState = this; 1930 GraphPrintSourceManager = &getContext().getSourceManager(); 1931 1932 llvm::ViewGraph(*G.roots_begin(), "ExprEngine"); 1933 1934 GraphPrintCheckerState = NULL; 1935 GraphPrintSourceManager = NULL; 1936 } 1937#endif 1938} 1939 1940void ExprEngine::ViewGraph(ExplodedNode** Beg, ExplodedNode** End) { 1941#ifndef NDEBUG 1942 GraphPrintCheckerState = this; 1943 GraphPrintSourceManager = &getContext().getSourceManager(); 1944 1945 std::auto_ptr<ExplodedGraph> TrimmedG(G.Trim(Beg, End).first); 1946 1947 if (!TrimmedG.get()) 1948 llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n"; 1949 else 1950 llvm::ViewGraph(*TrimmedG->roots_begin(), "TrimmedExprEngine"); 1951 1952 GraphPrintCheckerState = NULL; 1953 GraphPrintSourceManager = NULL; 1954#endif 1955} 1956