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/PathSensitive/ExprEngine.h"
19 #include "clang/AST/CharUnits.h"
20 #include "clang/AST/ParentMap.h"
21 #include "clang/AST/StmtCXX.h"
22 #include "clang/AST/StmtObjC.h"
23 #include "clang/Basic/Builtins.h"
24 #include "clang/Basic/PrettyStackTrace.h"
25 #include "clang/Basic/SourceManager.h"
26 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
27 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
28 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
29 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
30 #include "llvm/ADT/ImmutableList.h"
31 #include "llvm/ADT/Statistic.h"
32 #include "llvm/Support/raw_ostream.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,
60 InliningModes HowToInlineIn)
62 AnalysisDeclContexts(mgr.getAnalysisDeclContextManager()),
65 StateMgr(getContext(), mgr.getStoreManagerCreator(),
66 mgr.getConstraintManagerCreator(), G.getAllocator(),
68 SymMgr(StateMgr.getSymbolManager()),
69 svalBuilder(StateMgr.getSValBuilder()),
70 currStmtIdx(0), currBldrCtx(0),
71 ObjCNoRet(mgr.getASTContext()),
72 ObjCGCEnabled(gcEnabled), BR(mgr, *this),
73 VisitedCallees(VisitedCalleesIn),
74 HowToInline(HowToInlineIn)
76 unsigned TrimInterval = mgr.options.getGraphTrimInterval();
77 if (TrimInterval != 0) {
78 // Enable eager node reclaimation when constructing the ExplodedGraph.
79 G.enableNodeReclamation(TrimInterval);
83 ExprEngine::~ExprEngine() {
87 //===----------------------------------------------------------------------===//
89 //===----------------------------------------------------------------------===//
91 ProgramStateRef ExprEngine::getInitialState(const LocationContext *InitLoc) {
92 ProgramStateRef state = StateMgr.getInitialState(InitLoc);
93 const Decl *D = InitLoc->getDecl();
96 // FIXME: It would be nice if we had a more general mechanism to add
97 // such preconditions. Some day.
100 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
101 // Precondition: the first argument of 'main' is an integer guaranteed
103 const IdentifierInfo *II = FD->getIdentifier();
104 if (!II || !(II->getName() == "main" && FD->getNumParams() > 0))
107 const ParmVarDecl *PD = FD->getParamDecl(0);
108 QualType T = PD->getType();
109 if (!T->isIntegerType())
112 const MemRegion *R = state->getRegion(PD, InitLoc);
116 SVal V = state->getSVal(loc::MemRegionVal(R));
117 SVal Constraint_untested = evalBinOp(state, BO_GT, V,
118 svalBuilder.makeZeroVal(T),
121 Optional<DefinedOrUnknownSVal> Constraint =
122 Constraint_untested.getAs<DefinedOrUnknownSVal>();
127 if (ProgramStateRef newState = state->assume(*Constraint, true))
134 if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) {
135 // Precondition: 'self' is always non-null upon entry to an Objective-C
137 const ImplicitParamDecl *SelfD = MD->getSelfDecl();
138 const MemRegion *R = state->getRegion(SelfD, InitLoc);
139 SVal V = state->getSVal(loc::MemRegionVal(R));
141 if (Optional<Loc> LV = V.getAs<Loc>()) {
142 // Assume that the pointer value in 'self' is non-null.
143 state = state->assume(*LV, true);
144 assert(state && "'self' cannot be null");
148 if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(D)) {
149 if (!MD->isStatic()) {
150 // Precondition: 'this' is always non-null upon entry to the
151 // top-level function. This is our starting assumption for
152 // analyzing an "open" program.
153 const StackFrameContext *SFC = InitLoc->getCurrentStackFrame();
154 if (SFC->getParent() == 0) {
155 loc::MemRegionVal L = svalBuilder.getCXXThis(MD, SFC);
156 SVal V = state->getSVal(L);
157 if (Optional<Loc> LV = V.getAs<Loc>()) {
158 state = state->assume(*LV, true);
159 assert(state && "'this' cannot be null");
169 ExprEngine::createTemporaryRegionIfNeeded(ProgramStateRef State,
170 const LocationContext *LC,
172 const Expr *Result) {
173 SVal V = State->getSVal(Ex, LC);
175 // If we don't have an explicit result expression, we're in "if needed"
176 // mode. Only create a region if the current value is a NonLoc.
177 if (!V.getAs<NonLoc>())
181 // We need to create a region no matter what. For sanity, make sure we don't
182 // try to stuff a Loc into a non-pointer temporary region.
183 assert(!V.getAs<Loc>() || Loc::isLocType(Result->getType()));
186 ProgramStateManager &StateMgr = State->getStateManager();
187 MemRegionManager &MRMgr = StateMgr.getRegionManager();
188 StoreManager &StoreMgr = StateMgr.getStoreManager();
190 // We need to be careful about treating a derived type's value as
191 // bindings for a base type. Unless we're creating a temporary pointer region,
192 // start by stripping and recording base casts.
193 SmallVector<const CastExpr *, 4> Casts;
194 const Expr *Inner = Ex->IgnoreParens();
195 if (!Loc::isLocType(Result->getType())) {
196 while (const CastExpr *CE = dyn_cast<CastExpr>(Inner)) {
197 if (CE->getCastKind() == CK_DerivedToBase ||
198 CE->getCastKind() == CK_UncheckedDerivedToBase)
200 else if (CE->getCastKind() != CK_NoOp)
203 Inner = CE->getSubExpr()->IgnoreParens();
207 // Create a temporary object region for the inner expression (which may have
208 // a more derived type) and bind the value into it.
209 const TypedValueRegion *TR = MRMgr.getCXXTempObjectRegion(Inner, LC);
210 SVal Reg = loc::MemRegionVal(TR);
213 V = getSValBuilder().conjureSymbolVal(Result, LC, TR->getValueType(),
214 currBldrCtx->blockCount());
215 State = State->bindLoc(Reg, V);
217 // Re-apply the casts (from innermost to outermost) for type sanity.
218 for (SmallVectorImpl<const CastExpr *>::reverse_iterator I = Casts.rbegin(),
221 Reg = StoreMgr.evalDerivedToBase(Reg, *I);
224 State = State->BindExpr(Result, LC, Reg);
228 //===----------------------------------------------------------------------===//
229 // Top-level transfer function logic (Dispatcher).
230 //===----------------------------------------------------------------------===//
232 /// evalAssume - Called by ConstraintManager. Used to call checker-specific
233 /// logic for handling assumptions on symbolic values.
234 ProgramStateRef ExprEngine::processAssume(ProgramStateRef state,
235 SVal cond, bool assumption) {
236 return getCheckerManager().runCheckersForEvalAssume(state, cond, assumption);
239 bool ExprEngine::wantsRegionChangeUpdate(ProgramStateRef state) {
240 return getCheckerManager().wantsRegionChangeUpdate(state);
244 ExprEngine::processRegionChanges(ProgramStateRef state,
245 const InvalidatedSymbols *invalidated,
246 ArrayRef<const MemRegion *> Explicits,
247 ArrayRef<const MemRegion *> Regions,
248 const CallEvent *Call) {
249 return getCheckerManager().runCheckersForRegionChanges(state, invalidated,
250 Explicits, Regions, Call);
253 void ExprEngine::printState(raw_ostream &Out, ProgramStateRef State,
254 const char *NL, const char *Sep) {
255 getCheckerManager().runCheckersForPrintState(Out, State, NL, Sep);
258 void ExprEngine::processEndWorklist(bool hasWorkRemaining) {
259 getCheckerManager().runCheckersForEndAnalysis(G, BR, *this);
262 void ExprEngine::processCFGElement(const CFGElement E, ExplodedNode *Pred,
263 unsigned StmtIdx, NodeBuilderContext *Ctx) {
264 currStmtIdx = StmtIdx;
267 switch (E.getKind()) {
268 case CFGElement::Statement:
269 ProcessStmt(const_cast<Stmt*>(E.castAs<CFGStmt>().getStmt()), Pred);
271 case CFGElement::Initializer:
272 ProcessInitializer(E.castAs<CFGInitializer>().getInitializer(), Pred);
274 case CFGElement::AutomaticObjectDtor:
275 case CFGElement::BaseDtor:
276 case CFGElement::MemberDtor:
277 case CFGElement::TemporaryDtor:
278 ProcessImplicitDtor(E.castAs<CFGImplicitDtor>(), Pred);
284 static bool shouldRemoveDeadBindings(AnalysisManager &AMgr,
286 const ExplodedNode *Pred,
287 const LocationContext *LC) {
289 // Are we never purging state values?
290 if (AMgr.options.AnalysisPurgeOpt == PurgeNone)
293 // Is this the beginning of a basic block?
294 if (Pred->getLocation().getAs<BlockEntrance>())
297 // Is this on a non-expression?
298 if (!isa<Expr>(S.getStmt()))
301 // Run before processing a call.
302 if (CallEvent::isCallStmt(S.getStmt()))
305 // Is this an expression that is consumed by another expression? If so,
306 // postpone cleaning out the state.
307 ParentMap &PM = LC->getAnalysisDeclContext()->getParentMap();
308 return !PM.isConsumedExpr(cast<Expr>(S.getStmt()));
311 void ExprEngine::removeDead(ExplodedNode *Pred, ExplodedNodeSet &Out,
312 const Stmt *ReferenceStmt,
313 const LocationContext *LC,
314 const Stmt *DiagnosticStmt,
315 ProgramPoint::Kind K) {
316 assert((K == ProgramPoint::PreStmtPurgeDeadSymbolsKind ||
317 ReferenceStmt == 0 || isa<ReturnStmt>(ReferenceStmt))
318 && "PostStmt is not generally supported by the SymbolReaper yet");
319 assert(LC && "Must pass the current (or expiring) LocationContext");
321 if (!DiagnosticStmt) {
322 DiagnosticStmt = ReferenceStmt;
323 assert(DiagnosticStmt && "Required for clearing a LocationContext");
326 NumRemoveDeadBindings++;
327 ProgramStateRef CleanedState = Pred->getState();
329 // LC is the location context being destroyed, but SymbolReaper wants a
330 // location context that is still live. (If this is the top-level stack
331 // frame, this will be null.)
332 if (!ReferenceStmt) {
333 assert(K == ProgramPoint::PostStmtPurgeDeadSymbolsKind &&
334 "Use PostStmtPurgeDeadSymbolsKind for clearing a LocationContext");
335 LC = LC->getParent();
338 const StackFrameContext *SFC = LC ? LC->getCurrentStackFrame() : 0;
339 SymbolReaper SymReaper(SFC, ReferenceStmt, SymMgr, getStoreManager());
341 getCheckerManager().runCheckersForLiveSymbols(CleanedState, SymReaper);
343 // Create a state in which dead bindings are removed from the environment
344 // and the store. TODO: The function should just return new env and store,
346 CleanedState = StateMgr.removeDeadBindings(CleanedState, SFC, SymReaper);
348 // Process any special transfer function for dead symbols.
349 // A tag to track convenience transitions, which can be removed at cleanup.
350 static SimpleProgramPointTag cleanupTag("ExprEngine : Clean Node");
351 if (!SymReaper.hasDeadSymbols()) {
352 // Generate a CleanedNode that has the environment and store cleaned
353 // up. Since no symbols are dead, we can optimize and not clean out
354 // the constraint manager.
355 StmtNodeBuilder Bldr(Pred, Out, *currBldrCtx);
356 Bldr.generateNode(DiagnosticStmt, Pred, CleanedState, &cleanupTag, K);
359 // Call checkers with the non-cleaned state so that they could query the
360 // values of the soon to be dead symbols.
361 ExplodedNodeSet CheckedSet;
362 getCheckerManager().runCheckersForDeadSymbols(CheckedSet, Pred, SymReaper,
363 DiagnosticStmt, *this, K);
365 // For each node in CheckedSet, generate CleanedNodes that have the
366 // environment, the store, and the constraints cleaned up but have the
367 // user-supplied states as the predecessors.
368 StmtNodeBuilder Bldr(CheckedSet, Out, *currBldrCtx);
369 for (ExplodedNodeSet::const_iterator
370 I = CheckedSet.begin(), E = CheckedSet.end(); I != E; ++I) {
371 ProgramStateRef CheckerState = (*I)->getState();
373 // The constraint manager has not been cleaned up yet, so clean up now.
374 CheckerState = getConstraintManager().removeDeadBindings(CheckerState,
377 assert(StateMgr.haveEqualEnvironments(CheckerState, Pred->getState()) &&
378 "Checkers are not allowed to modify the Environment as a part of "
379 "checkDeadSymbols processing.");
380 assert(StateMgr.haveEqualStores(CheckerState, Pred->getState()) &&
381 "Checkers are not allowed to modify the Store as a part of "
382 "checkDeadSymbols processing.");
384 // Create a state based on CleanedState with CheckerState GDM and
385 // generate a transition to that state.
386 ProgramStateRef CleanedCheckerSt =
387 StateMgr.getPersistentStateWithGDM(CleanedState, CheckerState);
388 Bldr.generateNode(DiagnosticStmt, *I, CleanedCheckerSt, &cleanupTag, K);
393 void ExprEngine::ProcessStmt(const CFGStmt S,
394 ExplodedNode *Pred) {
395 // Reclaim any unnecessary nodes in the ExplodedGraph.
396 G.reclaimRecentlyAllocatedNodes();
398 const Stmt *currStmt = S.getStmt();
399 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
400 currStmt->getLocStart(),
401 "Error evaluating statement");
403 // Remove dead bindings and symbols.
404 ExplodedNodeSet CleanedStates;
405 if (shouldRemoveDeadBindings(AMgr, S, Pred, Pred->getLocationContext())){
406 removeDead(Pred, CleanedStates, currStmt, Pred->getLocationContext());
408 CleanedStates.Add(Pred);
410 // Visit the statement.
412 for (ExplodedNodeSet::iterator I = CleanedStates.begin(),
413 E = CleanedStates.end(); I != E; ++I) {
414 ExplodedNodeSet DstI;
415 // Visit the statement.
416 Visit(currStmt, *I, DstI);
420 // Enqueue the new nodes onto the work list.
421 Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
424 void ExprEngine::ProcessInitializer(const CFGInitializer Init,
425 ExplodedNode *Pred) {
426 const CXXCtorInitializer *BMI = Init.getInitializer();
428 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
429 BMI->getSourceLocation(),
430 "Error evaluating initializer");
432 // We don't clean up dead bindings here.
433 const StackFrameContext *stackFrame =
434 cast<StackFrameContext>(Pred->getLocationContext());
435 const CXXConstructorDecl *decl =
436 cast<CXXConstructorDecl>(stackFrame->getDecl());
438 ProgramStateRef State = Pred->getState();
439 SVal thisVal = State->getSVal(svalBuilder.getCXXThis(decl, stackFrame));
441 ExplodedNodeSet Tmp(Pred);
444 // Evaluate the initializer, if necessary
445 if (BMI->isAnyMemberInitializer()) {
446 // Constructors build the object directly in the field,
447 // but non-objects must be copied in from the initializer.
448 const Expr *Init = BMI->getInit()->IgnoreImplicit();
449 if (!isa<CXXConstructExpr>(Init)) {
450 const ValueDecl *Field;
451 if (BMI->isIndirectMemberInitializer()) {
452 Field = BMI->getIndirectMember();
453 FieldLoc = State->getLValue(BMI->getIndirectMember(), thisVal);
455 Field = BMI->getMember();
456 FieldLoc = State->getLValue(BMI->getMember(), thisVal);
460 if (BMI->getNumArrayIndices() > 0) {
461 // Handle arrays of trivial type. We can represent this with a
462 // primitive load/copy from the base array region.
463 const ArraySubscriptExpr *ASE;
464 while ((ASE = dyn_cast<ArraySubscriptExpr>(Init)))
465 Init = ASE->getBase()->IgnoreImplicit();
467 SVal LValue = State->getSVal(Init, stackFrame);
468 if (Optional<Loc> LValueLoc = LValue.getAs<Loc>())
469 InitVal = State->getSVal(*LValueLoc);
471 // If we fail to get the value for some reason, use a symbolic value.
472 if (InitVal.isUnknownOrUndef()) {
473 SValBuilder &SVB = getSValBuilder();
474 InitVal = SVB.conjureSymbolVal(BMI->getInit(), stackFrame,
476 currBldrCtx->blockCount());
479 InitVal = State->getSVal(BMI->getInit(), stackFrame);
482 assert(Tmp.size() == 1 && "have not generated any new nodes yet");
483 assert(*Tmp.begin() == Pred && "have not generated any new nodes yet");
486 PostInitializer PP(BMI, FieldLoc.getAsRegion(), stackFrame);
487 evalBind(Tmp, Init, Pred, FieldLoc, InitVal, /*isInit=*/true, &PP);
490 assert(BMI->isBaseInitializer() || BMI->isDelegatingInitializer());
491 // We already did all the work when visiting the CXXConstructExpr.
494 // Construct PostInitializer nodes whether the state changed or not,
495 // so that the diagnostics don't get confused.
496 PostInitializer PP(BMI, FieldLoc.getAsRegion(), stackFrame);
498 NodeBuilder Bldr(Tmp, Dst, *currBldrCtx);
499 for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I != E; ++I) {
500 ExplodedNode *N = *I;
501 Bldr.generateNode(PP, N->getState(), N);
504 // Enqueue the new nodes onto the work list.
505 Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
508 void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D,
509 ExplodedNode *Pred) {
511 switch (D.getKind()) {
512 case CFGElement::AutomaticObjectDtor:
513 ProcessAutomaticObjDtor(D.castAs<CFGAutomaticObjDtor>(), Pred, Dst);
515 case CFGElement::BaseDtor:
516 ProcessBaseDtor(D.castAs<CFGBaseDtor>(), Pred, Dst);
518 case CFGElement::MemberDtor:
519 ProcessMemberDtor(D.castAs<CFGMemberDtor>(), Pred, Dst);
521 case CFGElement::TemporaryDtor:
522 ProcessTemporaryDtor(D.castAs<CFGTemporaryDtor>(), Pred, Dst);
525 llvm_unreachable("Unexpected dtor kind.");
528 // Enqueue the new nodes onto the work list.
529 Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
532 void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor Dtor,
534 ExplodedNodeSet &Dst) {
535 const VarDecl *varDecl = Dtor.getVarDecl();
536 QualType varType = varDecl->getType();
538 ProgramStateRef state = Pred->getState();
539 SVal dest = state->getLValue(varDecl, Pred->getLocationContext());
540 const MemRegion *Region = dest.castAs<loc::MemRegionVal>().getRegion();
542 if (const ReferenceType *refType = varType->getAs<ReferenceType>()) {
543 varType = refType->getPointeeType();
544 Region = state->getSVal(Region).getAsRegion();
547 VisitCXXDestructor(varType, Region, Dtor.getTriggerStmt(), /*IsBase=*/ false,
551 void ExprEngine::ProcessBaseDtor(const CFGBaseDtor D,
552 ExplodedNode *Pred, ExplodedNodeSet &Dst) {
553 const LocationContext *LCtx = Pred->getLocationContext();
554 ProgramStateRef State = Pred->getState();
556 const CXXDestructorDecl *CurDtor = cast<CXXDestructorDecl>(LCtx->getDecl());
557 Loc ThisPtr = getSValBuilder().getCXXThis(CurDtor,
558 LCtx->getCurrentStackFrame());
559 SVal ThisVal = Pred->getState()->getSVal(ThisPtr);
561 // Create the base object region.
562 const CXXBaseSpecifier *Base = D.getBaseSpecifier();
563 QualType BaseTy = Base->getType();
564 SVal BaseVal = getStoreManager().evalDerivedToBase(ThisVal, BaseTy,
567 VisitCXXDestructor(BaseTy, BaseVal.castAs<loc::MemRegionVal>().getRegion(),
568 CurDtor->getBody(), /*IsBase=*/ true, Pred, Dst);
571 void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D,
572 ExplodedNode *Pred, ExplodedNodeSet &Dst) {
573 const FieldDecl *Member = D.getFieldDecl();
574 ProgramStateRef State = Pred->getState();
575 const LocationContext *LCtx = Pred->getLocationContext();
577 const CXXDestructorDecl *CurDtor = cast<CXXDestructorDecl>(LCtx->getDecl());
578 Loc ThisVal = getSValBuilder().getCXXThis(CurDtor,
579 LCtx->getCurrentStackFrame());
581 State->getLValue(Member, State->getSVal(ThisVal).castAs<Loc>());
583 VisitCXXDestructor(Member->getType(),
584 FieldVal.castAs<loc::MemRegionVal>().getRegion(),
585 CurDtor->getBody(), /*IsBase=*/false, Pred, Dst);
588 void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D,
590 ExplodedNodeSet &Dst) {}
592 void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred,
593 ExplodedNodeSet &DstTop) {
594 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
596 "Error evaluating statement");
598 StmtNodeBuilder Bldr(Pred, DstTop, *currBldrCtx);
600 assert(!isa<Expr>(S) || S == cast<Expr>(S)->IgnoreParens());
602 switch (S->getStmtClass()) {
603 // C++ and ARC stuff we don't support yet.
604 case Expr::ObjCIndirectCopyRestoreExprClass:
605 case Stmt::CXXDependentScopeMemberExprClass:
606 case Stmt::CXXPseudoDestructorExprClass:
607 case Stmt::CXXTryStmtClass:
608 case Stmt::CXXTypeidExprClass:
609 case Stmt::CXXUuidofExprClass:
610 case Stmt::CXXUnresolvedConstructExprClass:
611 case Stmt::DependentScopeDeclRefExprClass:
612 case Stmt::UnaryTypeTraitExprClass:
613 case Stmt::BinaryTypeTraitExprClass:
614 case Stmt::TypeTraitExprClass:
615 case Stmt::ArrayTypeTraitExprClass:
616 case Stmt::ExpressionTraitExprClass:
617 case Stmt::UnresolvedLookupExprClass:
618 case Stmt::UnresolvedMemberExprClass:
619 case Stmt::CXXNoexceptExprClass:
620 case Stmt::PackExpansionExprClass:
621 case Stmt::SubstNonTypeTemplateParmPackExprClass:
622 case Stmt::FunctionParmPackExprClass:
623 case Stmt::SEHTryStmtClass:
624 case Stmt::SEHExceptStmtClass:
625 case Stmt::LambdaExprClass:
626 case Stmt::SEHFinallyStmtClass: {
627 const ExplodedNode *node = Bldr.generateSink(S, Pred, Pred->getState());
628 Engine.addAbortedBlock(node, currBldrCtx->getBlock());
632 case Stmt::ParenExprClass:
633 llvm_unreachable("ParenExprs already handled.");
634 case Stmt::GenericSelectionExprClass:
635 llvm_unreachable("GenericSelectionExprs already handled.");
636 // Cases that should never be evaluated simply because they shouldn't
637 // appear in the CFG.
638 case Stmt::BreakStmtClass:
639 case Stmt::CaseStmtClass:
640 case Stmt::CompoundStmtClass:
641 case Stmt::ContinueStmtClass:
642 case Stmt::CXXForRangeStmtClass:
643 case Stmt::DefaultStmtClass:
644 case Stmt::DoStmtClass:
645 case Stmt::ForStmtClass:
646 case Stmt::GotoStmtClass:
647 case Stmt::IfStmtClass:
648 case Stmt::IndirectGotoStmtClass:
649 case Stmt::LabelStmtClass:
650 case Stmt::AttributedStmtClass:
651 case Stmt::NoStmtClass:
652 case Stmt::NullStmtClass:
653 case Stmt::SwitchStmtClass:
654 case Stmt::WhileStmtClass:
655 case Expr::MSDependentExistsStmtClass:
656 llvm_unreachable("Stmt should not be in analyzer evaluation loop");
658 case Stmt::ObjCSubscriptRefExprClass:
659 case Stmt::ObjCPropertyRefExprClass:
660 llvm_unreachable("These are handled by PseudoObjectExpr");
662 case Stmt::GNUNullExprClass: {
663 // GNU __null is a pointer-width integer, not an actual pointer.
664 ProgramStateRef state = Pred->getState();
665 state = state->BindExpr(S, Pred->getLocationContext(),
666 svalBuilder.makeIntValWithPtrWidth(0, false));
667 Bldr.generateNode(S, Pred, state);
671 case Stmt::ObjCAtSynchronizedStmtClass:
672 Bldr.takeNodes(Pred);
673 VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S), Pred, Dst);
677 case Stmt::ExprWithCleanupsClass:
678 // Handled due to fully linearised CFG.
681 // Cases not handled yet; but will handle some day.
682 case Stmt::DesignatedInitExprClass:
683 case Stmt::ExtVectorElementExprClass:
684 case Stmt::ImaginaryLiteralClass:
685 case Stmt::ObjCAtCatchStmtClass:
686 case Stmt::ObjCAtFinallyStmtClass:
687 case Stmt::ObjCAtTryStmtClass:
688 case Stmt::ObjCAutoreleasePoolStmtClass:
689 case Stmt::ObjCEncodeExprClass:
690 case Stmt::ObjCIsaExprClass:
691 case Stmt::ObjCProtocolExprClass:
692 case Stmt::ObjCSelectorExprClass:
693 case Stmt::ParenListExprClass:
694 case Stmt::PredefinedExprClass:
695 case Stmt::ShuffleVectorExprClass:
696 case Stmt::VAArgExprClass:
697 case Stmt::CUDAKernelCallExprClass:
698 case Stmt::OpaqueValueExprClass:
699 case Stmt::AsTypeExprClass:
700 case Stmt::AtomicExprClass:
703 // Cases we intentionally don't evaluate, since they don't need
704 // to be explicitly evaluated.
705 case Stmt::AddrLabelExprClass:
706 case Stmt::IntegerLiteralClass:
707 case Stmt::CharacterLiteralClass:
708 case Stmt::ImplicitValueInitExprClass:
709 case Stmt::CXXScalarValueInitExprClass:
710 case Stmt::CXXBoolLiteralExprClass:
711 case Stmt::ObjCBoolLiteralExprClass:
712 case Stmt::FloatingLiteralClass:
713 case Stmt::SizeOfPackExprClass:
714 case Stmt::StringLiteralClass:
715 case Stmt::ObjCStringLiteralClass:
716 case Stmt::CXXBindTemporaryExprClass:
717 case Stmt::SubstNonTypeTemplateParmExprClass:
718 case Stmt::CXXNullPtrLiteralExprClass: {
719 Bldr.takeNodes(Pred);
720 ExplodedNodeSet preVisit;
721 getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this);
722 getCheckerManager().runCheckersForPostStmt(Dst, preVisit, S, *this);
727 case Stmt::CXXDefaultArgExprClass: {
728 Bldr.takeNodes(Pred);
729 ExplodedNodeSet PreVisit;
730 getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
733 StmtNodeBuilder Bldr2(PreVisit, Tmp, *currBldrCtx);
735 const LocationContext *LCtx = Pred->getLocationContext();
736 const CXXDefaultArgExpr *DefaultE = cast<CXXDefaultArgExpr>(S);
737 const Expr *ArgE = DefaultE->getExpr();
739 // Avoid creating and destroying a lot of APSInts.
743 for (ExplodedNodeSet::iterator I = PreVisit.begin(), E = PreVisit.end();
745 ProgramStateRef State = (*I)->getState();
747 if (ArgE->EvaluateAsInt(Result, getContext()))
748 V = svalBuilder.makeIntVal(Result);
750 V = State->getSVal(ArgE, LCtx);
752 State = State->BindExpr(DefaultE, LCtx, V);
753 if (DefaultE->isGLValue())
754 State = createTemporaryRegionIfNeeded(State, LCtx, DefaultE,
756 Bldr2.generateNode(S, *I, State);
759 getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this);
764 case Expr::ObjCArrayLiteralClass:
765 case Expr::ObjCDictionaryLiteralClass:
766 // FIXME: explicitly model with a region and the actual contents
767 // of the container. For now, conjure a symbol.
768 case Expr::ObjCBoxedExprClass: {
769 Bldr.takeNodes(Pred);
771 ExplodedNodeSet preVisit;
772 getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this);
775 StmtNodeBuilder Bldr2(preVisit, Tmp, *currBldrCtx);
777 const Expr *Ex = cast<Expr>(S);
778 QualType resultType = Ex->getType();
780 for (ExplodedNodeSet::iterator it = preVisit.begin(), et = preVisit.end();
782 ExplodedNode *N = *it;
783 const LocationContext *LCtx = N->getLocationContext();
784 SVal result = svalBuilder.conjureSymbolVal(0, Ex, LCtx, resultType,
785 currBldrCtx->blockCount());
786 ProgramStateRef state = N->getState()->BindExpr(Ex, LCtx, result);
787 Bldr2.generateNode(S, N, state);
790 getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this);
795 case Stmt::ArraySubscriptExprClass:
796 Bldr.takeNodes(Pred);
797 VisitLvalArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Pred, Dst);
801 case Stmt::GCCAsmStmtClass:
802 Bldr.takeNodes(Pred);
803 VisitGCCAsmStmt(cast<GCCAsmStmt>(S), Pred, Dst);
807 case Stmt::MSAsmStmtClass:
808 Bldr.takeNodes(Pred);
809 VisitMSAsmStmt(cast<MSAsmStmt>(S), Pred, Dst);
813 case Stmt::BlockExprClass:
814 Bldr.takeNodes(Pred);
815 VisitBlockExpr(cast<BlockExpr>(S), Pred, Dst);
819 case Stmt::BinaryOperatorClass: {
820 const BinaryOperator* B = cast<BinaryOperator>(S);
821 if (B->isLogicalOp()) {
822 Bldr.takeNodes(Pred);
823 VisitLogicalExpr(B, Pred, Dst);
827 else if (B->getOpcode() == BO_Comma) {
828 ProgramStateRef state = Pred->getState();
829 Bldr.generateNode(B, Pred,
830 state->BindExpr(B, Pred->getLocationContext(),
831 state->getSVal(B->getRHS(),
832 Pred->getLocationContext())));
836 Bldr.takeNodes(Pred);
838 if (AMgr.options.eagerlyAssumeBinOpBifurcation &&
839 (B->isRelationalOp() || B->isEqualityOp())) {
841 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Tmp);
842 evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, cast<Expr>(S));
845 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
851 case Stmt::CXXOperatorCallExprClass: {
852 const CXXOperatorCallExpr *OCE = cast<CXXOperatorCallExpr>(S);
854 // For instance method operators, make sure the 'this' argument has a
856 const Decl *Callee = OCE->getCalleeDecl();
857 if (const CXXMethodDecl *MD = dyn_cast_or_null<CXXMethodDecl>(Callee)) {
858 if (MD->isInstance()) {
859 ProgramStateRef State = Pred->getState();
860 const LocationContext *LCtx = Pred->getLocationContext();
861 ProgramStateRef NewState =
862 createTemporaryRegionIfNeeded(State, LCtx, OCE->getArg(0));
863 if (NewState != State)
864 Pred = Bldr.generateNode(OCE, Pred, NewState, /*Tag=*/0,
865 ProgramPoint::PreStmtKind);
870 case Stmt::CallExprClass:
871 case Stmt::CXXMemberCallExprClass:
872 case Stmt::UserDefinedLiteralClass: {
873 Bldr.takeNodes(Pred);
874 VisitCallExpr(cast<CallExpr>(S), Pred, Dst);
879 case Stmt::CXXCatchStmtClass: {
880 Bldr.takeNodes(Pred);
881 VisitCXXCatchStmt(cast<CXXCatchStmt>(S), Pred, Dst);
886 case Stmt::CXXTemporaryObjectExprClass:
887 case Stmt::CXXConstructExprClass: {
888 Bldr.takeNodes(Pred);
889 VisitCXXConstructExpr(cast<CXXConstructExpr>(S), Pred, Dst);
894 case Stmt::CXXNewExprClass: {
895 Bldr.takeNodes(Pred);
896 ExplodedNodeSet PostVisit;
897 VisitCXXNewExpr(cast<CXXNewExpr>(S), Pred, PostVisit);
898 getCheckerManager().runCheckersForPostStmt(Dst, PostVisit, S, *this);
903 case Stmt::CXXDeleteExprClass: {
904 Bldr.takeNodes(Pred);
905 ExplodedNodeSet PreVisit;
906 const CXXDeleteExpr *CDE = cast<CXXDeleteExpr>(S);
907 getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
909 for (ExplodedNodeSet::iterator i = PreVisit.begin(),
910 e = PreVisit.end(); i != e ; ++i)
911 VisitCXXDeleteExpr(CDE, *i, Dst);
916 // FIXME: ChooseExpr is really a constant. We need to fix
917 // the CFG do not model them as explicit control-flow.
919 case Stmt::ChooseExprClass: { // __builtin_choose_expr
920 Bldr.takeNodes(Pred);
921 const ChooseExpr *C = cast<ChooseExpr>(S);
922 VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst);
927 case Stmt::CompoundAssignOperatorClass:
928 Bldr.takeNodes(Pred);
929 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
933 case Stmt::CompoundLiteralExprClass:
934 Bldr.takeNodes(Pred);
935 VisitCompoundLiteralExpr(cast<CompoundLiteralExpr>(S), Pred, Dst);
939 case Stmt::BinaryConditionalOperatorClass:
940 case Stmt::ConditionalOperatorClass: { // '?' operator
941 Bldr.takeNodes(Pred);
942 const AbstractConditionalOperator *C
943 = cast<AbstractConditionalOperator>(S);
944 VisitGuardedExpr(C, C->getTrueExpr(), C->getFalseExpr(), Pred, Dst);
949 case Stmt::CXXThisExprClass:
950 Bldr.takeNodes(Pred);
951 VisitCXXThisExpr(cast<CXXThisExpr>(S), Pred, Dst);
955 case Stmt::DeclRefExprClass: {
956 Bldr.takeNodes(Pred);
957 const DeclRefExpr *DE = cast<DeclRefExpr>(S);
958 VisitCommonDeclRefExpr(DE, DE->getDecl(), Pred, Dst);
963 case Stmt::DeclStmtClass:
964 Bldr.takeNodes(Pred);
965 VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst);
969 case Stmt::ImplicitCastExprClass:
970 case Stmt::CStyleCastExprClass:
971 case Stmt::CXXStaticCastExprClass:
972 case Stmt::CXXDynamicCastExprClass:
973 case Stmt::CXXReinterpretCastExprClass:
974 case Stmt::CXXConstCastExprClass:
975 case Stmt::CXXFunctionalCastExprClass:
976 case Stmt::ObjCBridgedCastExprClass: {
977 Bldr.takeNodes(Pred);
978 const CastExpr *C = cast<CastExpr>(S);
979 // Handle the previsit checks.
980 ExplodedNodeSet dstPrevisit;
981 getCheckerManager().runCheckersForPreStmt(dstPrevisit, Pred, C, *this);
983 // Handle the expression itself.
984 ExplodedNodeSet dstExpr;
985 for (ExplodedNodeSet::iterator i = dstPrevisit.begin(),
986 e = dstPrevisit.end(); i != e ; ++i) {
987 VisitCast(C, C->getSubExpr(), *i, dstExpr);
990 // Handle the postvisit checks.
991 getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, C, *this);
996 case Expr::MaterializeTemporaryExprClass: {
997 Bldr.takeNodes(Pred);
998 const MaterializeTemporaryExpr *MTE = cast<MaterializeTemporaryExpr>(S);
999 CreateCXXTemporaryObject(MTE, Pred, Dst);
1004 case Stmt::InitListExprClass:
1005 Bldr.takeNodes(Pred);
1006 VisitInitListExpr(cast<InitListExpr>(S), Pred, Dst);
1010 case Stmt::MemberExprClass:
1011 Bldr.takeNodes(Pred);
1012 VisitMemberExpr(cast<MemberExpr>(S), Pred, Dst);
1016 case Stmt::ObjCIvarRefExprClass:
1017 Bldr.takeNodes(Pred);
1018 VisitLvalObjCIvarRefExpr(cast<ObjCIvarRefExpr>(S), Pred, Dst);
1022 case Stmt::ObjCForCollectionStmtClass:
1023 Bldr.takeNodes(Pred);
1024 VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S), Pred, Dst);
1028 case Stmt::ObjCMessageExprClass:
1029 Bldr.takeNodes(Pred);
1030 VisitObjCMessage(cast<ObjCMessageExpr>(S), Pred, Dst);
1034 case Stmt::ObjCAtThrowStmtClass:
1035 case Stmt::CXXThrowExprClass:
1036 // FIXME: This is not complete. We basically treat @throw as
1038 Bldr.generateSink(S, Pred, Pred->getState());
1041 case Stmt::ReturnStmtClass:
1042 Bldr.takeNodes(Pred);
1043 VisitReturnStmt(cast<ReturnStmt>(S), Pred, Dst);
1047 case Stmt::OffsetOfExprClass:
1048 Bldr.takeNodes(Pred);
1049 VisitOffsetOfExpr(cast<OffsetOfExpr>(S), Pred, Dst);
1053 case Stmt::UnaryExprOrTypeTraitExprClass:
1054 Bldr.takeNodes(Pred);
1055 VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S),
1060 case Stmt::StmtExprClass: {
1061 const StmtExpr *SE = cast<StmtExpr>(S);
1063 if (SE->getSubStmt()->body_empty()) {
1064 // Empty statement expression.
1065 assert(SE->getType() == getContext().VoidTy
1066 && "Empty statement expression must have void type.");
1070 if (Expr *LastExpr = dyn_cast<Expr>(*SE->getSubStmt()->body_rbegin())) {
1071 ProgramStateRef state = Pred->getState();
1072 Bldr.generateNode(SE, Pred,
1073 state->BindExpr(SE, Pred->getLocationContext(),
1074 state->getSVal(LastExpr,
1075 Pred->getLocationContext())));
1080 case Stmt::UnaryOperatorClass: {
1081 Bldr.takeNodes(Pred);
1082 const UnaryOperator *U = cast<UnaryOperator>(S);
1083 if (AMgr.options.eagerlyAssumeBinOpBifurcation && (U->getOpcode() == UO_LNot)) {
1084 ExplodedNodeSet Tmp;
1085 VisitUnaryOperator(U, Pred, Tmp);
1086 evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, U);
1089 VisitUnaryOperator(U, Pred, Dst);
1094 case Stmt::PseudoObjectExprClass: {
1095 Bldr.takeNodes(Pred);
1096 ProgramStateRef state = Pred->getState();
1097 const PseudoObjectExpr *PE = cast<PseudoObjectExpr>(S);
1098 if (const Expr *Result = PE->getResultExpr()) {
1099 SVal V = state->getSVal(Result, Pred->getLocationContext());
1100 Bldr.generateNode(S, Pred,
1101 state->BindExpr(S, Pred->getLocationContext(), V));
1104 Bldr.generateNode(S, Pred,
1105 state->BindExpr(S, Pred->getLocationContext(),
1114 bool ExprEngine::replayWithoutInlining(ExplodedNode *N,
1115 const LocationContext *CalleeLC) {
1116 const StackFrameContext *CalleeSF = CalleeLC->getCurrentStackFrame();
1117 const StackFrameContext *CallerSF = CalleeSF->getParent()->getCurrentStackFrame();
1118 assert(CalleeSF && CallerSF);
1119 ExplodedNode *BeforeProcessingCall = 0;
1120 const Stmt *CE = CalleeSF->getCallSite();
1122 // Find the first node before we started processing the call expression.
1124 ProgramPoint L = N->getLocation();
1125 BeforeProcessingCall = N;
1126 N = N->pred_empty() ? NULL : *(N->pred_begin());
1128 // Skip the nodes corresponding to the inlined code.
1129 if (L.getLocationContext()->getCurrentStackFrame() != CallerSF)
1131 // We reached the caller. Find the node right before we started
1132 // processing the call.
1133 if (L.isPurgeKind())
1135 if (L.getAs<PreImplicitCall>())
1137 if (L.getAs<CallEnter>())
1139 if (Optional<StmtPoint> SP = L.getAs<StmtPoint>())
1140 if (SP->getStmt() == CE)
1145 if (!BeforeProcessingCall)
1148 // TODO: Clean up the unneeded nodes.
1150 // Build an Epsilon node from which we will restart the analyzes.
1151 // Note that CE is permitted to be NULL!
1152 ProgramPoint NewNodeLoc =
1153 EpsilonPoint(BeforeProcessingCall->getLocationContext(), CE);
1154 // Add the special flag to GDM to signal retrying with no inlining.
1155 // Note, changing the state ensures that we are not going to cache out.
1156 ProgramStateRef NewNodeState = BeforeProcessingCall->getState();
1158 NewNodeState->set<ReplayWithoutInlining>(const_cast<Stmt *>(CE));
1160 // Make the new node a successor of BeforeProcessingCall.
1162 ExplodedNode *NewNode = G.getNode(NewNodeLoc, NewNodeState, false, &IsNew);
1163 // We cached out at this point. Caching out is common due to us backtracking
1164 // from the inlined function, which might spawn several paths.
1168 NewNode->addPredecessor(BeforeProcessingCall, G);
1170 // Add the new node to the work list.
1171 Engine.enqueueStmtNode(NewNode, CalleeSF->getCallSiteBlock(),
1172 CalleeSF->getIndex());
1173 NumTimesRetriedWithoutInlining++;
1177 /// Block entrance. (Update counters).
1178 void ExprEngine::processCFGBlockEntrance(const BlockEdge &L,
1179 NodeBuilderWithSinks &nodeBuilder,
1180 ExplodedNode *Pred) {
1182 // FIXME: Refactor this into a checker.
1183 if (nodeBuilder.getContext().blockCount() >= AMgr.options.maxBlockVisitOnPath) {
1184 static SimpleProgramPointTag tag("ExprEngine : Block count exceeded");
1185 const ExplodedNode *Sink =
1186 nodeBuilder.generateSink(Pred->getState(), Pred, &tag);
1188 // Check if we stopped at the top level function or not.
1189 // Root node should have the location context of the top most function.
1190 const LocationContext *CalleeLC = Pred->getLocation().getLocationContext();
1191 const LocationContext *CalleeSF = CalleeLC->getCurrentStackFrame();
1192 const LocationContext *RootLC =
1193 (*G.roots_begin())->getLocation().getLocationContext();
1194 if (RootLC->getCurrentStackFrame() != CalleeSF) {
1195 Engine.FunctionSummaries->markReachedMaxBlockCount(CalleeSF->getDecl());
1197 // Re-run the call evaluation without inlining it, by storing the
1198 // no-inlining policy in the state and enqueuing the new work item on
1199 // the list. Replay should almost never fail. Use the stats to catch it
1201 if ((!AMgr.options.NoRetryExhausted &&
1202 replayWithoutInlining(Pred, CalleeLC)))
1204 NumMaxBlockCountReachedInInlined++;
1206 NumMaxBlockCountReached++;
1208 // Make sink nodes as exhausted(for stats) only if retry failed.
1209 Engine.blocksExhausted.push_back(std::make_pair(L, Sink));
1213 //===----------------------------------------------------------------------===//
1214 // Branch processing.
1215 //===----------------------------------------------------------------------===//
1217 /// RecoverCastedSymbol - A helper function for ProcessBranch that is used
1218 /// to try to recover some path-sensitivity for casts of symbolic
1219 /// integers that promote their values (which are currently not tracked well).
1220 /// This function returns the SVal bound to Condition->IgnoreCasts if all the
1221 // cast(s) did was sign-extend the original value.
1222 static SVal RecoverCastedSymbol(ProgramStateManager& StateMgr,
1223 ProgramStateRef state,
1224 const Stmt *Condition,
1225 const LocationContext *LCtx,
1228 const Expr *Ex = dyn_cast<Expr>(Condition);
1230 return UnknownVal();
1233 bool bitsInit = false;
1235 while (const CastExpr *CE = dyn_cast<CastExpr>(Ex)) {
1236 QualType T = CE->getType();
1238 if (!T->isIntegerType())
1239 return UnknownVal();
1241 uint64_t newBits = Ctx.getTypeSize(T);
1242 if (!bitsInit || newBits < bits) {
1247 Ex = CE->getSubExpr();
1250 // We reached a non-cast. Is it a symbolic value?
1251 QualType T = Ex->getType();
1253 if (!bitsInit || !T->isIntegerType() || Ctx.getTypeSize(T) > bits)
1254 return UnknownVal();
1256 return state->getSVal(Ex, LCtx);
1259 static const Stmt *ResolveCondition(const Stmt *Condition,
1260 const CFGBlock *B) {
1261 if (const Expr *Ex = dyn_cast<Expr>(Condition))
1262 Condition = Ex->IgnoreParens();
1264 const BinaryOperator *BO = dyn_cast<BinaryOperator>(Condition);
1265 if (!BO || !BO->isLogicalOp())
1268 // For logical operations, we still have the case where some branches
1269 // use the traditional "merge" approach and others sink the branch
1270 // directly into the basic blocks representing the logical operation.
1271 // We need to distinguish between those two cases here.
1273 // The invariants are still shifting, but it is possible that the
1274 // last element in a CFGBlock is not a CFGStmt. Look for the last
1275 // CFGStmt as the value of the condition.
1276 CFGBlock::const_reverse_iterator I = B->rbegin(), E = B->rend();
1277 for (; I != E; ++I) {
1278 CFGElement Elem = *I;
1279 Optional<CFGStmt> CS = Elem.getAs<CFGStmt>();
1282 if (CS->getStmt() != Condition)
1290 BO = dyn_cast<BinaryOperator>(Condition);
1291 if (!BO || !BO->isLogicalOp())
1293 Condition = BO->getRHS()->IgnoreParens();
1295 llvm_unreachable("could not resolve condition");
1298 void ExprEngine::processBranch(const Stmt *Condition, const Stmt *Term,
1299 NodeBuilderContext& BldCtx,
1301 ExplodedNodeSet &Dst,
1302 const CFGBlock *DstT,
1303 const CFGBlock *DstF) {
1304 currBldrCtx = &BldCtx;
1306 // Check for NULL conditions; e.g. "for(;;)"
1308 BranchNodeBuilder NullCondBldr(Pred, Dst, BldCtx, DstT, DstF);
1309 NullCondBldr.markInfeasible(false);
1310 NullCondBldr.generateNode(Pred->getState(), true, Pred);
1315 // Resolve the condition in the precense of nested '||' and '&&'.
1316 if (const Expr *Ex = dyn_cast<Expr>(Condition))
1317 Condition = Ex->IgnoreParens();
1319 Condition = ResolveCondition(Condition, BldCtx.getBlock());
1320 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
1321 Condition->getLocStart(),
1322 "Error evaluating branch");
1324 ExplodedNodeSet CheckersOutSet;
1325 getCheckerManager().runCheckersForBranchCondition(Condition, CheckersOutSet,
1327 // We generated only sinks.
1328 if (CheckersOutSet.empty())
1331 BranchNodeBuilder builder(CheckersOutSet, Dst, BldCtx, DstT, DstF);
1332 for (NodeBuilder::iterator I = CheckersOutSet.begin(),
1333 E = CheckersOutSet.end(); E != I; ++I) {
1334 ExplodedNode *PredI = *I;
1336 if (PredI->isSink())
1339 ProgramStateRef PrevState = PredI->getState();
1340 SVal X = PrevState->getSVal(Condition, PredI->getLocationContext());
1342 if (X.isUnknownOrUndef()) {
1343 // Give it a chance to recover from unknown.
1344 if (const Expr *Ex = dyn_cast<Expr>(Condition)) {
1345 if (Ex->getType()->isIntegerType()) {
1346 // Try to recover some path-sensitivity. Right now casts of symbolic
1347 // integers that promote their values are currently not tracked well.
1348 // If 'Condition' is such an expression, try and recover the
1349 // underlying value and use that instead.
1350 SVal recovered = RecoverCastedSymbol(getStateManager(),
1351 PrevState, Condition,
1352 PredI->getLocationContext(),
1355 if (!recovered.isUnknown()) {
1362 // If the condition is still unknown, give up.
1363 if (X.isUnknownOrUndef()) {
1364 builder.generateNode(PrevState, true, PredI);
1365 builder.generateNode(PrevState, false, PredI);
1369 DefinedSVal V = X.castAs<DefinedSVal>();
1371 ProgramStateRef StTrue, StFalse;
1372 tie(StTrue, StFalse) = PrevState->assume(V);
1374 // Process the true branch.
1375 if (builder.isFeasible(true)) {
1377 builder.generateNode(StTrue, true, PredI);
1379 builder.markInfeasible(true);
1382 // Process the false branch.
1383 if (builder.isFeasible(false)) {
1385 builder.generateNode(StFalse, false, PredI);
1387 builder.markInfeasible(false);
1393 /// The GDM component containing the set of global variables which have been
1394 /// previously initialized with explicit initializers.
1395 REGISTER_TRAIT_WITH_PROGRAMSTATE(InitializedGlobalsSet,
1396 llvm::ImmutableSet<const VarDecl *>)
1398 void ExprEngine::processStaticInitializer(const DeclStmt *DS,
1399 NodeBuilderContext &BuilderCtx,
1401 clang::ento::ExplodedNodeSet &Dst,
1402 const CFGBlock *DstT,
1403 const CFGBlock *DstF) {
1404 currBldrCtx = &BuilderCtx;
1406 const VarDecl *VD = cast<VarDecl>(DS->getSingleDecl());
1407 ProgramStateRef state = Pred->getState();
1408 bool initHasRun = state->contains<InitializedGlobalsSet>(VD);
1409 BranchNodeBuilder builder(Pred, Dst, BuilderCtx, DstT, DstF);
1412 state = state->add<InitializedGlobalsSet>(VD);
1415 builder.generateNode(state, initHasRun, Pred);
1416 builder.markInfeasible(!initHasRun);
1421 /// processIndirectGoto - Called by CoreEngine. Used to generate successor
1422 /// nodes by processing the 'effects' of a computed goto jump.
1423 void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) {
1425 ProgramStateRef state = builder.getState();
1426 SVal V = state->getSVal(builder.getTarget(), builder.getLocationContext());
1428 // Three possibilities:
1430 // (1) We know the computed label.
1431 // (2) The label is NULL (or some other constant), or Undefined.
1432 // (3) We have no clue about the label. Dispatch to all targets.
1435 typedef IndirectGotoNodeBuilder::iterator iterator;
1437 if (Optional<loc::GotoLabel> LV = V.getAs<loc::GotoLabel>()) {
1438 const LabelDecl *L = LV->getLabel();
1440 for (iterator I = builder.begin(), E = builder.end(); I != E; ++I) {
1441 if (I.getLabel() == L) {
1442 builder.generateNode(I, state);
1447 llvm_unreachable("No block with label.");
1450 if (V.getAs<loc::ConcreteInt>() || V.getAs<UndefinedVal>()) {
1451 // Dispatch to the first target and mark it as a sink.
1452 //ExplodedNode* N = builder.generateNode(builder.begin(), state, true);
1453 // FIXME: add checker visit.
1454 // UndefBranches.insert(N);
1458 // This is really a catch-all. We don't support symbolics yet.
1459 // FIXME: Implement dispatch for symbolic pointers.
1461 for (iterator I=builder.begin(), E=builder.end(); I != E; ++I)
1462 builder.generateNode(I, state);
1465 /// ProcessEndPath - Called by CoreEngine. Used to generate end-of-path
1466 /// nodes when the control reaches the end of a function.
1467 void ExprEngine::processEndOfFunction(NodeBuilderContext& BC,
1468 ExplodedNode *Pred) {
1469 StateMgr.EndPath(Pred->getState());
1471 ExplodedNodeSet Dst;
1472 if (Pred->getLocationContext()->inTopFrame()) {
1473 // Remove dead symbols.
1474 ExplodedNodeSet AfterRemovedDead;
1475 removeDeadOnEndOfFunction(BC, Pred, AfterRemovedDead);
1478 for (ExplodedNodeSet::iterator I = AfterRemovedDead.begin(),
1479 E = AfterRemovedDead.end(); I != E; ++I) {
1480 getCheckerManager().runCheckersForEndFunction(BC, Dst, *I, *this);
1483 getCheckerManager().runCheckersForEndFunction(BC, Dst, Pred, *this);
1486 Engine.enqueueEndOfFunction(Dst);
1489 /// ProcessSwitch - Called by CoreEngine. Used to generate successor
1490 /// nodes by processing the 'effects' of a switch statement.
1491 void ExprEngine::processSwitch(SwitchNodeBuilder& builder) {
1492 typedef SwitchNodeBuilder::iterator iterator;
1493 ProgramStateRef state = builder.getState();
1494 const Expr *CondE = builder.getCondition();
1495 SVal CondV_untested = state->getSVal(CondE, builder.getLocationContext());
1497 if (CondV_untested.isUndef()) {
1498 //ExplodedNode* N = builder.generateDefaultCaseNode(state, true);
1499 // FIXME: add checker
1500 //UndefBranches.insert(N);
1504 DefinedOrUnknownSVal CondV = CondV_untested.castAs<DefinedOrUnknownSVal>();
1506 ProgramStateRef DefaultSt = state;
1508 iterator I = builder.begin(), EI = builder.end();
1509 bool defaultIsFeasible = I == EI;
1511 for ( ; I != EI; ++I) {
1512 // Successor may be pruned out during CFG construction.
1516 const CaseStmt *Case = I.getCase();
1518 // Evaluate the LHS of the case value.
1519 llvm::APSInt V1 = Case->getLHS()->EvaluateKnownConstInt(getContext());
1520 assert(V1.getBitWidth() == getContext().getTypeSize(CondE->getType()));
1522 // Get the RHS of the case, if it exists.
1524 if (const Expr *E = Case->getRHS())
1525 V2 = E->EvaluateKnownConstInt(getContext());
1529 // FIXME: Eventually we should replace the logic below with a range
1530 // comparison, rather than concretize the values within the range.
1531 // This should be easy once we have "ranges" for NonLVals.
1534 nonloc::ConcreteInt CaseVal(getBasicVals().getValue(V1));
1535 DefinedOrUnknownSVal Res = svalBuilder.evalEQ(DefaultSt ? DefaultSt : state,
1538 // Now "assume" that the case matches.
1539 if (ProgramStateRef stateNew = state->assume(Res, true)) {
1540 builder.generateCaseStmtNode(I, stateNew);
1542 // If CondV evaluates to a constant, then we know that this
1543 // is the *only* case that we can take, so stop evaluating the
1545 if (CondV.getAs<nonloc::ConcreteInt>())
1549 // Now "assume" that the case doesn't match. Add this state
1550 // to the default state (if it is feasible).
1552 if (ProgramStateRef stateNew = DefaultSt->assume(Res, false)) {
1553 defaultIsFeasible = true;
1554 DefaultSt = stateNew;
1557 defaultIsFeasible = false;
1562 // Concretize the next value in the range.
1572 if (!defaultIsFeasible)
1575 // If we have switch(enum value), the default branch is not
1576 // feasible if all of the enum constants not covered by 'case:' statements
1577 // are not feasible values for the switch condition.
1579 // Note that this isn't as accurate as it could be. Even if there isn't
1580 // a case for a particular enum value as long as that enum value isn't
1581 // feasible then it shouldn't be considered for making 'default:' reachable.
1582 const SwitchStmt *SS = builder.getSwitch();
1583 const Expr *CondExpr = SS->getCond()->IgnoreParenImpCasts();
1584 if (CondExpr->getType()->getAs<EnumType>()) {
1585 if (SS->isAllEnumCasesCovered())
1589 builder.generateDefaultCaseNode(DefaultSt);
1592 //===----------------------------------------------------------------------===//
1593 // Transfer functions: Loads and stores.
1594 //===----------------------------------------------------------------------===//
1596 void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D,
1598 ExplodedNodeSet &Dst) {
1599 StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
1601 ProgramStateRef state = Pred->getState();
1602 const LocationContext *LCtx = Pred->getLocationContext();
1604 if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
1605 assert(Ex->isGLValue());
1606 SVal V = state->getLValue(VD, Pred->getLocationContext());
1608 // For references, the 'lvalue' is the pointer address stored in the
1609 // reference region.
1610 if (VD->getType()->isReferenceType()) {
1611 if (const MemRegion *R = V.getAsRegion())
1612 V = state->getSVal(R);
1617 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), 0,
1618 ProgramPoint::PostLValueKind);
1621 if (const EnumConstantDecl *ED = dyn_cast<EnumConstantDecl>(D)) {
1622 assert(!Ex->isGLValue());
1623 SVal V = svalBuilder.makeIntVal(ED->getInitVal());
1624 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V));
1627 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
1628 SVal V = svalBuilder.getFunctionPointer(FD);
1629 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), 0,
1630 ProgramPoint::PostLValueKind);
1633 if (isa<FieldDecl>(D)) {
1634 // FIXME: Compute lvalue of field pointers-to-member.
1635 // Right now we just use a non-null void pointer, so that it gives proper
1636 // results in boolean contexts.
1637 SVal V = svalBuilder.conjureSymbolVal(Ex, LCtx, getContext().VoidPtrTy,
1638 currBldrCtx->blockCount());
1639 state = state->assume(V.castAs<DefinedOrUnknownSVal>(), true);
1640 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), 0,
1641 ProgramPoint::PostLValueKind);
1645 llvm_unreachable("Support for this Decl not implemented.");
1648 /// VisitArraySubscriptExpr - Transfer function for array accesses
1649 void ExprEngine::VisitLvalArraySubscriptExpr(const ArraySubscriptExpr *A,
1651 ExplodedNodeSet &Dst){
1653 const Expr *Base = A->getBase()->IgnoreParens();
1654 const Expr *Idx = A->getIdx()->IgnoreParens();
1657 ExplodedNodeSet checkerPreStmt;
1658 getCheckerManager().runCheckersForPreStmt(checkerPreStmt, Pred, A, *this);
1660 StmtNodeBuilder Bldr(checkerPreStmt, Dst, *currBldrCtx);
1662 for (ExplodedNodeSet::iterator it = checkerPreStmt.begin(),
1663 ei = checkerPreStmt.end(); it != ei; ++it) {
1664 const LocationContext *LCtx = (*it)->getLocationContext();
1665 ProgramStateRef state = (*it)->getState();
1666 SVal V = state->getLValue(A->getType(),
1667 state->getSVal(Idx, LCtx),
1668 state->getSVal(Base, LCtx));
1669 assert(A->isGLValue());
1670 Bldr.generateNode(A, *it, state->BindExpr(A, LCtx, V), 0,
1671 ProgramPoint::PostLValueKind);
1675 /// VisitMemberExpr - Transfer function for member expressions.
1676 void ExprEngine::VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred,
1677 ExplodedNodeSet &TopDst) {
1679 StmtNodeBuilder Bldr(Pred, TopDst, *currBldrCtx);
1680 ExplodedNodeSet Dst;
1681 ValueDecl *Member = M->getMemberDecl();
1683 // Handle static member variables and enum constants accessed via
1685 if (isa<VarDecl>(Member) || isa<EnumConstantDecl>(Member)) {
1686 Bldr.takeNodes(Pred);
1687 VisitCommonDeclRefExpr(M, Member, Pred, Dst);
1692 ProgramStateRef state = Pred->getState();
1693 const LocationContext *LCtx = Pred->getLocationContext();
1694 Expr *BaseExpr = M->getBase();
1696 // Handle C++ method calls.
1697 if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(Member)) {
1698 if (MD->isInstance())
1699 state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr);
1701 SVal MDVal = svalBuilder.getFunctionPointer(MD);
1702 state = state->BindExpr(M, LCtx, MDVal);
1704 Bldr.generateNode(M, Pred, state);
1708 // Handle regular struct fields / member variables.
1709 state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr);
1710 SVal baseExprVal = state->getSVal(BaseExpr, LCtx);
1712 FieldDecl *field = cast<FieldDecl>(Member);
1713 SVal L = state->getLValue(field, baseExprVal);
1714 if (M->isGLValue()) {
1715 if (field->getType()->isReferenceType()) {
1716 if (const MemRegion *R = L.getAsRegion())
1717 L = state->getSVal(R);
1722 Bldr.generateNode(M, Pred, state->BindExpr(M, LCtx, L), 0,
1723 ProgramPoint::PostLValueKind);
1725 Bldr.takeNodes(Pred);
1726 evalLoad(Dst, M, M, Pred, state, L);
1732 class CollectReachableSymbolsCallback : public SymbolVisitor {
1733 InvalidatedSymbols Symbols;
1735 CollectReachableSymbolsCallback(ProgramStateRef State) {}
1736 const InvalidatedSymbols &getSymbols() const { return Symbols; }
1738 bool VisitSymbol(SymbolRef Sym) {
1739 Symbols.insert(Sym);
1743 } // end anonymous namespace
1745 // A value escapes in three possible cases:
1746 // (1) We are binding to something that is not a memory region.
1747 // (2) We are binding to a MemrRegion that does not have stack storage.
1748 // (3) We are binding to a MemRegion with stack storage that the store
1749 // does not understand.
1750 ProgramStateRef ExprEngine::processPointerEscapedOnBind(ProgramStateRef State,
1751 SVal Loc, SVal Val) {
1752 // Are we storing to something that causes the value to "escape"?
1753 bool escapes = true;
1755 // TODO: Move to StoreManager.
1756 if (Optional<loc::MemRegionVal> regionLoc = Loc.getAs<loc::MemRegionVal>()) {
1757 escapes = !regionLoc->getRegion()->hasStackStorage();
1760 // To test (3), generate a new state with the binding added. If it is
1761 // the same state, then it escapes (since the store cannot represent
1763 // Do this only if we know that the store is not supposed to generate the
1765 SVal StoredVal = State->getSVal(regionLoc->getRegion());
1766 if (StoredVal != Val)
1767 escapes = (State == (State->bindLoc(*regionLoc, Val)));
1771 // If our store can represent the binding and we aren't storing to something
1772 // that doesn't have local storage then just return and have the simulation
1773 // state continue as is.
1777 // Otherwise, find all symbols referenced by 'val' that we are tracking
1778 // and stop tracking them.
1779 CollectReachableSymbolsCallback Scanner =
1780 State->scanReachableSymbols<CollectReachableSymbolsCallback>(Val);
1781 const InvalidatedSymbols &EscapedSymbols = Scanner.getSymbols();
1782 State = getCheckerManager().runCheckersForPointerEscape(State,
1791 ExprEngine::notifyCheckersOfPointerEscape(ProgramStateRef State,
1792 const InvalidatedSymbols *Invalidated,
1793 ArrayRef<const MemRegion *> ExplicitRegions,
1794 ArrayRef<const MemRegion *> Regions,
1795 const CallEvent *Call,
1798 if (!Invalidated || Invalidated->empty())
1802 return getCheckerManager().runCheckersForPointerEscape(State,
1807 // Note: Due to current limitations of RegionStore, we only process the top
1808 // level const pointers correctly. The lower level const pointers are
1809 // currently treated as non-const.
1811 return getCheckerManager().runCheckersForPointerEscape(State,
1814 PSK_DirectEscapeOnCall,
1817 // If the symbols were invalidated by a call, we want to find out which ones
1818 // were invalidated directly due to being arguments to the call.
1819 InvalidatedSymbols SymbolsDirectlyInvalidated;
1820 for (ArrayRef<const MemRegion *>::iterator I = ExplicitRegions.begin(),
1821 E = ExplicitRegions.end(); I != E; ++I) {
1822 if (const SymbolicRegion *R = (*I)->StripCasts()->getAs<SymbolicRegion>())
1823 SymbolsDirectlyInvalidated.insert(R->getSymbol());
1826 InvalidatedSymbols SymbolsIndirectlyInvalidated;
1827 for (InvalidatedSymbols::const_iterator I=Invalidated->begin(),
1828 E = Invalidated->end(); I!=E; ++I) {
1830 if (SymbolsDirectlyInvalidated.count(sym))
1832 SymbolsIndirectlyInvalidated.insert(sym);
1835 if (!SymbolsDirectlyInvalidated.empty())
1836 State = getCheckerManager().runCheckersForPointerEscape(State,
1837 SymbolsDirectlyInvalidated, Call, PSK_DirectEscapeOnCall);
1839 // Notify about the symbols that get indirectly invalidated by the call.
1840 if (!SymbolsIndirectlyInvalidated.empty())
1841 State = getCheckerManager().runCheckersForPointerEscape(State,
1842 SymbolsIndirectlyInvalidated, Call, PSK_IndirectEscapeOnCall);
1847 /// evalBind - Handle the semantics of binding a value to a specific location.
1848 /// This method is used by evalStore and (soon) VisitDeclStmt, and others.
1849 void ExprEngine::evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE,
1851 SVal location, SVal Val,
1852 bool atDeclInit, const ProgramPoint *PP) {
1854 const LocationContext *LC = Pred->getLocationContext();
1855 PostStmt PS(StoreE, LC);
1859 // Do a previsit of the bind.
1860 ExplodedNodeSet CheckedSet;
1861 getCheckerManager().runCheckersForBind(CheckedSet, Pred, location, Val,
1862 StoreE, *this, *PP);
1865 StmtNodeBuilder Bldr(CheckedSet, Dst, *currBldrCtx);
1867 // If the location is not a 'Loc', it will already be handled by
1868 // the checkers. There is nothing left to do.
1869 if (!location.getAs<Loc>()) {
1870 const ProgramPoint L = PostStore(StoreE, LC, /*Loc*/0, /*tag*/0);
1871 ProgramStateRef state = Pred->getState();
1872 state = processPointerEscapedOnBind(state, location, Val);
1873 Bldr.generateNode(L, state, Pred);
1878 for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end();
1880 ExplodedNode *PredI = *I;
1881 ProgramStateRef state = PredI->getState();
1883 state = processPointerEscapedOnBind(state, location, Val);
1885 // When binding the value, pass on the hint that this is a initialization.
1886 // For initializations, we do not need to inform clients of region
1888 state = state->bindLoc(location.castAs<Loc>(),
1889 Val, /* notifyChanges = */ !atDeclInit);
1891 const MemRegion *LocReg = 0;
1892 if (Optional<loc::MemRegionVal> LocRegVal =
1893 location.getAs<loc::MemRegionVal>()) {
1894 LocReg = LocRegVal->getRegion();
1897 const ProgramPoint L = PostStore(StoreE, LC, LocReg, 0);
1898 Bldr.generateNode(L, state, PredI);
1902 /// evalStore - Handle the semantics of a store via an assignment.
1903 /// @param Dst The node set to store generated state nodes
1904 /// @param AssignE The assignment expression if the store happens in an
1906 /// @param LocationE The location expression that is stored to.
1907 /// @param state The current simulation state
1908 /// @param location The location to store the value
1909 /// @param Val The value to be stored
1910 void ExprEngine::evalStore(ExplodedNodeSet &Dst, const Expr *AssignE,
1911 const Expr *LocationE,
1913 ProgramStateRef state, SVal location, SVal Val,
1914 const ProgramPointTag *tag) {
1915 // Proceed with the store. We use AssignE as the anchor for the PostStore
1916 // ProgramPoint if it is non-NULL, and LocationE otherwise.
1917 const Expr *StoreE = AssignE ? AssignE : LocationE;
1919 // Evaluate the location (checks for bad dereferences).
1920 ExplodedNodeSet Tmp;
1921 evalLocation(Tmp, AssignE, LocationE, Pred, state, location, tag, false);
1926 if (location.isUndef())
1929 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI)
1930 evalBind(Dst, StoreE, *NI, location, Val, false);
1933 void ExprEngine::evalLoad(ExplodedNodeSet &Dst,
1935 const Expr *BoundEx,
1937 ProgramStateRef state,
1939 const ProgramPointTag *tag,
1942 assert(!location.getAs<NonLoc>() && "location cannot be a NonLoc.");
1944 // Are we loading from a region? This actually results in two loads; one
1945 // to fetch the address of the referenced value and one to fetch the
1946 // referenced value.
1947 if (const TypedValueRegion *TR =
1948 dyn_cast_or_null<TypedValueRegion>(location.getAsRegion())) {
1950 QualType ValTy = TR->getValueType();
1951 if (const ReferenceType *RT = ValTy->getAs<ReferenceType>()) {
1952 static SimpleProgramPointTag
1953 loadReferenceTag("ExprEngine : Load Reference");
1954 ExplodedNodeSet Tmp;
1955 evalLoadCommon(Tmp, NodeEx, BoundEx, Pred, state,
1956 location, &loadReferenceTag,
1957 getContext().getPointerType(RT->getPointeeType()));
1959 // Perform the load from the referenced value.
1960 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end() ; I!=E; ++I) {
1961 state = (*I)->getState();
1962 location = state->getSVal(BoundEx, (*I)->getLocationContext());
1963 evalLoadCommon(Dst, NodeEx, BoundEx, *I, state, location, tag, LoadTy);
1969 evalLoadCommon(Dst, NodeEx, BoundEx, Pred, state, location, tag, LoadTy);
1972 void ExprEngine::evalLoadCommon(ExplodedNodeSet &Dst,
1974 const Expr *BoundEx,
1976 ProgramStateRef state,
1978 const ProgramPointTag *tag,
1982 // Evaluate the location (checks for bad dereferences).
1983 ExplodedNodeSet Tmp;
1984 evalLocation(Tmp, NodeEx, BoundEx, Pred, state, location, tag, true);
1988 StmtNodeBuilder Bldr(Tmp, Dst, *currBldrCtx);
1989 if (location.isUndef())
1992 // Proceed with the load.
1993 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) {
1994 state = (*NI)->getState();
1995 const LocationContext *LCtx = (*NI)->getLocationContext();
1997 SVal V = UnknownVal();
1998 if (location.isValid()) {
1999 if (LoadTy.isNull())
2000 LoadTy = BoundEx->getType();
2001 V = state->getSVal(location.castAs<Loc>(), LoadTy);
2004 Bldr.generateNode(NodeEx, *NI, state->BindExpr(BoundEx, LCtx, V), tag,
2005 ProgramPoint::PostLoadKind);
2009 void ExprEngine::evalLocation(ExplodedNodeSet &Dst,
2011 const Stmt *BoundEx,
2013 ProgramStateRef state,
2015 const ProgramPointTag *tag,
2017 StmtNodeBuilder BldrTop(Pred, Dst, *currBldrCtx);
2018 // Early checks for performance reason.
2019 if (location.isUnknown()) {
2023 ExplodedNodeSet Src;
2024 BldrTop.takeNodes(Pred);
2025 StmtNodeBuilder Bldr(Pred, Src, *currBldrCtx);
2026 if (Pred->getState() != state) {
2027 // Associate this new state with an ExplodedNode.
2028 // FIXME: If I pass null tag, the graph is incorrect, e.g for
2032 // "p = 0" is not noted as "Null pointer value stored to 'p'" but
2033 // instead "int *p" is noted as
2034 // "Variable 'p' initialized to a null pointer value"
2036 static SimpleProgramPointTag tag("ExprEngine: Location");
2037 Bldr.generateNode(NodeEx, Pred, state, &tag);
2039 ExplodedNodeSet Tmp;
2040 getCheckerManager().runCheckersForLocation(Tmp, Src, location, isLoad,
2041 NodeEx, BoundEx, *this);
2042 BldrTop.addNodes(Tmp);
2045 std::pair<const ProgramPointTag *, const ProgramPointTag*>
2046 ExprEngine::geteagerlyAssumeBinOpBifurcationTags() {
2047 static SimpleProgramPointTag
2048 eagerlyAssumeBinOpBifurcationTrue("ExprEngine : Eagerly Assume True"),
2049 eagerlyAssumeBinOpBifurcationFalse("ExprEngine : Eagerly Assume False");
2050 return std::make_pair(&eagerlyAssumeBinOpBifurcationTrue,
2051 &eagerlyAssumeBinOpBifurcationFalse);
2054 void ExprEngine::evalEagerlyAssumeBinOpBifurcation(ExplodedNodeSet &Dst,
2055 ExplodedNodeSet &Src,
2057 StmtNodeBuilder Bldr(Src, Dst, *currBldrCtx);
2059 for (ExplodedNodeSet::iterator I=Src.begin(), E=Src.end(); I!=E; ++I) {
2060 ExplodedNode *Pred = *I;
2061 // Test if the previous node was as the same expression. This can happen
2062 // when the expression fails to evaluate to anything meaningful and
2063 // (as an optimization) we don't generate a node.
2064 ProgramPoint P = Pred->getLocation();
2065 if (!P.getAs<PostStmt>() || P.castAs<PostStmt>().getStmt() != Ex) {
2069 ProgramStateRef state = Pred->getState();
2070 SVal V = state->getSVal(Ex, Pred->getLocationContext());
2071 Optional<nonloc::SymbolVal> SEV = V.getAs<nonloc::SymbolVal>();
2072 if (SEV && SEV->isExpression()) {
2073 const std::pair<const ProgramPointTag *, const ProgramPointTag*> &tags =
2074 geteagerlyAssumeBinOpBifurcationTags();
2076 ProgramStateRef StateTrue, StateFalse;
2077 tie(StateTrue, StateFalse) = state->assume(*SEV);
2079 // First assume that the condition is true.
2081 SVal Val = svalBuilder.makeIntVal(1U, Ex->getType());
2082 StateTrue = StateTrue->BindExpr(Ex, Pred->getLocationContext(), Val);
2083 Bldr.generateNode(Ex, Pred, StateTrue, tags.first);
2086 // Next, assume that the condition is false.
2088 SVal Val = svalBuilder.makeIntVal(0U, Ex->getType());
2089 StateFalse = StateFalse->BindExpr(Ex, Pred->getLocationContext(), Val);
2090 Bldr.generateNode(Ex, Pred, StateFalse, tags.second);
2096 void ExprEngine::VisitGCCAsmStmt(const GCCAsmStmt *A, ExplodedNode *Pred,
2097 ExplodedNodeSet &Dst) {
2098 StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
2099 // We have processed both the inputs and the outputs. All of the outputs
2100 // should evaluate to Locs. Nuke all of their values.
2102 // FIXME: Some day in the future it would be nice to allow a "plug-in"
2103 // which interprets the inline asm and stores proper results in the
2106 ProgramStateRef state = Pred->getState();
2108 for (GCCAsmStmt::const_outputs_iterator OI = A->begin_outputs(),
2109 OE = A->end_outputs(); OI != OE; ++OI) {
2110 SVal X = state->getSVal(*OI, Pred->getLocationContext());
2111 assert (!X.getAs<NonLoc>()); // Should be an Lval, or unknown, undef.
2113 if (Optional<Loc> LV = X.getAs<Loc>())
2114 state = state->bindLoc(*LV, UnknownVal());
2117 Bldr.generateNode(A, Pred, state);
2120 void ExprEngine::VisitMSAsmStmt(const MSAsmStmt *A, ExplodedNode *Pred,
2121 ExplodedNodeSet &Dst) {
2122 StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
2123 Bldr.generateNode(A, Pred, Pred->getState());
2126 //===----------------------------------------------------------------------===//
2128 //===----------------------------------------------------------------------===//
2131 static ExprEngine* GraphPrintCheckerState;
2132 static SourceManager* GraphPrintSourceManager;
2136 struct DOTGraphTraits<ExplodedNode*> :
2137 public DefaultDOTGraphTraits {
2139 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {}
2141 // FIXME: Since we do not cache error nodes in ExprEngine now, this does not
2143 static std::string getNodeAttributes(const ExplodedNode *N, void*) {
2146 // FIXME: Replace with a general scheme to tell if the node is
2148 if (GraphPrintCheckerState->isImplicitNullDeref(N) ||
2149 GraphPrintCheckerState->isExplicitNullDeref(N) ||
2150 GraphPrintCheckerState->isUndefDeref(N) ||
2151 GraphPrintCheckerState->isUndefStore(N) ||
2152 GraphPrintCheckerState->isUndefControlFlow(N) ||
2153 GraphPrintCheckerState->isUndefResult(N) ||
2154 GraphPrintCheckerState->isBadCall(N) ||
2155 GraphPrintCheckerState->isUndefArg(N))
2156 return "color=\"red\",style=\"filled\"";
2158 if (GraphPrintCheckerState->isNoReturnCall(N))
2159 return "color=\"blue\",style=\"filled\"";
2164 static void printLocation(raw_ostream &Out, SourceLocation SLoc) {
2165 if (SLoc.isFileID()) {
2167 << GraphPrintSourceManager->getExpansionLineNumber(SLoc)
2169 << GraphPrintSourceManager->getExpansionColumnNumber(SLoc)
2174 static std::string getNodeLabel(const ExplodedNode *N, void*){
2177 llvm::raw_string_ostream Out(sbuf);
2179 // Program Location.
2180 ProgramPoint Loc = N->getLocation();
2182 switch (Loc.getKind()) {
2183 case ProgramPoint::BlockEntranceKind: {
2184 Out << "Block Entrance: B"
2185 << Loc.castAs<BlockEntrance>().getBlock()->getBlockID();
2186 if (const NamedDecl *ND =
2187 dyn_cast<NamedDecl>(Loc.getLocationContext()->getDecl())) {
2195 case ProgramPoint::BlockExitKind:
2199 case ProgramPoint::CallEnterKind:
2203 case ProgramPoint::CallExitBeginKind:
2204 Out << "CallExitBegin";
2207 case ProgramPoint::CallExitEndKind:
2208 Out << "CallExitEnd";
2211 case ProgramPoint::PostStmtPurgeDeadSymbolsKind:
2212 Out << "PostStmtPurgeDeadSymbols";
2215 case ProgramPoint::PreStmtPurgeDeadSymbolsKind:
2216 Out << "PreStmtPurgeDeadSymbols";
2219 case ProgramPoint::EpsilonKind:
2220 Out << "Epsilon Point";
2223 case ProgramPoint::PreImplicitCallKind: {
2224 ImplicitCallPoint PC = Loc.castAs<ImplicitCallPoint>();
2227 // FIXME: Get proper printing options.
2228 PC.getDecl()->print(Out, LangOptions());
2229 printLocation(Out, PC.getLocation());
2233 case ProgramPoint::PostImplicitCallKind: {
2234 ImplicitCallPoint PC = Loc.castAs<ImplicitCallPoint>();
2235 Out << "PostCall: ";
2237 // FIXME: Get proper printing options.
2238 PC.getDecl()->print(Out, LangOptions());
2239 printLocation(Out, PC.getLocation());
2243 case ProgramPoint::PostInitializerKind: {
2244 Out << "PostInitializer: ";
2245 const CXXCtorInitializer *Init =
2246 Loc.castAs<PostInitializer>().getInitializer();
2247 if (const FieldDecl *FD = Init->getAnyMember())
2250 QualType Ty = Init->getTypeSourceInfo()->getType();
2251 Ty = Ty.getLocalUnqualifiedType();
2252 LangOptions LO; // FIXME.
2258 case ProgramPoint::BlockEdgeKind: {
2259 const BlockEdge &E = Loc.castAs<BlockEdge>();
2260 Out << "Edge: (B" << E.getSrc()->getBlockID() << ", B"
2261 << E.getDst()->getBlockID() << ')';
2263 if (const Stmt *T = E.getSrc()->getTerminator()) {
2264 SourceLocation SLoc = T->getLocStart();
2266 Out << "\\|Terminator: ";
2267 LangOptions LO; // FIXME.
2268 E.getSrc()->printTerminator(Out, LO);
2270 if (SLoc.isFileID()) {
2272 << GraphPrintSourceManager->getExpansionLineNumber(SLoc)
2274 << GraphPrintSourceManager->getExpansionColumnNumber(SLoc);
2277 if (isa<SwitchStmt>(T)) {
2278 const Stmt *Label = E.getDst()->getLabel();
2281 if (const CaseStmt *C = dyn_cast<CaseStmt>(Label)) {
2283 LangOptions LO; // FIXME.
2284 C->getLHS()->printPretty(Out, 0, PrintingPolicy(LO));
2286 if (const Stmt *RHS = C->getRHS()) {
2288 RHS->printPretty(Out, 0, PrintingPolicy(LO));
2294 assert (isa<DefaultStmt>(Label));
2295 Out << "\\ldefault:";
2299 Out << "\\l(implicit) default:";
2301 else if (isa<IndirectGotoStmt>(T)) {
2305 Out << "\\lCondition: ";
2306 if (*E.getSrc()->succ_begin() == E.getDst())
2316 // FIXME: Replace with a general scheme to determine
2317 // the name of the check.
2318 if (GraphPrintCheckerState->isUndefControlFlow(N)) {
2319 Out << "\\|Control-flow based on\\lUndefined value.\\l";
2326 const Stmt *S = Loc.castAs<StmtPoint>().getStmt();
2328 Out << S->getStmtClassName() << ' ' << (const void*) S << ' ';
2329 LangOptions LO; // FIXME.
2330 S->printPretty(Out, 0, PrintingPolicy(LO));
2331 printLocation(Out, S->getLocStart());
2333 if (Loc.getAs<PreStmt>())
2334 Out << "\\lPreStmt\\l;";
2335 else if (Loc.getAs<PostLoad>())
2336 Out << "\\lPostLoad\\l;";
2337 else if (Loc.getAs<PostStore>())
2338 Out << "\\lPostStore\\l";
2339 else if (Loc.getAs<PostLValue>())
2340 Out << "\\lPostLValue\\l";
2343 // FIXME: Replace with a general scheme to determine
2344 // the name of the check.
2345 if (GraphPrintCheckerState->isImplicitNullDeref(N))
2346 Out << "\\|Implicit-Null Dereference.\\l";
2347 else if (GraphPrintCheckerState->isExplicitNullDeref(N))
2348 Out << "\\|Explicit-Null Dereference.\\l";
2349 else if (GraphPrintCheckerState->isUndefDeref(N))
2350 Out << "\\|Dereference of undefialied value.\\l";
2351 else if (GraphPrintCheckerState->isUndefStore(N))
2352 Out << "\\|Store to Undefined Loc.";
2353 else if (GraphPrintCheckerState->isUndefResult(N))
2354 Out << "\\|Result of operation is undefined.";
2355 else if (GraphPrintCheckerState->isNoReturnCall(N))
2356 Out << "\\|Call to function marked \"noreturn\".";
2357 else if (GraphPrintCheckerState->isBadCall(N))
2358 Out << "\\|Call to NULL/Undefined.";
2359 else if (GraphPrintCheckerState->isUndefArg(N))
2360 Out << "\\|Argument in call is undefined";
2367 ProgramStateRef state = N->getState();
2368 Out << "\\|StateID: " << (const void*) state.getPtr()
2369 << " NodeID: " << (const void*) N << "\\|";
2370 state->printDOT(Out);
2374 if (const ProgramPointTag *tag = Loc.getTag()) {
2375 Out << "\\|Tag: " << tag->getTagDescription();
2381 } // end llvm namespace
2385 template <typename ITERATOR>
2386 ExplodedNode *GetGraphNode(ITERATOR I) { return *I; }
2388 template <> ExplodedNode*
2389 GetGraphNode<llvm::DenseMap<ExplodedNode*, Expr*>::iterator>
2390 (llvm::DenseMap<ExplodedNode*, Expr*>::iterator I) {
2395 void ExprEngine::ViewGraph(bool trim) {
2398 std::vector<const ExplodedNode*> Src;
2400 // Flush any outstanding reports to make sure we cover all the nodes.
2401 // This does not cause them to get displayed.
2402 for (BugReporter::iterator I=BR.begin(), E=BR.end(); I!=E; ++I)
2403 const_cast<BugType*>(*I)->FlushReports(BR);
2405 // Iterate through the reports and get their nodes.
2406 for (BugReporter::EQClasses_iterator
2407 EI = BR.EQClasses_begin(), EE = BR.EQClasses_end(); EI != EE; ++EI) {
2408 ExplodedNode *N = const_cast<ExplodedNode*>(EI->begin()->getErrorNode());
2409 if (N) Src.push_back(N);
2415 GraphPrintCheckerState = this;
2416 GraphPrintSourceManager = &getContext().getSourceManager();
2418 llvm::ViewGraph(*G.roots_begin(), "ExprEngine");
2420 GraphPrintCheckerState = NULL;
2421 GraphPrintSourceManager = NULL;
2426 void ExprEngine::ViewGraph(ArrayRef<const ExplodedNode*> Nodes) {
2428 GraphPrintCheckerState = this;
2429 GraphPrintSourceManager = &getContext().getSourceManager();
2431 OwningPtr<ExplodedGraph> TrimmedG(G.trim(Nodes));
2433 if (!TrimmedG.get())
2434 llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n";
2436 llvm::ViewGraph(*TrimmedG->roots_begin(), "TrimmedExprEngine");
2438 GraphPrintCheckerState = NULL;
2439 GraphPrintSourceManager = NULL;