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