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