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