diff options
Diffstat (limited to 'lib/Checker/RegionStore.cpp')
| -rw-r--r-- | lib/Checker/RegionStore.cpp | 1905 |
1 files changed, 1905 insertions, 0 deletions
diff --git a/lib/Checker/RegionStore.cpp b/lib/Checker/RegionStore.cpp new file mode 100644 index 0000000..f70105a --- /dev/null +++ b/lib/Checker/RegionStore.cpp @@ -0,0 +1,1905 @@ +//== RegionStore.cpp - Field-sensitive store model --------------*- C++ -*--==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines a basic region store model. In this model, we do have field +// sensitivity. But we assume nothing about the heap shape. So recursive data +// structures are largely ignored. Basically we do 1-limiting analysis. +// Parameter pointers are assumed with no aliasing. Pointee objects of +// parameters are created lazily. +// +//===----------------------------------------------------------------------===// +#include "clang/Checker/PathSensitive/MemRegion.h" +#include "clang/Analysis/AnalysisContext.h" +#include "clang/Checker/PathSensitive/GRState.h" +#include "clang/Checker/PathSensitive/GRStateTrait.h" +#include "clang/Analysis/Analyses/LiveVariables.h" +#include "clang/Analysis/Support/Optional.h" +#include "clang/Basic/TargetInfo.h" +#include "clang/AST/CharUnits.h" + +#include "llvm/ADT/ImmutableMap.h" +#include "llvm/ADT/ImmutableList.h" +#include "llvm/Support/raw_ostream.h" + +using namespace clang; + +#define USE_EXPLICIT_COMPOUND 0 + +//===----------------------------------------------------------------------===// +// Representation of binding keys. +//===----------------------------------------------------------------------===// + +namespace { +class BindingKey { +public: + enum Kind { Direct = 0x0, Default = 0x1 }; +private: + llvm ::PointerIntPair<const MemRegion*, 1> P; + uint64_t Offset; + + explicit BindingKey(const MemRegion *r, uint64_t offset, Kind k) + : P(r, (unsigned) k), Offset(offset) { assert(r); } +public: + + bool isDefault() const { return P.getInt() == Default; } + bool isDirect() const { return P.getInt() == Direct; } + + const MemRegion *getRegion() const { return P.getPointer(); } + uint64_t getOffset() const { return Offset; } + + void Profile(llvm::FoldingSetNodeID& ID) const { + ID.AddPointer(P.getOpaqueValue()); + ID.AddInteger(Offset); + } + + 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 Offset < X.Offset; + } + + bool operator==(const BindingKey &X) const { + return P.getOpaqueValue() == X.P.getOpaqueValue() && + Offset == X.Offset; + } +}; +} // end anonymous namespace + +namespace llvm { + static inline + llvm::raw_ostream& operator<<(llvm::raw_ostream& os, BindingKey K) { + os << '(' << K.getRegion() << ',' << K.getOffset() + << ',' << (K.isDirect() ? "direct" : "default") + << ')'; + return os; + } +} // end llvm namespace + +//===----------------------------------------------------------------------===// +// Actual Store type. +//===----------------------------------------------------------------------===// + +typedef llvm::ImmutableMap<BindingKey, SVal> RegionBindings; + +//===----------------------------------------------------------------------===// +// Fine-grained control of RegionStoreManager. +//===----------------------------------------------------------------------===// + +namespace { +struct minimal_features_tag {}; +struct maximal_features_tag {}; + +class RegionStoreFeatures { + bool SupportsFields; + bool SupportsRemaining; + +public: + RegionStoreFeatures(minimal_features_tag) : + SupportsFields(false), SupportsRemaining(false) {} + + RegionStoreFeatures(maximal_features_tag) : + SupportsFields(true), SupportsRemaining(false) {} + + void enableFields(bool t) { SupportsFields = t; } + + bool supportsFields() const { return SupportsFields; } + bool supportsRemaining() const { return SupportsRemaining; } +}; +} + +//===----------------------------------------------------------------------===// +// Region "Extents" +//===----------------------------------------------------------------------===// +// +// MemRegions represent chunks of memory with a size (their "extent"). This +// GDM entry tracks the extents for regions. Extents are in bytes. +// +namespace { class RegionExtents {}; } +static int RegionExtentsIndex = 0; +namespace clang { + template<> struct GRStateTrait<RegionExtents> + : public GRStatePartialTrait<llvm::ImmutableMap<const MemRegion*, SVal> > { + static void* GDMIndex() { return &RegionExtentsIndex; } + }; +} + +//===----------------------------------------------------------------------===// +// Utility functions. +//===----------------------------------------------------------------------===// + +static bool IsAnyPointerOrIntptr(QualType ty, ASTContext &Ctx) { + if (ty->isAnyPointerType()) + return true; + + return ty->isIntegerType() && ty->isScalarType() && + Ctx.getTypeSize(ty) == Ctx.getTypeSize(Ctx.VoidPtrTy); +} + +//===----------------------------------------------------------------------===// +// Main RegionStore logic. +//===----------------------------------------------------------------------===// + +namespace { + +class RegionStoreSubRegionMap : public SubRegionMap { +public: + typedef llvm::ImmutableSet<const MemRegion*> Set; + typedef llvm::DenseMap<const MemRegion*, Set> Map; +private: + Set::Factory F; + Map M; +public: + bool add(const MemRegion* Parent, const MemRegion* SubRegion) { + Map::iterator I = M.find(Parent); + + if (I == M.end()) { + M.insert(std::make_pair(Parent, F.Add(F.GetEmptySet(), SubRegion))); + return true; + } + + I->second = F.Add(I->second, SubRegion); + return false; + } + + void process(llvm::SmallVectorImpl<const SubRegion*> &WL, const SubRegion *R); + + ~RegionStoreSubRegionMap() {} + + const Set *getSubRegions(const MemRegion *Parent) const { + Map::const_iterator I = M.find(Parent); + return I == M.end() ? NULL : &I->second; + } + + bool iterSubRegions(const MemRegion* Parent, Visitor& V) const { + Map::const_iterator I = M.find(Parent); + + if (I == M.end()) + return true; + + Set S = I->second; + for (Set::iterator SI=S.begin(),SE=S.end(); SI != SE; ++SI) { + if (!V.Visit(Parent, *SI)) + return false; + } + + return true; + } +}; + + +class RegionStoreManager : public StoreManager { + const RegionStoreFeatures Features; + RegionBindings::Factory RBFactory; + + typedef llvm::DenseMap<Store, RegionStoreSubRegionMap*> SMCache; + SMCache SC; + +public: + RegionStoreManager(GRStateManager& mgr, const RegionStoreFeatures &f) + : StoreManager(mgr), + Features(f), + RBFactory(mgr.getAllocator()) {} + + virtual ~RegionStoreManager() { + for (SMCache::iterator I = SC.begin(), E = SC.end(); I != E; ++I) + delete (*I).second; + } + + SubRegionMap *getSubRegionMap(Store store) { + return getRegionStoreSubRegionMap(store); + } + + RegionStoreSubRegionMap *getRegionStoreSubRegionMap(Store store); + + Optional<SVal> getBinding(RegionBindings B, const MemRegion *R); + Optional<SVal> getDirectBinding(RegionBindings B, const MemRegion *R); + /// getDefaultBinding - Returns an SVal* representing an optional default + /// binding associated with a region and its subregions. + Optional<SVal> getDefaultBinding(RegionBindings B, const MemRegion *R); + + /// setImplicitDefaultValue - Set the default binding for the provided + /// MemRegion to the value implicitly defined for compound literals when + /// the value is not specified. + Store setImplicitDefaultValue(Store store, const MemRegion *R, QualType T); + + /// ArrayToPointer - Emulates the "decay" of an array to a pointer + /// type. 'Array' represents the lvalue of the array being decayed + /// to a pointer, and the returned SVal represents the decayed + /// version of that lvalue (i.e., a pointer to the first element of + /// the array). This is called by GRExprEngine when evaluating + /// casts from arrays to pointers. + SVal ArrayToPointer(Loc Array); + + SVal EvalBinOp(BinaryOperator::Opcode Op,Loc L, NonLoc R, QualType resultTy); + + Store getInitialStore(const LocationContext *InitLoc) { + return RBFactory.GetEmptyMap().getRoot(); + } + + //===-------------------------------------------------------------------===// + // Binding values to regions. + //===-------------------------------------------------------------------===// + + Store InvalidateRegion(Store store, const MemRegion *R, const Expr *E, + unsigned Count, InvalidatedSymbols *IS) { + return RegionStoreManager::InvalidateRegions(store, &R, &R+1, E, Count, IS); + } + + Store InvalidateRegions(Store store, + const MemRegion * const *Begin, + const MemRegion * const *End, + const Expr *E, unsigned Count, + InvalidatedSymbols *IS); + +public: // Made public for helper classes. + + void RemoveSubRegionBindings(RegionBindings &B, const MemRegion *R, + RegionStoreSubRegionMap &M); + + RegionBindings Add(RegionBindings B, BindingKey K, SVal V); + + RegionBindings Add(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 Remove(RegionBindings B, BindingKey K); + RegionBindings Remove(RegionBindings B, const MemRegion *R, + BindingKey::Kind k); + + RegionBindings Remove(RegionBindings B, const MemRegion *R) { + return Remove(Remove(B, R, BindingKey::Direct), R, BindingKey::Default); + } + + Store Remove(Store store, BindingKey K); + +public: // Part of public interface to class. + + Store Bind(Store store, Loc LV, SVal V); + + Store BindCompoundLiteral(Store store, const CompoundLiteralExpr* CL, + const LocationContext *LC, SVal V); + + Store BindDecl(Store store, const VarRegion *VR, SVal InitVal); + + Store BindDeclWithNoInit(Store store, const VarRegion *) { + return store; + } + + /// BindStruct - Bind a compound value to a structure. + Store BindStruct(Store store, const TypedRegion* R, SVal V); + + Store BindArray(Store store, const TypedRegion* R, SVal V); + + /// KillStruct - Set the entire struct to unknown. + Store KillStruct(Store store, const TypedRegion* R); + + Store Remove(Store store, Loc LV); + + + //===------------------------------------------------------------------===// + // Loading values from regions. + //===------------------------------------------------------------------===// + + /// The high level logic for this method is this: + /// Retrieve (L) + /// if L has binding + /// return L's binding + /// else if L is in killset + /// return unknown + /// else + /// if L is on stack or heap + /// return undefined + /// else + /// return symbolic + SVal Retrieve(Store store, Loc L, QualType T = QualType()); + + SVal RetrieveElement(Store store, const ElementRegion *R); + + SVal RetrieveField(Store store, const FieldRegion *R); + + SVal RetrieveObjCIvar(Store store, const ObjCIvarRegion *R); + + SVal RetrieveVar(Store store, const VarRegion *R); + + SVal RetrieveLazySymbol(const TypedRegion *R); + + SVal RetrieveFieldOrElementCommon(Store store, const TypedRegion *R, + QualType Ty, const MemRegion *superR); + + /// Retrieve the values in a struct and return a CompoundVal, used when doing + /// struct copy: + /// struct s x, y; + /// x = y; + /// y's value is retrieved by this method. + SVal RetrieveStruct(Store store, const TypedRegion* R); + + SVal RetrieveArray(Store store, const TypedRegion* R); + + /// Get the state and region whose binding this region R corresponds to. + std::pair<Store, const MemRegion*> + GetLazyBinding(RegionBindings B, const MemRegion *R); + + Store CopyLazyBindings(nonloc::LazyCompoundVal V, Store store, + const TypedRegion *R); + + const ElementRegion *GetElementZeroRegion(const MemRegion *R, QualType T); + + //===------------------------------------------------------------------===// + // State pruning. + //===------------------------------------------------------------------===// + + /// RemoveDeadBindings - Scans the RegionStore of 'state' for dead values. + /// It returns a new Store with these values removed. + Store RemoveDeadBindings(Store store, Stmt* Loc, SymbolReaper& SymReaper, + llvm::SmallVectorImpl<const MemRegion*>& RegionRoots); + + const GRState *EnterStackFrame(const GRState *state, + const StackFrameContext *frame); + + //===------------------------------------------------------------------===// + // Region "extents". + //===------------------------------------------------------------------===// + + const GRState *setExtent(const GRState *state,const MemRegion* R,SVal Extent); + DefinedOrUnknownSVal getSizeInElements(const GRState *state, + const MemRegion* R, QualType EleTy); + + //===------------------------------------------------------------------===// + // Utility methods. + //===------------------------------------------------------------------===// + + static inline RegionBindings GetRegionBindings(Store store) { + return RegionBindings(static_cast<const RegionBindings::TreeTy*>(store)); + } + + void print(Store store, llvm::raw_ostream& Out, const char* nl, + const char *sep); + + void iterBindings(Store store, BindingsHandler& f) { + // FIXME: Implement. + } + + // FIXME: Remove. + BasicValueFactory& getBasicVals() { + return StateMgr.getBasicVals(); + } + + // FIXME: Remove. + ASTContext& getContext() { return StateMgr.getContext(); } +}; + +} // end anonymous namespace + +//===----------------------------------------------------------------------===// +// RegionStore creation. +//===----------------------------------------------------------------------===// + +StoreManager *clang::CreateRegionStoreManager(GRStateManager& StMgr) { + RegionStoreFeatures F = maximal_features_tag(); + return new RegionStoreManager(StMgr, F); +} + +StoreManager *clang::CreateFieldsOnlyRegionStoreManager(GRStateManager &StMgr) { + RegionStoreFeatures F = minimal_features_tag(); + F.enableFields(true); + return new RegionStoreManager(StMgr, F); +} + +void +RegionStoreSubRegionMap::process(llvm::SmallVectorImpl<const SubRegion*> &WL, + const SubRegion *R) { + const MemRegion *superR = R->getSuperRegion(); + if (add(superR, R)) + if (const SubRegion *sr = dyn_cast<SubRegion>(superR)) + WL.push_back(sr); +} + +RegionStoreSubRegionMap* +RegionStoreManager::getRegionStoreSubRegionMap(Store store) { + RegionBindings B = GetRegionBindings(store); + RegionStoreSubRegionMap *M = new RegionStoreSubRegionMap(); + + llvm::SmallVector<const SubRegion*, 10> WL; + + for (RegionBindings::iterator I=B.begin(), E=B.end(); I!=E; ++I) + if (const SubRegion *R = dyn_cast<SubRegion>(I.getKey().getRegion())) + M->process(WL, R); + + // We also need to record in the subregion map "intermediate" regions that + // don't have direct bindings but are super regions of those that do. + while (!WL.empty()) { + const SubRegion *R = WL.back(); + WL.pop_back(); + M->process(WL, R); + } + + return M; +} + +//===----------------------------------------------------------------------===// +// Binding invalidation. +//===----------------------------------------------------------------------===// + +void RegionStoreManager::RemoveSubRegionBindings(RegionBindings &B, + const MemRegion *R, + RegionStoreSubRegionMap &M) { + + if (const RegionStoreSubRegionMap::Set *S = M.getSubRegions(R)) + for (RegionStoreSubRegionMap::Set::iterator I = S->begin(), E = S->end(); + I != E; ++I) + RemoveSubRegionBindings(B, *I, M); + + B = Remove(B, R); +} + +namespace { +class InvalidateRegionsWorker { + typedef BumpVector<BindingKey> RegionCluster; + typedef llvm::DenseMap<const MemRegion *, RegionCluster *> ClusterMap; + typedef llvm::SmallVector<std::pair<const MemRegion *,RegionCluster*>, 10> + WorkList; + + BumpVectorContext BVC; + ClusterMap ClusterM; + WorkList WL; + + RegionStoreManager &RM; + StoreManager::InvalidatedSymbols *IS; + ASTContext &Ctx; + ValueManager &ValMgr; + +public: + InvalidateRegionsWorker(RegionStoreManager &rm, + StoreManager::InvalidatedSymbols *is, + ASTContext &ctx, ValueManager &valMgr) + : RM(rm), IS(is), Ctx(ctx), ValMgr(valMgr) {} + + Store InvalidateRegions(Store store, const MemRegion * const *I, + const MemRegion * const *E, + const Expr *Ex, unsigned Count); + +private: + void AddToWorkList(BindingKey K); + void AddToWorkList(const MemRegion *R); + void AddToCluster(BindingKey K); + RegionCluster **getCluster(const MemRegion *R); + void VisitBinding(SVal V); +}; +} + +void InvalidateRegionsWorker::AddToCluster(BindingKey K) { + const MemRegion *R = K.getRegion(); + const MemRegion *baseR = R->getBaseRegion(); + RegionCluster **CPtr = getCluster(baseR); + assert(*CPtr); + (*CPtr)->push_back(K, BVC); +} + +void InvalidateRegionsWorker::AddToWorkList(BindingKey K) { + AddToWorkList(K.getRegion()); +} + +void InvalidateRegionsWorker::AddToWorkList(const MemRegion *R) { + const MemRegion *baseR = R->getBaseRegion(); + RegionCluster **CPtr = getCluster(baseR); + if (RegionCluster *C = *CPtr) { + WL.push_back(std::make_pair(baseR, C)); + *CPtr = NULL; + } +} + +InvalidateRegionsWorker::RegionCluster ** +InvalidateRegionsWorker::getCluster(const MemRegion *R) { + RegionCluster *&CRef = ClusterM[R]; + if (!CRef) { + void *Mem = BVC.getAllocator().Allocate<RegionCluster>(); + CRef = new (Mem) RegionCluster(BVC, 10); + } + return &CRef; +} + +void InvalidateRegionsWorker::VisitBinding(SVal V) { + // A symbol? Mark it touched by the invalidation. + if (IS) + if (SymbolRef Sym = V.getAsSymbol()) + IS->insert(Sym); + + if (const MemRegion *R = V.getAsRegion()) { + AddToWorkList(R); + return; + } + + // Is it a LazyCompoundVal? All references get invalidated as well. + 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 MemRegion *baseR = RI.getKey().getRegion(); + if (cast<SubRegion>(baseR)->isSubRegionOf(LazyR)) + VisitBinding(RI.getData()); + } + + return; + } +} + +Store InvalidateRegionsWorker::InvalidateRegions(Store store, + const MemRegion * const *I, + const MemRegion * const *E, + const Expr *Ex, unsigned Count) +{ + RegionBindings B = RegionStoreManager::GetRegionBindings(store); + + // Scan the entire store and make the region clusters. + for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI) { + AddToCluster(RI.getKey()); + if (const MemRegion *R = RI.getData().getAsRegion()) { + // Generate a cluster, but don't add the region to the cluster + // if there aren't any bindings. + getCluster(R->getBaseRegion()); + } + } + + // Add the cluster for I .. E to a worklist. + for ( ; I != E; ++I) + AddToWorkList(*I); + + while (!WL.empty()) { + const MemRegion *baseR; + RegionCluster *C; + llvm::tie(baseR, C) = WL.back(); + WL.pop_back(); + + for (RegionCluster::iterator I = C->begin(), E = C->end(); I != E; ++I) { + BindingKey K = *I; + + // Get the old binding. Is it a region? If so, add it to the worklist. + if (const SVal *V = RM.Lookup(B, K)) + VisitBinding(*V); + + B = RM.Remove(B, K); + } + + // Now inspect the base region. + + if (IS) { + // Symbolic region? Mark that symbol touched by the invalidation. + if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) + IS->insert(SR->getSymbol()); + } + + // BlockDataRegion? If so, invalidate captured variables that are passed + // by reference. + 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); + } + continue; + } + + if (isa<AllocaRegion>(baseR) || isa<SymbolicRegion>(baseR)) { + // Invalidate the region by setting its default value to + // conjured symbol. The type of the symbol is irrelavant. + DefinedOrUnknownSVal V = ValMgr.getConjuredSymbolVal(baseR, Ex, Ctx.IntTy, + Count); + B = RM.Add(B, baseR, BindingKey::Default, V); + continue; + } + + if (!baseR->isBoundable()) + continue; + + const TypedRegion *TR = cast<TypedRegion>(baseR); + QualType T = TR->getValueType(Ctx); + + // Invalidate the binding. + if (const RecordType *RT = T->getAsStructureType()) { + const RecordDecl *RD = RT->getDecl()->getDefinition(); + // No record definition. There is nothing we can do. + if (!RD) { + B = RM.Remove(B, baseR); + continue; + } + + // Invalidate the region by setting its default value to + // conjured symbol. The type of the symbol is irrelavant. + DefinedOrUnknownSVal V = ValMgr.getConjuredSymbolVal(baseR, Ex, Ctx.IntTy, + Count); + B = RM.Add(B, baseR, BindingKey::Default, V); + continue; + } + + if (const ArrayType *AT = Ctx.getAsArrayType(T)) { + // Set the default value of the array to conjured symbol. + DefinedOrUnknownSVal V = + ValMgr.getConjuredSymbolVal(baseR, Ex, AT->getElementType(), Count); + B = RM.Add(B, baseR, BindingKey::Default, V); + continue; + } + + DefinedOrUnknownSVal V = ValMgr.getConjuredSymbolVal(baseR, Ex, T, Count); + assert(SymbolManager::canSymbolicate(T) || V.isUnknown()); + B = RM.Add(B, baseR, BindingKey::Direct, V); + } + + // Create a new state with the updated bindings. + return B.getRoot(); +} + +Store RegionStoreManager::InvalidateRegions(Store store, + const MemRegion * const *I, + const MemRegion * const *E, + const Expr *Ex, unsigned Count, + InvalidatedSymbols *IS) { + InvalidateRegionsWorker W(*this, IS, getContext(), + StateMgr.getValueManager()); + return W.InvalidateRegions(store, I, E, Ex, Count); +} + +//===----------------------------------------------------------------------===// +// Extents for regions. +//===----------------------------------------------------------------------===// + +DefinedOrUnknownSVal RegionStoreManager::getSizeInElements(const GRState *state, + const MemRegion *R, + QualType EleTy) { + + switch (R->getKind()) { + case MemRegion::CXXThisRegionKind: + assert(0 && "Cannot get size of 'this' region"); + case MemRegion::GenericMemSpaceRegionKind: + case MemRegion::StackLocalsSpaceRegionKind: + case MemRegion::StackArgumentsSpaceRegionKind: + case MemRegion::HeapSpaceRegionKind: + case MemRegion::GlobalsSpaceRegionKind: + case MemRegion::UnknownSpaceRegionKind: + assert(0 && "Cannot index into a MemSpace"); + return UnknownVal(); + + case MemRegion::FunctionTextRegionKind: + case MemRegion::BlockTextRegionKind: + case MemRegion::BlockDataRegionKind: + // Technically this can happen if people do funny things with casts. + return UnknownVal(); + + // Not yet handled. + case MemRegion::AllocaRegionKind: + case MemRegion::CompoundLiteralRegionKind: + case MemRegion::ElementRegionKind: + case MemRegion::FieldRegionKind: + case MemRegion::ObjCIvarRegionKind: + case MemRegion::CXXObjectRegionKind: + return UnknownVal(); + + case MemRegion::SymbolicRegionKind: { + const SVal *Size = state->get<RegionExtents>(R); + if (!Size) + return UnknownVal(); + const nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(Size); + if (!CI) + return UnknownVal(); + + CharUnits RegionSize = + CharUnits::fromQuantity(CI->getValue().getSExtValue()); + CharUnits EleSize = getContext().getTypeSizeInChars(EleTy); + assert(RegionSize % EleSize == 0); + + return ValMgr.makeIntVal(RegionSize / EleSize, false); + } + + case MemRegion::StringRegionKind: { + const StringLiteral* Str = cast<StringRegion>(R)->getStringLiteral(); + // We intentionally made the size value signed because it participates in + // operations with signed indices. + return ValMgr.makeIntVal(Str->getByteLength()+1, false); + } + + case MemRegion::VarRegionKind: { + const VarRegion* VR = cast<VarRegion>(R); + // Get the type of the variable. + QualType T = VR->getDesugaredValueType(getContext()); + + // FIXME: Handle variable-length arrays. + if (isa<VariableArrayType>(T)) + return UnknownVal(); + + if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(T)) { + // return the size as signed integer. + return ValMgr.makeIntVal(CAT->getSize(), false); + } + + // Clients can use ordinary variables as if they were arrays. These + // essentially are arrays of size 1. + return ValMgr.makeIntVal(1, false); + } + } + + assert(0 && "Unreachable"); + return UnknownVal(); +} + +const GRState *RegionStoreManager::setExtent(const GRState *state, + const MemRegion *region, + SVal extent) { + return state->set<RegionExtents>(region, extent); +} + +//===----------------------------------------------------------------------===// +// Location and region casting. +//===----------------------------------------------------------------------===// + +/// ArrayToPointer - Emulates the "decay" of an array to a pointer +/// type. 'Array' represents the lvalue of the array being decayed +/// to a pointer, and the returned SVal represents the decayed +/// version of that lvalue (i.e., a pointer to the first element of +/// the array). This is called by GRExprEngine when evaluating casts +/// from arrays to pointers. +SVal RegionStoreManager::ArrayToPointer(Loc Array) { + if (!isa<loc::MemRegionVal>(Array)) + return UnknownVal(); + + const MemRegion* R = cast<loc::MemRegionVal>(&Array)->getRegion(); + const TypedRegion* ArrayR = dyn_cast<TypedRegion>(R); + + if (!ArrayR) + return UnknownVal(); + + // Strip off typedefs from the ArrayRegion's ValueType. + QualType T = ArrayR->getValueType(getContext()).getDesugaredType(); + ArrayType *AT = cast<ArrayType>(T); + T = AT->getElementType(); + + SVal ZeroIdx = ValMgr.makeZeroArrayIndex(); + return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, ArrayR, + getContext())); +} + +//===----------------------------------------------------------------------===// +// Pointer arithmetic. +//===----------------------------------------------------------------------===// + +SVal RegionStoreManager::EvalBinOp(BinaryOperator::Opcode Op, Loc L, NonLoc R, + QualType resultTy) { + // Assume the base location is MemRegionVal. + if (!isa<loc::MemRegionVal>(L)) + return UnknownVal(); + + const MemRegion* MR = cast<loc::MemRegionVal>(L).getRegion(); + const ElementRegion *ER = 0; + + switch (MR->getKind()) { + case MemRegion::SymbolicRegionKind: { + const SymbolicRegion *SR = cast<SymbolicRegion>(MR); + SymbolRef Sym = SR->getSymbol(); + QualType T = Sym->getType(getContext()); + QualType EleTy; + + if (const PointerType *PT = T->getAs<PointerType>()) + EleTy = PT->getPointeeType(); + else + EleTy = T->getAs<ObjCObjectPointerType>()->getPointeeType(); + + SVal ZeroIdx = ValMgr.makeZeroArrayIndex(); + ER = MRMgr.getElementRegion(EleTy, ZeroIdx, SR, getContext()); + break; + } + case MemRegion::AllocaRegionKind: { + const AllocaRegion *AR = cast<AllocaRegion>(MR); + QualType T = getContext().CharTy; // Create an ElementRegion of bytes. + QualType EleTy = T->getAs<PointerType>()->getPointeeType(); + SVal ZeroIdx = ValMgr.makeZeroArrayIndex(); + ER = MRMgr.getElementRegion(EleTy, ZeroIdx, AR, getContext()); + break; + } + + case MemRegion::ElementRegionKind: { + ER = cast<ElementRegion>(MR); + break; + } + + // Not yet handled. + case MemRegion::VarRegionKind: + case MemRegion::StringRegionKind: { + + } + // Fall-through. + case MemRegion::CompoundLiteralRegionKind: + case MemRegion::FieldRegionKind: + case MemRegion::ObjCIvarRegionKind: + case MemRegion::CXXObjectRegionKind: + return UnknownVal(); + + case MemRegion::FunctionTextRegionKind: + case MemRegion::BlockTextRegionKind: + case MemRegion::BlockDataRegionKind: + // Technically this can happen if people do funny things with casts. + return UnknownVal(); + + case MemRegion::CXXThisRegionKind: + assert(0 && + "Cannot perform pointer arithmetic on implicit argument 'this'"); + case MemRegion::GenericMemSpaceRegionKind: + case MemRegion::StackLocalsSpaceRegionKind: + case MemRegion::StackArgumentsSpaceRegionKind: + case MemRegion::HeapSpaceRegionKind: + case MemRegion::GlobalsSpaceRegionKind: + case MemRegion::UnknownSpaceRegionKind: + assert(0 && "Cannot perform pointer arithmetic on a MemSpace"); + return UnknownVal(); + } + + SVal Idx = ER->getIndex(); + nonloc::ConcreteInt* Base = dyn_cast<nonloc::ConcreteInt>(&Idx); + + // For now, only support: + // (a) concrete integer indices that can easily be resolved + // (b) 0 + symbolic index + if (Base) { + if (nonloc::ConcreteInt *Offset = dyn_cast<nonloc::ConcreteInt>(&R)) { + // FIXME: Should use SValuator here. + SVal NewIdx = + Base->evalBinOp(ValMgr, Op, + cast<nonloc::ConcreteInt>(ValMgr.convertToArrayIndex(*Offset))); + const MemRegion* NewER = + MRMgr.getElementRegion(ER->getElementType(), NewIdx, + ER->getSuperRegion(), getContext()); + return ValMgr.makeLoc(NewER); + } + if (0 == Base->getValue()) { + const MemRegion* NewER = + MRMgr.getElementRegion(ER->getElementType(), R, + ER->getSuperRegion(), getContext()); + return ValMgr.makeLoc(NewER); + } + } + + return UnknownVal(); +} + +//===----------------------------------------------------------------------===// +// Loading values from regions. +//===----------------------------------------------------------------------===// + +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 TypedRegion *TR = dyn_cast<TypedRegion>(R)) + if (TR->getValueType(getContext())->isUnionType()) + return UnknownVal(); + + if (const SVal *V = Lookup(B, R, BindingKey::Default)) + return *V; + + return Optional<SVal>(); +} + +Optional<SVal> RegionStoreManager::getBinding(RegionBindings B, + const MemRegion *R) { + + if (Optional<SVal> V = getDirectBinding(B, R)) + return V; + + return getDefaultBinding(B, R); +} + +static bool IsReinterpreted(QualType RTy, QualType UsedTy, ASTContext &Ctx) { + RTy = Ctx.getCanonicalType(RTy); + UsedTy = Ctx.getCanonicalType(UsedTy); + + if (RTy == UsedTy) + return false; + + + // Recursively check the types. We basically want to see if a pointer value + // is ever reinterpreted as a non-pointer, e.g. void** and intptr_t* + // represents a reinterpretation. + if (Loc::IsLocType(RTy) && Loc::IsLocType(UsedTy)) { + const PointerType *PRTy = RTy->getAs<PointerType>(); + const PointerType *PUsedTy = UsedTy->getAs<PointerType>(); + + return PUsedTy && PRTy && + IsReinterpreted(PRTy->getPointeeType(), + PUsedTy->getPointeeType(), Ctx); + } + + return true; +} + +const ElementRegion * +RegionStoreManager::GetElementZeroRegion(const MemRegion *R, QualType T) { + ASTContext &Ctx = getContext(); + SVal idx = ValMgr.makeZeroArrayIndex(); + assert(!T.isNull()); + return MRMgr.getElementRegion(T, idx, R, Ctx); +} + +SVal RegionStoreManager::Retrieve(Store store, Loc L, QualType T) { + assert(!isa<UnknownVal>(L) && "location unknown"); + assert(!isa<UndefinedVal>(L) && "location undefined"); + + // FIXME: Is this even possible? Shouldn't this be treated as a null + // dereference at a higher level? + if (isa<loc::ConcreteInt>(L)) + return UndefinedVal(); + + const MemRegion *MR = cast<loc::MemRegionVal>(L).getRegion(); + + if (isa<AllocaRegion>(MR) || isa<SymbolicRegion>(MR)) + MR = GetElementZeroRegion(MR, T); + + if (isa<CodeTextRegion>(MR)) + return UnknownVal(); + + // FIXME: Perhaps this method should just take a 'const MemRegion*' argument + // instead of 'Loc', and have the other Loc cases handled at a higher level. + const TypedRegion *R = cast<TypedRegion>(MR); + QualType RTy = R->getValueType(getContext()); + + // FIXME: We should eventually handle funny addressing. e.g.: + // + // int x = ...; + // int *p = &x; + // char *q = (char*) p; + // char c = *q; // returns the first byte of 'x'. + // + // Such funny addressing will occur due to layering of regions. + +#if 0 + ASTContext &Ctx = getContext(); + if (!T.isNull() && IsReinterpreted(RTy, T, Ctx)) { + SVal ZeroIdx = ValMgr.makeZeroArrayIndex(); + R = MRMgr.getElementRegion(T, ZeroIdx, R, Ctx); + RTy = T; + assert(Ctx.getCanonicalType(RTy) == + Ctx.getCanonicalType(R->getValueType(Ctx))); + } +#endif + + if (RTy->isStructureType()) + return RetrieveStruct(store, R); + + // FIXME: Handle unions. + if (RTy->isUnionType()) + return UnknownVal(); + + if (RTy->isArrayType()) + return RetrieveArray(store, R); + + // FIXME: handle Vector types. + if (RTy->isVectorType()) + return UnknownVal(); + + if (const FieldRegion* FR = dyn_cast<FieldRegion>(R)) + return CastRetrievedVal(RetrieveField(store, FR), FR, T, false); + + if (const ElementRegion* ER = dyn_cast<ElementRegion>(R)) { + // FIXME: Here we actually perform an implicit conversion from the loaded + // value to the element type. Eventually we want to compose these values + // more intelligently. For example, an 'element' can encompass multiple + // bound regions (e.g., several bound bytes), or could be a subset of + // a larger value. + return CastRetrievedVal(RetrieveElement(store, ER), ER, T, false); + } + + if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) { + // FIXME: Here we actually perform an implicit conversion from the loaded + // value to the ivar type. What we should model is stores to ivars + // that blow past the extent of the ivar. If the address of the ivar is + // reinterpretted, it is possible we stored a different value that could + // fit within the ivar. Either we need to cast these when storing them + // or reinterpret them lazily (as we do here). + return CastRetrievedVal(RetrieveObjCIvar(store, IVR), IVR, T, false); + } + + if (const VarRegion *VR = dyn_cast<VarRegion>(R)) { + // FIXME: Here we actually perform an implicit conversion from the loaded + // value to the variable type. What we should model is stores to variables + // that blow past the extent of the variable. If the address of the + // variable is reinterpretted, it is possible we stored a different value + // that could fit within the variable. Either we need to cast these when + // storing them or reinterpret them lazily (as we do here). + return CastRetrievedVal(RetrieveVar(store, VR), VR, T, false); + } + + RegionBindings B = GetRegionBindings(store); + const SVal *V = Lookup(B, R, BindingKey::Direct); + + // Check if the region has a binding. + if (V) + return *V; + + // The location does not have a bound value. This means that it has + // the value it had upon its creation and/or entry to the analyzed + // function/method. These are either symbolic values or 'undefined'. + if (R->hasStackNonParametersStorage()) { + // All stack variables are considered to have undefined values + // upon creation. All heap allocated blocks are considered to + // have undefined values as well unless they are explicitly bound + // to specific values. + return UndefinedVal(); + } + + // All other values are symbolic. + return ValMgr.getRegionValueSymbolVal(R, RTy); +} + +std::pair<Store, const MemRegion *> +RegionStoreManager::GetLazyBinding(RegionBindings B, const MemRegion *R) { + if (Optional<SVal> OV = getDirectBinding(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()); + + 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()); + + if (X.second) + return std::make_pair(X.first, + MRMgr.getFieldRegionWithSuper(FR, X.second)); + } + // The NULL MemRegion indicates an non-existent lazy binding. A NULL Store is + // possible for a valid lazy binding. + return std::make_pair((Store) 0, (const MemRegion *) 0); +} + +SVal RegionStoreManager::RetrieveElement(Store store, + const ElementRegion* R) { + // Check if the region has a binding. + RegionBindings B = GetRegionBindings(store); + if (Optional<SVal> V = getDirectBinding(B, R)) + return *V; + + const MemRegion* superR = R->getSuperRegion(); + + // Check if the region is an element region of a string literal. + if (const StringRegion *StrR=dyn_cast<StringRegion>(superR)) { + // FIXME: Handle loads from strings where the literal is treated as + // an integer, e.g., *((unsigned int*)"hello") + ASTContext &Ctx = getContext(); + QualType T = Ctx.getAsArrayType(StrR->getValueType(Ctx))->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(); + int64_t byteLength = Str->getByteLength(); + if (i > byteLength) { + // Buffer overflow checking in GRExprEngine should handle this case, + // but we shouldn't rely on it to not overflow here if that checking + // is disabled. + return UnknownVal(); + } + char c = (i == byteLength) ? '\0' : Str->getStrData()[i]; + return ValMgr.makeIntVal(c, T); + } + } + + // Check if the immediate super region has a direct binding. + if (Optional<SVal> V = getDirectBinding(B, superR)) { + if (SymbolRef parentSym = V->getAsSymbol()) + return ValMgr.getDerivedRegionValueSymbolVal(parentSym, R); + + if (V->isUnknownOrUndef()) + return *V; + + // Handle LazyCompoundVals for the immediate super region. Other cases + // are handled in 'RetrieveFieldOrElementCommon'. + if (const nonloc::LazyCompoundVal *LCV = + dyn_cast<nonloc::LazyCompoundVal>(V)) { + + R = MRMgr.getElementRegionWithSuper(R, LCV->getRegion()); + return RetrieveElement(LCV->getStore(), R); + } + + // Other cases: give up. + return UnknownVal(); + } + + return RetrieveFieldOrElementCommon(store, R, R->getElementType(), superR); +} + +SVal RegionStoreManager::RetrieveField(Store store, + const FieldRegion* R) { + + // Check if the region has a binding. + RegionBindings B = GetRegionBindings(store); + if (Optional<SVal> V = getDirectBinding(B, R)) + return *V; + + QualType Ty = R->getValueType(getContext()); + return RetrieveFieldOrElementCommon(store, R, Ty, R->getSuperRegion()); +} + +SVal RegionStoreManager::RetrieveFieldOrElementCommon(Store store, + const TypedRegion *R, + QualType Ty, + const MemRegion *superR) { + + // At this point we have already checked in either RetrieveElement or + // RetrieveField if 'R' has a direct binding. + + RegionBindings B = GetRegionBindings(store); + + while (superR) { + if (const Optional<SVal> &D = getDefaultBinding(B, superR)) { + if (SymbolRef parentSym = D->getAsSymbol()) + return ValMgr.getDerivedRegionValueSymbolVal(parentSym, R); + + if (D->isZeroConstant()) + return ValMgr.makeZeroVal(Ty); + + if (D->isUnknown()) + return *D; + + assert(0 && "Unknown default value"); + } + + // If our super region is a field or element itself, walk up the region + // hierarchy to see if there is a default value installed in an ancestor. + if (isa<FieldRegion>(superR) || isa<ElementRegion>(superR)) { + superR = cast<SubRegion>(superR)->getSuperRegion(); + continue; + } + + break; + } + + // Lazy binding? + Store lazyBindingStore = NULL; + const MemRegion *lazyBindingRegion = NULL; + llvm::tie(lazyBindingStore, lazyBindingRegion) = GetLazyBinding(B, R); + + if (lazyBindingRegion) { + if (const ElementRegion *ER = dyn_cast<ElementRegion>(lazyBindingRegion)) + return RetrieveElement(lazyBindingStore, ER); + return RetrieveField(lazyBindingStore, + cast<FieldRegion>(lazyBindingRegion)); + } + + if (R->hasStackNonParametersStorage()) { + if (isa<ElementRegion>(R)) { + // Currently we don't reason specially about Clang-style vectors. Check + // if superR is a vector and if so return Unknown. + if (const TypedRegion *typedSuperR = dyn_cast<TypedRegion>(superR)) { + if (typedSuperR->getValueType(getContext())->isVectorType()) + return UnknownVal(); + } + } + + return UndefinedVal(); + } + + // All other values are symbolic. + return ValMgr.getRegionValueSymbolVal(R, Ty); +} + +SVal RegionStoreManager::RetrieveObjCIvar(Store store, const ObjCIvarRegion* R){ + + // Check if the region has a binding. + RegionBindings B = GetRegionBindings(store); + + if (Optional<SVal> V = getDirectBinding(B, R)) + return *V; + + const MemRegion *superR = R->getSuperRegion(); + + // Check if the super region has a default binding. + if (Optional<SVal> V = getDefaultBinding(B, superR)) { + if (SymbolRef parentSym = V->getAsSymbol()) + return ValMgr.getDerivedRegionValueSymbolVal(parentSym, R); + + // Other cases: give up. + return UnknownVal(); + } + + return RetrieveLazySymbol(R); +} + +SVal RegionStoreManager::RetrieveVar(Store store, const VarRegion *R) { + + // Check if the region has a binding. + RegionBindings B = GetRegionBindings(store); + + if (Optional<SVal> V = getDirectBinding(B, R)) + return *V; + + // Lazily derive a value for the VarRegion. + const VarDecl *VD = R->getDecl(); + QualType T = VD->getType(); + const MemSpaceRegion *MS = R->getMemorySpace(); + + if (isa<UnknownSpaceRegion>(MS) || + isa<StackArgumentsSpaceRegion>(MS)) + return ValMgr.getRegionValueSymbolVal(R, T); + + if (isa<GlobalsSpaceRegion>(MS)) { + if (VD->isFileVarDecl()) + return ValMgr.getRegionValueSymbolVal(R, T); + + if (T->isIntegerType()) + return ValMgr.makeIntVal(0, T); + if (T->isPointerType()) + return ValMgr.makeNull(); + + return UnknownVal(); + } + + return UndefinedVal(); +} + +SVal RegionStoreManager::RetrieveLazySymbol(const TypedRegion *R) { + + QualType valTy = R->getValueType(getContext()); + + // All other values are symbolic. + return ValMgr.getRegionValueSymbolVal(R, valTy); +} + +SVal RegionStoreManager::RetrieveStruct(Store store, const TypedRegion* R) { + QualType T = R->getValueType(getContext()); + assert(T->isStructureType()); + + const RecordType* RT = T->getAsStructureType(); + RecordDecl* RD = RT->getDecl(); + assert(RD->isDefinition()); + (void)RD; +#if USE_EXPLICIT_COMPOUND + llvm::ImmutableList<SVal> StructVal = getBasicVals().getEmptySValList(); + + // FIXME: We shouldn't use a std::vector. If RecordDecl doesn't have a + // reverse iterator, we should implement one. + std::vector<FieldDecl *> Fields(RD->field_begin(), RD->field_end()); + + for (std::vector<FieldDecl *>::reverse_iterator Field = Fields.rbegin(), + FieldEnd = Fields.rend(); + Field != FieldEnd; ++Field) { + FieldRegion* FR = MRMgr.getFieldRegion(*Field, R); + QualType FTy = (*Field)->getType(); + SVal FieldValue = Retrieve(store, loc::MemRegionVal(FR), FTy).getSVal(); + StructVal = getBasicVals().consVals(FieldValue, StructVal); + } + + return ValMgr.makeCompoundVal(T, StructVal); +#else + return ValMgr.makeLazyCompoundVal(store, R); +#endif +} + +SVal RegionStoreManager::RetrieveArray(Store store, const TypedRegion * R) { +#if USE_EXPLICIT_COMPOUND + QualType T = R->getValueType(getContext()); + ConstantArrayType* CAT = cast<ConstantArrayType>(T.getTypePtr()); + + llvm::ImmutableList<SVal> ArrayVal = getBasicVals().getEmptySValList(); + uint64_t size = CAT->getSize().getZExtValue(); + for (uint64_t i = 0; i < size; ++i) { + SVal Idx = ValMgr.makeArrayIndex(i); + ElementRegion* ER = MRMgr.getElementRegion(CAT->getElementType(), Idx, R, + getContext()); + QualType ETy = ER->getElementType(); + SVal ElementVal = Retrieve(store, loc::MemRegionVal(ER), ETy).getSVal(); + ArrayVal = getBasicVals().consVals(ElementVal, ArrayVal); + } + + return ValMgr.makeCompoundVal(T, ArrayVal); +#else + assert(isa<ConstantArrayType>(R->getValueType(getContext()))); + return ValMgr.makeLazyCompoundVal(store, R); +#endif +} + +//===----------------------------------------------------------------------===// +// Binding values to regions. +//===----------------------------------------------------------------------===// + +Store RegionStoreManager::Remove(Store store, Loc L) { + if (isa<loc::MemRegionVal>(L)) + if (const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion()) + return Remove(GetRegionBindings(store), R).getRoot(); + + return store; +} + +Store RegionStoreManager::Bind(Store store, Loc L, SVal V) { + if (isa<loc::ConcreteInt>(L)) + return store; + + // If we get here, the location should be a region. + const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion(); + + // Check if the region is a struct region. + if (const TypedRegion* TR = dyn_cast<TypedRegion>(R)) + if (TR->getValueType(getContext())->isStructureType()) + return BindStruct(store, TR, V); + + // Special case: the current region represents a cast and it and the super + // region both have pointer types or intptr_t types. If so, perform the + // bind to the super region. + // This is needed to support OSAtomicCompareAndSwap and friends or other + // loads that treat integers as pointers and vis versa. + if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) { + if (ER->getIndex().isZeroConstant()) { + if (const TypedRegion *superR = + dyn_cast<TypedRegion>(ER->getSuperRegion())) { + ASTContext &Ctx = getContext(); + QualType superTy = superR->getValueType(Ctx); + QualType erTy = ER->getValueType(Ctx); + + if (IsAnyPointerOrIntptr(superTy, Ctx) && + IsAnyPointerOrIntptr(erTy, Ctx)) { + V = ValMgr.getSValuator().EvalCast(V, superTy, erTy); + return Bind(store, loc::MemRegionVal(superR), V); + } + // For now, just invalidate the fields of the struct/union/class. + // FIXME: Precisely handle the fields of the record. + if (superTy->isRecordType()) + return InvalidateRegion(store, superR, NULL, 0, NULL); + } + } + } + else if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) { + // Binding directly to a symbolic region should be treated as binding + // to element 0. + QualType T = SR->getSymbol()->getType(getContext()); + + // FIXME: Is this the right way to handle symbols that are references? + if (const PointerType *PT = T->getAs<PointerType>()) + T = PT->getPointeeType(); + else + T = T->getAs<ReferenceType>()->getPointeeType(); + + R = GetElementZeroRegion(SR, T); + } + + // Perform the binding. + RegionBindings B = GetRegionBindings(store); + return Add(B, R, BindingKey::Direct, V).getRoot(); +} + +Store RegionStoreManager::BindDecl(Store store, const VarRegion *VR, + SVal InitVal) { + + QualType T = VR->getDecl()->getType(); + + if (T->isArrayType()) + return BindArray(store, VR, InitVal); + if (T->isStructureType()) + return BindStruct(store, VR, InitVal); + + return Bind(store, ValMgr.makeLoc(VR), InitVal); +} + +// FIXME: this method should be merged into Bind(). +Store RegionStoreManager::BindCompoundLiteral(Store store, + const CompoundLiteralExpr *CL, + const LocationContext *LC, + SVal V) { + return Bind(store, loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL, LC)), + V); +} + +Store RegionStoreManager::setImplicitDefaultValue(Store store, + const MemRegion *R, + QualType T) { + RegionBindings B = GetRegionBindings(store); + SVal V; + + if (Loc::IsLocType(T)) + V = ValMgr.makeNull(); + else if (T->isIntegerType()) + V = ValMgr.makeZeroVal(T); + else if (T->isStructureType() || T->isArrayType()) { + // Set the default value to a zero constant when it is a structure + // or array. The type doesn't really matter. + V = ValMgr.makeZeroVal(ValMgr.getContext().IntTy); + } + else { + return store; + } + + return Add(B, R, BindingKey::Default, V).getRoot(); +} + +Store RegionStoreManager::BindArray(Store store, const TypedRegion* R, + SVal Init) { + + ASTContext &Ctx = getContext(); + const ArrayType *AT = + cast<ArrayType>(Ctx.getCanonicalType(R->getValueType(Ctx))); + QualType ElementTy = AT->getElementType(); + Optional<uint64_t> Size; + + if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(AT)) + Size = CAT->getSize().getZExtValue(); + + // Check if the init expr is a StringLiteral. + if (isa<loc::MemRegionVal>(Init)) { + const MemRegion* InitR = cast<loc::MemRegionVal>(Init).getRegion(); + const StringLiteral* S = cast<StringRegion>(InitR)->getStringLiteral(); + const char* str = S->getStrData(); + unsigned len = S->getByteLength(); + unsigned j = 0; + + // Copy bytes from the string literal into the target array. Trailing bytes + // in the array that are not covered by the string literal are initialized + // to zero. + + // We assume that string constants are bound to + // constant arrays. + uint64_t size = Size.getValue(); + + for (uint64_t i = 0; i < size; ++i, ++j) { + if (j >= len) + break; + + SVal Idx = ValMgr.makeArrayIndex(i); + const ElementRegion* ER = MRMgr.getElementRegion(ElementTy, Idx, R, + getContext()); + + SVal V = ValMgr.makeIntVal(str[j], sizeof(char)*8, true); + store = Bind(store, loc::MemRegionVal(ER), V); + } + + return store; + } + + // Handle lazy compound values. + if (nonloc::LazyCompoundVal *LCV = dyn_cast<nonloc::LazyCompoundVal>(&Init)) + return CopyLazyBindings(*LCV, store, R); + + // Remaining case: explicit compound values. + + 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; + + for (; Size.hasValue() ? i < Size.getValue() : true ; ++i, ++VI) { + // The init list might be shorter than the array length. + if (VI == VE) + break; + + SVal Idx = ValMgr.makeArrayIndex(i); + const ElementRegion *ER = MRMgr.getElementRegion(ElementTy, Idx, R, getContext()); + + if (ElementTy->isStructureType()) + store = BindStruct(store, ER, *VI); + else + store = Bind(store, ValMgr.makeLoc(ER), *VI); + } + + // If the init list is shorter than the array length, set the + // array default value. + if (Size.hasValue() && i < Size.getValue()) + store = setImplicitDefaultValue(store, R, ElementTy); + + return store; +} + +Store RegionStoreManager::BindStruct(Store store, const TypedRegion* R, + SVal V) { + + if (!Features.supportsFields()) + return store; + + QualType T = R->getValueType(getContext()); + assert(T->isStructureType()); + + const RecordType* RT = T->getAs<RecordType>(); + RecordDecl* RD = RT->getDecl(); + + if (!RD->isDefinition()) + return store; + + // Handle lazy compound values. + if (const nonloc::LazyCompoundVal *LCV=dyn_cast<nonloc::LazyCompoundVal>(&V)) + return CopyLazyBindings(*LCV, store, R); + + // We may get non-CompoundVal accidentally due to imprecise cast logic. + // Ignore them and kill the field values. + if (V.isUnknown() || !isa<nonloc::CompoundVal>(V)) + return KillStruct(store, R); + + nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V); + nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); + + RecordDecl::field_iterator FI, FE; + + for (FI = RD->field_begin(), FE = RD->field_end(); FI != FE; ++FI, ++VI) { + + if (VI == VE) + break; + + QualType FTy = (*FI)->getType(); + const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R); + + if (FTy->isArrayType()) + store = BindArray(store, FR, *VI); + else if (FTy->isStructureType()) + store = BindStruct(store, FR, *VI); + else + store = Bind(store, ValMgr.makeLoc(FR), *VI); + } + + // There may be fewer values in the initialize list than the fields of struct. + if (FI != FE) { + RegionBindings B = GetRegionBindings(store); + B = Add(B, R, BindingKey::Default, ValMgr.makeIntVal(0, false)); + store = B.getRoot(); + } + + return store; +} + +Store RegionStoreManager::KillStruct(Store store, const TypedRegion* R) { + RegionBindings B = GetRegionBindings(store); + llvm::OwningPtr<RegionStoreSubRegionMap> + SubRegions(getRegionStoreSubRegionMap(store)); + RemoveSubRegionBindings(B, R, *SubRegions); + + // Set the default value of the struct region to "unknown". + return Add(B, R, BindingKey::Default, UnknownVal()).getRoot(); +} + +Store RegionStoreManager::CopyLazyBindings(nonloc::LazyCompoundVal V, + Store store, const TypedRegion *R) { + + // Nuke the old bindings stemming from R. + RegionBindings B = GetRegionBindings(store); + + llvm::OwningPtr<RegionStoreSubRegionMap> + SubRegions(getRegionStoreSubRegionMap(store)); + + // B and DVM are updated after the call to RemoveSubRegionBindings. + RemoveSubRegionBindings(B, R, *SubRegions.get()); + + // Now copy the bindings. This amounts to just binding 'V' to 'R'. This + // results in a zero-copy algorithm. + return Add(B, R, BindingKey::Direct, V).getRoot(); +} + +//===----------------------------------------------------------------------===// +// "Raw" retrievals and bindings. +//===----------------------------------------------------------------------===// + +BindingKey BindingKey::Make(const MemRegion *R, Kind k) { + if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) { + const RegionRawOffset &O = ER->getAsRawOffset(); + + if (O.getRegion()) + return BindingKey(O.getRegion(), O.getByteOffset(), k); + + // FIXME: There are some ElementRegions for which we cannot compute + // raw offsets yet, including regions with symbolic offsets. + } + + return BindingKey(R, 0, k); +} + +RegionBindings RegionStoreManager::Add(RegionBindings B, BindingKey K, SVal V) { + return RBFactory.Add(B, K, V); +} + +RegionBindings RegionStoreManager::Add(RegionBindings B, const MemRegion *R, + BindingKey::Kind k, SVal V) { + return Add(B, BindingKey::Make(R, k), V); +} + +const SVal *RegionStoreManager::Lookup(RegionBindings B, BindingKey K) { + return B.lookup(K); +} + +const SVal *RegionStoreManager::Lookup(RegionBindings B, + const MemRegion *R, + BindingKey::Kind k) { + return Lookup(B, BindingKey::Make(R, k)); +} + +RegionBindings RegionStoreManager::Remove(RegionBindings B, BindingKey K) { + return RBFactory.Remove(B, K); +} + +RegionBindings RegionStoreManager::Remove(RegionBindings B, const MemRegion *R, + BindingKey::Kind k){ + return Remove(B, BindingKey::Make(R, k)); +} + +Store RegionStoreManager::Remove(Store store, BindingKey K) { + RegionBindings B = GetRegionBindings(store); + return Remove(B, K).getRoot(); +} + +//===----------------------------------------------------------------------===// +// State pruning. +//===----------------------------------------------------------------------===// + +Store RegionStoreManager::RemoveDeadBindings(Store store, Stmt* Loc, + SymbolReaper& SymReaper, + llvm::SmallVectorImpl<const MemRegion*>& RegionRoots) +{ + typedef std::pair<Store, const MemRegion *> RBDNode; + + RegionBindings B = GetRegionBindings(store); + + // The backmap from regions to subregions. + llvm::OwningPtr<RegionStoreSubRegionMap> + SubRegions(getRegionStoreSubRegionMap(store)); + + // Do a pass over the regions in the store. For VarRegions we check if + // the variable is still live and if so add it to the list of live roots. + // For other regions we populate our region backmap. + llvm::SmallVector<const MemRegion*, 10> IntermediateRoots; + + // Scan the direct bindings for "intermediate" roots. + for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) { + const MemRegion *R = I.getKey().getRegion(); + IntermediateRoots.push_back(R); + } + + // Process the "intermediate" roots to find if they are referenced by + // real roots. + llvm::SmallVector<RBDNode, 10> WorkList; + llvm::SmallVector<RBDNode, 10> Postponed; + + llvm::DenseSet<const MemRegion*> IntermediateVisited; + + while (!IntermediateRoots.empty()) { + const MemRegion* R = IntermediateRoots.back(); + IntermediateRoots.pop_back(); + + if (IntermediateVisited.count(R)) + continue; + IntermediateVisited.insert(R); + + if (const VarRegion* VR = dyn_cast<VarRegion>(R)) { + if (SymReaper.isLive(Loc, VR)) + WorkList.push_back(std::make_pair(store, VR)); + continue; + } + + if (const SymbolicRegion* SR = dyn_cast<SymbolicRegion>(R)) { + llvm::SmallVectorImpl<RBDNode> &Q = + SymReaper.isLive(SR->getSymbol()) ? WorkList : Postponed; + + Q.push_back(std::make_pair(store, SR)); + + continue; + } + + // Add the super region for R to the worklist if it is a subregion. + if (const SubRegion* superR = + dyn_cast<SubRegion>(cast<SubRegion>(R)->getSuperRegion())) + IntermediateRoots.push_back(superR); + } + + // Enqueue the RegionRoots onto WorkList. + for (llvm::SmallVectorImpl<const MemRegion*>::iterator I=RegionRoots.begin(), + E=RegionRoots.end(); I!=E; ++I) { + WorkList.push_back(std::make_pair(store, *I)); + } + RegionRoots.clear(); + + llvm::DenseSet<RBDNode> Visited; + +tryAgain: + while (!WorkList.empty()) { + RBDNode N = WorkList.back(); + WorkList.pop_back(); + + // Have we visited this node before? + if (Visited.count(N)) + continue; + Visited.insert(N); + + const MemRegion *R = N.second; + Store store_N = N.first; + + // Enqueue subregions. + RegionStoreSubRegionMap *M; + + if (store == store_N) + M = SubRegions.get(); + else { + RegionStoreSubRegionMap *& SM = SC[store_N]; + if (!SM) + SM = getRegionStoreSubRegionMap(store_N); + M = SM; + } + + if (const RegionStoreSubRegionMap::Set *S = M->getSubRegions(R)) + for (RegionStoreSubRegionMap::Set::iterator I = S->begin(), E = S->end(); + I != E; ++I) + WorkList.push_back(std::make_pair(store_N, *I)); + + // Enqueue the super region. + if (const SubRegion *SR = dyn_cast<SubRegion>(R)) { + const MemRegion *superR = SR->getSuperRegion(); + if (!isa<MemSpaceRegion>(superR)) { + // If 'R' is a field or an element, we want to keep the bindings + // for the other fields and elements around. The reason is that + // pointer arithmetic can get us to the other fields or elements. + assert(isa<FieldRegion>(R) || isa<ElementRegion>(R) + || isa<ObjCIvarRegion>(R)); + WorkList.push_back(std::make_pair(store_N, superR)); + } + } + + // Mark the symbol for any live SymbolicRegion as "live". This means we + // should continue to track that symbol. + if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(R)) + SymReaper.markLive(SymR->getSymbol()); + + // For BlockDataRegions, enqueue the VarRegions for variables marked + // with __block (passed-by-reference). + // via BlockDeclRefExprs. + if (const BlockDataRegion *BD = dyn_cast<BlockDataRegion>(R)) { + for (BlockDataRegion::referenced_vars_iterator + RI = BD->referenced_vars_begin(), RE = BD->referenced_vars_end(); + RI != RE; ++RI) { + if ((*RI)->getDecl()->getAttr<BlocksAttr>()) + WorkList.push_back(std::make_pair(store_N, *RI)); + } + // No possible data bindings on a BlockDataRegion. Continue to the + // next region in the worklist. + continue; + } + + RegionBindings B_N = GetRegionBindings(store_N); + + // Get the data binding for R (if any). + Optional<SVal> V = getBinding(B_N, R); + + if (V) { + // Check for lazy bindings. + if (const nonloc::LazyCompoundVal *LCV = + dyn_cast<nonloc::LazyCompoundVal>(V.getPointer())) { + + const LazyCompoundValData *D = LCV->getCVData(); + WorkList.push_back(std::make_pair(D->getStore(), D->getRegion())); + } + else { + // Update the set of live symbols. + for (SVal::symbol_iterator SI=V->symbol_begin(), SE=V->symbol_end(); + SI!=SE;++SI) + SymReaper.markLive(*SI); + + // If V is a region, then add it to the worklist. + if (const MemRegion *RX = V->getAsRegion()) + WorkList.push_back(std::make_pair(store_N, RX)); + } + } + } + + // See if any postponed SymbolicRegions are actually live now, after + // having done a scan. + for (llvm::SmallVectorImpl<RBDNode>::iterator I = Postponed.begin(), + E = Postponed.end() ; I != E ; ++I) { + if (const SymbolicRegion *SR = cast_or_null<SymbolicRegion>(I->second)) { + if (SymReaper.isLive(SR->getSymbol())) { + WorkList.push_back(*I); + I->second = NULL; + } + } + } + + if (!WorkList.empty()) + goto tryAgain; + + // We have now scanned the store, marking reachable regions and symbols + // as live. We now remove all the regions that are dead from the store + // as well as update DSymbols with the set symbols that are now dead. + Store new_store = store; + for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) { + const MemRegion* R = I.getKey().getRegion(); + // If this region live? Is so, none of its symbols are dead. + if (Visited.count(std::make_pair(store, R))) + continue; + + // Remove this dead region from the store. + new_store = Remove(new_store, I.getKey()); + + // Mark all non-live symbols that this region references as dead. + if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(R)) + SymReaper.maybeDead(SymR->getSymbol()); + + SVal X = I.getData(); + SVal::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end(); + for (; SI != SE; ++SI) + SymReaper.maybeDead(*SI); + } + + return new_store; +} + +GRState const *RegionStoreManager::EnterStackFrame(GRState const *state, + StackFrameContext const *frame) { + FunctionDecl const *FD = cast<FunctionDecl>(frame->getDecl()); + CallExpr const *CE = cast<CallExpr>(frame->getCallSite()); + + FunctionDecl::param_const_iterator PI = FD->param_begin(); + + CallExpr::const_arg_iterator AI = CE->arg_begin(), AE = CE->arg_end(); + + // Copy the arg expression value to the arg variables. + Store store = state->getStore(); + for (; AI != AE; ++AI, ++PI) { + SVal ArgVal = state->getSVal(*AI); + store = Bind(store, ValMgr.makeLoc(MRMgr.getVarRegion(*PI, frame)), ArgVal); + } + + return state->makeWithStore(store); +} + +//===----------------------------------------------------------------------===// +// Utility methods. +//===----------------------------------------------------------------------===// + +void RegionStoreManager::print(Store store, llvm::raw_ostream& OS, + const char* nl, const char *sep) { + RegionBindings B = GetRegionBindings(store); + OS << "Store (direct and default bindings):" << nl; + + for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) + OS << ' ' << I.getKey() << " : " << I.getData() << nl; +} |
