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