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