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