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