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