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