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 const BuiltinType *BT = dyn_cast<BuiltinType>(T);
110 if (!BT || !BT->isInteger())
113 const MemRegion *R = state->getRegion(PD, InitLoc);
117 SVal V = state->getSVal(loc::MemRegionVal(R));
118 SVal Constraint_untested = evalBinOp(state, BO_GT, V,
119 svalBuilder.makeZeroVal(T),
122 Optional<DefinedOrUnknownSVal> Constraint =
123 Constraint_untested.getAs<DefinedOrUnknownSVal>();
128 if (ProgramStateRef newState = state->assume(*Constraint, true))
135 if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) {
136 // Precondition: 'self' is always non-null upon entry to an Objective-C
138 const ImplicitParamDecl *SelfD = MD->getSelfDecl();
139 const MemRegion *R = state->getRegion(SelfD, InitLoc);
140 SVal V = state->getSVal(loc::MemRegionVal(R));
142 if (Optional<Loc> LV = V.getAs<Loc>()) {
143 // Assume that the pointer value in 'self' is non-null.
144 state = state->assume(*LV, true);
145 assert(state && "'self' cannot be null");
149 if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(D)) {
150 if (!MD->isStatic()) {
151 // Precondition: 'this' is always non-null upon entry to the
152 // top-level function. This is our starting assumption for
153 // analyzing an "open" program.
154 const StackFrameContext *SFC = InitLoc->getCurrentStackFrame();
155 if (SFC->getParent() == 0) {
156 loc::MemRegionVal L = svalBuilder.getCXXThis(MD, SFC);
157 SVal V = state->getSVal(L);
158 if (Optional<Loc> LV = V.getAs<Loc>()) {
159 state = state->assume(*LV, true);
160 assert(state && "'this' cannot be null");
170 ExprEngine::createTemporaryRegionIfNeeded(ProgramStateRef State,
171 const LocationContext *LC,
173 const Expr *Result) {
174 SVal V = State->getSVal(Ex, LC);
176 // If we don't have an explicit result expression, we're in "if needed"
177 // mode. Only create a region if the current value is a NonLoc.
178 if (!V.getAs<NonLoc>())
182 // We need to create a region no matter what. For sanity, make sure we don't
183 // try to stuff a Loc into a non-pointer temporary region.
184 assert(!V.getAs<Loc>() || Loc::isLocType(Result->getType()) ||
185 Result->getType()->isMemberPointerType());
188 ProgramStateManager &StateMgr = State->getStateManager();
189 MemRegionManager &MRMgr = StateMgr.getRegionManager();
190 StoreManager &StoreMgr = StateMgr.getStoreManager();
192 // We need to be careful about treating a derived type's value as
193 // bindings for a base type. Unless we're creating a temporary pointer region,
194 // start by stripping and recording base casts.
195 SmallVector<const CastExpr *, 4> Casts;
196 const Expr *Inner = Ex->IgnoreParens();
197 if (!Loc::isLocType(Result->getType())) {
198 while (const CastExpr *CE = dyn_cast<CastExpr>(Inner)) {
199 if (CE->getCastKind() == CK_DerivedToBase ||
200 CE->getCastKind() == CK_UncheckedDerivedToBase)
202 else if (CE->getCastKind() != CK_NoOp)
205 Inner = CE->getSubExpr()->IgnoreParens();
209 // Create a temporary object region for the inner expression (which may have
210 // a more derived type) and bind the value into it.
211 const TypedValueRegion *TR = MRMgr.getCXXTempObjectRegion(Inner, LC);
212 SVal Reg = loc::MemRegionVal(TR);
215 V = getSValBuilder().conjureSymbolVal(Result, LC, TR->getValueType(),
216 currBldrCtx->blockCount());
217 State = State->bindLoc(Reg, V);
219 // Re-apply the casts (from innermost to outermost) for type sanity.
220 for (SmallVectorImpl<const CastExpr *>::reverse_iterator I = Casts.rbegin(),
223 Reg = StoreMgr.evalDerivedToBase(Reg, *I);
226 State = State->BindExpr(Result, LC, Reg);
230 //===----------------------------------------------------------------------===//
231 // Top-level transfer function logic (Dispatcher).
232 //===----------------------------------------------------------------------===//
234 /// evalAssume - Called by ConstraintManager. Used to call checker-specific
235 /// logic for handling assumptions on symbolic values.
236 ProgramStateRef ExprEngine::processAssume(ProgramStateRef state,
237 SVal cond, bool assumption) {
238 return getCheckerManager().runCheckersForEvalAssume(state, cond, assumption);
241 bool ExprEngine::wantsRegionChangeUpdate(ProgramStateRef state) {
242 return getCheckerManager().wantsRegionChangeUpdate(state);
246 ExprEngine::processRegionChanges(ProgramStateRef state,
247 const InvalidatedSymbols *invalidated,
248 ArrayRef<const MemRegion *> Explicits,
249 ArrayRef<const MemRegion *> Regions,
250 const CallEvent *Call) {
251 return getCheckerManager().runCheckersForRegionChanges(state, invalidated,
252 Explicits, Regions, Call);
255 void ExprEngine::printState(raw_ostream &Out, ProgramStateRef State,
256 const char *NL, const char *Sep) {
257 getCheckerManager().runCheckersForPrintState(Out, State, NL, Sep);
260 void ExprEngine::processEndWorklist(bool hasWorkRemaining) {
261 getCheckerManager().runCheckersForEndAnalysis(G, BR, *this);
264 void ExprEngine::processCFGElement(const CFGElement E, ExplodedNode *Pred,
265 unsigned StmtIdx, NodeBuilderContext *Ctx) {
266 currStmtIdx = StmtIdx;
269 switch (E.getKind()) {
270 case CFGElement::Statement:
271 ProcessStmt(const_cast<Stmt*>(E.castAs<CFGStmt>().getStmt()), Pred);
273 case CFGElement::Initializer:
274 ProcessInitializer(E.castAs<CFGInitializer>().getInitializer(), Pred);
276 case CFGElement::AutomaticObjectDtor:
277 case CFGElement::BaseDtor:
278 case CFGElement::MemberDtor:
279 case CFGElement::TemporaryDtor:
280 ProcessImplicitDtor(E.castAs<CFGImplicitDtor>(), Pred);
286 static bool shouldRemoveDeadBindings(AnalysisManager &AMgr,
288 const ExplodedNode *Pred,
289 const LocationContext *LC) {
291 // Are we never purging state values?
292 if (AMgr.options.AnalysisPurgeOpt == PurgeNone)
295 // Is this the beginning of a basic block?
296 if (Pred->getLocation().getAs<BlockEntrance>())
299 // Is this on a non-expression?
300 if (!isa<Expr>(S.getStmt()))
303 // Run before processing a call.
304 if (CallEvent::isCallStmt(S.getStmt()))
307 // Is this an expression that is consumed by another expression? If so,
308 // postpone cleaning out the state.
309 ParentMap &PM = LC->getAnalysisDeclContext()->getParentMap();
310 return !PM.isConsumedExpr(cast<Expr>(S.getStmt()));
313 void ExprEngine::removeDead(ExplodedNode *Pred, ExplodedNodeSet &Out,
314 const Stmt *ReferenceStmt,
315 const LocationContext *LC,
316 const Stmt *DiagnosticStmt,
317 ProgramPoint::Kind K) {
318 assert((K == ProgramPoint::PreStmtPurgeDeadSymbolsKind ||
319 ReferenceStmt == 0 || isa<ReturnStmt>(ReferenceStmt))
320 && "PostStmt is not generally supported by the SymbolReaper yet");
321 assert(LC && "Must pass the current (or expiring) LocationContext");
323 if (!DiagnosticStmt) {
324 DiagnosticStmt = ReferenceStmt;
325 assert(DiagnosticStmt && "Required for clearing a LocationContext");
328 NumRemoveDeadBindings++;
329 ProgramStateRef CleanedState = Pred->getState();
331 // LC is the location context being destroyed, but SymbolReaper wants a
332 // location context that is still live. (If this is the top-level stack
333 // frame, this will be null.)
334 if (!ReferenceStmt) {
335 assert(K == ProgramPoint::PostStmtPurgeDeadSymbolsKind &&
336 "Use PostStmtPurgeDeadSymbolsKind for clearing a LocationContext");
337 LC = LC->getParent();
340 const StackFrameContext *SFC = LC ? LC->getCurrentStackFrame() : 0;
341 SymbolReaper SymReaper(SFC, ReferenceStmt, SymMgr, getStoreManager());
343 getCheckerManager().runCheckersForLiveSymbols(CleanedState, SymReaper);
345 // Create a state in which dead bindings are removed from the environment
346 // and the store. TODO: The function should just return new env and store,
348 CleanedState = StateMgr.removeDeadBindings(CleanedState, SFC, SymReaper);
350 // Process any special transfer function for dead symbols.
351 // A tag to track convenience transitions, which can be removed at cleanup.
352 static SimpleProgramPointTag cleanupTag("ExprEngine : Clean Node");
353 if (!SymReaper.hasDeadSymbols()) {
354 // Generate a CleanedNode that has the environment and store cleaned
355 // up. Since no symbols are dead, we can optimize and not clean out
356 // the constraint manager.
357 StmtNodeBuilder Bldr(Pred, Out, *currBldrCtx);
358 Bldr.generateNode(DiagnosticStmt, Pred, CleanedState, &cleanupTag, K);
361 // Call checkers with the non-cleaned state so that they could query the
362 // values of the soon to be dead symbols.
363 ExplodedNodeSet CheckedSet;
364 getCheckerManager().runCheckersForDeadSymbols(CheckedSet, Pred, SymReaper,
365 DiagnosticStmt, *this, K);
367 // For each node in CheckedSet, generate CleanedNodes that have the
368 // environment, the store, and the constraints cleaned up but have the
369 // user-supplied states as the predecessors.
370 StmtNodeBuilder Bldr(CheckedSet, Out, *currBldrCtx);
371 for (ExplodedNodeSet::const_iterator
372 I = CheckedSet.begin(), E = CheckedSet.end(); I != E; ++I) {
373 ProgramStateRef CheckerState = (*I)->getState();
375 // The constraint manager has not been cleaned up yet, so clean up now.
376 CheckerState = getConstraintManager().removeDeadBindings(CheckerState,
379 assert(StateMgr.haveEqualEnvironments(CheckerState, Pred->getState()) &&
380 "Checkers are not allowed to modify the Environment as a part of "
381 "checkDeadSymbols processing.");
382 assert(StateMgr.haveEqualStores(CheckerState, Pred->getState()) &&
383 "Checkers are not allowed to modify the Store as a part of "
384 "checkDeadSymbols processing.");
386 // Create a state based on CleanedState with CheckerState GDM and
387 // generate a transition to that state.
388 ProgramStateRef CleanedCheckerSt =
389 StateMgr.getPersistentStateWithGDM(CleanedState, CheckerState);
390 Bldr.generateNode(DiagnosticStmt, *I, CleanedCheckerSt, &cleanupTag, K);
395 void ExprEngine::ProcessStmt(const CFGStmt S,
396 ExplodedNode *Pred) {
397 // Reclaim any unnecessary nodes in the ExplodedGraph.
398 G.reclaimRecentlyAllocatedNodes();
400 const Stmt *currStmt = S.getStmt();
401 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
402 currStmt->getLocStart(),
403 "Error evaluating statement");
405 // Remove dead bindings and symbols.
406 ExplodedNodeSet CleanedStates;
407 if (shouldRemoveDeadBindings(AMgr, S, Pred, Pred->getLocationContext())){
408 removeDead(Pred, CleanedStates, currStmt, Pred->getLocationContext());
410 CleanedStates.Add(Pred);
412 // Visit the statement.
414 for (ExplodedNodeSet::iterator I = CleanedStates.begin(),
415 E = CleanedStates.end(); I != E; ++I) {
416 ExplodedNodeSet DstI;
417 // Visit the statement.
418 Visit(currStmt, *I, DstI);
422 // Enqueue the new nodes onto the work list.
423 Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
426 void ExprEngine::ProcessInitializer(const CFGInitializer Init,
427 ExplodedNode *Pred) {
428 const CXXCtorInitializer *BMI = Init.getInitializer();
430 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
431 BMI->getSourceLocation(),
432 "Error evaluating initializer");
434 // We don't clean up dead bindings here.
435 const StackFrameContext *stackFrame =
436 cast<StackFrameContext>(Pred->getLocationContext());
437 const CXXConstructorDecl *decl =
438 cast<CXXConstructorDecl>(stackFrame->getDecl());
440 ProgramStateRef State = Pred->getState();
441 SVal thisVal = State->getSVal(svalBuilder.getCXXThis(decl, stackFrame));
443 ExplodedNodeSet Tmp(Pred);
446 // Evaluate the initializer, if necessary
447 if (BMI->isAnyMemberInitializer()) {
448 // Constructors build the object directly in the field,
449 // but non-objects must be copied in from the initializer.
450 const Expr *Init = BMI->getInit()->IgnoreImplicit();
451 if (!isa<CXXConstructExpr>(Init)) {
452 const ValueDecl *Field;
453 if (BMI->isIndirectMemberInitializer()) {
454 Field = BMI->getIndirectMember();
455 FieldLoc = State->getLValue(BMI->getIndirectMember(), thisVal);
457 Field = BMI->getMember();
458 FieldLoc = State->getLValue(BMI->getMember(), thisVal);
462 if (BMI->getNumArrayIndices() > 0) {
463 // Handle arrays of trivial type. We can represent this with a
464 // primitive load/copy from the base array region.
465 const ArraySubscriptExpr *ASE;
466 while ((ASE = dyn_cast<ArraySubscriptExpr>(Init)))
467 Init = ASE->getBase()->IgnoreImplicit();
469 SVal LValue = State->getSVal(Init, stackFrame);
470 if (Optional<Loc> LValueLoc = LValue.getAs<Loc>())
471 InitVal = State->getSVal(*LValueLoc);
473 // If we fail to get the value for some reason, use a symbolic value.
474 if (InitVal.isUnknownOrUndef()) {
475 SValBuilder &SVB = getSValBuilder();
476 InitVal = SVB.conjureSymbolVal(BMI->getInit(), stackFrame,
478 currBldrCtx->blockCount());
481 InitVal = State->getSVal(BMI->getInit(), stackFrame);
484 assert(Tmp.size() == 1 && "have not generated any new nodes yet");
485 assert(*Tmp.begin() == Pred && "have not generated any new nodes yet");
488 PostInitializer PP(BMI, FieldLoc.getAsRegion(), stackFrame);
489 evalBind(Tmp, Init, Pred, FieldLoc, InitVal, /*isInit=*/true, &PP);
492 assert(BMI->isBaseInitializer() || BMI->isDelegatingInitializer());
493 // We already did all the work when visiting the CXXConstructExpr.
496 // Construct PostInitializer nodes whether the state changed or not,
497 // so that the diagnostics don't get confused.
498 PostInitializer PP(BMI, FieldLoc.getAsRegion(), stackFrame);
500 NodeBuilder Bldr(Tmp, Dst, *currBldrCtx);
501 for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I != E; ++I) {
502 ExplodedNode *N = *I;
503 Bldr.generateNode(PP, N->getState(), N);
506 // Enqueue the new nodes onto the work list.
507 Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
510 void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D,
511 ExplodedNode *Pred) {
513 switch (D.getKind()) {
514 case CFGElement::AutomaticObjectDtor:
515 ProcessAutomaticObjDtor(D.castAs<CFGAutomaticObjDtor>(), Pred, Dst);
517 case CFGElement::BaseDtor:
518 ProcessBaseDtor(D.castAs<CFGBaseDtor>(), Pred, Dst);
520 case CFGElement::MemberDtor:
521 ProcessMemberDtor(D.castAs<CFGMemberDtor>(), Pred, Dst);
523 case CFGElement::TemporaryDtor:
524 ProcessTemporaryDtor(D.castAs<CFGTemporaryDtor>(), Pred, Dst);
527 llvm_unreachable("Unexpected dtor kind.");
530 // Enqueue the new nodes onto the work list.
531 Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
534 void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor Dtor,
536 ExplodedNodeSet &Dst) {
537 const VarDecl *varDecl = Dtor.getVarDecl();
538 QualType varType = varDecl->getType();
540 ProgramStateRef state = Pred->getState();
541 SVal dest = state->getLValue(varDecl, Pred->getLocationContext());
542 const MemRegion *Region = dest.castAs<loc::MemRegionVal>().getRegion();
544 if (const ReferenceType *refType = varType->getAs<ReferenceType>()) {
545 varType = refType->getPointeeType();
546 Region = state->getSVal(Region).getAsRegion();
549 VisitCXXDestructor(varType, Region, Dtor.getTriggerStmt(), /*IsBase=*/ false,
553 void ExprEngine::ProcessBaseDtor(const CFGBaseDtor D,
554 ExplodedNode *Pred, ExplodedNodeSet &Dst) {
555 const LocationContext *LCtx = Pred->getLocationContext();
556 ProgramStateRef State = Pred->getState();
558 const CXXDestructorDecl *CurDtor = cast<CXXDestructorDecl>(LCtx->getDecl());
559 Loc ThisPtr = getSValBuilder().getCXXThis(CurDtor,
560 LCtx->getCurrentStackFrame());
561 SVal ThisVal = Pred->getState()->getSVal(ThisPtr);
563 // Create the base object region.
564 const CXXBaseSpecifier *Base = D.getBaseSpecifier();
565 QualType BaseTy = Base->getType();
566 SVal BaseVal = getStoreManager().evalDerivedToBase(ThisVal, BaseTy,
569 VisitCXXDestructor(BaseTy, BaseVal.castAs<loc::MemRegionVal>().getRegion(),
570 CurDtor->getBody(), /*IsBase=*/ true, Pred, Dst);
573 void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D,
574 ExplodedNode *Pred, ExplodedNodeSet &Dst) {
575 const FieldDecl *Member = D.getFieldDecl();
576 ProgramStateRef State = Pred->getState();
577 const LocationContext *LCtx = Pred->getLocationContext();
579 const CXXDestructorDecl *CurDtor = cast<CXXDestructorDecl>(LCtx->getDecl());
580 Loc ThisVal = getSValBuilder().getCXXThis(CurDtor,
581 LCtx->getCurrentStackFrame());
583 State->getLValue(Member, State->getSVal(ThisVal).castAs<Loc>());
585 VisitCXXDestructor(Member->getType(),
586 FieldVal.castAs<loc::MemRegionVal>().getRegion(),
587 CurDtor->getBody(), /*IsBase=*/false, Pred, Dst);
590 void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D,
592 ExplodedNodeSet &Dst) {}
594 void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred,
595 ExplodedNodeSet &DstTop) {
596 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
598 "Error evaluating statement");
600 StmtNodeBuilder Bldr(Pred, DstTop, *currBldrCtx);
602 assert(!isa<Expr>(S) || S == cast<Expr>(S)->IgnoreParens());
604 switch (S->getStmtClass()) {
605 // C++ and ARC stuff we don't support yet.
606 case Expr::ObjCIndirectCopyRestoreExprClass:
607 case Stmt::CXXDefaultInitExprClass:
608 case Stmt::CXXDependentScopeMemberExprClass:
609 case Stmt::CXXPseudoDestructorExprClass:
610 case Stmt::CXXTryStmtClass:
611 case Stmt::CXXTypeidExprClass:
612 case Stmt::CXXUuidofExprClass:
613 case Stmt::MSPropertyRefExprClass:
614 case Stmt::CXXUnresolvedConstructExprClass:
615 case Stmt::DependentScopeDeclRefExprClass:
616 case Stmt::UnaryTypeTraitExprClass:
617 case Stmt::BinaryTypeTraitExprClass:
618 case Stmt::TypeTraitExprClass:
619 case Stmt::ArrayTypeTraitExprClass:
620 case Stmt::ExpressionTraitExprClass:
621 case Stmt::UnresolvedLookupExprClass:
622 case Stmt::UnresolvedMemberExprClass:
623 case Stmt::CXXNoexceptExprClass:
624 case Stmt::PackExpansionExprClass:
625 case Stmt::SubstNonTypeTemplateParmPackExprClass:
626 case Stmt::FunctionParmPackExprClass:
627 case Stmt::SEHTryStmtClass:
628 case Stmt::SEHExceptStmtClass:
629 case Stmt::LambdaExprClass:
630 case Stmt::SEHFinallyStmtClass: {
631 const ExplodedNode *node = Bldr.generateSink(S, Pred, Pred->getState());
632 Engine.addAbortedBlock(node, currBldrCtx->getBlock());
636 case Stmt::ParenExprClass:
637 llvm_unreachable("ParenExprs already handled.");
638 case Stmt::GenericSelectionExprClass:
639 llvm_unreachable("GenericSelectionExprs already handled.");
640 // Cases that should never be evaluated simply because they shouldn't
641 // appear in the CFG.
642 case Stmt::BreakStmtClass:
643 case Stmt::CaseStmtClass:
644 case Stmt::CompoundStmtClass:
645 case Stmt::ContinueStmtClass:
646 case Stmt::CXXForRangeStmtClass:
647 case Stmt::DefaultStmtClass:
648 case Stmt::DoStmtClass:
649 case Stmt::ForStmtClass:
650 case Stmt::GotoStmtClass:
651 case Stmt::IfStmtClass:
652 case Stmt::IndirectGotoStmtClass:
653 case Stmt::LabelStmtClass:
654 case Stmt::AttributedStmtClass:
655 case Stmt::NoStmtClass:
656 case Stmt::NullStmtClass:
657 case Stmt::SwitchStmtClass:
658 case Stmt::WhileStmtClass:
659 case Expr::MSDependentExistsStmtClass:
660 case Stmt::CapturedStmtClass:
661 llvm_unreachable("Stmt should not be in analyzer evaluation loop");
663 case Stmt::ObjCSubscriptRefExprClass:
664 case Stmt::ObjCPropertyRefExprClass:
665 llvm_unreachable("These are handled by PseudoObjectExpr");
667 case Stmt::GNUNullExprClass: {
668 // GNU __null is a pointer-width integer, not an actual pointer.
669 ProgramStateRef state = Pred->getState();
670 state = state->BindExpr(S, Pred->getLocationContext(),
671 svalBuilder.makeIntValWithPtrWidth(0, false));
672 Bldr.generateNode(S, Pred, state);
676 case Stmt::ObjCAtSynchronizedStmtClass:
677 Bldr.takeNodes(Pred);
678 VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S), Pred, Dst);
682 case Stmt::ExprWithCleanupsClass:
683 // Handled due to fully linearised CFG.
686 // Cases not handled yet; but will handle some day.
687 case Stmt::DesignatedInitExprClass:
688 case Stmt::ExtVectorElementExprClass:
689 case Stmt::ImaginaryLiteralClass:
690 case Stmt::ObjCAtCatchStmtClass:
691 case Stmt::ObjCAtFinallyStmtClass:
692 case Stmt::ObjCAtTryStmtClass:
693 case Stmt::ObjCAutoreleasePoolStmtClass:
694 case Stmt::ObjCEncodeExprClass:
695 case Stmt::ObjCIsaExprClass:
696 case Stmt::ObjCProtocolExprClass:
697 case Stmt::ObjCSelectorExprClass:
698 case Stmt::ParenListExprClass:
699 case Stmt::PredefinedExprClass:
700 case Stmt::ShuffleVectorExprClass:
701 case Stmt::VAArgExprClass:
702 case Stmt::CUDAKernelCallExprClass:
703 case Stmt::OpaqueValueExprClass:
704 case Stmt::AsTypeExprClass:
705 case Stmt::AtomicExprClass:
708 // Cases we intentionally don't evaluate, since they don't need
709 // to be explicitly evaluated.
710 case Stmt::AddrLabelExprClass:
711 case Stmt::IntegerLiteralClass:
712 case Stmt::CharacterLiteralClass:
713 case Stmt::ImplicitValueInitExprClass:
714 case Stmt::CXXScalarValueInitExprClass:
715 case Stmt::CXXBoolLiteralExprClass:
716 case Stmt::ObjCBoolLiteralExprClass:
717 case Stmt::FloatingLiteralClass:
718 case Stmt::SizeOfPackExprClass:
719 case Stmt::StringLiteralClass:
720 case Stmt::ObjCStringLiteralClass:
721 case Stmt::CXXBindTemporaryExprClass:
722 case Stmt::SubstNonTypeTemplateParmExprClass:
723 case Stmt::CXXNullPtrLiteralExprClass: {
724 Bldr.takeNodes(Pred);
725 ExplodedNodeSet preVisit;
726 getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this);
727 getCheckerManager().runCheckersForPostStmt(Dst, preVisit, S, *this);
732 case Stmt::CXXDefaultArgExprClass: {
733 Bldr.takeNodes(Pred);
734 ExplodedNodeSet PreVisit;
735 getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
738 StmtNodeBuilder Bldr2(PreVisit, Tmp, *currBldrCtx);
740 const LocationContext *LCtx = Pred->getLocationContext();
741 const CXXDefaultArgExpr *DefaultE = cast<CXXDefaultArgExpr>(S);
742 const Expr *ArgE = DefaultE->getExpr();
744 bool IsTemporary = false;
745 if (const MaterializeTemporaryExpr *MTE =
746 dyn_cast<MaterializeTemporaryExpr>(ArgE)) {
747 ArgE = MTE->GetTemporaryExpr();
751 Optional<SVal> ConstantVal = svalBuilder.getConstantVal(ArgE);
753 ConstantVal = UnknownVal();
755 for (ExplodedNodeSet::iterator I = PreVisit.begin(), E = PreVisit.end();
757 ProgramStateRef State = (*I)->getState();
758 State = State->BindExpr(DefaultE, LCtx, *ConstantVal);
760 State = createTemporaryRegionIfNeeded(State, LCtx, DefaultE,
762 Bldr2.generateNode(S, *I, State);
765 getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this);
770 case Expr::ObjCArrayLiteralClass:
771 case Expr::ObjCDictionaryLiteralClass:
772 // FIXME: explicitly model with a region and the actual contents
773 // of the container. For now, conjure a symbol.
774 case Expr::ObjCBoxedExprClass: {
775 Bldr.takeNodes(Pred);
777 ExplodedNodeSet preVisit;
778 getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this);
781 StmtNodeBuilder Bldr2(preVisit, Tmp, *currBldrCtx);
783 const Expr *Ex = cast<Expr>(S);
784 QualType resultType = Ex->getType();
786 for (ExplodedNodeSet::iterator it = preVisit.begin(), et = preVisit.end();
788 ExplodedNode *N = *it;
789 const LocationContext *LCtx = N->getLocationContext();
790 SVal result = svalBuilder.conjureSymbolVal(0, Ex, LCtx, resultType,
791 currBldrCtx->blockCount());
792 ProgramStateRef state = N->getState()->BindExpr(Ex, LCtx, result);
793 Bldr2.generateNode(S, N, state);
796 getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this);
801 case Stmt::ArraySubscriptExprClass:
802 Bldr.takeNodes(Pred);
803 VisitLvalArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Pred, Dst);
807 case Stmt::GCCAsmStmtClass:
808 Bldr.takeNodes(Pred);
809 VisitGCCAsmStmt(cast<GCCAsmStmt>(S), Pred, Dst);
813 case Stmt::MSAsmStmtClass:
814 Bldr.takeNodes(Pred);
815 VisitMSAsmStmt(cast<MSAsmStmt>(S), Pred, Dst);
819 case Stmt::BlockExprClass:
820 Bldr.takeNodes(Pred);
821 VisitBlockExpr(cast<BlockExpr>(S), Pred, Dst);
825 case Stmt::BinaryOperatorClass: {
826 const BinaryOperator* B = cast<BinaryOperator>(S);
827 if (B->isLogicalOp()) {
828 Bldr.takeNodes(Pred);
829 VisitLogicalExpr(B, Pred, Dst);
833 else if (B->getOpcode() == BO_Comma) {
834 ProgramStateRef state = Pred->getState();
835 Bldr.generateNode(B, Pred,
836 state->BindExpr(B, Pred->getLocationContext(),
837 state->getSVal(B->getRHS(),
838 Pred->getLocationContext())));
842 Bldr.takeNodes(Pred);
844 if (AMgr.options.eagerlyAssumeBinOpBifurcation &&
845 (B->isRelationalOp() || B->isEqualityOp())) {
847 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Tmp);
848 evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, cast<Expr>(S));
851 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
857 case Stmt::CXXOperatorCallExprClass: {
858 const CXXOperatorCallExpr *OCE = cast<CXXOperatorCallExpr>(S);
860 // For instance method operators, make sure the 'this' argument has a
862 const Decl *Callee = OCE->getCalleeDecl();
863 if (const CXXMethodDecl *MD = dyn_cast_or_null<CXXMethodDecl>(Callee)) {
864 if (MD->isInstance()) {
865 ProgramStateRef State = Pred->getState();
866 const LocationContext *LCtx = Pred->getLocationContext();
867 ProgramStateRef NewState =
868 createTemporaryRegionIfNeeded(State, LCtx, OCE->getArg(0));
869 if (NewState != State) {
870 Pred = Bldr.generateNode(OCE, Pred, NewState, /*Tag=*/0,
871 ProgramPoint::PreStmtKind);
880 case Stmt::CallExprClass:
881 case Stmt::CXXMemberCallExprClass:
882 case Stmt::UserDefinedLiteralClass: {
883 Bldr.takeNodes(Pred);
884 VisitCallExpr(cast<CallExpr>(S), Pred, Dst);
889 case Stmt::CXXCatchStmtClass: {
890 Bldr.takeNodes(Pred);
891 VisitCXXCatchStmt(cast<CXXCatchStmt>(S), Pred, Dst);
896 case Stmt::CXXTemporaryObjectExprClass:
897 case Stmt::CXXConstructExprClass: {
898 Bldr.takeNodes(Pred);
899 VisitCXXConstructExpr(cast<CXXConstructExpr>(S), Pred, Dst);
904 case Stmt::CXXNewExprClass: {
905 Bldr.takeNodes(Pred);
906 ExplodedNodeSet PostVisit;
907 VisitCXXNewExpr(cast<CXXNewExpr>(S), Pred, PostVisit);
908 getCheckerManager().runCheckersForPostStmt(Dst, PostVisit, S, *this);
913 case Stmt::CXXDeleteExprClass: {
914 Bldr.takeNodes(Pred);
915 ExplodedNodeSet PreVisit;
916 const CXXDeleteExpr *CDE = cast<CXXDeleteExpr>(S);
917 getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
919 for (ExplodedNodeSet::iterator i = PreVisit.begin(),
920 e = PreVisit.end(); i != e ; ++i)
921 VisitCXXDeleteExpr(CDE, *i, Dst);
926 // FIXME: ChooseExpr is really a constant. We need to fix
927 // the CFG do not model them as explicit control-flow.
929 case Stmt::ChooseExprClass: { // __builtin_choose_expr
930 Bldr.takeNodes(Pred);
931 const ChooseExpr *C = cast<ChooseExpr>(S);
932 VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst);
937 case Stmt::CompoundAssignOperatorClass:
938 Bldr.takeNodes(Pred);
939 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
943 case Stmt::CompoundLiteralExprClass:
944 Bldr.takeNodes(Pred);
945 VisitCompoundLiteralExpr(cast<CompoundLiteralExpr>(S), Pred, Dst);
949 case Stmt::BinaryConditionalOperatorClass:
950 case Stmt::ConditionalOperatorClass: { // '?' operator
951 Bldr.takeNodes(Pred);
952 const AbstractConditionalOperator *C
953 = cast<AbstractConditionalOperator>(S);
954 VisitGuardedExpr(C, C->getTrueExpr(), C->getFalseExpr(), Pred, Dst);
959 case Stmt::CXXThisExprClass:
960 Bldr.takeNodes(Pred);
961 VisitCXXThisExpr(cast<CXXThisExpr>(S), Pred, Dst);
965 case Stmt::DeclRefExprClass: {
966 Bldr.takeNodes(Pred);
967 const DeclRefExpr *DE = cast<DeclRefExpr>(S);
968 VisitCommonDeclRefExpr(DE, DE->getDecl(), Pred, Dst);
973 case Stmt::DeclStmtClass:
974 Bldr.takeNodes(Pred);
975 VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst);
979 case Stmt::ImplicitCastExprClass:
980 case Stmt::CStyleCastExprClass:
981 case Stmt::CXXStaticCastExprClass:
982 case Stmt::CXXDynamicCastExprClass:
983 case Stmt::CXXReinterpretCastExprClass:
984 case Stmt::CXXConstCastExprClass:
985 case Stmt::CXXFunctionalCastExprClass:
986 case Stmt::ObjCBridgedCastExprClass: {
987 Bldr.takeNodes(Pred);
988 const CastExpr *C = cast<CastExpr>(S);
989 // Handle the previsit checks.
990 ExplodedNodeSet dstPrevisit;
991 getCheckerManager().runCheckersForPreStmt(dstPrevisit, Pred, C, *this);
993 // Handle the expression itself.
994 ExplodedNodeSet dstExpr;
995 for (ExplodedNodeSet::iterator i = dstPrevisit.begin(),
996 e = dstPrevisit.end(); i != e ; ++i) {
997 VisitCast(C, C->getSubExpr(), *i, dstExpr);
1000 // Handle the postvisit checks.
1001 getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, C, *this);
1006 case Expr::MaterializeTemporaryExprClass: {
1007 Bldr.takeNodes(Pred);
1008 const MaterializeTemporaryExpr *MTE = cast<MaterializeTemporaryExpr>(S);
1009 CreateCXXTemporaryObject(MTE, Pred, Dst);
1014 case Stmt::InitListExprClass:
1015 Bldr.takeNodes(Pred);
1016 VisitInitListExpr(cast<InitListExpr>(S), Pred, Dst);
1020 case Stmt::MemberExprClass:
1021 Bldr.takeNodes(Pred);
1022 VisitMemberExpr(cast<MemberExpr>(S), Pred, Dst);
1026 case Stmt::ObjCIvarRefExprClass:
1027 Bldr.takeNodes(Pred);
1028 VisitLvalObjCIvarRefExpr(cast<ObjCIvarRefExpr>(S), Pred, Dst);
1032 case Stmt::ObjCForCollectionStmtClass:
1033 Bldr.takeNodes(Pred);
1034 VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S), Pred, Dst);
1038 case Stmt::ObjCMessageExprClass:
1039 Bldr.takeNodes(Pred);
1040 VisitObjCMessage(cast<ObjCMessageExpr>(S), Pred, Dst);
1044 case Stmt::ObjCAtThrowStmtClass:
1045 case Stmt::CXXThrowExprClass:
1046 // FIXME: This is not complete. We basically treat @throw as
1048 Bldr.generateSink(S, Pred, Pred->getState());
1051 case Stmt::ReturnStmtClass:
1052 Bldr.takeNodes(Pred);
1053 VisitReturnStmt(cast<ReturnStmt>(S), Pred, Dst);
1057 case Stmt::OffsetOfExprClass:
1058 Bldr.takeNodes(Pred);
1059 VisitOffsetOfExpr(cast<OffsetOfExpr>(S), Pred, Dst);
1063 case Stmt::UnaryExprOrTypeTraitExprClass:
1064 Bldr.takeNodes(Pred);
1065 VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S),
1070 case Stmt::StmtExprClass: {
1071 const StmtExpr *SE = cast<StmtExpr>(S);
1073 if (SE->getSubStmt()->body_empty()) {
1074 // Empty statement expression.
1075 assert(SE->getType() == getContext().VoidTy
1076 && "Empty statement expression must have void type.");
1080 if (Expr *LastExpr = dyn_cast<Expr>(*SE->getSubStmt()->body_rbegin())) {
1081 ProgramStateRef state = Pred->getState();
1082 Bldr.generateNode(SE, Pred,
1083 state->BindExpr(SE, Pred->getLocationContext(),
1084 state->getSVal(LastExpr,
1085 Pred->getLocationContext())));
1090 case Stmt::UnaryOperatorClass: {
1091 Bldr.takeNodes(Pred);
1092 const UnaryOperator *U = cast<UnaryOperator>(S);
1093 if (AMgr.options.eagerlyAssumeBinOpBifurcation && (U->getOpcode() == UO_LNot)) {
1094 ExplodedNodeSet Tmp;
1095 VisitUnaryOperator(U, Pred, Tmp);
1096 evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, U);
1099 VisitUnaryOperator(U, Pred, Dst);
1104 case Stmt::PseudoObjectExprClass: {
1105 Bldr.takeNodes(Pred);
1106 ProgramStateRef state = Pred->getState();
1107 const PseudoObjectExpr *PE = cast<PseudoObjectExpr>(S);
1108 if (const Expr *Result = PE->getResultExpr()) {
1109 SVal V = state->getSVal(Result, Pred->getLocationContext());
1110 Bldr.generateNode(S, Pred,
1111 state->BindExpr(S, Pred->getLocationContext(), V));
1114 Bldr.generateNode(S, Pred,
1115 state->BindExpr(S, Pred->getLocationContext(),
1124 bool ExprEngine::replayWithoutInlining(ExplodedNode *N,
1125 const LocationContext *CalleeLC) {
1126 const StackFrameContext *CalleeSF = CalleeLC->getCurrentStackFrame();
1127 const StackFrameContext *CallerSF = CalleeSF->getParent()->getCurrentStackFrame();
1128 assert(CalleeSF && CallerSF);
1129 ExplodedNode *BeforeProcessingCall = 0;
1130 const Stmt *CE = CalleeSF->getCallSite();
1132 // Find the first node before we started processing the call expression.
1134 ProgramPoint L = N->getLocation();
1135 BeforeProcessingCall = N;
1136 N = N->pred_empty() ? NULL : *(N->pred_begin());
1138 // Skip the nodes corresponding to the inlined code.
1139 if (L.getLocationContext()->getCurrentStackFrame() != CallerSF)
1141 // We reached the caller. Find the node right before we started
1142 // processing the call.
1143 if (L.isPurgeKind())
1145 if (L.getAs<PreImplicitCall>())
1147 if (L.getAs<CallEnter>())
1149 if (Optional<StmtPoint> SP = L.getAs<StmtPoint>())
1150 if (SP->getStmt() == CE)
1155 if (!BeforeProcessingCall)
1158 // TODO: Clean up the unneeded nodes.
1160 // Build an Epsilon node from which we will restart the analyzes.
1161 // Note that CE is permitted to be NULL!
1162 ProgramPoint NewNodeLoc =
1163 EpsilonPoint(BeforeProcessingCall->getLocationContext(), CE);
1164 // Add the special flag to GDM to signal retrying with no inlining.
1165 // Note, changing the state ensures that we are not going to cache out.
1166 ProgramStateRef NewNodeState = BeforeProcessingCall->getState();
1168 NewNodeState->set<ReplayWithoutInlining>(const_cast<Stmt *>(CE));
1170 // Make the new node a successor of BeforeProcessingCall.
1172 ExplodedNode *NewNode = G.getNode(NewNodeLoc, NewNodeState, false, &IsNew);
1173 // We cached out at this point. Caching out is common due to us backtracking
1174 // from the inlined function, which might spawn several paths.
1178 NewNode->addPredecessor(BeforeProcessingCall, G);
1180 // Add the new node to the work list.
1181 Engine.enqueueStmtNode(NewNode, CalleeSF->getCallSiteBlock(),
1182 CalleeSF->getIndex());
1183 NumTimesRetriedWithoutInlining++;
1187 /// Block entrance. (Update counters).
1188 void ExprEngine::processCFGBlockEntrance(const BlockEdge &L,
1189 NodeBuilderWithSinks &nodeBuilder,
1190 ExplodedNode *Pred) {
1192 // FIXME: Refactor this into a checker.
1193 if (nodeBuilder.getContext().blockCount() >= AMgr.options.maxBlockVisitOnPath) {
1194 static SimpleProgramPointTag tag("ExprEngine : Block count exceeded");
1195 const ExplodedNode *Sink =
1196 nodeBuilder.generateSink(Pred->getState(), Pred, &tag);
1198 // Check if we stopped at the top level function or not.
1199 // Root node should have the location context of the top most function.
1200 const LocationContext *CalleeLC = Pred->getLocation().getLocationContext();
1201 const LocationContext *CalleeSF = CalleeLC->getCurrentStackFrame();
1202 const LocationContext *RootLC =
1203 (*G.roots_begin())->getLocation().getLocationContext();
1204 if (RootLC->getCurrentStackFrame() != CalleeSF) {
1205 Engine.FunctionSummaries->markReachedMaxBlockCount(CalleeSF->getDecl());
1207 // Re-run the call evaluation without inlining it, by storing the
1208 // no-inlining policy in the state and enqueuing the new work item on
1209 // the list. Replay should almost never fail. Use the stats to catch it
1211 if ((!AMgr.options.NoRetryExhausted &&
1212 replayWithoutInlining(Pred, CalleeLC)))
1214 NumMaxBlockCountReachedInInlined++;
1216 NumMaxBlockCountReached++;
1218 // Make sink nodes as exhausted(for stats) only if retry failed.
1219 Engine.blocksExhausted.push_back(std::make_pair(L, Sink));
1223 //===----------------------------------------------------------------------===//
1224 // Branch processing.
1225 //===----------------------------------------------------------------------===//
1227 /// RecoverCastedSymbol - A helper function for ProcessBranch that is used
1228 /// to try to recover some path-sensitivity for casts of symbolic
1229 /// integers that promote their values (which are currently not tracked well).
1230 /// This function returns the SVal bound to Condition->IgnoreCasts if all the
1231 // cast(s) did was sign-extend the original value.
1232 static SVal RecoverCastedSymbol(ProgramStateManager& StateMgr,
1233 ProgramStateRef state,
1234 const Stmt *Condition,
1235 const LocationContext *LCtx,
1238 const Expr *Ex = dyn_cast<Expr>(Condition);
1240 return UnknownVal();
1243 bool bitsInit = false;
1245 while (const CastExpr *CE = dyn_cast<CastExpr>(Ex)) {
1246 QualType T = CE->getType();
1248 if (!T->isIntegralOrEnumerationType())
1249 return UnknownVal();
1251 uint64_t newBits = Ctx.getTypeSize(T);
1252 if (!bitsInit || newBits < bits) {
1257 Ex = CE->getSubExpr();
1260 // We reached a non-cast. Is it a symbolic value?
1261 QualType T = Ex->getType();
1263 if (!bitsInit || !T->isIntegralOrEnumerationType() ||
1264 Ctx.getTypeSize(T) > bits)
1265 return UnknownVal();
1267 return state->getSVal(Ex, LCtx);
1270 static const Stmt *ResolveCondition(const Stmt *Condition,
1271 const CFGBlock *B) {
1272 if (const Expr *Ex = dyn_cast<Expr>(Condition))
1273 Condition = Ex->IgnoreParens();
1275 const BinaryOperator *BO = dyn_cast<BinaryOperator>(Condition);
1276 if (!BO || !BO->isLogicalOp())
1279 // For logical operations, we still have the case where some branches
1280 // use the traditional "merge" approach and others sink the branch
1281 // directly into the basic blocks representing the logical operation.
1282 // We need to distinguish between those two cases here.
1284 // The invariants are still shifting, but it is possible that the
1285 // last element in a CFGBlock is not a CFGStmt. Look for the last
1286 // CFGStmt as the value of the condition.
1287 CFGBlock::const_reverse_iterator I = B->rbegin(), E = B->rend();
1288 for (; I != E; ++I) {
1289 CFGElement Elem = *I;
1290 Optional<CFGStmt> CS = Elem.getAs<CFGStmt>();
1293 if (CS->getStmt() != Condition)
1301 BO = dyn_cast<BinaryOperator>(Condition);
1302 if (!BO || !BO->isLogicalOp())
1304 Condition = BO->getRHS()->IgnoreParens();
1306 llvm_unreachable("could not resolve condition");
1309 void ExprEngine::processBranch(const Stmt *Condition, const Stmt *Term,
1310 NodeBuilderContext& BldCtx,
1312 ExplodedNodeSet &Dst,
1313 const CFGBlock *DstT,
1314 const CFGBlock *DstF) {
1315 currBldrCtx = &BldCtx;
1317 // Check for NULL conditions; e.g. "for(;;)"
1319 BranchNodeBuilder NullCondBldr(Pred, Dst, BldCtx, DstT, DstF);
1320 NullCondBldr.markInfeasible(false);
1321 NullCondBldr.generateNode(Pred->getState(), true, Pred);
1326 // Resolve the condition in the precense of nested '||' and '&&'.
1327 if (const Expr *Ex = dyn_cast<Expr>(Condition))
1328 Condition = Ex->IgnoreParens();
1330 Condition = ResolveCondition(Condition, BldCtx.getBlock());
1331 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
1332 Condition->getLocStart(),
1333 "Error evaluating branch");
1335 ExplodedNodeSet CheckersOutSet;
1336 getCheckerManager().runCheckersForBranchCondition(Condition, CheckersOutSet,
1338 // We generated only sinks.
1339 if (CheckersOutSet.empty())
1342 BranchNodeBuilder builder(CheckersOutSet, Dst, BldCtx, DstT, DstF);
1343 for (NodeBuilder::iterator I = CheckersOutSet.begin(),
1344 E = CheckersOutSet.end(); E != I; ++I) {
1345 ExplodedNode *PredI = *I;
1347 if (PredI->isSink())
1350 ProgramStateRef PrevState = PredI->getState();
1351 SVal X = PrevState->getSVal(Condition, PredI->getLocationContext());
1353 if (X.isUnknownOrUndef()) {
1354 // Give it a chance to recover from unknown.
1355 if (const Expr *Ex = dyn_cast<Expr>(Condition)) {
1356 if (Ex->getType()->isIntegralOrEnumerationType()) {
1357 // Try to recover some path-sensitivity. Right now casts of symbolic
1358 // integers that promote their values are currently not tracked well.
1359 // If 'Condition' is such an expression, try and recover the
1360 // underlying value and use that instead.
1361 SVal recovered = RecoverCastedSymbol(getStateManager(),
1362 PrevState, Condition,
1363 PredI->getLocationContext(),
1366 if (!recovered.isUnknown()) {
1373 // If the condition is still unknown, give up.
1374 if (X.isUnknownOrUndef()) {
1375 builder.generateNode(PrevState, true, PredI);
1376 builder.generateNode(PrevState, false, PredI);
1380 DefinedSVal V = X.castAs<DefinedSVal>();
1382 ProgramStateRef StTrue, StFalse;
1383 tie(StTrue, StFalse) = PrevState->assume(V);
1385 // Process the true branch.
1386 if (builder.isFeasible(true)) {
1388 builder.generateNode(StTrue, true, PredI);
1390 builder.markInfeasible(true);
1393 // Process the false branch.
1394 if (builder.isFeasible(false)) {
1396 builder.generateNode(StFalse, false, PredI);
1398 builder.markInfeasible(false);
1404 /// The GDM component containing the set of global variables which have been
1405 /// previously initialized with explicit initializers.
1406 REGISTER_TRAIT_WITH_PROGRAMSTATE(InitializedGlobalsSet,
1407 llvm::ImmutableSet<const VarDecl *>)
1409 void ExprEngine::processStaticInitializer(const DeclStmt *DS,
1410 NodeBuilderContext &BuilderCtx,
1412 clang::ento::ExplodedNodeSet &Dst,
1413 const CFGBlock *DstT,
1414 const CFGBlock *DstF) {
1415 currBldrCtx = &BuilderCtx;
1417 const VarDecl *VD = cast<VarDecl>(DS->getSingleDecl());
1418 ProgramStateRef state = Pred->getState();
1419 bool initHasRun = state->contains<InitializedGlobalsSet>(VD);
1420 BranchNodeBuilder builder(Pred, Dst, BuilderCtx, DstT, DstF);
1423 state = state->add<InitializedGlobalsSet>(VD);
1426 builder.generateNode(state, initHasRun, Pred);
1427 builder.markInfeasible(!initHasRun);
1432 /// processIndirectGoto - Called by CoreEngine. Used to generate successor
1433 /// nodes by processing the 'effects' of a computed goto jump.
1434 void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) {
1436 ProgramStateRef state = builder.getState();
1437 SVal V = state->getSVal(builder.getTarget(), builder.getLocationContext());
1439 // Three possibilities:
1441 // (1) We know the computed label.
1442 // (2) The label is NULL (or some other constant), or Undefined.
1443 // (3) We have no clue about the label. Dispatch to all targets.
1446 typedef IndirectGotoNodeBuilder::iterator iterator;
1448 if (Optional<loc::GotoLabel> LV = V.getAs<loc::GotoLabel>()) {
1449 const LabelDecl *L = LV->getLabel();
1451 for (iterator I = builder.begin(), E = builder.end(); I != E; ++I) {
1452 if (I.getLabel() == L) {
1453 builder.generateNode(I, state);
1458 llvm_unreachable("No block with label.");
1461 if (V.getAs<loc::ConcreteInt>() || V.getAs<UndefinedVal>()) {
1462 // Dispatch to the first target and mark it as a sink.
1463 //ExplodedNode* N = builder.generateNode(builder.begin(), state, true);
1464 // FIXME: add checker visit.
1465 // UndefBranches.insert(N);
1469 // This is really a catch-all. We don't support symbolics yet.
1470 // FIXME: Implement dispatch for symbolic pointers.
1472 for (iterator I=builder.begin(), E=builder.end(); I != E; ++I)
1473 builder.generateNode(I, state);
1476 /// ProcessEndPath - Called by CoreEngine. Used to generate end-of-path
1477 /// nodes when the control reaches the end of a function.
1478 void ExprEngine::processEndOfFunction(NodeBuilderContext& BC,
1479 ExplodedNode *Pred) {
1480 StateMgr.EndPath(Pred->getState());
1482 ExplodedNodeSet Dst;
1483 if (Pred->getLocationContext()->inTopFrame()) {
1484 // Remove dead symbols.
1485 ExplodedNodeSet AfterRemovedDead;
1486 removeDeadOnEndOfFunction(BC, Pred, AfterRemovedDead);
1489 for (ExplodedNodeSet::iterator I = AfterRemovedDead.begin(),
1490 E = AfterRemovedDead.end(); I != E; ++I) {
1491 getCheckerManager().runCheckersForEndFunction(BC, Dst, *I, *this);
1494 getCheckerManager().runCheckersForEndFunction(BC, Dst, Pred, *this);
1497 Engine.enqueueEndOfFunction(Dst);
1500 /// ProcessSwitch - Called by CoreEngine. Used to generate successor
1501 /// nodes by processing the 'effects' of a switch statement.
1502 void ExprEngine::processSwitch(SwitchNodeBuilder& builder) {
1503 typedef SwitchNodeBuilder::iterator iterator;
1504 ProgramStateRef state = builder.getState();
1505 const Expr *CondE = builder.getCondition();
1506 SVal CondV_untested = state->getSVal(CondE, builder.getLocationContext());
1508 if (CondV_untested.isUndef()) {
1509 //ExplodedNode* N = builder.generateDefaultCaseNode(state, true);
1510 // FIXME: add checker
1511 //UndefBranches.insert(N);
1515 DefinedOrUnknownSVal CondV = CondV_untested.castAs<DefinedOrUnknownSVal>();
1517 ProgramStateRef DefaultSt = state;
1519 iterator I = builder.begin(), EI = builder.end();
1520 bool defaultIsFeasible = I == EI;
1522 for ( ; I != EI; ++I) {
1523 // Successor may be pruned out during CFG construction.
1527 const CaseStmt *Case = I.getCase();
1529 // Evaluate the LHS of the case value.
1530 llvm::APSInt V1 = Case->getLHS()->EvaluateKnownConstInt(getContext());
1531 assert(V1.getBitWidth() == getContext().getTypeSize(CondE->getType()));
1533 // Get the RHS of the case, if it exists.
1535 if (const Expr *E = Case->getRHS())
1536 V2 = E->EvaluateKnownConstInt(getContext());
1540 // FIXME: Eventually we should replace the logic below with a range
1541 // comparison, rather than concretize the values within the range.
1542 // This should be easy once we have "ranges" for NonLVals.
1545 nonloc::ConcreteInt CaseVal(getBasicVals().getValue(V1));
1546 DefinedOrUnknownSVal Res = svalBuilder.evalEQ(DefaultSt ? DefaultSt : state,
1549 // Now "assume" that the case matches.
1550 if (ProgramStateRef stateNew = state->assume(Res, true)) {
1551 builder.generateCaseStmtNode(I, stateNew);
1553 // If CondV evaluates to a constant, then we know that this
1554 // is the *only* case that we can take, so stop evaluating the
1556 if (CondV.getAs<nonloc::ConcreteInt>())
1560 // Now "assume" that the case doesn't match. Add this state
1561 // to the default state (if it is feasible).
1563 if (ProgramStateRef stateNew = DefaultSt->assume(Res, false)) {
1564 defaultIsFeasible = true;
1565 DefaultSt = stateNew;
1568 defaultIsFeasible = false;
1573 // Concretize the next value in the range.
1583 if (!defaultIsFeasible)
1586 // If we have switch(enum value), the default branch is not
1587 // feasible if all of the enum constants not covered by 'case:' statements
1588 // are not feasible values for the switch condition.
1590 // Note that this isn't as accurate as it could be. Even if there isn't
1591 // a case for a particular enum value as long as that enum value isn't
1592 // feasible then it shouldn't be considered for making 'default:' reachable.
1593 const SwitchStmt *SS = builder.getSwitch();
1594 const Expr *CondExpr = SS->getCond()->IgnoreParenImpCasts();
1595 if (CondExpr->getType()->getAs<EnumType>()) {
1596 if (SS->isAllEnumCasesCovered())
1600 builder.generateDefaultCaseNode(DefaultSt);
1603 //===----------------------------------------------------------------------===//
1604 // Transfer functions: Loads and stores.
1605 //===----------------------------------------------------------------------===//
1607 void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D,
1609 ExplodedNodeSet &Dst) {
1610 StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
1612 ProgramStateRef state = Pred->getState();
1613 const LocationContext *LCtx = Pred->getLocationContext();
1615 if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
1616 assert(Ex->isGLValue());
1617 SVal V = state->getLValue(VD, Pred->getLocationContext());
1619 // For references, the 'lvalue' is the pointer address stored in the
1620 // reference region.
1621 if (VD->getType()->isReferenceType()) {
1622 if (const MemRegion *R = V.getAsRegion())
1623 V = state->getSVal(R);
1628 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), 0,
1629 ProgramPoint::PostLValueKind);
1632 if (const EnumConstantDecl *ED = dyn_cast<EnumConstantDecl>(D)) {
1633 assert(!Ex->isGLValue());
1634 SVal V = svalBuilder.makeIntVal(ED->getInitVal());
1635 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V));
1638 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
1639 SVal V = svalBuilder.getFunctionPointer(FD);
1640 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), 0,
1641 ProgramPoint::PostLValueKind);
1644 if (isa<FieldDecl>(D)) {
1645 // FIXME: Compute lvalue of field pointers-to-member.
1646 // Right now we just use a non-null void pointer, so that it gives proper
1647 // results in boolean contexts.
1648 SVal V = svalBuilder.conjureSymbolVal(Ex, LCtx, getContext().VoidPtrTy,
1649 currBldrCtx->blockCount());
1650 state = state->assume(V.castAs<DefinedOrUnknownSVal>(), true);
1651 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), 0,
1652 ProgramPoint::PostLValueKind);
1656 llvm_unreachable("Support for this Decl not implemented.");
1659 /// VisitArraySubscriptExpr - Transfer function for array accesses
1660 void ExprEngine::VisitLvalArraySubscriptExpr(const ArraySubscriptExpr *A,
1662 ExplodedNodeSet &Dst){
1664 const Expr *Base = A->getBase()->IgnoreParens();
1665 const Expr *Idx = A->getIdx()->IgnoreParens();
1668 ExplodedNodeSet checkerPreStmt;
1669 getCheckerManager().runCheckersForPreStmt(checkerPreStmt, Pred, A, *this);
1671 StmtNodeBuilder Bldr(checkerPreStmt, Dst, *currBldrCtx);
1673 for (ExplodedNodeSet::iterator it = checkerPreStmt.begin(),
1674 ei = checkerPreStmt.end(); it != ei; ++it) {
1675 const LocationContext *LCtx = (*it)->getLocationContext();
1676 ProgramStateRef state = (*it)->getState();
1677 SVal V = state->getLValue(A->getType(),
1678 state->getSVal(Idx, LCtx),
1679 state->getSVal(Base, LCtx));
1680 assert(A->isGLValue());
1681 Bldr.generateNode(A, *it, state->BindExpr(A, LCtx, V), 0,
1682 ProgramPoint::PostLValueKind);
1686 /// VisitMemberExpr - Transfer function for member expressions.
1687 void ExprEngine::VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred,
1688 ExplodedNodeSet &TopDst) {
1690 StmtNodeBuilder Bldr(Pred, TopDst, *currBldrCtx);
1691 ExplodedNodeSet Dst;
1692 ValueDecl *Member = M->getMemberDecl();
1694 // Handle static member variables and enum constants accessed via
1696 if (isa<VarDecl>(Member) || isa<EnumConstantDecl>(Member)) {
1697 Bldr.takeNodes(Pred);
1698 VisitCommonDeclRefExpr(M, Member, Pred, Dst);
1703 ProgramStateRef state = Pred->getState();
1704 const LocationContext *LCtx = Pred->getLocationContext();
1705 Expr *BaseExpr = M->getBase();
1707 // Handle C++ method calls.
1708 if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(Member)) {
1709 if (MD->isInstance())
1710 state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr);
1712 SVal MDVal = svalBuilder.getFunctionPointer(MD);
1713 state = state->BindExpr(M, LCtx, MDVal);
1715 Bldr.generateNode(M, Pred, state);
1719 // Handle regular struct fields / member variables.
1720 state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr);
1721 SVal baseExprVal = state->getSVal(BaseExpr, LCtx);
1723 FieldDecl *field = cast<FieldDecl>(Member);
1724 SVal L = state->getLValue(field, baseExprVal);
1725 if (M->isGLValue()) {
1726 if (field->getType()->isReferenceType()) {
1727 if (const MemRegion *R = L.getAsRegion())
1728 L = state->getSVal(R);
1733 Bldr.generateNode(M, Pred, state->BindExpr(M, LCtx, L), 0,
1734 ProgramPoint::PostLValueKind);
1736 Bldr.takeNodes(Pred);
1737 evalLoad(Dst, M, M, Pred, state, L);
1743 class CollectReachableSymbolsCallback : public SymbolVisitor {
1744 InvalidatedSymbols Symbols;
1746 CollectReachableSymbolsCallback(ProgramStateRef State) {}
1747 const InvalidatedSymbols &getSymbols() const { return Symbols; }
1749 bool VisitSymbol(SymbolRef Sym) {
1750 Symbols.insert(Sym);
1754 } // end anonymous namespace
1756 // A value escapes in three possible cases:
1757 // (1) We are binding to something that is not a memory region.
1758 // (2) We are binding to a MemrRegion that does not have stack storage.
1759 // (3) We are binding to a MemRegion with stack storage that the store
1760 // does not understand.
1761 ProgramStateRef ExprEngine::processPointerEscapedOnBind(ProgramStateRef State,
1762 SVal Loc, SVal Val) {
1763 // Are we storing to something that causes the value to "escape"?
1764 bool escapes = true;
1766 // TODO: Move to StoreManager.
1767 if (Optional<loc::MemRegionVal> regionLoc = Loc.getAs<loc::MemRegionVal>()) {
1768 escapes = !regionLoc->getRegion()->hasStackStorage();
1771 // To test (3), generate a new state with the binding added. If it is
1772 // the same state, then it escapes (since the store cannot represent
1774 // Do this only if we know that the store is not supposed to generate the
1776 SVal StoredVal = State->getSVal(regionLoc->getRegion());
1777 if (StoredVal != Val)
1778 escapes = (State == (State->bindLoc(*regionLoc, Val)));
1782 // If our store can represent the binding and we aren't storing to something
1783 // that doesn't have local storage then just return and have the simulation
1784 // state continue as is.
1788 // Otherwise, find all symbols referenced by 'val' that we are tracking
1789 // and stop tracking them.
1790 CollectReachableSymbolsCallback Scanner =
1791 State->scanReachableSymbols<CollectReachableSymbolsCallback>(Val);
1792 const InvalidatedSymbols &EscapedSymbols = Scanner.getSymbols();
1793 State = getCheckerManager().runCheckersForPointerEscape(State,
1802 ExprEngine::notifyCheckersOfPointerEscape(ProgramStateRef State,
1803 const InvalidatedSymbols *Invalidated,
1804 ArrayRef<const MemRegion *> ExplicitRegions,
1805 ArrayRef<const MemRegion *> Regions,
1806 const CallEvent *Call,
1809 if (!Invalidated || Invalidated->empty())
1813 return getCheckerManager().runCheckersForPointerEscape(State,
1819 // Note: Due to current limitations of RegionStore, we only process the top
1820 // level const pointers correctly. The lower level const pointers are
1821 // currently treated as non-const.
1823 return getCheckerManager().runCheckersForPointerEscape(State,
1826 PSK_DirectEscapeOnCall,
1829 // If the symbols were invalidated by a call, we want to find out which ones
1830 // were invalidated directly due to being arguments to the call.
1831 InvalidatedSymbols SymbolsDirectlyInvalidated;
1832 for (ArrayRef<const MemRegion *>::iterator I = ExplicitRegions.begin(),
1833 E = ExplicitRegions.end(); I != E; ++I) {
1834 if (const SymbolicRegion *R = (*I)->StripCasts()->getAs<SymbolicRegion>())
1835 SymbolsDirectlyInvalidated.insert(R->getSymbol());
1838 InvalidatedSymbols SymbolsIndirectlyInvalidated;
1839 for (InvalidatedSymbols::const_iterator I=Invalidated->begin(),
1840 E = Invalidated->end(); I!=E; ++I) {
1842 if (SymbolsDirectlyInvalidated.count(sym))
1844 SymbolsIndirectlyInvalidated.insert(sym);
1847 if (!SymbolsDirectlyInvalidated.empty())
1848 State = getCheckerManager().runCheckersForPointerEscape(State,
1849 SymbolsDirectlyInvalidated, Call, PSK_DirectEscapeOnCall);
1851 // Notify about the symbols that get indirectly invalidated by the call.
1852 if (!SymbolsIndirectlyInvalidated.empty())
1853 State = getCheckerManager().runCheckersForPointerEscape(State,
1854 SymbolsIndirectlyInvalidated, Call, PSK_IndirectEscapeOnCall);
1859 /// evalBind - Handle the semantics of binding a value to a specific location.
1860 /// This method is used by evalStore and (soon) VisitDeclStmt, and others.
1861 void ExprEngine::evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE,
1863 SVal location, SVal Val,
1864 bool atDeclInit, const ProgramPoint *PP) {
1866 const LocationContext *LC = Pred->getLocationContext();
1867 PostStmt PS(StoreE, LC);
1871 // Do a previsit of the bind.
1872 ExplodedNodeSet CheckedSet;
1873 getCheckerManager().runCheckersForBind(CheckedSet, Pred, location, Val,
1874 StoreE, *this, *PP);
1877 StmtNodeBuilder Bldr(CheckedSet, Dst, *currBldrCtx);
1879 // If the location is not a 'Loc', it will already be handled by
1880 // the checkers. There is nothing left to do.
1881 if (!location.getAs<Loc>()) {
1882 const ProgramPoint L = PostStore(StoreE, LC, /*Loc*/0, /*tag*/0);
1883 ProgramStateRef state = Pred->getState();
1884 state = processPointerEscapedOnBind(state, location, Val);
1885 Bldr.generateNode(L, state, Pred);
1890 for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end();
1892 ExplodedNode *PredI = *I;
1893 ProgramStateRef state = PredI->getState();
1895 state = processPointerEscapedOnBind(state, location, Val);
1897 // When binding the value, pass on the hint that this is a initialization.
1898 // For initializations, we do not need to inform clients of region
1900 state = state->bindLoc(location.castAs<Loc>(),
1901 Val, /* notifyChanges = */ !atDeclInit);
1903 const MemRegion *LocReg = 0;
1904 if (Optional<loc::MemRegionVal> LocRegVal =
1905 location.getAs<loc::MemRegionVal>()) {
1906 LocReg = LocRegVal->getRegion();
1909 const ProgramPoint L = PostStore(StoreE, LC, LocReg, 0);
1910 Bldr.generateNode(L, state, PredI);
1914 /// evalStore - Handle the semantics of a store via an assignment.
1915 /// @param Dst The node set to store generated state nodes
1916 /// @param AssignE The assignment expression if the store happens in an
1918 /// @param LocationE The location expression that is stored to.
1919 /// @param state The current simulation state
1920 /// @param location The location to store the value
1921 /// @param Val The value to be stored
1922 void ExprEngine::evalStore(ExplodedNodeSet &Dst, const Expr *AssignE,
1923 const Expr *LocationE,
1925 ProgramStateRef state, SVal location, SVal Val,
1926 const ProgramPointTag *tag) {
1927 // Proceed with the store. We use AssignE as the anchor for the PostStore
1928 // ProgramPoint if it is non-NULL, and LocationE otherwise.
1929 const Expr *StoreE = AssignE ? AssignE : LocationE;
1931 // Evaluate the location (checks for bad dereferences).
1932 ExplodedNodeSet Tmp;
1933 evalLocation(Tmp, AssignE, LocationE, Pred, state, location, tag, false);
1938 if (location.isUndef())
1941 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI)
1942 evalBind(Dst, StoreE, *NI, location, Val, false);
1945 void ExprEngine::evalLoad(ExplodedNodeSet &Dst,
1947 const Expr *BoundEx,
1949 ProgramStateRef state,
1951 const ProgramPointTag *tag,
1954 assert(!location.getAs<NonLoc>() && "location cannot be a NonLoc.");
1956 // Are we loading from a region? This actually results in two loads; one
1957 // to fetch the address of the referenced value and one to fetch the
1958 // referenced value.
1959 if (const TypedValueRegion *TR =
1960 dyn_cast_or_null<TypedValueRegion>(location.getAsRegion())) {
1962 QualType ValTy = TR->getValueType();
1963 if (const ReferenceType *RT = ValTy->getAs<ReferenceType>()) {
1964 static SimpleProgramPointTag
1965 loadReferenceTag("ExprEngine : Load Reference");
1966 ExplodedNodeSet Tmp;
1967 evalLoadCommon(Tmp, NodeEx, BoundEx, Pred, state,
1968 location, &loadReferenceTag,
1969 getContext().getPointerType(RT->getPointeeType()));
1971 // Perform the load from the referenced value.
1972 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end() ; I!=E; ++I) {
1973 state = (*I)->getState();
1974 location = state->getSVal(BoundEx, (*I)->getLocationContext());
1975 evalLoadCommon(Dst, NodeEx, BoundEx, *I, state, location, tag, LoadTy);
1981 evalLoadCommon(Dst, NodeEx, BoundEx, Pred, state, location, tag, LoadTy);
1984 void ExprEngine::evalLoadCommon(ExplodedNodeSet &Dst,
1986 const Expr *BoundEx,
1988 ProgramStateRef state,
1990 const ProgramPointTag *tag,
1994 // Evaluate the location (checks for bad dereferences).
1995 ExplodedNodeSet Tmp;
1996 evalLocation(Tmp, NodeEx, BoundEx, Pred, state, location, tag, true);
2000 StmtNodeBuilder Bldr(Tmp, Dst, *currBldrCtx);
2001 if (location.isUndef())
2004 // Proceed with the load.
2005 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) {
2006 state = (*NI)->getState();
2007 const LocationContext *LCtx = (*NI)->getLocationContext();
2009 SVal V = UnknownVal();
2010 if (location.isValid()) {
2011 if (LoadTy.isNull())
2012 LoadTy = BoundEx->getType();
2013 V = state->getSVal(location.castAs<Loc>(), LoadTy);
2016 Bldr.generateNode(NodeEx, *NI, state->BindExpr(BoundEx, LCtx, V), tag,
2017 ProgramPoint::PostLoadKind);
2021 void ExprEngine::evalLocation(ExplodedNodeSet &Dst,
2023 const Stmt *BoundEx,
2025 ProgramStateRef state,
2027 const ProgramPointTag *tag,
2029 StmtNodeBuilder BldrTop(Pred, Dst, *currBldrCtx);
2030 // Early checks for performance reason.
2031 if (location.isUnknown()) {
2035 ExplodedNodeSet Src;
2036 BldrTop.takeNodes(Pred);
2037 StmtNodeBuilder Bldr(Pred, Src, *currBldrCtx);
2038 if (Pred->getState() != state) {
2039 // Associate this new state with an ExplodedNode.
2040 // FIXME: If I pass null tag, the graph is incorrect, e.g for
2044 // "p = 0" is not noted as "Null pointer value stored to 'p'" but
2045 // instead "int *p" is noted as
2046 // "Variable 'p' initialized to a null pointer value"
2048 static SimpleProgramPointTag tag("ExprEngine: Location");
2049 Bldr.generateNode(NodeEx, Pred, state, &tag);
2051 ExplodedNodeSet Tmp;
2052 getCheckerManager().runCheckersForLocation(Tmp, Src, location, isLoad,
2053 NodeEx, BoundEx, *this);
2054 BldrTop.addNodes(Tmp);
2057 std::pair<const ProgramPointTag *, const ProgramPointTag*>
2058 ExprEngine::geteagerlyAssumeBinOpBifurcationTags() {
2059 static SimpleProgramPointTag
2060 eagerlyAssumeBinOpBifurcationTrue("ExprEngine : Eagerly Assume True"),
2061 eagerlyAssumeBinOpBifurcationFalse("ExprEngine : Eagerly Assume False");
2062 return std::make_pair(&eagerlyAssumeBinOpBifurcationTrue,
2063 &eagerlyAssumeBinOpBifurcationFalse);
2066 void ExprEngine::evalEagerlyAssumeBinOpBifurcation(ExplodedNodeSet &Dst,
2067 ExplodedNodeSet &Src,
2069 StmtNodeBuilder Bldr(Src, Dst, *currBldrCtx);
2071 for (ExplodedNodeSet::iterator I=Src.begin(), E=Src.end(); I!=E; ++I) {
2072 ExplodedNode *Pred = *I;
2073 // Test if the previous node was as the same expression. This can happen
2074 // when the expression fails to evaluate to anything meaningful and
2075 // (as an optimization) we don't generate a node.
2076 ProgramPoint P = Pred->getLocation();
2077 if (!P.getAs<PostStmt>() || P.castAs<PostStmt>().getStmt() != Ex) {
2081 ProgramStateRef state = Pred->getState();
2082 SVal V = state->getSVal(Ex, Pred->getLocationContext());
2083 Optional<nonloc::SymbolVal> SEV = V.getAs<nonloc::SymbolVal>();
2084 if (SEV && SEV->isExpression()) {
2085 const std::pair<const ProgramPointTag *, const ProgramPointTag*> &tags =
2086 geteagerlyAssumeBinOpBifurcationTags();
2088 ProgramStateRef StateTrue, StateFalse;
2089 tie(StateTrue, StateFalse) = state->assume(*SEV);
2091 // First assume that the condition is true.
2093 SVal Val = svalBuilder.makeIntVal(1U, Ex->getType());
2094 StateTrue = StateTrue->BindExpr(Ex, Pred->getLocationContext(), Val);
2095 Bldr.generateNode(Ex, Pred, StateTrue, tags.first);
2098 // Next, assume that the condition is false.
2100 SVal Val = svalBuilder.makeIntVal(0U, Ex->getType());
2101 StateFalse = StateFalse->BindExpr(Ex, Pred->getLocationContext(), Val);
2102 Bldr.generateNode(Ex, Pred, StateFalse, tags.second);
2108 void ExprEngine::VisitGCCAsmStmt(const GCCAsmStmt *A, ExplodedNode *Pred,
2109 ExplodedNodeSet &Dst) {
2110 StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
2111 // We have processed both the inputs and the outputs. All of the outputs
2112 // should evaluate to Locs. Nuke all of their values.
2114 // FIXME: Some day in the future it would be nice to allow a "plug-in"
2115 // which interprets the inline asm and stores proper results in the
2118 ProgramStateRef state = Pred->getState();
2120 for (GCCAsmStmt::const_outputs_iterator OI = A->begin_outputs(),
2121 OE = A->end_outputs(); OI != OE; ++OI) {
2122 SVal X = state->getSVal(*OI, Pred->getLocationContext());
2123 assert (!X.getAs<NonLoc>()); // Should be an Lval, or unknown, undef.
2125 if (Optional<Loc> LV = X.getAs<Loc>())
2126 state = state->bindLoc(*LV, UnknownVal());
2129 Bldr.generateNode(A, Pred, state);
2132 void ExprEngine::VisitMSAsmStmt(const MSAsmStmt *A, ExplodedNode *Pred,
2133 ExplodedNodeSet &Dst) {
2134 StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
2135 Bldr.generateNode(A, Pred, Pred->getState());
2138 //===----------------------------------------------------------------------===//
2140 //===----------------------------------------------------------------------===//
2143 static ExprEngine* GraphPrintCheckerState;
2144 static SourceManager* GraphPrintSourceManager;
2148 struct DOTGraphTraits<ExplodedNode*> :
2149 public DefaultDOTGraphTraits {
2151 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {}
2153 // FIXME: Since we do not cache error nodes in ExprEngine now, this does not
2155 static std::string getNodeAttributes(const ExplodedNode *N, void*) {
2158 // FIXME: Replace with a general scheme to tell if the node is
2160 if (GraphPrintCheckerState->isImplicitNullDeref(N) ||
2161 GraphPrintCheckerState->isExplicitNullDeref(N) ||
2162 GraphPrintCheckerState->isUndefDeref(N) ||
2163 GraphPrintCheckerState->isUndefStore(N) ||
2164 GraphPrintCheckerState->isUndefControlFlow(N) ||
2165 GraphPrintCheckerState->isUndefResult(N) ||
2166 GraphPrintCheckerState->isBadCall(N) ||
2167 GraphPrintCheckerState->isUndefArg(N))
2168 return "color=\"red\",style=\"filled\"";
2170 if (GraphPrintCheckerState->isNoReturnCall(N))
2171 return "color=\"blue\",style=\"filled\"";
2176 static void printLocation(raw_ostream &Out, SourceLocation SLoc) {
2177 if (SLoc.isFileID()) {
2179 << GraphPrintSourceManager->getExpansionLineNumber(SLoc)
2181 << GraphPrintSourceManager->getExpansionColumnNumber(SLoc)
2186 static std::string getNodeLabel(const ExplodedNode *N, void*){
2189 llvm::raw_string_ostream Out(sbuf);
2191 // Program Location.
2192 ProgramPoint Loc = N->getLocation();
2194 switch (Loc.getKind()) {
2195 case ProgramPoint::BlockEntranceKind: {
2196 Out << "Block Entrance: B"
2197 << Loc.castAs<BlockEntrance>().getBlock()->getBlockID();
2198 if (const NamedDecl *ND =
2199 dyn_cast<NamedDecl>(Loc.getLocationContext()->getDecl())) {
2207 case ProgramPoint::BlockExitKind:
2211 case ProgramPoint::CallEnterKind:
2215 case ProgramPoint::CallExitBeginKind:
2216 Out << "CallExitBegin";
2219 case ProgramPoint::CallExitEndKind:
2220 Out << "CallExitEnd";
2223 case ProgramPoint::PostStmtPurgeDeadSymbolsKind:
2224 Out << "PostStmtPurgeDeadSymbols";
2227 case ProgramPoint::PreStmtPurgeDeadSymbolsKind:
2228 Out << "PreStmtPurgeDeadSymbols";
2231 case ProgramPoint::EpsilonKind:
2232 Out << "Epsilon Point";
2235 case ProgramPoint::PreImplicitCallKind: {
2236 ImplicitCallPoint PC = Loc.castAs<ImplicitCallPoint>();
2239 // FIXME: Get proper printing options.
2240 PC.getDecl()->print(Out, LangOptions());
2241 printLocation(Out, PC.getLocation());
2245 case ProgramPoint::PostImplicitCallKind: {
2246 ImplicitCallPoint PC = Loc.castAs<ImplicitCallPoint>();
2247 Out << "PostCall: ";
2249 // FIXME: Get proper printing options.
2250 PC.getDecl()->print(Out, LangOptions());
2251 printLocation(Out, PC.getLocation());
2255 case ProgramPoint::PostInitializerKind: {
2256 Out << "PostInitializer: ";
2257 const CXXCtorInitializer *Init =
2258 Loc.castAs<PostInitializer>().getInitializer();
2259 if (const FieldDecl *FD = Init->getAnyMember())
2262 QualType Ty = Init->getTypeSourceInfo()->getType();
2263 Ty = Ty.getLocalUnqualifiedType();
2264 LangOptions LO; // FIXME.
2270 case ProgramPoint::BlockEdgeKind: {
2271 const BlockEdge &E = Loc.castAs<BlockEdge>();
2272 Out << "Edge: (B" << E.getSrc()->getBlockID() << ", B"
2273 << E.getDst()->getBlockID() << ')';
2275 if (const Stmt *T = E.getSrc()->getTerminator()) {
2276 SourceLocation SLoc = T->getLocStart();
2278 Out << "\\|Terminator: ";
2279 LangOptions LO; // FIXME.
2280 E.getSrc()->printTerminator(Out, LO);
2282 if (SLoc.isFileID()) {
2284 << GraphPrintSourceManager->getExpansionLineNumber(SLoc)
2286 << GraphPrintSourceManager->getExpansionColumnNumber(SLoc);
2289 if (isa<SwitchStmt>(T)) {
2290 const Stmt *Label = E.getDst()->getLabel();
2293 if (const CaseStmt *C = dyn_cast<CaseStmt>(Label)) {
2295 LangOptions LO; // FIXME.
2296 C->getLHS()->printPretty(Out, 0, PrintingPolicy(LO));
2298 if (const Stmt *RHS = C->getRHS()) {
2300 RHS->printPretty(Out, 0, PrintingPolicy(LO));
2306 assert (isa<DefaultStmt>(Label));
2307 Out << "\\ldefault:";
2311 Out << "\\l(implicit) default:";
2313 else if (isa<IndirectGotoStmt>(T)) {
2317 Out << "\\lCondition: ";
2318 if (*E.getSrc()->succ_begin() == E.getDst())
2328 // FIXME: Replace with a general scheme to determine
2329 // the name of the check.
2330 if (GraphPrintCheckerState->isUndefControlFlow(N)) {
2331 Out << "\\|Control-flow based on\\lUndefined value.\\l";
2338 const Stmt *S = Loc.castAs<StmtPoint>().getStmt();
2340 Out << S->getStmtClassName() << ' ' << (const void*) S << ' ';
2341 LangOptions LO; // FIXME.
2342 S->printPretty(Out, 0, PrintingPolicy(LO));
2343 printLocation(Out, S->getLocStart());
2345 if (Loc.getAs<PreStmt>())
2346 Out << "\\lPreStmt\\l;";
2347 else if (Loc.getAs<PostLoad>())
2348 Out << "\\lPostLoad\\l;";
2349 else if (Loc.getAs<PostStore>())
2350 Out << "\\lPostStore\\l";
2351 else if (Loc.getAs<PostLValue>())
2352 Out << "\\lPostLValue\\l";
2355 // FIXME: Replace with a general scheme to determine
2356 // the name of the check.
2357 if (GraphPrintCheckerState->isImplicitNullDeref(N))
2358 Out << "\\|Implicit-Null Dereference.\\l";
2359 else if (GraphPrintCheckerState->isExplicitNullDeref(N))
2360 Out << "\\|Explicit-Null Dereference.\\l";
2361 else if (GraphPrintCheckerState->isUndefDeref(N))
2362 Out << "\\|Dereference of undefialied value.\\l";
2363 else if (GraphPrintCheckerState->isUndefStore(N))
2364 Out << "\\|Store to Undefined Loc.";
2365 else if (GraphPrintCheckerState->isUndefResult(N))
2366 Out << "\\|Result of operation is undefined.";
2367 else if (GraphPrintCheckerState->isNoReturnCall(N))
2368 Out << "\\|Call to function marked \"noreturn\".";
2369 else if (GraphPrintCheckerState->isBadCall(N))
2370 Out << "\\|Call to NULL/Undefined.";
2371 else if (GraphPrintCheckerState->isUndefArg(N))
2372 Out << "\\|Argument in call is undefined";
2379 ProgramStateRef state = N->getState();
2380 Out << "\\|StateID: " << (const void*) state.getPtr()
2381 << " NodeID: " << (const void*) N << "\\|";
2382 state->printDOT(Out);
2386 if (const ProgramPointTag *tag = Loc.getTag()) {
2387 Out << "\\|Tag: " << tag->getTagDescription();
2393 } // end llvm namespace
2397 template <typename ITERATOR>
2398 ExplodedNode *GetGraphNode(ITERATOR I) { return *I; }
2400 template <> ExplodedNode*
2401 GetGraphNode<llvm::DenseMap<ExplodedNode*, Expr*>::iterator>
2402 (llvm::DenseMap<ExplodedNode*, Expr*>::iterator I) {
2407 void ExprEngine::ViewGraph(bool trim) {
2410 std::vector<const ExplodedNode*> Src;
2412 // Flush any outstanding reports to make sure we cover all the nodes.
2413 // This does not cause them to get displayed.
2414 for (BugReporter::iterator I=BR.begin(), E=BR.end(); I!=E; ++I)
2415 const_cast<BugType*>(*I)->FlushReports(BR);
2417 // Iterate through the reports and get their nodes.
2418 for (BugReporter::EQClasses_iterator
2419 EI = BR.EQClasses_begin(), EE = BR.EQClasses_end(); EI != EE; ++EI) {
2420 ExplodedNode *N = const_cast<ExplodedNode*>(EI->begin()->getErrorNode());
2421 if (N) Src.push_back(N);
2427 GraphPrintCheckerState = this;
2428 GraphPrintSourceManager = &getContext().getSourceManager();
2430 llvm::ViewGraph(*G.roots_begin(), "ExprEngine");
2432 GraphPrintCheckerState = NULL;
2433 GraphPrintSourceManager = NULL;
2438 void ExprEngine::ViewGraph(ArrayRef<const ExplodedNode*> Nodes) {
2440 GraphPrintCheckerState = this;
2441 GraphPrintSourceManager = &getContext().getSourceManager();
2443 OwningPtr<ExplodedGraph> TrimmedG(G.trim(Nodes));
2445 if (!TrimmedG.get())
2446 llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n";
2448 llvm::ViewGraph(*TrimmedG->roots_begin(), "TrimmedExprEngine");
2450 GraphPrintCheckerState = NULL;
2451 GraphPrintSourceManager = NULL;