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