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