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