clang: /home/buildbot/as-worker-4/publish-doxygen-docs/llvm-project/clang/lib/StaticAnalyzer/Core/RegionStore.cpp (original) (raw)

This is a helper function for getConstantValFromConstArrayInitializer.

This is a helper function for getConstantValFromConstArrayInitializer.Convert array of offsets from SVal to uint64_t in consideration of respective array extents.

#include "llvm/ADT/ImmutableMap.h"

#include "llvm/ADT/STLExtras.h"

#include "llvm/Support/raw_ostream.h"

#include

#include

using namespace clang;

using namespace ento;

namespace {

class BindingKey {

public:

enum Kind { Default = 0x0, Direct = 0x1 };

private:

enum { Symbolic = 0x2 };

llvm::PointerIntPair<const MemRegion *, 2> P;

explicit BindingKey(const SubRegion *r, const SubRegion *Base, Kind k)

assert(r && Base && "Must have known regions.");

assert(getConcreteOffsetRegion() == Base && "Failed to store base region");

}

explicit BindingKey(const MemRegion *r, uint64_t offset, Kind k)

: P(r, k), Data(offset) {

assert(r && "Must have known regions.");

assert(getOffset() == offset && "Failed to store offset");

assert((r == r->getBaseRegion() ||

isa<ObjCIvarRegion, CXXDerivedObjectRegion>(r)) &&

"Not a base");

}

public:

bool isDirect() const { return P.getInt() & Direct; }

bool isDefault() const { return !isDirect(); }

bool hasSymbolicOffset() const { return P.getInt() & Symbolic; }

const MemRegion *getRegion() const { return P.getPointer(); }

uint64_t getOffset() const {

assert(!hasSymbolicOffset());

}

const SubRegion *getConcreteOffsetRegion() const {

assert(hasSymbolicOffset());

return reinterpret_cast<const SubRegion *>(static_cast<uintptr_t>(Data));

}

const MemRegion *getBaseRegion() const {

if (hasSymbolicOffset())

return getConcreteOffsetRegion()->getBaseRegion();

}

void Profile(llvm::FoldingSetNodeID& ID) const {

ID.AddPointer(P.getOpaqueValue());

}

static BindingKey Make(const MemRegion *R, Kind k);

bool operator<(const BindingKey &X) const {

if (P.getOpaqueValue() < X.P.getOpaqueValue())

return true;

if (P.getOpaqueValue() > X.P.getOpaqueValue())

return false;

return Data < X.Data;

}

bool operator==(const BindingKey &X) const {

return P.getOpaqueValue() == X.P.getOpaqueValue() &&

}

LLVM_DUMP_METHOD void dump() const;

};

}

BindingKey BindingKey::Make(const MemRegion *R, Kind k) {

const RegionOffset &RO = R->getAsOffset();

if (RO.hasSymbolicOffset())

return BindingKey(cast(R), cast(RO.getRegion()), k);

return BindingKey(RO.getRegion(), RO.getOffset(), k);

}

static inline raw_ostream &operator<<(raw_ostream &Out, BindingKey K) {

Out << "\"kind\": \"" << (K.isDirect() ? "Direct" : "Default")

<< "\", \"offset\": ";

if (!K.hasSymbolicOffset())

Out << K.getOffset();

else

Out << "null";

return Out;

}

}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

void BindingKey::dump() const { llvm::errs() << *this; }

#endif

typedef llvm::ImmutableMap<BindingKey, SVal> ClusterBindings;

typedef std::pair<BindingKey, SVal> BindingPair;

typedef llvm::ImmutableMap<const MemRegion *, ClusterBindings>

namespace {

class RegionBindingsRef : public llvm::ImmutableMapRef<const MemRegion *,

ClusterBindings> {

ClusterBindings::Factory *CBFactory;

bool IsMainAnalysis;

public:

typedef llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>

ParentTy;

RegionBindingsRef(ClusterBindings::Factory &CBFactory,

const RegionBindings::TreeTy *T,

RegionBindings::TreeTy::Factory *F,

bool IsMainAnalysis)

CBFactory(&CBFactory), IsMainAnalysis(IsMainAnalysis) {}

RegionBindingsRef(const ParentTy &P,

ClusterBindings::Factory &CBFactory,

bool IsMainAnalysis)

CBFactory(&CBFactory), IsMainAnalysis(IsMainAnalysis) {}

RegionBindingsRef add(key_type_ref K, data_type_ref D) const {

return RegionBindingsRef(static_cast<const ParentTy *>(this)->add(K, D),

*CBFactory, IsMainAnalysis);

}

RegionBindingsRef remove(key_type_ref K) const {

return RegionBindingsRef(static_cast<const ParentTy *>(this)->remove(K),

*CBFactory, IsMainAnalysis);

}

RegionBindingsRef addBinding(BindingKey K, SVal V) const;

RegionBindingsRef addBinding(const MemRegion *R,

BindingKey::Kind k, SVal V) const;

const SVal *lookup(BindingKey K) const;

const SVal *lookup(const MemRegion *R, BindingKey::Kind k) const;

using llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>::lookup;

RegionBindingsRef removeBinding(BindingKey K);

RegionBindingsRef removeBinding(const MemRegion *R,

BindingKey::Kind k);

RegionBindingsRef removeBinding(const MemRegion *R) {

return removeBinding(R, BindingKey::Direct).

removeBinding(R, BindingKey::Default);

}

std::optional getDirectBinding(const MemRegion *R) const;

std::optional getDefaultBinding(const MemRegion *R) const;

Store asStore() const {

llvm::PointerIntPair<Store, 1, bool> Ptr = {

asImmutableMap().getRootWithoutRetain(), IsMainAnalysis};

return reinterpret_cast<Store>(Ptr.getOpaqueValue());

}

bool isMainAnalysis() const {

return IsMainAnalysis;

}

void printJson(raw_ostream &Out, const char *NL = "\n",

unsigned int Space = 0, bool IsDot = false) const {

using namespace llvm;

DenseMap<const MemRegion *, std::string> StringifyCache;

auto ToString = [&StringifyCache](const MemRegion *R) {

auto [Place, Inserted] = StringifyCache.try_emplace(R);

if (!Inserted)

return Place->second;

std::string Res;

raw_string_ostream OS(Res);

OS << R;

Place->second = Res;

return Res;

};

using Cluster =

std::pair<const MemRegion *, ImmutableMap<BindingKey, SVal>>;

using Binding = std::pair<BindingKey, SVal>;

const auto MemSpaceBeforeRegionName = [&ToString](const Cluster *L,

const Cluster *R) {

if (isa(L->first) && !isa(R->first))

return true;

if (!isa(L->first) && isa(R->first))

return false;

return ToString(L->first) < ToString(R->first);

};

const auto SymbolicBeforeOffset = [&ToString](const BindingKey &L,

const BindingKey &R) {

if (L.hasSymbolicOffset() && !R.hasSymbolicOffset())

return true;

if (!L.hasSymbolicOffset() && R.hasSymbolicOffset())

return false;

if (L.hasSymbolicOffset() && R.hasSymbolicOffset())

return ToString(L.getRegion()) < ToString(R.getRegion());

return L.getOffset() < R.getOffset();

};

const auto DefaultBindingBeforeDirectBindings =

[&SymbolicBeforeOffset](const Binding *LPtr, const Binding *RPtr) {

const BindingKey &L = LPtr->first;

const BindingKey &R = RPtr->first;

if (L.isDefault() && !R.isDefault())

return true;

if (!L.isDefault() && R.isDefault())

return false;

assert(L.isDefault() == R.isDefault());

return SymbolicBeforeOffset(L, R);

};

const auto AddrOf = [](const auto &Item) { return &Item; };

std::vector<const Cluster *> SortedClusters;

SortedClusters.reserve(std::distance(begin(), end()));

append_range(SortedClusters, map_range(*this, AddrOf));

llvm::sort(SortedClusters, MemSpaceBeforeRegionName);

for (auto [Idx, C] : llvm::enumerate(SortedClusters)) {

const auto &[BaseRegion, Bindings] = *C;

Indent(Out, Space, IsDot)

<< "{ \"cluster\": \"" << BaseRegion << "\", \"pointer\": \""

<< (const void *)BaseRegion << "\", \"items\": [" << NL;

std::vector<const Binding *> SortedBindings;

SortedBindings.reserve(std::distance(Bindings.begin(), Bindings.end()));

append_range(SortedBindings, map_range(Bindings, AddrOf));

llvm::sort(SortedBindings, DefaultBindingBeforeDirectBindings);

++Space;

for (auto [Idx, B] : llvm::enumerate(SortedBindings)) {

const auto &[Key, Value] = *B;

Indent(Out, Space, IsDot) << "{ " << Key << ", \"value\": ";

Value.printJson(Out, true);

Out << " }";

if (Idx != SortedBindings.size() - 1)

Out << ',';

Out << NL;

}

--Space;

Indent(Out, Space, IsDot) << "]}";

if (Idx != SortedClusters.size() - 1)

Out << ',';

Out << NL;

}

}

LLVM_DUMP_METHOD void dump() const { printJson(llvm::errs()); }

};

}

