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