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