std::optional

RegionBindingsRef::getDirectBinding(const MemRegion *R) const {

const SVal *V = lookup(R, BindingKey::Direct);

return V ? std::optional(*V) : std::nullopt;

}

std::optional

RegionBindingsRef::getDefaultBinding(const MemRegion *R) const {

const SVal *V = lookup(R, BindingKey::Default);

return V ? std::optional(*V) : std::nullopt;

}

RegionBindingsRef RegionBindingsRef::addBinding(BindingKey K, SVal V) const {

const MemRegion *Base = K.getBaseRegion();

(ExistingCluster ? *ExistingCluster : CBFactory->getEmptyMap());

return add(Base, NewCluster);

}

RegionBindingsRef RegionBindingsRef::addBinding(const MemRegion *R,

BindingKey::Kind k,

SVal V) const {

return addBinding(BindingKey::Make(R, k), V);

}

const SVal *RegionBindingsRef::lookup(BindingKey K) const {

if (!Cluster)

return nullptr;

return Cluster->lookup(K);

}

const SVal *RegionBindingsRef::lookup(const MemRegion *R,

BindingKey::Kind k) const {

return lookup(BindingKey::Make(R, k));

}

RegionBindingsRef RegionBindingsRef::removeBinding(BindingKey K) {

const MemRegion *Base = K.getBaseRegion();

if (!Cluster)

return *this;

if (NewCluster.isEmpty())

return add(Base, NewCluster);

}

RegionBindingsRef RegionBindingsRef::removeBinding(const MemRegion *R,

BindingKey::Kind k){

return removeBinding(BindingKey::Make(R, k));

}

namespace {

class InvalidateRegionsWorker;

class RegionStoreManager : public StoreManager {

public:

RegionBindings::Factory RBFactory;

mutable ClusterBindings::Factory CBFactory;

typedef std::vector SValListTy;

private:

typedef llvm::DenseMap<const LazyCompoundValData *,

SValListTy> LazyBindingsMapTy;

LazyBindingsMapTy LazyBindingsMap;

unsigned SmallStructLimit;

unsigned SmallArrayLimit;

void populateWorkList(InvalidateRegionsWorker &W,

InvalidatedRegions *TopLevelRegions);

public:

RegionStoreManager(ProgramStateManager &mgr)

: StoreManager(mgr), RBFactory(mgr.getAllocator()),

CBFactory(mgr.getAllocator()), SmallStructLimit(0), SmallArrayLimit(0) {

ExprEngine &Eng = StateMgr.getOwningEngine();

SmallStructLimit = Options.RegionStoreSmallStructLimit;

SmallArrayLimit = Options.RegionStoreSmallArrayLimit;

}

SVal ArrayToPointer(Loc Array, QualType ElementTy) override;

StoreRef getInitialStore(const LocationContext *InitLoc) override {

bool IsMainAnalysis = false;

if (const auto *FD = dyn_cast(InitLoc->getDecl()))

IsMainAnalysis = FD->isMain() && !Ctx.getLangOpts().CPlusPlus;

return StoreRef(RegionBindingsRef(

RegionBindingsRef::ParentTy(RBFactory.getEmptyMap(), RBFactory),

CBFactory, IsMainAnalysis).asStore(), *this);

}

RegionBindingsRef invalidateGlobalRegion(MemRegion::Kind K, const Stmt *S,

unsigned Count,

RegionBindingsRef B,

InvalidatedRegions *Invalidated);

StoreRef invalidateRegions(Store store, ArrayRef Values, const Stmt *S,

const CallEvent *Call, InvalidatedSymbols &IS,

RegionAndSymbolInvalidationTraits &ITraits,

InvalidatedRegions *Invalidated,

InvalidatedRegions *InvalidatedTopLevel) override;

bool scanReachableSymbols(Store S, const MemRegion *R,

ScanReachableSymbols &Callbacks) override;

const SubRegion *R);

std::optional

const ElementRegion *R);

std::optional

SVal getSValFromStringLiteral(const StringLiteral *SL, uint64_t Offset,

public:

StoreRef Bind(Store store, Loc LV, SVal V) override {

return StoreRef(bind(getRegionBindings(store), LV, V).asStore(), *this);

}

StoreRef BindDefaultInitial(Store store, const MemRegion *R,

SVal V) override {

RegionBindingsRef B = getRegionBindings(store);

assert(!(B.getDefaultBinding(R) || B.getDirectBinding(R)) &&

"Double initialization!");

B = B.addBinding(BindingKey::Make(R, BindingKey::Default), V);

return StoreRef(B.asImmutableMap().getRootWithoutRetain(), *this);

}

StoreRef BindDefaultZero(Store store, const MemRegion *R) override {

if (const auto *BR = dyn_cast(R))

if (BR->getDecl()->isEmpty())

return StoreRef(store, *this);

RegionBindingsRef B = getRegionBindings(store);

SVal V = svalBuilder.makeZeroVal(Ctx.CharTy);

B = removeSubRegionBindings(B, cast(R));

B = B.addBinding(BindingKey::Make(R, BindingKey::Default), V);

return StoreRef(B.asImmutableMap().getRootWithoutRetain(), *this);

}

std::optional

const RecordDecl *RD, nonloc::LazyCompoundVal LCV);

const TypedValueRegion* R, SVal V);

const TypedValueRegion* R, SVal V);

std::optional

const ArrayType *AT, nonloc::LazyCompoundVal LCV);

const TypedValueRegion* R,

SVal V);

const TypedRegion *R,

SVal DefaultVal);

StoreRef killBinding(Store ST, Loc L) override;

void incrementReferenceCount(Store store) override {

getRegionBindings(store).manualRetain();

}

void decrementReferenceCount(Store store) override {

getRegionBindings(store).manualRelease();

}

bool includedInBindings(Store store, const MemRegion *region) const override;

SVal getBinding(Store S, Loc L, QualType T) override {

return getBinding(getRegionBindings(S), L, T);

}

const TypedValueRegion *R) const;

std::optional

getUniqueDefaultBinding(nonloc::LazyCompoundVal LCV) const;

std::optional getDefaultBinding(Store S, const MemRegion *R) override {

RegionBindingsRef B = getRegionBindings(S);

return B.getDefaultBinding(R->getBaseRegion());

}

SVal getBindingForLazySymbol(const TypedValueRegion *R);

const TypedValueRegion *R,

SVal getLazyBinding(const SubRegion *LazyBindingRegion,

RegionBindingsRef LazyBinding);

std::optional

const MemRegion *superR,

const TypedValueRegion *R, QualType Ty);

std::pair<Store, const SubRegion *>

const SubRegion *originalRegion);

const SValListTy &getInterestingValues(nonloc::LazyCompoundVal LCV);

StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx,

SymbolReaper& SymReaper) override;

RegionBindingsRef getRegionBindings(Store store) const {

llvm::PointerIntPair<Store, 1, bool> Ptr;

Ptr.setFromOpaqueValue(const_cast<void *>(store));

return RegionBindingsRef(

CBFactory,

static_cast<const RegionBindings::TreeTy *>(Ptr.getPointer()),

RBFactory.getTreeFactory(),

Ptr.getInt());

}

void printJson(raw_ostream &Out, Store S, const char *NL = "\n",

unsigned int Space = 0, bool IsDot = false) const override;

void iterBindings(Store store, BindingsHandler& f) override {

RegionBindingsRef B = getRegionBindings(store);

for (const auto &[Region, Cluster] : B) {

for (const auto &[Key, Value] : Cluster) {

if (!Key.isDirect())

continue;

if (const SubRegion *R = dyn_cast(Key.getRegion())) {

if (!f.HandleBinding(*this, store, R, Value))

return;

}

}

}

}

};

}

std::unique_ptr

ento::CreateRegionStoreManager(ProgramStateManager &StMgr) {

return std::make_unique(StMgr);

}

