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