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