#include "clang/AST/CharUnits.h"
#include "clang/Analysis/Analyses/LiveVariables.h"
#include "clang/Analysis/AnalysisContext.h"
#include "clang/Basic/TargetInfo.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
#include "llvm/ADT/ImmutableList.h"
#include "llvm/ADT/ImmutableMap.h"
#include "llvm/ADT/Optional.h"
#include "llvm/Support/raw_ostream.h"
using namespace clang;
using namespace ento;
using llvm::Optional;
namespace {
class BindingKey {
public:
enum Kind { Default = 0x0, Direct = 0x1 };
private:
enum { Symbolic = 0x2 };
llvm::PointerIntPair<const MemRegion *, 2> P;
uint64_t Data;
explicit BindingKey(const MemRegion *r, const MemRegion *Base, Kind k)
: P(r, k | Symbolic), Data(reinterpret_cast<uintptr_t>(Base)) {
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>(r)) && "Not a base");
}
public:
bool isDirect() const { return P.getInt() & Direct; }
bool hasSymbolicOffset() const { return P.getInt() & Symbolic; }
const MemRegion *getRegion() const { return P.getPointer(); }
uint64_t getOffset() const {
assert(!hasSymbolicOffset());
return Data;
}
const MemRegion *getConcreteOffsetRegion() const {
assert(hasSymbolicOffset());
return reinterpret_cast<const MemRegion *>(static_cast<uintptr_t>(Data));
}
const MemRegion *getBaseRegion() const {
if (hasSymbolicOffset())
return getConcreteOffsetRegion()->getBaseRegion();
return getRegion()->getBaseRegion();
}
void Profile(llvm::FoldingSetNodeID& ID) const {
ID.AddPointer(P.getOpaqueValue());
ID.AddInteger(Data);
}
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() &&
Data == X.Data;
}
LLVM_ATTRIBUTE_USED void dump() const;
};
}
BindingKey BindingKey::Make(const MemRegion *R, Kind k) {
const RegionOffset &RO = R->getAsOffset();
if (RO.hasSymbolicOffset())
return BindingKey(R, RO.getRegion(), k);
return BindingKey(RO.getRegion(), RO.getOffset(), k);
}
namespace llvm {
static inline
raw_ostream &operator<<(raw_ostream &os, BindingKey K) {
os << '(' << K.getRegion();
if (!K.hasSymbolicOffset())
os << ',' << K.getOffset();
os << ',' << (K.isDirect() ? "direct" : "default")
<< ')';
return os;
}
}
void BindingKey::dump() const {
llvm::errs() << *this;
}
typedef llvm::ImmutableMap<BindingKey, SVal> ClusterBindings;
typedef llvm::ImmutableMap<const MemRegion *, ClusterBindings> RegionBindings;
namespace {
struct minimal_features_tag {};
struct maximal_features_tag {};
class RegionStoreFeatures {
bool SupportsFields;
public:
RegionStoreFeatures(minimal_features_tag) :
SupportsFields(false) {}
RegionStoreFeatures(maximal_features_tag) :
SupportsFields(true) {}
void enableFields(bool t) { SupportsFields = t; }
bool supportsFields() const { return SupportsFields; }
};
}
namespace {
class RegionStoreManager : public StoreManager {
const RegionStoreFeatures Features;
RegionBindings::Factory RBFactory;
ClusterBindings::Factory CBFactory;
public:
RegionStoreManager(ProgramStateManager& mgr, const RegionStoreFeatures &f)
: StoreManager(mgr), Features(f),
RBFactory(mgr.getAllocator()), CBFactory(mgr.getAllocator()) {}
Optional<SVal> getDirectBinding(RegionBindings B, const MemRegion *R);
Optional<SVal> getDefaultBinding(RegionBindings B, const MemRegion *R);
StoreRef setImplicitDefaultValue(Store store, const MemRegion *R, QualType T);
SVal ArrayToPointer(Loc Array);
StoreRef getInitialStore(const LocationContext *InitLoc) {
return StoreRef(RBFactory.getEmptyMap().getRootWithoutRetain(), *this);
}
RegionBindings invalidateGlobalRegion(MemRegion::Kind K,
const Expr *Ex,
unsigned Count,
const LocationContext *LCtx,
RegionBindings B,
InvalidatedRegions *Invalidated);
StoreRef invalidateRegions(Store store, ArrayRef<const MemRegion *> Regions,
const Expr *E, unsigned Count,
const LocationContext *LCtx,
InvalidatedSymbols &IS,
const CallEvent *Call,
InvalidatedRegions *Invalidated);
bool scanReachableSymbols(Store S, const MemRegion *R,
ScanReachableSymbols &Callbacks);
public:
RegionBindings removeSubRegionBindings(RegionBindings B, const SubRegion *R);
RegionBindings addBinding(RegionBindings B, BindingKey K, SVal V);
RegionBindings addBinding(RegionBindings B, const MemRegion *R,
BindingKey::Kind k, SVal V);
const SVal *lookup(RegionBindings B, BindingKey K);
const SVal *lookup(RegionBindings B, const MemRegion *R, BindingKey::Kind k);
RegionBindings removeBinding(RegionBindings B, BindingKey K);
RegionBindings removeBinding(RegionBindings B, const MemRegion *R,
BindingKey::Kind k);
RegionBindings removeBinding(RegionBindings B, const MemRegion *R) {
return removeBinding(removeBinding(B, R, BindingKey::Direct), R,
BindingKey::Default);
}
RegionBindings removeCluster(RegionBindings B, const MemRegion *R);
public:
StoreRef Bind(Store store, Loc LV, SVal V);
StoreRef BindDefault(Store store, const MemRegion *R, SVal V) {
RegionBindings B = GetRegionBindings(store);
assert(!lookup(B, R, BindingKey::Default));
assert(!lookup(B, R, BindingKey::Direct));
return StoreRef(addBinding(B, R, BindingKey::Default, V)
.getRootWithoutRetain(), *this);
}
StoreRef bindCompoundLiteral(Store ST,
const CompoundLiteralExpr *CL,
const LocationContext *LC, SVal V);
StoreRef BindStruct(Store store, const TypedValueRegion* R, SVal V);
StoreRef BindVector(Store store, const TypedValueRegion* R, SVal V);
StoreRef BindArray(Store store, const TypedValueRegion* R, SVal V);
StoreRef BindAggregate(Store store, const TypedRegion *R, SVal DefaultVal);
StoreRef killBinding(Store ST, Loc L);
void incrementReferenceCount(Store store) {
GetRegionBindings(store).manualRetain();
}
void decrementReferenceCount(Store store) {
GetRegionBindings(store).manualRelease();
}
bool includedInBindings(Store store, const MemRegion *region) const;
SVal getBinding(Store store, Loc L, QualType T = QualType());
SVal getBindingForElement(Store store, const ElementRegion *R);
SVal getBindingForField(Store store, const FieldRegion *R);
SVal getBindingForObjCIvar(Store store, const ObjCIvarRegion *R);
SVal getBindingForVar(Store store, const VarRegion *R);
SVal getBindingForLazySymbol(const TypedValueRegion *R);
SVal getBindingForFieldOrElementCommon(Store store, const TypedValueRegion *R,
QualType Ty, const MemRegion *superR);
SVal getLazyBinding(const MemRegion *lazyBindingRegion,
Store lazyBindingStore);
SVal getBindingForStruct(Store store, const TypedValueRegion* R);
SVal getBindingForArray(Store store, const TypedValueRegion* R);
Optional<SVal> getBindingForDerivedDefaultValue(RegionBindings B,
const MemRegion *superR,
const TypedValueRegion *R,
QualType Ty);
std::pair<Store, const MemRegion*>
GetLazyBinding(RegionBindings B, const MemRegion *R,
const MemRegion *originalRegion,
bool includeSuffix = false);
StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx,
SymbolReaper& SymReaper);
DefinedOrUnknownSVal getSizeInElements(ProgramStateRef state,
const MemRegion* R, QualType EleTy);
static inline RegionBindings GetRegionBindings(Store store) {
return RegionBindings(static_cast<const RegionBindings::TreeTy*>(store));
}
void print(Store store, raw_ostream &Out, const char* nl,
const char *sep);
void iterBindings(Store store, BindingsHandler& f) {
RegionBindings B = GetRegionBindings(store);
for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) {
const ClusterBindings &Cluster = I.getData();
for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end();
CI != CE; ++CI) {
const BindingKey &K = CI.getKey();
if (!K.isDirect())
continue;
if (const SubRegion *R = dyn_cast<SubRegion>(K.getRegion())) {
if (!f.HandleBinding(*this, store, R, CI.getData()))
return;
}
}
}
}
};
}
StoreManager *ento::CreateRegionStoreManager(ProgramStateManager& StMgr) {
RegionStoreFeatures F = maximal_features_tag();
return new RegionStoreManager(StMgr, F);
}
StoreManager *
ento::CreateFieldsOnlyRegionStoreManager(ProgramStateManager &StMgr) {
RegionStoreFeatures F = minimal_features_tag();
F.enableFields(true);
return new RegionStoreManager(StMgr, F);
}
namespace {
template <typename DERIVED>
class ClusterAnalysis {
protected:
typedef llvm::DenseMap<const MemRegion *, const ClusterBindings *> ClusterMap;
typedef SmallVector<const MemRegion *, 10> WorkList;
llvm::SmallPtrSet<const ClusterBindings *, 16> Visited;
WorkList WL;
RegionStoreManager &RM;
ASTContext &Ctx;
SValBuilder &svalBuilder;
RegionBindings B;
const bool includeGlobals;
const ClusterBindings *getCluster(const MemRegion *R) {
return B.lookup(R);
}
public:
ClusterAnalysis(RegionStoreManager &rm, ProgramStateManager &StateMgr,
RegionBindings b, const bool includeGlobals)
: RM(rm), Ctx(StateMgr.getContext()),
svalBuilder(StateMgr.getSValBuilder()),
B(b), includeGlobals(includeGlobals) {}
RegionBindings getRegionBindings() const { return B; }
bool isVisited(const MemRegion *R) {
return Visited.count(getCluster(R));
}
void GenerateClusters() {
for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){
const MemRegion *Base = RI.getKey();
const ClusterBindings &Cluster = RI.getData();
assert(!Cluster.isEmpty() && "Empty clusters should be removed");
static_cast<DERIVED*>(this)->VisitAddedToCluster(Base, Cluster);
if (includeGlobals)
if (isa<NonStaticGlobalSpaceRegion>(Base->getMemorySpace()))
AddToWorkList(Base, &Cluster);
}
}
bool AddToWorkList(const MemRegion *R, const ClusterBindings *C) {
if (C && !Visited.insert(C))
return false;
WL.push_back(R);
return true;
}
bool AddToWorkList(const MemRegion *R) {
const MemRegion *baseR = R->getBaseRegion();
return AddToWorkList(baseR, getCluster(baseR));
}
void RunWorkList() {
while (!WL.empty()) {
const MemRegion *baseR = WL.pop_back_val();
if (const ClusterBindings *Cluster = getCluster(baseR))
static_cast<DERIVED*>(this)->VisitCluster(baseR, *Cluster);
static_cast<DERIVED*>(this)->VisitBaseRegion(baseR);
}
}
public:
void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C) {}
void VisitCluster(const MemRegion *baseR, const ClusterBindings &C) {}
void VisitBaseRegion(const MemRegion *baseR) {}
};
}
bool RegionStoreManager::scanReachableSymbols(Store S, const MemRegion *R,
ScanReachableSymbols &Callbacks) {
assert(R == R->getBaseRegion() && "Should only be called for base regions");
RegionBindings B = GetRegionBindings(S);
const ClusterBindings *Cluster = B.lookup(R);
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();
}
typedef SmallVector<const FieldDecl *, 8> FieldVector;
void getSymbolicOffsetFields(BindingKey K, FieldVector &Fields) {
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<FieldRegion>(R))
if (!isUnionField(FR))
Fields.push_back(FR->getDecl());
R = cast<SubRegion>(R)->getSuperRegion();
}
}
static bool isCompatibleWithFields(BindingKey K, const FieldVector &Fields) {
assert(K.hasSymbolicOffset() && "Not implemented for concrete offset keys");
if (Fields.empty())
return true;
FieldVector FieldsInBindingKey;
getSymbolicOffsetFields(K, FieldsInBindingKey);
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);
}
RegionBindings RegionStoreManager::removeSubRegionBindings(RegionBindings B,
const SubRegion *R) {
BindingKey SRKey = BindingKey::Make(R, BindingKey::Default);
const MemRegion *ClusterHead = SRKey.getBaseRegion();
if (R == ClusterHead) {
return RBFactory.remove(B, R);
}
FieldVector FieldsInSymbolicSubregions;
bool HasSymbolicOffset = SRKey.hasSymbolicOffset();
if (HasSymbolicOffset) {
getSymbolicOffsetFields(SRKey, FieldsInSymbolicSubregions);
R = cast<SubRegion>(SRKey.getConcreteOffsetRegion());
SRKey = BindingKey::Make(R, BindingKey::Default);
}
uint64_t Length = UINT64_MAX;
SVal Extent = R->getExtent(svalBuilder);
if (nonloc::ConcreteInt *ExtentCI = dyn_cast<nonloc::ConcreteInt>(&Extent)) {
const llvm::APSInt &ExtentInt = ExtentCI->getValue();
assert(ExtentInt.isNonNegative() || ExtentInt.isUnsigned());
Length = ExtentInt.getLimitedValue() * Ctx.getCharWidth();
}
const ClusterBindings *Cluster = B.lookup(ClusterHead);
if (!Cluster)
return B;
ClusterBindings Result = *Cluster;
for (ClusterBindings::iterator I = Cluster->begin(), E = Cluster->end();
I != E; ++I) {
BindingKey NextKey = I.getKey();
if (NextKey.getRegion() == SRKey.getRegion()) {
if (NextKey.getOffset() > SRKey.getOffset() &&
NextKey.getOffset() - SRKey.getOffset() < Length) {
Result = CBFactory.remove(Result, NextKey);
} else if (NextKey.getOffset() == SRKey.getOffset()) {
if (NextKey.isDirect())
Result = CBFactory.remove(Result, NextKey);
}
} else if (NextKey.hasSymbolicOffset()) {
const MemRegion *Base = NextKey.getConcreteOffsetRegion();
if (R->isSubRegionOf(Base)) {
if (NextKey.isDirect())
if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions))
Result = CBFactory.remove(Result, NextKey);
} else if (const SubRegion *BaseSR = dyn_cast<SubRegion>(Base)) {
if (R == Base || BaseSR->isSubRegionOf(R))
if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions))
Result = CBFactory.remove(Result, NextKey);
}
}
}
if (HasSymbolicOffset)
Result = CBFactory.add(Result, SRKey, UnknownVal());
if (Result.isEmpty())
return RBFactory.remove(B, ClusterHead);
return RBFactory.add(B, ClusterHead, Result);
}
namespace {
class invalidateRegionsWorker : public ClusterAnalysis<invalidateRegionsWorker>
{
const Expr *Ex;
unsigned Count;
const LocationContext *LCtx;
StoreManager::InvalidatedSymbols &IS;
StoreManager::InvalidatedRegions *Regions;
public:
invalidateRegionsWorker(RegionStoreManager &rm,
ProgramStateManager &stateMgr,
RegionBindings b,
const Expr *ex, unsigned count,
const LocationContext *lctx,
StoreManager::InvalidatedSymbols &is,
StoreManager::InvalidatedRegions *r,
bool includeGlobals)
: ClusterAnalysis<invalidateRegionsWorker>(rm, stateMgr, b, includeGlobals),
Ex(ex), Count(count), LCtx(lctx), IS(is), Regions(r) {}
void VisitCluster(const MemRegion *baseR, const ClusterBindings &C);
void VisitBaseRegion(const MemRegion *baseR);
private:
void VisitBinding(SVal V);
};
}
void invalidateRegionsWorker::VisitBinding(SVal V) {
if (SymbolRef Sym = V.getAsSymbol())
IS.insert(Sym);
if (const MemRegion *R = V.getAsRegion()) {
AddToWorkList(R);
return;
}
if (const nonloc::LazyCompoundVal *LCS =
dyn_cast<nonloc::LazyCompoundVal>(&V)) {
const MemRegion *LazyR = LCS->getRegion();
RegionBindings B = RegionStoreManager::GetRegionBindings(LCS->getStore());
for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){
const ClusterBindings &Cluster = RI.getData();
for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end();
CI != CE; ++CI) {
BindingKey K = CI.getKey();
if (const SubRegion *BaseR = dyn_cast<SubRegion>(K.getRegion())) {
if (BaseR == LazyR)
VisitBinding(CI.getData());
else if (K.hasSymbolicOffset() && BaseR->isSubRegionOf(LazyR))
VisitBinding(CI.getData());
}
}
}
return;
}
}
void invalidateRegionsWorker::VisitCluster(const MemRegion *BaseR,
const ClusterBindings &C) {
for (ClusterBindings::iterator I = C.begin(), E = C.end(); I != E; ++I)
VisitBinding(I.getData());
B = RM.removeCluster(B, BaseR);
}
void invalidateRegionsWorker::VisitBaseRegion(const MemRegion *baseR) {
if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR))
IS.insert(SR->getSymbol());
if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(baseR)) {
for (BlockDataRegion::referenced_vars_iterator
BI = BR->referenced_vars_begin(), BE = BR->referenced_vars_end() ;
BI != BE; ++BI) {
const VarRegion *VR = *BI;
const VarDecl *VD = VR->getDecl();
if (VD->getAttr<BlocksAttr>() || !VD->hasLocalStorage()) {
AddToWorkList(VR);
}
else if (Loc::isLocType(VR->getValueType())) {
Store store = B.getRootWithoutRetain();
SVal V = RM.getBinding(store, loc::MemRegionVal(VR));
if (const Loc *L = dyn_cast<Loc>(&V)) {
if (const MemRegion *LR = L->getAsRegion())
AddToWorkList(LR);
}
}
}
return;
}
if (Regions)
Regions->push_back(baseR);
if (isa<AllocaRegion>(baseR) || isa<SymbolicRegion>(baseR)) {
DefinedOrUnknownSVal V =
svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, Ctx.IntTy, Count);
B = RM.addBinding(B, baseR, BindingKey::Default, V);
return;
}
if (!baseR->isBoundable())
return;
const TypedValueRegion *TR = cast<TypedValueRegion>(baseR);
QualType T = TR->getValueType();
if (T->isStructureOrClassType()) {
DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx,
Ctx.IntTy, Count);
B = RM.addBinding(B, baseR, BindingKey::Default, V);
return;
}
if (const ArrayType *AT = Ctx.getAsArrayType(T)) {
DefinedOrUnknownSVal V =
svalBuilder.conjureSymbolVal(baseR, Ex, LCtx,
AT->getElementType(), Count);
B = RM.addBinding(B, baseR, BindingKey::Default, V);
return;
}
if (includeGlobals &&
isa<NonStaticGlobalSpaceRegion>(baseR->getMemorySpace())) {
B = RM.removeBinding(B, baseR);
return;
}
DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx,
T,Count);
assert(SymbolManager::canSymbolicate(T) || V.isUnknown());
B = RM.addBinding(B, baseR, BindingKey::Direct, V);
}
RegionBindings RegionStoreManager::invalidateGlobalRegion(MemRegion::Kind K,
const Expr *Ex,
unsigned Count,
const LocationContext *LCtx,
RegionBindings B,
InvalidatedRegions *Invalidated) {
const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion(K);
SVal V = svalBuilder.conjureSymbolVal( (const void*) GS, Ex, LCtx,
Ctx.IntTy,
Count);
B = removeBinding(B, GS);
B = addBinding(B, BindingKey::Make(GS, BindingKey::Default), V);
if (Invalidated)
Invalidated->push_back(GS);
return B;
}
StoreRef RegionStoreManager::invalidateRegions(Store store,
ArrayRef<const MemRegion *> Regions,
const Expr *Ex, unsigned Count,
const LocationContext *LCtx,
InvalidatedSymbols &IS,
const CallEvent *Call,
InvalidatedRegions *Invalidated) {
invalidateRegionsWorker W(*this, StateMgr,
RegionStoreManager::GetRegionBindings(store),
Ex, Count, LCtx, IS, Invalidated, false);
W.GenerateClusters();
for (ArrayRef<const MemRegion *>::iterator
I = Regions.begin(), E = Regions.end(); I != E; ++I)
W.AddToWorkList(*I);
W.RunWorkList();
RegionBindings B = W.getRegionBindings();
if (Call && Call->isInSystemHeader()) {
B = invalidateGlobalRegion(MemRegion::GlobalSystemSpaceRegionKind,
Ex, Count, LCtx, B, Invalidated);
} else {
B = invalidateGlobalRegion(MemRegion::GlobalSystemSpaceRegionKind,
Ex, Count, LCtx, B, Invalidated);
B = invalidateGlobalRegion(MemRegion::GlobalInternalSpaceRegionKind,
Ex, Count, LCtx, B, Invalidated);
}
return StoreRef(B.getRootWithoutRetain(), *this);
}
DefinedOrUnknownSVal
RegionStoreManager::getSizeInElements(ProgramStateRef state,
const MemRegion *R,
QualType EleTy) {
SVal Size = cast<SubRegion>(R)->getExtent(svalBuilder);
const llvm::APSInt *SizeInt = svalBuilder.getKnownValue(state, Size);
if (!SizeInt)
return UnknownVal();
CharUnits RegionSize = CharUnits::fromQuantity(SizeInt->getSExtValue());
if (Ctx.getAsVariableArrayType(EleTy)) {
return UnknownVal();
}
CharUnits EleSize = Ctx.getTypeSizeInChars(EleTy);
return svalBuilder.makeIntVal(RegionSize / EleSize, false);
}
SVal RegionStoreManager::ArrayToPointer(Loc Array) {
if (!isa<loc::MemRegionVal>(Array))
return UnknownVal();
const MemRegion* R = cast<loc::MemRegionVal>(&Array)->getRegion();
const TypedValueRegion* ArrayR = dyn_cast<TypedValueRegion>(R);
if (!ArrayR)
return UnknownVal();
QualType T = ArrayR->getValueType().getDesugaredType(Ctx);
const ArrayType *AT = cast<ArrayType>(T);
T = AT->getElementType();
NonLoc ZeroIdx = svalBuilder.makeZeroArrayIndex();
return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, ArrayR, Ctx));
}
Optional<SVal> RegionStoreManager::getDirectBinding(RegionBindings B,
const MemRegion *R) {
if (const SVal *V = lookup(B, R, BindingKey::Direct))
return *V;
return Optional<SVal>();
}
Optional<SVal> RegionStoreManager::getDefaultBinding(RegionBindings B,
const MemRegion *R) {
if (R->isBoundable())
if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R))
if (TR->getValueType()->isUnionType())
return UnknownVal();
if (const SVal *V = lookup(B, R, BindingKey::Default))
return *V;
return Optional<SVal>();
}
SVal RegionStoreManager::getBinding(Store store, Loc L, QualType T) {
assert(!isa<UnknownVal>(L) && "location unknown");
assert(!isa<UndefinedVal>(L) && "location undefined");
if (isa<loc::ConcreteInt>(L)) {
return UnknownVal();
}
if (!isa<loc::MemRegionVal>(L)) {
return UnknownVal();
}
const MemRegion *MR = cast<loc::MemRegionVal>(L).getRegion();
if (isa<AllocaRegion>(MR) ||
isa<SymbolicRegion>(MR) ||
isa<CodeTextRegion>(MR)) {
if (T.isNull()) {
if (const TypedRegion *TR = dyn_cast<TypedRegion>(MR))
T = TR->getLocationType();
else {
const SymbolicRegion *SR = cast<SymbolicRegion>(MR);
T = SR->getSymbol()->getType();
}
}
MR = GetElementZeroRegion(MR, T);
}
const TypedValueRegion *R = cast<TypedValueRegion>(MR);
QualType RTy = R->getValueType();
if (RTy->isStructureOrClassType())
return getBindingForStruct(store, R);
if (RTy->isUnionType())
return UnknownVal();
if (RTy->isArrayType()) {
if (RTy->isConstantArrayType())
return getBindingForArray(store, R);
else
return UnknownVal();
}
if (RTy->isVectorType())
return UnknownVal();
if (const FieldRegion* FR = dyn_cast<FieldRegion>(R))
return CastRetrievedVal(getBindingForField(store, FR), FR, T, false);
if (const ElementRegion* ER = dyn_cast<ElementRegion>(R)) {
return CastRetrievedVal(getBindingForElement(store, ER), ER, T, false);
}
if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) {
return CastRetrievedVal(getBindingForObjCIvar(store, IVR), IVR, T, false);
}
if (const VarRegion *VR = dyn_cast<VarRegion>(R)) {
return CastRetrievedVal(getBindingForVar(store, VR), VR, T, false);
}
RegionBindings B = GetRegionBindings(store);
const SVal *V = lookup(B, R, BindingKey::Direct);
if (V)
return *V;
if (R->hasStackNonParametersStorage()) {
return UndefinedVal();
}
return svalBuilder.getRegionValueSymbolVal(R);
}
std::pair<Store, const MemRegion *>
RegionStoreManager::GetLazyBinding(RegionBindings B, const MemRegion *R,
const MemRegion *originalRegion,
bool includeSuffix) {
if (originalRegion != R) {
if (Optional<SVal> OV = getDefaultBinding(B, R)) {
if (const nonloc::LazyCompoundVal *V =
dyn_cast<nonloc::LazyCompoundVal>(OV.getPointer()))
return std::make_pair(V->getStore(), V->getRegion());
}
}
if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
const std::pair<Store, const MemRegion *> &X =
GetLazyBinding(B, ER->getSuperRegion(), originalRegion);
if (X.second)
return std::make_pair(X.first,
MRMgr.getElementRegionWithSuper(ER, X.second));
}
else if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) {
const std::pair<Store, const MemRegion *> &X =
GetLazyBinding(B, FR->getSuperRegion(), originalRegion);
if (X.second) {
if (includeSuffix)
return std::make_pair(X.first,
MRMgr.getFieldRegionWithSuper(FR, X.second));
return X;
}
}
else if (const CXXBaseObjectRegion *baseReg =
dyn_cast<CXXBaseObjectRegion>(R)) {
const std::pair<Store, const MemRegion *> &X =
GetLazyBinding(B, baseReg->getSuperRegion(), originalRegion);
if (X.second) {
if (includeSuffix)
return std::make_pair(X.first,
MRMgr.getCXXBaseObjectRegionWithSuper(baseReg,
X.second));
return X;
}
}
return std::make_pair((Store) 0, (const MemRegion *) 0);
}
SVal RegionStoreManager::getBindingForElement(Store store,
const ElementRegion* R) {
if (isa<CompoundLiteralRegion>(R->getBaseRegion()))
return UnknownVal();
RegionBindings B = GetRegionBindings(store);
if (const Optional<SVal> &V = getDirectBinding(B, R))
return *V;
const MemRegion* superR = R->getSuperRegion();
if (const StringRegion *StrR=dyn_cast<StringRegion>(superR)) {
QualType T = Ctx.getAsArrayType(StrR->getValueType())->getElementType();
if (T != Ctx.getCanonicalType(R->getElementType()))
return UnknownVal();
const StringLiteral *Str = StrR->getStringLiteral();
SVal Idx = R->getIndex();
if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&Idx)) {
int64_t i = CI->getValue().getSExtValue();
if (i < 0)
return UndefinedVal();
int64_t length = Str->getLength();
char c = (i >= length) ? '\0' : Str->getCodeUnit(i);
return svalBuilder.makeIntVal(c, T);
}
}
if (isa<CodeTextRegion>(superR))
return UnknownVal();
const RegionRawOffset &O = R->getAsArrayOffset();
if (!O.getRegion())
return UnknownVal();
if (const TypedValueRegion *baseR =
dyn_cast_or_null<TypedValueRegion>(O.getRegion())) {
QualType baseT = baseR->getValueType();
if (baseT->isScalarType()) {
QualType elemT = R->getElementType();
if (elemT->isScalarType()) {
if (Ctx.getTypeSizeInChars(baseT) >= Ctx.getTypeSizeInChars(elemT)) {
if (const Optional<SVal> &V = getDirectBinding(B, superR)) {
if (SymbolRef parentSym = V->getAsSymbol())
return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
if (V->isUnknownOrUndef())
return *V;
return UnknownVal();
}
}
}
}
}
return getBindingForFieldOrElementCommon(store, R, R->getElementType(),
superR);
}
SVal RegionStoreManager::getBindingForField(Store store,
const FieldRegion* R) {
RegionBindings B = GetRegionBindings(store);
if (const Optional<SVal> &V = getDirectBinding(B, R))
return *V;
QualType Ty = R->getValueType();
return getBindingForFieldOrElementCommon(store, R, Ty, R->getSuperRegion());
}
Optional<SVal>
RegionStoreManager::getBindingForDerivedDefaultValue(RegionBindings B,
const MemRegion *superR,
const TypedValueRegion *R,
QualType Ty) {
if (const Optional<SVal> &D = getDefaultBinding(B, superR)) {
const SVal &val = D.getValue();
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>(val))
return Optional<SVal>();
llvm_unreachable("Unknown default value");
}
return Optional<SVal>();
}
SVal RegionStoreManager::getLazyBinding(const MemRegion *lazyBindingRegion,
Store lazyBindingStore) {
if (const ElementRegion *ER = dyn_cast<ElementRegion>(lazyBindingRegion))
return getBindingForElement(lazyBindingStore, ER);
return getBindingForField(lazyBindingStore,
cast<FieldRegion>(lazyBindingRegion));
}
SVal RegionStoreManager::getBindingForFieldOrElementCommon(Store store,
const TypedValueRegion *R,
QualType Ty,
const MemRegion *superR) {
RegionBindings B = GetRegionBindings(store);
Store lazyBindingStore = NULL;
const MemRegion *lazyBindingRegion = NULL;
llvm::tie(lazyBindingStore, lazyBindingRegion) = GetLazyBinding(B, R, R,
true);
if (lazyBindingRegion)
return getLazyBinding(lazyBindingRegion, lazyBindingStore);
bool hasSymbolicIndex = false;
while (superR) {
if (const Optional<SVal> &D =
getBindingForDerivedDefaultValue(B, superR, R, Ty))
return *D;
if (const ElementRegion *ER = dyn_cast<ElementRegion>(superR)) {
NonLoc index = ER->getIndex();
if (!index.isConstant())
hasSymbolicIndex = true;
}
if (const SubRegion *SR = dyn_cast<SubRegion>(superR)) {
superR = SR->getSuperRegion();
continue;
}
break;
}
if (R->hasStackNonParametersStorage()) {
if (isa<ElementRegion>(R)) {
if (const TypedValueRegion *typedSuperR =
dyn_cast<TypedValueRegion>(superR)) {
if (typedSuperR->getValueType()->isVectorType())
return UnknownVal();
}
}
if (hasSymbolicIndex)
return UnknownVal();
return UndefinedVal();
}
return svalBuilder.getRegionValueSymbolVal(R);
}
SVal RegionStoreManager::getBindingForObjCIvar(Store store,
const ObjCIvarRegion* R) {
RegionBindings B = GetRegionBindings(store);
if (const Optional<SVal> &V = getDirectBinding(B, R))
return *V;
const MemRegion *superR = R->getSuperRegion();
if (const Optional<SVal> &V = getDefaultBinding(B, superR)) {
if (SymbolRef parentSym = V->getAsSymbol())
return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
return UnknownVal();
}
return getBindingForLazySymbol(R);
}
SVal RegionStoreManager::getBindingForVar(Store store, const VarRegion *R) {
RegionBindings B = GetRegionBindings(store);
if (const Optional<SVal> &V = getDirectBinding(B, R))
return *V;
const VarDecl *VD = R->getDecl();
QualType T = VD->getType();
const MemSpaceRegion *MS = R->getMemorySpace();
if (isa<UnknownSpaceRegion>(MS) ||
isa<StackArgumentsSpaceRegion>(MS))
return svalBuilder.getRegionValueSymbolVal(R);
if (isa<GlobalsSpaceRegion>(MS)) {
if (isa<NonStaticGlobalSpaceRegion>(MS)) {
QualType CT = Ctx.getCanonicalType(T);
if (CT.isConstQualified()) {
const Expr *Init = VD->getInit();
if (Init)
if (const IntegerLiteral *IL =
dyn_cast<IntegerLiteral>(Init->IgnoreParenCasts())) {
const nonloc::ConcreteInt &V = svalBuilder.makeIntVal(IL);
return svalBuilder.evalCast(V, Init->getType(), IL->getType());
}
}
if (const Optional<SVal> &V
= getBindingForDerivedDefaultValue(B, MS, R, CT))
return V.getValue();
return svalBuilder.getRegionValueSymbolVal(R);
}
if (T->isIntegerType())
return svalBuilder.makeIntVal(0, T);
if (T->isPointerType())
return svalBuilder.makeNull();
return UnknownVal();
}
return UndefinedVal();
}
SVal RegionStoreManager::getBindingForLazySymbol(const TypedValueRegion *R) {
return svalBuilder.getRegionValueSymbolVal(R);
}
static bool mayHaveLazyBinding(QualType Ty) {
return Ty->isArrayType() || Ty->isStructureOrClassType();
}
SVal RegionStoreManager::getBindingForStruct(Store store,
const TypedValueRegion* R) {
const RecordDecl *RD = R->getValueType()->castAs<RecordType>()->getDecl();
if (RD->field_empty())
return UnknownVal();
QualType FirstFieldType = RD->field_begin()->getType();
if (!mayHaveLazyBinding(FirstFieldType)) {
RegionBindings B = GetRegionBindings(store);
BindingKey K = BindingKey::Make(R, BindingKey::Default);
if (const nonloc::LazyCompoundVal *V =
dyn_cast_or_null<nonloc::LazyCompoundVal>(lookup(B, K))) {
return *V;
}
}
return svalBuilder.makeLazyCompoundVal(StoreRef(store, *this), R);
}
SVal RegionStoreManager::getBindingForArray(Store store,
const TypedValueRegion * R) {
const ConstantArrayType *Ty = Ctx.getAsConstantArrayType(R->getValueType());
assert(Ty && "Only constant array types can have compound bindings.");
if (!mayHaveLazyBinding(Ty->getElementType())) {
RegionBindings B = GetRegionBindings(store);
BindingKey K = BindingKey::Make(R, BindingKey::Default);
if (const nonloc::LazyCompoundVal *V =
dyn_cast_or_null<nonloc::LazyCompoundVal>(lookup(B, K))) {
return *V;
}
}
return svalBuilder.makeLazyCompoundVal(StoreRef(store, *this), R);
}
bool RegionStoreManager::includedInBindings(Store store,
const MemRegion *region) const {
RegionBindings B = GetRegionBindings(store);
region = region->getBaseRegion();
if (B.lookup(region))
return true;
for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI) {
const ClusterBindings &Cluster = RI.getData();
for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end();
CI != CE; ++CI) {
const 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 (isa<loc::MemRegionVal>(L))
if (const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion())
return StoreRef(removeBinding(GetRegionBindings(ST),
R).getRootWithoutRetain(),
*this);
return StoreRef(ST, *this);
}
StoreRef RegionStoreManager::Bind(Store store, Loc L, SVal V) {
if (isa<loc::ConcreteInt>(L))
return StoreRef(store, *this);
const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion();
if (const TypedValueRegion* TR = dyn_cast<TypedValueRegion>(R)) {
QualType Ty = TR->getValueType();
if (Ty->isArrayType())
return BindArray(store, TR, V);
if (Ty->isStructureOrClassType())
return BindStruct(store, TR, V);
if (Ty->isVectorType())
return BindVector(store, TR, V);
}
if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) {
QualType T = SR->getSymbol()->getType();
if (T->isAnyPointerType() || T->isReferenceType())
T = T->getPointeeType();
R = GetElementZeroRegion(SR, T);
}
RegionBindings B = GetRegionBindings(store);
B = removeSubRegionBindings(B, cast<SubRegion>(R));
BindingKey Key = BindingKey::Make(R, BindingKey::Direct);
return StoreRef(addBinding(B, Key, V).getRootWithoutRetain(), *this);
}
StoreRef RegionStoreManager::bindCompoundLiteral(Store ST,
const CompoundLiteralExpr *CL,
const LocationContext *LC,
SVal V) {
return Bind(ST, loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL, LC)), V);
}
StoreRef RegionStoreManager::setImplicitDefaultValue(Store store,
const MemRegion *R,
QualType T) {
RegionBindings B = GetRegionBindings(store);
SVal V;
if (Loc::isLocType(T))
V = svalBuilder.makeNull();
else if (T->isIntegerType())
V = svalBuilder.makeZeroVal(T);
else if (T->isStructureOrClassType() || T->isArrayType()) {
V = svalBuilder.makeZeroVal(Ctx.IntTy);
}
else {
assert(!SymbolManager::canSymbolicate(T) && "This type is representable");
V = UnknownVal();
}
return StoreRef(addBinding(B, R, BindingKey::Default,
V).getRootWithoutRetain(), *this);
}
StoreRef RegionStoreManager::BindArray(Store store, const TypedValueRegion* R,
SVal Init) {
const ArrayType *AT =cast<ArrayType>(Ctx.getCanonicalType(R->getValueType()));
QualType ElementTy = AT->getElementType();
Optional<uint64_t> Size;
if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(AT))
Size = CAT->getSize().getZExtValue();
if (loc::MemRegionVal *MRV = dyn_cast<loc::MemRegionVal>(&Init)) {
const StringRegion *S = cast<StringRegion>(MRV->getRegion());
nonloc::LazyCompoundVal LCV =
cast<nonloc::LazyCompoundVal>(svalBuilder.
makeLazyCompoundVal(StoreRef(store, *this), S));
return BindAggregate(store, R, LCV);
}
if (isa<nonloc::LazyCompoundVal>(Init))
return BindAggregate(store, R, Init);
if (Init.isUnknown())
return setImplicitDefaultValue(store, R, ElementTy);
nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(Init);
nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
uint64_t i = 0;
StoreRef newStore(store, *this);
for (; Size.hasValue() ? i < Size.getValue() : true ; ++i, ++VI) {
if (VI == VE)
break;
const NonLoc &Idx = svalBuilder.makeArrayIndex(i);
const ElementRegion *ER = MRMgr.getElementRegion(ElementTy, Idx, R, Ctx);
if (ElementTy->isStructureOrClassType())
newStore = BindStruct(newStore.getStore(), ER, *VI);
else if (ElementTy->isArrayType())
newStore = BindArray(newStore.getStore(), ER, *VI);
else
newStore = Bind(newStore.getStore(), svalBuilder.makeLoc(ER), *VI);
}
if (Size.hasValue() && i < Size.getValue())
newStore = setImplicitDefaultValue(newStore.getStore(), R, ElementTy);
return newStore;
}
StoreRef RegionStoreManager::BindVector(Store store, const TypedValueRegion* R,
SVal V) {
QualType T = R->getValueType();
assert(T->isVectorType());
const VectorType *VT = T->getAs<VectorType>();
if (isa<nonloc::LazyCompoundVal>(V) || isa<nonloc::SymbolVal>(V))
return BindAggregate(store, R, V);
if (!isa<nonloc::CompoundVal>(V)) {
return BindAggregate(store, R, UnknownVal());
}
QualType ElemType = VT->getElementType();
nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V);
nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
unsigned index = 0, numElements = VT->getNumElements();
StoreRef newStore(store, *this);
for ( ; index != numElements ; ++index) {
if (VI == VE)
break;
NonLoc Idx = svalBuilder.makeArrayIndex(index);
const ElementRegion *ER = MRMgr.getElementRegion(ElemType, Idx, R, Ctx);
if (ElemType->isArrayType())
newStore = BindArray(newStore.getStore(), ER, *VI);
else if (ElemType->isStructureOrClassType())
newStore = BindStruct(newStore.getStore(), ER, *VI);
else
newStore = Bind(newStore.getStore(), svalBuilder.makeLoc(ER), *VI);
}
return newStore;
}
StoreRef RegionStoreManager::BindStruct(Store store, const TypedValueRegion* R,
SVal V) {
if (!Features.supportsFields())
return StoreRef(store, *this);
QualType T = R->getValueType();
assert(T->isStructureOrClassType());
const RecordType* RT = T->getAs<RecordType>();
RecordDecl *RD = RT->getDecl();
if (!RD->isCompleteDefinition())
return StoreRef(store, *this);
if (isa<nonloc::LazyCompoundVal>(V) || isa<nonloc::SymbolVal>(V))
return BindAggregate(store, R, V);
if (V.isUnknown() || !isa<nonloc::CompoundVal>(V))
return BindAggregate(store, R, UnknownVal());
nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V);
nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
RecordDecl::field_iterator FI, FE;
StoreRef newStore(store, *this);
for (FI = RD->field_begin(), FE = RD->field_end(); FI != FE; ++FI) {
if (VI == VE)
break;
if (FI->isUnnamedBitfield())
continue;
QualType FTy = FI->getType();
const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);
if (FTy->isArrayType())
newStore = BindArray(newStore.getStore(), FR, *VI);
else if (FTy->isStructureOrClassType())
newStore = BindStruct(newStore.getStore(), FR, *VI);
else
newStore = Bind(newStore.getStore(), svalBuilder.makeLoc(FR), *VI);
++VI;
}
if (FI != FE) {
RegionBindings B = GetRegionBindings(newStore.getStore());
B = addBinding(B, R, BindingKey::Default, svalBuilder.makeIntVal(0, false));
newStore = StoreRef(B.getRootWithoutRetain(), *this);
}
return newStore;
}
StoreRef RegionStoreManager::BindAggregate(Store store, const TypedRegion *R,
SVal Val) {
RegionBindings B = GetRegionBindings(store);
B = removeSubRegionBindings(B, R);
B = addBinding(B, R, BindingKey::Default, Val);
return StoreRef(B.getRootWithoutRetain(), *this);
}
RegionBindings RegionStoreManager::addBinding(RegionBindings B, BindingKey K,
SVal V) {
const MemRegion *Base = K.getBaseRegion();
const ClusterBindings *ExistingCluster = B.lookup(Base);
ClusterBindings Cluster = (ExistingCluster ? *ExistingCluster
: CBFactory.getEmptyMap());
ClusterBindings NewCluster = CBFactory.add(Cluster, K, V);
return RBFactory.add(B, Base, NewCluster);
}
RegionBindings RegionStoreManager::addBinding(RegionBindings B,
const MemRegion *R,
BindingKey::Kind k, SVal V) {
return addBinding(B, BindingKey::Make(R, k), V);
}
const SVal *RegionStoreManager::lookup(RegionBindings B, BindingKey K) {
const ClusterBindings *Cluster = B.lookup(K.getBaseRegion());
if (!Cluster)
return 0;
return Cluster->lookup(K);
}
const SVal *RegionStoreManager::lookup(RegionBindings B,
const MemRegion *R,
BindingKey::Kind k) {
return lookup(B, BindingKey::Make(R, k));
}
RegionBindings RegionStoreManager::removeBinding(RegionBindings B,
BindingKey K) {
const MemRegion *Base = K.getBaseRegion();
const ClusterBindings *Cluster = B.lookup(Base);
if (!Cluster)
return B;
ClusterBindings NewCluster = CBFactory.remove(*Cluster, K);
if (NewCluster.isEmpty())
return RBFactory.remove(B, Base);
return RBFactory.add(B, Base, NewCluster);
}
RegionBindings RegionStoreManager::removeBinding(RegionBindings B,
const MemRegion *R,
BindingKey::Kind k){
return removeBinding(B, BindingKey::Make(R, k));
}
RegionBindings RegionStoreManager::removeCluster(RegionBindings B,
const MemRegion *Base) {
return RBFactory.remove(B, Base);
}
namespace {
class removeDeadBindingsWorker :
public ClusterAnalysis<removeDeadBindingsWorker> {
SmallVector<const SymbolicRegion*, 12> Postponed;
SymbolReaper &SymReaper;
const StackFrameContext *CurrentLCtx;
public:
removeDeadBindingsWorker(RegionStoreManager &rm,
ProgramStateManager &stateMgr,
RegionBindings b, SymbolReaper &symReaper,
const StackFrameContext *LCtx)
: ClusterAnalysis<removeDeadBindingsWorker>(rm, stateMgr, b,
false),
SymReaper(symReaper), CurrentLCtx(LCtx) {}
void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C);
void VisitCluster(const MemRegion *baseR, const ClusterBindings &C);
bool UpdatePostponed();
void VisitBinding(SVal V);
};
}
void removeDeadBindingsWorker::VisitAddedToCluster(const MemRegion *baseR,
const ClusterBindings &C) {
if (const VarRegion *VR = dyn_cast<VarRegion>(baseR)) {
if (SymReaper.isLive(VR))
AddToWorkList(baseR, &C);
return;
}
if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) {
if (SymReaper.isLive(SR->getSymbol()))
AddToWorkList(SR, &C);
else
Postponed.push_back(SR);
return;
}
if (isa<NonStaticGlobalSpaceRegion>(baseR)) {
AddToWorkList(baseR, &C);
return;
}
if (const CXXThisRegion *TR = dyn_cast<CXXThisRegion>(baseR)) {
const StackArgumentsSpaceRegion *StackReg =
cast<StackArgumentsSpaceRegion>(TR->getSuperRegion());
const StackFrameContext *RegCtx = StackReg->getStackFrame();
if (RegCtx == CurrentLCtx || RegCtx->isParentOf(CurrentLCtx))
AddToWorkList(TR, &C);
}
}
void removeDeadBindingsWorker::VisitCluster(const MemRegion *baseR,
const ClusterBindings &C) {
if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(baseR))
SymReaper.markLive(SymR->getSymbol());
for (ClusterBindings::iterator I = C.begin(), E = C.end(); I != E; ++I)
VisitBinding(I.getData());
}
void removeDeadBindingsWorker::VisitBinding(SVal V) {
if (const nonloc::LazyCompoundVal *LCS =
dyn_cast<nonloc::LazyCompoundVal>(&V)) {
const MemRegion *LazyR = LCS->getRegion();
RegionBindings B = RegionStoreManager::GetRegionBindings(LCS->getStore());
for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){
const ClusterBindings &Cluster = RI.getData();
for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end();
CI != CE; ++CI) {
BindingKey K = CI.getKey();
if (const SubRegion *BaseR = dyn_cast<SubRegion>(K.getRegion())) {
if (BaseR == LazyR)
VisitBinding(CI.getData());
else if (K.hasSymbolicOffset() && BaseR->isSubRegionOf(LazyR))
VisitBinding(CI.getData());
}
}
}
return;
}
if (const MemRegion *R = V.getAsRegion()) {
AddToWorkList(R);
if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(R)) {
BlockDataRegion::referenced_vars_iterator I = BR->referenced_vars_begin(),
E = BR->referenced_vars_end();
for ( ; I != E; ++I)
AddToWorkList(I.getCapturedRegion());
}
}
for (SymExpr::symbol_iterator SI = V.symbol_begin(), SE = V.symbol_end();
SI!=SE; ++SI)
SymReaper.markLive(*SI);
}
bool removeDeadBindingsWorker::UpdatePostponed() {
bool changed = false;
for (SmallVectorImpl<const SymbolicRegion*>::iterator
I = Postponed.begin(), E = Postponed.end() ; I != E ; ++I) {
if (const SymbolicRegion *SR = *I) {
if (SymReaper.isLive(SR->getSymbol())) {
changed |= AddToWorkList(SR);
*I = NULL;
}
}
}
return changed;
}
StoreRef RegionStoreManager::removeDeadBindings(Store store,
const StackFrameContext *LCtx,
SymbolReaper& SymReaper) {
RegionBindings B = GetRegionBindings(store);
removeDeadBindingsWorker W(*this, StateMgr, B, SymReaper, LCtx);
W.GenerateClusters();
for (SymbolReaper::region_iterator I = SymReaper.region_begin(),
E = SymReaper.region_end(); I != E; ++I) {
W.AddToWorkList(*I);
}
do W.RunWorkList(); while (W.UpdatePostponed());
for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) {
const MemRegion *Base = I.getKey();
if (W.isVisited(Base))
continue;
B = removeCluster(B, Base);
if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(Base))
SymReaper.maybeDead(SymR->getSymbol());
const ClusterBindings &Cluster = I.getData();
for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end();
CI != CE; ++CI) {
SVal X = CI.getData();
SymExpr::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
for (; SI != SE; ++SI)
SymReaper.maybeDead(*SI);
}
}
return StoreRef(B.getRootWithoutRetain(), *this);
}
void RegionStoreManager::print(Store store, raw_ostream &OS,
const char* nl, const char *sep) {
RegionBindings B = GetRegionBindings(store);
OS << "Store (direct and default bindings), "
<< (void*) B.getRootWithoutRetain()
<< " :" << nl;
for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) {
const ClusterBindings &Cluster = I.getData();
for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end();
CI != CE; ++CI) {
OS << ' ' << CI.getKey() << " : " << CI.getData() << nl;
}
OS << nl;
}
}