28#include "llvm/ADT/ImmutableMap.h"
29#include "llvm/ADT/STLExtras.h"
30#include "llvm/Support/TimeProfiler.h"
31#include "llvm/Support/raw_ostream.h"
53 llvm::PointerIntPair<const MemRegion *, 2> P;
58 explicit BindingKey(
const SubRegion *r,
const SubRegion *Base, Kind k)
59 : P(r, k | Symbolic), Data(reinterpret_cast<
uintptr_t>(
Base)) {
60 assert(r && Base &&
"Must have known regions.");
61 assert(getConcreteOffsetRegion() == Base &&
"Failed to store base region");
65 explicit BindingKey(
const MemRegion *r, uint64_t offset, Kind k)
66 : P(r, k), Data(offset) {
67 assert(r &&
"Must have known regions.");
68 assert(getOffset() == offset &&
"Failed to store offset");
75 bool isDirect()
const {
return P.getInt() & Direct; }
76 bool isDefault()
const {
return !isDirect(); }
77 bool hasSymbolicOffset()
const {
return P.getInt() & Symbolic; }
79 const MemRegion *
getRegion()
const {
return P.getPointer(); }
81 assert(!hasSymbolicOffset());
85 const SubRegion *getConcreteOffsetRegion()
const {
86 assert(hasSymbolicOffset());
87 return reinterpret_cast<const SubRegion *
>(
static_cast<uintptr_t>(Data));
90 const MemRegion *getBaseRegion()
const {
91 if (hasSymbolicOffset())
92 return getConcreteOffsetRegion()->getBaseRegion();
96 void Profile(llvm::FoldingSetNodeID& ID)
const {
97 ID.AddPointer(P.getOpaqueValue());
101 static BindingKey
Make(
const MemRegion *R, Kind k);
104 if (P.getOpaqueValue() <
X.P.getOpaqueValue())
106 if (P.getOpaqueValue() >
X.P.getOpaqueValue())
108 return Data <
X.Data;
112 return P.getOpaqueValue() ==
X.P.getOpaqueValue() &&
116 LLVM_DUMP_METHOD
void dump()
const;
119std::string locDescr(
Loc L) {
121 llvm::raw_string_ostream
OS(S);
127BindingKey BindingKey::Make(
const MemRegion *R, Kind k) {
136static inline raw_ostream &
operator<<(raw_ostream &Out, BindingKey K) {
137 Out <<
"\"kind\": \"" << (K.isDirect() ?
"Direct" :
"Default")
138 <<
"\", \"offset\": ";
140 if (!K.hasSymbolicOffset())
141 Out << K.getOffset();
150#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
151void BindingKey::dump()
const { llvm::errs() << *
this; }
162typedef llvm::ImmutableMap<const MemRegion *, ClusterBindings>
166class RegionBindingsRef :
public llvm::ImmutableMapRef<const MemRegion *,
168 ClusterBindings::Factory *CBFactory;
182 typedef llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>
185 RegionBindingsRef(ClusterBindings::Factory &CBFactory,
186 const RegionBindings::TreeTy *
T,
187 RegionBindings::TreeTy::Factory *F,
bool IsMainAnalysis)
188 : RegionBindingsRef(ParentTy(
T, F), CBFactory, IsMainAnalysis) {}
190 RegionBindingsRef(
const ParentTy &P, ClusterBindings::Factory &CBFactory,
192 : ParentTy(P), CBFactory(&CBFactory), IsMainAnalysis(IsMainAnalysis) {}
194 RegionBindingsRef removeCluster(
const MemRegion *BaseRegion)
const {
195 return RegionBindingsRef(ParentTy::remove(BaseRegion), *CBFactory,
199 RegionBindingsRef addBinding(BindingKey K,
SVal V)
const;
201 RegionBindingsRef addBinding(
const MemRegion *R,
202 BindingKey::Kind k,
SVal V)
const;
204 const SVal *lookup(BindingKey K)
const;
205 const SVal *lookup(
const MemRegion *R, BindingKey::Kind k)
const;
208 RegionBindingsRef removeBinding(BindingKey K);
210 RegionBindingsRef removeBinding(
const MemRegion *R,
213 RegionBindingsRef removeBinding(
const MemRegion *R) {
214 return removeBinding(R, BindingKey::Direct).
215 removeBinding(R, BindingKey::Default);
218 std::optional<SVal> getDirectBinding(
const MemRegion *R)
const;
222 std::optional<SVal> getDefaultBinding(
const MemRegion *R)
const;
225 Store asStore()
const {
226 llvm::PointerIntPair<Store, 1, bool> Ptr = {
227 asImmutableMap().getRootWithoutRetain(), IsMainAnalysis};
228 return reinterpret_cast<Store>(Ptr.getOpaqueValue());
231 bool isMainAnalysis()
const {
232 return IsMainAnalysis;
235 void printJson(raw_ostream &Out,
const char *NL =
"\n",
236 unsigned int Space = 0,
bool IsDot =
false)
const {
237 using namespace llvm;
238 DenseMap<const MemRegion *, std::string> StringifyCache;
239 auto ToString = [&StringifyCache](
const MemRegion *R) {
240 auto [Place, Inserted] = StringifyCache.try_emplace(R);
242 return Place->second;
244 raw_string_ostream
OS(Res);
251 std::pair<const MemRegion *, ImmutableMap<BindingKey, SVal>>;
252 using Binding = std::pair<BindingKey, SVal>;
254 const auto MemSpaceBeforeRegionName = [&ToString](
const Cluster *L,
260 return ToString(L->first) < ToString(R->first);
263 const auto SymbolicBeforeOffset = [&ToString](
const BindingKey &L,
264 const BindingKey &R) {
265 if (L.hasSymbolicOffset() && !R.hasSymbolicOffset())
267 if (!L.hasSymbolicOffset() && R.hasSymbolicOffset())
269 if (L.hasSymbolicOffset() && R.hasSymbolicOffset())
270 return ToString(L.getRegion()) < ToString(R.getRegion());
271 return L.getOffset() < R.getOffset();
274 const auto DefaultBindingBeforeDirectBindings =
275 [&SymbolicBeforeOffset](
const Binding *LPtr,
const Binding *RPtr) {
276 const BindingKey &L = LPtr->first;
277 const BindingKey &R = RPtr->first;
278 if (L.isDefault() && !R.isDefault())
280 if (!L.isDefault() && R.isDefault())
282 assert(L.isDefault() == R.isDefault());
283 return SymbolicBeforeOffset(L, R);
286 const auto AddrOf = [](
const auto &Item) {
return &Item; };
288 std::vector<const Cluster *> SortedClusters;
289 SortedClusters.reserve(std::distance(begin(), end()));
290 append_range(SortedClusters, map_range(*
this, AddrOf));
291 llvm::sort(SortedClusters, MemSpaceBeforeRegionName);
293 for (
auto [Idx,
C] : llvm::enumerate(SortedClusters)) {
296 <<
"{ \"cluster\": \"" << BaseRegion <<
"\", \"pointer\": \""
297 << (
const void *)BaseRegion <<
"\", \"items\": [" << NL;
299 std::vector<const Binding *> SortedBindings;
301 append_range(SortedBindings, map_range(
Bindings, AddrOf));
302 llvm::sort(SortedBindings, DefaultBindingBeforeDirectBindings);
305 for (
auto [Idx, B] : llvm::enumerate(SortedBindings)) {
306 const auto &[Key,
Value] = *B;
307 Indent(Out, Space, IsDot) <<
"{ " << Key <<
", \"value\": ";
308 Value.printJson(Out,
true);
310 if (Idx != SortedBindings.size() - 1)
315 Indent(Out, Space, IsDot) <<
"]}";
316 if (Idx != SortedClusters.size() - 1)
322 LLVM_DUMP_METHOD
void dump()
const { printJson(llvm::errs()); }
326 commitBindingsToCluster(
const MemRegion *BaseRegion,
337 std::optional<unsigned> BindingsLeft)
338 : RegionBindingsRef(
Base),
339 EscapedValuesDuringBind(&EscapedValuesDuringBind),
340 BindingsLeft(BindingsLeft) {}
343 return BindingsLeft.has_value() && BindingsLeft.value() == 0;
347 EscapedValuesDuringBind->push_back(
V);
354 for (
SVal V : llvm::make_range(Begin, End))
361 data_type_ref BindingKeyAndValue)
const {
363 BaseRegion, BindingKeyAndValue),
364 *EscapedValuesDuringBind, BindingsLeft};
369 RegionBindingsRef::removeCluster(BaseRegion), *EscapedValuesDuringBind,
374 std::optional<unsigned> NewBindingsLeft = BindingsLeft;
375 if (NewBindingsLeft.has_value()) {
376 assert(NewBindingsLeft.value() != 0);
377 NewBindingsLeft.value() -= 1;
381 if (NewBindingsLeft.value() == 0) {
383 K = BindingKey::Make(K.getRegion(), BindingKey::Default);
389 *EscapedValuesDuringBind, NewBindingsLeft};
399 std::optional<unsigned> BindingsLeft;
406RegionBindingsRef::getDirectBinding(
const MemRegion *R)
const {
407 const SVal *
V = lookup(R, BindingKey::Direct);
408 return V ? std::optional<SVal>(*
V) : std::nullopt;
412RegionBindingsRef::getDefaultBinding(
const MemRegion *R)
const {
413 const SVal *
V = lookup(R, BindingKey::Default);
414 return V ? std::optional<SVal>(*
V) : std::nullopt;
417RegionBindingsRef RegionBindingsRef::commitBindingsToCluster(
419 return RegionBindingsRef(ParentTy::add(BaseRegion,
Bindings), *CBFactory,
423RegionBindingsRef RegionBindingsRef::addBinding(BindingKey K, SVal
V)
const {
424 const MemRegion *
Base = K.getBaseRegion();
428 (ExistingCluster ? *ExistingCluster : CBFactory->getEmptyMap());
430 return commitBindingsToCluster(Base,
Bindings);
433RegionBindingsRef RegionBindingsRef::addBinding(
const MemRegion *R,
436 return addBinding(BindingKey::Make(R, k),
V);
439const SVal *RegionBindingsRef::lookup(BindingKey K)
const {
443 return Cluster->lookup(K);
446const SVal *RegionBindingsRef::lookup(
const MemRegion *R,
447 BindingKey::Kind k)
const {
448 return lookup(BindingKey::Make(R, k));
451RegionBindingsRef RegionBindingsRef::removeBinding(BindingKey K) {
452 const MemRegion *
Base = K.getBaseRegion();
458 if (NewCluster.isEmpty())
459 return removeCluster(Base);
460 return commitBindingsToCluster(Base, NewCluster);
463RegionBindingsRef RegionBindingsRef::removeBinding(
const MemRegion *R,
465 return removeBinding(BindingKey::Make(R, k));
473class InvalidateRegionsWorker;
475class RegionStoreManager :
public StoreManager {
477 RegionBindings::Factory RBFactory;
478 mutable ClusterBindings::Factory CBFactory;
480 typedef std::vector<SVal> SValListTy;
482 typedef llvm::DenseMap<
const LazyCompoundValData *,
483 SValListTy> LazyBindingsMapTy;
484 LazyBindingsMapTy LazyBindingsMap;
494 const unsigned SmallStructLimit;
504 const unsigned SmallArrayLimit;
510 const std::optional<unsigned> RegionStoreMaxBindingFanOutPlusOne;
514 void populateWorkList(InvalidateRegionsWorker &W,
515 ArrayRef<SVal> Values,
516 InvalidatedRegions *TopLevelRegions);
518 const AnalyzerOptions &getOptions() {
519 return StateMgr.getOwningEngine().getAnalysisManager().options;
523 RegionStoreManager(ProgramStateManager &mgr)
524 : StoreManager(mgr), RBFactory(mgr.getAllocator()),
525 CBFactory(mgr.getAllocator()),
526 SmallStructLimit(getOptions().RegionStoreSmallStructLimit),
527 SmallArrayLimit(getOptions().RegionStoreSmallArrayLimit),
528 RegionStoreMaxBindingFanOutPlusOne([&]() -> std::optional<unsigned> {
529 unsigned FanOut = getOptions().RegionStoreMaxBindingFanOut;
530 assert(FanOut != std::numeric_limits<unsigned>::max());
539 LimitedRegionBindingsRef
549 SVal ArrayToPointer(Loc Array, QualType ElementTy)
override;
553 StoreRef getInitialStore(
const LocationContext *InitLoc)
override {
554 bool IsMainAnalysis =
false;
555 if (
const auto *FD = dyn_cast<FunctionDecl>(InitLoc->
getDecl()))
556 IsMainAnalysis = FD->isMain() && !Ctx.getLangOpts().CPlusPlus;
557 return StoreRef(RegionBindingsRef(RegionBindingsRef::ParentTy(
558 RBFactory.getEmptyMap(), RBFactory),
559 CBFactory, IsMainAnalysis)
569 unsigned Count,
const LocationContext *LCtx,
570 RegionBindingsRef B, InvalidatedRegions *Invalidated);
572 StoreRef invalidateRegions(
Store store, ArrayRef<SVal> Values,
574 const LocationContext *LCtx,
const CallEvent *
Call,
576 RegionAndSymbolInvalidationTraits &ITraits,
577 InvalidatedRegions *Invalidated,
578 InvalidatedRegions *InvalidatedTopLevel)
override;
580 bool scanReachableSymbols(
Store S,
const MemRegion *R,
581 ScanReachableSymbols &Callbacks)
override;
583 LimitedRegionBindingsRef
587 const ElementRegion *R);
589 getSValFromInitListExpr(
const InitListExpr *ILE,
590 const SmallVector<uint64_t, 2> &ConcreteOffsets,
592 SVal getSValFromStringLiteral(
const StringLiteral *SL, uint64_t Offset,
596 BindResult
Bind(
Store store, Loc LV, SVal
V)
override {
597 llvm::SmallVector<SVal, 0> EscapedValuesDuringBind;
598 LimitedRegionBindingsRef BoundedBindings =
599 getRegionBindings(store, EscapedValuesDuringBind);
600 return BindResult{StoreRef(bind(BoundedBindings, LV,
V).asStore(), *
this),
601 std::move(EscapedValuesDuringBind)};
609 BindResult BindDefaultInitial(
Store store,
const MemRegion *R,
611 RegionBindingsRef B = getRegionBindings(store);
614 assert(!(B.getDefaultBinding(R) || B.getDirectBinding(R)) &&
615 "Double initialization!");
616 B = B.addBinding(BindingKey::Make(R, BindingKey::Default),
V);
618 StoreRef(B.asImmutableMap().getRootWithoutRetain(), *
this), {}};
623 BindResult BindDefaultZero(
Store store,
const MemRegion *R)
override {
633 if (
const auto *BR = dyn_cast<CXXBaseObjectRegion>(R))
634 if (BR->getDecl()->isEmpty())
635 return BindResult{StoreRef(store, *
this), {}};
637 llvm::SmallVector<SVal, 0> EscapedValuesDuringBind;
638 LimitedRegionBindingsRef B =
639 getRegionBindings(store, EscapedValuesDuringBind);
640 SVal
V = svalBuilder.makeZeroVal(Ctx.CharTy);
642 B = B.
addBinding(BindingKey::Make(R, BindingKey::Default),
V);
644 StoreRef(B.asImmutableMap().getRootWithoutRetain(), *
this),
645 std::move(EscapedValuesDuringBind)};
658 std::optional<LimitedRegionBindingsRef>
660 const RecordDecl *RD, nonloc::LazyCompoundVal LCV);
664 const TypedValueRegion *R, SVal
V);
668 const TypedValueRegion *R, SVal
V);
670 std::optional<LimitedRegionBindingsRef>
672 const ArrayType *AT, nonloc::LazyCompoundVal LCV);
675 const TypedValueRegion *R, SVal
V);
680 const TypedRegion *R, SVal DefaultVal);
685 StoreRef killBinding(
Store ST, Loc L)
override;
687 void incrementReferenceCount(
Store store)
override {
688 getRegionBindings(store).manualRetain();
694 void decrementReferenceCount(
Store store)
override {
695 getRegionBindings(store).manualRelease();
698 bool includedInBindings(
Store store,
const MemRegion *region)
const override;
713 SVal getBinding(
Store S, Loc L, QualType
T)
override {
714 return getBinding(getRegionBindings(S), L,
T);
718 const TypedValueRegion *R)
const;
720 getUniqueDefaultBinding(nonloc::LazyCompoundVal LCV)
const;
722 std::optional<SVal> getDefaultBinding(
Store S,
const MemRegion *R)
override {
723 RegionBindingsRef B = getRegionBindings(S);
740 SVal getBindingForLazySymbol(
const TypedValueRegion *R);
743 const TypedValueRegion *R,
746 SVal getLazyBinding(
const SubRegion *LazyBindingRegion,
747 RegionBindingsRef LazyBinding);
765 const MemRegion *superR,
766 const TypedValueRegion *R, QualType Ty);
772 std::pair<Store, const SubRegion *>
774 const SubRegion *originalRegion);
786 const SValListTy &getInterestingValues(nonloc::LazyCompoundVal LCV);
794 StoreRef removeDeadBindings(
Store store,
const StackFrameContext *LCtx,
795 SymbolReaper& SymReaper)
override;
801 RegionBindingsRef getRegionBindings(
Store store)
const {
802 llvm::PointerIntPair<Store, 1, bool> Ptr;
803 Ptr.setFromOpaqueValue(
const_cast<void *
>(store));
805 static_cast<const RegionBindings::TreeTy *
>(Ptr.getPointer()),
806 RBFactory.getTreeFactory(), Ptr.getInt()};
809 LimitedRegionBindingsRef
810 getRegionBindings(
Store store,
811 SmallVectorImpl<SVal> &EscapedValuesDuringBind)
const {
812 return LimitedRegionBindingsRef(
813 getRegionBindings(store), EscapedValuesDuringBind,
814 RegionStoreMaxBindingFanOutPlusOne);
817 void printJson(raw_ostream &Out,
Store S,
const char *NL =
"\n",
818 unsigned int Space = 0,
bool IsDot =
false)
const override;
820 void iterBindings(
Store store, BindingsHandler& f)
override {
821 RegionBindingsRef B = getRegionBindings(store);
822 for (
const auto &[Region, Cluster] : B) {
823 for (
const auto &[Key,
Value] : Cluster) {
826 if (
const SubRegion *R = dyn_cast<SubRegion>(Key.getRegion())) {
828 if (!f.HandleBinding(*
this, store, R,
Value))
842std::unique_ptr<StoreManager>
844 return std::make_unique<RegionStoreManager>(StMgr);
854enum GlobalsFilterKind {
863template <
typename DERIVED>
864class ClusterAnalysis {
866 typedef llvm::DenseMap<const MemRegion *, const ClusterBindings *> ClusterMap;
867 typedef const MemRegion * WorkListElement;
874 RegionStoreManager &RM;
889 bool includeEntireMemorySpace(
const MemRegion *Base) {
894 ClusterAnalysis(RegionStoreManager &rm, ProgramStateManager &StateMgr,
896 : RM(rm), Ctx(StateMgr.getContext()),
897 svalBuilder(StateMgr.getSValBuilder()), B(std::move(
b)) {}
899 RegionBindingsRef getRegionBindings()
const {
return B; }
901 bool isVisited(
const MemRegion *R) {
902 return Visited.count(getCluster(R));
905 void GenerateClusters() {
907 for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end();
909 const MemRegion *
Base = RI.getKey();
912 assert(!Cluster.isEmpty() &&
"Empty clusters should be removed");
913 static_cast<DERIVED*
>(
this)->VisitAddedToCluster(Base, Cluster);
917 if (
static_cast<DERIVED*
>(
this)->includeEntireMemorySpace(Base))
918 AddToWorkList(WorkListElement(Base), &Cluster);
923 if (
C && !Visited.insert(
C).second)
929 bool AddToWorkList(
const MemRegion *R) {
930 return static_cast<DERIVED*
>(
this)->AddToWorkList(R);
934 while (!WL.empty()) {
935 WorkListElement E = WL.pop_back_val();
936 const MemRegion *BaseR = E;
938 static_cast<DERIVED*
>(
this)->VisitCluster(BaseR, getCluster(BaseR));
942 void VisitAddedToCluster(
const MemRegion *baseR,
const ClusterBindings &
C) {}
947 static_cast<DERIVED*
>(
this)->VisitCluster(BaseR,
C);
956bool RegionStoreManager::scanReachableSymbols(
Store S,
const MemRegion *R,
957 ScanReachableSymbols &Callbacks) {
958 assert(R == R->
getBaseRegion() &&
"Should only be called for base regions");
959 RegionBindingsRef B = getRegionBindings(S);
965 for (ClusterBindings::iterator RI = Cluster->begin(), RE = Cluster->end();
967 if (!Callbacks.
scan(RI.getData()))
981 assert(K.hasSymbolicOffset() &&
"Not implemented for concrete offset keys");
987 if (
const FieldRegion *FR = dyn_cast<FieldRegion>(R))
989 Fields.push_back(FR->getDecl());
996 assert(K.hasSymbolicOffset() &&
"Not implemented for concrete offset keys");
1004 ptrdiff_t Delta = FieldsInBindingKey.size() - Fields.size();
1006 return std::equal(FieldsInBindingKey.begin() + Delta,
1007 FieldsInBindingKey.end(),
1010 return std::equal(FieldsInBindingKey.begin(), FieldsInBindingKey.end(),
1011 Fields.begin() - Delta);
1026 const SubRegion *Top, BindingKey TopKey,
1027 bool IncludeAllDefaultBindings) {
1029 if (TopKey.hasSymbolicOffset()) {
1031 Top = TopKey.getConcreteOffsetRegion();
1032 TopKey = BindingKey::Make(Top, BindingKey::Default);
1036 uint64_t Length = UINT64_MAX;
1038 if (std::optional<nonloc::ConcreteInt> ExtentCI =
1040 const llvm::APSInt &ExtentInt = ExtentCI->getValue();
1041 assert(ExtentInt.isNonNegative() || ExtentInt.isUnsigned());
1044 }
else if (
const FieldRegion *FR = dyn_cast<FieldRegion>(Top)) {
1045 if (FR->getDecl()->isBitField())
1046 Length = FR->getDecl()->getBitWidthValue();
1049 for (
const auto &StoreEntry : Cluster) {
1050 BindingKey NextKey = StoreEntry.first;
1051 if (NextKey.getRegion() == TopKey.getRegion()) {
1057 if (NextKey.getOffset() > TopKey.getOffset() &&
1058 NextKey.getOffset() - TopKey.getOffset() < Length) {
1063 }
else if (NextKey.getOffset() == TopKey.getOffset()) {
1070 if (IncludeAllDefaultBindings || NextKey.isDirect())
1074 }
else if (NextKey.hasSymbolicOffset()) {
1080 if (IncludeAllDefaultBindings || NextKey.isDirect())
1083 }
else if (
const SubRegion *BaseSR = dyn_cast<SubRegion>(
Base)) {
1086 if (BaseSR->isSubRegionOf(Top))
1097 const SubRegion *Top,
bool IncludeAllDefaultBindings) {
1099 BindingKey::Make(Top, BindingKey::Default),
1100 IncludeAllDefaultBindings);
1103LimitedRegionBindingsRef
1105 const SubRegion *Top) {
1106 BindingKey TopKey = BindingKey::Make(Top, BindingKey::Default);
1107 const MemRegion *ClusterHead = TopKey.getBaseRegion();
1109 if (Top == ClusterHead) {
1118 if (TopKey.hasSymbolicOffset()) {
1119 const SubRegion *Concrete = TopKey.getConcreteOffsetRegion();
1120 return B.
addBinding(Concrete, BindingKey::Default, UnknownVal());
1125 SmallVector<BindingPair, 32>
Bindings;
1130 for (BindingKey Key : llvm::make_first_range(
Bindings))
1137 if (TopKey.hasSymbolicOffset()) {
1138 const SubRegion *Concrete = TopKey.getConcreteOffsetRegion();
1139 Result =
Result.add(BindingKey::Make(Concrete, BindingKey::Default),
1149class InvalidateRegionsWorker :
public ClusterAnalysis<InvalidateRegionsWorker>
1153 const LocationContext *LCtx;
1155 RegionAndSymbolInvalidationTraits &ITraits;
1157 GlobalsFilterKind GlobalsFilter;
1159 InvalidateRegionsWorker(RegionStoreManager &rm, ProgramStateManager &stateMgr,
1161 unsigned count,
const LocationContext *lctx,
1163 RegionAndSymbolInvalidationTraits &ITraitsIn,
1165 GlobalsFilterKind GFK)
1166 : ClusterAnalysis<InvalidateRegionsWorker>(rm, stateMgr,
b), Elem(elem),
1167 Count(count), LCtx(lctx), IS(
is), ITraits(ITraitsIn), Regions(r),
1168 GlobalsFilter(GFK) {}
1171 void VisitBinding(SVal
V);
1173 using ClusterAnalysis::AddToWorkList;
1175 bool AddToWorkList(
const MemRegion *R);
1179 bool includeEntireMemorySpace(
const MemRegion *Base);
1183 bool isInitiallyIncludedGlobalRegion(
const MemRegion *R);
1187bool InvalidateRegionsWorker::AddToWorkList(
const MemRegion *R) {
1188 bool doNotInvalidateSuperRegion = ITraits.
hasTrait(
1190 const MemRegion *BaseR = doNotInvalidateSuperRegion ? R : R->
getBaseRegion();
1191 return AddToWorkList(WorkListElement(BaseR), getCluster(BaseR));
1194void InvalidateRegionsWorker::VisitBinding(SVal
V) {
1199 if (
const MemRegion *R =
V.getAsRegion()) {
1205 if (std::optional<nonloc::LazyCompoundVal> LCS =
1206 V.getAs<nonloc::LazyCompoundVal>()) {
1210 for (SVal
V : RM.getInterestingValues(*LCS))
1218void InvalidateRegionsWorker::VisitCluster(
const MemRegion *baseR,
1221 bool PreserveRegionsContents =
1226 for (SVal Val : llvm::make_second_range(*
C))
1230 if (!PreserveRegionsContents)
1234 if (
const auto *TO = dyn_cast<TypedValueRegion>(baseR)) {
1235 if (
const auto *RD = TO->getValueType()->getAsCXXRecordDecl()) {
1240 if (RD->isLambda() && RD->getLambdaCallOperator()->getBody()) {
1241 using namespace ast_matchers;
1243 const char *DeclBind =
"DeclBind";
1245 to(
varDecl(hasStaticStorageDuration()).bind(DeclBind)))));
1247 match(RefToStatic, *RD->getLambdaCallOperator()->getBody(),
1248 RD->getASTContext());
1250 for (BoundNodes &
Match : Matches) {
1251 auto *VD =
Match.getNodeAs<VarDecl>(DeclBind);
1252 const VarRegion *ToInvalidate =
1253 RM.getRegionManager().getVarRegion(VD, LCtx);
1254 AddToWorkList(ToInvalidate);
1262 if (
const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(baseR)) {
1263 for (
auto Var : BR->referenced_vars()) {
1264 const VarRegion *VR = Var.getCapturedRegion();
1265 const VarDecl *VD = VR->
getDecl();
1275 SVal
V = RM.getBinding(B, loc::MemRegionVal(VR));
1276 if (std::optional<Loc> L =
V.getAs<Loc>()) {
1286 if (
const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR))
1287 IS.insert(SR->getSymbol());
1290 if (PreserveRegionsContents)
1295 Regions->push_back(baseR);
1300 DefinedOrUnknownSVal
V =
1312 if (isInitiallyIncludedGlobalRegion(baseR)) {
1322 DefinedOrUnknownSVal
V =
1329 bool doNotInvalidateSuperRegion = ITraits.
hasTrait(
1333 if (doNotInvalidateSuperRegion) {
1336 std::optional<uint64_t> NumElements;
1339 if (
const ConstantArrayType *CAT = dyn_cast<ConstantArrayType>(AT))
1340 NumElements = CAT->getZExtSize();
1342 goto conjure_default;
1343 QualType ElementTy = AT->getElementType();
1351 AddToWorkList(SuperR);
1352 goto conjure_default;
1356 uint64_t UpperOffset = LowerOffset + *NumElements * ElemSize;
1357 bool UpperOverflow = UpperOffset < LowerOffset;
1362 goto conjure_default;
1366 goto conjure_default;
1368 for (
const auto &[BK,
V] : *
C) {
1369 std::optional<uint64_t> ROffset =
1370 BK.hasSymbolicOffset() ? std::optional<uint64_t>() : BK.getOffset();
1375 ((*ROffset >= LowerOffset && *ROffset < UpperOffset) ||
1377 (*ROffset >= LowerOffset || *ROffset < UpperOffset)) ||
1378 (LowerOffset == UpperOffset && *ROffset == LowerOffset))) {
1379 B = B.removeBinding(BK);
1382 const MemRegion *R =
V.getAsRegion();
1383 if (isa_and_nonnull<SymbolicRegion>(R))
1391 baseR, Elem, LCtx, AT->getElementType(), Count);
1396 DefinedOrUnknownSVal
V =
1402bool InvalidateRegionsWorker::isInitiallyIncludedGlobalRegion(
1403 const MemRegion *R) {
1404 switch (GlobalsFilter) {
1407 case GFK_SystemOnly:
1413 llvm_unreachable(
"unknown globals filter");
1416bool InvalidateRegionsWorker::includeEntireMemorySpace(
const MemRegion *Base) {
1417 if (isInitiallyIncludedGlobalRegion(Base))
1420 const MemSpaceRegion *MemSpace =
Base->getRawMemorySpace();
1425RegionBindingsRef RegionStoreManager::invalidateGlobalRegion(
1427 const LocationContext *LCtx, RegionBindingsRef B,
1428 InvalidatedRegions *Invalidated) {
1431 const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion(K);
1433 (
const void *)GS, Elem, LCtx,
1436 B = B.removeBinding(GS)
1437 .addBinding(BindingKey::Make(GS, BindingKey::Default),
V);
1442 Invalidated->push_back(GS);
1447void RegionStoreManager::populateWorkList(InvalidateRegionsWorker &W,
1448 ArrayRef<SVal> Values,
1449 InvalidatedRegions *TopLevelRegions) {
1450 for (SVal
V : Values) {
1451 if (
auto LCS =
V.getAs<nonloc::LazyCompoundVal>()) {
1452 for (SVal S : getInterestingValues(*LCS))
1453 if (
const MemRegion *R = S.getAsRegion())
1459 if (
const MemRegion *R =
V.getAsRegion()) {
1460 if (TopLevelRegions)
1461 TopLevelRegions->push_back(R);
1468StoreRef RegionStoreManager::invalidateRegions(
1471 RegionAndSymbolInvalidationTraits &ITraits,
1472 InvalidatedRegions *TopLevelRegions, InvalidatedRegions *Invalidated) {
1473 GlobalsFilterKind GlobalsFilter;
1475 if (
Call->isInSystemHeader())
1476 GlobalsFilter = GFK_SystemOnly;
1478 GlobalsFilter = GFK_All;
1480 GlobalsFilter = GFK_None;
1483 RegionBindingsRef B = getRegionBindings(store);
1484 InvalidateRegionsWorker W(*
this, StateMgr, B, Elem, Count, LCtx, IS, ITraits,
1485 Invalidated, GlobalsFilter);
1488 W.GenerateClusters();
1491 populateWorkList(W, Values, TopLevelRegions);
1496 B = W.getRegionBindings();
1502 switch (GlobalsFilter) {
1504 B = invalidateGlobalRegion(MemRegion::GlobalInternalSpaceRegionKind, Elem,
1505 Count, LCtx, B, Invalidated);
1507 case GFK_SystemOnly:
1508 B = invalidateGlobalRegion(MemRegion::GlobalSystemSpaceRegionKind, Elem,
1509 Count, LCtx, B, Invalidated);
1515 return StoreRef(B.asStore(), *
this);
1528SVal RegionStoreManager::ArrayToPointer(Loc Array, QualType
T) {
1533 return UnknownVal();
1535 const SubRegion *R =
1538 return loc::MemRegionVal(MRMgr.getElementRegion(
T, ZeroIdx, R, Ctx));
1555 if (L.
getAs<loc::ConcreteInt>()) {
1556 return UnknownVal();
1558 if (!L.
getAs<loc::MemRegionVal>()) {
1559 return UnknownVal();
1565 return UnknownVal();
1570 if (
const auto *TVR = dyn_cast<TypedValueRegion>(MR))
1571 T = TVR->getValueType();
1572 else if (
const auto *TR = dyn_cast<TypedRegion>(MR))
1574 else if (
const auto *SR = dyn_cast<SymbolicRegion>(MR))
1575 T = SR->getPointeeStaticType();
1577 assert(!
T.isNull() &&
"Unable to auto-detect binding type!");
1578 assert(!
T->
isVoidType() &&
"Attempting to dereference a void pointer!");
1591 return UnknownVal();
1602 return getBindingForStruct(B, R);
1606 return createLazyBinding(B, R);
1610 return getBindingForArray(B, R);
1612 return UnknownVal();
1617 return UnknownVal();
1619 if (
const FieldRegion* FR = dyn_cast<FieldRegion>(R))
1620 return svalBuilder.
evalCast(getBindingForField(B, FR),
T, QualType{});
1622 if (
const ElementRegion* ER = dyn_cast<ElementRegion>(R)) {
1628 return svalBuilder.
evalCast(getBindingForElement(B, ER),
T, QualType{});
1631 if (
const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) {
1638 return svalBuilder.
evalCast(getBindingForObjCIvar(B, IVR),
T, QualType{});
1641 if (
const VarRegion *VR = dyn_cast<VarRegion>(R)) {
1648 return svalBuilder.
evalCast(getBindingForVar(B, VR),
T, QualType{});
1651 const SVal *
V = B.lookup(R, BindingKey::Direct);
1665 return UndefinedVal();
1675 RegionTy = TVR->getValueType();
1678 RegionTy = SR->getSymbol()->getType();
1690static std::optional<nonloc::LazyCompoundVal>
1692 const SubRegion *R,
bool AllowSubregionBindings) {
1693 std::optional<SVal>
V = B.getDefaultBinding(R);
1695 return std::nullopt;
1697 std::optional<nonloc::LazyCompoundVal> LCV =
1700 return std::nullopt;
1705 if (!RegionTy.
isNull() &&
1707 QualType SourceRegionTy = LCV->getRegion()->getValueType();
1709 return std::nullopt;
1712 if (!AllowSubregionBindings) {
1719 return std::nullopt;
1725std::pair<Store, const SubRegion *>
1728 const SubRegion *originalRegion) {
1729 if (originalRegion != R) {
1730 if (std::optional<nonloc::LazyCompoundVal>
V =
1732 return std::make_pair(
V->getStore(),
V->getRegion());
1735 typedef std::pair<Store, const SubRegion *> StoreRegionPair;
1736 StoreRegionPair
Result = StoreRegionPair();
1738 if (
const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
1743 Result.second = MRMgr.getElementRegionWithSuper(ER,
Result.second);
1745 }
else if (
const FieldRegion *FR = dyn_cast<FieldRegion>(R)) {
1750 Result.second = MRMgr.getFieldRegionWithSuper(FR,
Result.second);
1752 }
else if (
const CXXBaseObjectRegion *BaseReg =
1753 dyn_cast<CXXBaseObjectRegion>(R)) {
1760 Result.second = MRMgr.getCXXBaseObjectRegionWithSuper(BaseReg,
1772static SmallVector<uint64_t, 2>
1774 assert(CAT &&
"ConstantArrayType should not be null");
1779 }
while ((CAT = dyn_cast<ConstantArrayType>(CAT->
getElementType())));
1797static std::pair<SmallVector<SVal, 2>,
const MemRegion *>
1799 assert(ER &&
"ConstantArrayType should not be null");
1803 SValOffsets.push_back(ER->
getIndex());
1805 ER = dyn_cast<ElementRegion>(
Base);
1807 return {SValOffsets,
Base};
1831static std::optional<SVal>
1852 DstOffsets.resize(SrcOffsets.size());
1853 auto ExtentIt = ArrayExtents.begin();
1854 auto OffsetIt = DstOffsets.begin();
1856 for (
SVal V : llvm::reverse(SrcOffsets)) {
1859 const llvm::APSInt &Offset = CI->getValue();
1860 if (Offset.isNegative() || Offset.uge(*(ExtentIt++)))
1863 *(OffsetIt++) = Offset.getZExtValue();
1871 return std::nullopt;
1874std::optional<SVal> RegionStoreManager::getConstantValFromConstArrayInitializer(
1876 assert(R &&
"ElementRegion should not be null");
1879 SmallVector<SVal, 2> SValOffsets;
1880 const MemRegion *
Base;
1882 const VarRegion *VR = dyn_cast<VarRegion>(Base);
1884 return std::nullopt;
1886 assert(!SValOffsets.empty() &&
"getElementRegionOffsets guarantees the "
1887 "offsets vector is not empty.");
1891 const VarDecl *VD = VR->
getDecl();
1895 return std::nullopt;
1910 return std::nullopt;
1916 return std::nullopt;
1927 if (SValOffsets.size() != Extents.size())
1928 return std::nullopt;
1930 SmallVector<uint64_t, 2> ConcreteOffsets;
1932 SValOffsets, Extents, ConcreteOffsets))
1938 if (
const auto *ILE = dyn_cast<InitListExpr>(
Init))
1939 return getSValFromInitListExpr(ILE, ConcreteOffsets, R->
getElementType());
1944 if (
const auto *SL = dyn_cast<StringLiteral>(
Init))
1945 return getSValFromStringLiteral(SL, ConcreteOffsets.front(),
1950 return std::nullopt;
1970std::optional<SVal> RegionStoreManager::getSValFromInitListExpr(
1971 const InitListExpr *ILE,
const SmallVector<uint64_t, 2> &Offsets,
1973 assert(ILE &&
"InitListExpr should not be null");
1975 for (uint64_t Offset : Offsets) {
1982 if (
const auto *SL = dyn_cast<StringLiteral>(ILE->
getInit(0)))
1983 return getSValFromStringLiteral(SL, Offset, ElemT);
1991 const Expr *E = ILE->
getInit(Offset);
1992 const auto *IL = dyn_cast<InitListExpr>(E);
2006 return std::nullopt;
2034SVal RegionStoreManager::getSValFromStringLiteral(
const StringLiteral *SL,
2037 assert(SL &&
"StringLiteral should not be null");
2053 if (
const std::optional<SVal> &ParentValue =
2054 B.getDirectBinding(BaseRegion)) {
2055 if (
SymbolRef ParentValueAsSym = ParentValue->getAsSymbol())
2058 if (ParentValue->isUndef())
2067 return std::nullopt;
2071 const ElementRegion* R) {
2073 if (
const std::optional<SVal> &
V = B.getDirectBinding(R))
2079 if (
const StringRegion *StrR = dyn_cast<StringRegion>(superR)) {
2085 return UnknownVal();
2086 if (
const auto CI = R->
getIndex().
getAs<nonloc::ConcreteInt>()) {
2087 const llvm::APSInt &Idx = CI->getValue();
2089 return UndefinedVal();
2090 const StringLiteral *SL = StrR->getStringLiteral();
2091 return getSValFromStringLiteral(SL, Idx.getZExtValue(),
T);
2094 if (std::optional<SVal>
V = getConstantValFromConstArrayInitializer(B, R))
2100 return UnknownVal();
2112 return UnknownVal();
2114 if (
const TypedValueRegion *baseR = dyn_cast<TypedValueRegion>(O.
getRegion()))
2118 return getBindingForFieldOrElementCommon(B, R, R->
getElementType());
2122 const FieldRegion* R) {
2125 if (
const std::optional<SVal> &
V = B.getDirectBinding(R))
2129 const FieldDecl *FD = R->
getDecl();
2132 if (
const auto *VR = dyn_cast<VarRegion>(superR)) {
2133 const VarDecl *VD = VR->
getDecl();
2134 QualType RecordVarTy = VD->
getType();
2142 if (
const auto *InitList = dyn_cast<InitListExpr>(
Init)) {
2143 if (Index < InitList->getNumInits()) {
2144 if (
const Expr *FieldInit = InitList->getInit(Index))
2169 if (
const auto *Base = dyn_cast<TypedValueRegion>(R->
getBaseRegion()))
2173 return getBindingForFieldOrElementCommon(B, R, Ty);
2176std::optional<SVal> RegionStoreManager::getBindingForDerivedDefaultValue(
2178 const TypedValueRegion *R, QualType Ty) {
2180 if (
const std::optional<SVal> &D = B.getDefaultBinding(superR)) {
2196 llvm_unreachable(
"Unknown default value");
2199 return std::nullopt;
2202SVal RegionStoreManager::getLazyBinding(
const SubRegion *LazyBindingRegion,
2203 RegionBindingsRef LazyBinding) {
2205 if (
const ElementRegion *ER = dyn_cast<ElementRegion>(LazyBindingRegion))
2206 Result = getBindingForElement(LazyBinding, ER);
2208 Result = getBindingForField(LazyBinding,
2233 const TypedValueRegion *R,
2240 Store lazyBindingStore =
nullptr;
2241 const SubRegion *lazyBindingRegion =
nullptr;
2242 std::tie(lazyBindingStore, lazyBindingRegion) = findLazyBinding(B, R, R);
2243 if (lazyBindingRegion)
2244 return getLazyBinding(lazyBindingRegion,
2245 getRegionBindings(lazyBindingStore));
2249 bool hasSymbolicIndex =
false;
2265 bool hasPartialLazyBinding =
false;
2267 const SubRegion *SR = R;
2270 if (std::optional<SVal> D =
2271 getBindingForDerivedDefaultValue(B, Base, R, Ty)) {
2272 if (D->getAs<nonloc::LazyCompoundVal>()) {
2273 hasPartialLazyBinding =
true;
2280 if (
const ElementRegion *ER = dyn_cast<ElementRegion>(Base)) {
2281 NonLoc index = ER->getIndex();
2283 hasSymbolicIndex =
true;
2288 SR = dyn_cast<SubRegion>(Base);
2295 if (
const TypedValueRegion *typedSuperR =
2297 if (typedSuperR->getValueType()->isVectorType())
2298 return UnknownVal();
2306 if (hasSymbolicIndex)
2307 return UnknownVal();
2313 if (
const std::optional<SVal> &
V = B.getDefaultBinding(R))
2315 return UndefinedVal();
2324 const ObjCIvarRegion* R) {
2326 if (
const std::optional<SVal> &
V = B.getDirectBinding(R))
2332 if (
const std::optional<SVal> &
V = B.getDefaultBinding(superR)) {
2337 return UnknownVal();
2340 return getBindingForLazySymbol(R);
2344 const VarRegion *R) {
2347 if (std::optional<SVal>
V = B.getDirectBinding(R))
2350 if (std::optional<SVal>
V = B.getDefaultBinding(R))
2354 const VarDecl *VD = R->
getDecl();
2370 return UnknownVal();
2383 if (B.isMainAnalysis())
2395 if (std::optional<SVal>
V = getBindingForDerivedDefaultValue(B, MS, R,
T)) {
2396 assert(!
V->getAs<nonloc::LazyCompoundVal>());
2403 return UndefinedVal();
2406SVal RegionStoreManager::getBindingForLazySymbol(
const TypedValueRegion *R) {
2411const RegionStoreManager::SValListTy &
2412RegionStoreManager::getInterestingValues(nonloc::LazyCompoundVal LCV) {
2414 LazyBindingsMapTy::iterator I = LazyBindingsMap.find(LCV.
getCVData());
2415 if (I != LazyBindingsMap.end())
2421 const SubRegion *LazyR = LCV.
getRegion();
2422 RegionBindingsRef B = getRegionBindings(LCV.
getStore());
2428 return (LazyBindingsMap[LCV.
getCVData()] = std::move(List));
2430 SmallVector<BindingPair, 32>
Bindings;
2433 for (SVal
V : llvm::make_second_range(
Bindings)) {
2434 if (
V.isUnknownOrUndef() ||
V.isConstant())
2437 if (
auto InnerLCV =
V.getAs<nonloc::LazyCompoundVal>()) {
2438 const SValListTy &InnerList = getInterestingValues(*InnerLCV);
2439 llvm::append_range(List, InnerList);
2445 return (LazyBindingsMap[LCV.
getCVData()] = std::move(List));
2449 const TypedValueRegion *R) {
2450 if (std::optional<nonloc::LazyCompoundVal>
V =
2458 const TypedValueRegion *R) {
2459 const RecordDecl *RD =
2462 return UnknownVal();
2471 if (std::optional<SVal> Val = getUniqueDefaultBinding(B, R))
2473 return createLazyBinding(B, R);
2477 const TypedValueRegion *R) {
2479 "Only constant array types can have compound bindings.");
2481 return createLazyBinding(B, R);
2484bool RegionStoreManager::includedInBindings(
Store store,
2485 const MemRegion *region)
const {
2486 RegionBindingsRef B = getRegionBindings(store);
2490 if (B.lookup(region))
2494 for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI) {
2496 for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end();
2498 SVal D = CI.getData();
2512StoreRef RegionStoreManager::killBinding(
Store ST, Loc L) {
2513 if (std::optional<loc::MemRegionVal> LV = L.
getAs<loc::MemRegionVal>())
2514 if (
const MemRegion* R = LV->getRegion())
2515 return StoreRef(getRegionBindings(ST)
2518 .getRootWithoutRetain(),
2521 return StoreRef(ST, *
this);
2524LimitedRegionBindingsRef
2526 llvm::TimeTraceScope TimeScope(
"RegionStoreManager::bind",
2527 [&L]() {
return locDescr(L); });
2533 auto MemRegVal = L.
getAs<loc::MemRegionVal>();
2537 const MemRegion *R = MemRegVal->getRegion();
2541 if (
const auto *SymReg = dyn_cast<SymbolicRegion>(R)) {
2542 QualType Ty = SymReg->getPointeeStaticType();
2544 Ty = StateMgr.getContext().CharTy;
2545 R = GetElementZeroRegion(SymReg, Ty);
2549 if (
const TypedValueRegion* TR = dyn_cast<TypedValueRegion>(R)) {
2552 return bindArray(B, TR,
V);
2554 return bindStruct(B, TR,
V);
2556 return bindVector(B, TR,
V);
2558 return bindAggregate(B, TR,
V);
2562 "'this' pointer is not an l-value and is not assignable");
2569 : BindingKey::Direct;
2570 return NewB.addBinding(BindingKey::Make(R, KeyKind),
V);
2573LimitedRegionBindingsRef
2575 const MemRegion *R, QualType
T) {
2602std::optional<LimitedRegionBindingsRef> RegionStoreManager::tryBindSmallArray(
2604 const ArrayType *AT, nonloc::LazyCompoundVal LCV) {
2608 auto CAT = dyn_cast<ConstantArrayType>(AT);
2612 return std::nullopt;
2616 return std::nullopt;
2620 if (ArrSize > SmallArrayLimit)
2621 return std::nullopt;
2623 LimitedRegionBindingsRef NewB = B;
2625 for (uint64_t i = 0; i < ArrSize; ++i) {
2627 const ElementRegion *SrcER =
2628 MRMgr.getElementRegion(Ty, Idx, LCV.
getRegion(), Ctx);
2629 SVal
V = getBindingForElement(getRegionBindings(LCV.
getStore()), SrcER);
2631 const ElementRegion *DstER = MRMgr.getElementRegion(Ty, Idx, R, Ctx);
2632 NewB = bind(NewB, loc::MemRegionVal(DstER),
V);
2638LimitedRegionBindingsRef
2640 const TypedValueRegion *R, SVal
Init) {
2641 llvm::TimeTraceScope TimeScope(
"RegionStoreManager::bindArray",
2648 std::optional<uint64_t>
Size;
2650 if (
const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(AT))
2656 if (std::optional<loc::MemRegionVal> MRV =
Init.getAs<loc::MemRegionVal>()) {
2658 return bindAggregate(B, R,
V);
2662 if (std::optional LCV =
Init.getAs<nonloc::LazyCompoundVal>()) {
2663 if (std::optional NewB = tryBindSmallArray(B, R, AT, *LCV))
2666 return bindAggregate(B, R,
Init);
2669 if (
Init.isUnknown())
2670 return bindAggregate(B, R, UnknownVal());
2673 const nonloc::CompoundVal& CV =
Init.castAs<nonloc::CompoundVal>();
2677 LimitedRegionBindingsRef NewB = B;
2679 for (;
Size ? i < *
Size :
true; ++i, ++VI) {
2687 const ElementRegion *ER = MRMgr.getElementRegion(ElementTy, Idx, R, Ctx);
2690 NewB = bindStruct(NewB, ER, *VI);
2692 NewB = bindArray(NewB, ER, *VI);
2694 NewB = bind(NewB, loc::MemRegionVal(ER), *VI);
2700 if (!Size || i < *Size)
2701 NewB = setImplicitDefaultValue(NewB, R, ElementTy);
2706LimitedRegionBindingsRef
2708 const TypedValueRegion *R, SVal
V) {
2709 llvm::TimeTraceScope TimeScope(
"RegionStoreManager::bindVector",
2715 const VectorType *VT =
T->
castAs<VectorType>();
2719 return bindAggregate(B, R,
V);
2725 return bindAggregate(B, R, UnknownVal());
2729 nonloc::CompoundVal CV =
V.
castAs<nonloc::CompoundVal>();
2732 LimitedRegionBindingsRef NewB = B;
2734 for ( ; index != numElements ; ++index) {
2742 const ElementRegion *ER = MRMgr.getElementRegion(ElemType, Idx, R, Ctx);
2745 NewB = bindArray(NewB, ER, *VI);
2747 NewB = bindStruct(NewB, ER, *VI);
2749 NewB = bind(NewB, loc::MemRegionVal(ER), *VI);
2756 const TypedValueRegion *R)
const {
2758 return std::nullopt;
2760 const auto *Cluster = B.lookup(R);
2761 if (!Cluster || !llvm::hasSingleElement(*Cluster))
2762 return std::nullopt;
2764 const auto [Key,
Value] = *Cluster->begin();
2765 return Key.isDirect() ? std::optional<SVal>{} :
Value;
2769RegionStoreManager::getUniqueDefaultBinding(nonloc::LazyCompoundVal LCV)
const {
2770 auto B = getRegionBindings(LCV.
getStore());
2771 return getUniqueDefaultBinding(B, LCV.
getRegion());
2774std::optional<LimitedRegionBindingsRef> RegionStoreManager::tryBindSmallStruct(
2776 const RecordDecl *RD, nonloc::LazyCompoundVal LCV) {
2794 if (std::optional<SVal> Val = getUniqueDefaultBinding(LCV)) {
2795 return B.
addBinding(BindingKey::Make(R, BindingKey::Default), Val.value());
2800 if (
const CXXRecordDecl *
Class = dyn_cast<CXXRecordDecl>(RD))
2801 if (
Class->getNumBases() != 0 ||
Class->getNumVBases() != 0)
2802 return std::nullopt;
2804 for (
const auto *FD : RD->
fields()) {
2810 if (Fields.size() == SmallStructLimit)
2811 return std::nullopt;
2821 return std::nullopt;
2823 Fields.push_back(FD);
2826 LimitedRegionBindingsRef NewB = B;
2828 for (
const FieldDecl *Field : Fields) {
2829 const FieldRegion *SourceFR = MRMgr.getFieldRegion(Field, LCV.
getRegion());
2830 SVal
V = getBindingForField(getRegionBindings(LCV.
getStore()), SourceFR);
2832 const FieldRegion *DestFR = MRMgr.getFieldRegion(Field, R);
2833 NewB = bind(NewB, loc::MemRegionVal(DestFR),
V);
2839LimitedRegionBindingsRef
2841 const TypedValueRegion *R, SVal
V) {
2842 llvm::TimeTraceScope TimeScope(
"RegionStoreManager::bindStruct",
2855 if (std::optional<nonloc::LazyCompoundVal> LCV =
2856 V.getAs<nonloc::LazyCompoundVal>()) {
2857 if (std::optional NewB = tryBindSmallStruct(B, R, RD, *LCV))
2859 return bindAggregate(B, R,
V);
2862 return bindAggregate(B, R,
V);
2868 return bindAggregate(B, R, UnknownVal());
2886 const nonloc::CompoundVal& CV =
V.
castAs<nonloc::CompoundVal>();
2889 LimitedRegionBindingsRef NewB = B;
2893 if (
const auto *CRD = dyn_cast<CXXRecordDecl>(RD)) {
2901 assert((CRD->isAggregate() || (Ctx.
getLangOpts().ObjC && VI == VE)) &&
2902 "Non-aggregates are constructed with a constructor!");
2904 for (
const auto &B : CRD->bases()) {
2906 assert(!B.isVirtual() &&
"Aggregates cannot have virtual base classes!");
2913 QualType BTy = B.getType();
2917 assert(BRD &&
"Base classes must be C++ classes!");
2919 const CXXBaseObjectRegion *BR =
2920 MRMgr.getCXXBaseObjectRegion(BRD, R,
false);
2922 NewB = bindStruct(NewB, BR, *VI);
2939 if (FI->isUnnamedBitField())
2942 QualType FTy = FI->getType();
2943 const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);
2946 NewB = bindArray(NewB, FR, *VI);
2948 NewB = bindStruct(NewB, FR, *VI);
2950 NewB = bind(NewB, loc::MemRegionVal(FR), *VI);
2959 NewB = NewB.
addBinding(R, BindingKey::Default,
2966LimitedRegionBindingsRef
2968 const TypedRegion *R, SVal Val) {
2969 llvm::TimeTraceScope TimeScope(
"RegionStoreManager::bindAggregate",
2976 return removeSubRegionBindings(B, R).
addBinding(R, BindingKey::Default, Val);
2984class RemoveDeadBindingsWorker
2985 :
public ClusterAnalysis<RemoveDeadBindingsWorker> {
2986 SmallVector<const SymbolicRegion *, 12> Postponed;
2987 SymbolReaper &SymReaper;
2988 const StackFrameContext *CurrentLCtx;
2991 RemoveDeadBindingsWorker(RegionStoreManager &rm,
2992 ProgramStateManager &stateMgr,
2993 RegionBindingsRef
b, SymbolReaper &symReaper,
2994 const StackFrameContext *LCtx)
2995 : ClusterAnalysis<RemoveDeadBindingsWorker>(rm, stateMgr,
b),
2996 SymReaper(symReaper), CurrentLCtx(LCtx) {}
2999 void VisitAddedToCluster(
const MemRegion *baseR,
const ClusterBindings &
C);
3001 using ClusterAnalysis<RemoveDeadBindingsWorker>::VisitCluster;
3003 using ClusterAnalysis::AddToWorkList;
3005 bool AddToWorkList(
const MemRegion *R);
3007 bool UpdatePostponed();
3008 void VisitBinding(SVal
V);
3012bool RemoveDeadBindingsWorker::AddToWorkList(
const MemRegion *R) {
3014 return AddToWorkList(WorkListElement(BaseR), getCluster(BaseR));
3017void RemoveDeadBindingsWorker::VisitAddedToCluster(
const MemRegion *baseR,
3020 if (
const VarRegion *VR = dyn_cast<VarRegion>(baseR)) {
3021 if (SymReaper.
isLive(VR))
3022 AddToWorkList(baseR, &
C);
3027 if (
const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) {
3028 if (SymReaper.
isLive(SR->getSymbol()))
3029 AddToWorkList(SR, &
C);
3031 Postponed.push_back(SR);
3037 AddToWorkList(baseR, &
C);
3042 if (
const CXXThisRegion *TR = dyn_cast<CXXThisRegion>(baseR)) {
3043 const auto *StackReg =
3045 const StackFrameContext *RegCtx = StackReg->getStackFrame();
3047 (RegCtx == CurrentLCtx || RegCtx->
isParentOf(CurrentLCtx)))
3048 AddToWorkList(TR, &
C);
3052void RemoveDeadBindingsWorker::VisitCluster(
const MemRegion *baseR,
3059 if (
const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(baseR))
3060 SymReaper.
markLive(SymR->getSymbol());
3062 for (
const auto &[Key, Val] : *
C) {
3070void RemoveDeadBindingsWorker::VisitBinding(SVal
V) {
3073 if (
auto LCS =
V.getAs<nonloc::LazyCompoundVal>()) {
3076 for (SVal
V : RM.getInterestingValues(*LCS)) {
3077 if (
auto DepLCS =
V.getAs<nonloc::LazyCompoundVal>())
3087 if (
const MemRegion *R =
V.getAsRegion()) {
3092 if (
const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(R)) {
3093 for (
auto Var : BR->referenced_vars())
3094 AddToWorkList(Var.getCapturedRegion());
3104bool RemoveDeadBindingsWorker::UpdatePostponed() {
3109 for (
const SymbolicRegion *SR : Postponed) {
3110 if (SymReaper.
isLive(SR->getSymbol())) {
3119StoreRef RegionStoreManager::removeDeadBindings(
Store store,
3120 const StackFrameContext *LCtx,
3121 SymbolReaper& SymReaper) {
3122 RegionBindingsRef B = getRegionBindings(store);
3123 RemoveDeadBindingsWorker W(*
this, StateMgr, B, SymReaper, LCtx);
3124 W.GenerateClusters();
3127 for (
const MemRegion *Reg : SymReaper.
regions()) {
3128 W.AddToWorkList(Reg);
3131 do W.RunWorkList();
while (W.UpdatePostponed());
3136 for (
const MemRegion *Base : llvm::make_first_range(B)) {
3139 if (!W.isVisited(Base))
3140 B = B.removeCluster(Base);
3143 return StoreRef(B.asStore(), *
this);
3150void RegionStoreManager::printJson(raw_ostream &Out,
Store S,
const char *NL,
3151 unsigned int Space,
bool IsDot)
const {
3152 RegionBindingsRef
Bindings = getRegionBindings(S);
3154 Indent(Out, Space, IsDot) <<
"\"store\": ";
3157 Out <<
"null," << NL;
3161 Out <<
"{ \"pointer\": \"" <<
Bindings.asStore() <<
"\", \"items\": [" << NL;
3162 Bindings.printJson(Out, NL, Space + 1, IsDot);
3163 Indent(Out, Space, IsDot) <<
"]}," << NL;
This file defines AnalysisDeclContext, a class that manages the analysis context data for context sen...
static const MemRegion * getRegion(const CallEvent &Call, const MutexDescriptor &Descriptor, bool IsLock)
static void dump(llvm::raw_ostream &OS, StringRef FunctionName, ArrayRef< CounterExpression > Expressions, ArrayRef< CounterMappingRegion > Regions)
static std::optional< SVal > convertOffsetsFromSvalToUnsigneds(const SmallVector< SVal, 2 > &SrcOffsets, const SmallVector< uint64_t, 2 > ArrayExtents, SmallVector< uint64_t, 2 > &DstOffsets)
llvm::ImmutableMap< const MemRegion *, ClusterBindings > RegionBindings
static std::optional< SVal > getDerivedSymbolForBinding(RegionBindingsConstRef B, const TypedValueRegion *BaseRegion, const TypedValueRegion *SubReg, const ASTContext &Ctx, SValBuilder &SVB)
std::pair< BindingKey, SVal > BindingPair
static bool isCompatibleWithFields(BindingKey K, const FieldVector &Fields)
SmallVector< const FieldDecl *, 8 > FieldVector
llvm::ImmutableMap< BindingKey, SVal > ClusterBindings
static bool isUnionField(const FieldRegion *FR)
const LimitedRegionBindingsRef & LimitedRegionBindingsConstRef
static void getSymbolicOffsetFields(BindingKey K, FieldVector &Fields)
static QualType getUnderlyingType(const SubRegion *R)
llvm::ImmutableMapRef< BindingKey, SVal > ClusterBindingsRef
static SmallVector< uint64_t, 2 > getConstantArrayExtents(const ConstantArrayType *CAT)
This is a helper function for getConstantValFromConstArrayInitializer.
static std::pair< SmallVector< SVal, 2 >, const MemRegion * > getElementRegionOffsetsWithBase(const ElementRegion *ER)
This is a helper function for getConstantValFromConstArrayInitializer.
const RegionBindingsRef & RegionBindingsConstRef
static std::optional< nonloc::LazyCompoundVal > getExistingLazyBinding(SValBuilder &SVB, RegionBindingsConstRef B, const SubRegion *R, bool AllowSubregionBindings)
Checks to see if store B has a lazy binding for region R.
static void collectSubRegionBindings(SmallVectorImpl< BindingPair > &Bindings, SValBuilder &SVB, const ClusterBindings &Cluster, const SubRegion *Top, BindingKey TopKey, bool IncludeAllDefaultBindings)
Collects all bindings in Cluster that may refer to bindings within Top.
llvm::SmallVector< std::pair< const MemRegion *, SVal >, 4 > Bindings
__PTRDIFF_TYPE__ ptrdiff_t
A signed integer type that is the result of subtracting two pointers.
This class represents the same as RegionBindingsRef, but with a limit on the number of bindings that ...
LimitedRegionBindingsRef removeCluster(const MemRegion *BaseRegion) const
LimitedRegionBindingsRef withValuesEscaped(nonloc::CompoundVal::iterator Begin, nonloc::CompoundVal::iterator End) const
LimitedRegionBindingsRef withValuesEscaped(SVal V) const
LimitedRegionBindingsRef(RegionBindingsRef Base, SmallVectorImpl< SVal > &EscapedValuesDuringBind, std::optional< unsigned > BindingsLeft)
bool hasExhaustedBindingLimit() const
LimitedRegionBindingsRef addBinding(BindingKey K, SVal V) const
LimitedRegionBindingsRef addBinding(const MemRegion *R, BindingKey::Kind k, SVal V) const
LimitedRegionBindingsRef addWithoutDecreasingLimit(const MemRegion *BaseRegion, data_type_ref BindingKeyAndValue) const
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
const ConstantArrayType * getAsConstantArrayType(QualType T) const
CanQualType getCanonicalType(QualType T) const
Return the canonical (structural) type corresponding to the specified potentially non-canonical type ...
const LangOptions & getLangOpts() const
bool hasSameUnqualifiedType(QualType T1, QualType T2) const
Determine whether the given types are equivalent after cvr-qualifiers have been removed.
const ArrayType * getAsArrayType(QualType T) const
Type Query functions.
uint64_t getTypeSize(QualType T) const
Return the size of the specified (complete) type T, in bits.
CharUnits getTypeSizeInChars(QualType T) const
Return the size of the specified (complete) type T, in characters.
uint64_t getConstantArrayElementCount(const ConstantArrayType *CA) const
Return number of constant array elements.
uint64_t getCharWidth() const
Return the size of the character type, in bits.
QualType getElementType() const
Represents the canonical version of C arrays with a specified constant size.
uint64_t getLimitedSize() const
Return the size zero-extended to uint64_t or UINT64_MAX if the value is larger than UINT64_MAX.
uint64_t getZExtSize() const
Return the size zero-extended as a uint64_t.
unsigned getFieldIndex() const
Returns the index of this field within its record, as appropriate for passing to ASTRecordLayout::get...
const RecordDecl * getParent() const
Returns the parent of this field declaration, which is the struct in which this field is defined.
bool isUnnamedBitField() const
Determines whether this is an unnamed bitfield.
bool isStringLiteralInit() const
Is this an initializer for an array of characters, initialized by a string literal or an @encode?
unsigned getNumInits() const
const Expr * getInit(unsigned Init) const
bool isParentOf(const LocationContext *LC) const
const Decl * getDecl() const
A (possibly-)qualified type.
bool isNull() const
Return true if this QualType doesn't point to a type yet.
bool isConstQualified() const
Determine whether this type is const-qualified.
field_iterator field_end() const
field_range fields() const
RecordDecl * getDefinition() const
Returns the RecordDecl that actually defines this struct/union/class.
specific_decl_iterator< FieldDecl > field_iterator
field_iterator field_begin() const
unsigned getLength() const
uint32_t getCodeUnit(size_t i) const
bool isCompleteDefinition() const
Return true if this decl has its body fully specified.
CXXRecordDecl * getAsCXXRecordDecl() const
Retrieves the CXXRecordDecl that this type refers to, either because the type is a RecordType or beca...
bool isConstantArrayType() const
bool isVoidPointerType() const
const T * castAs() const
Member-template castAs<specific type>.
bool isReferenceType() const
bool isScalarType() const
QualType getPointeeType() const
If this is a pointer, ObjC object pointer, or block pointer, this returns the respective pointee.
bool isIntegralOrEnumerationType() const
Determine whether this type is an integral or enumeration type.
RecordDecl * castAsRecordDecl() const
bool isAnyComplexType() const
QualType getCanonicalTypeInternal() const
bool isStructureOrClassType() const
bool isVectorType() const
const T * castAsCanonical() const
Return this type's canonical type cast to the specified type.
bool isRecordType() const
bool hasGlobalStorage() const
Returns true for all variables that do not have local storage.
bool hasLocalStorage() const
Returns true if a variable with function scope is a non-static local variable.
const Expr * getAnyInitializer() const
Get the initializer for this variable, no matter which declaration it is attached to.
unsigned getNumElements() const
QualType getElementType() const
ElementRegion is used to represent both array elements and casts.
QualType getElementType() const
RegionRawOffset getAsArrayOffset() const
Compute the offset within the array. The array might also be a subobject.
LLVM_ATTRIBUTE_RETURNS_NONNULL const FieldDecl * getDecl() const override
void dumpToStream(raw_ostream &Out) const
static bool isLocType(QualType T)
DefinedOrUnknownSVal getStaticSize(const MemRegion *MR, SValBuilder &SVB) const
MemRegion - The root abstract class for all memory regions.
virtual bool isBoundable() const
RegionOffset getAsOffset() const
Compute the offset within the top level memory object.
std::string getDescriptiveName(bool UseQuotes=true) const
Get descriptive name for memory region.
LLVM_ATTRIBUTE_RETURNS_NONNULL const MemRegion * getBaseRegion() const
LLVM_ATTRIBUTE_RETURNS_NONNULL const MemSpaceRegion * getRawMemorySpace() const
Deprecated.
@ TK_PreserveContents
Tells that a region's contents is not changed.
@ TK_DoNotInvalidateSuperRegion
@ TK_EntireMemSpace
When applied to a MemSpaceRegion, indicates the entire memory space should be invalidated.
bool hasTrait(SymbolRef Sym, InvalidationKinds IK) const
bool hasSymbolicOffset() const
const MemRegion * getRegion() const
It might return null.
int64_t getOffset() const
const MemRegion * getRegion() const
DefinedOrUnknownSVal makeZeroVal(QualType type)
Construct an SVal representing '0' for the specified type.
NonLoc makeArrayIndex(uint64_t idx)
ASTContext & getContext()
nonloc::ConcreteInt makeIntVal(const IntegerLiteral *integer)
SVal evalCast(SVal V, QualType CastTy, QualType OriginalTy)
Cast a given SVal to another SVal using given QualType's.
DefinedOrUnknownSVal getDerivedRegionValueSymbolVal(SymbolRef parentSymbol, const TypedValueRegion *region)
loc::ConcreteInt makeNullWithType(QualType type)
Create NULL pointer, with proper pointer bit-width for given address space.
std::optional< SVal > getConstantVal(const Expr *E)
Returns the value of E, if it can be determined in a non-path-sensitive manner.
DefinedOrUnknownSVal conjureSymbolVal(const void *symbolTag, ConstCFGElementRef elem, const LocationContext *LCtx, unsigned count)
Create a new symbol with a unique 'name'.
NonLoc makeZeroArrayIndex()
DefinedOrUnknownSVal getRegionValueSymbolVal(const TypedValueRegion *region)
Make a unique symbol for value of region.
NonLoc makeLazyCompoundVal(const StoreRef &store, const TypedValueRegion *region)
SVal - This represents a symbolic expression, which can be either an L-value or an R-value.
bool isZeroConstant() const
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.
bool scan(nonloc::LazyCompoundVal val)
SmallVector< const MemRegion *, 8 > InvalidatedRegions
SubRegion - A region that subsets another larger region.
LLVM_ATTRIBUTE_RETURNS_NONNULL const MemRegion * getSuperRegion() const
bool isSubRegionOf(const MemRegion *R) const override
Check if the region is a subregion of the given region.
MemRegionManager & getMemRegionManager() const override
llvm::iterator_range< symbol_iterator > symbols() const
static bool canSymbolicate(QualType T)
void markLive(SymbolRef sym)
Unconditionally marks a symbol as live.
void markElementIndicesLive(const MemRegion *region)
void markLazilyCopied(const MemRegion *region)
bool isLive(SymbolRef sym)
llvm::iterator_range< RegionSetTy::const_iterator > regions() const
SymbolicRegion - A special, "non-concrete" region.
TypedValueRegion - An abstract class representing regions having a typed value.
virtual QualType getValueType() const =0
QualType getLocationType() const override
QualType getValueType() const override
const VarDecl * getDecl() const override=0
llvm::ImmutableList< SVal >::iterator iterator
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.
Defines the clang::TargetInfo interface.
const internal::VariadicDynCastAllOfMatcher< Decl, VarDecl > varDecl
Matches variable declarations.
const internal::VariadicDynCastAllOfMatcher< Stmt, DeclRefExpr > declRefExpr
Matches expressions that refer to declarations.
const internal::ArgumentAdaptingMatcherFunc< internal::HasDescendantMatcher > hasDescendant
Matches AST nodes that have descendant AST nodes that match the provided matcher.
SmallVector< BoundNodes, 1 > match(MatcherT Matcher, const NodeT &Node, ASTContext &Context)
Returns the results of matching Matcher on Node.
internal::Matcher< Stmt > StatementMatcher
const internal::VariadicAllOfMatcher< Stmt > stmt
Matches statements.
llvm::DenseSet< SymbolRef > InvalidatedSymbols
const SymExpr * SymbolRef
@ OS
Indicates that the tracking object is a descendant of a referenced-counted OSObject,...
std::unique_ptr< StoreManager > CreateRegionStoreManager(ProgramStateManager &StMgr)
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.
@ Match
This is not an overload because the signature exactly matches an existing declaration.
bool isa(CodeGen::Address addr)
CFGBlock::ConstCFGElementRef ConstCFGElementRef
@ Bind
'bind' clause, allowed on routine constructs.
bool operator==(const CallGraphNode::CallRecord &LHS, const CallGraphNode::CallRecord &RHS)
bool operator<(DeclarationName LHS, DeclarationName RHS)
Ordering on two declaration names.
const StreamingDiagnostic & operator<<(const StreamingDiagnostic &DB, const ASTContext::SectionInfo &Section)
Insertion operator for diagnostics.
raw_ostream & Indent(raw_ostream &Out, const unsigned int Space, bool IsDot)
@ Result
The result type of a method or function.
const FunctionProtoType * T
U cast(CodeGen::Address addr)
@ Class
The "class" keyword introduces the elaborated-type-specifier.
Diagnostic wrappers for TextAPI types for error reporting.
__UINTPTR_TYPE__ uintptr_t
An unsigned integer type with the property that any valid pointer to void can be converted to this ty...