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