lib/StaticAnalyzer/Core/ExprEngine.cpp

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