namespace {

enum GlobalsFilterKind {

GFK_None,

GFK_SystemOnly,

GFK_All

};

template

class ClusterAnalysis {

protected:

typedef llvm::DenseMap<const MemRegion *, const ClusterBindings *> ClusterMap;

typedef const MemRegion * WorkListElement;

WorkList WL;

RegionStoreManager &RM;

SValBuilder &svalBuilder;

RegionBindingsRef B;

protected:

return B.lookup(R);

}

bool includeEntireMemorySpace(const MemRegion *Base) {

return false;

}

public:

ClusterAnalysis(RegionStoreManager &rm, ProgramStateManager &StateMgr,

RegionBindingsRef b)

: RM(rm), Ctx(StateMgr.getContext()),

svalBuilder(StateMgr.getSValBuilder()), B(std::move(b)) {}

RegionBindingsRef getRegionBindings() const { return B; }

bool isVisited(const MemRegion *R) {

return Visited.count(getCluster(R));

}

void GenerateClusters() {

for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end();

RI != RE; ++RI){

const MemRegion *Base = RI.getKey();

assert(!Cluster.isEmpty() && "Empty clusters should be removed");

static_cast<DERIVED*>(this)->VisitAddedToCluster(Base, Cluster);

if (static_cast<DERIVED*>(this)->includeEntireMemorySpace(Base))

AddToWorkList(WorkListElement(Base), &Cluster);

}

}

bool AddToWorkList(WorkListElement E, const ClusterBindings *C) {

if (C && .insert(C).second)

return false;

WL.push_back(E);

return true;

}

bool AddToWorkList(const MemRegion *R) {

return static_cast<DERIVED*>(this)->AddToWorkList(R);

}

void RunWorkList() {

while (!WL.empty()) {

WorkListElement E = WL.pop_back_val();

const MemRegion *BaseR = E;

static_cast<DERIVED*>(this)->VisitCluster(BaseR, getCluster(BaseR));

}

}

void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C) {}

void VisitCluster(const MemRegion *baseR, const ClusterBindings *C) {}

void VisitCluster(const MemRegion *BaseR, const ClusterBindings *C,

bool Flag) {

static_cast<DERIVED*>(this)->VisitCluster(BaseR, C);

}

};

}

bool RegionStoreManager::scanReachableSymbols(Store S, const MemRegion *R,

ScanReachableSymbols &Callbacks) {

assert(R == R->getBaseRegion() && "Should only be called for base regions");

RegionBindingsRef B = getRegionBindings(S);

if (!Cluster)

return true;

for (ClusterBindings::iterator RI = Cluster->begin(), RE = Cluster->end();

RI != RE; ++RI) {

if (!Callbacks.scan(RI.getData()))

return false;

}

return true;

}

static inline bool isUnionField(const FieldRegion *FR) {

return FR->getDecl()->getParent()->isUnion();

}

assert(K.hasSymbolicOffset() && "Not implemented for concrete offset keys");

const MemRegion *Base = K.getConcreteOffsetRegion();

const MemRegion *R = K.getRegion();

while (R != Base) {

if (const FieldRegion *FR = dyn_cast(R))

Fields.push_back(FR->getDecl());

R = cast(R)->getSuperRegion();

}

}

assert(K.hasSymbolicOffset() && "Not implemented for concrete offset keys");

if (Fields.empty())

return true;

ptrdiff_t Delta = FieldsInBindingKey.size() - Fields.size();

if (Delta >= 0)

return std::equal(FieldsInBindingKey.begin() + Delta,

FieldsInBindingKey.end(),

Fields.begin());

else

return std::equal(FieldsInBindingKey.begin(), FieldsInBindingKey.end(),

Fields.begin() - Delta);

}

static void

const SubRegion *Top, BindingKey TopKey,

bool IncludeAllDefaultBindings) {

if (TopKey.hasSymbolicOffset()) {

Top = TopKey.getConcreteOffsetRegion();

TopKey = BindingKey::Make(Top, BindingKey::Default);

}

SVal Extent = Top->getMemRegionManager().getStaticSize(Top, SVB);

if (std::optionalnonloc::ConcreteInt ExtentCI =

Extent.getAsnonloc::ConcreteInt()) {

const llvm::APSInt &ExtentInt = ExtentCI->getValue();

assert(ExtentInt.isNonNegative() || ExtentInt.isUnsigned());

Length = ExtentInt.getLimitedValue() * SVB.getContext().getCharWidth();

} else if (const FieldRegion *FR = dyn_cast(Top)) {

if (FR->getDecl()->isBitField())

Length = FR->getDecl()->getBitWidthValue();

}

for (const auto &StoreEntry : Cluster) {

BindingKey NextKey = StoreEntry.first;

if (NextKey.getRegion() == TopKey.getRegion()) {

if (NextKey.getOffset() > TopKey.getOffset() &&

NextKey.getOffset() - TopKey.getOffset() < Length) {

} else if (NextKey.getOffset() == TopKey.getOffset()) {

if (IncludeAllDefaultBindings || NextKey.isDirect())

}

} else if (NextKey.hasSymbolicOffset()) {

const MemRegion *Base = NextKey.getConcreteOffsetRegion();

if (Top->isSubRegionOf(Base) && Top != Base) {

if (IncludeAllDefaultBindings || NextKey.isDirect())

} else if (const SubRegion *BaseSR = dyn_cast(Base)) {

if (BaseSR->isSubRegionOf(Top))

}

}

}

}

static void

const SubRegion *Top, bool IncludeAllDefaultBindings) {

BindingKey::Make(Top, BindingKey::Default),

IncludeAllDefaultBindings);

}

RegionBindingsRef

const SubRegion *Top) {

BindingKey TopKey = BindingKey::Make(Top, BindingKey::Default);

const MemRegion *ClusterHead = TopKey.getBaseRegion();

if (Top == ClusterHead) {

return B.remove(Top);

}

if (!Cluster) {

if (TopKey.hasSymbolicOffset()) {

const SubRegion *Concrete = TopKey.getConcreteOffsetRegion();

return B.addBinding(Concrete, BindingKey::Default, UnknownVal());

}

return B;

}

false);

for (BindingKey Key : llvm::make_first_range(Bindings))

Result = Result.remove(Key);

if (TopKey.hasSymbolicOffset()) {

const SubRegion *Concrete = TopKey.getConcreteOffsetRegion();

Result = Result.add(BindingKey::Make(Concrete, BindingKey::Default),

UnknownVal());

}

if (Result.isEmpty())

return B.remove(ClusterHead);

return B.add(ClusterHead, Result.asImmutableMap());

}

namespace {

class InvalidateRegionsWorker : public ClusterAnalysis

{

unsigned Count;

RegionAndSymbolInvalidationTraits &ITraits;

StoreManager::InvalidatedRegions *Regions;

GlobalsFilterKind GlobalsFilter;

public:

InvalidateRegionsWorker(RegionStoreManager &rm, ProgramStateManager &stateMgr,

RegionBindingsRef b, const Stmt *S, unsigned count,

RegionAndSymbolInvalidationTraits &ITraitsIn,

StoreManager::InvalidatedRegions *r,

GlobalsFilterKind GFK)

: ClusterAnalysis(rm, stateMgr, b), S(S),

Count(count), LCtx(lctx), IS(is), ITraits(ITraitsIn), Regions(r),

GlobalsFilter(GFK) {}

void VisitCluster(const MemRegion *baseR, const ClusterBindings *C);

void VisitBinding(SVal V);

using ClusterAnalysis::AddToWorkList;

bool AddToWorkList(const MemRegion *R);

bool includeEntireMemorySpace(const MemRegion *Base);

bool isInitiallyIncludedGlobalRegion(const MemRegion *R);

};

}

bool InvalidateRegionsWorker::AddToWorkList(const MemRegion *R) {

bool doNotInvalidateSuperRegion = ITraits.hasTrait(

R, RegionAndSymbolInvalidationTraits::TK_DoNotInvalidateSuperRegion);

const MemRegion *BaseR = doNotInvalidateSuperRegion ? R : R->getBaseRegion();

return AddToWorkList(WorkListElement(BaseR), getCluster(BaseR));

}

void InvalidateRegionsWorker::VisitBinding(SVal V) {

if (SymbolRef Sym = V.getAsSymbol())

IS.insert(Sym);

if (const MemRegion *R = V.getAsRegion()) {

AddToWorkList(R);

return;

}

if (std::optionalnonloc::LazyCompoundVal LCS =

V.getAsnonloc::LazyCompoundVal()) {

for (SVal V : RM.getInterestingValues(*LCS))

if (!isanonloc::LazyCompoundVal(V))

VisitBinding(V);

return;

}

}

void InvalidateRegionsWorker::VisitCluster(const MemRegion *baseR,

bool PreserveRegionsContents =

ITraits.hasTrait(baseR,

RegionAndSymbolInvalidationTraits::TK_PreserveContents);

if (C) {

for (SVal Val : llvm::make_second_range(*C))

VisitBinding(Val);

if (!PreserveRegionsContents)

B = B.remove(baseR);

}

if (const auto *TO = dyn_cast(baseR)) {

if (const auto *RD = TO->getValueType()->getAsCXXRecordDecl()) {

if (RD->isLambda() && RD->getLambdaCallOperator()->getBody()) {

using namespace ast_matchers;

const char *DeclBind = "DeclBind";

to(varDecl(hasStaticStorageDuration()).bind(DeclBind)))));

auto Matches =

match(RefToStatic, *RD->getLambdaCallOperator()->getBody(),

RD->getASTContext());

auto *VD = Match.getNodeAs<VarDecl>(DeclBind);

const VarRegion *ToInvalidate =

RM.getRegionManager().getVarRegion(VD, LCtx);

AddToWorkList(ToInvalidate);

}

}

}

}

