30 #include "llvm/ADT/ImmutableMap.h"
31 #include "llvm/ADT/Optional.h"
32 #include "llvm/Support/raw_ostream.h"
35 using namespace clang;
47 enum { Symbolic = 0x2 };
49 llvm::PointerIntPair<const MemRegion *, 2>
P;
54 explicit BindingKey(
const SubRegion *r,
const SubRegion *
Base,
Kind k)
56 assert(r &&
Base &&
"Must have known regions.");
57 assert(getConcreteOffsetRegion() ==
Base &&
"Failed to store base region");
61 explicit BindingKey(
const MemRegion *r, uint64_t offset,
Kind k)
62 :
P(r, k), Data(offset) {
63 assert(r &&
"Must have known regions.");
64 assert(getOffset() == offset &&
"Failed to store offset");
65 assert((r == r->getBaseRegion() ||
66 isa<ObjCIvarRegion, CXXDerivedObjectRegion>(r)) &&
71 bool isDirect()
const {
return P.getInt() & Direct; }
72 bool hasSymbolicOffset()
const {
return P.getInt() & Symbolic; }
74 const MemRegion *getRegion()
const {
return P.getPointer(); }
75 uint64_t getOffset()
const {
76 assert(!hasSymbolicOffset());
80 const SubRegion *getConcreteOffsetRegion()
const {
81 assert(hasSymbolicOffset());
82 return reinterpret_cast<const SubRegion *
>(
static_cast<uintptr_t>(Data));
85 const MemRegion *getBaseRegion()
const {
86 if (hasSymbolicOffset())
87 return getConcreteOffsetRegion()->getBaseRegion();
88 return getRegion()->getBaseRegion();
91 void Profile(llvm::FoldingSetNodeID&
ID)
const {
92 ID.AddPointer(
P.getOpaqueValue());
96 static BindingKey
Make(
const MemRegion *R,
Kind k);
99 if (
P.getOpaqueValue() <
X.P.getOpaqueValue())
101 if (
P.getOpaqueValue() >
X.P.getOpaqueValue())
103 return Data <
X.Data;
107 return P.getOpaqueValue() ==
X.P.getOpaqueValue() &&
111 LLVM_DUMP_METHOD
void dump()
const;
115 BindingKey BindingKey::Make(
const MemRegion *R,
Kind k) {
116 const RegionOffset &RO = R->getAsOffset();
117 if (RO.hasSymbolicOffset())
118 return BindingKey(cast<SubRegion>(R), cast<SubRegion>(RO.getRegion()), k);
120 return BindingKey(RO.getRegion(), RO.getOffset(), k);
124 static inline raw_ostream &
operator<<(raw_ostream &Out, BindingKey K) {
125 Out <<
"\"kind\": \"" << (K.isDirect() ?
"Direct" :
"Default")
126 <<
"\", \"offset\": ";
128 if (!K.hasSymbolicOffset())
129 Out << K.getOffset();
138 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
150 typedef llvm::ImmutableMap<const MemRegion *, ClusterBindings>
154 class RegionBindingsRef :
public llvm::ImmutableMapRef<const MemRegion *,
156 ClusterBindings::Factory *CBFactory;
170 typedef llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>
173 RegionBindingsRef(ClusterBindings::Factory &CBFactory,
174 const RegionBindings::TreeTy *T,
175 RegionBindings::TreeTy::Factory *F,
177 : llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>(T, F),
178 CBFactory(&CBFactory), IsMainAnalysis(IsMainAnalysis) {}
180 RegionBindingsRef(
const ParentTy &
P,
181 ClusterBindings::Factory &CBFactory,
183 : llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>(
P),
184 CBFactory(&CBFactory), IsMainAnalysis(IsMainAnalysis) {}
186 RegionBindingsRef add(key_type_ref K, data_type_ref D)
const {
187 return RegionBindingsRef(
static_cast<const ParentTy *
>(
this)->add(K, D),
188 *CBFactory, IsMainAnalysis);
191 RegionBindingsRef
remove(key_type_ref K)
const {
192 return RegionBindingsRef(
static_cast<const ParentTy *
>(
this)->
remove(K),
193 *CBFactory, IsMainAnalysis);
196 RegionBindingsRef addBinding(BindingKey K, SVal
V)
const;
198 RegionBindingsRef addBinding(
const MemRegion *R,
199 BindingKey::Kind k, SVal
V)
const;
201 const SVal *lookup(BindingKey K)
const;
202 const SVal *lookup(
const MemRegion *R, BindingKey::Kind k)
const;
203 using llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>::lookup;
205 RegionBindingsRef removeBinding(BindingKey K);
207 RegionBindingsRef removeBinding(
const MemRegion *R,
210 RegionBindingsRef removeBinding(
const MemRegion *R) {
211 return removeBinding(R, BindingKey::Direct).
212 removeBinding(R, BindingKey::Default);
222 Store asStore()
const {
223 llvm::PointerIntPair<Store, 1, bool> Ptr = {
224 asImmutableMap().getRootWithoutRetain(), IsMainAnalysis};
225 return reinterpret_cast<Store>(Ptr.getOpaqueValue());
228 bool isMainAnalysis()
const {
229 return IsMainAnalysis;
232 void printJson(raw_ostream &Out,
const char *NL =
"\n",
233 unsigned int Space = 0,
bool IsDot =
false)
const {
234 for (iterator I = begin(); I != end(); ++I) {
237 <<
"{ \"cluster\": \"" << I.getKey() <<
"\", \"pointer\": \""
238 << (
const void *)I.getKey() <<
"\", \"items\": [" << NL;
242 for (ClusterBindings::iterator CI = CB.begin(); CI != CB.end(); ++CI) {
243 Indent(Out, Space, IsDot) <<
"{ " << CI.getKey() <<
", \"value\": ";
244 CI.getData().printJson(Out,
true);
246 if (std::next(CI) != CB.end())
252 Indent(Out, Space, IsDot) <<
"]}";
253 if (std::next(I) != end())
259 LLVM_DUMP_METHOD
void dump()
const { printJson(llvm::errs()); }
265 Optional<SVal> RegionBindingsRef::getDirectBinding(
const MemRegion *R)
const {
269 Optional<SVal> RegionBindingsRef::getDefaultBinding(
const MemRegion *R)
const {
273 RegionBindingsRef RegionBindingsRef::addBinding(BindingKey K, SVal
V)
const {
274 const MemRegion *
Base = K.getBaseRegion();
278 (ExistingCluster ? *ExistingCluster : CBFactory->getEmptyMap());
281 return add(
Base, NewCluster);
285 RegionBindingsRef RegionBindingsRef::addBinding(
const MemRegion *R,
288 return addBinding(BindingKey::Make(R, k),
V);
291 const SVal *RegionBindingsRef::lookup(BindingKey K)
const {
295 return Cluster->lookup(K);
298 const SVal *RegionBindingsRef::lookup(
const MemRegion *R,
299 BindingKey::Kind k)
const {
300 return lookup(BindingKey::Make(R, k));
303 RegionBindingsRef RegionBindingsRef::removeBinding(BindingKey K) {
304 const MemRegion *
Base = K.getBaseRegion();
310 if (NewCluster.isEmpty())
312 return add(
Base, NewCluster);
315 RegionBindingsRef RegionBindingsRef::removeBinding(
const MemRegion *R,
317 return removeBinding(BindingKey::Make(R, k));
325 struct minimal_features_tag {};
326 struct maximal_features_tag {};
328 class RegionStoreFeatures {
331 RegionStoreFeatures(minimal_features_tag) :
332 SupportsFields(
false) {}
334 RegionStoreFeatures(maximal_features_tag) :
335 SupportsFields(
true) {}
337 void enableFields(
bool t) { SupportsFields = t; }
339 bool supportsFields()
const {
return SupportsFields; }
348 class InvalidateRegionsWorker;
350 class RegionStoreManager :
public StoreManager {
352 const RegionStoreFeatures Features;
354 RegionBindings::Factory RBFactory;
355 mutable ClusterBindings::Factory CBFactory;
357 typedef std::vector<SVal> SValListTy;
359 typedef llvm::DenseMap<
const LazyCompoundValData *,
360 SValListTy> LazyBindingsMapTy;
361 LazyBindingsMapTy LazyBindingsMap;
371 unsigned SmallStructLimit;
375 void populateWorkList(InvalidateRegionsWorker &W,
376 ArrayRef<SVal> Values,
377 InvalidatedRegions *TopLevelRegions);
380 RegionStoreManager(ProgramStateManager& mgr,
const RegionStoreFeatures &f)
381 : StoreManager(mgr), Features(f),
382 RBFactory(mgr.getAllocator()), CBFactory(mgr.getAllocator()),
383 SmallStructLimit(0) {
384 ExprEngine &Eng = StateMgr.getOwningEngine();
386 SmallStructLimit = Options.RegionStoreSmallStructLimit;
402 SVal ArrayToPointer(Loc Array,
QualType ElementTy)
override;
407 bool IsMainAnalysis =
false;
408 if (
const auto *FD = dyn_cast<FunctionDecl>(InitLoc->
getDecl()))
409 IsMainAnalysis = FD->isMain() && !Ctx.getLangOpts().CPlusPlus;
410 return StoreRef(RegionBindingsRef(
411 RegionBindingsRef::ParentTy(RBFactory.getEmptyMap(), RBFactory),
412 CBFactory, IsMainAnalysis).asStore(), *
this);
423 InvalidatedRegions *Invalidated);
425 StoreRef invalidateRegions(
Store store,
426 ArrayRef<SVal> Values,
427 const Expr *E,
unsigned Count,
429 const CallEvent *Call,
431 RegionAndSymbolInvalidationTraits &ITraits,
432 InvalidatedRegions *Invalidated,
433 InvalidatedRegions *InvalidatedTopLevel)
override;
435 bool scanReachableSymbols(
Store S,
const MemRegion *R,
436 ScanReachableSymbols &Callbacks)
override;
442 const ElementRegion *R);
445 const SmallVector<uint64_t, 2> &ConcreteOffsets,
452 StoreRef Bind(
Store store, Loc LV, SVal
V)
override {
453 return StoreRef(bind(getRegionBindings(store), LV,
V).asStore(), *
this);
460 StoreRef BindDefaultInitial(
Store store,
const MemRegion *R,
462 RegionBindingsRef B = getRegionBindings(store);
465 assert(!(B.getDefaultBinding(R) || B.getDirectBinding(R)) &&
466 "Double initialization!");
467 B = B.addBinding(BindingKey::Make(R, BindingKey::Default),
V);
468 return StoreRef(B.asImmutableMap().getRootWithoutRetain(), *
this);
473 StoreRef BindDefaultZero(
Store store,
const MemRegion *R)
override {
483 if (
const auto *BR = dyn_cast<CXXBaseObjectRegion>(R))
484 if (BR->getDecl()->isEmpty())
485 return StoreRef(store, *
this);
487 RegionBindingsRef B = getRegionBindings(store);
488 SVal
V = svalBuilder.makeZeroVal(Ctx.CharTy);
489 B = removeSubRegionBindings(B, cast<SubRegion>(R));
490 B = B.addBinding(BindingKey::Make(R, BindingKey::Default),
V);
491 return StoreRef(B.asImmutableMap().getRootWithoutRetain(), *
this);
505 const TypedValueRegion *R,
507 nonloc::LazyCompoundVal LCV);
511 const TypedValueRegion* R, SVal
V);
515 const TypedValueRegion* R, SVal
V);
518 const TypedValueRegion* R,
524 const TypedRegion *R,
530 StoreRef killBinding(
Store ST, Loc L)
override;
532 void incrementReferenceCount(
Store store)
override {
533 getRegionBindings(store).manualRetain();
539 void decrementReferenceCount(
Store store)
override {
540 getRegionBindings(store).manualRelease();
543 bool includedInBindings(
Store store,
const MemRegion *region)
const override;
559 return getBinding(getRegionBindings(S), L, T);
563 RegionBindingsRef B = getRegionBindings(S);
567 return B.getDefaultBinding(R->getBaseRegion());
580 SVal getBindingForLazySymbol(
const TypedValueRegion *R);
583 const TypedValueRegion *R,
586 SVal getLazyBinding(
const SubRegion *LazyBindingRegion,
587 RegionBindingsRef LazyBinding);
604 const MemRegion *superR,
605 const TypedValueRegion *R,
612 std::pair<Store, const SubRegion *>
614 const SubRegion *originalRegion);
622 const SValListTy &getInterestingValues(nonloc::LazyCompoundVal LCV);
631 SymbolReaper& SymReaper)
override;
637 RegionBindingsRef getRegionBindings(
Store store)
const {
638 llvm::PointerIntPair<Store, 1, bool> Ptr;
639 Ptr.setFromOpaqueValue(
const_cast<void *
>(store));
640 return RegionBindingsRef(
642 static_cast<const RegionBindings::TreeTy *
>(Ptr.getPointer()),
643 RBFactory.getTreeFactory(),
647 void printJson(raw_ostream &Out,
Store S,
const char *NL =
"\n",
648 unsigned int Space = 0,
bool IsDot =
false)
const override;
650 void iterBindings(
Store store, BindingsHandler& f)
override {
651 RegionBindingsRef B = getRegionBindings(store);
652 for (RegionBindingsRef::iterator I = B.begin(), E = B.end(); I != E; ++I) {
654 for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end();
656 const BindingKey &K = CI.getKey();
659 if (
const SubRegion *R = dyn_cast<SubRegion>(K.getRegion())) {
661 if (!f.HandleBinding(*
this, store, R, CI.getData()))
675 std::unique_ptr<StoreManager>
677 RegionStoreFeatures F = maximal_features_tag();
678 return std::make_unique<RegionStoreManager>(StMgr, F);
681 std::unique_ptr<StoreManager>
683 RegionStoreFeatures F = minimal_features_tag();
684 F.enableFields(
true);
685 return std::make_unique<RegionStoreManager>(StMgr, F);
696 enum GlobalsFilterKind {
705 template <
typename DERIVED>
706 class ClusterAnalysis {
708 typedef llvm::DenseMap<const MemRegion *, const ClusterBindings *> ClusterMap;
709 typedef const MemRegion * WorkListElement;
710 typedef SmallVector<WorkListElement, 10> WorkList;
716 RegionStoreManager &RM;
718 SValBuilder &svalBuilder;
731 bool includeEntireMemorySpace(
const MemRegion *
Base) {
736 ClusterAnalysis(RegionStoreManager &rm, ProgramStateManager &StateMgr,
738 : RM(rm), Ctx(StateMgr.getContext()),
739 svalBuilder(StateMgr.getSValBuilder()), B(
std::move(
b)) {}
741 RegionBindingsRef getRegionBindings()
const {
return B; }
743 bool isVisited(
const MemRegion *R) {
744 return Visited.count(getCluster(R));
747 void GenerateClusters() {
749 for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end();
751 const MemRegion *
Base = RI.getKey();
754 assert(!Cluster.isEmpty() &&
"Empty clusters should be removed");
755 static_cast<DERIVED*
>(
this)->VisitAddedToCluster(
Base, Cluster);
759 if (
static_cast<DERIVED*
>(
this)->includeEntireMemorySpace(
Base))
760 AddToWorkList(WorkListElement(
Base), &Cluster);
765 if (C && !Visited.insert(C).second)
771 bool AddToWorkList(
const MemRegion *R) {
772 return static_cast<DERIVED*
>(
this)->AddToWorkList(R);
776 while (!WL.empty()) {
777 WorkListElement E = WL.pop_back_val();
778 const MemRegion *BaseR = E;
780 static_cast<DERIVED*
>(
this)->VisitCluster(BaseR, getCluster(BaseR));
784 void VisitAddedToCluster(
const MemRegion *baseR,
const ClusterBindings &C) {}
789 static_cast<DERIVED*
>(
this)->VisitCluster(BaseR, C);
798 bool RegionStoreManager::scanReachableSymbols(
Store S,
const MemRegion *R,
799 ScanReachableSymbols &Callbacks) {
800 assert(R == R->getBaseRegion() &&
"Should only be called for base regions");
801 RegionBindingsRef B = getRegionBindings(S);
807 for (ClusterBindings::iterator RI = Cluster->begin(), RE = Cluster->end();
809 if (!Callbacks.scan(RI.getData()))
817 return FR->getDecl()->getParent()->isUnion();
823 assert(K.hasSymbolicOffset() &&
"Not implemented for concrete offset keys");
825 const MemRegion *
Base = K.getConcreteOffsetRegion();
826 const MemRegion *R = K.getRegion();
829 if (
const FieldRegion *FR = dyn_cast<FieldRegion>(R))
831 Fields.push_back(FR->getDecl());
833 R = cast<SubRegion>(R)->getSuperRegion();
838 assert(K.hasSymbolicOffset() &&
"Not implemented for concrete offset keys");
846 ptrdiff_t Delta = FieldsInBindingKey.size() - Fields.size();
848 return std::equal(FieldsInBindingKey.begin() + Delta,
849 FieldsInBindingKey.end(),
852 return std::equal(FieldsInBindingKey.begin(), FieldsInBindingKey.end(),
853 Fields.begin() - Delta);
868 const SubRegion *Top, BindingKey TopKey,
869 bool IncludeAllDefaultBindings) {
871 if (TopKey.hasSymbolicOffset()) {
873 Top = TopKey.getConcreteOffsetRegion();
874 TopKey = BindingKey::Make(Top, BindingKey::Default);
878 uint64_t Length = UINT64_MAX;
879 SVal Extent = Top->getMemRegionManager().getStaticSize(Top, SVB);
881 Extent.getAs<nonloc::ConcreteInt>()) {
883 assert(ExtentInt.isNonNegative() || ExtentInt.isUnsigned());
885 Length = ExtentInt.getLimitedValue() * SVB.getContext().getCharWidth();
886 }
else if (
const FieldRegion *FR = dyn_cast<FieldRegion>(Top)) {
887 if (FR->getDecl()->isBitField())
888 Length = FR->getDecl()->getBitWidthValue(SVB.getContext());
891 for (ClusterBindings::iterator I = Cluster.begin(), E = Cluster.end();
893 BindingKey NextKey = I.getKey();
894 if (NextKey.getRegion() == TopKey.getRegion()) {
900 if (NextKey.getOffset() > TopKey.getOffset() &&
901 NextKey.getOffset() - TopKey.getOffset() < Length) {
906 }
else if (NextKey.getOffset() == TopKey.getOffset()) {
913 if (IncludeAllDefaultBindings || NextKey.isDirect())
917 }
else if (NextKey.hasSymbolicOffset()) {
918 const MemRegion *
Base = NextKey.getConcreteOffsetRegion();
919 if (Top->isSubRegionOf(
Base) && Top !=
Base) {
923 if (IncludeAllDefaultBindings || NextKey.isDirect())
926 }
else if (
const SubRegion *BaseSR = dyn_cast<SubRegion>(
Base)) {
929 if (BaseSR->isSubRegionOf(Top))
940 const SubRegion *Top,
bool IncludeAllDefaultBindings) {
942 BindingKey::Make(Top, BindingKey::Default),
943 IncludeAllDefaultBindings);
948 const SubRegion *Top) {
949 BindingKey TopKey = BindingKey::Make(Top, BindingKey::Default);
950 const MemRegion *ClusterHead = TopKey.getBaseRegion();
952 if (Top == ClusterHead) {
954 return B.remove(Top);
961 if (TopKey.hasSymbolicOffset()) {
962 const SubRegion *Concrete = TopKey.getConcreteOffsetRegion();
963 return B.addBinding(Concrete, BindingKey::Default, UnknownVal());
968 SmallVector<BindingPair, 32>
Bindings;
973 for (SmallVectorImpl<BindingPair>::const_iterator I =
Bindings.begin(),
976 Result = Result.remove(I->first);
982 if (TopKey.hasSymbolicOffset()) {
983 const SubRegion *Concrete = TopKey.getConcreteOffsetRegion();
984 Result = Result.
add(BindingKey::Make(Concrete, BindingKey::Default),
988 if (Result.isEmpty())
989 return B.remove(ClusterHead);
990 return B.add(ClusterHead, Result.asImmutableMap());
994 class InvalidateRegionsWorker :
public ClusterAnalysis<InvalidateRegionsWorker>
1000 RegionAndSymbolInvalidationTraits &ITraits;
1002 GlobalsFilterKind GlobalsFilter;
1004 InvalidateRegionsWorker(RegionStoreManager &rm,
1005 ProgramStateManager &stateMgr,
1006 RegionBindingsRef
b,
1007 const Expr *ex,
unsigned count,
1010 RegionAndSymbolInvalidationTraits &ITraitsIn,
1012 GlobalsFilterKind GFK)
1013 : ClusterAnalysis<InvalidateRegionsWorker>(rm, stateMgr,
b),
1014 Ex(ex), Count(count), LCtx(lctx), IS(is), ITraits(ITraitsIn), Regions(r),
1015 GlobalsFilter(GFK) {}
1018 void VisitBinding(SVal
V);
1020 using ClusterAnalysis::AddToWorkList;
1022 bool AddToWorkList(
const MemRegion *R);
1026 bool includeEntireMemorySpace(
const MemRegion *
Base);
1030 bool isInitiallyIncludedGlobalRegion(
const MemRegion *R);
1034 bool InvalidateRegionsWorker::AddToWorkList(
const MemRegion *R) {
1035 bool doNotInvalidateSuperRegion = ITraits.hasTrait(
1037 const MemRegion *BaseR = doNotInvalidateSuperRegion ? R : R->getBaseRegion();
1038 return AddToWorkList(WorkListElement(BaseR), getCluster(BaseR));
1041 void InvalidateRegionsWorker::VisitBinding(SVal
V) {
1046 if (
const MemRegion *R =
V.getAsRegion()) {
1053 V.getAs<nonloc::LazyCompoundVal>()) {
1055 const RegionStoreManager::SValListTy &Vals = RM.getInterestingValues(*LCS);
1057 for (RegionStoreManager::SValListTy::const_iterator I = Vals.begin(),
1066 void InvalidateRegionsWorker::VisitCluster(
const MemRegion *baseR,
1069 bool PreserveRegionsContents =
1070 ITraits.hasTrait(baseR,
1074 for (ClusterBindings::iterator I =
C->begin(), E =
C->end(); I != E; ++I)
1075 VisitBinding(I.getData());
1078 if (!PreserveRegionsContents)
1079 B = B.remove(baseR);
1082 if (
const auto *TO = dyn_cast<TypedValueRegion>(baseR)) {
1083 if (
const auto *RD = TO->getValueType()->getAsCXXRecordDecl()) {
1088 if (RD->isLambda() && RD->getLambdaCallOperator()->getBody()) {
1089 using namespace ast_matchers;
1091 const char *DeclBind =
"DeclBind";
1093 to(
varDecl(hasStaticStorageDuration()).bind(DeclBind)))));
1095 match(RefToStatic, *RD->getLambdaCallOperator()->getBody(),
1096 RD->getASTContext());
1099 auto *VD = Match.getNodeAs<
VarDecl>(DeclBind);
1100 const VarRegion *ToInvalidate =
1101 RM.getRegionManager().getVarRegion(VD, LCtx);
1102 AddToWorkList(ToInvalidate);
1110 if (
const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(baseR)) {
1111 for (BlockDataRegion::referenced_vars_iterator
1112 BI = BR->referenced_vars_begin(), BE = BR->referenced_vars_end() ;
1114 const VarRegion *VR = BI.getCapturedRegion();
1115 const VarDecl *VD = VR->getDecl();
1125 SVal
V = RM.getBinding(B, loc::MemRegionVal(VR));
1127 if (
const MemRegion *LR = L->getAsRegion())
1136 if (
const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR))
1137 IS.insert(SR->getSymbol());
1140 if (PreserveRegionsContents)
1145 Regions->push_back(baseR);
1147 if (isa<AllocaRegion, SymbolicRegion>(baseR)) {
1150 DefinedOrUnknownSVal
V =
1151 svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, Ctx.
IntTy, Count);
1152 B = B.addBinding(baseR, BindingKey::Default,
V);
1156 if (!baseR->isBoundable())
1159 const TypedValueRegion *TR = cast<TypedValueRegion>(baseR);
1162 if (isInitiallyIncludedGlobalRegion(baseR)) {
1172 DefinedOrUnknownSVal
V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx,
1174 B = B.addBinding(baseR, BindingKey::Default,
V);
1179 bool doNotInvalidateSuperRegion = ITraits.hasTrait(
1183 if (doNotInvalidateSuperRegion) {
1190 NumElements = CAT->getSize().getZExtValue();
1192 goto conjure_default;
1193 QualType ElementTy = AT->getElementType();
1195 const RegionOffset &RO = baseR->getAsOffset();
1196 const MemRegion *SuperR = baseR->getBaseRegion();
1197 if (RO.hasSymbolicOffset()) {
1201 AddToWorkList(SuperR);
1202 goto conjure_default;
1205 uint64_t LowerOffset = RO.getOffset();
1206 uint64_t UpperOffset = LowerOffset + *NumElements * ElemSize;
1207 bool UpperOverflow = UpperOffset < LowerOffset;
1212 goto conjure_default;
1216 goto conjure_default;
1218 for (ClusterBindings::iterator I =
C->begin(), E =
C->end(); I != E;
1220 const BindingKey &BK = I.getKey();
1227 ((*ROffset >= LowerOffset && *ROffset < UpperOffset) ||
1229 (*ROffset >= LowerOffset || *ROffset < UpperOffset)) ||
1230 (LowerOffset == UpperOffset && *ROffset == LowerOffset))) {
1231 B = B.removeBinding(I.getKey());
1234 SVal
V = I.getData();
1235 const MemRegion *R =
V.getAsRegion();
1236 if (isa_and_nonnull<SymbolicRegion>(R))
1243 DefinedOrUnknownSVal
V =
1244 svalBuilder.conjureSymbolVal(baseR, Ex, LCtx,
1245 AT->getElementType(), Count);
1246 B = B.addBinding(baseR, BindingKey::Default,
V);
1250 DefinedOrUnknownSVal
V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx,
1253 B = B.addBinding(baseR, BindingKey::Direct,
V);
1256 bool InvalidateRegionsWorker::isInitiallyIncludedGlobalRegion(
1257 const MemRegion *R) {
1258 switch (GlobalsFilter) {
1261 case GFK_SystemOnly:
1262 return isa<GlobalSystemSpaceRegion>(R->getMemorySpace());
1264 return isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace());
1267 llvm_unreachable(
"unknown globals filter");
1270 bool InvalidateRegionsWorker::includeEntireMemorySpace(
const MemRegion *
Base) {
1271 if (isInitiallyIncludedGlobalRegion(
Base))
1274 const MemSpaceRegion *MemSpace =
Base->getMemorySpace();
1275 return ITraits.hasTrait(MemSpace,
1284 RegionBindingsRef B,
1285 InvalidatedRegions *Invalidated) {
1288 const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion(K);
1289 SVal
V = svalBuilder.conjureSymbolVal( (
const void*) GS, Ex, LCtx,
1293 B = B.removeBinding(GS)
1294 .addBinding(BindingKey::Make(GS, BindingKey::Default),
V);
1299 Invalidated->push_back(GS);
1304 void RegionStoreManager::populateWorkList(InvalidateRegionsWorker &W,
1305 ArrayRef<SVal> Values,
1306 InvalidatedRegions *TopLevelRegions) {
1307 for (ArrayRef<SVal>::iterator I = Values.begin(),
1308 E = Values.end(); I != E; ++I) {
1311 V.getAs<nonloc::LazyCompoundVal>()) {
1313 const SValListTy &Vals = getInterestingValues(*LCS);
1315 for (SValListTy::const_iterator I = Vals.begin(),
1316 E = Vals.end(); I != E; ++I) {
1319 if (
const MemRegion *R = (*I).getAsRegion())
1325 if (
const MemRegion *R =
V.getAsRegion()) {
1326 if (TopLevelRegions)
1327 TopLevelRegions->push_back(R);
1335 RegionStoreManager::invalidateRegions(
Store store,
1336 ArrayRef<SVal> Values,
1337 const Expr *Ex,
unsigned Count,
1339 const CallEvent *Call,
1341 RegionAndSymbolInvalidationTraits &ITraits,
1342 InvalidatedRegions *TopLevelRegions,
1343 InvalidatedRegions *Invalidated) {
1344 GlobalsFilterKind GlobalsFilter;
1346 if (
Call->isInSystemHeader())
1347 GlobalsFilter = GFK_SystemOnly;
1349 GlobalsFilter = GFK_All;
1351 GlobalsFilter = GFK_None;
1354 RegionBindingsRef B = getRegionBindings(store);
1355 InvalidateRegionsWorker W(*
this, StateMgr, B, Ex, Count, LCtx, IS, ITraits,
1356 Invalidated, GlobalsFilter);
1359 W.GenerateClusters();
1362 populateWorkList(W, Values, TopLevelRegions);
1367 B = W.getRegionBindings();
1373 switch (GlobalsFilter) {
1375 B = invalidateGlobalRegion(MemRegion::GlobalInternalSpaceRegionKind,
1376 Ex, Count, LCtx, B, Invalidated);
1378 case GFK_SystemOnly:
1379 B = invalidateGlobalRegion(MemRegion::GlobalSystemSpaceRegionKind,
1380 Ex, Count, LCtx, B, Invalidated);
1386 return StoreRef(B.asStore(), *
this);
1399 SVal RegionStoreManager::ArrayToPointer(Loc Array,
QualType T) {
1400 if (Array.getAs<loc::ConcreteInt>())
1403 if (!Array.getAs<loc::MemRegionVal>())
1404 return UnknownVal();
1406 const SubRegion *R =
1407 cast<SubRegion>(Array.castAs<loc::MemRegionVal>().getRegion());
1408 NonLoc ZeroIdx = svalBuilder.makeZeroArrayIndex();
1409 return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, R, Ctx));
1417 assert(!L.getAs<UnknownVal>() &&
"location unknown");
1418 assert(!L.getAs<UndefinedVal>() &&
"location undefined");
1426 if (L.getAs<loc::ConcreteInt>()) {
1427 return UnknownVal();
1429 if (!L.getAs<loc::MemRegionVal>()) {
1430 return UnknownVal();
1433 const MemRegion *MR = L.castAs<loc::MemRegionVal>().getRegion();
1435 if (isa<BlockDataRegion>(MR)) {
1436 return UnknownVal();
1439 if (!isa<TypedValueRegion>(MR)) {
1441 if (
const TypedRegion *TR = dyn_cast<TypedRegion>(MR))
1443 else if (
const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR))
1446 assert(!T.
isNull() &&
"Unable to auto-detect binding type!");
1447 assert(!T->
isVoidType() &&
"Attempting to dereference a void pointer!");
1448 MR = GetElementZeroRegion(cast<SubRegion>(MR), T);
1450 T = cast<TypedValueRegion>(MR)->getValueType();
1455 const TypedValueRegion *R = cast<TypedValueRegion>(MR);
1461 return UnknownVal();
1472 return getBindingForStruct(B, R);
1476 return createLazyBinding(B, R);
1480 return getBindingForArray(B, R);
1482 return UnknownVal();
1487 return UnknownVal();
1489 if (
const FieldRegion* FR = dyn_cast<FieldRegion>(R))
1490 return svalBuilder.evalCast(getBindingForField(B, FR), T,
QualType{});
1492 if (
const ElementRegion* ER = dyn_cast<ElementRegion>(R)) {
1498 return svalBuilder.evalCast(getBindingForElement(B, ER), T,
QualType{});
1501 if (
const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) {
1508 return svalBuilder.evalCast(getBindingForObjCIvar(B, IVR), T,
QualType{});
1511 if (
const VarRegion *VR = dyn_cast<VarRegion>(R)) {
1518 return svalBuilder.evalCast(getBindingForVar(B, VR), T,
QualType{});
1521 const SVal *
V = B.lookup(R, BindingKey::Direct);
1530 if (R->hasStackNonParametersStorage()) {
1535 return UndefinedVal();
1539 return svalBuilder.getRegionValueSymbolVal(R);
1544 if (
const TypedValueRegion *TVR = dyn_cast<TypedValueRegion>(R))
1545 RegionTy = TVR->getValueType();
1547 if (
const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
1548 RegionTy = SR->getSymbol()->getType();
1562 const SubRegion *R,
bool AllowSubregionBindings) {
1574 if (!RegionTy.
isNull() &&
1576 QualType SourceRegionTy = LCV->getRegion()->getValueType();
1577 if (!SVB.getContext().hasSameUnqualifiedType(RegionTy, SourceRegionTy))
1581 if (!AllowSubregionBindings) {
1584 SmallVector<BindingPair, 16>
Bindings;
1595 std::pair<Store, const SubRegion *>
1598 const SubRegion *originalRegion) {
1599 if (originalRegion != R) {
1602 return std::make_pair(
V->getStore(),
V->getRegion());
1605 typedef std::pair<Store, const SubRegion *> StoreRegionPair;
1606 StoreRegionPair Result = StoreRegionPair();
1608 if (
const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
1609 Result = findLazyBinding(B, cast<SubRegion>(ER->getSuperRegion()),
1613 Result.second = MRMgr.getElementRegionWithSuper(ER, Result.second);
1615 }
else if (
const FieldRegion *FR = dyn_cast<FieldRegion>(R)) {
1616 Result = findLazyBinding(B, cast<SubRegion>(FR->getSuperRegion()),
1620 Result.second = MRMgr.getFieldRegionWithSuper(FR, Result.second);
1622 }
else if (
const CXXBaseObjectRegion *BaseReg =
1623 dyn_cast<CXXBaseObjectRegion>(R)) {
1626 Result = findLazyBinding(B, cast<SubRegion>(BaseReg->getSuperRegion()),
1630 Result.second = MRMgr.getCXXBaseObjectRegionWithSuper(BaseReg,
1642 static SmallVector<uint64_t, 2>
1644 assert(CAT &&
"ConstantArrayType should not be null");
1646 SmallVector<uint64_t, 2> Extents;
1648 Extents.push_back(CAT->
getSize().getZExtValue());
1649 }
while ((CAT = dyn_cast<ConstantArrayType>(CAT->
getElementType())));
1667 static std::pair<SmallVector<SVal, 2>,
const MemRegion *>
1669 assert(ER &&
"ConstantArrayType should not be null");
1670 const MemRegion *
Base;
1671 SmallVector<SVal, 2> SValOffsets;
1673 SValOffsets.push_back(ER->getIndex());
1674 Base = ER->getSuperRegion();
1675 ER = dyn_cast<ElementRegion>(
Base);
1677 return {SValOffsets,
Base};
1703 const SmallVector<uint64_t, 2> ArrayExtents,
1704 SmallVector<uint64_t, 2> &DstOffsets) {
1722 DstOffsets.resize(SrcOffsets.size());
1723 auto ExtentIt = ArrayExtents.begin();
1724 auto OffsetIt = DstOffsets.begin();
1726 for (SVal
V : llvm::reverse(SrcOffsets)) {
1727 if (
auto CI =
V.getAs<nonloc::ConcreteInt>()) {
1731 return UndefinedVal();
1733 *(OffsetIt++) =
Offset.getZExtValue();
1739 return UnknownVal();
1744 Optional<SVal> RegionStoreManager::getConstantValFromConstArrayInitializer(
1746 assert(R &&
"ElementRegion should not be null");
1749 SmallVector<SVal, 2> SValOffsets;
1750 const MemRegion *
Base;
1752 const VarRegion *VR = dyn_cast<VarRegion>(
Base);
1756 assert(!SValOffsets.empty() &&
"getElementRegionOffsets guarantees the "
1757 "offsets vector is not empty.");
1761 const VarDecl *VD = VR->getDecl();
1763 !R->getElementType().isConstQualified() &&
1797 if (SValOffsets.size() != Extents.size())
1800 SmallVector<uint64_t, 2> ConcreteOffsets;
1808 if (
const auto *ILE = dyn_cast<InitListExpr>(Init))
1809 return getSValFromInitListExpr(ILE, ConcreteOffsets, R->getElementType());
1814 if (
const auto *SL = dyn_cast<StringLiteral>(Init))
1815 return getSValFromStringLiteral(SL, ConcreteOffsets.front(),
1816 R->getElementType());
1841 const InitListExpr *ILE,
const SmallVector<uint64_t, 2> &Offsets,
1843 assert(ILE &&
"InitListExpr should not be null");
1845 for (uint64_t
Offset : Offsets) {
1852 if (
const auto *SL = dyn_cast<StringLiteral>(ILE->
getInit(0)))
1853 return getSValFromStringLiteral(SL,
Offset, ElemT);
1859 return svalBuilder.makeZeroVal(ElemT);
1862 const auto *IL = dyn_cast<InitListExpr>(E);
1866 return svalBuilder.getConstantVal(E);
1872 "Unhandled InitListExpr sub-expressions or invalid offsets.");
1900 SVal RegionStoreManager::getSValFromStringLiteral(
const StringLiteral *SL,
1903 assert(SL &&
"StringLiteral should not be null");
1908 return svalBuilder.makeIntVal(Code, ElemT);
1912 const ElementRegion* R) {
1917 const MemRegion* superR = R->getSuperRegion();
1920 if (
const StringRegion *StrR = dyn_cast<StringRegion>(superR)) {
1926 return UnknownVal();
1927 if (
const auto CI = R->getIndex().getAs<nonloc::ConcreteInt>()) {
1930 return UndefinedVal();
1932 return getSValFromStringLiteral(SL, Idx.getZExtValue(), T);
1934 }
else if (isa<ElementRegion, VarRegion>(superR)) {
1940 if (isa<CodeTextRegion>(superR))
1941 return UnknownVal();
1949 const RegionRawOffset &O = R->getAsArrayOffset();
1953 return UnknownVal();
1955 if (
const TypedValueRegion *baseR =
1956 dyn_cast_or_null<TypedValueRegion>(O.getRegion())) {
1957 QualType baseT = baseR->getValueType();
1959 QualType elemT = R->getElementType();
1964 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
1966 if (
V->isUnknownOrUndef())
1970 return UnknownVal();
1976 return getBindingForFieldOrElementCommon(B, R, R->getElementType());
1980 const FieldRegion* R) {
1989 const MemRegion* superR = R->getSuperRegion();
1990 if (
const auto *VR = dyn_cast<VarRegion>(superR)) {
1991 const VarDecl *VD = VR->getDecl();
2000 if (
const auto *InitList = dyn_cast<InitListExpr>(Init)) {
2001 if (Index < InitList->getNumInits()) {
2002 if (
const Expr *FieldInit = InitList->getInit(Index))
2006 return svalBuilder.makeZeroVal(Ty);
2011 return getBindingForFieldOrElementCommon(B, R, Ty);
2016 const MemRegion *superR,
2017 const TypedValueRegion *R,
2021 const SVal &val = D.getValue();
2022 if (
SymbolRef parentSym = val.getAsSymbol())
2023 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
2025 if (val.isZeroConstant())
2026 return svalBuilder.makeZeroVal(Ty);
2028 if (val.isUnknownOrUndef())
2033 if (val.getAs<nonloc::LazyCompoundVal>() ||
2034 val.getAs<nonloc::CompoundVal>())
2037 llvm_unreachable(
"Unknown default value");
2043 SVal RegionStoreManager::getLazyBinding(
const SubRegion *LazyBindingRegion,
2044 RegionBindingsRef LazyBinding) {
2046 if (
const ElementRegion *ER = dyn_cast<ElementRegion>(LazyBindingRegion))
2047 Result = getBindingForElement(LazyBinding, ER);
2049 Result = getBindingForField(LazyBinding,
2050 cast<FieldRegion>(LazyBindingRegion));
2066 if (Result.isUndef())
2067 Result = UnknownVal();
2074 const TypedValueRegion *R,
2081 Store lazyBindingStore =
nullptr;
2082 const SubRegion *lazyBindingRegion =
nullptr;
2083 std::tie(lazyBindingStore, lazyBindingRegion) = findLazyBinding(B, R, R);
2084 if (lazyBindingRegion)
2085 return getLazyBinding(lazyBindingRegion,
2086 getRegionBindings(lazyBindingStore));
2090 bool hasSymbolicIndex =
false;
2106 bool hasPartialLazyBinding =
false;
2108 const SubRegion *SR = R;
2110 const MemRegion *
Base = SR->getSuperRegion();
2112 if (D->getAs<nonloc::LazyCompoundVal>()) {
2113 hasPartialLazyBinding =
true;
2120 if (
const ElementRegion *ER = dyn_cast<ElementRegion>(
Base)) {
2121 NonLoc index = ER->getIndex();
2122 if (!index.isConstant())
2123 hasSymbolicIndex =
true;
2128 SR = dyn_cast<SubRegion>(
Base);
2131 if (R->hasStackNonParametersStorage()) {
2132 if (isa<ElementRegion>(R)) {
2135 if (
const TypedValueRegion *typedSuperR =
2136 dyn_cast<TypedValueRegion>(R->getSuperRegion())) {
2137 if (typedSuperR->getValueType()->isVectorType())
2138 return UnknownVal();
2146 if (hasSymbolicIndex)
2147 return UnknownVal();
2152 if (!hasPartialLazyBinding && !isa<BlockDataRegion>(R->getBaseRegion())) {
2155 return UndefinedVal();
2160 return svalBuilder.getRegionValueSymbolVal(R);
2164 const ObjCIvarRegion* R) {
2169 const MemRegion *superR = R->getSuperRegion();
2174 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
2177 return UnknownVal();
2180 return getBindingForLazySymbol(R);
2184 const VarRegion *R) {
2194 const VarDecl *VD = R->getDecl();
2195 const MemSpaceRegion *MS = R->getMemorySpace();
2198 if (isa<StackArgumentsSpaceRegion>(MS))
2199 return svalBuilder.getRegionValueSymbolVal(R);
2210 return UnknownVal();
2216 if (isa<UnknownSpaceRegion>(MS))
2217 return svalBuilder.getRegionValueSymbolVal(R);
2219 if (isa<GlobalsSpaceRegion>(MS)) {
2223 if (B.isMainAnalysis())
2232 if (isa<StaticGlobalSpaceRegion>(MS))
2233 return svalBuilder.makeZeroVal(T);
2235 if (
Optional<SVal> V = getBindingForDerivedDefaultValue(B, MS, R, T)) {
2236 assert(!
V->getAs<nonloc::LazyCompoundVal>());
2237 return V.getValue();
2240 return svalBuilder.getRegionValueSymbolVal(R);
2243 return UndefinedVal();
2246 SVal RegionStoreManager::getBindingForLazySymbol(
const TypedValueRegion *R) {
2248 return svalBuilder.getRegionValueSymbolVal(R);
2251 const RegionStoreManager::SValListTy &
2252 RegionStoreManager::getInterestingValues(nonloc::LazyCompoundVal LCV) {
2254 LazyBindingsMapTy::iterator I = LazyBindingsMap.find(LCV.getCVData());
2255 if (I != LazyBindingsMap.end())
2261 const SubRegion *LazyR = LCV.getRegion();
2262 RegionBindingsRef B = getRegionBindings(LCV.getStore());
2268 return (LazyBindingsMap[LCV.getCVData()] = std::move(List));
2270 SmallVector<BindingPair, 32>
Bindings;
2273 for (SmallVectorImpl<BindingPair>::const_iterator I =
Bindings.begin(),
2277 if (
V.isUnknownOrUndef() ||
V.isConstant())
2281 V.getAs<nonloc::LazyCompoundVal>()) {
2282 const SValListTy &InnerList = getInterestingValues(*InnerLCV);
2283 List.insert(List.end(), InnerList.begin(), InnerList.end());
2290 return (LazyBindingsMap[LCV.getCVData()] = std::move(List));
2294 const TypedValueRegion *R) {
2299 return svalBuilder.makeLazyCompoundVal(StoreRef(B.asStore(), *
this), R);
2306 return CRD->getNumBases() == 0;
2311 const TypedValueRegion *R) {
2314 return UnknownVal();
2316 return createLazyBinding(B, R);
2320 const TypedValueRegion *R) {
2322 "Only constant array types can have compound bindings.");
2324 return createLazyBinding(B, R);
2327 bool RegionStoreManager::includedInBindings(
Store store,
2328 const MemRegion *region)
const {
2329 RegionBindingsRef B = getRegionBindings(store);
2330 region = region->getBaseRegion();
2333 if (B.lookup(region))
2337 for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI) {
2339 for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end();
2341 const SVal &D = CI.getData();
2342 if (
const MemRegion *R = D.getAsRegion())
2343 if (R->getBaseRegion() == region)
2355 StoreRef RegionStoreManager::killBinding(
Store ST, Loc L) {
2357 if (
const MemRegion* R = LV->getRegion())
2358 return StoreRef(getRegionBindings(ST).removeBinding(R)
2360 .getRootWithoutRetain(),
2363 return StoreRef(ST, *
this);
2368 if (L.getAs<loc::ConcreteInt>())
2372 const MemRegion *R = L.castAs<loc::MemRegionVal>().getRegion();
2375 if (
const TypedValueRegion* TR = dyn_cast<TypedValueRegion>(R)) {
2378 return bindArray(B, TR,
V);
2380 return bindStruct(B, TR,
V);
2382 return bindVector(B, TR,
V);
2384 return bindAggregate(B, TR,
V);
2387 if (
const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) {
2390 QualType T = SR->getSymbol()->getType();
2394 R = GetElementZeroRegion(SR, T);
2397 assert((!isa<CXXThisRegion>(R) || !B.lookup(R)) &&
2398 "'this' pointer is not an l-value and is not assignable");
2401 RegionBindingsRef NewB = removeSubRegionBindings(B, cast<SubRegion>(R));
2402 return NewB.addBinding(BindingKey::Make(R, BindingKey::Direct),
V);
2412 V = svalBuilder.makeNullWithType(T);
2414 V = svalBuilder.makeZeroVal(T);
2418 V = svalBuilder.makeZeroVal(Ctx.
IntTy);
2429 return B.addBinding(R, BindingKey::Default,
V);
2434 const TypedValueRegion* R,
2448 SVal
V = getBinding(B.asStore(), *MRV, R->getValueType());
2449 return bindAggregate(B, R,
V);
2453 if (Init.getAs<nonloc::LazyCompoundVal>())
2454 return bindAggregate(B, R, Init);
2456 if (Init.isUnknown())
2457 return bindAggregate(B, R, UnknownVal());
2460 const nonloc::CompoundVal& CV = Init.castAs<nonloc::CompoundVal>();
2464 RegionBindingsRef NewB(B);
2466 for (;
Size.hasValue() ? i <
Size.getValue() :
true ; ++i, ++VI) {
2471 const NonLoc &Idx = svalBuilder.makeArrayIndex(i);
2472 const ElementRegion *ER = MRMgr.getElementRegion(ElementTy, Idx, R, Ctx);
2475 NewB = bindStruct(NewB, ER, *VI);
2477 NewB = bindArray(NewB, ER, *VI);
2479 NewB = bind(NewB, loc::MemRegionVal(ER), *VI);
2485 if (!
Size.hasValue() || i <
Size.getValue())
2486 NewB = setImplicitDefaultValue(NewB, R, ElementTy);
2492 const TypedValueRegion* R,
2498 if (
V.getAs<nonloc::LazyCompoundVal>() ||
V.getAs<nonloc::SymbolVal>())
2499 return bindAggregate(B, R,
V);
2504 if (!
V.getAs<nonloc::CompoundVal>()) {
2505 return bindAggregate(B, R, UnknownVal());
2509 nonloc::CompoundVal CV =
V.castAs<nonloc::CompoundVal>();
2512 RegionBindingsRef NewB(B);
2514 for ( ; index != numElements ; ++index) {
2518 NonLoc Idx = svalBuilder.makeArrayIndex(index);
2519 const ElementRegion *ER = MRMgr.getElementRegion(ElemType, Idx, R, Ctx);
2522 NewB = bindArray(NewB, ER, *VI);
2524 NewB = bindStruct(NewB, ER, *VI);
2526 NewB = bind(NewB, loc::MemRegionVal(ER), *VI);
2533 const TypedValueRegion *R,
2535 nonloc::LazyCompoundVal LCV) {
2538 if (
const CXXRecordDecl *Class = dyn_cast<CXXRecordDecl>(RD))
2539 if (
Class->getNumBases() != 0 ||
Class->getNumVBases() != 0)
2542 for (
const auto *FD : RD->
fields()) {
2548 if (Fields.size() == SmallStructLimit)
2555 Fields.push_back(FD);
2558 RegionBindingsRef NewB = B;
2560 for (FieldVector::iterator I = Fields.begin(), E = Fields.end(); I != E; ++I){
2561 const FieldRegion *SourceFR = MRMgr.getFieldRegion(*I, LCV.getRegion());
2562 SVal
V = getBindingForField(getRegionBindings(LCV.getStore()), SourceFR);
2564 const FieldRegion *DestFR = MRMgr.getFieldRegion(*I, R);
2565 NewB = bind(NewB, loc::MemRegionVal(DestFR),
V);
2572 const TypedValueRegion* R,
2574 if (!Features.supportsFields())
2583 if (!RD->isCompleteDefinition())
2588 V.getAs<nonloc::LazyCompoundVal>()) {
2591 return bindAggregate(B, R,
V);
2593 if (
V.getAs<nonloc::SymbolVal>())
2594 return bindAggregate(B, R,
V);
2599 if (
V.isUnknown() || !
V.getAs<nonloc::CompoundVal>())
2600 return bindAggregate(B, R, UnknownVal());
2618 const nonloc::CompoundVal& CV =
V.castAs<nonloc::CompoundVal>();
2621 RegionBindingsRef NewB(B);
2625 if (
const auto *CRD = dyn_cast<CXXRecordDecl>(RD)) {
2633 assert((CRD->isAggregate() || (Ctx.
getLangOpts().ObjC && VI == VE)) &&
2634 "Non-aggregates are constructed with a constructor!");
2636 for (
const auto &B : CRD->bases()) {
2638 assert(!B.isVirtual() &&
"Aggregates cannot have virtual base classes!");
2647 assert(BRD &&
"Base classes must be C++ classes!");
2649 const CXXBaseObjectRegion *BR =
2650 MRMgr.getCXXBaseObjectRegion(BRD, R,
false);
2652 NewB = bindStruct(NewB, BR, *VI);
2660 for (FI = RD->field_begin(), FE = RD->field_end(); FI != FE; ++FI) {
2666 if (FI->isUnnamedBitfield())
2670 const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);
2673 NewB = bindArray(NewB, FR, *VI);
2675 NewB = bindStruct(NewB, FR, *VI);
2677 NewB = bind(NewB, loc::MemRegionVal(FR), *VI);
2683 NewB = NewB.addBinding(R, BindingKey::Default,
2684 svalBuilder.makeIntVal(0,
false));
2692 const TypedRegion *R,
2696 return removeSubRegionBindings(B, R).addBinding(R, BindingKey::Default, Val);
2704 class RemoveDeadBindingsWorker
2705 :
public ClusterAnalysis<RemoveDeadBindingsWorker> {
2706 SmallVector<const SymbolicRegion *, 12> Postponed;
2707 SymbolReaper &SymReaper;
2711 RemoveDeadBindingsWorker(RegionStoreManager &rm,
2712 ProgramStateManager &stateMgr,
2713 RegionBindingsRef
b, SymbolReaper &symReaper,
2715 : ClusterAnalysis<RemoveDeadBindingsWorker>(rm, stateMgr,
b),
2716 SymReaper(symReaper), CurrentLCtx(LCtx) {}
2719 void VisitAddedToCluster(
const MemRegion *baseR,
const ClusterBindings &C);
2721 using ClusterAnalysis<RemoveDeadBindingsWorker>::VisitCluster;
2723 using ClusterAnalysis::AddToWorkList;
2725 bool AddToWorkList(
const MemRegion *R);
2727 bool UpdatePostponed();
2728 void VisitBinding(SVal
V);
2732 bool RemoveDeadBindingsWorker::AddToWorkList(
const MemRegion *R) {
2733 const MemRegion *BaseR = R->getBaseRegion();
2734 return AddToWorkList(WorkListElement(BaseR), getCluster(BaseR));
2737 void RemoveDeadBindingsWorker::VisitAddedToCluster(
const MemRegion *baseR,
2740 if (
const VarRegion *VR = dyn_cast<VarRegion>(baseR)) {
2741 if (SymReaper.isLive(VR))
2742 AddToWorkList(baseR, &C);
2747 if (
const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) {
2748 if (SymReaper.isLive(SR->getSymbol()))
2749 AddToWorkList(SR, &C);
2751 Postponed.push_back(SR);
2756 if (isa<NonStaticGlobalSpaceRegion>(baseR)) {
2757 AddToWorkList(baseR, &C);
2762 if (
const CXXThisRegion *TR = dyn_cast<CXXThisRegion>(baseR)) {
2763 const auto *StackReg =
2764 cast<StackArgumentsSpaceRegion>(TR->getSuperRegion());
2767 (RegCtx == CurrentLCtx || RegCtx->
isParentOf(CurrentLCtx)))
2768 AddToWorkList(TR, &C);
2772 void RemoveDeadBindingsWorker::VisitCluster(
const MemRegion *baseR,
2779 if (
const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(baseR))
2780 SymReaper.markLive(SymR->getSymbol());
2782 for (ClusterBindings::iterator I =
C->begin(), E =
C->end(); I != E; ++I) {
2784 SymReaper.markElementIndicesLive(I.getKey().getRegion());
2786 VisitBinding(I.getData());
2790 void RemoveDeadBindingsWorker::VisitBinding(SVal
V) {
2793 V.getAs<nonloc::LazyCompoundVal>()) {
2795 const RegionStoreManager::SValListTy &Vals = RM.getInterestingValues(*LCS);
2797 for (RegionStoreManager::SValListTy::const_iterator I = Vals.begin(),
2806 if (
const MemRegion *R =
V.getAsRegion()) {
2808 SymReaper.markLive(R);
2811 if (
const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(R)) {
2812 BlockDataRegion::referenced_vars_iterator I = BR->referenced_vars_begin(),
2813 E = BR->referenced_vars_end();
2814 for ( ; I != E; ++I)
2815 AddToWorkList(I.getCapturedRegion());
2821 for (
auto SI =
V.symbol_begin(), SE =
V.symbol_end(); SI!=SE; ++SI)
2822 SymReaper.markLive(*SI);
2825 bool RemoveDeadBindingsWorker::UpdatePostponed() {
2830 for (
auto I = Postponed.begin(), E = Postponed.end(); I != E; ++I) {
2831 if (
const SymbolicRegion *SR = *I) {
2832 if (SymReaper.isLive(SR->getSymbol())) {
2842 StoreRef RegionStoreManager::removeDeadBindings(
Store store,
2844 SymbolReaper& SymReaper) {
2845 RegionBindingsRef B = getRegionBindings(store);
2846 RemoveDeadBindingsWorker W(*
this, StateMgr, B, SymReaper, LCtx);
2847 W.GenerateClusters();
2851 E = SymReaper.region_end(); I != E; ++I) {
2852 W.AddToWorkList(*I);
2855 do W.RunWorkList();
while (W.UpdatePostponed());
2860 for (RegionBindingsRef::iterator I = B.begin(), E = B.end(); I != E; ++I) {
2861 const MemRegion *
Base = I.getKey();
2865 if (!W.isVisited(
Base))
2869 return StoreRef(B.asStore(), *
this);
2876 void RegionStoreManager::printJson(raw_ostream &Out,
Store S,
const char *NL,
2877 unsigned int Space,
bool IsDot)
const {
2878 RegionBindingsRef
Bindings = getRegionBindings(S);
2880 Indent(Out, Space, IsDot) <<
"\"store\": ";
2883 Out <<
"null," << NL;
2887 Out <<
"{ \"pointer\": \"" <<
Bindings.asStore() <<
"\", \"items\": [" << NL;
2888 Bindings.printJson(Out, NL, Space + 1, IsDot);
2889 Indent(Out, Space, IsDot) <<
"]}," << NL;