1 //=-- ExprEngine.cpp - Path-Sensitive Expression-Level Dataflow ---*- C++ -*-=
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
14 //===----------------------------------------------------------------------===//
16 #define DEBUG_TYPE "ExprEngine"
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"
35 #include "llvm/Support/GraphWriter.h"
38 using namespace clang;
42 STATISTIC(NumRemoveDeadBindings,
43 "The # of times RemoveDeadBindings is called");
44 STATISTIC(NumMaxBlockCountReached,
45 "The # of aborted paths due to reaching the maximum block count in "
46 "a top level function");
47 STATISTIC(NumMaxBlockCountReachedInInlined,
48 "The # of aborted paths due to reaching the maximum block count in "
49 "an inlined function");
50 STATISTIC(NumTimesRetriedWithoutInlining,
51 "The # of times we re-evaluated a call without inlining");
53 //===----------------------------------------------------------------------===//
54 // Engine construction and deletion.
55 //===----------------------------------------------------------------------===//
57 ExprEngine::ExprEngine(AnalysisManager &mgr, bool gcEnabled,
58 SetOfConstDecls *VisitedCalleesIn,
59 FunctionSummariesTy *FS)
61 AnalysisDeclContexts(mgr.getAnalysisDeclContextManager()),
64 StateMgr(getContext(), mgr.getStoreManagerCreator(),
65 mgr.getConstraintManagerCreator(), G.getAllocator(),
67 SymMgr(StateMgr.getSymbolManager()),
68 svalBuilder(StateMgr.getSValBuilder()),
70 currStmt(NULL), currStmtIdx(0), currBldrCtx(0),
71 ObjCNoRet(mgr.getASTContext()),
72 ObjCGCEnabled(gcEnabled), BR(mgr, *this),
73 VisitedCallees(VisitedCalleesIn)
75 unsigned TrimInterval = mgr.options.getGraphTrimInterval();
76 if (TrimInterval != 0) {
77 // Enable eager node reclaimation when constructing the ExplodedGraph.
78 G.enableNodeReclamation(TrimInterval);
82 ExprEngine::~ExprEngine() {
86 //===----------------------------------------------------------------------===//
88 //===----------------------------------------------------------------------===//
90 ProgramStateRef ExprEngine::getInitialState(const LocationContext *InitLoc) {
91 ProgramStateRef state = StateMgr.getInitialState(InitLoc);
92 const Decl *D = InitLoc->getDecl();
95 // FIXME: It would be nice if we had a more general mechanism to add
96 // such preconditions. Some day.
99 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
100 // Precondition: the first argument of 'main' is an integer guaranteed
102 const IdentifierInfo *II = FD->getIdentifier();
103 if (!II || !(II->getName() == "main" && FD->getNumParams() > 0))
106 const ParmVarDecl *PD = FD->getParamDecl(0);
107 QualType T = PD->getType();
108 if (!T->isIntegerType())
111 const MemRegion *R = state->getRegion(PD, InitLoc);
115 SVal V = state->getSVal(loc::MemRegionVal(R));
116 SVal Constraint_untested = evalBinOp(state, BO_GT, V,
117 svalBuilder.makeZeroVal(T),
120 DefinedOrUnknownSVal *Constraint =
121 dyn_cast<DefinedOrUnknownSVal>(&Constraint_untested);
126 if (ProgramStateRef newState = state->assume(*Constraint, true))
133 if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) {
134 // Precondition: 'self' is always non-null upon entry to an Objective-C
136 const ImplicitParamDecl *SelfD = MD->getSelfDecl();
137 const MemRegion *R = state->getRegion(SelfD, InitLoc);
138 SVal V = state->getSVal(loc::MemRegionVal(R));
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");
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");
167 /// If the value of the given expression is a NonLoc, copy it into a new
168 /// temporary region, and replace the value of the expression with that.
169 static ProgramStateRef createTemporaryRegionIfNeeded(ProgramStateRef State,
170 const LocationContext *LC,
172 SVal V = State->getSVal(E, LC);
174 if (isa<NonLoc>(V)) {
175 MemRegionManager &MRMgr = State->getStateManager().getRegionManager();
176 const MemRegion *R = MRMgr.getCXXTempObjectRegion(E, LC);
177 State = State->bindLoc(loc::MemRegionVal(R), V);
178 State = State->BindExpr(E, LC, loc::MemRegionVal(R));
184 //===----------------------------------------------------------------------===//
185 // Top-level transfer function logic (Dispatcher).
186 //===----------------------------------------------------------------------===//
188 /// evalAssume - Called by ConstraintManager. Used to call checker-specific
189 /// logic for handling assumptions on symbolic values.
190 ProgramStateRef ExprEngine::processAssume(ProgramStateRef state,
191 SVal cond, bool assumption) {
192 return getCheckerManager().runCheckersForEvalAssume(state, cond, assumption);
195 bool ExprEngine::wantsRegionChangeUpdate(ProgramStateRef state) {
196 return getCheckerManager().wantsRegionChangeUpdate(state);
200 ExprEngine::processRegionChanges(ProgramStateRef state,
201 const StoreManager::InvalidatedSymbols *invalidated,
202 ArrayRef<const MemRegion *> Explicits,
203 ArrayRef<const MemRegion *> Regions,
204 const CallEvent *Call) {
205 return getCheckerManager().runCheckersForRegionChanges(state, invalidated,
206 Explicits, Regions, Call);
209 void ExprEngine::printState(raw_ostream &Out, ProgramStateRef State,
210 const char *NL, const char *Sep) {
211 getCheckerManager().runCheckersForPrintState(Out, State, NL, Sep);
214 void ExprEngine::processEndWorklist(bool hasWorkRemaining) {
215 getCheckerManager().runCheckersForEndAnalysis(G, BR, *this);
218 void ExprEngine::processCFGElement(const CFGElement E, ExplodedNode *Pred,
219 unsigned StmtIdx, NodeBuilderContext *Ctx) {
220 currStmtIdx = StmtIdx;
223 switch (E.getKind()) {
224 case CFGElement::Invalid:
225 llvm_unreachable("Unexpected CFGElement kind.");
226 case CFGElement::Statement:
227 ProcessStmt(const_cast<Stmt*>(E.getAs<CFGStmt>()->getStmt()), Pred);
229 case CFGElement::Initializer:
230 ProcessInitializer(E.getAs<CFGInitializer>()->getInitializer(), Pred);
232 case CFGElement::AutomaticObjectDtor:
233 case CFGElement::BaseDtor:
234 case CFGElement::MemberDtor:
235 case CFGElement::TemporaryDtor:
236 ProcessImplicitDtor(*E.getAs<CFGImplicitDtor>(), Pred);
242 static bool shouldRemoveDeadBindings(AnalysisManager &AMgr,
244 const ExplodedNode *Pred,
245 const LocationContext *LC) {
247 // Are we never purging state values?
248 if (AMgr.options.AnalysisPurgeOpt == PurgeNone)
251 // Is this the beginning of a basic block?
252 if (isa<BlockEntrance>(Pred->getLocation()))
255 // Is this on a non-expression?
256 if (!isa<Expr>(S.getStmt()))
259 // Run before processing a call.
260 if (CallEvent::isCallStmt(S.getStmt()))
263 // Is this an expression that is consumed by another expression? If so,
264 // postpone cleaning out the state.
265 ParentMap &PM = LC->getAnalysisDeclContext()->getParentMap();
266 return !PM.isConsumedExpr(cast<Expr>(S.getStmt()));
269 void ExprEngine::removeDead(ExplodedNode *Pred, ExplodedNodeSet &Out,
270 const Stmt *ReferenceStmt,
271 const StackFrameContext *LC,
272 const Stmt *DiagnosticStmt,
273 ProgramPoint::Kind K) {
274 assert((K == ProgramPoint::PreStmtPurgeDeadSymbolsKind ||
276 && "PostStmt is not generally supported by the SymbolReaper yet");
277 NumRemoveDeadBindings++;
278 CleanedState = Pred->getState();
279 SymbolReaper SymReaper(LC, ReferenceStmt, SymMgr, getStoreManager());
281 getCheckerManager().runCheckersForLiveSymbols(CleanedState, SymReaper);
283 // Create a state in which dead bindings are removed from the environment
284 // and the store. TODO: The function should just return new env and store,
286 const StackFrameContext *SFC = LC->getCurrentStackFrame();
287 CleanedState = StateMgr.removeDeadBindings(CleanedState, SFC, SymReaper);
289 // Process any special transfer function for dead symbols.
290 // A tag to track convenience transitions, which can be removed at cleanup.
291 static SimpleProgramPointTag cleanupTag("ExprEngine : Clean Node");
292 if (!SymReaper.hasDeadSymbols()) {
293 // Generate a CleanedNode that has the environment and store cleaned
294 // up. Since no symbols are dead, we can optimize and not clean out
295 // the constraint manager.
296 StmtNodeBuilder Bldr(Pred, Out, *currBldrCtx);
297 Bldr.generateNode(DiagnosticStmt, Pred, CleanedState, &cleanupTag, K);
300 // Call checkers with the non-cleaned state so that they could query the
301 // values of the soon to be dead symbols.
302 ExplodedNodeSet CheckedSet;
303 getCheckerManager().runCheckersForDeadSymbols(CheckedSet, Pred, SymReaper,
304 DiagnosticStmt, *this, K);
306 // For each node in CheckedSet, generate CleanedNodes that have the
307 // environment, the store, and the constraints cleaned up but have the
308 // user-supplied states as the predecessors.
309 StmtNodeBuilder Bldr(CheckedSet, Out, *currBldrCtx);
310 for (ExplodedNodeSet::const_iterator
311 I = CheckedSet.begin(), E = CheckedSet.end(); I != E; ++I) {
312 ProgramStateRef CheckerState = (*I)->getState();
314 // The constraint manager has not been cleaned up yet, so clean up now.
315 CheckerState = getConstraintManager().removeDeadBindings(CheckerState,
318 assert(StateMgr.haveEqualEnvironments(CheckerState, Pred->getState()) &&
319 "Checkers are not allowed to modify the Environment as a part of "
320 "checkDeadSymbols processing.");
321 assert(StateMgr.haveEqualStores(CheckerState, Pred->getState()) &&
322 "Checkers are not allowed to modify the Store as a part of "
323 "checkDeadSymbols processing.");
325 // Create a state based on CleanedState with CheckerState GDM and
326 // generate a transition to that state.
327 ProgramStateRef CleanedCheckerSt =
328 StateMgr.getPersistentStateWithGDM(CleanedState, CheckerState);
329 Bldr.generateNode(DiagnosticStmt, *I, CleanedCheckerSt, &cleanupTag, K);
334 void ExprEngine::ProcessStmt(const CFGStmt S,
335 ExplodedNode *Pred) {
336 // Reclaim any unnecessary nodes in the ExplodedGraph.
337 G.reclaimRecentlyAllocatedNodes();
339 currStmt = S.getStmt();
340 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
341 currStmt->getLocStart(),
342 "Error evaluating statement");
344 // Remove dead bindings and symbols.
346 ExplodedNodeSet CleanedStates;
347 if (shouldRemoveDeadBindings(AMgr, S, Pred, EntryNode->getLocationContext())){
348 removeDead(EntryNode, CleanedStates, currStmt,
349 Pred->getStackFrame(), currStmt);
351 CleanedStates.Add(EntryNode);
353 // Visit the statement.
355 for (ExplodedNodeSet::iterator I = CleanedStates.begin(),
356 E = CleanedStates.end(); I != E; ++I) {
357 ExplodedNodeSet DstI;
358 // Visit the statement.
359 Visit(currStmt, *I, DstI);
363 // Enqueue the new nodes onto the work list.
364 Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
366 // NULL out these variables to cleanup.
372 void ExprEngine::ProcessInitializer(const CFGInitializer Init,
373 ExplodedNode *Pred) {
374 const CXXCtorInitializer *BMI = Init.getInitializer();
376 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
377 BMI->getSourceLocation(),
378 "Error evaluating initializer");
380 // We don't set EntryNode and currStmt. And we don't clean up state.
381 const StackFrameContext *stackFrame =
382 cast<StackFrameContext>(Pred->getLocationContext());
383 const CXXConstructorDecl *decl =
384 cast<CXXConstructorDecl>(stackFrame->getDecl());
386 ProgramStateRef State = Pred->getState();
387 SVal thisVal = State->getSVal(svalBuilder.getCXXThis(decl, stackFrame));
389 PostInitializer PP(BMI, stackFrame);
390 ExplodedNodeSet Tmp(Pred);
392 // Evaluate the initializer, if necessary
393 if (BMI->isAnyMemberInitializer()) {
394 // Constructors build the object directly in the field,
395 // but non-objects must be copied in from the initializer.
396 const Expr *Init = BMI->getInit();
397 if (!isa<CXXConstructExpr>(Init)) {
399 if (BMI->isIndirectMemberInitializer())
400 FieldLoc = State->getLValue(BMI->getIndirectMember(), thisVal);
402 FieldLoc = State->getLValue(BMI->getMember(), thisVal);
404 SVal InitVal = State->getSVal(BMI->getInit(), stackFrame);
407 evalBind(Tmp, Init, Pred, FieldLoc, InitVal, /*isInit=*/true, &PP);
410 assert(BMI->isBaseInitializer() || BMI->isDelegatingInitializer());
411 // We already did all the work when visiting the CXXConstructExpr.
414 // Construct PostInitializer nodes whether the state changed or not,
415 // so that the diagnostics don't get confused.
417 NodeBuilder Bldr(Tmp, Dst, *currBldrCtx);
418 for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I != E; ++I) {
419 ExplodedNode *N = *I;
420 Bldr.generateNode(PP, N->getState(), N);
423 // Enqueue the new nodes onto the work list.
424 Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
427 void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D,
428 ExplodedNode *Pred) {
430 switch (D.getKind()) {
431 case CFGElement::AutomaticObjectDtor:
432 ProcessAutomaticObjDtor(cast<CFGAutomaticObjDtor>(D), Pred, Dst);
434 case CFGElement::BaseDtor:
435 ProcessBaseDtor(cast<CFGBaseDtor>(D), Pred, Dst);
437 case CFGElement::MemberDtor:
438 ProcessMemberDtor(cast<CFGMemberDtor>(D), Pred, Dst);
440 case CFGElement::TemporaryDtor:
441 ProcessTemporaryDtor(cast<CFGTemporaryDtor>(D), Pred, Dst);
444 llvm_unreachable("Unexpected dtor kind.");
447 // Enqueue the new nodes onto the work list.
448 Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
451 void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor Dtor,
453 ExplodedNodeSet &Dst) {
454 ProgramStateRef state = Pred->getState();
455 const VarDecl *varDecl = Dtor.getVarDecl();
457 QualType varType = varDecl->getType();
459 if (const ReferenceType *refType = varType->getAs<ReferenceType>())
460 varType = refType->getPointeeType();
462 Loc dest = state->getLValue(varDecl, Pred->getLocationContext());
464 VisitCXXDestructor(varType, cast<loc::MemRegionVal>(dest).getRegion(),
465 Dtor.getTriggerStmt(), /*IsBase=*/false, Pred, Dst);
468 void ExprEngine::ProcessBaseDtor(const CFGBaseDtor D,
469 ExplodedNode *Pred, ExplodedNodeSet &Dst) {
470 const LocationContext *LCtx = Pred->getLocationContext();
471 ProgramStateRef State = Pred->getState();
473 const CXXDestructorDecl *CurDtor = cast<CXXDestructorDecl>(LCtx->getDecl());
474 Loc ThisPtr = getSValBuilder().getCXXThis(CurDtor,
475 LCtx->getCurrentStackFrame());
476 SVal ThisVal = Pred->getState()->getSVal(ThisPtr);
478 // Create the base object region.
479 QualType BaseTy = D.getBaseSpecifier()->getType();
480 SVal BaseVal = getStoreManager().evalDerivedToBase(ThisVal, BaseTy);
482 VisitCXXDestructor(BaseTy, cast<loc::MemRegionVal>(BaseVal).getRegion(),
483 CurDtor->getBody(), /*IsBase=*/true, Pred, Dst);
486 void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D,
487 ExplodedNode *Pred, ExplodedNodeSet &Dst) {
488 const FieldDecl *Member = D.getFieldDecl();
489 ProgramStateRef State = Pred->getState();
490 const LocationContext *LCtx = Pred->getLocationContext();
492 const CXXDestructorDecl *CurDtor = cast<CXXDestructorDecl>(LCtx->getDecl());
493 Loc ThisVal = getSValBuilder().getCXXThis(CurDtor,
494 LCtx->getCurrentStackFrame());
495 SVal FieldVal = State->getLValue(Member, cast<Loc>(State->getSVal(ThisVal)));
497 VisitCXXDestructor(Member->getType(),
498 cast<loc::MemRegionVal>(FieldVal).getRegion(),
499 CurDtor->getBody(), /*IsBase=*/false, Pred, Dst);
502 void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D,
504 ExplodedNodeSet &Dst) {}
506 void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred,
507 ExplodedNodeSet &DstTop) {
508 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
510 "Error evaluating statement");
512 StmtNodeBuilder Bldr(Pred, DstTop, *currBldrCtx);
514 // Expressions to ignore.
515 if (const Expr *Ex = dyn_cast<Expr>(S))
516 S = Ex->IgnoreParens();
518 // FIXME: add metadata to the CFG so that we can disable
519 // this check when we KNOW that there is no block-level subexpression.
520 // The motivation is that this check requires a hashtable lookup.
522 if (S != currStmt && Pred->getLocationContext()->getCFG()->isBlkExpr(S))
525 switch (S->getStmtClass()) {
526 // C++ and ARC stuff we don't support yet.
527 case Expr::ObjCIndirectCopyRestoreExprClass:
528 case Stmt::CXXDependentScopeMemberExprClass:
529 case Stmt::CXXPseudoDestructorExprClass:
530 case Stmt::CXXTryStmtClass:
531 case Stmt::CXXTypeidExprClass:
532 case Stmt::CXXUuidofExprClass:
533 case Stmt::CXXUnresolvedConstructExprClass:
534 case Stmt::DependentScopeDeclRefExprClass:
535 case Stmt::UnaryTypeTraitExprClass:
536 case Stmt::BinaryTypeTraitExprClass:
537 case Stmt::TypeTraitExprClass:
538 case Stmt::ArrayTypeTraitExprClass:
539 case Stmt::ExpressionTraitExprClass:
540 case Stmt::UnresolvedLookupExprClass:
541 case Stmt::UnresolvedMemberExprClass:
542 case Stmt::CXXNoexceptExprClass:
543 case Stmt::PackExpansionExprClass:
544 case Stmt::SubstNonTypeTemplateParmPackExprClass:
545 case Stmt::FunctionParmPackExprClass:
546 case Stmt::SEHTryStmtClass:
547 case Stmt::SEHExceptStmtClass:
548 case Stmt::LambdaExprClass:
549 case Stmt::SEHFinallyStmtClass: {
550 const ExplodedNode *node = Bldr.generateSink(S, Pred, Pred->getState());
551 Engine.addAbortedBlock(node, currBldrCtx->getBlock());
555 case Stmt::ParenExprClass:
556 llvm_unreachable("ParenExprs already handled.");
557 case Stmt::GenericSelectionExprClass:
558 llvm_unreachable("GenericSelectionExprs already handled.");
559 // Cases that should never be evaluated simply because they shouldn't
560 // appear in the CFG.
561 case Stmt::BreakStmtClass:
562 case Stmt::CaseStmtClass:
563 case Stmt::CompoundStmtClass:
564 case Stmt::ContinueStmtClass:
565 case Stmt::CXXForRangeStmtClass:
566 case Stmt::DefaultStmtClass:
567 case Stmt::DoStmtClass:
568 case Stmt::ForStmtClass:
569 case Stmt::GotoStmtClass:
570 case Stmt::IfStmtClass:
571 case Stmt::IndirectGotoStmtClass:
572 case Stmt::LabelStmtClass:
573 case Stmt::AttributedStmtClass:
574 case Stmt::NoStmtClass:
575 case Stmt::NullStmtClass:
576 case Stmt::SwitchStmtClass:
577 case Stmt::WhileStmtClass:
578 case Expr::MSDependentExistsStmtClass:
579 llvm_unreachable("Stmt should not be in analyzer evaluation loop");
581 case Stmt::ObjCSubscriptRefExprClass:
582 case Stmt::ObjCPropertyRefExprClass:
583 llvm_unreachable("These are handled by PseudoObjectExpr");
585 case Stmt::GNUNullExprClass: {
586 // GNU __null is a pointer-width integer, not an actual pointer.
587 ProgramStateRef state = Pred->getState();
588 state = state->BindExpr(S, Pred->getLocationContext(),
589 svalBuilder.makeIntValWithPtrWidth(0, false));
590 Bldr.generateNode(S, Pred, state);
594 case Stmt::ObjCAtSynchronizedStmtClass:
595 Bldr.takeNodes(Pred);
596 VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S), Pred, Dst);
600 case Stmt::ExprWithCleanupsClass:
601 // Handled due to fully linearised CFG.
604 // Cases not handled yet; but will handle some day.
605 case Stmt::DesignatedInitExprClass:
606 case Stmt::ExtVectorElementExprClass:
607 case Stmt::ImaginaryLiteralClass:
608 case Stmt::ObjCAtCatchStmtClass:
609 case Stmt::ObjCAtFinallyStmtClass:
610 case Stmt::ObjCAtTryStmtClass:
611 case Stmt::ObjCAutoreleasePoolStmtClass:
612 case Stmt::ObjCEncodeExprClass:
613 case Stmt::ObjCIsaExprClass:
614 case Stmt::ObjCProtocolExprClass:
615 case Stmt::ObjCSelectorExprClass:
616 case Stmt::ParenListExprClass:
617 case Stmt::PredefinedExprClass:
618 case Stmt::ShuffleVectorExprClass:
619 case Stmt::VAArgExprClass:
620 case Stmt::CUDAKernelCallExprClass:
621 case Stmt::OpaqueValueExprClass:
622 case Stmt::AsTypeExprClass:
623 case Stmt::AtomicExprClass:
626 // Cases we intentionally don't evaluate, since they don't need
627 // to be explicitly evaluated.
628 case Stmt::AddrLabelExprClass:
629 case Stmt::IntegerLiteralClass:
630 case Stmt::CharacterLiteralClass:
631 case Stmt::ImplicitValueInitExprClass:
632 case Stmt::CXXScalarValueInitExprClass:
633 case Stmt::CXXBoolLiteralExprClass:
634 case Stmt::ObjCBoolLiteralExprClass:
635 case Stmt::FloatingLiteralClass:
636 case Stmt::SizeOfPackExprClass:
637 case Stmt::StringLiteralClass:
638 case Stmt::ObjCStringLiteralClass:
639 case Stmt::CXXBindTemporaryExprClass:
640 case Stmt::CXXDefaultArgExprClass:
641 case Stmt::SubstNonTypeTemplateParmExprClass:
642 case Stmt::CXXNullPtrLiteralExprClass: {
643 Bldr.takeNodes(Pred);
644 ExplodedNodeSet preVisit;
645 getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this);
646 getCheckerManager().runCheckersForPostStmt(Dst, preVisit, S, *this);
651 case Expr::ObjCArrayLiteralClass:
652 case Expr::ObjCDictionaryLiteralClass:
653 // FIXME: explicitly model with a region and the actual contents
654 // of the container. For now, conjure a symbol.
655 case Expr::ObjCBoxedExprClass: {
656 Bldr.takeNodes(Pred);
658 ExplodedNodeSet preVisit;
659 getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this);
662 StmtNodeBuilder Bldr2(preVisit, Tmp, *currBldrCtx);
664 const Expr *Ex = cast<Expr>(S);
665 QualType resultType = Ex->getType();
667 for (ExplodedNodeSet::iterator it = preVisit.begin(), et = preVisit.end();
669 ExplodedNode *N = *it;
670 const LocationContext *LCtx = N->getLocationContext();
671 SVal result = svalBuilder.conjureSymbolVal(0, Ex, LCtx, resultType,
672 currBldrCtx->blockCount());
673 ProgramStateRef state = N->getState()->BindExpr(Ex, LCtx, result);
674 Bldr2.generateNode(S, N, state);
677 getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this);
682 case Stmt::ArraySubscriptExprClass:
683 Bldr.takeNodes(Pred);
684 VisitLvalArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Pred, Dst);
688 case Stmt::GCCAsmStmtClass:
689 Bldr.takeNodes(Pred);
690 VisitGCCAsmStmt(cast<GCCAsmStmt>(S), Pred, Dst);
694 case Stmt::MSAsmStmtClass:
695 Bldr.takeNodes(Pred);
696 VisitMSAsmStmt(cast<MSAsmStmt>(S), Pred, Dst);
700 case Stmt::BlockExprClass:
701 Bldr.takeNodes(Pred);
702 VisitBlockExpr(cast<BlockExpr>(S), Pred, Dst);
706 case Stmt::BinaryOperatorClass: {
707 const BinaryOperator* B = cast<BinaryOperator>(S);
708 if (B->isLogicalOp()) {
709 Bldr.takeNodes(Pred);
710 VisitLogicalExpr(B, Pred, Dst);
714 else if (B->getOpcode() == BO_Comma) {
715 ProgramStateRef state = Pred->getState();
716 Bldr.generateNode(B, Pred,
717 state->BindExpr(B, Pred->getLocationContext(),
718 state->getSVal(B->getRHS(),
719 Pred->getLocationContext())));
723 Bldr.takeNodes(Pred);
725 if (AMgr.options.eagerlyAssumeBinOpBifurcation &&
726 (B->isRelationalOp() || B->isEqualityOp())) {
728 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Tmp);
729 evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, cast<Expr>(S));
732 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
738 case Stmt::CXXOperatorCallExprClass: {
739 const CXXOperatorCallExpr *OCE = cast<CXXOperatorCallExpr>(S);
741 // For instance method operators, make sure the 'this' argument has a
743 const Decl *Callee = OCE->getCalleeDecl();
744 if (const CXXMethodDecl *MD = dyn_cast_or_null<CXXMethodDecl>(Callee)) {
745 if (MD->isInstance()) {
746 ProgramStateRef State = Pred->getState();
747 const LocationContext *LCtx = Pred->getLocationContext();
748 ProgramStateRef NewState =
749 createTemporaryRegionIfNeeded(State, LCtx, OCE->getArg(0));
750 if (NewState != State)
751 Pred = Bldr.generateNode(OCE, Pred, NewState, /*Tag=*/0,
752 ProgramPoint::PreStmtKind);
757 case Stmt::CallExprClass:
758 case Stmt::CXXMemberCallExprClass:
759 case Stmt::UserDefinedLiteralClass: {
760 Bldr.takeNodes(Pred);
761 VisitCallExpr(cast<CallExpr>(S), Pred, Dst);
766 case Stmt::CXXCatchStmtClass: {
767 Bldr.takeNodes(Pred);
768 VisitCXXCatchStmt(cast<CXXCatchStmt>(S), Pred, Dst);
773 case Stmt::CXXTemporaryObjectExprClass:
774 case Stmt::CXXConstructExprClass: {
775 Bldr.takeNodes(Pred);
776 VisitCXXConstructExpr(cast<CXXConstructExpr>(S), Pred, Dst);
781 case Stmt::CXXNewExprClass: {
782 Bldr.takeNodes(Pred);
783 const CXXNewExpr *NE = cast<CXXNewExpr>(S);
784 VisitCXXNewExpr(NE, Pred, Dst);
789 case Stmt::CXXDeleteExprClass: {
790 Bldr.takeNodes(Pred);
791 const CXXDeleteExpr *CDE = cast<CXXDeleteExpr>(S);
792 VisitCXXDeleteExpr(CDE, Pred, Dst);
796 // FIXME: ChooseExpr is really a constant. We need to fix
797 // the CFG do not model them as explicit control-flow.
799 case Stmt::ChooseExprClass: { // __builtin_choose_expr
800 Bldr.takeNodes(Pred);
801 const ChooseExpr *C = cast<ChooseExpr>(S);
802 VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst);
807 case Stmt::CompoundAssignOperatorClass:
808 Bldr.takeNodes(Pred);
809 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
813 case Stmt::CompoundLiteralExprClass:
814 Bldr.takeNodes(Pred);
815 VisitCompoundLiteralExpr(cast<CompoundLiteralExpr>(S), Pred, Dst);
819 case Stmt::BinaryConditionalOperatorClass:
820 case Stmt::ConditionalOperatorClass: { // '?' operator
821 Bldr.takeNodes(Pred);
822 const AbstractConditionalOperator *C
823 = cast<AbstractConditionalOperator>(S);
824 VisitGuardedExpr(C, C->getTrueExpr(), C->getFalseExpr(), Pred, Dst);
829 case Stmt::CXXThisExprClass:
830 Bldr.takeNodes(Pred);
831 VisitCXXThisExpr(cast<CXXThisExpr>(S), Pred, Dst);
835 case Stmt::DeclRefExprClass: {
836 Bldr.takeNodes(Pred);
837 const DeclRefExpr *DE = cast<DeclRefExpr>(S);
838 VisitCommonDeclRefExpr(DE, DE->getDecl(), Pred, Dst);
843 case Stmt::DeclStmtClass:
844 Bldr.takeNodes(Pred);
845 VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst);
849 case Stmt::ImplicitCastExprClass:
850 case Stmt::CStyleCastExprClass:
851 case Stmt::CXXStaticCastExprClass:
852 case Stmt::CXXDynamicCastExprClass:
853 case Stmt::CXXReinterpretCastExprClass:
854 case Stmt::CXXConstCastExprClass:
855 case Stmt::CXXFunctionalCastExprClass:
856 case Stmt::ObjCBridgedCastExprClass: {
857 Bldr.takeNodes(Pred);
858 const CastExpr *C = cast<CastExpr>(S);
859 // Handle the previsit checks.
860 ExplodedNodeSet dstPrevisit;
861 getCheckerManager().runCheckersForPreStmt(dstPrevisit, Pred, C, *this);
863 // Handle the expression itself.
864 ExplodedNodeSet dstExpr;
865 for (ExplodedNodeSet::iterator i = dstPrevisit.begin(),
866 e = dstPrevisit.end(); i != e ; ++i) {
867 VisitCast(C, C->getSubExpr(), *i, dstExpr);
870 // Handle the postvisit checks.
871 getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, C, *this);
876 case Expr::MaterializeTemporaryExprClass: {
877 Bldr.takeNodes(Pred);
878 const MaterializeTemporaryExpr *MTE = cast<MaterializeTemporaryExpr>(S);
879 CreateCXXTemporaryObject(MTE, Pred, Dst);
884 case Stmt::InitListExprClass:
885 Bldr.takeNodes(Pred);
886 VisitInitListExpr(cast<InitListExpr>(S), Pred, Dst);
890 case Stmt::MemberExprClass:
891 Bldr.takeNodes(Pred);
892 VisitMemberExpr(cast<MemberExpr>(S), Pred, Dst);
896 case Stmt::ObjCIvarRefExprClass:
897 Bldr.takeNodes(Pred);
898 VisitLvalObjCIvarRefExpr(cast<ObjCIvarRefExpr>(S), Pred, Dst);
902 case Stmt::ObjCForCollectionStmtClass:
903 Bldr.takeNodes(Pred);
904 VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S), Pred, Dst);
908 case Stmt::ObjCMessageExprClass:
909 Bldr.takeNodes(Pred);
910 VisitObjCMessage(cast<ObjCMessageExpr>(S), Pred, Dst);
914 case Stmt::ObjCAtThrowStmtClass:
915 case Stmt::CXXThrowExprClass:
916 // FIXME: This is not complete. We basically treat @throw as
918 Bldr.generateSink(S, Pred, Pred->getState());
921 case Stmt::ReturnStmtClass:
922 Bldr.takeNodes(Pred);
923 VisitReturnStmt(cast<ReturnStmt>(S), Pred, Dst);
927 case Stmt::OffsetOfExprClass:
928 Bldr.takeNodes(Pred);
929 VisitOffsetOfExpr(cast<OffsetOfExpr>(S), Pred, Dst);
933 case Stmt::UnaryExprOrTypeTraitExprClass:
934 Bldr.takeNodes(Pred);
935 VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S),
940 case Stmt::StmtExprClass: {
941 const StmtExpr *SE = cast<StmtExpr>(S);
943 if (SE->getSubStmt()->body_empty()) {
944 // Empty statement expression.
945 assert(SE->getType() == getContext().VoidTy
946 && "Empty statement expression must have void type.");
950 if (Expr *LastExpr = dyn_cast<Expr>(*SE->getSubStmt()->body_rbegin())) {
951 ProgramStateRef state = Pred->getState();
952 Bldr.generateNode(SE, Pred,
953 state->BindExpr(SE, Pred->getLocationContext(),
954 state->getSVal(LastExpr,
955 Pred->getLocationContext())));
960 case Stmt::UnaryOperatorClass: {
961 Bldr.takeNodes(Pred);
962 const UnaryOperator *U = cast<UnaryOperator>(S);
963 if (AMgr.options.eagerlyAssumeBinOpBifurcation && (U->getOpcode() == UO_LNot)) {
965 VisitUnaryOperator(U, Pred, Tmp);
966 evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, U);
969 VisitUnaryOperator(U, Pred, Dst);
974 case Stmt::PseudoObjectExprClass: {
975 Bldr.takeNodes(Pred);
976 ProgramStateRef state = Pred->getState();
977 const PseudoObjectExpr *PE = cast<PseudoObjectExpr>(S);
978 if (const Expr *Result = PE->getResultExpr()) {
979 SVal V = state->getSVal(Result, Pred->getLocationContext());
980 Bldr.generateNode(S, Pred,
981 state->BindExpr(S, Pred->getLocationContext(), V));
984 Bldr.generateNode(S, Pred,
985 state->BindExpr(S, Pred->getLocationContext(),
994 bool ExprEngine::replayWithoutInlining(ExplodedNode *N,
995 const LocationContext *CalleeLC) {
996 const StackFrameContext *CalleeSF = CalleeLC->getCurrentStackFrame();
997 const StackFrameContext *CallerSF = CalleeSF->getParent()->getCurrentStackFrame();
998 assert(CalleeSF && CallerSF);
999 ExplodedNode *BeforeProcessingCall = 0;
1000 const Stmt *CE = CalleeSF->getCallSite();
1002 // Find the first node before we started processing the call expression.
1004 ProgramPoint L = N->getLocation();
1005 BeforeProcessingCall = N;
1006 N = N->pred_empty() ? NULL : *(N->pred_begin());
1008 // Skip the nodes corresponding to the inlined code.
1009 if (L.getLocationContext()->getCurrentStackFrame() != CallerSF)
1011 // We reached the caller. Find the node right before we started
1012 // processing the call.
1013 if (L.isPurgeKind())
1015 if (isa<PreImplicitCall>(&L))
1017 if (isa<CallEnter>(&L))
1019 if (const StmtPoint *SP = dyn_cast<StmtPoint>(&L))
1020 if (SP->getStmt() == CE)
1025 if (!BeforeProcessingCall)
1028 // TODO: Clean up the unneeded nodes.
1030 // Build an Epsilon node from which we will restart the analyzes.
1031 // Note that CE is permitted to be NULL!
1032 ProgramPoint NewNodeLoc =
1033 EpsilonPoint(BeforeProcessingCall->getLocationContext(), CE);
1034 // Add the special flag to GDM to signal retrying with no inlining.
1035 // Note, changing the state ensures that we are not going to cache out.
1036 ProgramStateRef NewNodeState = BeforeProcessingCall->getState();
1037 NewNodeState = NewNodeState->set<ReplayWithoutInlining>((void*)CE);
1039 // Make the new node a successor of BeforeProcessingCall.
1041 ExplodedNode *NewNode = G.getNode(NewNodeLoc, NewNodeState, false, &IsNew);
1042 // We cached out at this point. Caching out is common due to us backtracking
1043 // from the inlined function, which might spawn several paths.
1047 NewNode->addPredecessor(BeforeProcessingCall, G);
1049 // Add the new node to the work list.
1050 Engine.enqueueStmtNode(NewNode, CalleeSF->getCallSiteBlock(),
1051 CalleeSF->getIndex());
1052 NumTimesRetriedWithoutInlining++;
1056 /// Block entrance. (Update counters).
1057 void ExprEngine::processCFGBlockEntrance(const BlockEdge &L,
1058 NodeBuilderWithSinks &nodeBuilder,
1059 ExplodedNode *Pred) {
1061 // FIXME: Refactor this into a checker.
1062 if (nodeBuilder.getContext().blockCount() >= AMgr.options.maxBlockVisitOnPath) {
1063 static SimpleProgramPointTag tag("ExprEngine : Block count exceeded");
1064 const ExplodedNode *Sink =
1065 nodeBuilder.generateSink(Pred->getState(), Pred, &tag);
1067 // Check if we stopped at the top level function or not.
1068 // Root node should have the location context of the top most function.
1069 const LocationContext *CalleeLC = Pred->getLocation().getLocationContext();
1070 const LocationContext *CalleeSF = CalleeLC->getCurrentStackFrame();
1071 const LocationContext *RootLC =
1072 (*G.roots_begin())->getLocation().getLocationContext();
1073 if (RootLC->getCurrentStackFrame() != CalleeSF) {
1074 Engine.FunctionSummaries->markReachedMaxBlockCount(CalleeSF->getDecl());
1076 // Re-run the call evaluation without inlining it, by storing the
1077 // no-inlining policy in the state and enqueuing the new work item on
1078 // the list. Replay should almost never fail. Use the stats to catch it
1080 if ((!AMgr.options.NoRetryExhausted &&
1081 replayWithoutInlining(Pred, CalleeLC)))
1083 NumMaxBlockCountReachedInInlined++;
1085 NumMaxBlockCountReached++;
1087 // Make sink nodes as exhausted(for stats) only if retry failed.
1088 Engine.blocksExhausted.push_back(std::make_pair(L, Sink));
1092 //===----------------------------------------------------------------------===//
1093 // Branch processing.
1094 //===----------------------------------------------------------------------===//
1096 /// RecoverCastedSymbol - A helper function for ProcessBranch that is used
1097 /// to try to recover some path-sensitivity for casts of symbolic
1098 /// integers that promote their values (which are currently not tracked well).
1099 /// This function returns the SVal bound to Condition->IgnoreCasts if all the
1100 // cast(s) did was sign-extend the original value.
1101 static SVal RecoverCastedSymbol(ProgramStateManager& StateMgr,
1102 ProgramStateRef state,
1103 const Stmt *Condition,
1104 const LocationContext *LCtx,
1107 const Expr *Ex = dyn_cast<Expr>(Condition);
1109 return UnknownVal();
1112 bool bitsInit = false;
1114 while (const CastExpr *CE = dyn_cast<CastExpr>(Ex)) {
1115 QualType T = CE->getType();
1117 if (!T->isIntegerType())
1118 return UnknownVal();
1120 uint64_t newBits = Ctx.getTypeSize(T);
1121 if (!bitsInit || newBits < bits) {
1126 Ex = CE->getSubExpr();
1129 // We reached a non-cast. Is it a symbolic value?
1130 QualType T = Ex->getType();
1132 if (!bitsInit || !T->isIntegerType() || Ctx.getTypeSize(T) > bits)
1133 return UnknownVal();
1135 return state->getSVal(Ex, LCtx);
1138 static const Stmt *ResolveCondition(const Stmt *Condition,
1139 const CFGBlock *B) {
1140 if (const Expr *Ex = dyn_cast<Expr>(Condition))
1141 Condition = Ex->IgnoreParens();
1143 const BinaryOperator *BO = dyn_cast<BinaryOperator>(Condition);
1144 if (!BO || !BO->isLogicalOp())
1147 // For logical operations, we still have the case where some branches
1148 // use the traditional "merge" approach and others sink the branch
1149 // directly into the basic blocks representing the logical operation.
1150 // We need to distinguish between those two cases here.
1152 // The invariants are still shifting, but it is possible that the
1153 // last element in a CFGBlock is not a CFGStmt. Look for the last
1154 // CFGStmt as the value of the condition.
1155 CFGBlock::const_reverse_iterator I = B->rbegin(), E = B->rend();
1156 for (; I != E; ++I) {
1157 CFGElement Elem = *I;
1158 CFGStmt *CS = dyn_cast<CFGStmt>(&Elem);
1161 if (CS->getStmt() != Condition)
1169 BO = dyn_cast<BinaryOperator>(Condition);
1170 if (!BO || !BO->isLogicalOp())
1172 Condition = BO->getRHS()->IgnoreParens();
1174 llvm_unreachable("could not resolve condition");
1177 void ExprEngine::processBranch(const Stmt *Condition, const Stmt *Term,
1178 NodeBuilderContext& BldCtx,
1180 ExplodedNodeSet &Dst,
1181 const CFGBlock *DstT,
1182 const CFGBlock *DstF) {
1183 currBldrCtx = &BldCtx;
1185 // Check for NULL conditions; e.g. "for(;;)"
1187 BranchNodeBuilder NullCondBldr(Pred, Dst, BldCtx, DstT, DstF);
1188 NullCondBldr.markInfeasible(false);
1189 NullCondBldr.generateNode(Pred->getState(), true, Pred);
1194 // Resolve the condition in the precense of nested '||' and '&&'.
1195 if (const Expr *Ex = dyn_cast<Expr>(Condition))
1196 Condition = Ex->IgnoreParens();
1198 Condition = ResolveCondition(Condition, BldCtx.getBlock());
1199 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
1200 Condition->getLocStart(),
1201 "Error evaluating branch");
1203 ExplodedNodeSet CheckersOutSet;
1204 getCheckerManager().runCheckersForBranchCondition(Condition, CheckersOutSet,
1206 // We generated only sinks.
1207 if (CheckersOutSet.empty())
1210 BranchNodeBuilder builder(CheckersOutSet, Dst, BldCtx, DstT, DstF);
1211 for (NodeBuilder::iterator I = CheckersOutSet.begin(),
1212 E = CheckersOutSet.end(); E != I; ++I) {
1213 ExplodedNode *PredI = *I;
1215 if (PredI->isSink())
1218 ProgramStateRef PrevState = Pred->getState();
1219 SVal X = PrevState->getSVal(Condition, Pred->getLocationContext());
1221 if (X.isUnknownOrUndef()) {
1222 // Give it a chance to recover from unknown.
1223 if (const Expr *Ex = dyn_cast<Expr>(Condition)) {
1224 if (Ex->getType()->isIntegerType()) {
1225 // Try to recover some path-sensitivity. Right now casts of symbolic
1226 // integers that promote their values are currently not tracked well.
1227 // If 'Condition' is such an expression, try and recover the
1228 // underlying value and use that instead.
1229 SVal recovered = RecoverCastedSymbol(getStateManager(),
1230 PrevState, Condition,
1231 Pred->getLocationContext(),
1234 if (!recovered.isUnknown()) {
1241 // If the condition is still unknown, give up.
1242 if (X.isUnknownOrUndef()) {
1243 builder.generateNode(PrevState, true, PredI);
1244 builder.generateNode(PrevState, false, PredI);
1248 DefinedSVal V = cast<DefinedSVal>(X);
1250 // Process the true branch.
1251 if (builder.isFeasible(true)) {
1252 if (ProgramStateRef state = PrevState->assume(V, true))
1253 builder.generateNode(state, true, PredI);
1255 builder.markInfeasible(true);
1258 // Process the false branch.
1259 if (builder.isFeasible(false)) {
1260 if (ProgramStateRef state = PrevState->assume(V, false))
1261 builder.generateNode(state, false, PredI);
1263 builder.markInfeasible(false);
1269 /// processIndirectGoto - Called by CoreEngine. Used to generate successor
1270 /// nodes by processing the 'effects' of a computed goto jump.
1271 void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) {
1273 ProgramStateRef state = builder.getState();
1274 SVal V = state->getSVal(builder.getTarget(), builder.getLocationContext());
1276 // Three possibilities:
1278 // (1) We know the computed label.
1279 // (2) The label is NULL (or some other constant), or Undefined.
1280 // (3) We have no clue about the label. Dispatch to all targets.
1283 typedef IndirectGotoNodeBuilder::iterator iterator;
1285 if (isa<loc::GotoLabel>(V)) {
1286 const LabelDecl *L = cast<loc::GotoLabel>(V).getLabel();
1288 for (iterator I = builder.begin(), E = builder.end(); I != E; ++I) {
1289 if (I.getLabel() == L) {
1290 builder.generateNode(I, state);
1295 llvm_unreachable("No block with label.");
1298 if (isa<loc::ConcreteInt>(V) || isa<UndefinedVal>(V)) {
1299 // Dispatch to the first target and mark it as a sink.
1300 //ExplodedNode* N = builder.generateNode(builder.begin(), state, true);
1301 // FIXME: add checker visit.
1302 // UndefBranches.insert(N);
1306 // This is really a catch-all. We don't support symbolics yet.
1307 // FIXME: Implement dispatch for symbolic pointers.
1309 for (iterator I=builder.begin(), E=builder.end(); I != E; ++I)
1310 builder.generateNode(I, state);
1313 /// ProcessEndPath - Called by CoreEngine. Used to generate end-of-path
1314 /// nodes when the control reaches the end of a function.
1315 void ExprEngine::processEndOfFunction(NodeBuilderContext& BC,
1316 ExplodedNode *Pred) {
1317 StateMgr.EndPath(Pred->getState());
1319 ExplodedNodeSet Dst;
1320 if (Pred->getLocationContext()->inTopFrame()) {
1321 // Remove dead symbols.
1322 ExplodedNodeSet AfterRemovedDead;
1323 removeDeadOnEndOfFunction(BC, Pred, AfterRemovedDead);
1326 for (ExplodedNodeSet::iterator I = AfterRemovedDead.begin(),
1327 E = AfterRemovedDead.end(); I != E; ++I) {
1328 getCheckerManager().runCheckersForEndPath(BC, Dst, *I, *this);
1331 getCheckerManager().runCheckersForEndPath(BC, Dst, Pred, *this);
1334 Engine.enqueueEndOfFunction(Dst);
1337 /// ProcessSwitch - Called by CoreEngine. Used to generate successor
1338 /// nodes by processing the 'effects' of a switch statement.
1339 void ExprEngine::processSwitch(SwitchNodeBuilder& builder) {
1340 typedef SwitchNodeBuilder::iterator iterator;
1341 ProgramStateRef state = builder.getState();
1342 const Expr *CondE = builder.getCondition();
1343 SVal CondV_untested = state->getSVal(CondE, builder.getLocationContext());
1345 if (CondV_untested.isUndef()) {
1346 //ExplodedNode* N = builder.generateDefaultCaseNode(state, true);
1347 // FIXME: add checker
1348 //UndefBranches.insert(N);
1352 DefinedOrUnknownSVal CondV = cast<DefinedOrUnknownSVal>(CondV_untested);
1354 ProgramStateRef DefaultSt = state;
1356 iterator I = builder.begin(), EI = builder.end();
1357 bool defaultIsFeasible = I == EI;
1359 for ( ; I != EI; ++I) {
1360 // Successor may be pruned out during CFG construction.
1364 const CaseStmt *Case = I.getCase();
1366 // Evaluate the LHS of the case value.
1367 llvm::APSInt V1 = Case->getLHS()->EvaluateKnownConstInt(getContext());
1368 assert(V1.getBitWidth() == getContext().getTypeSize(CondE->getType()));
1370 // Get the RHS of the case, if it exists.
1372 if (const Expr *E = Case->getRHS())
1373 V2 = E->EvaluateKnownConstInt(getContext());
1377 // FIXME: Eventually we should replace the logic below with a range
1378 // comparison, rather than concretize the values within the range.
1379 // This should be easy once we have "ranges" for NonLVals.
1382 nonloc::ConcreteInt CaseVal(getBasicVals().getValue(V1));
1383 DefinedOrUnknownSVal Res = svalBuilder.evalEQ(DefaultSt ? DefaultSt : state,
1386 // Now "assume" that the case matches.
1387 if (ProgramStateRef stateNew = state->assume(Res, true)) {
1388 builder.generateCaseStmtNode(I, stateNew);
1390 // If CondV evaluates to a constant, then we know that this
1391 // is the *only* case that we can take, so stop evaluating the
1393 if (isa<nonloc::ConcreteInt>(CondV))
1397 // Now "assume" that the case doesn't match. Add this state
1398 // to the default state (if it is feasible).
1400 if (ProgramStateRef stateNew = DefaultSt->assume(Res, false)) {
1401 defaultIsFeasible = true;
1402 DefaultSt = stateNew;
1405 defaultIsFeasible = false;
1410 // Concretize the next value in the range.
1420 if (!defaultIsFeasible)
1423 // If we have switch(enum value), the default branch is not
1424 // feasible if all of the enum constants not covered by 'case:' statements
1425 // are not feasible values for the switch condition.
1427 // Note that this isn't as accurate as it could be. Even if there isn't
1428 // a case for a particular enum value as long as that enum value isn't
1429 // feasible then it shouldn't be considered for making 'default:' reachable.
1430 const SwitchStmt *SS = builder.getSwitch();
1431 const Expr *CondExpr = SS->getCond()->IgnoreParenImpCasts();
1432 if (CondExpr->getType()->getAs<EnumType>()) {
1433 if (SS->isAllEnumCasesCovered())
1437 builder.generateDefaultCaseNode(DefaultSt);
1440 //===----------------------------------------------------------------------===//
1441 // Transfer functions: Loads and stores.
1442 //===----------------------------------------------------------------------===//
1444 void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D,
1446 ExplodedNodeSet &Dst) {
1447 StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
1449 ProgramStateRef state = Pred->getState();
1450 const LocationContext *LCtx = Pred->getLocationContext();
1452 if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
1453 assert(Ex->isGLValue());
1454 SVal V = state->getLValue(VD, Pred->getLocationContext());
1456 // For references, the 'lvalue' is the pointer address stored in the
1457 // reference region.
1458 if (VD->getType()->isReferenceType()) {
1459 if (const MemRegion *R = V.getAsRegion())
1460 V = state->getSVal(R);
1465 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), 0,
1466 ProgramPoint::PostLValueKind);
1469 if (const EnumConstantDecl *ED = dyn_cast<EnumConstantDecl>(D)) {
1470 assert(!Ex->isGLValue());
1471 SVal V = svalBuilder.makeIntVal(ED->getInitVal());
1472 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V));
1475 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
1476 SVal V = svalBuilder.getFunctionPointer(FD);
1477 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), 0,
1478 ProgramPoint::PostLValueKind);
1481 if (isa<FieldDecl>(D)) {
1482 // FIXME: Compute lvalue of field pointers-to-member.
1483 // Right now we just use a non-null void pointer, so that it gives proper
1484 // results in boolean contexts.
1485 SVal V = svalBuilder.conjureSymbolVal(Ex, LCtx, getContext().VoidPtrTy,
1486 currBldrCtx->blockCount());
1487 state = state->assume(cast<DefinedOrUnknownSVal>(V), true);
1488 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), 0,
1489 ProgramPoint::PostLValueKind);
1493 llvm_unreachable("Support for this Decl not implemented.");
1496 /// VisitArraySubscriptExpr - Transfer function for array accesses
1497 void ExprEngine::VisitLvalArraySubscriptExpr(const ArraySubscriptExpr *A,
1499 ExplodedNodeSet &Dst){
1501 const Expr *Base = A->getBase()->IgnoreParens();
1502 const Expr *Idx = A->getIdx()->IgnoreParens();
1505 ExplodedNodeSet checkerPreStmt;
1506 getCheckerManager().runCheckersForPreStmt(checkerPreStmt, Pred, A, *this);
1508 StmtNodeBuilder Bldr(checkerPreStmt, Dst, *currBldrCtx);
1510 for (ExplodedNodeSet::iterator it = checkerPreStmt.begin(),
1511 ei = checkerPreStmt.end(); it != ei; ++it) {
1512 const LocationContext *LCtx = (*it)->getLocationContext();
1513 ProgramStateRef state = (*it)->getState();
1514 SVal V = state->getLValue(A->getType(),
1515 state->getSVal(Idx, LCtx),
1516 state->getSVal(Base, LCtx));
1517 assert(A->isGLValue());
1518 Bldr.generateNode(A, *it, state->BindExpr(A, LCtx, V), 0,
1519 ProgramPoint::PostLValueKind);
1523 /// VisitMemberExpr - Transfer function for member expressions.
1524 void ExprEngine::VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred,
1525 ExplodedNodeSet &TopDst) {
1527 StmtNodeBuilder Bldr(Pred, TopDst, *currBldrCtx);
1528 ExplodedNodeSet Dst;
1529 ValueDecl *Member = M->getMemberDecl();
1531 // Handle static member variables and enum constants accessed via
1533 if (isa<VarDecl>(Member) || isa<EnumConstantDecl>(Member)) {
1534 Bldr.takeNodes(Pred);
1535 VisitCommonDeclRefExpr(M, Member, Pred, Dst);
1540 ProgramStateRef state = Pred->getState();
1541 const LocationContext *LCtx = Pred->getLocationContext();
1542 Expr *BaseExpr = M->getBase();
1544 // Handle C++ method calls.
1545 if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(Member)) {
1546 if (MD->isInstance())
1547 state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr);
1549 SVal MDVal = svalBuilder.getFunctionPointer(MD);
1550 state = state->BindExpr(M, LCtx, MDVal);
1552 Bldr.generateNode(M, Pred, state);
1556 // Handle regular struct fields / member variables.
1557 state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr);
1558 SVal baseExprVal = state->getSVal(BaseExpr, LCtx);
1560 FieldDecl *field = cast<FieldDecl>(Member);
1561 SVal L = state->getLValue(field, baseExprVal);
1562 if (M->isGLValue()) {
1563 if (field->getType()->isReferenceType()) {
1564 if (const MemRegion *R = L.getAsRegion())
1565 L = state->getSVal(R);
1570 Bldr.generateNode(M, Pred, state->BindExpr(M, LCtx, L), 0,
1571 ProgramPoint::PostLValueKind);
1573 Bldr.takeNodes(Pred);
1574 evalLoad(Dst, M, M, Pred, state, L);
1579 /// evalBind - Handle the semantics of binding a value to a specific location.
1580 /// This method is used by evalStore and (soon) VisitDeclStmt, and others.
1581 void ExprEngine::evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE,
1583 SVal location, SVal Val,
1584 bool atDeclInit, const ProgramPoint *PP) {
1586 const LocationContext *LC = Pred->getLocationContext();
1587 PostStmt PS(StoreE, LC);
1591 // Do a previsit of the bind.
1592 ExplodedNodeSet CheckedSet;
1593 getCheckerManager().runCheckersForBind(CheckedSet, Pred, location, Val,
1594 StoreE, *this, *PP);
1596 // If the location is not a 'Loc', it will already be handled by
1597 // the checkers. There is nothing left to do.
1598 if (!isa<Loc>(location)) {
1603 ExplodedNodeSet TmpDst;
1604 StmtNodeBuilder Bldr(CheckedSet, TmpDst, *currBldrCtx);
1606 for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end();
1608 ExplodedNode *PredI = *I;
1609 ProgramStateRef state = PredI->getState();
1611 // When binding the value, pass on the hint that this is a initialization.
1612 // For initializations, we do not need to inform clients of region
1614 state = state->bindLoc(cast<Loc>(location),
1615 Val, /* notifyChanges = */ !atDeclInit);
1617 const MemRegion *LocReg = 0;
1618 if (loc::MemRegionVal *LocRegVal = dyn_cast<loc::MemRegionVal>(&location)) {
1619 LocReg = LocRegVal->getRegion();
1622 const ProgramPoint L = PostStore(StoreE, LC, LocReg, 0);
1623 Bldr.generateNode(L, state, PredI);
1628 /// evalStore - Handle the semantics of a store via an assignment.
1629 /// @param Dst The node set to store generated state nodes
1630 /// @param AssignE The assignment expression if the store happens in an
1632 /// @param LocationE The location expression that is stored to.
1633 /// @param state The current simulation state
1634 /// @param location The location to store the value
1635 /// @param Val The value to be stored
1636 void ExprEngine::evalStore(ExplodedNodeSet &Dst, const Expr *AssignE,
1637 const Expr *LocationE,
1639 ProgramStateRef state, SVal location, SVal Val,
1640 const ProgramPointTag *tag) {
1641 // Proceed with the store. We use AssignE as the anchor for the PostStore
1642 // ProgramPoint if it is non-NULL, and LocationE otherwise.
1643 const Expr *StoreE = AssignE ? AssignE : LocationE;
1645 // Evaluate the location (checks for bad dereferences).
1646 ExplodedNodeSet Tmp;
1647 evalLocation(Tmp, AssignE, LocationE, Pred, state, location, tag, false);
1652 if (location.isUndef())
1655 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI)
1656 evalBind(Dst, StoreE, *NI, location, Val, false);
1659 void ExprEngine::evalLoad(ExplodedNodeSet &Dst,
1661 const Expr *BoundEx,
1663 ProgramStateRef state,
1665 const ProgramPointTag *tag,
1668 assert(!isa<NonLoc>(location) && "location cannot be a NonLoc.");
1670 // Are we loading from a region? This actually results in two loads; one
1671 // to fetch the address of the referenced value and one to fetch the
1672 // referenced value.
1673 if (const TypedValueRegion *TR =
1674 dyn_cast_or_null<TypedValueRegion>(location.getAsRegion())) {
1676 QualType ValTy = TR->getValueType();
1677 if (const ReferenceType *RT = ValTy->getAs<ReferenceType>()) {
1678 static SimpleProgramPointTag
1679 loadReferenceTag("ExprEngine : Load Reference");
1680 ExplodedNodeSet Tmp;
1681 evalLoadCommon(Tmp, NodeEx, BoundEx, Pred, state,
1682 location, &loadReferenceTag,
1683 getContext().getPointerType(RT->getPointeeType()));
1685 // Perform the load from the referenced value.
1686 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end() ; I!=E; ++I) {
1687 state = (*I)->getState();
1688 location = state->getSVal(BoundEx, (*I)->getLocationContext());
1689 evalLoadCommon(Dst, NodeEx, BoundEx, *I, state, location, tag, LoadTy);
1695 evalLoadCommon(Dst, NodeEx, BoundEx, Pred, state, location, tag, LoadTy);
1698 void ExprEngine::evalLoadCommon(ExplodedNodeSet &Dst,
1700 const Expr *BoundEx,
1702 ProgramStateRef state,
1704 const ProgramPointTag *tag,
1708 // Evaluate the location (checks for bad dereferences).
1709 ExplodedNodeSet Tmp;
1710 evalLocation(Tmp, NodeEx, BoundEx, Pred, state, location, tag, true);
1714 StmtNodeBuilder Bldr(Tmp, Dst, *currBldrCtx);
1715 if (location.isUndef())
1718 // Proceed with the load.
1719 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) {
1720 state = (*NI)->getState();
1721 const LocationContext *LCtx = (*NI)->getLocationContext();
1723 if (location.isUnknown()) {
1724 // This is important. We must nuke the old binding.
1725 Bldr.generateNode(NodeEx, *NI,
1726 state->BindExpr(BoundEx, LCtx, UnknownVal()),
1727 tag, ProgramPoint::PostLoadKind);
1730 if (LoadTy.isNull())
1731 LoadTy = BoundEx->getType();
1732 SVal V = state->getSVal(cast<Loc>(location), LoadTy);
1733 Bldr.generateNode(NodeEx, *NI,
1734 state->bindExprAndLocation(BoundEx, LCtx, location, V),
1735 tag, ProgramPoint::PostLoadKind);
1740 void ExprEngine::evalLocation(ExplodedNodeSet &Dst,
1742 const Stmt *BoundEx,
1744 ProgramStateRef state,
1746 const ProgramPointTag *tag,
1748 StmtNodeBuilder BldrTop(Pred, Dst, *currBldrCtx);
1749 // Early checks for performance reason.
1750 if (location.isUnknown()) {
1754 ExplodedNodeSet Src;
1755 BldrTop.takeNodes(Pred);
1756 StmtNodeBuilder Bldr(Pred, Src, *currBldrCtx);
1757 if (Pred->getState() != state) {
1758 // Associate this new state with an ExplodedNode.
1759 // FIXME: If I pass null tag, the graph is incorrect, e.g for
1763 // "p = 0" is not noted as "Null pointer value stored to 'p'" but
1764 // instead "int *p" is noted as
1765 // "Variable 'p' initialized to a null pointer value"
1767 static SimpleProgramPointTag tag("ExprEngine: Location");
1768 Bldr.generateNode(NodeEx, Pred, state, &tag);
1770 ExplodedNodeSet Tmp;
1771 getCheckerManager().runCheckersForLocation(Tmp, Src, location, isLoad,
1772 NodeEx, BoundEx, *this);
1773 BldrTop.addNodes(Tmp);
1776 std::pair<const ProgramPointTag *, const ProgramPointTag*>
1777 ExprEngine::geteagerlyAssumeBinOpBifurcationTags() {
1778 static SimpleProgramPointTag
1779 eagerlyAssumeBinOpBifurcationTrue("ExprEngine : Eagerly Assume True"),
1780 eagerlyAssumeBinOpBifurcationFalse("ExprEngine : Eagerly Assume False");
1781 return std::make_pair(&eagerlyAssumeBinOpBifurcationTrue,
1782 &eagerlyAssumeBinOpBifurcationFalse);
1785 void ExprEngine::evalEagerlyAssumeBinOpBifurcation(ExplodedNodeSet &Dst,
1786 ExplodedNodeSet &Src,
1788 StmtNodeBuilder Bldr(Src, Dst, *currBldrCtx);
1790 for (ExplodedNodeSet::iterator I=Src.begin(), E=Src.end(); I!=E; ++I) {
1791 ExplodedNode *Pred = *I;
1792 // Test if the previous node was as the same expression. This can happen
1793 // when the expression fails to evaluate to anything meaningful and
1794 // (as an optimization) we don't generate a node.
1795 ProgramPoint P = Pred->getLocation();
1796 if (!isa<PostStmt>(P) || cast<PostStmt>(P).getStmt() != Ex) {
1800 ProgramStateRef state = Pred->getState();
1801 SVal V = state->getSVal(Ex, Pred->getLocationContext());
1802 nonloc::SymbolVal *SEV = dyn_cast<nonloc::SymbolVal>(&V);
1803 if (SEV && SEV->isExpression()) {
1804 const std::pair<const ProgramPointTag *, const ProgramPointTag*> &tags =
1805 geteagerlyAssumeBinOpBifurcationTags();
1807 // First assume that the condition is true.
1808 if (ProgramStateRef StateTrue = state->assume(*SEV, true)) {
1809 SVal Val = svalBuilder.makeIntVal(1U, Ex->getType());
1810 StateTrue = StateTrue->BindExpr(Ex, Pred->getLocationContext(), Val);
1811 Bldr.generateNode(Ex, Pred, StateTrue, tags.first);
1814 // Next, assume that the condition is false.
1815 if (ProgramStateRef StateFalse = state->assume(*SEV, false)) {
1816 SVal Val = svalBuilder.makeIntVal(0U, Ex->getType());
1817 StateFalse = StateFalse->BindExpr(Ex, Pred->getLocationContext(), Val);
1818 Bldr.generateNode(Ex, Pred, StateFalse, tags.second);
1824 void ExprEngine::VisitGCCAsmStmt(const GCCAsmStmt *A, ExplodedNode *Pred,
1825 ExplodedNodeSet &Dst) {
1826 StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
1827 // We have processed both the inputs and the outputs. All of the outputs
1828 // should evaluate to Locs. Nuke all of their values.
1830 // FIXME: Some day in the future it would be nice to allow a "plug-in"
1831 // which interprets the inline asm and stores proper results in the
1834 ProgramStateRef state = Pred->getState();
1836 for (GCCAsmStmt::const_outputs_iterator OI = A->begin_outputs(),
1837 OE = A->end_outputs(); OI != OE; ++OI) {
1838 SVal X = state->getSVal(*OI, Pred->getLocationContext());
1839 assert (!isa<NonLoc>(X)); // Should be an Lval, or unknown, undef.
1842 state = state->bindLoc(cast<Loc>(X), UnknownVal());
1845 Bldr.generateNode(A, Pred, state);
1848 void ExprEngine::VisitMSAsmStmt(const MSAsmStmt *A, ExplodedNode *Pred,
1849 ExplodedNodeSet &Dst) {
1850 StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
1851 Bldr.generateNode(A, Pred, Pred->getState());
1854 //===----------------------------------------------------------------------===//
1856 //===----------------------------------------------------------------------===//
1859 static ExprEngine* GraphPrintCheckerState;
1860 static SourceManager* GraphPrintSourceManager;
1864 struct DOTGraphTraits<ExplodedNode*> :
1865 public DefaultDOTGraphTraits {
1867 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {}
1869 // FIXME: Since we do not cache error nodes in ExprEngine now, this does not
1871 static std::string getNodeAttributes(const ExplodedNode *N, void*) {
1874 // FIXME: Replace with a general scheme to tell if the node is
1876 if (GraphPrintCheckerState->isImplicitNullDeref(N) ||
1877 GraphPrintCheckerState->isExplicitNullDeref(N) ||
1878 GraphPrintCheckerState->isUndefDeref(N) ||
1879 GraphPrintCheckerState->isUndefStore(N) ||
1880 GraphPrintCheckerState->isUndefControlFlow(N) ||
1881 GraphPrintCheckerState->isUndefResult(N) ||
1882 GraphPrintCheckerState->isBadCall(N) ||
1883 GraphPrintCheckerState->isUndefArg(N))
1884 return "color=\"red\",style=\"filled\"";
1886 if (GraphPrintCheckerState->isNoReturnCall(N))
1887 return "color=\"blue\",style=\"filled\"";
1892 static void printLocation(llvm::raw_ostream &Out, SourceLocation SLoc) {
1893 if (SLoc.isFileID()) {
1895 << GraphPrintSourceManager->getExpansionLineNumber(SLoc)
1897 << GraphPrintSourceManager->getExpansionColumnNumber(SLoc)
1902 static std::string getNodeLabel(const ExplodedNode *N, void*){
1905 llvm::raw_string_ostream Out(sbuf);
1907 // Program Location.
1908 ProgramPoint Loc = N->getLocation();
1910 switch (Loc.getKind()) {
1911 case ProgramPoint::BlockEntranceKind: {
1912 Out << "Block Entrance: B"
1913 << cast<BlockEntrance>(Loc).getBlock()->getBlockID();
1914 if (const NamedDecl *ND =
1915 dyn_cast<NamedDecl>(Loc.getLocationContext()->getDecl())) {
1923 case ProgramPoint::BlockExitKind:
1927 case ProgramPoint::CallEnterKind:
1931 case ProgramPoint::CallExitBeginKind:
1932 Out << "CallExitBegin";
1935 case ProgramPoint::CallExitEndKind:
1936 Out << "CallExitEnd";
1939 case ProgramPoint::PostStmtPurgeDeadSymbolsKind:
1940 Out << "PostStmtPurgeDeadSymbols";
1943 case ProgramPoint::PreStmtPurgeDeadSymbolsKind:
1944 Out << "PreStmtPurgeDeadSymbols";
1947 case ProgramPoint::EpsilonKind:
1948 Out << "Epsilon Point";
1951 case ProgramPoint::PreImplicitCallKind: {
1952 ImplicitCallPoint *PC = cast<ImplicitCallPoint>(&Loc);
1955 // FIXME: Get proper printing options.
1956 PC->getDecl()->print(Out, LangOptions());
1957 printLocation(Out, PC->getLocation());
1961 case ProgramPoint::PostImplicitCallKind: {
1962 ImplicitCallPoint *PC = cast<ImplicitCallPoint>(&Loc);
1963 Out << "PostCall: ";
1965 // FIXME: Get proper printing options.
1966 PC->getDecl()->print(Out, LangOptions());
1967 printLocation(Out, PC->getLocation());
1972 if (StmtPoint *L = dyn_cast<StmtPoint>(&Loc)) {
1973 const Stmt *S = L->getStmt();
1975 Out << S->getStmtClassName() << ' ' << (const void*) S << ' ';
1976 LangOptions LO; // FIXME.
1977 S->printPretty(Out, 0, PrintingPolicy(LO));
1978 printLocation(Out, S->getLocStart());
1980 if (isa<PreStmt>(Loc))
1981 Out << "\\lPreStmt\\l;";
1982 else if (isa<PostLoad>(Loc))
1983 Out << "\\lPostLoad\\l;";
1984 else if (isa<PostStore>(Loc))
1985 Out << "\\lPostStore\\l";
1986 else if (isa<PostLValue>(Loc))
1987 Out << "\\lPostLValue\\l";
1990 // FIXME: Replace with a general scheme to determine
1991 // the name of the check.
1992 if (GraphPrintCheckerState->isImplicitNullDeref(N))
1993 Out << "\\|Implicit-Null Dereference.\\l";
1994 else if (GraphPrintCheckerState->isExplicitNullDeref(N))
1995 Out << "\\|Explicit-Null Dereference.\\l";
1996 else if (GraphPrintCheckerState->isUndefDeref(N))
1997 Out << "\\|Dereference of undefialied value.\\l";
1998 else if (GraphPrintCheckerState->isUndefStore(N))
1999 Out << "\\|Store to Undefined Loc.";
2000 else if (GraphPrintCheckerState->isUndefResult(N))
2001 Out << "\\|Result of operation is undefined.";
2002 else if (GraphPrintCheckerState->isNoReturnCall(N))
2003 Out << "\\|Call to function marked \"noreturn\".";
2004 else if (GraphPrintCheckerState->isBadCall(N))
2005 Out << "\\|Call to NULL/Undefined.";
2006 else if (GraphPrintCheckerState->isUndefArg(N))
2007 Out << "\\|Argument in call is undefined";
2013 const BlockEdge &E = cast<BlockEdge>(Loc);
2014 Out << "Edge: (B" << E.getSrc()->getBlockID() << ", B"
2015 << E.getDst()->getBlockID() << ')';
2017 if (const Stmt *T = E.getSrc()->getTerminator()) {
2019 SourceLocation SLoc = T->getLocStart();
2021 Out << "\\|Terminator: ";
2022 LangOptions LO; // FIXME.
2023 E.getSrc()->printTerminator(Out, LO);
2025 if (SLoc.isFileID()) {
2027 << GraphPrintSourceManager->getExpansionLineNumber(SLoc)
2029 << GraphPrintSourceManager->getExpansionColumnNumber(SLoc);
2032 if (isa<SwitchStmt>(T)) {
2033 const Stmt *Label = E.getDst()->getLabel();
2036 if (const CaseStmt *C = dyn_cast<CaseStmt>(Label)) {
2038 LangOptions LO; // FIXME.
2039 C->getLHS()->printPretty(Out, 0, PrintingPolicy(LO));
2041 if (const Stmt *RHS = C->getRHS()) {
2043 RHS->printPretty(Out, 0, PrintingPolicy(LO));
2049 assert (isa<DefaultStmt>(Label));
2050 Out << "\\ldefault:";
2054 Out << "\\l(implicit) default:";
2056 else if (isa<IndirectGotoStmt>(T)) {
2060 Out << "\\lCondition: ";
2061 if (*E.getSrc()->succ_begin() == E.getDst())
2071 // FIXME: Replace with a general scheme to determine
2072 // the name of the check.
2073 if (GraphPrintCheckerState->isUndefControlFlow(N)) {
2074 Out << "\\|Control-flow based on\\lUndefined value.\\l";
2080 ProgramStateRef state = N->getState();
2081 Out << "\\|StateID: " << (const void*) state.getPtr()
2082 << " NodeID: " << (const void*) N << "\\|";
2083 state->printDOT(Out);
2087 if (const ProgramPointTag *tag = Loc.getTag()) {
2088 Out << "\\|Tag: " << tag->getTagDescription();
2094 } // end llvm namespace
2098 template <typename ITERATOR>
2099 ExplodedNode *GetGraphNode(ITERATOR I) { return *I; }
2101 template <> ExplodedNode*
2102 GetGraphNode<llvm::DenseMap<ExplodedNode*, Expr*>::iterator>
2103 (llvm::DenseMap<ExplodedNode*, Expr*>::iterator I) {
2108 void ExprEngine::ViewGraph(bool trim) {
2111 std::vector<ExplodedNode*> Src;
2113 // Flush any outstanding reports to make sure we cover all the nodes.
2114 // This does not cause them to get displayed.
2115 for (BugReporter::iterator I=BR.begin(), E=BR.end(); I!=E; ++I)
2116 const_cast<BugType*>(*I)->FlushReports(BR);
2118 // Iterate through the reports and get their nodes.
2119 for (BugReporter::EQClasses_iterator
2120 EI = BR.EQClasses_begin(), EE = BR.EQClasses_end(); EI != EE; ++EI) {
2121 ExplodedNode *N = const_cast<ExplodedNode*>(EI->begin()->getErrorNode());
2122 if (N) Src.push_back(N);
2125 ViewGraph(&Src[0], &Src[0]+Src.size());
2128 GraphPrintCheckerState = this;
2129 GraphPrintSourceManager = &getContext().getSourceManager();
2131 llvm::ViewGraph(*G.roots_begin(), "ExprEngine");
2133 GraphPrintCheckerState = NULL;
2134 GraphPrintSourceManager = NULL;
2139 void ExprEngine::ViewGraph(ExplodedNode** Beg, ExplodedNode** End) {
2141 GraphPrintCheckerState = this;
2142 GraphPrintSourceManager = &getContext().getSourceManager();
2144 std::auto_ptr<ExplodedGraph> TrimmedG(G.Trim(Beg, End).first);
2146 if (!TrimmedG.get())
2147 llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n";
2149 llvm::ViewGraph(*TrimmedG->roots_begin(), "TrimmedExprEngine");
2151 GraphPrintCheckerState = NULL;
2152 GraphPrintSourceManager = NULL;