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