clang: lib/StaticAnalyzer/Core/ProgramState.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
20#include "llvm/Support/raw_ostream.h"
21#include
22
23using namespace clang;
24using namespace ento;
25
27
28
32
33
35 assert(state->refCount > 0);
37 if (--s->refCount == 0) {
39 Mgr.StateSet.RemoveNode(s);
40 s->~ProgramState();
41 Mgr.freeStates.push_back(s);
42 }
43}
44}}
45
48 : stateMgr(mgr),
49 Env(env),
51 GDM(gdm),
52 refCount(0) {
53 stateMgr->getStoreManager().incrementReferenceCount(store);
54}
55
57 : stateMgr(RHS.stateMgr), Env(RHS.Env), store(RHS.store), GDM(RHS.GDM),
58 PosteriorlyOverconstrained(RHS.PosteriorlyOverconstrained), refCount(0) {
59 stateMgr->getStoreManager().incrementReferenceCount(store);
60}
61
63 if (store)
64 stateMgr->getStoreManager().decrementReferenceCount(store);
65}
66
70
74 llvm::BumpPtrAllocator &alloc,
76 : Eng(ExprEng), EnvMgr(alloc), GDMFactory(alloc),
79 StoreMgr = (*CreateSMgr)(*this);
80 ConstraintMgr = (*CreateCMgr)(*this, ExprEng);
81}
82
83
85 for (GDMContextsTy::iterator I=GDMContexts.begin(), E=GDMContexts.end();
86 I!=E; ++I)
87 I->second.second(I->second.first);
88}
89
93
94
95
96
97
98
99
101
102 NewState.Env = EnvMgr.removeDeadBindings(NewState.Env, SymReaper, state);
103
104
105 StoreRef newStore = StoreMgr->removeDeadBindings(NewState.getStore(), LCtx,
106 SymReaper);
107 NewState.setStore(newStore);
109
111}
112
116 bool notifyChanges) const {
121
122 if (MR && notifyChanges)
124
125 return State;
126}
127
137
146
149
156 for (const MemRegion *Reg : Regions)
158
159 return invalidateRegions(Values, Elem, Count, LCtx, CausedByPointerEscape, IS,
160 Call, ITraits);
161}
162
165 const LocationContext *LCtx, bool CausedByPointerEscape,
168
171
173 if (!IS)
174 IS = &InvalidatedSyms;
175
176 RegionAndSymbolInvalidationTraits ITraitsLocal;
177 if (!ITraits)
178 ITraits = &ITraitsLocal;
179
182 const StoreRef &NewStore = Mgr.StoreMgr->invalidateRegions(
183 getStore(), Values, Elem, Count, LCtx, Call, *IS, *ITraits,
184 &TopLevelInvalidated, &Invalidated);
185
187
188 if (CausedByPointerEscape) {
190 NewState, IS, TopLevelInvalidated, Call, *ITraits);
191 }
192
194 Invalidated, LCtx, Call);
195}
196
201
202 if (newStore.getStore() == OldStore)
203 return this;
204
205 return makeWithStore(newStore);
206}
207
208
209
210
211SVal ProgramState::desugarReference(SVal Val) const {
212 const auto *TyReg = dyn_cast_or_null(Val.getAsRegion());
213 if (!TyReg || !TyReg->getValueType()->isReferenceType())
214 return Val;
216}
217
218
219
220
221
222SVal ProgramState::wrapSymbolicRegion(SVal Val) const {
223 const auto *BaseReg = dyn_cast_or_null(Val.getAsRegion());
224 if (!BaseReg)
225 return Val;
226
228 QualType ElemTy = BaseReg->getPointeeStaticType();
230}
231
235 return makeWithStore(
237}
238
241 if (!SelfDecl)
242 return SVal();
244}
245
247
248
249
252
253 if (const TypedValueRegion *TR = dyn_cast(R)) {
257 }
258
260}
261
264
265
266
267
268
269
270
271 if (.isNull() && (T->isIntegralOrEnumerationType() || Loc::isLocType(T))) {
272 if (SymbolRef sym = V.getAsSymbol()) {
275 .getSymVal(this, sym)) {
276
277
278
279
280
281
282
283
284
285
286
287
288
289
294 }
295 }
296 }
297
298 return V;
299}
300
303 SVal V, bool Invalidate) const{
306 Invalidate);
307 if (NewEnv == Env)
308 return this;
309
311 NewSt.Env = NewEnv;
313}
314
315[[nodiscard]] std::pair<ProgramStateRef, ProgramStateRef>
320 return {this, this};
321
322
323
324
328
329
331 if (indexTy.isNull())
334
335
339 return {this, this};
340
341
342 SVal newBound =
344 Min, indexTy);
345
347 return {this, this};
348
349
353 return {this, this};
354
355
358}
359
362 bool Assumption,
364 std::pair<ProgramStateRef, ProgramStateRef> R =
366 return Assumption ? R.first : R.second;
367}
368
371 if (IsNull.isUnderconstrained())
374}
375
377 return stateMgr->getSValBuilder().areEqual(this, Lhs, Rhs);
378}
379
381 if (V.isZeroConstant())
382 return true;
383
384 if (V.isConstant())
385 return false;
386
387 SymbolRef Sym = V.getAsSymbol( true);
388 if (!Sym)
390
391 return getStateManager().ConstraintMgr->isNull(this, Sym);
392}
393
396 EnvMgr.getInitialEnvironment(),
397 StoreMgr->getInitialStore(InitLoc),
398 GDMFactory.getEmptyMap());
399
401}
402
407 NewState.GDM = GDMState->GDM;
409}
410
412
413 llvm::FoldingSetNodeID ID;
414 State.Profile(ID);
415 void *InsertPos;
416
417 if (ProgramState *I = StateSet.FindNodeOrInsertPos(ID, InsertPos))
418 return I;
419
421 if (!freeStates.empty()) {
422 newState = freeStates.back();
423 freeStates.pop_back();
424 }
425 else {
427 }
429 StateSet.InsertNode(newState, InsertPos);
430 return newState;
431}
432
435 NewSt.setStore(store);
437}
438
442
443
444
445
447 return State;
449}
450
451ProgramStateRef ProgramState::cloneAsPosteriorlyOverconstrained() const {
453 NewSt.PosteriorlyOverconstrained = true;
455}
456
457void ProgramState::setStore(const StoreRef &newStore) {
459 if (newStoreStore)
460 stateMgr->getStoreManager().incrementReferenceCount(newStoreStore);
461 if (store)
462 stateMgr->getStoreManager().decrementReferenceCount(store);
463 store = newStoreStore;
464}
465
471
474 Base = desugarReference(Base);
475 Base = wrapSymbolicRegion(Base);
476
477
478
479
480 for (const auto *I : D->chain()) {
482 }
484}
485
486
487
488
489
491 const char *NL, unsigned int Space,
492 bool IsDot) const {
493 Indent(Out, Space, IsDot) << "\"program_state\": {" << NL;
494 ++Space;
495
497
498
500
501
502 Env.printJson(Out, Mgr.getContext(), LCtx, NL, Space, IsDot);
503
504
506
507
509
510
512
513 --Space;
514 Indent(Out, Space, IsDot) << '}';
515}
516
518 unsigned int Space) const {
519 printJson(Out, LCtx, "\\l", Space, true);
520}
521
525
527 return stateMgr->getOwningEngine().getAnalysisManager();
528}
529
530
531
532
533
535 return GDM.lookup(K);
536}
537
538void*
540 void *(*CreateContext)(llvm::BumpPtrAllocator&),
541 void (*DeleteContext)(void*)) {
542
543 std::pair<void*, void (*)(void*)>& p = GDMContexts[K];
544 if (!p.first) {
545 p.first = CreateContext(Alloc);
546 p.second = DeleteContext;
547 }
548
549 return p.first;
550}
551
555
556 if (M1 == M2)
557 return St;
558
560 NewSt.GDM = M2;
562}
563
567
568 if (NewM == OldM)
569 return state;
570
572 NewState.GDM = NewM;
574}
575
577 bool wasVisited = !visited.insert(val.getCVData()).second;
578 if (wasVisited)
579 return true;
580
581 StoreManager &StoreMgr = state->getStateManager().getStoreManager();
582
583
584
587}
588
592 return false;
593
594 return true;
595}
596
599 bool wasVisited = !visited.insert(SubSym).second;
600 if (wasVisited)
601 continue;
602
603 if (!visitor.VisitSymbol(SubSym))
604 return false;
605 }
606
607 return true;
608}
609
612 return scan(X->getRegion());
613
614 if (std::optionalnonloc::LazyCompoundVal X =
617
620
622 return scan(Sym);
623
626
627 return true;
628}
629
632 return true;
633
634 bool wasVisited = !visited.insert(R).second;
635 if (wasVisited)
636 return true;
637
638 if (!visitor.VisitMemRegion(R))
639 return false;
640
641
642 if (const SymbolicRegion *SR = dyn_cast(R))
643 if (!visitor.VisitSymbol(SR->getSymbol()))
644 return false;
645
646
647 if (const SubRegion *SR = dyn_cast(R)) {
648 const MemRegion *Super = SR->getSuperRegion();
649 if ((Super))
650 return false;
651
652
654 StoreManager &StoreMgr = state->getStateManager().getStoreManager();
656 return false;
657 }
658 }
659
660
661 if (const BlockDataRegion *BDR = dyn_cast(R)) {
662 for (auto Var : BDR->referenced_vars()) {
663 if ((Var.getCapturedRegion()))
664 return false;
665 }
666 }
667
668 return true;
669}
670
673 return S.scan(val);
674}
675
677 llvm::iterator_range<region_iterator> Reachable,
680 for (const MemRegion *R : Reachable) {
681 if (!S.scan(R))
682 return false;
683 }
684 return true;
685}
ArrayRef< const MemRegion * > RegionList
Definition ProgramState.cpp:147
ArrayRef< SVal > ValueList
Definition ProgramState.cpp:148
__device__ __2f16 float __ockl_bool s
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Represents a member of a struct/union/class.
Represents a field injected from an anonymous union/struct into the parent scope.
ArrayRef< NamedDecl * > chain() const
It wraps the AnalysisDeclContext to represent both the call stack with the help of StackFrameContext ...
const ImplicitParamDecl * getSelfDecl() const
A (possibly-)qualified type.
bool isNull() const
Return true if this QualType doesn't point to a type yet.
It represents a stack frame of the call stack (based on CallEvent).
Stmt - This represents one statement.
A safe wrapper around APSInt objects allocated and owned by BasicValueFactory.
APSIntPtr getMinValue(const llvm::APSInt &v)
APSIntPtr Convert(const llvm::APSInt &To, const llvm::APSInt &From)
Convert - Create a new persistent APSInt with the same value as 'From' but with the bitwidth and sign...
BlockDataRegion - A region that represents a block instance.
Manages the lifetime of CallEvent objects.
Represents an abstract call to a function or method along a particular path.
ProgramStatePair assumeDual(ProgramStateRef State, DefinedSVal Cond)
Returns a pair of states (StTrue, StFalse) where the given condition is assumed to be true or false,...
virtual void printJson(raw_ostream &Out, ProgramStateRef State, const char *NL, unsigned int Space, bool IsDot) const =0
An entry in the environment consists of a Stmt and an LocationContext.
Environment bindExpr(Environment Env, const EnvironmentEntry &E, SVal V, bool Invalidate)
Bind a symbolic value to the given environment entry.
An immutable map from EnvironemntEntries to SVals.
ProgramStateRef processRegionChange(ProgramStateRef state, const MemRegion *MR, const LocationContext *LCtx)
void printJson(raw_ostream &Out, ProgramStateRef State, const LocationContext *LCtx, const char *NL, unsigned int Space, bool IsDot) const
printJson - Called by ProgramStateManager to print checker-specific data.
ProgramStateRef processRegionChanges(ProgramStateRef state, const InvalidatedSymbols *invalidated, ArrayRef< const MemRegion * > ExplicitRegions, ArrayRef< const MemRegion * > Regions, const LocationContext *LCtx, const CallEvent *Call)
processRegionChanges - Called by ProgramStateManager whenever a change is made to the store.
ProgramStateRef notifyCheckersOfPointerEscape(ProgramStateRef State, const InvalidatedSymbols *Invalidated, ArrayRef< const MemRegion * > ExplicitRegions, const CallEvent *Call, RegionAndSymbolInvalidationTraits &ITraits)
Call PointerEscape callback when a value escapes as a result of region invalidation.
ProgramStateRef escapeValues(ProgramStateRef State, ArrayRef< SVal > Vs, PointerEscapeKind K, const CallEvent *Call=nullptr) const
A simple wrapper when you only need to notify checkers of pointer-escape of some values.
static bool isLocType(QualType T)
MemRegion - The root abstract class for all memory regions.
virtual bool isBoundable() const
LLVM_ATTRIBUTE_RETURNS_NONNULL const MemRegion * getBaseRegion() const
ProgramStateRef removeDeadBindingsFromEnvironmentAndStore(ProgramStateRef St, const StackFrameContext *LCtx, SymbolReaper &SymReaper)
Definition ProgramState.cpp:90
ExprEngine & getOwningEngine()
ProgramStateRef removeGDM(ProgramStateRef state, void *Key)
Definition ProgramState.cpp:564
void * FindGDMContext(void *index, void *(*CreateContext)(llvm::BumpPtrAllocator &), void(*DeleteContext)(void *))
Definition ProgramState.cpp:539
friend class ProgramState
ASTContext & getContext()
ProgramStateRef getPersistentStateWithGDM(ProgramStateRef FromState, ProgramStateRef GDMState)
Definition ProgramState.cpp:403
ProgramStateRef addGDM(ProgramStateRef St, void *Key, void *Data)
Definition ProgramState.cpp:552
ProgramStateRef getPersistentState(ProgramState &Impl)
Definition ProgramState.cpp:411
ProgramStateRef getInitialState(const LocationContext *InitLoc)
Definition ProgramState.cpp:394
StoreManager & getStoreManager()
~ProgramStateManager()
Definition ProgramState.cpp:84
ProgramStateManager(ASTContext &Ctx, StoreManagerCreator CreateStoreManager, ConstraintManagerCreator CreateConstraintManager, llvm::BumpPtrAllocator &alloc, ExprEngine *expreng)
Definition ProgramState.cpp:71
ConstraintManager & getConstraintManager()
ProgramState - This class encapsulates:
bool scanReachableSymbols(SVal val, SymbolVisitor &visitor) const
Visits the symbols reachable from the given SVal using the provided SymbolVisitor.
Definition ProgramState.cpp:671
Loc getLValue(const CXXBaseSpecifier &BaseSpec, const SubRegion *Super) const
Get the lvalue for a base class object reference.
ProgramStateRef bindDefaultZero(SVal loc, const LocationContext *LCtx) const
Performs C++ zero-initialization procedure on the region of memory represented by loc.
Definition ProgramState.cpp:139
llvm::ImmutableMap< void *, void * > GenericDataMap
friend class ProgramStateManager
ProgramStateRef BindExpr(const Stmt *S, const LocationContext *LCtx, SVal V, bool Invalidate=true) const
Create a new state by binding the value 'V' to the statement 'S' in the state's environment.
Definition ProgramState.cpp:301
void printJson(raw_ostream &Out, const LocationContext *LCtx=nullptr, const char *NL="\n", unsigned int Space=0, bool IsDot=false) const
Definition ProgramState.cpp:490
ProgramStateRef bindDefaultInitial(SVal loc, SVal V, const LocationContext *LCtx) const
Initializes the region of memory represented by loc with an initial value.
Definition ProgramState.cpp:129
ConstraintManager & getConstraintManager() const
Return the ConstraintManager.
SVal getSValAsScalarOrLoc(const Stmt *Ex, const LocationContext *LCtx) const
SVal getSelfSVal(const LocationContext *LC) const
Return the value of 'self' if available in the given context.
Definition ProgramState.cpp:239
SVal getRawSVal(Loc LV, QualType T=QualType()) const
Returns the "raw" SVal bound to LV before any value simplification.
ConditionTruthVal isNull(SVal V) const
Check if the given SVal is constrained to zero or is a zero constant.
Definition ProgramState.cpp:380
ProgramStateManager & getStateManager() const
Return the ProgramStateManager associated with this state.
ProgramStateRef killBinding(Loc LV) const
Definition ProgramState.cpp:197
ProgramState(ProgramStateManager *mgr, const Environment &env, StoreRef st, GenericDataMap gdm)
This ctor is used when creating the first ProgramState object.
Definition ProgramState.cpp:46
Store getStore() const
Return the store associated with this state.
ConditionTruthVal areEqual(SVal Lhs, SVal Rhs) const
Definition ProgramState.cpp:376
void printDOT(raw_ostream &Out, const LocationContext *LCtx=nullptr, unsigned int Space=0) const
Definition ProgramState.cpp:517
ConditionTruthVal isNonNull(SVal V) const
Check if the given SVal is not constrained to zero and is not a zero constant.
Definition ProgramState.cpp:369
ProgramStateRef assumeInBound(DefinedOrUnknownSVal idx, DefinedOrUnknownSVal upperBound, bool assumption, QualType IndexType=QualType()) const
Definition ProgramState.cpp:360
ProgramStateRef enterStackFrame(const CallEvent &Call, const StackFrameContext *CalleeCtx) const
enterStackFrame - Returns the state for entry to the given stack frame, preserving the current state.
Definition ProgramState.cpp:233
int64_t getID() const
Definition ProgramState.cpp:67
LLVM_ATTRIBUTE_RETURNS_NONNULL const VarRegion * getRegion(const VarDecl *D, const LocationContext *LC) const
Utility method for getting regions.
SVal getSVal(const Stmt *S, const LocationContext *LCtx) const
Returns the SVal bound to the statement 'S' in the state's environment.
ProgramStateRef invalidateRegions(ArrayRef< const MemRegion * > Regions, ConstCFGElementRef Elem, unsigned BlockCount, const LocationContext *LCtx, bool CausesPointerEscape, InvalidatedSymbols *IS=nullptr, const CallEvent *Call=nullptr, RegionAndSymbolInvalidationTraits *ITraits=nullptr) const
Returns the state with bindings for the given regions cleared from the store.
~ProgramState()
Definition ProgramState.cpp:62
void dump() const
Definition ProgramState.cpp:522
ProgramStateRef bindLoc(Loc location, SVal V, const LocationContext *LCtx, bool notifyChanges=true) const
Definition ProgramState.cpp:113
friend class ConstraintManager
BasicValueFactory & getBasicVals() const
std::pair< ProgramStateRef, ProgramStateRef > assumeInBoundDual(DefinedOrUnknownSVal idx, DefinedOrUnknownSVal upperBound, QualType IndexType=QualType()) const
Definition ProgramState.cpp:316
AnalysisManager & getAnalysisManager() const
Definition ProgramState.cpp:526
void *const * FindGDM(void *K) const
Definition ProgramState.cpp:534
Information about invalidation for a particular region/symbol.
BasicValueFactory & getBasicValueFactory()
ASTContext & getContext()
QualType getArrayIndexType() const
virtual SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op, NonLoc lhs, NonLoc rhs, QualType resultTy)=0
Create a new value which represents a binary expression with two non- location operands.
SVal - This represents a symbolic expression, which can be either an L-value or an R-value.
bool isUnknownOrUndef() const
SymbolRef getAsSymbol(bool IncludeBaseRegions=false) const
If this SVal wraps a symbol return that SymbolRef.
std::optional< T > getAs() const
Convert to the specified SVal type, returning std::nullopt if this SVal is not of the desired type.
const MemRegion * getAsRegion() const
T castAs() const
Convert to the specified SVal type, asserting that this SVal is of the desired type.
A utility class that visits the reachable symbols using a custom SymbolVisitor.
bool scan(nonloc::LazyCompoundVal val)
Definition ProgramState.cpp:576
virtual bool scanReachableSymbols(Store S, const MemRegion *R, ScanReachableSymbols &Visitor)=0
Finds the transitive closure of symbols within the given region.
SmallVector< const MemRegion *, 8 > InvalidatedRegions
virtual void printJson(raw_ostream &Out, Store S, const char *NL, unsigned int Space, bool IsDot) const =0
SubRegion - A region that subsets another larger region.
llvm::iterator_range< symbol_iterator > symbols() const
A class responsible for cleaning up unused symbols.
void setReapedStore(StoreRef st)
Set to the value of the symbolic store after StoreManager::removeDeadBindings has been called.
SymbolicRegion - A special, "non-concrete" region.
TypedValueRegion - An abstract class representing regions having a typed value.
The simplest example of a concrete compound value is nonloc::CompoundVal, which represents a concrete...
Value representing integer constant.
While nonloc::CompoundVal covers a few simple use cases, nonloc::LazyCompoundVal is a more performant...
LLVM_ATTRIBUTE_RETURNS_NONNULL const LazyCompoundValData * getCVData() const
LLVM_ATTRIBUTE_RETURNS_NONNULL const TypedValueRegion * getRegion() const
This function itself is immaterial.
const void * getStore() const
It might return null.
@ PSK_EscapeOnBind
A pointer escapes due to binding its value to a location that the analyzer cannot track.
SValBuilder * createSimpleSValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context, ProgramStateManager &stateMgr)
llvm::DenseSet< SymbolRef > InvalidatedSymbols
void printDynamicTypeInfoJson(raw_ostream &Out, ProgramStateRef State, const char *NL="\n", unsigned int Space=0, bool IsDot=false)
IntrusiveRefCntPtr< const ProgramState > ProgramStateRef
const SymExpr * SymbolRef
std::unique_ptr< ConstraintManager >(* ConstraintManagerCreator)(ProgramStateManager &, ExprEngine *)
std::unique_ptr< StoreManager >(* StoreManagerCreator)(ProgramStateManager &)
void ProgramStateRetain(const ProgramState *state)
Increments the number of times this state is referenced.
Definition ProgramState.cpp:29
void ProgramStateRelease(const ProgramState *state)
Decrement the number of times this state is referenced.
Definition ProgramState.cpp:34
const void * Store
Store - This opaque type encapsulates an immutable mapping from locations to values.
The JSON file list parser is used to communicate input to InstallAPI.
bool isa(CodeGen::Address addr)
CFGBlock::ConstCFGElementRef ConstCFGElementRef
raw_ostream & Indent(raw_ostream &Out, const unsigned int Space, bool IsDot)
const FunctionProtoType * T
U cast(CodeGen::Address addr)
llvm::SmallVector< SVal, 0 > FailedToBindValues