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