contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp

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