if (const BlockDataRegion *BR = dyn_cast(baseR)) {

for (auto Var : BR->referenced_vars()) {

const VarRegion *VR = Var.getCapturedRegion();

const VarDecl *VD = VR->getDecl();

AddToWorkList(VR);

}

else if (Loc::isLocType(VR->getValueType())) {

SVal V = RM.getBinding(B, loc::MemRegionVal(VR));

if (std::optional L = V.getAs<Loc>()) {

if (const MemRegion *LR = L->getAsRegion())

AddToWorkList(LR);

}

}

}

return;

}

if (const SymbolicRegion *SR = dyn_cast(baseR))

IS.insert(SR->getSymbol());

if (PreserveRegionsContents)

return;

if (Regions)

Regions->push_back(baseR);

if (isa<AllocaRegion, SymbolicRegion>(baseR)) {

DefinedOrUnknownSVal V =

svalBuilder.conjureSymbolVal(baseR, S, LCtx, Ctx.IntTy, Count);

B = B.addBinding(baseR, BindingKey::Default, V);

return;

}

if (!baseR->isBoundable())

return;

const TypedValueRegion *TR = cast(baseR);

if (isInitiallyIncludedGlobalRegion(baseR)) {

return;

}

DefinedOrUnknownSVal V =

svalBuilder.conjureSymbolVal(baseR, S, LCtx, Ctx.IntTy, Count);

B = B.addBinding(baseR, BindingKey::Default, V);

return;

}

if (const ArrayType *AT = Ctx.getAsArrayType(T)) {

bool doNotInvalidateSuperRegion = ITraits.hasTrait(

baseR,

RegionAndSymbolInvalidationTraits::TK_DoNotInvalidateSuperRegion);

if (doNotInvalidateSuperRegion) {

std::optional<uint64_t> NumElements;

NumElements = CAT->getZExtSize();

if (!NumElements)

goto conjure_default;

QualType ElementTy = AT->getElementType();

uint64_t ElemSize = Ctx.getTypeSize(ElementTy);

const RegionOffset &RO = baseR->getAsOffset();

const MemRegion *SuperR = baseR->getBaseRegion();

if (RO.hasSymbolicOffset()) {

if (SuperR)

AddToWorkList(SuperR);

goto conjure_default;

}

uint64_t LowerOffset = RO.getOffset();

uint64_t UpperOffset = LowerOffset + *NumElements * ElemSize;

bool UpperOverflow = UpperOffset < LowerOffset;

if (!SuperR)

goto conjure_default;

if (!C)

goto conjure_default;

for (const auto &[BK, V] : *C) {

std::optional<uint64_t> ROffset =

BK.hasSymbolicOffset() ? std::optional<uint64_t>() : BK.getOffset();

if (!ROffset ||

((*ROffset >= LowerOffset && *ROffset < UpperOffset) ||

(UpperOverflow &&

(*ROffset >= LowerOffset || *ROffset < UpperOffset)) ||

(LowerOffset == UpperOffset && *ROffset == LowerOffset))) {

B = B.removeBinding(BK);

const MemRegion *R = V.getAsRegion();

if (isa_and_nonnull(R))

VisitBinding(V);

}

}

}

conjure_default:

DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(

baseR, S, LCtx, AT->getElementType(), Count);

B = B.addBinding(baseR, BindingKey::Default, V);

return;

}

DefinedOrUnknownSVal V =

svalBuilder.conjureSymbolVal(baseR, S, LCtx, T, Count);

assert(SymbolManager::canSymbolicate(T) || V.isUnknown());

B = B.addBinding(baseR, BindingKey::Direct, V);

}

bool InvalidateRegionsWorker::isInitiallyIncludedGlobalRegion(

const MemRegion *R) {

switch (GlobalsFilter) {

case GFK_None:

return false;

case GFK_SystemOnly:

return isa(R->getMemorySpace());

case GFK_All:

return isa(R->getMemorySpace());

}

llvm_unreachable("unknown globals filter");

}

bool InvalidateRegionsWorker::includeEntireMemorySpace(const MemRegion *Base) {

if (isInitiallyIncludedGlobalRegion(Base))

return true;

const MemSpaceRegion *MemSpace = Base->getMemorySpace();

return ITraits.hasTrait(MemSpace,

RegionAndSymbolInvalidationTraits::TK_EntireMemSpace);

}

RegionBindingsRef RegionStoreManager::invalidateGlobalRegion(

MemRegion::Kind K, const Stmt *S, unsigned Count,

InvalidatedRegions *Invalidated) {

const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion(K);

SVal V =

svalBuilder.conjureSymbolVal( (const void *)GS, S, LCtx,

Ctx.IntTy, Count);

B = B.removeBinding(GS)

.addBinding(BindingKey::Make(GS, BindingKey::Default), V);

if (Invalidated)

Invalidated->push_back(GS);

return B;

}

void RegionStoreManager::populateWorkList(InvalidateRegionsWorker &W,

InvalidatedRegions *TopLevelRegions) {

for (SVal V : Values) {

if (auto LCS = V.getAsnonloc::LazyCompoundVal()) {

for (SVal S : getInterestingValues(*LCS))

if (const MemRegion *R = S.getAsRegion())

W.AddToWorkList(R);

continue;

}

if (const MemRegion *R = V.getAsRegion()) {

if (TopLevelRegions)

TopLevelRegions->push_back(R);

W.AddToWorkList(R);

continue;

}

}

}

StoreRef RegionStoreManager::invalidateRegions(

RegionAndSymbolInvalidationTraits &ITraits,

InvalidatedRegions *TopLevelRegions, InvalidatedRegions *Invalidated) {

GlobalsFilterKind GlobalsFilter;

if (Call->isInSystemHeader())

GlobalsFilter = GFK_SystemOnly;

else

GlobalsFilter = GFK_All;

} else {

GlobalsFilter = GFK_None;

}

RegionBindingsRef B = getRegionBindings(store);

InvalidateRegionsWorker W(*this, StateMgr, B, S, Count, LCtx, IS, ITraits,

Invalidated, GlobalsFilter);

W.GenerateClusters();

populateWorkList(W, Values, TopLevelRegions);

W.RunWorkList();

B = W.getRegionBindings();

switch (GlobalsFilter) {

case GFK_All:

B = invalidateGlobalRegion(MemRegion::GlobalInternalSpaceRegionKind, S,

Count, LCtx, B, Invalidated);

[[fallthrough]];

case GFK_SystemOnly:

B = invalidateGlobalRegion(MemRegion::GlobalSystemSpaceRegionKind, S, Count,

LCtx, B, Invalidated);

[[fallthrough]];

case GFK_None:

break;

}

return StoreRef(B.asStore(), *this);

}

SVal RegionStoreManager::ArrayToPointer(Loc Array, QualType T) {

if (isaloc::ConcreteInt(Array))

return Array;

if (!isaloc::MemRegionVal(Array))

return UnknownVal();

const SubRegion *R =

cast(Array.castAsloc::MemRegionVal().getRegion());

NonLoc ZeroIdx = svalBuilder.makeZeroArrayIndex();

return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, R, Ctx));

}

assert(!isa(L) && "location unknown");

assert(!isa(L) && "location undefined");

if (L.getAsloc::ConcreteInt()) {

return UnknownVal();

}

if (!L.getAsloc::MemRegionVal()) {

return UnknownVal();

}

const MemRegion *MR = L.castAsloc::MemRegionVal().getRegion();

if (isa(MR)) {

return UnknownVal();

}

if (T.isNull()) {

if (const auto *TVR = dyn_cast(MR))

T = TVR->getValueType();

else if (const auto *TR = dyn_cast(MR))

else if (const auto *SR = dyn_cast(MR))

T = SR->getPointeeStaticType();

}

assert(.isNull() && "Unable to auto-detect binding type!");

assert(->isVoidType() && "Attempting to dereference a void pointer!");

if (!isa(MR))

MR = GetElementZeroRegion(cast(MR), T);

const TypedValueRegion *R = cast(MR);

QualType RTy = R->getValueType();

return UnknownVal();

return getBindingForStruct(B, R);

return createLazyBinding(B, R);

return getBindingForArray(B, R);

else

return UnknownVal();

}

return UnknownVal();

if (const FieldRegion* FR = dyn_cast(R))

return svalBuilder.evalCast(getBindingForField(B, FR), T, QualType{});

