clang 20.0.0git
ProgramState.cpp
Go to the documentation of this file.
1//= ProgramState.cpp - Path-Sensitive "State" for tracking values --*- C++ -*--=
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements ProgramState and ProgramStateManager.
10//
11//===----------------------------------------------------------------------===//
12
14#include "clang/Analysis/CFG.h"
21#include "llvm/Support/raw_ostream.h"
22#include <optional>
23
24using namespace clang;
25using namespace ento;
26
27namespace clang { namespace ento {
28/// Increments the number of times this state is referenced.
29
30void ProgramStateRetain(const ProgramState *state) {
31 ++const_cast<ProgramState*>(state)->refCount;
32}
33
34/// Decrement the number of times this state is referenced.
36 assert(state->refCount > 0);
37 ProgramState *s = const_cast<ProgramState*>(state);
38 if (--s->refCount == 0) {
39 ProgramStateManager &Mgr = s->getStateManager();
40 Mgr.StateSet.RemoveNode(s);
41 s->~ProgramState();
42 Mgr.freeStates.push_back(s);
43 }
44}
45}}
46
49 : stateMgr(mgr),
50 Env(env),
51 store(st.getStore()),
52 GDM(gdm),
53 refCount(0) {
55}
56
58 : stateMgr(RHS.stateMgr), Env(RHS.Env), store(RHS.store), GDM(RHS.GDM),
59 PosteriorlyOverconstrained(RHS.PosteriorlyOverconstrained), refCount(0) {
61}
62
64 if (store)
66}
67
68int64_t ProgramState::getID() const {
69 return getStateManager().Alloc.identifyKnownAlignedObject<ProgramState>(this);
70}
71
73 StoreManagerCreator CreateSMgr,
74 ConstraintManagerCreator CreateCMgr,
75 llvm::BumpPtrAllocator &alloc,
76 ExprEngine *ExprEng)
77 : Eng(ExprEng), EnvMgr(alloc), GDMFactory(alloc),
78 svalBuilder(createSimpleSValBuilder(alloc, Ctx, *this)),
79 CallEventMgr(new CallEventManager(alloc)), Alloc(alloc) {
80 StoreMgr = (*CreateSMgr)(*this);
81 ConstraintMgr = (*CreateCMgr)(*this, ExprEng);
82}
83
84
86 for (GDMContextsTy::iterator I=GDMContexts.begin(), E=GDMContexts.end();
87 I!=E; ++I)
88 I->second.second(I->second.first);
89}
90
92 ProgramStateRef state, const StackFrameContext *LCtx,
93 SymbolReaper &SymReaper) {
94
95 // This code essentially performs a "mark-and-sweep" of the VariableBindings.
96 // The roots are any Block-level exprs and Decls that our liveness algorithm
97 // tells us are live. We then see what Decls they may reference, and keep
98 // those around. This code more than likely can be made faster, and the
99 // frequency of which this method is called should be experimented with
100 // for optimum performance.
101 ProgramState NewState = *state;
102
103 NewState.Env = EnvMgr.removeDeadBindings(NewState.Env, SymReaper, state);
104
105 // Clean up the store.
106 StoreRef newStore = StoreMgr->removeDeadBindings(NewState.getStore(), LCtx,
107 SymReaper);
108 NewState.setStore(newStore);
109 SymReaper.setReapedStore(newStore);
110
111 return getPersistentState(NewState);
112}
113
115 SVal V,
116 const LocationContext *LCtx,
117 bool notifyChanges) const {
119 ProgramStateRef newState = makeWithStore(Mgr.StoreMgr->Bind(getStore(),
120 LV, V));
121 const MemRegion *MR = LV.getAsRegion();
122 if (MR && notifyChanges)
123 return Mgr.getOwningEngine().processRegionChange(newState, MR, LCtx);
124
125 return newState;
126}
127
130 const LocationContext *LCtx) const {
132 const MemRegion *R = loc.castAs<loc::MemRegionVal>().getRegion();
133 const StoreRef &newStore = Mgr.StoreMgr->BindDefaultInitial(getStore(), R, V);
134 ProgramStateRef new_state = makeWithStore(newStore);
135 return Mgr.getOwningEngine().processRegionChange(new_state, R, LCtx);
136}
137
141 const MemRegion *R = loc.castAs<loc::MemRegionVal>().getRegion();
142 const StoreRef &newStore = Mgr.StoreMgr->BindDefaultZero(getStore(), R);
143 ProgramStateRef new_state = makeWithStore(newStore);
144 return Mgr.getOwningEngine().processRegionChange(new_state, R, LCtx);
145}
146
149
151 RegionList Regions, const Stmt *S, unsigned Count,
152 const LocationContext *LCtx, bool CausedByPointerEscape,
154 RegionAndSymbolInvalidationTraits *ITraits) const {
156 for (const MemRegion *Reg : Regions)
157 Values.push_back(loc::MemRegionVal(Reg));
158
159 return invalidateRegions(Values, S, Count, LCtx, CausedByPointerEscape, IS,
160 Call, ITraits);
161}
162
164 ValueList Values, const Stmt *S, unsigned Count,
165 const LocationContext *LCtx, bool CausedByPointerEscape,
167 RegionAndSymbolInvalidationTraits *ITraits) const {
168
170 ExprEngine &Eng = Mgr.getOwningEngine();
171
172 InvalidatedSymbols InvalidatedSyms;
173 if (!IS)
174 IS = &InvalidatedSyms;
175
177 if (!ITraits)
178 ITraits = &ITraitsLocal;
179
180 StoreManager::InvalidatedRegions TopLevelInvalidated;
182 const StoreRef &NewStore = Mgr.StoreMgr->invalidateRegions(
183 getStore(), Values, S, Count, LCtx, Call, *IS, *ITraits,
184 &TopLevelInvalidated, &Invalidated);
185
186 ProgramStateRef NewState = makeWithStore(NewStore);
187
188 if (CausedByPointerEscape) {
189 NewState = Eng.notifyCheckersOfPointerEscape(
190 NewState, IS, TopLevelInvalidated, Call, *ITraits);
191 }
192
193 return Eng.processRegionChanges(NewState, IS, TopLevelInvalidated,
194 Invalidated, LCtx, Call);
195}
196
198 Store OldStore = getStore();
199 const StoreRef &newStore =
200 getStateManager().StoreMgr->killBinding(OldStore, LV);
201
202 if (newStore.getStore() == OldStore)
203 return this;
204
205 return makeWithStore(newStore);
206}
207
208/// We should never form a MemRegion that would wrap a TypedValueRegion of a
209/// reference type. What we actually wanted was to create a MemRegion refering
210/// to the pointee of that reference.
211SVal ProgramState::desugarReference(SVal Val) const {
212 const auto *TyReg = dyn_cast_or_null<TypedValueRegion>(Val.getAsRegion());
213 if (!TyReg || !TyReg->getValueType()->isReferenceType())
214 return Val;
215 return getSVal(TyReg);
216}
217
218/// SymbolicRegions are expected to be wrapped by an ElementRegion as a
219/// canonical representation. As a canonical representation, SymbolicRegions
220/// should be wrapped by ElementRegions before getting a FieldRegion.
221/// See f8643a9b31c4029942f67d4534c9139b45173504 why.
222SVal ProgramState::wrapSymbolicRegion(SVal Val) const {
223 const auto *BaseReg = dyn_cast_or_null<SymbolicRegion>(Val.getAsRegion());
224 if (!BaseReg)
225 return Val;
226
228 QualType ElemTy = BaseReg->getPointeeStaticType();
229 return loc::MemRegionVal{SM.GetElementZeroRegion(BaseReg, ElemTy)};
230}
231
234 const StackFrameContext *CalleeCtx) const {
235 const StoreRef &NewStore =
236 getStateManager().StoreMgr->enterStackFrame(getStore(), Call, CalleeCtx);
237 return makeWithStore(NewStore);
238}
239
241 const ImplicitParamDecl *SelfDecl = LCtx->getSelfDecl();
242 if (!SelfDecl)
243 return SVal();
244 return getSVal(getRegion(SelfDecl, LCtx));
245}
246
248 // We only want to do fetches from regions that we can actually bind
249 // values. For example, SymbolicRegions of type 'id<...>' cannot
250 // have direct bindings (but their can be bindings on their subregions).
251 if (!R->isBoundable())
252 return UnknownVal();
253
254 if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) {
255 QualType T = TR->getValueType();
257 return getSVal(R);
258 }
259
260 return UnknownVal();
261}
262
264 SVal V = getRawSVal(location, T);
265
266 // If 'V' is a symbolic value that is *perfectly* constrained to
267 // be a constant value, use that value instead to lessen the burden
268 // on later analysis stages (so we have less symbolic values to reason
269 // about).
270 // We only go into this branch if we can convert the APSInt value we have
271 // to the type of T, which is not always the case (e.g. for void).
272 if (!T.isNull() && (T->isIntegralOrEnumerationType() || Loc::isLocType(T))) {
273 if (SymbolRef sym = V.getAsSymbol()) {
274 if (const llvm::APSInt *Int = getStateManager()
276 .getSymVal(this, sym)) {
277 // FIXME: Because we don't correctly model (yet) sign-extension
278 // and truncation of symbolic values, we need to convert
279 // the integer value to the correct signedness and bitwidth.
280 //
281 // This shows up in the following:
282 //
283 // char foo();
284 // unsigned x = foo();
285 // if (x == 54)
286 // ...
287 //
288 // The symbolic value stored to 'x' is actually the conjured
289 // symbol for the call to foo(); the type of that symbol is 'char',
290 // not unsigned.
291 APSIntPtr NewV = getBasicVals().Convert(T, *Int);
292 if (V.getAs<Loc>())
293 return loc::ConcreteInt(NewV);
294 return nonloc::ConcreteInt(NewV);
295 }
296 }
297 }
298
299 return V;
300}
301
303 const LocationContext *LCtx,
304 SVal V, bool Invalidate) const{
305 Environment NewEnv =
306 getStateManager().EnvMgr.bindExpr(Env, EnvironmentEntry(S, LCtx), V,
307 Invalidate);
308 if (NewEnv == Env)
309 return this;
310
311 ProgramState NewSt = *this;
312 NewSt.Env = NewEnv;
313 return getStateManager().getPersistentState(NewSt);
314}
315
316[[nodiscard]] std::pair<ProgramStateRef, ProgramStateRef>
318 DefinedOrUnknownSVal UpperBound,
319 QualType indexTy) const {
320 if (Idx.isUnknown() || UpperBound.isUnknown())
321 return {this, this};
322
323 // Build an expression for 0 <= Idx < UpperBound.
324 // This is the same as Idx + MIN < UpperBound + MIN, if overflow is allowed.
325 // FIXME: This should probably be part of SValBuilder.
327 SValBuilder &svalBuilder = SM.getSValBuilder();
328 ASTContext &Ctx = svalBuilder.getContext();
329
330 // Get the offset: the minimum value of the array index type.
331 BasicValueFactory &BVF = svalBuilder.getBasicValueFactory();
332 if (indexTy.isNull())
333 indexTy = svalBuilder.getArrayIndexType();
334 nonloc::ConcreteInt Min(BVF.getMinValue(indexTy));
335
336 // Adjust the index.
337 SVal newIdx = svalBuilder.evalBinOpNN(this, BO_Add,
338 Idx.castAs<NonLoc>(), Min, indexTy);
339 if (newIdx.isUnknownOrUndef())
340 return {this, this};
341
342 // Adjust the upper bound.
343 SVal newBound =
344 svalBuilder.evalBinOpNN(this, BO_Add, UpperBound.castAs<NonLoc>(),
345 Min, indexTy);
346
347 if (newBound.isUnknownOrUndef())
348 return {this, this};
349
350 // Build the actual comparison.
351 SVal inBound = svalBuilder.evalBinOpNN(this, BO_LT, newIdx.castAs<NonLoc>(),
352 newBound.castAs<NonLoc>(), Ctx.IntTy);
353 if (inBound.isUnknownOrUndef())
354 return {this, this};
355
356 // Finally, let the constraint manager take care of it.
357 ConstraintManager &CM = SM.getConstraintManager();
358 return CM.assumeDual(this, inBound.castAs<DefinedSVal>());
359}
360
362 DefinedOrUnknownSVal UpperBound,
363 bool Assumption,
364 QualType indexTy) const {
365 std::pair<ProgramStateRef, ProgramStateRef> R =
366 assumeInBoundDual(Idx, UpperBound, indexTy);
367 return Assumption ? R.first : R.second;
368}
369
372 if (IsNull.isUnderconstrained())
373 return IsNull;
374 return ConditionTruthVal(!IsNull.getValue());
375}
376
378 return stateMgr->getSValBuilder().areEqual(this, Lhs, Rhs);
379}
380
382 if (V.isZeroConstant())
383 return true;
384
385 if (V.isConstant())
386 return false;
387
388 SymbolRef Sym = V.getAsSymbol(/* IncludeBaseRegion */ true);
389 if (!Sym)
390 return ConditionTruthVal();
391
392 return getStateManager().ConstraintMgr->isNull(this, Sym);
393}
394
396 ProgramState State(this,
397 EnvMgr.getInitialEnvironment(),
398 StoreMgr->getInitialStore(InitLoc),
399 GDMFactory.getEmptyMap());
400
401 return getPersistentState(State);
402}
403
405 ProgramStateRef FromState,
406 ProgramStateRef GDMState) {
407 ProgramState NewState(*FromState);
408 NewState.GDM = GDMState->GDM;
409 return getPersistentState(NewState);
410}
411
413
414 llvm::FoldingSetNodeID ID;
415 State.Profile(ID);
416 void *InsertPos;
417
418 if (ProgramState *I = StateSet.FindNodeOrInsertPos(ID, InsertPos))
419 return I;
420
421 ProgramState *newState = nullptr;
422 if (!freeStates.empty()) {
423 newState = freeStates.back();
424 freeStates.pop_back();
425 }
426 else {
427 newState = Alloc.Allocate<ProgramState>();
428 }
429 new (newState) ProgramState(State);
430 StateSet.InsertNode(newState, InsertPos);
431 return newState;
432}
433
434ProgramStateRef ProgramState::makeWithStore(const StoreRef &store) const {
435 ProgramState NewSt(*this);
436 NewSt.setStore(store);
437 return getStateManager().getPersistentState(NewSt);
438}
439
440ProgramStateRef ProgramState::cloneAsPosteriorlyOverconstrained() const {
441 ProgramState NewSt(*this);
442 NewSt.PosteriorlyOverconstrained = true;
443 return getStateManager().getPersistentState(NewSt);
444}
445
446void ProgramState::setStore(const StoreRef &newStore) {
447 Store newStoreStore = newStore.getStore();
448 if (newStoreStore)
449 stateMgr->getStoreManager().incrementReferenceCount(newStoreStore);
450 if (store)
451 stateMgr->getStoreManager().decrementReferenceCount(store);
452 store = newStoreStore;
453}
454
456 Base = desugarReference(Base);
457 Base = wrapSymbolicRegion(Base);
458 return getStateManager().StoreMgr->getLValueField(D, Base);
459}
460
462 StoreManager &SM = *getStateManager().StoreMgr;
463 Base = desugarReference(Base);
464 Base = wrapSymbolicRegion(Base);
465
466 // FIXME: This should work with `SM.getLValueField(D->getAnonField(), Base)`,
467 // but that would break some tests. There is probably a bug somewhere that it
468 // would expose.
469 for (const auto *I : D->chain()) {
470 Base = SM.getLValueField(cast<FieldDecl>(I), Base);
471 }
472 return Base;
473}
474
475//===----------------------------------------------------------------------===//
476// State pretty-printing.
477//===----------------------------------------------------------------------===//
478
479void ProgramState::printJson(raw_ostream &Out, const LocationContext *LCtx,
480 const char *NL, unsigned int Space,
481 bool IsDot) const {
482 Indent(Out, Space, IsDot) << "\"program_state\": {" << NL;
483 ++Space;
484
486
487 // Print the store.
488 Mgr.getStoreManager().printJson(Out, getStore(), NL, Space, IsDot);
489
490 // Print out the environment.
491 Env.printJson(Out, Mgr.getContext(), LCtx, NL, Space, IsDot);
492
493 // Print out the constraints.
494 Mgr.getConstraintManager().printJson(Out, this, NL, Space, IsDot);
495
496 // Print out the tracked dynamic types.
497 printDynamicTypeInfoJson(Out, this, NL, Space, IsDot);
498
499 // Print checker-specific data.
500 Mgr.getOwningEngine().