106f32e7eSjoerg //= ProgramState.cpp - Path-Sensitive "State" for tracking values --*- C++ -*--=
206f32e7eSjoerg //
306f32e7eSjoerg // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
406f32e7eSjoerg // See https://llvm.org/LICENSE.txt for license information.
506f32e7eSjoerg // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
606f32e7eSjoerg //
706f32e7eSjoerg //===----------------------------------------------------------------------===//
806f32e7eSjoerg //
906f32e7eSjoerg // This file implements ProgramState and ProgramStateManager.
1006f32e7eSjoerg //
1106f32e7eSjoerg //===----------------------------------------------------------------------===//
1206f32e7eSjoerg
1306f32e7eSjoerg #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
1406f32e7eSjoerg #include "clang/Analysis/CFG.h"
1506f32e7eSjoerg #include "clang/Basic/JsonSupport.h"
1606f32e7eSjoerg #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
1706f32e7eSjoerg #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
1806f32e7eSjoerg #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h"
19*13fbcb42Sjoerg #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
2006f32e7eSjoerg #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
2106f32e7eSjoerg #include "llvm/Support/raw_ostream.h"
2206f32e7eSjoerg
2306f32e7eSjoerg using namespace clang;
2406f32e7eSjoerg using namespace ento;
2506f32e7eSjoerg
2606f32e7eSjoerg namespace clang { namespace ento {
2706f32e7eSjoerg /// Increments the number of times this state is referenced.
2806f32e7eSjoerg
ProgramStateRetain(const ProgramState * state)2906f32e7eSjoerg void ProgramStateRetain(const ProgramState *state) {
3006f32e7eSjoerg ++const_cast<ProgramState*>(state)->refCount;
3106f32e7eSjoerg }
3206f32e7eSjoerg
3306f32e7eSjoerg /// Decrement the number of times this state is referenced.
ProgramStateRelease(const ProgramState * state)3406f32e7eSjoerg void ProgramStateRelease(const ProgramState *state) {
3506f32e7eSjoerg assert(state->refCount > 0);
3606f32e7eSjoerg ProgramState *s = const_cast<ProgramState*>(state);
3706f32e7eSjoerg if (--s->refCount == 0) {
3806f32e7eSjoerg ProgramStateManager &Mgr = s->getStateManager();
3906f32e7eSjoerg Mgr.StateSet.RemoveNode(s);
4006f32e7eSjoerg s->~ProgramState();
4106f32e7eSjoerg Mgr.freeStates.push_back(s);
4206f32e7eSjoerg }
4306f32e7eSjoerg }
4406f32e7eSjoerg }}
4506f32e7eSjoerg
ProgramState(ProgramStateManager * mgr,const Environment & env,StoreRef st,GenericDataMap gdm)4606f32e7eSjoerg ProgramState::ProgramState(ProgramStateManager *mgr, const Environment& env,
4706f32e7eSjoerg StoreRef st, GenericDataMap gdm)
4806f32e7eSjoerg : stateMgr(mgr),
4906f32e7eSjoerg Env(env),
5006f32e7eSjoerg store(st.getStore()),
5106f32e7eSjoerg GDM(gdm),
5206f32e7eSjoerg refCount(0) {
5306f32e7eSjoerg stateMgr->getStoreManager().incrementReferenceCount(store);
5406f32e7eSjoerg }
5506f32e7eSjoerg
ProgramState(const ProgramState & RHS)5606f32e7eSjoerg ProgramState::ProgramState(const ProgramState &RHS)
5706f32e7eSjoerg : llvm::FoldingSetNode(),
5806f32e7eSjoerg stateMgr(RHS.stateMgr),
5906f32e7eSjoerg Env(RHS.Env),
6006f32e7eSjoerg store(RHS.store),
6106f32e7eSjoerg GDM(RHS.GDM),
6206f32e7eSjoerg refCount(0) {
6306f32e7eSjoerg stateMgr->getStoreManager().incrementReferenceCount(store);
6406f32e7eSjoerg }
6506f32e7eSjoerg
~ProgramState()6606f32e7eSjoerg ProgramState::~ProgramState() {
6706f32e7eSjoerg if (store)
6806f32e7eSjoerg stateMgr->getStoreManager().decrementReferenceCount(store);
6906f32e7eSjoerg }
7006f32e7eSjoerg
getID() const7106f32e7eSjoerg int64_t ProgramState::getID() const {
7206f32e7eSjoerg return getStateManager().Alloc.identifyKnownAlignedObject<ProgramState>(this);
7306f32e7eSjoerg }
7406f32e7eSjoerg
ProgramStateManager(ASTContext & Ctx,StoreManagerCreator CreateSMgr,ConstraintManagerCreator CreateCMgr,llvm::BumpPtrAllocator & alloc,ExprEngine * ExprEng)7506f32e7eSjoerg ProgramStateManager::ProgramStateManager(ASTContext &Ctx,
7606f32e7eSjoerg StoreManagerCreator CreateSMgr,
7706f32e7eSjoerg ConstraintManagerCreator CreateCMgr,
7806f32e7eSjoerg llvm::BumpPtrAllocator &alloc,
79*13fbcb42Sjoerg ExprEngine *ExprEng)
80*13fbcb42Sjoerg : Eng(ExprEng), EnvMgr(alloc), GDMFactory(alloc),
8106f32e7eSjoerg svalBuilder(createSimpleSValBuilder(alloc, Ctx, *this)),
8206f32e7eSjoerg CallEventMgr(new CallEventManager(alloc)), Alloc(alloc) {
8306f32e7eSjoerg StoreMgr = (*CreateSMgr)(*this);
84*13fbcb42Sjoerg ConstraintMgr = (*CreateCMgr)(*this, ExprEng);
8506f32e7eSjoerg }
8606f32e7eSjoerg
8706f32e7eSjoerg
~ProgramStateManager()8806f32e7eSjoerg ProgramStateManager::~ProgramStateManager() {
8906f32e7eSjoerg for (GDMContextsTy::iterator I=GDMContexts.begin(), E=GDMContexts.end();
9006f32e7eSjoerg I!=E; ++I)
9106f32e7eSjoerg I->second.second(I->second.first);
9206f32e7eSjoerg }
9306f32e7eSjoerg
removeDeadBindingsFromEnvironmentAndStore(ProgramStateRef state,const StackFrameContext * LCtx,SymbolReaper & SymReaper)94*13fbcb42Sjoerg ProgramStateRef ProgramStateManager::removeDeadBindingsFromEnvironmentAndStore(
95*13fbcb42Sjoerg ProgramStateRef state, const StackFrameContext *LCtx,
9606f32e7eSjoerg SymbolReaper &SymReaper) {
9706f32e7eSjoerg
9806f32e7eSjoerg // This code essentially performs a "mark-and-sweep" of the VariableBindings.
9906f32e7eSjoerg // The roots are any Block-level exprs and Decls that our liveness algorithm
10006f32e7eSjoerg // tells us are live. We then see what Decls they may reference, and keep
10106f32e7eSjoerg // those around. This code more than likely can be made faster, and the
10206f32e7eSjoerg // frequency of which this method is called should be experimented with
10306f32e7eSjoerg // for optimum performance.
10406f32e7eSjoerg ProgramState NewState = *state;
10506f32e7eSjoerg
10606f32e7eSjoerg NewState.Env = EnvMgr.removeDeadBindings(NewState.Env, SymReaper, state);
10706f32e7eSjoerg
10806f32e7eSjoerg // Clean up the store.
10906f32e7eSjoerg StoreRef newStore = StoreMgr->removeDeadBindings(NewState.getStore(), LCtx,
11006f32e7eSjoerg SymReaper);
11106f32e7eSjoerg NewState.setStore(newStore);
11206f32e7eSjoerg SymReaper.setReapedStore(newStore);
11306f32e7eSjoerg
114*13fbcb42Sjoerg return getPersistentState(NewState);
11506f32e7eSjoerg }
11606f32e7eSjoerg
bindLoc(Loc LV,SVal V,const LocationContext * LCtx,bool notifyChanges) const11706f32e7eSjoerg ProgramStateRef ProgramState::bindLoc(Loc LV,
11806f32e7eSjoerg SVal V,
11906f32e7eSjoerg const LocationContext *LCtx,
12006f32e7eSjoerg bool notifyChanges) const {
12106f32e7eSjoerg ProgramStateManager &Mgr = getStateManager();
12206f32e7eSjoerg ProgramStateRef newState = makeWithStore(Mgr.StoreMgr->Bind(getStore(),
12306f32e7eSjoerg LV, V));
12406f32e7eSjoerg const MemRegion *MR = LV.getAsRegion();
12506f32e7eSjoerg if (MR && notifyChanges)
12606f32e7eSjoerg return Mgr.getOwningEngine().processRegionChange(newState, MR, LCtx);
12706f32e7eSjoerg
12806f32e7eSjoerg return newState;
12906f32e7eSjoerg }
13006f32e7eSjoerg
13106f32e7eSjoerg ProgramStateRef
bindDefaultInitial(SVal loc,SVal V,const LocationContext * LCtx) const13206f32e7eSjoerg ProgramState::bindDefaultInitial(SVal loc, SVal V,
13306f32e7eSjoerg const LocationContext *LCtx) const {
13406f32e7eSjoerg ProgramStateManager &Mgr = getStateManager();
13506f32e7eSjoerg const MemRegion *R = loc.castAs<loc::MemRegionVal>().getRegion();
13606f32e7eSjoerg const StoreRef &newStore = Mgr.StoreMgr->BindDefaultInitial(getStore(), R, V);
13706f32e7eSjoerg ProgramStateRef new_state = makeWithStore(newStore);
13806f32e7eSjoerg return Mgr.getOwningEngine().processRegionChange(new_state, R, LCtx);
13906f32e7eSjoerg }
14006f32e7eSjoerg
14106f32e7eSjoerg ProgramStateRef
bindDefaultZero(SVal loc,const LocationContext * LCtx) const14206f32e7eSjoerg ProgramState::bindDefaultZero(SVal loc, const LocationContext *LCtx) const {
14306f32e7eSjoerg ProgramStateManager &Mgr = getStateManager();
14406f32e7eSjoerg const MemRegion *R = loc.castAs<loc::MemRegionVal>().getRegion();
14506f32e7eSjoerg const StoreRef &newStore = Mgr.StoreMgr->BindDefaultZero(getStore(), R);
14606f32e7eSjoerg ProgramStateRef new_state = makeWithStore(newStore);
14706f32e7eSjoerg return Mgr.getOwningEngine().processRegionChange(new_state, R, LCtx);
14806f32e7eSjoerg }
14906f32e7eSjoerg
15006f32e7eSjoerg typedef ArrayRef<const MemRegion *> RegionList;
15106f32e7eSjoerg typedef ArrayRef<SVal> ValueList;
15206f32e7eSjoerg
15306f32e7eSjoerg ProgramStateRef
invalidateRegions(RegionList Regions,const Expr * E,unsigned Count,const LocationContext * LCtx,bool CausedByPointerEscape,InvalidatedSymbols * IS,const CallEvent * Call,RegionAndSymbolInvalidationTraits * ITraits) const15406f32e7eSjoerg ProgramState::invalidateRegions(RegionList Regions,
15506f32e7eSjoerg const Expr *E, unsigned Count,
15606f32e7eSjoerg const LocationContext *LCtx,
15706f32e7eSjoerg bool CausedByPointerEscape,
15806f32e7eSjoerg InvalidatedSymbols *IS,
15906f32e7eSjoerg const CallEvent *Call,
16006f32e7eSjoerg RegionAndSymbolInvalidationTraits *ITraits) const {
16106f32e7eSjoerg SmallVector<SVal, 8> Values;
16206f32e7eSjoerg for (RegionList::const_iterator I = Regions.begin(),
16306f32e7eSjoerg End = Regions.end(); I != End; ++I)
16406f32e7eSjoerg Values.push_back(loc::MemRegionVal(*I));
16506f32e7eSjoerg
16606f32e7eSjoerg return invalidateRegionsImpl(Values, E, Count, LCtx, CausedByPointerEscape,
16706f32e7eSjoerg IS, ITraits, Call);
16806f32e7eSjoerg }
16906f32e7eSjoerg
17006f32e7eSjoerg ProgramStateRef
invalidateRegions(ValueList Values,const Expr * E,unsigned Count,const LocationContext * LCtx,bool CausedByPointerEscape,InvalidatedSymbols * IS,const CallEvent * Call,RegionAndSymbolInvalidationTraits * ITraits) const17106f32e7eSjoerg ProgramState::invalidateRegions(ValueList Values,
17206f32e7eSjoerg const Expr *E, unsigned Count,
17306f32e7eSjoerg const LocationContext *LCtx,
17406f32e7eSjoerg bool CausedByPointerEscape,
17506f32e7eSjoerg InvalidatedSymbols *IS,
17606f32e7eSjoerg const CallEvent *Call,
17706f32e7eSjoerg RegionAndSymbolInvalidationTraits *ITraits) const {
17806f32e7eSjoerg
17906f32e7eSjoerg return invalidateRegionsImpl(Values, E, Count, LCtx, CausedByPointerEscape,
18006f32e7eSjoerg IS, ITraits, Call);
18106f32e7eSjoerg }
18206f32e7eSjoerg
18306f32e7eSjoerg ProgramStateRef
invalidateRegionsImpl(ValueList Values,const Expr * E,unsigned Count,const LocationContext * LCtx,bool CausedByPointerEscape,InvalidatedSymbols * IS,RegionAndSymbolInvalidationTraits * ITraits,const CallEvent * Call) const18406f32e7eSjoerg ProgramState::invalidateRegionsImpl(ValueList Values,
18506f32e7eSjoerg const Expr *E, unsigned Count,
18606f32e7eSjoerg const LocationContext *LCtx,
18706f32e7eSjoerg bool CausedByPointerEscape,
18806f32e7eSjoerg InvalidatedSymbols *IS,
18906f32e7eSjoerg RegionAndSymbolInvalidationTraits *ITraits,
19006f32e7eSjoerg const CallEvent *Call) const {
19106f32e7eSjoerg ProgramStateManager &Mgr = getStateManager();
192*13fbcb42Sjoerg ExprEngine &Eng = Mgr.getOwningEngine();
19306f32e7eSjoerg
19406f32e7eSjoerg InvalidatedSymbols InvalidatedSyms;
19506f32e7eSjoerg if (!IS)
19606f32e7eSjoerg IS = &InvalidatedSyms;
19706f32e7eSjoerg
19806f32e7eSjoerg RegionAndSymbolInvalidationTraits ITraitsLocal;
19906f32e7eSjoerg if (!ITraits)
20006f32e7eSjoerg ITraits = &ITraitsLocal;
20106f32e7eSjoerg
20206f32e7eSjoerg StoreManager::InvalidatedRegions TopLevelInvalidated;
20306f32e7eSjoerg StoreManager::InvalidatedRegions Invalidated;
20406f32e7eSjoerg const StoreRef &newStore
20506f32e7eSjoerg = Mgr.StoreMgr->invalidateRegions(getStore(), Values, E, Count, LCtx, Call,
20606f32e7eSjoerg *IS, *ITraits, &TopLevelInvalidated,
20706f32e7eSjoerg &Invalidated);
20806f32e7eSjoerg
20906f32e7eSjoerg ProgramStateRef newState = makeWithStore(newStore);
21006f32e7eSjoerg
21106f32e7eSjoerg if (CausedByPointerEscape) {
21206f32e7eSjoerg newState = Eng.notifyCheckersOfPointerEscape(newState, IS,
21306f32e7eSjoerg TopLevelInvalidated,
21406f32e7eSjoerg Call,
21506f32e7eSjoerg *ITraits);
21606f32e7eSjoerg }
21706f32e7eSjoerg
21806f32e7eSjoerg return Eng.processRegionChanges(newState, IS, TopLevelInvalidated,
21906f32e7eSjoerg Invalidated, LCtx, Call);
22006f32e7eSjoerg }
22106f32e7eSjoerg
killBinding(Loc LV) const22206f32e7eSjoerg ProgramStateRef ProgramState::killBinding(Loc LV) const {
22306f32e7eSjoerg assert(!LV.getAs<loc::MemRegionVal>() && "Use invalidateRegion instead.");
22406f32e7eSjoerg
22506f32e7eSjoerg Store OldStore = getStore();
22606f32e7eSjoerg const StoreRef &newStore =
22706f32e7eSjoerg getStateManager().StoreMgr->killBinding(OldStore, LV);
22806f32e7eSjoerg
22906f32e7eSjoerg if (newStore.getStore() == OldStore)
23006f32e7eSjoerg return this;
23106f32e7eSjoerg
23206f32e7eSjoerg return makeWithStore(newStore);
23306f32e7eSjoerg }
23406f32e7eSjoerg
23506f32e7eSjoerg ProgramStateRef
enterStackFrame(const CallEvent & Call,const StackFrameContext * CalleeCtx) const23606f32e7eSjoerg ProgramState::enterStackFrame(const CallEvent &Call,
23706f32e7eSjoerg const StackFrameContext *CalleeCtx) const {
23806f32e7eSjoerg const StoreRef &NewStore =
23906f32e7eSjoerg getStateManager().StoreMgr->enterStackFrame(getStore(), Call, CalleeCtx);
24006f32e7eSjoerg return makeWithStore(NewStore);
24106f32e7eSjoerg }
24206f32e7eSjoerg
getSelfSVal(const LocationContext * LCtx) const243*13fbcb42Sjoerg SVal ProgramState::getSelfSVal(const LocationContext *LCtx) const {
244*13fbcb42Sjoerg const ImplicitParamDecl *SelfDecl = LCtx->getSelfDecl();
245*13fbcb42Sjoerg if (!SelfDecl)
246*13fbcb42Sjoerg return SVal();
247*13fbcb42Sjoerg return getSVal(getRegion(SelfDecl, LCtx));
248*13fbcb42Sjoerg }
249*13fbcb42Sjoerg
getSValAsScalarOrLoc(const MemRegion * R) const25006f32e7eSjoerg SVal ProgramState::getSValAsScalarOrLoc(const MemRegion *R) const {
25106f32e7eSjoerg // We only want to do fetches from regions that we can actually bind
25206f32e7eSjoerg // values. For example, SymbolicRegions of type 'id<...>' cannot
25306f32e7eSjoerg // have direct bindings (but their can be bindings on their subregions).
25406f32e7eSjoerg if (!R->isBoundable())
25506f32e7eSjoerg return UnknownVal();
25606f32e7eSjoerg
25706f32e7eSjoerg if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) {
25806f32e7eSjoerg QualType T = TR->getValueType();
25906f32e7eSjoerg if (Loc::isLocType(T) || T->isIntegralOrEnumerationType())
26006f32e7eSjoerg return getSVal(R);
26106f32e7eSjoerg }
26206f32e7eSjoerg
26306f32e7eSjoerg return UnknownVal();
26406f32e7eSjoerg }
26506f32e7eSjoerg
getSVal(Loc location,QualType T) const26606f32e7eSjoerg SVal ProgramState::getSVal(Loc location, QualType T) const {
26706f32e7eSjoerg SVal V = getRawSVal(location, T);
26806f32e7eSjoerg
26906f32e7eSjoerg // If 'V' is a symbolic value that is *perfectly* constrained to
27006f32e7eSjoerg // be a constant value, use that value instead to lessen the burden
27106f32e7eSjoerg // on later analysis stages (so we have less symbolic values to reason
27206f32e7eSjoerg // about).
27306f32e7eSjoerg // We only go into this branch if we can convert the APSInt value we have
27406f32e7eSjoerg // to the type of T, which is not always the case (e.g. for void).
27506f32e7eSjoerg if (!T.isNull() && (T->isIntegralOrEnumerationType() || Loc::isLocType(T))) {
27606f32e7eSjoerg if (SymbolRef sym = V.getAsSymbol()) {
27706f32e7eSjoerg if (const llvm::APSInt *Int = getStateManager()
27806f32e7eSjoerg .getConstraintManager()
27906f32e7eSjoerg .getSymVal(this, sym)) {
28006f32e7eSjoerg // FIXME: Because we don't correctly model (yet) sign-extension
28106f32e7eSjoerg // and truncation of symbolic values, we need to convert
28206f32e7eSjoerg // the integer value to the correct signedness and bitwidth.
28306f32e7eSjoerg //
28406f32e7eSjoerg // This shows up in the following:
28506f32e7eSjoerg //
28606f32e7eSjoerg // char foo();
28706f32e7eSjoerg // unsigned x = foo();
28806f32e7eSjoerg // if (x == 54)
28906f32e7eSjoerg // ...
29006f32e7eSjoerg //
29106f32e7eSjoerg // The symbolic value stored to 'x' is actually the conjured
29206f32e7eSjoerg // symbol for the call to foo(); the type of that symbol is 'char',
29306f32e7eSjoerg // not unsigned.
29406f32e7eSjoerg const llvm::APSInt &NewV = getBasicVals().Convert(T, *Int);
29506f32e7eSjoerg
29606f32e7eSjoerg if (V.getAs<Loc>())
29706f32e7eSjoerg return loc::ConcreteInt(NewV);
29806f32e7eSjoerg else
29906f32e7eSjoerg return nonloc::ConcreteInt(NewV);
30006f32e7eSjoerg }
30106f32e7eSjoerg }
30206f32e7eSjoerg }
30306f32e7eSjoerg
30406f32e7eSjoerg return V;
30506f32e7eSjoerg }
30606f32e7eSjoerg
BindExpr(const Stmt * S,const LocationContext * LCtx,SVal V,bool Invalidate) const30706f32e7eSjoerg ProgramStateRef ProgramState::BindExpr(const Stmt *S,
30806f32e7eSjoerg const LocationContext *LCtx,
30906f32e7eSjoerg SVal V, bool Invalidate) const{
31006f32e7eSjoerg Environment NewEnv =
31106f32e7eSjoerg getStateManager().EnvMgr.bindExpr(Env, EnvironmentEntry(S, LCtx), V,
31206f32e7eSjoerg Invalidate);
31306f32e7eSjoerg if (NewEnv == Env)
31406f32e7eSjoerg return this;
31506f32e7eSjoerg
31606f32e7eSjoerg ProgramState NewSt = *this;
31706f32e7eSjoerg NewSt.Env = NewEnv;
31806f32e7eSjoerg return getStateManager().getPersistentState(NewSt);
31906f32e7eSjoerg }
32006f32e7eSjoerg
assumeInBound(DefinedOrUnknownSVal Idx,DefinedOrUnknownSVal UpperBound,bool Assumption,QualType indexTy) const32106f32e7eSjoerg ProgramStateRef ProgramState::assumeInBound(DefinedOrUnknownSVal Idx,
32206f32e7eSjoerg DefinedOrUnknownSVal UpperBound,
32306f32e7eSjoerg bool Assumption,
32406f32e7eSjoerg QualType indexTy) const {
32506f32e7eSjoerg if (Idx.isUnknown() || UpperBound.isUnknown())
32606f32e7eSjoerg return this;
32706f32e7eSjoerg
32806f32e7eSjoerg // Build an expression for 0 <= Idx < UpperBound.
32906f32e7eSjoerg // This is the same as Idx + MIN < UpperBound + MIN, if overflow is allowed.
33006f32e7eSjoerg // FIXME: This should probably be part of SValBuilder.
33106f32e7eSjoerg ProgramStateManager &SM = getStateManager();
33206f32e7eSjoerg SValBuilder &svalBuilder = SM.getSValBuilder();
33306f32e7eSjoerg ASTContext &Ctx = svalBuilder.getContext();
33406f32e7eSjoerg
33506f32e7eSjoerg // Get the offset: the minimum value of the array index type.
33606f32e7eSjoerg BasicValueFactory &BVF = svalBuilder.getBasicValueFactory();
33706f32e7eSjoerg if (indexTy.isNull())
33806f32e7eSjoerg indexTy = svalBuilder.getArrayIndexType();
33906f32e7eSjoerg nonloc::ConcreteInt Min(BVF.getMinValue(indexTy));
34006f32e7eSjoerg
34106f32e7eSjoerg // Adjust the index.
34206f32e7eSjoerg SVal newIdx = svalBuilder.evalBinOpNN(this, BO_Add,
34306f32e7eSjoerg Idx.castAs<NonLoc>(), Min, indexTy);
34406f32e7eSjoerg if (newIdx.isUnknownOrUndef())
34506f32e7eSjoerg return this;
34606f32e7eSjoerg
34706f32e7eSjoerg // Adjust the upper bound.
34806f32e7eSjoerg SVal newBound =
34906f32e7eSjoerg svalBuilder.evalBinOpNN(this, BO_Add, UpperBound.castAs<NonLoc>(),
35006f32e7eSjoerg Min, indexTy);
35106f32e7eSjoerg
35206f32e7eSjoerg if (newBound.isUnknownOrUndef())
35306f32e7eSjoerg return this;
35406f32e7eSjoerg
35506f32e7eSjoerg // Build the actual comparison.
35606f32e7eSjoerg SVal inBound = svalBuilder.evalBinOpNN(this, BO_LT, newIdx.castAs<NonLoc>(),
35706f32e7eSjoerg newBound.castAs<NonLoc>(), Ctx.IntTy);
35806f32e7eSjoerg if (inBound.isUnknownOrUndef())
35906f32e7eSjoerg return this;
36006f32e7eSjoerg
36106f32e7eSjoerg // Finally, let the constraint manager take care of it.
36206f32e7eSjoerg ConstraintManager &CM = SM.getConstraintManager();
36306f32e7eSjoerg return CM.assume(this, inBound.castAs<DefinedSVal>(), Assumption);
36406f32e7eSjoerg }
36506f32e7eSjoerg
isNonNull(SVal V) const36606f32e7eSjoerg ConditionTruthVal ProgramState::isNonNull(SVal V) const {
36706f32e7eSjoerg ConditionTruthVal IsNull = isNull(V);
36806f32e7eSjoerg if (IsNull.isUnderconstrained())
36906f32e7eSjoerg return IsNull;
37006f32e7eSjoerg return ConditionTruthVal(!IsNull.getValue());
37106f32e7eSjoerg }
37206f32e7eSjoerg
areEqual(SVal Lhs,SVal Rhs) const37306f32e7eSjoerg ConditionTruthVal ProgramState::areEqual(SVal Lhs, SVal Rhs) const {
37406f32e7eSjoerg return stateMgr->getSValBuilder().areEqual(this, Lhs, Rhs);
37506f32e7eSjoerg }
37606f32e7eSjoerg
isNull(SVal V) const37706f32e7eSjoerg ConditionTruthVal ProgramState::isNull(SVal V) const {
37806f32e7eSjoerg if (V.isZeroConstant())
37906f32e7eSjoerg return true;
38006f32e7eSjoerg
38106f32e7eSjoerg if (V.isConstant())
38206f32e7eSjoerg return false;
38306f32e7eSjoerg
38406f32e7eSjoerg SymbolRef Sym = V.getAsSymbol(/* IncludeBaseRegion */ true);
38506f32e7eSjoerg if (!Sym)
38606f32e7eSjoerg return ConditionTruthVal();
38706f32e7eSjoerg
38806f32e7eSjoerg return getStateManager().ConstraintMgr->isNull(this, Sym);
38906f32e7eSjoerg }
39006f32e7eSjoerg
getInitialState(const LocationContext * InitLoc)39106f32e7eSjoerg ProgramStateRef ProgramStateManager::getInitialState(const LocationContext *InitLoc) {
39206f32e7eSjoerg ProgramState State(this,
39306f32e7eSjoerg EnvMgr.getInitialEnvironment(),
39406f32e7eSjoerg StoreMgr->getInitialStore(InitLoc),
39506f32e7eSjoerg GDMFactory.getEmptyMap());
39606f32e7eSjoerg
39706f32e7eSjoerg return getPersistentState(State);
39806f32e7eSjoerg }
39906f32e7eSjoerg
getPersistentStateWithGDM(ProgramStateRef FromState,ProgramStateRef GDMState)40006f32e7eSjoerg ProgramStateRef ProgramStateManager::getPersistentStateWithGDM(
40106f32e7eSjoerg ProgramStateRef FromState,
40206f32e7eSjoerg ProgramStateRef GDMState) {
40306f32e7eSjoerg ProgramState NewState(*FromState);
40406f32e7eSjoerg NewState.GDM = GDMState->GDM;
40506f32e7eSjoerg return getPersistentState(NewState);
40606f32e7eSjoerg }
40706f32e7eSjoerg
getPersistentState(ProgramState & State)40806f32e7eSjoerg ProgramStateRef ProgramStateManager::getPersistentState(ProgramState &State) {
40906f32e7eSjoerg
41006f32e7eSjoerg llvm::FoldingSetNodeID ID;
41106f32e7eSjoerg State.Profile(ID);
41206f32e7eSjoerg void *InsertPos;
41306f32e7eSjoerg
41406f32e7eSjoerg if (ProgramState *I = StateSet.FindNodeOrInsertPos(ID, InsertPos))
41506f32e7eSjoerg return I;
41606f32e7eSjoerg
41706f32e7eSjoerg ProgramState *newState = nullptr;
41806f32e7eSjoerg if (!freeStates.empty()) {
41906f32e7eSjoerg newState = freeStates.back();
42006f32e7eSjoerg freeStates.pop_back();
42106f32e7eSjoerg }
42206f32e7eSjoerg else {
42306f32e7eSjoerg newState = (ProgramState*) Alloc.Allocate<ProgramState>();
42406f32e7eSjoerg }
42506f32e7eSjoerg new (newState) ProgramState(State);
42606f32e7eSjoerg StateSet.InsertNode(newState, InsertPos);
42706f32e7eSjoerg return newState;
42806f32e7eSjoerg }
42906f32e7eSjoerg
makeWithStore(const StoreRef & store) const43006f32e7eSjoerg ProgramStateRef ProgramState::makeWithStore(const StoreRef &store) const {
43106f32e7eSjoerg ProgramState NewSt(*this);
43206f32e7eSjoerg NewSt.setStore(store);
43306f32e7eSjoerg return getStateManager().getPersistentState(NewSt);
43406f32e7eSjoerg }
43506f32e7eSjoerg
setStore(const StoreRef & newStore)43606f32e7eSjoerg void ProgramState::setStore(const StoreRef &newStore) {
43706f32e7eSjoerg Store newStoreStore = newStore.getStore();
43806f32e7eSjoerg if (newStoreStore)
43906f32e7eSjoerg stateMgr->getStoreManager().incrementReferenceCount(newStoreStore);
44006f32e7eSjoerg if (store)
44106f32e7eSjoerg stateMgr->getStoreManager().decrementReferenceCount(store);
44206f32e7eSjoerg store = newStoreStore;
44306f32e7eSjoerg }
44406f32e7eSjoerg
44506f32e7eSjoerg //===----------------------------------------------------------------------===//
44606f32e7eSjoerg // State pretty-printing.
44706f32e7eSjoerg //===----------------------------------------------------------------------===//
44806f32e7eSjoerg
printJson(raw_ostream & Out,const LocationContext * LCtx,const char * NL,unsigned int Space,bool IsDot) const44906f32e7eSjoerg void ProgramState::printJson(raw_ostream &Out, const LocationContext *LCtx,
45006f32e7eSjoerg const char *NL, unsigned int Space,
45106f32e7eSjoerg bool IsDot) const {
45206f32e7eSjoerg Indent(Out, Space, IsDot) << "\"program_state\": {" << NL;
45306f32e7eSjoerg ++Space;
45406f32e7eSjoerg
45506f32e7eSjoerg ProgramStateManager &Mgr = getStateManager();
45606f32e7eSjoerg
45706f32e7eSjoerg // Print the store.
45806f32e7eSjoerg Mgr.getStoreManager().printJson(Out, getStore(), NL, Space, IsDot);
45906f32e7eSjoerg
46006f32e7eSjoerg // Print out the environment.
46106f32e7eSjoerg Env.printJson(Out, Mgr.getContext(), LCtx, NL, Space, IsDot);
46206f32e7eSjoerg
46306f32e7eSjoerg // Print out the constraints.
46406f32e7eSjoerg Mgr.getConstraintManager().printJson(Out, this, NL, Space, IsDot);
46506f32e7eSjoerg
46606f32e7eSjoerg // Print out the tracked dynamic types.
46706f32e7eSjoerg printDynamicTypeInfoJson(Out, this, NL, Space, IsDot);
46806f32e7eSjoerg
46906f32e7eSjoerg // Print checker-specific data.
47006f32e7eSjoerg Mgr.getOwningEngine().printJson(Out, this, LCtx, NL, Space, IsDot);
47106f32e7eSjoerg
47206f32e7eSjoerg --Space;
47306f32e7eSjoerg Indent(Out, Space, IsDot) << '}';
47406f32e7eSjoerg }
47506f32e7eSjoerg
printDOT(raw_ostream & Out,const LocationContext * LCtx,unsigned int Space) const47606f32e7eSjoerg void ProgramState::printDOT(raw_ostream &Out, const LocationContext *LCtx,
47706f32e7eSjoerg unsigned int Space) const {
47806f32e7eSjoerg printJson(Out, LCtx, /*NL=*/"\\l", Space, /*IsDot=*/true);
47906f32e7eSjoerg }
48006f32e7eSjoerg
dump() const48106f32e7eSjoerg LLVM_DUMP_METHOD void ProgramState::dump() const {
48206f32e7eSjoerg printJson(llvm::errs());
48306f32e7eSjoerg }
48406f32e7eSjoerg
getAnalysisManager() const48506f32e7eSjoerg AnalysisManager& ProgramState::getAnalysisManager() const {
48606f32e7eSjoerg return stateMgr->getOwningEngine().getAnalysisManager();
48706f32e7eSjoerg }
48806f32e7eSjoerg
48906f32e7eSjoerg //===----------------------------------------------------------------------===//
49006f32e7eSjoerg // Generic Data Map.
49106f32e7eSjoerg //===----------------------------------------------------------------------===//
49206f32e7eSjoerg
FindGDM(void * K) const49306f32e7eSjoerg void *const* ProgramState::FindGDM(void *K) const {
49406f32e7eSjoerg return GDM.lookup(K);
49506f32e7eSjoerg }
49606f32e7eSjoerg
49706f32e7eSjoerg void*
FindGDMContext(void * K,void * (* CreateContext)(llvm::BumpPtrAllocator &),void (* DeleteContext)(void *))49806f32e7eSjoerg ProgramStateManager::FindGDMContext(void *K,
49906f32e7eSjoerg void *(*CreateContext)(llvm::BumpPtrAllocator&),
50006f32e7eSjoerg void (*DeleteContext)(void*)) {
50106f32e7eSjoerg
50206f32e7eSjoerg std::pair<void*, void (*)(void*)>& p = GDMContexts[K];
50306f32e7eSjoerg if (!p.first) {
50406f32e7eSjoerg p.first = CreateContext(Alloc);
50506f32e7eSjoerg p.second = DeleteContext;
50606f32e7eSjoerg }
50706f32e7eSjoerg
50806f32e7eSjoerg return p.first;
50906f32e7eSjoerg }
51006f32e7eSjoerg
addGDM(ProgramStateRef St,void * Key,void * Data)51106f32e7eSjoerg ProgramStateRef ProgramStateManager::addGDM(ProgramStateRef St, void *Key, void *Data){
51206f32e7eSjoerg ProgramState::GenericDataMap M1 = St->getGDM();
51306f32e7eSjoerg ProgramState::GenericDataMap M2 = GDMFactory.add(M1, Key, Data);
51406f32e7eSjoerg
51506f32e7eSjoerg if (M1 == M2)
51606f32e7eSjoerg return St;
51706f32e7eSjoerg
51806f32e7eSjoerg ProgramState NewSt = *St;
51906f32e7eSjoerg NewSt.GDM = M2;
52006f32e7eSjoerg return getPersistentState(NewSt);
52106f32e7eSjoerg }
52206f32e7eSjoerg
removeGDM(ProgramStateRef state,void * Key)52306f32e7eSjoerg ProgramStateRef ProgramStateManager::removeGDM(ProgramStateRef state, void *Key) {
52406f32e7eSjoerg ProgramState::GenericDataMap OldM = state->getGDM();
52506f32e7eSjoerg ProgramState::GenericDataMap NewM = GDMFactory.remove(OldM, Key);
52606f32e7eSjoerg
52706f32e7eSjoerg if (NewM == OldM)
52806f32e7eSjoerg return state;
52906f32e7eSjoerg
53006f32e7eSjoerg ProgramState NewState = *state;
53106f32e7eSjoerg NewState.GDM = NewM;
53206f32e7eSjoerg return getPersistentState(NewState);
53306f32e7eSjoerg }
53406f32e7eSjoerg
scan(nonloc::LazyCompoundVal val)53506f32e7eSjoerg bool ScanReachableSymbols::scan(nonloc::LazyCompoundVal val) {
53606f32e7eSjoerg bool wasVisited = !visited.insert(val.getCVData()).second;
53706f32e7eSjoerg if (wasVisited)
53806f32e7eSjoerg return true;
53906f32e7eSjoerg
54006f32e7eSjoerg StoreManager &StoreMgr = state->getStateManager().getStoreManager();
54106f32e7eSjoerg // FIXME: We don't really want to use getBaseRegion() here because pointer
54206f32e7eSjoerg // arithmetic doesn't apply, but scanReachableSymbols only accepts base
54306f32e7eSjoerg // regions right now.
54406f32e7eSjoerg const MemRegion *R = val.getRegion()->getBaseRegion();
54506f32e7eSjoerg return StoreMgr.scanReachableSymbols(val.getStore(), R, *this);
54606f32e7eSjoerg }
54706f32e7eSjoerg
scan(nonloc::CompoundVal val)54806f32e7eSjoerg bool ScanReachableSymbols::scan(nonloc::CompoundVal val) {
54906f32e7eSjoerg for (nonloc::CompoundVal::iterator I=val.begin(), E=val.end(); I!=E; ++I)
55006f32e7eSjoerg if (!scan(*I))
55106f32e7eSjoerg return false;
55206f32e7eSjoerg
55306f32e7eSjoerg return true;
55406f32e7eSjoerg }
55506f32e7eSjoerg
scan(const SymExpr * sym)55606f32e7eSjoerg bool ScanReachableSymbols::scan(const SymExpr *sym) {
55706f32e7eSjoerg for (SymExpr::symbol_iterator SI = sym->symbol_begin(),
55806f32e7eSjoerg SE = sym->symbol_end();
55906f32e7eSjoerg SI != SE; ++SI) {
56006f32e7eSjoerg bool wasVisited = !visited.insert(*SI).second;
56106f32e7eSjoerg if (wasVisited)
56206f32e7eSjoerg continue;
56306f32e7eSjoerg
56406f32e7eSjoerg if (!visitor.VisitSymbol(*SI))
56506f32e7eSjoerg return false;
56606f32e7eSjoerg }
56706f32e7eSjoerg
56806f32e7eSjoerg return true;
56906f32e7eSjoerg }
57006f32e7eSjoerg
scan(SVal val)57106f32e7eSjoerg bool ScanReachableSymbols::scan(SVal val) {
57206f32e7eSjoerg if (Optional<loc::MemRegionVal> X = val.getAs<loc::MemRegionVal>())
57306f32e7eSjoerg return scan(X->getRegion());
57406f32e7eSjoerg
57506f32e7eSjoerg if (Optional<nonloc::LazyCompoundVal> X =
57606f32e7eSjoerg val.getAs<nonloc::LazyCompoundVal>())
57706f32e7eSjoerg return scan(*X);
57806f32e7eSjoerg
57906f32e7eSjoerg if (Optional<nonloc::LocAsInteger> X = val.getAs<nonloc::LocAsInteger>())
58006f32e7eSjoerg return scan(X->getLoc());
58106f32e7eSjoerg
58206f32e7eSjoerg if (SymbolRef Sym = val.getAsSymbol())
58306f32e7eSjoerg return scan(Sym);
58406f32e7eSjoerg
58506f32e7eSjoerg if (Optional<nonloc::CompoundVal> X = val.getAs<nonloc::CompoundVal>())
58606f32e7eSjoerg return scan(*X);
58706f32e7eSjoerg
58806f32e7eSjoerg return true;
58906f32e7eSjoerg }
59006f32e7eSjoerg
scan(const MemRegion * R)59106f32e7eSjoerg bool ScanReachableSymbols::scan(const MemRegion *R) {
59206f32e7eSjoerg if (isa<MemSpaceRegion>(R))
59306f32e7eSjoerg return true;
59406f32e7eSjoerg
59506f32e7eSjoerg bool wasVisited = !visited.insert(R).second;
59606f32e7eSjoerg if (wasVisited)
59706f32e7eSjoerg return true;
59806f32e7eSjoerg
59906f32e7eSjoerg if (!visitor.VisitMemRegion(R))
60006f32e7eSjoerg return false;
60106f32e7eSjoerg
60206f32e7eSjoerg // If this is a symbolic region, visit the symbol for the region.
60306f32e7eSjoerg if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
60406f32e7eSjoerg if (!visitor.VisitSymbol(SR->getSymbol()))
60506f32e7eSjoerg return false;
60606f32e7eSjoerg
60706f32e7eSjoerg // If this is a subregion, also visit the parent regions.
60806f32e7eSjoerg if (const SubRegion *SR = dyn_cast<SubRegion>(R)) {
60906f32e7eSjoerg const MemRegion *Super = SR->getSuperRegion();
61006f32e7eSjoerg if (!scan(Super))
61106f32e7eSjoerg return false;
61206f32e7eSjoerg
61306f32e7eSjoerg // When we reach the topmost region, scan all symbols in it.
61406f32e7eSjoerg if (isa<MemSpaceRegion>(Super)) {
61506f32e7eSjoerg StoreManager &StoreMgr = state->getStateManager().getStoreManager();
61606f32e7eSjoerg if (!StoreMgr.scanReachableSymbols(state->getStore(), SR, *this))
61706f32e7eSjoerg return false;
61806f32e7eSjoerg }
61906f32e7eSjoerg }
62006f32e7eSjoerg
62106f32e7eSjoerg // Regions captured by a block are also implicitly reachable.
62206f32e7eSjoerg if (const BlockDataRegion *BDR = dyn_cast<BlockDataRegion>(R)) {
62306f32e7eSjoerg BlockDataRegion::referenced_vars_iterator I = BDR->referenced_vars_begin(),
62406f32e7eSjoerg E = BDR->referenced_vars_end();
62506f32e7eSjoerg for ( ; I != E; ++I) {
62606f32e7eSjoerg if (!scan(I.getCapturedRegion()))
62706f32e7eSjoerg return false;
62806f32e7eSjoerg }
62906f32e7eSjoerg }
63006f32e7eSjoerg
63106f32e7eSjoerg return true;
63206f32e7eSjoerg }
63306f32e7eSjoerg
scanReachableSymbols(SVal val,SymbolVisitor & visitor) const63406f32e7eSjoerg bool ProgramState::scanReachableSymbols(SVal val, SymbolVisitor& visitor) const {
63506f32e7eSjoerg ScanReachableSymbols S(this, visitor);
63606f32e7eSjoerg return S.scan(val);
63706f32e7eSjoerg }
63806f32e7eSjoerg
scanReachableSymbols(llvm::iterator_range<region_iterator> Reachable,SymbolVisitor & visitor) const63906f32e7eSjoerg bool ProgramState::scanReachableSymbols(
64006f32e7eSjoerg llvm::iterator_range<region_iterator> Reachable,
64106f32e7eSjoerg SymbolVisitor &visitor) const {
64206f32e7eSjoerg ScanReachableSymbols S(this, visitor);
64306f32e7eSjoerg for (const MemRegion *R : Reachable) {
64406f32e7eSjoerg if (!S.scan(R))
64506f32e7eSjoerg return false;
64606f32e7eSjoerg }
64706f32e7eSjoerg return true;
64806f32e7eSjoerg }
649