if (const ElementRegion* ER = dyn_cast(R)) {

return svalBuilder.evalCast(getBindingForElement(B, ER), T, QualType{});

}

if (const ObjCIvarRegion *IVR = dyn_cast(R)) {

return svalBuilder.evalCast(getBindingForObjCIvar(B, IVR), T, QualType{});

}

if (const VarRegion *VR = dyn_cast(R)) {

return svalBuilder.evalCast(getBindingForVar(B, VR), T, QualType{});

}

const SVal *V = B.lookup(R, BindingKey::Direct);

if (V)

return *V;

if (R->hasStackNonParametersStorage()) {

return UndefinedVal();

}

return svalBuilder.getRegionValueSymbolVal(R);

}

if (const TypedValueRegion *TVR = dyn_cast(R))

RegionTy = TVR->getValueType();

if (const SymbolicRegion *SR = dyn_cast(R))

RegionTy = SR->getSymbol()->getType();

return RegionTy;

}

static std::optionalnonloc::LazyCompoundVal

const SubRegion *R, bool AllowSubregionBindings) {

std::optional V = B.getDefaultBinding(R);

if ()

return std::nullopt;

std::optionalnonloc::LazyCompoundVal LCV =

V->getAsnonloc::LazyCompoundVal();

if (!LCV)

return std::nullopt;

if (!RegionTy.isNull() &&

QualType SourceRegionTy = LCV->getRegion()->getValueType();

if (!SVB.getContext().hasSameUnqualifiedType(RegionTy, SourceRegionTy))

return std::nullopt;

}

if (!AllowSubregionBindings) {

true);

return std::nullopt;

}

return *LCV;

}

std::pair<Store, const SubRegion *>

const SubRegion *R,

const SubRegion *originalRegion) {

if (originalRegion != R) {

if (std::optionalnonloc::LazyCompoundVal V =

return std::make_pair(V->getStore(), V->getRegion());

}

typedef std::pair<Store, const SubRegion *> StoreRegionPair;

StoreRegionPair Result = StoreRegionPair();

if (const ElementRegion *ER = dyn_cast(R)) {

Result = findLazyBinding(B, cast(ER->getSuperRegion()),

originalRegion);

if (Result.second)

Result.second = MRMgr.getElementRegionWithSuper(ER, Result.second);

} else if (const FieldRegion *FR = dyn_cast(R)) {

Result = findLazyBinding(B, cast(FR->getSuperRegion()),

originalRegion);

if (Result.second)

Result.second = MRMgr.getFieldRegionWithSuper(FR, Result.second);

} else if (const CXXBaseObjectRegion *BaseReg =

dyn_cast(R)) {

Result = findLazyBinding(B, cast(BaseReg->getSuperRegion()),

originalRegion);

if (Result.second)

Result.second = MRMgr.getCXXBaseObjectRegionWithSuper(BaseReg,

Result.second);

}

return Result;

}

assert(CAT && "ConstantArrayType should not be null");

do {

} while ((CAT = dyn_cast(CAT->getElementType())));

return Extents;

}

static std::pair<SmallVector<SVal, 2>, const MemRegion *>

assert(ER && "ConstantArrayType should not be null");

const MemRegion *Base;

do {

SValOffsets.push_back(ER->getIndex());

Base = ER->getSuperRegion();

ER = dyn_cast(Base);

} while (ER);

return {SValOffsets, Base};

}

static std::optional

DstOffsets.resize(SrcOffsets.size());

auto ExtentIt = ArrayExtents.begin();

auto OffsetIt = DstOffsets.begin();

for (SVal V : llvm::reverse(SrcOffsets)) {

if (auto CI = V.getAsnonloc::ConcreteInt()) {

const llvm::APSInt &Offset = CI->getValue();

if (Offset.isNegative() || Offset.uge(*(ExtentIt++)))

return UndefinedVal();

*(OffsetIt++) = Offset.getZExtValue();

continue;

}

return UnknownVal();

}

return std::nullopt;

}

std::optional RegionStoreManager::getConstantValFromConstArrayInitializer(

assert(R && "ElementRegion should not be null");

const MemRegion *Base;

const VarRegion *VR = dyn_cast(Base);

if (!VR)

return std::nullopt;

assert(!SValOffsets.empty() && "getElementRegionOffsets guarantees the "

"offsets vector is not empty.");

const VarDecl *VD = VR->getDecl();

!R->getElementType().isConstQualified() &&

return std::nullopt;

if (!Init)

return std::nullopt;

if (!CAT)

return std::nullopt;

if (SValOffsets.size() != Extents.size())

return std::nullopt;

SValOffsets, Extents, ConcreteOffsets))

return *V;

if (const auto *ILE = dyn_cast(Init))

return getSValFromInitListExpr(ILE, ConcreteOffsets, R->getElementType());

if (const auto *SL = dyn_cast(Init))

return getSValFromStringLiteral(SL, ConcreteOffsets.front(),

R->getElementType());

return std::nullopt;

}

std::optional RegionStoreManager::getSValFromInitListExpr(

assert(ILE && "InitListExpr should not be null");

for (uint64_t Offset : Offsets) {

if (const auto *SL = dyn_cast(ILE->getInit(0)))

return getSValFromStringLiteral(SL, Offset, ElemT);

return svalBuilder.makeZeroVal(ElemT);

const auto *IL = dyn_cast(E);

if (!IL)

return svalBuilder.getConstantVal(E);

ILE = IL;

}

assert(ILE);

return std::nullopt;

}

SVal RegionStoreManager::getSValFromStringLiteral(const StringLiteral *SL,

uint64_t Offset,

assert(SL && "StringLiteral should not be null");

return svalBuilder.makeIntVal(Code, ElemT);

}

const TypedValueRegion *SubReg, const ASTContext &Ctx, SValBuilder &SVB) {

assert(BaseRegion);

QualType BaseTy = BaseRegion->getValueType();

QualType Ty = SubReg->getValueType();

if (Ctx.getTypeSizeInChars(BaseTy) >= Ctx.getTypeSizeInChars(Ty)) {

if (const std::optional &ParentValue =

B.getDirectBinding(BaseRegion)) {

if (SymbolRef ParentValueAsSym = ParentValue->getAsSymbol())

return SVB.getDerivedRegionValueSymbolVal(ParentValueAsSym, SubReg);

if (ParentValue->isUndef())

return UndefinedVal();

return UnknownVal();

}

}

}

return std::nullopt;

}

const ElementRegion* R) {

if (const std::optional &V = B.getDirectBinding(R))

return *V;

const MemRegion* superR = R->getSuperRegion();

if (const StringRegion *StrR = dyn_cast(superR)) {

QualType T = Ctx.getAsArrayType(StrR->getValueType())->getElementType();

if (!Ctx.hasSameUnqualifiedType(T, R->getElementType()))

return UnknownVal();

if (const auto CI = R->getIndex().getAsnonloc::ConcreteInt()) {

const llvm::APSInt &Idx = CI->getValue();

if (Idx < 0)

return UndefinedVal();

return getSValFromStringLiteral(SL, Idx.getZExtValue(), T);

}

} else if (isa<ElementRegion, VarRegion>(superR)) {

if (std::optional V = getConstantValFromConstArrayInitializer(B, R))

return *V;

}

if (isa(superR))

return UnknownVal();

const RegionRawOffset &O = R->getAsArrayOffset();

if (!O.getRegion())

return UnknownVal();

if (const TypedValueRegion *baseR = dyn_cast(O.getRegion()))

return *V;

return getBindingForFieldOrElementCommon(B, R, R->getElementType());

}

const FieldRegion* R) {

if (const std::optional &V = B.getDirectBinding(R))

return *V;

const MemRegion* superR = R->getSuperRegion();

if (const auto *VR = dyn_cast(superR)) {

const VarDecl *VD = VR->getDecl();

if (const auto *InitList = dyn_cast(Init)) {

if (Index < InitList->getNumInits()) {

if (const Expr *FieldInit = InitList->getInit(Index))

if (std::optional V = svalBuilder.getConstantVal(FieldInit))

return *V;

} else {

return svalBuilder.makeZeroVal(Ty);

}

}

}

if (const auto *Base = dyn_cast(R->getBaseRegion()))

return *V;

return getBindingForFieldOrElementCommon(B, R, Ty);

}

std::optional RegionStoreManager::getBindingForDerivedDefaultValue(

const TypedValueRegion *R, QualType Ty) {

if (const std::optional &D = B.getDefaultBinding(superR)) {

SVal val = *D;

if (SymbolRef parentSym = val.getAsSymbol())

return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);

if (val.isZeroConstant())

return svalBuilder.makeZeroVal(Ty);

if (val.isUnknownOrUndef())

return val;

if (isa<nonloc::LazyCompoundVal, nonloc::CompoundVal>(val))

return val;

llvm_unreachable("Unknown default value");

}

