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