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)
55 : P(r, k | Symbolic), Data(reinterpret_cast<
uintptr_t>(Base)) {
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() || isa<ObjCIvarRegion>(r) ||
66 isa <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;
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).
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;
241 const ClusterBindings &CB = I.getData();
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();
276 const ClusterBindings *ExistingCluster = lookup(Base);
277 ClusterBindings Cluster =
278 (ExistingCluster ? *ExistingCluster : CBFactory->getEmptyMap());
280 ClusterBindings NewCluster = CBFactory->add(Cluster, K, V);
281 return add(Base, NewCluster);
285 RegionBindingsRef RegionBindingsRef::addBinding(
const MemRegion *R,
291 const SVal *RegionBindingsRef::lookup(BindingKey K)
const {
292 const ClusterBindings *Cluster = lookup(K.getBaseRegion());
295 return Cluster->lookup(K);
298 const SVal *RegionBindingsRef::lookup(
const MemRegion *R,
299 BindingKey::Kind k)
const {
303 RegionBindingsRef RegionBindingsRef::removeBinding(BindingKey K) {
304 const MemRegion *Base = K.getBaseRegion();
305 const ClusterBindings *Cluster = lookup(Base);
309 ClusterBindings NewCluster = CBFactory->remove(*Cluster, K);
310 if (NewCluster.isEmpty())
312 return add(Base, NewCluster);
315 RegionBindingsRef RegionBindingsRef::removeBinding(
const MemRegion *R,
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,
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 SubEngine &Eng = StateMgr.getOwningEngine();
386 SmallStructLimit = Options.RegionStoreSmallStructLimit;
393 RegionBindingsRef setImplicitDefaultValue(RegionBindingsConstRef B,
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,
427 const Expr *E,
unsigned Count,
431 RegionAndSymbolInvalidationTraits &ITraits,
432 InvalidatedRegions *Invalidated,
433 InvalidatedRegions *InvalidatedTopLevel)
override;
435 bool scanReachableSymbols(
Store S,
const MemRegion *R,
436 ScanReachableSymbols &Callbacks)
override;
438 RegionBindingsRef removeSubRegionBindings(RegionBindingsConstRef B,
443 StoreRef Bind(
Store store, Loc LV, SVal V)
override {
444 return StoreRef(bind(getRegionBindings(store), LV, V).asStore(), *
this);
447 RegionBindingsRef bind(RegionBindingsConstRef B, Loc LV, SVal V);
451 StoreRef BindDefaultInitial(
Store store,
const MemRegion *R,
453 RegionBindingsRef B = getRegionBindings(store);
456 assert(!(B.getDefaultBinding(R) || B.getDirectBinding(R)) &&
457 "Double initialization!");
459 return StoreRef(B.asImmutableMap().getRootWithoutRetain(), *
this);
464 StoreRef BindDefaultZero(
Store store,
const MemRegion *R)
override {
474 if (
const auto *BR = dyn_cast<CXXBaseObjectRegion>(R))
475 if (BR->getDecl()->isEmpty())
476 return StoreRef(store, *
this);
478 RegionBindingsRef B = getRegionBindings(store);
479 SVal V = svalBuilder.makeZeroVal(Ctx.CharTy);
480 B = removeSubRegionBindings(B, cast<SubRegion>(R));
482 return StoreRef(B.asImmutableMap().getRootWithoutRetain(), *
this);
496 const TypedValueRegion *R,
498 nonloc::LazyCompoundVal LCV);
501 RegionBindingsRef bindStruct(RegionBindingsConstRef B,
502 const TypedValueRegion* R, SVal V);
505 RegionBindingsRef bindVector(RegionBindingsConstRef B,
506 const TypedValueRegion* R, SVal V);
508 RegionBindingsRef bindArray(RegionBindingsConstRef B,
509 const TypedValueRegion* R,
514 RegionBindingsRef bindAggregate(RegionBindingsConstRef B,
515 const TypedRegion *R,
521 StoreRef killBinding(
Store ST, Loc L)
override;
523 void incrementReferenceCount(
Store store)
override {
524 getRegionBindings(store).manualRetain();
530 void decrementReferenceCount(
Store store)
override {
531 getRegionBindings(store).manualRelease();
534 bool includedInBindings(
Store store,
const MemRegion *region)
const override;
550 return getBinding(getRegionBindings(S), L, T);
554 RegionBindingsRef B = getRegionBindings(S);
558 return B.getDefaultBinding(R->getBaseRegion());
563 SVal getBindingForElement(RegionBindingsConstRef B,
const ElementRegion *R);
565 SVal getBindingForField(RegionBindingsConstRef B,
const FieldRegion *R);
567 SVal getBindingForObjCIvar(RegionBindingsConstRef B,
const ObjCIvarRegion *R);
569 SVal getBindingForVar(RegionBindingsConstRef B,
const VarRegion *R);
571 SVal getBindingForLazySymbol(
const TypedValueRegion *R);
573 SVal getBindingForFieldOrElementCommon(RegionBindingsConstRef B,
574 const TypedValueRegion *R,
577 SVal getLazyBinding(
const SubRegion *LazyBindingRegion,
578 RegionBindingsRef LazyBinding);
585 SVal getBindingForStruct(RegionBindingsConstRef B,
const TypedValueRegion *R);
586 SVal getBindingForArray(RegionBindingsConstRef B,
const TypedValueRegion *R);
587 NonLoc createLazyBinding(RegionBindingsConstRef B,
const TypedValueRegion *R);
594 Optional<SVal> getBindingForDerivedDefaultValue(RegionBindingsConstRef B,
595 const MemRegion *superR,
596 const TypedValueRegion *R,
603 std::pair<Store, const SubRegion *>
604 findLazyBinding(RegionBindingsConstRef B,
const SubRegion *R,
605 const SubRegion *originalRegion);
613 const SValListTy &getInterestingValues(nonloc::LazyCompoundVal LCV);
622 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) {
653 const ClusterBindings &Cluster = I.getData();
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);
705 template <
typename DERIVED>
706 class ClusterAnalysis {
708 typedef llvm::DenseMap<const MemRegion *, const ClusterBindings *> ClusterMap;
709 typedef const MemRegion * WorkListElement;
712 llvm::SmallPtrSet<const ClusterBindings *, 16> Visited;
716 RegionStoreManager &RM;
718 SValBuilder &svalBuilder;
724 const ClusterBindings *getCluster(
const MemRegion *R) {
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();
753 const ClusterBindings &Cluster = RI.getData();
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);
764 bool AddToWorkList(WorkListElement E,
const ClusterBindings *C) {
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) {}
785 void VisitCluster(
const MemRegion *baseR,
const ClusterBindings *C) {}
787 void VisitCluster(
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);
802 const ClusterBindings *Cluster = B.lookup(R);
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");
843 FieldVector FieldsInBindingKey;
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);
867 SValBuilder &SVB,
const ClusterBindings &Cluster,
868 const SubRegion *Top, BindingKey TopKey,
869 bool IncludeAllDefaultBindings) {
870 FieldVector FieldsInSymbolicSubregions;
871 if (TopKey.hasSymbolicOffset()) {
873 Top = TopKey.getConcreteOffsetRegion();
878 uint64_t Length = UINT64_MAX;
879 SVal Extent = Top->getExtent(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) {
904 Bindings.push_back(*I);
906 }
else if (NextKey.getOffset() == TopKey.getOffset()) {
913 if (IncludeAllDefaultBindings || NextKey.isDirect())
914 Bindings.push_back(*I);
917 }
else if (NextKey.hasSymbolicOffset()) {
918 const MemRegion *Base = NextKey.getConcreteOffsetRegion();
919 if (Top->isSubRegionOf(Base) && Top != Base) {
923 if (IncludeAllDefaultBindings || NextKey.isDirect())
925 Bindings.push_back(*I);
926 }
else if (
const SubRegion *BaseSR = dyn_cast<SubRegion>(Base)) {
929 if (BaseSR->isSubRegionOf(Top))
931 Bindings.push_back(*I);
939 SValBuilder &SVB,
const ClusterBindings &Cluster,
940 const SubRegion *Top,
bool IncludeAllDefaultBindings) {
943 IncludeAllDefaultBindings);
947 RegionStoreManager::removeSubRegionBindings(RegionBindingsConstRef B,
948 const SubRegion *Top) {
950 const MemRegion *ClusterHead = TopKey.getBaseRegion();
952 if (Top == ClusterHead) {
954 return B.remove(Top);
957 const ClusterBindings *Cluster = B.lookup(ClusterHead);
961 if (TopKey.hasSymbolicOffset()) {
962 const SubRegion *Concrete = TopKey.getConcreteOffsetRegion();
972 ClusterBindingsRef Result(*Cluster, CBFactory);
976 Result = Result.remove(I->first);
982 if (TopKey.hasSymbolicOffset()) {
983 const SubRegion *Concrete = TopKey.getConcreteOffsetRegion();
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;
1004 InvalidateRegionsWorker(RegionStoreManager &rm,
1005 ProgramStateManager &stateMgr,
1006 RegionBindingsRef b,
1007 const Expr *ex,
unsigned count,
1010 RegionAndSymbolInvalidationTraits &ITraitsIn,
1013 : ClusterAnalysis<InvalidateRegionsWorker>(rm, stateMgr, b),
1014 Ex(ex), Count(count), LCtx(lctx), IS(is), ITraits(ITraitsIn), Regions(r),
1015 GlobalsFilter(GFK) {}
1017 void VisitCluster(
const MemRegion *baseR,
const ClusterBindings *C);
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,
1067 const ClusterBindings *C) {
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()) {
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>(baseR) || isa<SymbolicRegion>(baseR)) {
1150 DefinedOrUnknownSVal V =
1151 svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, Ctx.IntTy, Count);
1156 if (!baseR->isBoundable())
1159 const TypedValueRegion *TR = cast<TypedValueRegion>(baseR);
1162 if (isInitiallyIncludedGlobalRegion(baseR)) {
1169 if (T->isRecordType()) {
1172 DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx,
1178 if (
const ArrayType *AT = Ctx.getAsArrayType(T)) {
1179 bool doNotInvalidateSuperRegion = ITraits.hasTrait(
1183 if (doNotInvalidateSuperRegion) {
1190 NumElements = CAT->getSize().getZExtValue();
1192 goto conjure_default;
1193 QualType ElementTy = AT->getElementType();
1194 uint64_t ElemSize = Ctx.getTypeSize(ElementTy);
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;
1214 const ClusterBindings *C = B.lookup(SuperR);
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 (R && isa<SymbolicRegion>(R))
1243 DefinedOrUnknownSVal V =
1244 svalBuilder.conjureSymbolVal(baseR, Ex, LCtx,
1245 AT->getElementType(), Count);
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)
1299 Invalidated->push_back(GS);
1304 void RegionStoreManager::populateWorkList(InvalidateRegionsWorker &W,
1306 InvalidatedRegions *TopLevelRegions) {
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,
1337 const Expr *Ex,
unsigned Count,
1341 RegionAndSymbolInvalidationTraits &ITraits,
1342 InvalidatedRegions *TopLevelRegions,
1343 InvalidatedRegions *Invalidated) {
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);
1393 DefinedOrUnknownSVal
1397 SVal Size = cast<SubRegion>(R)->getExtent(svalBuilder);
1398 const llvm::APSInt *SizeInt = svalBuilder.getKnownValue(state, Size);
1400 return UnknownVal();
1404 if (Ctx.getAsVariableArrayType(EleTy)) {
1408 return UnknownVal();
1411 CharUnits EleSize = Ctx.getTypeSizeInChars(EleTy);
1416 return svalBuilder.makeIntVal(RegionSize / EleSize,
1417 svalBuilder.getArrayIndexType());
1430 SVal RegionStoreManager::ArrayToPointer(Loc Array,
QualType T) {
1431 if (Array.getAs<loc::ConcreteInt>())
1434 if (!Array.getAs<loc::MemRegionVal>())
1435 return UnknownVal();
1437 const SubRegion *R =
1438 cast<SubRegion>(Array.castAs<loc::MemRegionVal>().getRegion());
1439 NonLoc ZeroIdx = svalBuilder.makeZeroArrayIndex();
1440 return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, R, Ctx));
1447 SVal RegionStoreManager::getBinding(RegionBindingsConstRef B, Loc L,
QualType T) {
1448 assert(!L.getAs<UnknownVal>() &&
"location unknown");
1449 assert(!L.getAs<UndefinedVal>() &&
"location undefined");
1457 if (L.getAs<loc::ConcreteInt>()) {
1458 return UnknownVal();
1460 if (!L.getAs<loc::MemRegionVal>()) {
1461 return UnknownVal();
1464 const MemRegion *MR = L.castAs<loc::MemRegionVal>().getRegion();
1466 if (isa<BlockDataRegion>(MR)) {
1467 return UnknownVal();
1470 if (!isa<TypedValueRegion>(MR)) {
1472 if (
const TypedRegion *TR = dyn_cast<TypedRegion>(MR))
1474 else if (
const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR))
1477 assert(!T.
isNull() &&
"Unable to auto-detect binding type!");
1478 assert(!T->
isVoidType() &&
"Attempting to dereference a void pointer!");
1479 MR = GetElementZeroRegion(cast<SubRegion>(MR), T);
1481 T = cast<TypedValueRegion>(MR)->getValueType();
1486 const TypedValueRegion *R = cast<TypedValueRegion>(MR);
1491 if (RTy->isAnyComplexType())
1492 return UnknownVal();
1502 if (RTy->isStructureOrClassType())
1503 return getBindingForStruct(B, R);
1506 if (RTy->isUnionType())
1507 return createLazyBinding(B, R);
1509 if (RTy->isArrayType()) {
1510 if (RTy->isConstantArrayType())
1511 return getBindingForArray(B, R);
1513 return UnknownVal();
1517 if (RTy->isVectorType())
1518 return UnknownVal();
1520 if (
const FieldRegion* FR = dyn_cast<FieldRegion>(R))
1521 return CastRetrievedVal(getBindingForField(B, FR), FR, T);
1523 if (
const ElementRegion* ER = dyn_cast<ElementRegion>(R)) {
1529 return CastRetrievedVal(getBindingForElement(B, ER), ER, T);
1532 if (
const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) {
1539 return CastRetrievedVal(getBindingForObjCIvar(B, IVR), IVR, T);
1542 if (
const VarRegion *VR = dyn_cast<VarRegion>(R)) {
1549 return CastRetrievedVal(getBindingForVar(B, VR), VR, T);
1552 const SVal *V = B.lookup(R, BindingKey::Direct);
1561 if (R->hasStackNonParametersStorage()) {
1566 return UndefinedVal();
1570 return svalBuilder.getRegionValueSymbolVal(R);
1575 if (
const TypedValueRegion *TVR = dyn_cast<TypedValueRegion>(R))
1576 RegionTy = TVR->getValueType();
1578 if (
const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
1579 RegionTy = SR->getSymbol()->getType();
1593 const SubRegion *R,
bool AllowSubregionBindings) {
1605 if (!RegionTy.
isNull() &&
1607 QualType SourceRegionTy = LCV->getRegion()->getValueType();
1608 if (!SVB.getContext().hasSameUnqualifiedType(RegionTy, SourceRegionTy))
1612 if (!AllowSubregionBindings) {
1618 if (Bindings.size() > 1)
1626 std::pair<Store, const SubRegion *>
1627 RegionStoreManager::findLazyBinding(RegionBindingsConstRef B,
1629 const SubRegion *originalRegion) {
1630 if (originalRegion != R) {
1633 return std::make_pair(V->getStore(), V->getRegion());
1636 typedef std::pair<Store, const SubRegion *> StoreRegionPair;
1637 StoreRegionPair Result = StoreRegionPair();
1639 if (
const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
1640 Result = findLazyBinding(B, cast<SubRegion>(ER->getSuperRegion()),
1644 Result.second = MRMgr.getElementRegionWithSuper(ER, Result.second);
1646 }
else if (
const FieldRegion *FR = dyn_cast<FieldRegion>(R)) {
1647 Result = findLazyBinding(B, cast<SubRegion>(FR->getSuperRegion()),
1651 Result.second = MRMgr.getFieldRegionWithSuper(FR, Result.second);
1653 }
else if (
const CXXBaseObjectRegion *BaseReg =
1654 dyn_cast<CXXBaseObjectRegion>(R)) {
1657 Result = findLazyBinding(B, cast<SubRegion>(BaseReg->getSuperRegion()),
1661 Result.second = MRMgr.getCXXBaseObjectRegionWithSuper(BaseReg,
1668 SVal RegionStoreManager::getBindingForElement(RegionBindingsConstRef B,
1669 const ElementRegion* R) {
1671 if (isa<CompoundLiteralRegion>(R->getBaseRegion()))
1672 return UnknownVal();
1678 const MemRegion* superR = R->getSuperRegion();
1681 if (
const StringRegion *StrR = dyn_cast<StringRegion>(superR)) {
1684 QualType T = Ctx.getAsArrayType(StrR->getValueType())->getElementType();
1685 if (!Ctx.hasSameUnqualifiedType(T, R->getElementType()))
1686 return UnknownVal();
1689 SVal Idx = R->getIndex();
1691 int64_t i = CI->getValue().getSExtValue();
1695 return UndefinedVal();
1702 return svalBuilder.makeIntVal(c, T);
1704 }
else if (
const VarRegion *VR = dyn_cast<VarRegion>(superR)) {
1707 const VarDecl *VD = VR->getDecl();
1709 R->getElementType().isConstQualified() ||
1712 if (
const auto *InitList = dyn_cast<InitListExpr>(Init)) {
1714 if (
auto CI = R->getIndex().getAs<nonloc::ConcreteInt>()) {
1715 int64_t i = CI->getValue().getSExtValue();
1719 return UndefinedVal();
1721 if (
auto CAT = Ctx.getAsConstantArrayType(VD->
getType()))
1722 if (CAT->getSize().sle(i))
1723 return UndefinedVal();
1726 if (i >= InitList->getNumInits())
1727 return svalBuilder.makeZeroVal(R->getElementType());
1729 if (
const Expr *ElemInit = InitList->getInit(i))
1739 if (isa<CodeTextRegion>(superR))
1740 return UnknownVal();
1748 const RegionRawOffset &O = R->getAsArrayOffset();
1752 return UnknownVal();
1754 if (
const TypedValueRegion *baseR =
1755 dyn_cast_or_null<TypedValueRegion>(O.getRegion())) {
1756 QualType baseT = baseR->getValueType();
1758 QualType elemT = R->getElementType();
1760 if (Ctx.getTypeSizeInChars(baseT) >= Ctx.getTypeSizeInChars(elemT)) {
1762 if (
SymbolRef parentSym = V->getAsSymbol())
1763 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
1765 if (V->isUnknownOrUndef())
1769 return UnknownVal();
1775 return getBindingForFieldOrElementCommon(B, R, R->getElementType());
1778 SVal RegionStoreManager::getBindingForField(RegionBindingsConstRef B,
1779 const FieldRegion* R) {
1794 const MemRegion* superR = R->getSuperRegion();
1795 if (
const auto *VR = dyn_cast<VarRegion>(superR)) {
1796 const VarDecl *VD = VR->getDecl();
1805 if (
const auto *InitList = dyn_cast<InitListExpr>(Init)) {
1806 if (Index < InitList->getNumInits()) {
1807 if (
const Expr *FieldInit = InitList->getInit(Index))
1811 return svalBuilder.makeZeroVal(Ty);
1816 return getBindingForFieldOrElementCommon(B, R, Ty);
1820 RegionStoreManager::getBindingForDerivedDefaultValue(RegionBindingsConstRef B,
1821 const MemRegion *superR,
1822 const TypedValueRegion *R,
1826 const SVal &val = D.getValue();
1827 if (
SymbolRef parentSym = val.getAsSymbol())
1828 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
1830 if (val.isZeroConstant())
1831 return svalBuilder.makeZeroVal(Ty);
1833 if (val.isUnknownOrUndef())
1838 if (val.getAs<nonloc::LazyCompoundVal>() ||
1839 val.getAs<nonloc::CompoundVal>())
1842 llvm_unreachable(
"Unknown default value");
1848 SVal RegionStoreManager::getLazyBinding(
const SubRegion *LazyBindingRegion,
1849 RegionBindingsRef LazyBinding) {
1851 if (
const ElementRegion *ER = dyn_cast<ElementRegion>(LazyBindingRegion))
1852 Result = getBindingForElement(LazyBinding, ER);
1854 Result = getBindingForField(LazyBinding,
1855 cast<FieldRegion>(LazyBindingRegion));
1871 if (Result.isUndef())
1872 Result = UnknownVal();
1878 RegionStoreManager::getBindingForFieldOrElementCommon(RegionBindingsConstRef B,
1879 const TypedValueRegion *R,
1886 Store lazyBindingStore =
nullptr;
1887 const SubRegion *lazyBindingRegion =
nullptr;
1888 std::tie(lazyBindingStore, lazyBindingRegion) = findLazyBinding(B, R, R);
1889 if (lazyBindingRegion)
1890 return getLazyBinding(lazyBindingRegion,
1891 getRegionBindings(lazyBindingStore));
1895 bool hasSymbolicIndex =
false;
1911 bool hasPartialLazyBinding =
false;
1913 const SubRegion *SR = R;
1915 const MemRegion *Base = SR->getSuperRegion();
1916 if (
Optional<SVal> D = getBindingForDerivedDefaultValue(B, Base, R, Ty)) {
1917 if (D->getAs<nonloc::LazyCompoundVal>()) {
1918 hasPartialLazyBinding =
true;
1925 if (
const ElementRegion *ER = dyn_cast<ElementRegion>(Base)) {
1926 NonLoc index = ER->getIndex();
1927 if (!index.isConstant())
1928 hasSymbolicIndex =
true;
1933 SR = dyn_cast<SubRegion>(Base);
1936 if (R->hasStackNonParametersStorage()) {
1937 if (isa<ElementRegion>(R)) {
1940 if (
const TypedValueRegion *typedSuperR =
1941 dyn_cast<TypedValueRegion>(R->getSuperRegion())) {
1942 if (typedSuperR->getValueType()->isVectorType())
1943 return UnknownVal();
1951 if (hasSymbolicIndex)
1952 return UnknownVal();
1954 if (!hasPartialLazyBinding)
1955 return UndefinedVal();
1959 return svalBuilder.getRegionValueSymbolVal(R);
1962 SVal RegionStoreManager::getBindingForObjCIvar(RegionBindingsConstRef B,
1963 const ObjCIvarRegion* R) {
1968 const MemRegion *superR = R->getSuperRegion();
1972 if (
SymbolRef parentSym = V->getAsSymbol())
1973 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
1976 return UnknownVal();
1979 return getBindingForLazySymbol(R);
1982 SVal RegionStoreManager::getBindingForVar(RegionBindingsConstRef B,
1983 const VarRegion *R) {
1993 const VarDecl *VD = R->getDecl();
1994 const MemSpaceRegion *MS = R->getMemorySpace();
1997 if (isa<StackArgumentsSpaceRegion>(MS))
1998 return svalBuilder.getRegionValueSymbolVal(R);
2009 return UnknownVal();
2015 if (isa<UnknownSpaceRegion>(MS))
2016 return svalBuilder.getRegionValueSymbolVal(R);
2018 if (isa<GlobalsSpaceRegion>(MS)) {
2022 if (B.isMainAnalysis())
2031 if (isa<StaticGlobalSpaceRegion>(MS))
2032 return svalBuilder.makeZeroVal(T);
2034 if (
Optional<SVal> V = getBindingForDerivedDefaultValue(B, MS, R, T)) {
2035 assert(!V->getAs<nonloc::LazyCompoundVal>());
2036 return V.getValue();
2039 return svalBuilder.getRegionValueSymbolVal(R);
2042 return UndefinedVal();
2045 SVal RegionStoreManager::getBindingForLazySymbol(
const TypedValueRegion *R) {
2047 return svalBuilder.getRegionValueSymbolVal(R);
2050 const RegionStoreManager::SValListTy &
2051 RegionStoreManager::getInterestingValues(nonloc::LazyCompoundVal LCV) {
2053 LazyBindingsMapTy::iterator I = LazyBindingsMap.find(LCV.getCVData());
2054 if (I != LazyBindingsMap.end())
2060 const SubRegion *LazyR = LCV.getRegion();
2061 RegionBindingsRef B = getRegionBindings(LCV.getStore());
2065 const ClusterBindings *Cluster = B.lookup(LazyR->getBaseRegion());
2067 return (LazyBindingsMap[LCV.getCVData()] = std::move(List));
2076 if (V.isUnknownOrUndef() || V.isConstant())
2080 V.getAs<nonloc::LazyCompoundVal>()) {
2081 const SValListTy &InnerList = getInterestingValues(*InnerLCV);
2082 List.insert(List.end(), InnerList.begin(), InnerList.end());
2089 return (LazyBindingsMap[LCV.getCVData()] = std::move(List));
2092 NonLoc RegionStoreManager::createLazyBinding(RegionBindingsConstRef B,
2093 const TypedValueRegion *R) {
2098 return svalBuilder.makeLazyCompoundVal(StoreRef(B.asStore(), *
this), R);
2105 return CRD->getNumBases() == 0;
2109 SVal RegionStoreManager::getBindingForStruct(RegionBindingsConstRef B,
2110 const TypedValueRegion *R) {
2113 return UnknownVal();
2115 return createLazyBinding(B, R);
2118 SVal RegionStoreManager::getBindingForArray(RegionBindingsConstRef B,
2119 const TypedValueRegion *R) {
2120 assert(Ctx.getAsConstantArrayType(R->getValueType()) &&
2121 "Only constant array types can have compound bindings.");
2123 return createLazyBinding(B, R);
2126 bool RegionStoreManager::includedInBindings(
Store store,
2127 const MemRegion *region)
const {
2128 RegionBindingsRef B = getRegionBindings(store);
2129 region = region->getBaseRegion();
2132 if (B.lookup(region))
2136 for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI) {
2137 const ClusterBindings &Cluster = RI.getData();
2138 for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end();
2140 const SVal &D = CI.getData();
2141 if (
const MemRegion *R = D.getAsRegion())
2142 if (R->getBaseRegion() == region)
2154 StoreRef RegionStoreManager::killBinding(
Store ST, Loc L) {
2156 if (
const MemRegion* R = LV->getRegion())
2157 return StoreRef(getRegionBindings(ST).removeBinding(R)
2159 .getRootWithoutRetain(),
2162 return StoreRef(ST, *
this);
2166 RegionStoreManager::bind(RegionBindingsConstRef B, Loc L, SVal V) {
2167 if (L.getAs<loc::ConcreteInt>())
2171 const MemRegion *R = L.castAs<loc::MemRegionVal>().getRegion();
2174 if (
const TypedValueRegion* TR = dyn_cast<TypedValueRegion>(R)) {
2177 return bindArray(B, TR, V);
2179 return bindStruct(B, TR, V);
2181 return bindVector(B, TR, V);
2183 return bindAggregate(B, TR, V);
2186 if (
const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) {
2189 QualType T = SR->getSymbol()->getType();
2193 R = GetElementZeroRegion(SR, T);
2196 assert((!isa<CXXThisRegion>(R) || !B.lookup(R)) &&
2197 "'this' pointer is not an l-value and is not assignable");
2200 RegionBindingsRef NewB = removeSubRegionBindings(B, cast<SubRegion>(R));
2205 RegionStoreManager::setImplicitDefaultValue(RegionBindingsConstRef B,
2211 V = svalBuilder.makeNull();
2213 V = svalBuilder.makeZeroVal(T);
2217 V = svalBuilder.makeZeroVal(Ctx.IntTy);
2232 RegionStoreManager::bindArray(RegionBindingsConstRef B,
2233 const TypedValueRegion* R,
2236 const ArrayType *AT =cast<ArrayType>(Ctx.getCanonicalType(R->getValueType()));
2241 Size = CAT->getSize().getZExtValue();
2247 SVal V = getBinding(B.asStore(), *MRV, R->getValueType());
2248 return bindAggregate(B, R, V);
2252 if (Init.getAs<nonloc::LazyCompoundVal>())
2253 return bindAggregate(B, R, Init);
2255 if (Init.isUnknown())
2256 return bindAggregate(B, R, UnknownVal());
2259 const nonloc::CompoundVal& CV = Init.castAs<nonloc::CompoundVal>();
2263 RegionBindingsRef NewB(B);
2265 for (; Size.hasValue() ? i < Size.getValue() :
true ; ++i, ++VI) {
2270 const NonLoc &Idx = svalBuilder.makeArrayIndex(i);
2271 const ElementRegion *ER = MRMgr.getElementRegion(ElementTy, Idx, R, Ctx);
2274 NewB = bindStruct(NewB, ER, *VI);
2276 NewB = bindArray(NewB, ER, *VI);
2278 NewB = bind(NewB, loc::MemRegionVal(ER), *VI);
2284 if (!Size.hasValue() || i < Size.getValue())
2285 NewB = setImplicitDefaultValue(NewB, R, ElementTy);
2290 RegionBindingsRef RegionStoreManager::bindVector(RegionBindingsConstRef B,
2291 const TypedValueRegion* R,
2297 if (V.getAs<nonloc::LazyCompoundVal>() || V.getAs<nonloc::SymbolVal>())
2298 return bindAggregate(B, R, V);
2303 if (!V.getAs<nonloc::CompoundVal>()) {
2304 return bindAggregate(B, R, UnknownVal());
2308 nonloc::CompoundVal CV = V.castAs<nonloc::CompoundVal>();
2311 RegionBindingsRef NewB(B);
2313 for ( ; index != numElements ; ++index) {
2317 NonLoc Idx = svalBuilder.makeArrayIndex(index);
2318 const ElementRegion *ER = MRMgr.getElementRegion(ElemType, Idx, R, Ctx);
2321 NewB = bindArray(NewB, ER, *VI);
2323 NewB = bindStruct(NewB, ER, *VI);
2325 NewB = bind(NewB, loc::MemRegionVal(ER), *VI);
2331 RegionStoreManager::tryBindSmallStruct(RegionBindingsConstRef B,
2332 const TypedValueRegion *R,
2334 nonloc::LazyCompoundVal LCV) {
2337 if (
const CXXRecordDecl *Class = dyn_cast<CXXRecordDecl>(RD))
2338 if (Class->getNumBases() != 0 || Class->getNumVBases() != 0)
2341 for (
const auto *FD : RD->
fields()) {
2342 if (FD->isUnnamedBitfield())
2347 if (Fields.size() == SmallStructLimit)
2354 Fields.push_back(FD);
2357 RegionBindingsRef NewB = B;
2359 for (FieldVector::iterator I = Fields.begin(), E = Fields.end(); I != E; ++I){
2360 const FieldRegion *SourceFR = MRMgr.getFieldRegion(*I, LCV.getRegion());
2361 SVal V = getBindingForField(getRegionBindings(LCV.getStore()), SourceFR);
2363 const FieldRegion *DestFR = MRMgr.getFieldRegion(*I, R);
2364 NewB = bind(NewB, loc::MemRegionVal(DestFR), V);
2370 RegionBindingsRef RegionStoreManager::bindStruct(RegionBindingsConstRef B,
2371 const TypedValueRegion* R,
2373 if (!Features.supportsFields())
2382 if (!RD->isCompleteDefinition())
2387 V.getAs<nonloc::LazyCompoundVal>()) {
2390 return bindAggregate(B, R, V);
2392 if (V.getAs<nonloc::SymbolVal>())
2393 return bindAggregate(B, R, V);
2398 if (V.isUnknown() || !V.getAs<nonloc::CompoundVal>())
2399 return bindAggregate(B, R, UnknownVal());
2417 const nonloc::CompoundVal& CV = V.castAs<nonloc::CompoundVal>();
2420 RegionBindingsRef NewB(B);
2424 if (
const auto *CRD = dyn_cast<CXXRecordDecl>(RD)) {
2432 assert((CRD->isAggregate() || (Ctx.getLangOpts().ObjC && VI == VE)) &&
2433 "Non-aggregates are constructed with a constructor!");
2435 for (
const auto &B : CRD->bases()) {
2437 assert(!B.isVirtual() &&
"Aggregates cannot have virtual base classes!");
2446 assert(BRD &&
"Base classes must be C++ classes!");
2448 const CXXBaseObjectRegion *BR =
2449 MRMgr.getCXXBaseObjectRegion(BRD, R,
false);
2451 NewB = bindStruct(NewB, BR, *VI);
2459 for (FI = RD->field_begin(), FE = RD->field_end(); FI != FE; ++FI) {
2465 if (FI->isUnnamedBitfield())
2469 const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);
2472 NewB = bindArray(NewB, FR, *VI);
2474 NewB = bindStruct(NewB, FR, *VI);
2476 NewB = bind(NewB, loc::MemRegionVal(FR), *VI);
2483 svalBuilder.makeIntVal(0,
false));
2490 RegionStoreManager::bindAggregate(RegionBindingsConstRef B,
2491 const TypedRegion *R,
2503 class RemoveDeadBindingsWorker
2504 :
public ClusterAnalysis<RemoveDeadBindingsWorker> {
2506 SymbolReaper &SymReaper;
2510 RemoveDeadBindingsWorker(RegionStoreManager &rm,
2511 ProgramStateManager &stateMgr,
2512 RegionBindingsRef b, SymbolReaper &symReaper,
2514 : ClusterAnalysis<RemoveDeadBindingsWorker>(rm, stateMgr, b),
2515 SymReaper(symReaper), CurrentLCtx(LCtx) {}
2518 void VisitAddedToCluster(
const MemRegion *baseR,
const ClusterBindings &C);
2519 void VisitCluster(
const MemRegion *baseR,
const ClusterBindings *C);
2520 using ClusterAnalysis<RemoveDeadBindingsWorker>::VisitCluster;
2522 using ClusterAnalysis::AddToWorkList;
2524 bool AddToWorkList(
const MemRegion *R);
2526 bool UpdatePostponed();
2527 void VisitBinding(SVal V);
2531 bool RemoveDeadBindingsWorker::AddToWorkList(
const MemRegion *R) {
2532 const MemRegion *BaseR = R->getBaseRegion();
2533 return AddToWorkList(WorkListElement(BaseR), getCluster(BaseR));
2536 void RemoveDeadBindingsWorker::VisitAddedToCluster(
const MemRegion *baseR,
2537 const ClusterBindings &C) {
2539 if (
const VarRegion *VR = dyn_cast<VarRegion>(baseR)) {
2540 if (SymReaper.isLive(VR))
2541 AddToWorkList(baseR, &C);
2546 if (
const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) {
2547 if (SymReaper.isLive(SR->getSymbol()))
2548 AddToWorkList(SR, &C);
2550 Postponed.push_back(SR);
2555 if (isa<NonStaticGlobalSpaceRegion>(baseR)) {
2556 AddToWorkList(baseR, &C);
2561 if (
const CXXThisRegion *TR = dyn_cast<CXXThisRegion>(baseR)) {
2562 const auto *StackReg =
2563 cast<StackArgumentsSpaceRegion>(TR->getSuperRegion());
2566 (RegCtx == CurrentLCtx || RegCtx->isParentOf(CurrentLCtx)))
2567 AddToWorkList(TR, &C);
2571 void RemoveDeadBindingsWorker::VisitCluster(
const MemRegion *baseR,
2572 const ClusterBindings *C) {
2578 if (
const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(baseR))
2579 SymReaper.markLive(SymR->getSymbol());
2581 for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I) {
2583 SymReaper.markElementIndicesLive(I.getKey().getRegion());
2585 VisitBinding(I.getData());
2589 void RemoveDeadBindingsWorker::VisitBinding(SVal V) {
2592 V.getAs<nonloc::LazyCompoundVal>()) {
2594 const RegionStoreManager::SValListTy &Vals = RM.getInterestingValues(*LCS);
2596 for (RegionStoreManager::SValListTy::const_iterator I = Vals.begin(),
2605 if (
const MemRegion *R = V.getAsRegion()) {
2607 SymReaper.markLive(R);
2610 if (
const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(R)) {
2611 BlockDataRegion::referenced_vars_iterator I = BR->referenced_vars_begin(),
2612 E = BR->referenced_vars_end();
2613 for ( ; I != E; ++I)
2614 AddToWorkList(I.getCapturedRegion());
2620 for (
auto SI = V.symbol_begin(), SE = V.symbol_end(); SI!=SE; ++SI)
2621 SymReaper.markLive(*SI);
2624 bool RemoveDeadBindingsWorker::UpdatePostponed() {
2627 bool Changed =
false;
2629 for (
auto I = Postponed.begin(), E = Postponed.end(); I != E; ++I) {
2630 if (
const SymbolicRegion *SR = *I) {
2631 if (SymReaper.isLive(SR->getSymbol())) {
2632 Changed |= AddToWorkList(SR);
2641 StoreRef RegionStoreManager::removeDeadBindings(
Store store,
2643 SymbolReaper& SymReaper) {
2644 RegionBindingsRef B = getRegionBindings(store);
2645 RemoveDeadBindingsWorker W(*
this, StateMgr, B, SymReaper, LCtx);
2646 W.GenerateClusters();
2650 E = SymReaper.region_end(); I != E; ++I) {
2651 W.AddToWorkList(*I);
2654 do W.RunWorkList();
while (W.UpdatePostponed());
2659 for (RegionBindingsRef::iterator I = B.begin(), E = B.end(); I != E; ++I) {
2660 const MemRegion *Base = I.getKey();
2664 if (!W.isVisited(Base))
2668 return StoreRef(B.asStore(), *
this);
2675 void RegionStoreManager::printJson(raw_ostream &Out,
Store S,
const char *NL,
2676 unsigned int Space,
bool IsDot)
const {
2677 RegionBindingsRef Bindings = getRegionBindings(S);
2679 Indent(Out, Space, IsDot) <<
"\"store\": ";
2681 if (Bindings.isEmpty()) {
2682 Out <<
"null," << NL;
2686 Out <<
"{ \"pointer\": \"" << Bindings.asStore() <<
"\", \"items\": [" << NL;
2687 Bindings.printJson(Out, NL, Space + 1, IsDot);
2688 Indent(Out, Space, IsDot) <<
"]}," << NL;
A (possibly-)qualified type.
static void getSymbolicOffsetFields(BindingKey K, FieldVector &Fields)
const internal::VariadicAllOfMatcher< Stmt > stmt
Matches statements.
bool operator==(CanQual< T > x, CanQual< U > y)
llvm::DenseSet< SymbolRef > InvalidatedSymbols
Specialize PointerLikeTypeTraits to allow LazyGenerationalUpdatePtr to be placed into a PointerUnion...
internal::Matcher< Stmt > StatementMatcher
QualType getPointeeType() const
If this is a pointer, ObjC object pointer, or block pointer, this returns the respective pointee...
IntrusiveRefCntPtr< const ProgramState > ProgramStateRef
static bool isRecordEmpty(const RecordDecl *RD)
unsigned getFieldIndex() const
Returns the index of this field within its record, as appropriate for passing to ASTRecordLayout::get...
const internal::ArgumentAdaptingMatcherFunc< internal::HasDescendantMatcher > hasDescendant
Matches AST nodes that have descendant AST nodes that match the provided matcher. ...
Represents an array type, per C99 6.7.5.2 - Array Declarators.
static 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.
const Expr * getAnyInitializer() const
Get the initializer for this variable, no matter which declaration it is attached to...
QualType getElementType() const
Represents a variable declaration or definition.
const void * Store
Store - This opaque type encapsulates an immutable mapping from locations to values.
const internal::VariadicDynCastAllOfMatcher< Decl, VarDecl > varDecl
Matches variable declarations.
std::unique_ptr< StoreManager > CreateFieldsOnlyRegionStoreManager(ProgramStateManager &StMgr)
Represents a struct/union/class.
llvm::ImmutableMap< BindingKey, SVal > ClusterBindings
SmallVector< const FieldDecl *, 8 > FieldVector
const SymExpr * SymbolRef
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
llvm::ImmutableList< SVal >::iterator iterator
RecordDecl * getDefinition() const
Returns the RecordDecl that actually defines this struct/union/class.
field_range fields() const
Represents a member of a struct/union/class.
static bool canSymbolicate(QualType T)
bool isReferenceType() const
i32 captured_struct **param SharedsTy A type which contains references the shared variables *param Shareds Context with the list of shared variables from the p *TaskFunction *param Data Additional data for task generation like final * state
bool isIntegralOrEnumerationType() const
Determine whether this type is an integral or enumeration type.
static bool isLocType(QualType T)
unsigned getLength() const
const internal::VariadicDynCastAllOfMatcher< Stmt, DeclRefExpr > declRefExpr
Matches expressions that refer to declarations.
CharUnits - This is an opaque type for sizes expressed in character units.
static void dump(llvm::raw_ostream &OS, StringRef FunctionName, ArrayRef< CounterExpression > Expressions, ArrayRef< CounterMappingRegion > Regions)
RegionSetTy::const_iterator region_iterator
llvm::ImmutableMap< const MemRegion *, ClusterBindings > RegionBindings
SmallVector< const MemRegion *, 8 > InvalidatedRegions
bool isScalarType() const
SmallVector< BoundNodes, 1 > match(MatcherT Matcher, const NodeT &Node, ASTContext &Context)
Returns the results of matching Matcher on Node.
std::unique_ptr< StoreManager > CreateRegionStoreManager(ProgramStateManager &StMgr)
CXXRecordDecl * getAsCXXRecordDecl() const
Retrieves the CXXRecordDecl that this type refers to, either because the type is a RecordType or beca...
static bool isCompatibleWithFields(BindingKey K, const FieldVector &Fields)
When applied to a MemSpaceRegion, indicates the entire memory space should be invalidated.
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.
This represents one expression.
GlobalsFilterKind
Used to determine which global regions are automatically included in the initial worklist of a Cluste...
bool hasLocalStorage() const
Returns true if a variable with function scope is a non-static local variable.
const T * castAs() const
Member-template castAs<specific type>.
__UINTPTR_TYPE__ uintptr_t
An unsigned integer type with the property that any valid pointer to void can be converted to this ty...
uint32_t getCodeUnit(size_t i) const
static CharUnits fromQuantity(QuantityType Quantity)
fromQuantity - Construct a CharUnits quantity from a raw integer type.
Represents a GCC generic vector type.
float __ovld __cnfn length(float p)
Return the length of vector p, i.e., sqrt(p.x2 + p.y 2 + ...)
bool isNull() const
Return true if this QualType doesn't point to a type yet.
llvm::ImmutableMapRef< BindingKey, SVal > ClusterBindingsRef
bool isConstQualified() const
Determine whether this type is const-qualified.
bool isVoidPointerType() const
Maps string IDs to AST nodes matched by parts of a matcher.
bool isStructureOrClassType() const
QualType getElementType() const
static QualType getUnderlyingType(const SubRegion *R)
Expr * getInClassInitializer() const
Get the C++11 default member initializer for this member, or null if one has not been set...
bool hasGlobalStorage() const
Returns true for all variables that do not have local storage.
bool isAnyPointerType() const
bool operator<(DeclarationName LHS, DeclarationName RHS)
Ordering on two declaration names.
bool isVectorType() const
Tells that a region's contents is not changed.
Dataflow Directional Tag Classes.
raw_ostream & operator<<(raw_ostream &Out, const CheckerBase &Checker)
Dump checker name to stream.
std::unique_ptr< DiagnosticConsumer > create(StringRef OutputFile, DiagnosticOptions *Diags, bool MergeChildRecords=false)
Returns a DiagnosticConsumer that serializes diagnostics to a bitcode file.
specific_decl_iterator - Iterates over a subrange of declarations stored in a DeclContext, providing only those that are of type SpecificDecl (or a class derived from it).
const Decl * getDecl() const
A helper class that allows the use of isa/cast/dyncast to detect TagType objects of structs/unions/cl...
const StackFrameContext * getStackFrame() const
std::pair< BindingKey, SVal > BindingPair
Stores options for the analyzer from the command line.
X
Add a minimal nested name specifier fixit hint to allow lookup of a tag name from an outer enclosing ...
__PTRDIFF_TYPE__ ptrdiff_t
A signed integer type that is the result of subtracting two pointers.
static bool isUnionField(const FieldRegion *FR)
Represents a C++ struct/union/class.
StringLiteral - This represents a string literal expression, e.g.
Defines the clang::TargetInfo interface.
unsigned getNumElements() const
raw_ostream & Indent(raw_ostream &Out, const unsigned int Space, bool IsDot)
const RegionBindingsRef & RegionBindingsConstRef
Represents the canonical version of C arrays with a specified constant size.