return std::nullopt;

}

SVal RegionStoreManager::getLazyBinding(const SubRegion *LazyBindingRegion,

RegionBindingsRef LazyBinding) {

SVal Result;

if (const ElementRegion *ER = dyn_cast(LazyBindingRegion))

Result = getBindingForElement(LazyBinding, ER);

else

Result = getBindingForField(LazyBinding,

cast(LazyBindingRegion));

if (Result.isUndef())

Result = UnknownVal();

return Result;

}

SVal

const TypedValueRegion *R,

Store lazyBindingStore = nullptr;

const SubRegion *lazyBindingRegion = nullptr;

std::tie(lazyBindingStore, lazyBindingRegion) = findLazyBinding(B, R, R);

if (lazyBindingRegion)

return getLazyBinding(lazyBindingRegion,

getRegionBindings(lazyBindingStore));

bool hasSymbolicIndex = false;

bool hasPartialLazyBinding = false;

const SubRegion *SR = R;

while (SR) {

const MemRegion *Base = SR->getSuperRegion();

if (std::optional D =

getBindingForDerivedDefaultValue(B, Base, R, Ty)) {

if (D->getAsnonloc::LazyCompoundVal()) {

hasPartialLazyBinding = true;

break;

}

return *D;

}

if (const ElementRegion *ER = dyn_cast(Base)) {

NonLoc index = ER->getIndex();

if (!index.isConstant())

hasSymbolicIndex = true;

}

SR = dyn_cast(Base);

}

if (R->hasStackNonParametersStorage()) {

if (isa(R)) {

if (const TypedValueRegion *typedSuperR =

dyn_cast(R->getSuperRegion())) {

if (typedSuperR->getValueType()->isVectorType())

return UnknownVal();

}

}

if (hasSymbolicIndex)

return UnknownVal();

if (!hasPartialLazyBinding && !isa(R->getBaseRegion())) {

if (const std::optional &V = B.getDefaultBinding(R))

return *V;

return UndefinedVal();

}

}

return svalBuilder.getRegionValueSymbolVal(R);

}

const ObjCIvarRegion* R) {

if (const std::optional &V = B.getDirectBinding(R))

return *V;

const MemRegion *superR = R->getSuperRegion();

if (const std::optional &V = B.getDefaultBinding(superR)) {

if (SymbolRef parentSym = V->getAsSymbol())

return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);

return UnknownVal();

}

return getBindingForLazySymbol(R);

}

const VarRegion *R) {

if (std::optional V = B.getDirectBinding(R))

return *V;

if (std::optional V = B.getDefaultBinding(R))

return *V;

const VarDecl *VD = R->getDecl();

const MemSpaceRegion *MS = R->getMemorySpace();

if (isa(MS))

return svalBuilder.getRegionValueSymbolVal(R);

if (std::optional V = svalBuilder.getConstantVal(Init))

return *V;

return UnknownVal();

}

}

if (isa(MS))

return svalBuilder.getRegionValueSymbolVal(R);

if (isa(MS)) {

if (B.isMainAnalysis())

if (std::optional V = svalBuilder.getConstantVal(Init))

return *V;

if (isa(MS))

return svalBuilder.makeZeroVal(T);

if (std::optional V = getBindingForDerivedDefaultValue(B, MS, R, T)) {

assert(->getAsnonloc::LazyCompoundVal());

return *V;

}

return svalBuilder.getRegionValueSymbolVal(R);

}

return UndefinedVal();

}

SVal RegionStoreManager::getBindingForLazySymbol(const TypedValueRegion *R) {

return svalBuilder.getRegionValueSymbolVal(R);

}

const RegionStoreManager::SValListTy &

RegionStoreManager::getInterestingValues(nonloc::LazyCompoundVal LCV) {

LazyBindingsMapTy::iterator I = LazyBindingsMap.find(LCV.getCVData());

if (I != LazyBindingsMap.end())

return I->second;

SValListTy List;

const SubRegion *LazyR = LCV.getRegion();

RegionBindingsRef B = getRegionBindings(LCV.getStore());

const ClusterBindings *Cluster = B.lookup(LazyR->getBaseRegion());

if (!Cluster)

return (LazyBindingsMap[LCV.getCVData()] = std::move(List));

true);

for (SVal V : llvm::make_second_range(Bindings)) {

if (V.isUnknownOrUndef() || V.isConstant())

continue;

if (auto InnerLCV = V.getAsnonloc::LazyCompoundVal()) {

const SValListTy &InnerList = getInterestingValues(*InnerLCV);

List.insert(List.end(), InnerList.begin(), InnerList.end());

}

List.push_back(V);

}

return (LazyBindingsMap[LCV.getCVData()] = std::move(List));

}

const TypedValueRegion *R) {

if (std::optionalnonloc::LazyCompoundVal V =

return *V;

return svalBuilder.makeLazyCompoundVal(StoreRef(B.asStore(), *this), R);

}

const TypedValueRegion *R) {

return UnknownVal();

if (std::optional Val = getUniqueDefaultBinding(B, R))

return *Val;

return createLazyBinding(B, R);

}

const TypedValueRegion *R) {

assert(Ctx.getAsConstantArrayType(R->getValueType()) &&

"Only constant array types can have compound bindings.");

return createLazyBinding(B, R);

}

bool RegionStoreManager::includedInBindings(Store store,

const MemRegion *region) const {

RegionBindingsRef B = getRegionBindings(store);

region = region->getBaseRegion();

if (B.lookup(region))

return true;

for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI) {

for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end();

CI != CE; ++CI) {

SVal D = CI.getData();

if (const MemRegion *R = D.getAsRegion())

if (R->getBaseRegion() == region)

return true;

}

}

return false;

}

StoreRef RegionStoreManager::killBinding(Store ST, Loc L) {

if (std::optionalloc::MemRegionVal LV = L.getAsloc::MemRegionVal())

if (const MemRegion* R = LV->getRegion())

return StoreRef(getRegionBindings(ST).removeBinding(R)

.asImmutableMap()

.getRootWithoutRetain(),

*this);

return StoreRef(ST, *this);

}

RegionBindingsRef

auto MemRegVal = L.getAsloc::MemRegionVal();

if (!MemRegVal)

return B;

const MemRegion *R = MemRegVal->getRegion();

if (const TypedValueRegion* TR = dyn_cast(R)) {

QualType Ty = TR->getValueType();

return bindArray(B, TR, V);

return bindStruct(B, TR, V);

return bindVector(B, TR, V);

return bindAggregate(B, TR, V);

}

if (const auto *SymReg = dyn_cast(R)) {

QualType Ty = SymReg->getPointeeStaticType();

Ty = StateMgr.getContext().CharTy;

R = GetElementZeroRegion(SymReg, Ty);

}

assert((!isa(R) || !B.lookup(R)) &&

"'this' pointer is not an l-value and is not assignable");

RegionBindingsRef NewB = removeSubRegionBindings(B, cast(R));

auto KeyKind = isanonloc::LazyCompoundVal(V) ? BindingKey::Default

: BindingKey::Direct;

return NewB.addBinding(BindingKey::Make(R, KeyKind), V);

}

RegionBindingsRef

const MemRegion *R,

SVal V;

if (Loc::isLocType(T))

V = svalBuilder.makeNullWithType(T);

V = svalBuilder.makeZeroVal(T);

V = svalBuilder.makeZeroVal(Ctx.IntTy);

}

else {

assert(!SymbolManager::canSymbolicate(T) && "This type is representable");

V = UnknownVal();

}

return B.addBinding(R, BindingKey::Default, V);

}

std::optional RegionStoreManager::tryBindSmallArray(

nonloc::LazyCompoundVal LCV) {

auto CAT = dyn_cast(AT);

if (!CAT)

return std::nullopt;

return std::nullopt;

if (ArrSize > SmallArrayLimit)

return std::nullopt;

RegionBindingsRef NewB = B;

for (uint64_t i = 0; i < ArrSize; ++i) {

auto Idx = svalBuilder.makeArrayIndex(i);

const ElementRegion *SrcER =

MRMgr.getElementRegion(Ty, Idx, LCV.getRegion(), Ctx);

SVal V = getBindingForElement(getRegionBindings(LCV.getStore()), SrcER);

const ElementRegion *DstER = MRMgr.getElementRegion(Ty, Idx, R, Ctx);

NewB = bind(NewB, loc::MemRegionVal(DstER), V);

}

return NewB;

}

RegionBindingsRef

const TypedValueRegion* R,

