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