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