SVal Init) {

const ArrayType *AT =cast(Ctx.getCanonicalType(R->getValueType()));

std::optional<uint64_t> Size;

if (std::optionalloc::MemRegionVal MRV = Init.getAsloc::MemRegionVal()) {

SVal V = getBinding(B.asStore(), *MRV, R->getValueType());

return bindAggregate(B, R, V);

}

if (std::optionalnonloc::LazyCompoundVal LCV =

Init.getAsnonloc::LazyCompoundVal()) {

if (std::optional NewB =

tryBindSmallArray(B, R, AT, *LCV))

return *NewB;

return bindAggregate(B, R, Init);

}

if (Init.isUnknown())

return bindAggregate(B, R, UnknownVal());

const nonloc::CompoundVal& CV = Init.castAsnonloc::CompoundVal();

nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();

RegionBindingsRef NewB(B);

for (; Size ? i < *Size : true; ++i, ++VI) {

if (VI == VE)

break;

NonLoc Idx = svalBuilder.makeArrayIndex(i);

const ElementRegion *ER = MRMgr.getElementRegion(ElementTy, Idx, R, Ctx);

NewB = bindStruct(NewB, ER, *VI);

NewB = bindArray(NewB, ER, *VI);

else

NewB = bind(NewB, loc::MemRegionVal(ER), *VI);

}

if (!Size || i < *Size)

NewB = setImplicitDefaultValue(NewB, R, ElementTy);

return NewB;

}

const TypedValueRegion* R,

SVal V) {

if (isa<nonloc::LazyCompoundVal, nonloc::SymbolVal>(V))

return bindAggregate(B, R, V);

if (!isanonloc::CompoundVal(V)) {

return bindAggregate(B, R, UnknownVal());

}

nonloc::CompoundVal CV = V.castAsnonloc::CompoundVal();

nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();

RegionBindingsRef NewB(B);

for ( ; index != numElements ; ++index) {

if (VI == VE)

break;

NonLoc Idx = svalBuilder.makeArrayIndex(index);

const ElementRegion *ER = MRMgr.getElementRegion(ElemType, Idx, R, Ctx);

NewB = bindArray(NewB, ER, *VI);

NewB = bindStruct(NewB, ER, *VI);

else

NewB = bind(NewB, loc::MemRegionVal(ER), *VI);

}

return NewB;

}

std::optional

const TypedValueRegion *R) const {

if (R != R->getBaseRegion())

return std::nullopt;

const auto *Cluster = B.lookup(R);

if (!Cluster || !llvm::hasSingleElement(*Cluster))

return std::nullopt;

const auto [Key, Value] = *Cluster->begin();

return Key.isDirect() ? std::optional{} : Value;

}

std::optional

RegionStoreManager::getUniqueDefaultBinding(nonloc::LazyCompoundVal LCV) const {

return getUniqueDefaultBinding(B, LCV.getRegion());

}

std::optional RegionStoreManager::tryBindSmallStruct(

nonloc::LazyCompoundVal LCV) {

if (std::optional Val = getUniqueDefaultBinding(LCV)) {

return B.addBinding(BindingKey::Make(R, BindingKey::Default), Val.value());

}

if (const CXXRecordDecl *Class = dyn_cast(RD))

if (Class->getNumBases() != 0 || Class->getNumVBases() != 0)

return std::nullopt;

for (const auto *FD : RD->fields()) {

continue;

if (Fields.size() == SmallStructLimit)

return std::nullopt;

Ctx.getConstantArrayElementCount(Ctx.getAsConstantArrayType(Ty)) == 0)

continue;

return std::nullopt;

Fields.push_back(FD);

}

RegionBindingsRef NewB = B;

for (const FieldDecl *Field : Fields) {

const FieldRegion *SourceFR = MRMgr.getFieldRegion(Field, LCV.getRegion());

SVal V = getBindingForField(getRegionBindings(LCV.getStore()), SourceFR);

const FieldRegion *DestFR = MRMgr.getFieldRegion(Field, R);

NewB = bind(NewB, loc::MemRegionVal(DestFR), V);

}

return NewB;

}

const TypedValueRegion *R,

SVal V) {

if (!RD->isCompleteDefinition())

return B;

if (std::optionalnonloc::LazyCompoundVal LCV =

V.getAsnonloc::LazyCompoundVal()) {

if (std::optional NewB =

tryBindSmallStruct(B, R, RD, *LCV))

return *NewB;

return bindAggregate(B, R, V);

}

if (isanonloc::SymbolVal(V))

return bindAggregate(B, R, V);

if (V.isUnknown() || !isanonloc::CompoundVal(V))

return bindAggregate(B, R, UnknownVal());

const nonloc::CompoundVal& CV = V.castAsnonloc::CompoundVal();

nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();

RegionBindingsRef NewB(B);

if (const auto *CRD = dyn_cast(RD)) {

assert((CRD->isAggregate() || (Ctx.getLangOpts().ObjC && VI == VE)) &&

"Non-aggregates are constructed with a constructor!");

for (const auto &B : CRD->bases()) {

assert(!B.isVirtual() && "Aggregates cannot have virtual base classes!");

if (VI == VE)

break;

assert(BRD && "Base classes must be C++ classes!");

const CXXBaseObjectRegion *BR =

MRMgr.getCXXBaseObjectRegion(BRD, R, false);

NewB = bindStruct(NewB, BR, *VI);

++VI;

}

}

for (FI = RD->field_begin(), FE = RD->field_end(); FI != FE; ++FI) {

if (VI == VE)

break;

if (FI->isUnnamedBitField())

continue;

const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);

NewB = bindArray(NewB, FR, *VI);

NewB = bindStruct(NewB, FR, *VI);

else

NewB = bind(NewB, loc::MemRegionVal(FR), *VI);

++VI;

}

if (FI != FE) {

NewB = NewB.addBinding(R, BindingKey::Default,

svalBuilder.makeIntVal(0, false));

}

return NewB;

}

RegionBindingsRef

const TypedRegion *R,

SVal Val) {

return removeSubRegionBindings(B, R).addBinding(R, BindingKey::Default, Val);

}

namespace {

class RemoveDeadBindingsWorker

: public ClusterAnalysis {

SymbolReaper &SymReaper;

public:

RemoveDeadBindingsWorker(RegionStoreManager &rm,

ProgramStateManager &stateMgr,

RegionBindingsRef b, SymbolReaper &symReaper,

: ClusterAnalysis(rm, stateMgr, b),

SymReaper(symReaper), CurrentLCtx(LCtx) {}

void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C);

void VisitCluster(const MemRegion *baseR, const ClusterBindings *C);

using ClusterAnalysis::VisitCluster;

using ClusterAnalysis::AddToWorkList;

bool AddToWorkList(const MemRegion *R);

bool UpdatePostponed();

void VisitBinding(SVal V);

};

}

bool RemoveDeadBindingsWorker::AddToWorkList(const MemRegion *R) {

const MemRegion *BaseR = R->getBaseRegion();

return AddToWorkList(WorkListElement(BaseR), getCluster(BaseR));

}

void RemoveDeadBindingsWorker::VisitAddedToCluster(const MemRegion *baseR,

if (const VarRegion *VR = dyn_cast(baseR)) {

if (SymReaper.isLive(VR))

AddToWorkList(baseR, &C);

return;

}

if (const SymbolicRegion *SR = dyn_cast(baseR)) {

if (SymReaper.isLive(SR->getSymbol()))

AddToWorkList(SR, &C);

else

Postponed.push_back(SR);

return;

}

if (isa(baseR)) {

AddToWorkList(baseR, &C);

return;

}

if (const CXXThisRegion *TR = dyn_cast(baseR)) {

const auto *StackReg =

cast(TR->getSuperRegion());

if (CurrentLCtx &&

(RegCtx == CurrentLCtx || RegCtx->isParentOf(CurrentLCtx)))

AddToWorkList(TR, &C);

}

}

void RemoveDeadBindingsWorker::VisitCluster(const MemRegion *baseR,

if (!C)

return;

if (const SymbolicRegion *SymR = dyn_cast(baseR))

SymReaper.markLive(SymR->getSymbol());

for (const auto &[Key, Val] : *C) {

SymReaper.markElementIndicesLive(Key.getRegion());

VisitBinding(Val);

}

}

void RemoveDeadBindingsWorker::VisitBinding(SVal V) {

if (auto LCS = V.getAsnonloc::LazyCompoundVal()) {

SymReaper.markLazilyCopied(LCS->getRegion());

for (SVal V : RM.getInterestingValues(*LCS)) {

if (auto DepLCS = V.getAsnonloc::LazyCompoundVal())

SymReaper.markLazilyCopied(DepLCS->getRegion());

else

VisitBinding(V);

}

return;

}

if (const MemRegion *R = V.getAsRegion()) {

AddToWorkList(R);

SymReaper.markLive(R);

if (const BlockDataRegion *BR = dyn_cast(R)) {

for (auto Var : BR->referenced_vars())

AddToWorkList(Var.getCapturedRegion());

}

}

for (SymbolRef Sym : V.symbols())

SymReaper.markLive(Sym);

}

