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