bool RemoveDeadBindingsWorker::UpdatePostponed() {

for (const SymbolicRegion *SR : Postponed) {

if (SymReaper.isLive(SR->getSymbol())) {

Changed |= AddToWorkList(SR);

SR = nullptr;

}

}

}

StoreRef RegionStoreManager::removeDeadBindings(Store store,

SymbolReaper& SymReaper) {

RegionBindingsRef B = getRegionBindings(store);

RemoveDeadBindingsWorker W(*this, StateMgr, B, SymReaper, LCtx);

W.GenerateClusters();

for (const MemRegion *Reg : SymReaper.regions()) {

W.AddToWorkList(Reg);

}

do W.RunWorkList(); while (W.UpdatePostponed());

for (const MemRegion *Base : llvm::make_first_range(B)) {

if (!W.isVisited(Base))

B = B.remove(Base);

}

return StoreRef(B.asStore(), *this);

}

void RegionStoreManager::printJson(raw_ostream &Out, Store S, const char *NL,

unsigned int Space, bool IsDot) const {

RegionBindingsRef Bindings = getRegionBindings(S);

Indent(Out, Space, IsDot) << "\"store\": ";

Out << "null," << NL;

return;

}

Out << "{ \"pointer\": \"" << Bindings.asStore() << "\", \"items\": [" << NL;

Bindings.printJson(Out, NL, Space + 1, IsDot);

Indent(Out, Space, IsDot) << "]}," << NL;

}

This file defines AnalysisDeclContext, a class that manages the analysis context data for context sen...

static const MemRegion * getRegion(const CallEvent &Call, const MutexDescriptor &Descriptor, bool IsLock)

enum clang::sema::@1727::IndirectLocalPathEntry::EntryKind Kind

static void dump(llvm::raw_ostream &OS, StringRef FunctionName, ArrayRef< CounterExpression > Expressions, ArrayRef< CounterMappingRegion > Regions)

llvm::DenseSet< const void * > Visited

static std::optional< SVal > convertOffsetsFromSvalToUnsigneds(const SmallVector< SVal, 2 > &SrcOffsets, const SmallVector< uint64_t, 2 > ArrayExtents, SmallVector< uint64_t, 2 > &DstOffsets)

llvm::ImmutableMap< const MemRegion *, ClusterBindings > RegionBindings

static std::optional< SVal > getDerivedSymbolForBinding(RegionBindingsConstRef B, const TypedValueRegion *BaseRegion, const TypedValueRegion *SubReg, const ASTContext &Ctx, SValBuilder &SVB)

std::pair< BindingKey, SVal > BindingPair

static bool isCompatibleWithFields(BindingKey K, const FieldVector &Fields)

SmallVector< const FieldDecl *, 8 > FieldVector

llvm::ImmutableMap< BindingKey, SVal > ClusterBindings

static bool isUnionField(const FieldRegion *FR)

static void getSymbolicOffsetFields(BindingKey K, FieldVector &Fields)

static QualType getUnderlyingType(const SubRegion *R)

llvm::ImmutableMapRef< BindingKey, SVal > ClusterBindingsRef

static SmallVector< uint64_t, 2 > getConstantArrayExtents(const ConstantArrayType *CAT)

This is a helper function for getConstantValFromConstArrayInitializer.

static std::pair< SmallVector< SVal, 2 >, const MemRegion * > getElementRegionOffsetsWithBase(const ElementRegion *ER)

This is a helper function for getConstantValFromConstArrayInitializer.

const RegionBindingsRef & RegionBindingsConstRef

static std::optional< nonloc::LazyCompoundVal > getExistingLazyBinding(SValBuilder &SVB, RegionBindingsConstRef B, const SubRegion *R, bool AllowSubregionBindings)

Checks to see if store B has a lazy binding for region R.

static void collectSubRegionBindings(SmallVectorImpl< BindingPair > &Bindings, SValBuilder &SVB, const ClusterBindings &Cluster, const SubRegion *Top, BindingKey TopKey, bool IncludeAllDefaultBindings)

Collects all bindings in Cluster that may refer to bindings within Top.

llvm::SmallVector< std::pair< const MemRegion *, SVal >, 4 > Bindings

__PTRDIFF_TYPE__ ptrdiff_t

Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...

Stores options for the analyzer from the command line.

Represents an array type, per C99 6.7.5.2 - Array Declarators.

QualType getElementType() const

Represents a C++ struct/union/class.

Represents the canonical version of C arrays with a specified constant size.

uint64_t getLimitedSize() const

Return the size zero-extended to uint64_t or UINT64_MAX if the value is larger than UINT64_MAX.

uint64_t getZExtSize() const

Return the size zero-extended as a uint64_t.

specific_decl_iterator - Iterates over a subrange of declarations stored in a DeclContext,...

This represents one expression.

Represents a member of a struct/union/class.

unsigned getFieldIndex() const

Returns the index of this field within its record, as appropriate for passing to ASTRecordLayout::get...

bool isUnnamedBitField() const

Determines whether this is an unnamed bitfield.

Describes an C or C++ initializer list.

bool isStringLiteralInit() const

Is this an initializer for an array of characters, initialized by a string literal or an @encode?

unsigned getNumInits() const

const Expr * getInit(unsigned Init) const

It wraps the AnalysisDeclContext to represent both the call stack with the help of StackFrameContext ...

bool isParentOf(const LocationContext *LC) const

const Decl * getDecl() const

const StackFrameContext * getStackFrame() const

A (possibly-)qualified type.

bool isNull() const

Return true if this QualType doesn't point to a type yet.

bool isConstQualified() const

Determine whether this type is const-qualified.

Represents a struct/union/class.

field_range fields() const

RecordDecl * getDefinition() const

Returns the RecordDecl that actually defines this struct/union/class.

A helper class that allows the use of isa/cast/dyncast to detect TagType objects of structs/unions/cl...

RecordDecl * getDecl() const

It represents a stack frame of the call stack (based on CallEvent).

Stmt - This represents one statement.

StringLiteral - This represents a string literal expression, e.g.

unsigned getLength() const

uint32_t getCodeUnit(size_t i) const

CXXRecordDecl * getAsCXXRecordDecl() const

Retrieves the CXXRecordDecl that this type refers to, either because the type is a RecordType or beca...

bool isConstantArrayType() const

bool isVoidPointerType() const

const T * castAs() const

Member-template castAs.

bool isReferenceType() const

bool isScalarType() const

QualType getPointeeType() const

If this is a pointer, ObjC object pointer, or block pointer, this returns the respective pointee.

bool isIntegralOrEnumerationType() const

Determine whether this type is an integral or enumeration type.

bool isAnyComplexType() const

QualType getCanonicalTypeInternal() const

bool isStructureOrClassType() const

bool isVectorType() const

bool isRecordType() const

Represents a variable declaration or definition.

bool hasGlobalStorage() const

Returns true for all variables that do not have local storage.

bool hasLocalStorage() const

Returns true if a variable with function scope is a non-static local variable.

const Expr * getAnyInitializer() const

Get the initializer for this variable, no matter which declaration it is attached to.

Represents a GCC generic vector type.

unsigned getNumElements() const

QualType getElementType() const

Maps string IDs to AST nodes matched by parts of a matcher.

Defines the clang::TargetInfo interface.

const internal::VariadicDynCastAllOfMatcher< Decl, VarDecl > varDecl

Matches variable declarations.

const internal::VariadicDynCastAllOfMatcher< Stmt, DeclRefExpr > declRefExpr

Matches expressions that refer to declarations.

const internal::ArgumentAdaptingMatcherFunc< internal::HasDescendantMatcher > hasDescendant

Matches AST nodes that have descendant AST nodes that match the provided matcher.

SmallVector< BoundNodes, 1 > match(MatcherT Matcher, const NodeT &Node, ASTContext &Context)

Returns the results of matching Matcher on Node.

internal::Matcher< Stmt > StatementMatcher

const internal::VariadicAllOfMatcher< Stmt > stmt

Matches statements.

llvm::DenseSet< SymbolRef > InvalidatedSymbols

const void * Store

Store - This opaque type encapsulates an immutable mapping from locations to values.

bool Init(InterpState &S, CodePtr OpPC)

ASTEdit remove(RangeSelector S)

Removes the source selected by S.

The JSON file list parser is used to communicate input to InstallAPI.

const FunctionProtoType * T

@ Class

The "class" keyword introduces the elaborated-type-specifier.

Diagnostic wrappers for TextAPI types for error reporting.

static raw_ostream & operator<<(raw_ostream &Out, BindingKey K)

__UINTPTR_TYPE__ uintptr_t

An unsigned integer type with the property that any valid pointer to void can be converted to this ty...