diff options
Diffstat (limited to 'clang/lib/Analysis/RegionStore.cpp')
| -rw-r--r-- | clang/lib/Analysis/RegionStore.cpp | 504 |
1 files changed, 252 insertions, 252 deletions
diff --git a/clang/lib/Analysis/RegionStore.cpp b/clang/lib/Analysis/RegionStore.cpp index 5114035d5f4..41866909391 100644 --- a/clang/lib/Analysis/RegionStore.cpp +++ b/clang/lib/Analysis/RegionStore.cpp @@ -41,21 +41,21 @@ typedef llvm::ImmutableMap<const MemRegion*, SVal> RegionBindings; namespace { struct VISIBILITY_HIDDEN minimal_features_tag {}; -struct VISIBILITY_HIDDEN maximal_features_tag {}; - +struct VISIBILITY_HIDDEN maximal_features_tag {}; + class VISIBILITY_HIDDEN 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; } }; @@ -107,7 +107,7 @@ typedef RegionDefaultValue::MapTy RegionDefaultBindings; static bool IsAnyPointerOrIntptr(QualType ty, ASTContext &Ctx) { if (ty->isAnyPointerType()) return true; - + return ty->isIntegerType() && ty->isScalarType() && Ctx.getTypeSize(ty) == Ctx.getTypeSize(Ctx.VoidPtrTy); } @@ -117,10 +117,10 @@ static bool IsAnyPointerOrIntptr(QualType ty, ASTContext &Ctx) { //===----------------------------------------------------------------------===// namespace { - + class VISIBILITY_HIDDEN RegionStoreSubRegionMap : public SubRegionMap { typedef llvm::ImmutableSet<const MemRegion*> SetTy; - typedef llvm::DenseMap<const MemRegion*, SetTy> Map; + typedef llvm::DenseMap<const MemRegion*, SetTy> Map; SetTy::Factory F; Map M; public: @@ -135,27 +135,27 @@ public: I->second = F.Add(I->second, SubRegion); return false; } - + void process(llvm::SmallVectorImpl<const SubRegion*> &WL, const SubRegion *R); - + ~RegionStoreSubRegionMap() {} - + bool iterSubRegions(const MemRegion* Parent, Visitor& V) const { Map::iterator I = M.find(Parent); if (I == M.end()) return true; - + llvm::ImmutableSet<const MemRegion*> S = I->second; for (llvm::ImmutableSet<const MemRegion*>::iterator SI=S.begin(),SE=S.end(); SI != SE; ++SI) { if (!V.Visit(Parent, *SI)) return false; } - + return true; } - + typedef SetTy::iterator iterator; std::pair<iterator, iterator> begin_end(const MemRegion *R) { @@ -163,13 +163,13 @@ public: SetTy S = I == M.end() ? F.GetEmptySet() : I->second; return std::make_pair(S.begin(), S.end()); } -}; +}; class VISIBILITY_HIDDEN RegionStoreManager : public StoreManager { const RegionStoreFeatures Features; RegionBindings::Factory RBFactory; public: - RegionStoreManager(GRStateManager& mgr, const RegionStoreFeatures &f) + RegionStoreManager(GRStateManager& mgr, const RegionStoreFeatures &f) : StoreManager(mgr), Features(f), RBFactory(mgr.getAllocator()) {} @@ -177,14 +177,14 @@ public: virtual ~RegionStoreManager() {} SubRegionMap *getSubRegionMap(const GRState *state); - + RegionStoreSubRegionMap *getRegionStoreSubRegionMap(const GRState *state); - - + + /// getDefaultBinding - Returns an SVal* representing an optional default /// binding associated with a region and its subregions. Optional<SVal> getDefaultBinding(const GRState *state, const MemRegion *R); - + /// getLValueString - Returns an SVal representing the lvalue of a /// StringLiteral. Within RegionStore a StringLiteral has an /// associated StringRegion, and the lvalue of a StringLiteral is @@ -202,11 +202,11 @@ public: /// VarRegion, and the lvalue of the variable is the lvalue of that region. SVal getLValueVar(const GRState *ST, const VarDecl *VD, const LocationContext *LC); - + SVal getLValueIvar(const GRState *state, const ObjCIvarDecl* D, SVal Base); SVal getLValueField(const GRState *state, SVal Base, const FieldDecl* D); - + SVal getLValueFieldOrIvar(const GRState *state, SVal Base, const Decl* D); SVal getLValueElement(const GRState *state, QualType elementType, @@ -224,7 +224,7 @@ public: SVal EvalBinOp(const GRState *state, BinaryOperator::Opcode Op,Loc L, NonLoc R, QualType resultTy); - Store getInitialStore(const LocationContext *InitLoc) { + Store getInitialStore(const LocationContext *InitLoc) { return RBFactory.GetEmptyMap().getRoot(); } @@ -234,20 +234,20 @@ public: const GRState *InvalidateRegion(const GRState *state, const MemRegion *R, const Expr *E, unsigned Count); - + private: void RemoveSubRegionBindings(RegionBindings &B, RegionDefaultBindings &DVM, RegionDefaultBindings::Factory &DVMFactory, const MemRegion *R, RegionStoreSubRegionMap &M); - -public: + +public: const GRState *Bind(const GRState *state, Loc LV, SVal V); const GRState *BindCompoundLiteral(const GRState *state, const CompoundLiteralExpr* CL, SVal V); - + const GRState *BindDecl(const GRState *ST, const VarDecl *VD, const LocationContext *LC, SVal InitVal); @@ -258,10 +258,10 @@ public: /// BindStruct - Bind a compound value to a structure. const GRState *BindStruct(const GRState *, const TypedRegion* R, SVal V); - + const GRState *BindArray(const GRState *state, const TypedRegion* R, SVal V); - - /// KillStruct - Set the entire struct to unknown. + + /// KillStruct - Set the entire struct to unknown. const GRState *KillStruct(const GRState *state, const TypedRegion* R); const GRState *setDefaultValue(const GRState *state, const MemRegion* R, SVal V); @@ -271,7 +271,7 @@ public: //===------------------------------------------------------------------===// // Loading values from regions. //===------------------------------------------------------------------===// - + /// The high level logic for this method is this: /// Retrieve (L) /// if L has binding @@ -289,28 +289,28 @@ public: SVal RetrieveElement(const GRState *state, const ElementRegion *R); SVal RetrieveField(const GRState *state, const FieldRegion *R); - + SVal RetrieveObjCIvar(const GRState *state, const ObjCIvarRegion *R); - + SVal RetrieveVar(const GRState *state, const VarRegion *R); - + SVal RetrieveLazySymbol(const GRState *state, const TypedRegion *R); - + SVal RetrieveFieldOrElementCommon(const GRState *state, 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; + /// struct copy: + /// struct s x, y; /// x = y; /// y's value is retrieved by this method. SVal RetrieveStruct(const GRState *St, const TypedRegion* R); - + SVal RetrieveArray(const GRState *St, const TypedRegion* R); - + std::pair<const GRState*, const MemRegion*> GetLazyBinding(RegionBindings B, const MemRegion *R); - + const GRState* CopyLazyBindings(nonloc::LazyCompoundVal V, const GRState *state, const TypedRegion *R); @@ -318,7 +318,7 @@ public: //===------------------------------------------------------------------===// // State pruning. //===------------------------------------------------------------------===// - + /// RemoveDeadBindings - Scans the RegionStore of 'state' for dead values. /// It returns a new Store with these values removed. void RemoveDeadBindings(GRState &state, Stmt* Loc, SymbolReaper& SymReaper, @@ -327,14 +327,14 @@ public: //===------------------------------------------------------------------===// // Region "extents". //===------------------------------------------------------------------===// - + const GRState *setExtent(const GRState *state, const MemRegion* R, SVal Extent); SVal getSizeInElements(const GRState *state, const MemRegion* R); //===------------------------------------------------------------------===// // Utility methods. //===------------------------------------------------------------------===// - + static inline RegionBindings GetRegionBindings(Store store) { return RegionBindings(static_cast<const RegionBindings::TreeTy*>(store)); } @@ -350,7 +350,7 @@ public: BasicValueFactory& getBasicVals() { return StateMgr.getBasicVals(); } - + // FIXME: Remove. ASTContext& getContext() { return StateMgr.getContext(); } }; @@ -374,31 +374,31 @@ StoreManager *clang::CreateFieldsOnlyRegionStoreManager(GRStateManager &StMgr) { void RegionStoreSubRegionMap::process(llvm::SmallVectorImpl<const SubRegion*> &WL, - const SubRegion *R) { + const SubRegion *R) { const MemRegion *superR = R->getSuperRegion(); if (add(superR, R)) if (const SubRegion *sr = dyn_cast<SubRegion>(superR)) - WL.push_back(sr); + WL.push_back(sr); } RegionStoreSubRegionMap* RegionStoreManager::getRegionStoreSubRegionMap(const GRState *state) { RegionBindings B = GetRegionBindings(state->getStore()); 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())) M->process(WL, R); - + RegionDefaultBindings DVM = state->get<RegionDefaultValue>(); for (RegionDefaultBindings::iterator I = DVM.begin(), E = DVM.end(); - I != E; ++I) + I != E; ++I) if (const SubRegion *R = dyn_cast<SubRegion>(I.getKey())) M->process(WL, R); - // We also need to record in the subregion map "intermediate" regions that + // 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(); @@ -423,12 +423,12 @@ RegionStoreManager::RemoveSubRegionBindings(RegionBindings &B, RegionDefaultBindings::Factory &DVMFactory, const MemRegion *R, RegionStoreSubRegionMap &M) { - + RegionStoreSubRegionMap::iterator I, E; for (llvm::tie(I, E) = M.begin_end(R); I != E; ++I) RemoveSubRegionBindings(B, DVM, DVMFactory, *I, M); - + B = RBFactory.Remove(B, R); DVM = DVMFactory.Remove(DVM, R); } @@ -439,48 +439,48 @@ const GRState *RegionStoreManager::InvalidateRegion(const GRState *state, const Expr *E, unsigned Count) { ASTContext& Ctx = StateMgr.getContext(); - + // Strip away casts. R = R->getBaseRegion(); // Remove the bindings to subregions. - { + { // Get the mapping of regions -> subregions. llvm::OwningPtr<RegionStoreSubRegionMap> SubRegions(getRegionStoreSubRegionMap(state)); - + RegionBindings B = GetRegionBindings(state->getStore()); - RegionDefaultBindings DVM = state->get<RegionDefaultValue>(); + RegionDefaultBindings DVM = state->get<RegionDefaultValue>(); RegionDefaultBindings::Factory &DVMFactory = state->get_context<RegionDefaultValue>(); - - RemoveSubRegionBindings(B, DVM, DVMFactory, R, *SubRegions.get()); + + RemoveSubRegionBindings(B, DVM, DVMFactory, R, *SubRegions.get()); state = state->makeWithStore(B.getRoot())->set<RegionDefaultValue>(DVM); } if (!R->isBoundable()) return state; - + if (isa<AllocaRegion>(R) || isa<SymbolicRegion>(R) || isa<ObjCObjectRegion>(R)) { - // Invalidate the region by setting its default value to + // Invalidate the region by setting its default value to // conjured symbol. The type of the symbol is irrelavant. SVal V = ValMgr.getConjuredSymbolVal(E, Ctx.IntTy, Count); return setDefaultValue(state, R, V); } - + const TypedRegion *TR = cast<TypedRegion>(R); QualType T = TR->getValueType(Ctx); - + if (const RecordType *RT = T->getAsStructureType()) { // FIXME: handle structs with default region value. const RecordDecl *RD = RT->getDecl()->getDefinition(Ctx); - + // No record definition. There is nothing we can do. if (!RD) return state; - - // Invalidate the region by setting its default value to + + // Invalidate the region by setting its default value to // conjured symbol. The type of the symbol is irrelavant. SVal V = ValMgr.getConjuredSymbolVal(E, Ctx.IntTy, Count); return setDefaultValue(state, R, V); @@ -492,7 +492,7 @@ const GRState *RegionStoreManager::InvalidateRegion(const GRState *state, Count); return setDefaultValue(state, TR, V); } - + SVal V = ValMgr.getConjuredSymbolVal(E, T, Count); assert(SymbolManager::canSymbolicate(T) || V.isUnknown()); return Bind(state, ValMgr.makeLoc(TR), V); @@ -506,7 +506,7 @@ const GRState *RegionStoreManager::InvalidateRegion(const GRState *state, /// StringLiteral. Within RegionStore a StringLiteral has an /// associated StringRegion, and the lvalue of a StringLiteral is the /// lvalue of that region. -SVal RegionStoreManager::getLValueString(const GRState *St, +SVal RegionStoreManager::getLValueString(const GRState *St, const StringLiteral* S) { return loc::MemRegionVal(MRMgr.getStringRegion(S)); } @@ -525,7 +525,7 @@ SVal RegionStoreManager::getLValueVar(const GRState *ST, const VarDecl *VD, /// is the lvalue of that region. SVal RegionStoreManager::getLValueCompoundLiteral(const GRState *St, - const CompoundLiteralExpr* CL) { + const CompoundLiteralExpr* CL) { return loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL)); } @@ -567,7 +567,7 @@ SVal RegionStoreManager::getLValueFieldOrIvar(const GRState *St, SVal Base, assert(0 && "Unhandled Base."); return Base; } - + // NOTE: We must have this check first because ObjCIvarDecl is a subclass // of FieldDecl. if (const ObjCIvarDecl *ID = dyn_cast<ObjCIvarDecl>(D)) @@ -595,10 +595,10 @@ SVal RegionStoreManager::getLValueElement(const GRState *St, // Pointer of any type can be cast and used as array base. const ElementRegion *ElemR = dyn_cast<ElementRegion>(BaseRegion); - + // Convert the offset to the appropriate size and signedness. Offset = ValMgr.convertToArrayIndex(Offset); - + if (!ElemR) { // // If the base region is not an ElementRegion, create one. @@ -612,23 +612,23 @@ SVal RegionStoreManager::getLValueElement(const GRState *St, return loc::MemRegionVal(MRMgr.getElementRegion(elementType, Offset, BaseRegion, getContext())); } - + SVal BaseIdx = ElemR->getIndex(); - + if (!isa<nonloc::ConcreteInt>(BaseIdx)) return UnknownVal(); - + const llvm::APSInt& BaseIdxI = cast<nonloc::ConcreteInt>(BaseIdx).getValue(); const llvm::APSInt& OffI = cast<nonloc::ConcreteInt>(Offset).getValue(); assert(BaseIdxI.isSigned()); - + // Compute the new index. SVal NewIdx = nonloc::ConcreteInt(getBasicVals().getValue(BaseIdxI + OffI)); - + // Construct the new ElementRegion. const MemRegion *ArrayR = ElemR->getSuperRegion(); return loc::MemRegionVal(MRMgr.getElementRegion(elementType, NewIdx, ArrayR, - getContext())); + getContext())); } //===----------------------------------------------------------------------===// @@ -637,12 +637,12 @@ SVal RegionStoreManager::getLValueElement(const GRState *St, SVal RegionStoreManager::getSizeInElements(const GRState *state, const MemRegion *R) { - + switch (R->getKind()) { case MemRegion::MemSpaceRegionKind: assert(0 && "Cannot index into a MemSpace"); - return UnknownVal(); - + return UnknownVal(); + case MemRegion::CodeTextRegionKind: // Technically this can happen if people do funny things with casts. return UnknownVal(); @@ -656,23 +656,23 @@ SVal RegionStoreManager::getSizeInElements(const GRState *state, case MemRegion::ObjCObjectRegionKind: case MemRegion::SymbolicRegionKind: return UnknownVal(); - + case MemRegion::StringRegionKind: { const StringLiteral* Str = cast<StringRegion>(R)->getStringLiteral(); - // We intentionally made the size value signed because it participates in + // 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); @@ -682,7 +682,7 @@ SVal RegionStoreManager::getSizeInElements(const GRState *state, // essentially are arrays of size 1. return ValMgr.makeIntVal(1, false); } - + case MemRegion::BEG_DECL_REGIONS: case MemRegion::END_DECL_REGIONS: case MemRegion::BEG_TYPED_REGIONS: @@ -690,7 +690,7 @@ SVal RegionStoreManager::getSizeInElements(const GRState *state, assert(0 && "Infeasible region"); return UnknownVal(); } - + assert(0 && "Unreachable"); return UnknownVal(); } @@ -714,29 +714,29 @@ const GRState *RegionStoreManager::setExtent(const GRState *state, 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(); ElementRegion* ER = MRMgr.getElementRegion(T, ZeroIdx, ArrayR, getContext()); - - return loc::MemRegionVal(ER); + + return loc::MemRegionVal(ER); } //===----------------------------------------------------------------------===// // Pointer arithmetic. //===----------------------------------------------------------------------===// -SVal RegionStoreManager::EvalBinOp(const GRState *state, +SVal RegionStoreManager::EvalBinOp(const GRState *state, BinaryOperator::Opcode Op, Loc L, NonLoc R, QualType resultTy) { // Assume the base location is MemRegionVal. @@ -752,15 +752,15 @@ SVal RegionStoreManager::EvalBinOp(const GRState *state, SymbolRef Sym = SR->getSymbol(); QualType T = Sym->getType(getContext()); QualType EleTy; - + if (const PointerType *PT = T->getAs<PointerType>()) EleTy = PT->getPointeeType(); else EleTy = T->getAsObjCObjectPointerType()->getPointeeType(); - + SVal ZeroIdx = ValMgr.makeZeroArrayIndex(); ER = MRMgr.getElementRegion(EleTy, ZeroIdx, SR, getContext()); - break; + break; } case MemRegion::AllocaRegionKind: { const AllocaRegion *AR = cast<AllocaRegion>(MR); @@ -768,14 +768,14 @@ SVal RegionStoreManager::EvalBinOp(const GRState *state, QualType EleTy = T->getAs<PointerType>()->getPointeeType(); SVal ZeroIdx = ValMgr.makeZeroArrayIndex(); ER = MRMgr.getElementRegion(EleTy, ZeroIdx, AR, getContext()); - break; + break; } case MemRegion::ElementRegionKind: { ER = cast<ElementRegion>(MR); break; } - + // Not yet handled. case MemRegion::VarRegionKind: case MemRegion::StringRegionKind: @@ -784,15 +784,15 @@ SVal RegionStoreManager::EvalBinOp(const GRState *state, case MemRegion::ObjCObjectRegionKind: case MemRegion::ObjCIvarRegionKind: return UnknownVal(); - + case MemRegion::CodeTextRegionKind: // Technically this can happen if people do funny things with casts. return UnknownVal(); - + case MemRegion::MemSpaceRegionKind: assert(0 && "Cannot perform pointer arithmetic on a MemSpace"); return UnknownVal(); - + case MemRegion::BEG_DECL_REGIONS: case MemRegion::END_DECL_REGIONS: case MemRegion::BEG_TYPED_REGIONS: @@ -815,7 +815,7 @@ SVal RegionStoreManager::EvalBinOp(const GRState *state, getContext()); return ValMgr.makeLoc(NewER); } - + return UnknownVal(); } @@ -825,7 +825,7 @@ SVal RegionStoreManager::EvalBinOp(const GRState *state, Optional<SVal> RegionStoreManager::getDefaultBinding(const GRState *state, const MemRegion *R) { - + if (R->isBoundable()) if (const TypedRegion *TR = dyn_cast<TypedRegion>(R)) if (TR->getValueType(getContext())->isUnionType()) @@ -837,21 +837,21 @@ Optional<SVal> RegionStoreManager::getDefaultBinding(const GRState *state, 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* + // 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 *PRTy = RTy->getAs<PointerType>(); const PointerType *PUsedTy = UsedTy->getAs<PointerType>(); return PUsedTy && PRTy && IsReinterpreted(PRTy->getPointeeType(), - PUsedTy->getPointeeType(), Ctx); + PUsedTy->getPointeeType(), Ctx); } return true; @@ -878,17 +878,17 @@ RegionStoreManager::Retrieve(const GRState *state, Loc L, QualType T) { // c = *p; if (isa<AllocaRegion>(MR)) return SValuator::CastResult(state, UnknownVal()); - + if (isa<SymbolicRegion>(MR)) { ASTContext &Ctx = getContext(); SVal idx = ValMgr.makeZeroArrayIndex(); assert(!T.isNull()); MR = MRMgr.getElementRegion(T, idx, MR, Ctx); } - + if (isa<CodeTextRegion>(MR)) return SValuator::CastResult(state, 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); @@ -911,12 +911,12 @@ RegionStoreManager::Retrieve(const GRState *state, Loc L, QualType T) { RTy = T; assert(Ctx.getCanonicalType(RTy) == Ctx.getCanonicalType(R->getValueType(Ctx))); - } + } #endif if (RTy->isStructureType()) return SValuator::CastResult(state, RetrieveStruct(state, R)); - + // FIXME: Handle unions. if (RTy->isUnionType()) return SValuator::CastResult(state, UnknownVal()); @@ -933,10 +933,10 @@ RegionStoreManager::Retrieve(const GRState *state, Loc L, QualType T) { if (const ElementRegion* ER = dyn_cast<ElementRegion>(R)) return CastRetrievedVal(RetrieveElement(state, ER), state, ER, T); - + if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) return CastRetrievedVal(RetrieveObjCIvar(state, IVR), state, IVR, T); - + if (const VarRegion *VR = dyn_cast<VarRegion>(R)) return CastRetrievedVal(RetrieveVar(state, VR), state, VR, T); @@ -967,26 +967,26 @@ RegionStoreManager::Retrieve(const GRState *state, Loc L, QualType T) { return SValuator::CastResult(state, ValMgr.getRegionValueSymbolValOrUnknown(R, RTy)); } - + std::pair<const GRState*, const MemRegion*> RegionStoreManager::GetLazyBinding(RegionBindings B, const MemRegion *R) { if (const nonloc::LazyCompoundVal *V = dyn_cast_or_null<nonloc::LazyCompoundVal>(B.lookup(R))) return std::make_pair(V->getState(), V->getRegion()); - + if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) { const std::pair<const GRState *, const MemRegion *> &X = GetLazyBinding(B, ER->getSuperRegion()); - + if (X.first) return std::make_pair(X.first, MRMgr.getElementRegionWithSuper(ER, X.second)); - } + } else if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) { const std::pair<const GRState *, const MemRegion *> &X = GetLazyBinding(B, FR->getSuperRegion()); - + if (X.first) return std::make_pair(X.first, MRMgr.getFieldRegionWithSuper(FR, X.second)); @@ -1010,23 +1010,23 @@ SVal RegionStoreManager::RetrieveElement(const GRState* state, SVal Idx = R->getIndex(); if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&Idx)) { int64_t i = CI->getValue().getSExtValue(); - int64_t byteLength = Str->getByteLength(); + 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, getContext().CharTy); } } - + // 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 // retrieve from the super region and appropriately "cast" the value. // This is needed to support OSAtomicCompareAndSwap and friends or other - // loads that treat integers as pointers and vis versa. + // loads that treat integers as pointers and vis versa. if (R->getIndex().isZeroConstant()) { if (const TypedRegion *superTR = dyn_cast<TypedRegion>(superR)) { ASTContext &Ctx = getContext(); @@ -1054,21 +1054,21 @@ SVal RegionStoreManager::RetrieveElement(const GRState* state, // Handle LazyCompoundVals for the immediate super region. Other cases // are handled in 'RetrieveFieldOrElementCommon'. - if (const nonloc::LazyCompoundVal *LCV = + if (const nonloc::LazyCompoundVal *LCV = dyn_cast<nonloc::LazyCompoundVal>(V)) { - + R = MRMgr.getElementRegionWithSuper(R, LCV->getRegion()); return RetrieveElement(LCV->getState(), R); } - + // Other cases: give up. return UnknownVal(); } - + return RetrieveFieldOrElementCommon(state, R, R->getElementType(), superR); } -SVal RegionStoreManager::RetrieveField(const GRState* state, +SVal RegionStoreManager::RetrieveField(const GRState* state, const FieldRegion* R) { // Check if the region has a binding. @@ -1079,76 +1079,76 @@ SVal RegionStoreManager::RetrieveField(const GRState* state, QualType Ty = R->getValueType(getContext()); return RetrieveFieldOrElementCommon(state, R, Ty, R->getSuperRegion()); } - + SVal RegionStoreManager::RetrieveFieldOrElementCommon(const GRState *state, const TypedRegion *R, QualType Ty, const MemRegion *superR) { - // At this point we have already checked in either RetrieveElement or + // At this point we have already checked in either RetrieveElement or // RetrieveField if 'R' has a direct binding. - + RegionBindings B = GetRegionBindings(state->getStore()); - + while (superR) { if (const Optional<SVal> &D = getDefaultBinding(state, 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? const GRState *lazyBindingState = NULL; const MemRegion *lazyBindingRegion = NULL; llvm::tie(lazyBindingState, lazyBindingRegion) = GetLazyBinding(B, R); - + if (lazyBindingState) { assert(lazyBindingRegion && "Lazy-binding region not set"); - + if (isa<ElementRegion>(R)) return RetrieveElement(lazyBindingState, cast<ElementRegion>(lazyBindingRegion)); - + return RetrieveField(lazyBindingState, cast<FieldRegion>(lazyBindingRegion)); - } - + } + if (R->hasStackStorage() && !R->hasParametersStorage()) { - + 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.getRegionValueSymbolValOrUnknown(R, Ty); } - -SVal RegionStoreManager::RetrieveObjCIvar(const GRState* state, + +SVal RegionStoreManager::RetrieveObjCIvar(const GRState* state, const ObjCIvarRegion* R) { // Check if the region has a binding. @@ -1156,50 +1156,50 @@ SVal RegionStoreManager::RetrieveObjCIvar(const GRState* state, if (const SVal* V = B.lookup(R)) return *V; - + const MemRegion *superR = R->getSuperRegion(); // Check if the super region has a binding. if (const SVal *V = B.lookup(superR)) { if (SymbolRef parentSym = V->getAsSymbol()) return ValMgr.getDerivedRegionValueSymbolVal(parentSym, R); - + // Other cases: give up. return UnknownVal(); } - + return RetrieveLazySymbol(state, R); } SVal RegionStoreManager::RetrieveVar(const GRState *state, const VarRegion *R) { - + // Check if the region has a binding. RegionBindings B = GetRegionBindings(state->getStore()); - + if (const SVal* V = B.lookup(R)) return *V; - + // Lazily derive a value for the VarRegion. const VarDecl *VD = R->getDecl(); - + if (R->hasGlobalsOrParametersStorage()) return ValMgr.getRegionValueSymbolValOrUnknown(R, VD->getType()); - + return UndefinedVal(); } -SVal RegionStoreManager::RetrieveLazySymbol(const GRState *state, +SVal RegionStoreManager::RetrieveLazySymbol(const GRState *state, const TypedRegion *R) { - + QualType valTy = R->getValueType(getContext()); // All other values are symbolic. return ValMgr.getRegionValueSymbolValOrUnknown(R, valTy); } -SVal RegionStoreManager::RetrieveStruct(const GRState *state, - const TypedRegion* R){ +SVal RegionStoreManager::RetrieveStruct(const GRState *state, + const TypedRegion* R) { QualType T = R->getValueType(getContext()); assert(T->isStructureType()); @@ -1240,7 +1240,7 @@ SVal RegionStoreManager::RetrieveArray(const GRState *state, for (uint64_t i = 0; i < size; ++i) { SVal Idx = ValMgr.makeArrayIndex(i); ElementRegion* ER = MRMgr.getElementRegion(CAT->getElementType(), Idx, R, - getContext()); + getContext()); QualType ETy = ER->getElementType(); SVal ElementVal = Retrieve(state, loc::MemRegionVal(ER), ETy).getSVal(); ArrayVal = getBasicVals().consVals(ElementVal, ArrayVal); @@ -1259,15 +1259,15 @@ SVal RegionStoreManager::RetrieveArray(const GRState *state, Store RegionStoreManager::Remove(Store store, Loc L) { const MemRegion* R = 0; - + if (isa<loc::MemRegionVal>(L)) R = cast<loc::MemRegionVal>(L).getRegion(); - + if (R) { - RegionBindings B = GetRegionBindings(store); + RegionBindings B = GetRegionBindings(store); return RBFactory.Remove(B, R).getRoot(); } - + return store; } @@ -1277,17 +1277,17 @@ const GRState *RegionStoreManager::Bind(const GRState *state, Loc L, SVal V) { // 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(state, 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. + // 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 = @@ -1295,17 +1295,17 @@ const GRState *RegionStoreManager::Bind(const GRState *state, Loc L, SVal V) { ASTContext &Ctx = getContext(); QualType superTy = superR->getValueType(Ctx); QualType erTy = ER->getValueType(Ctx); - - if (IsAnyPointerOrIntptr(superTy, Ctx) && + + if (IsAnyPointerOrIntptr(superTy, Ctx) && IsAnyPointerOrIntptr(erTy, Ctx)) { - SValuator::CastResult cr = - ValMgr.getSValuator().EvalCast(V, state, superTy, erTy); + SValuator::CastResult cr = + ValMgr.getSValuator().EvalCast(V, state, superTy, erTy); return Bind(cr.getState(), loc::MemRegionVal(superR), cr.getSVal()); } } } } - + // Perform the binding. RegionBindings B = GetRegionBindings(state->getStore()); return state->makeWithStore(RBFactory.Add(B, R, V).getRoot()); @@ -1332,7 +1332,7 @@ const GRState * RegionStoreManager::BindCompoundLiteral(const GRState *state, const CompoundLiteralExpr* CL, SVal V) { - + CompoundLiteralRegion* R = MRMgr.getCompoundLiteralRegion(CL); return Bind(state, loc::MemRegionVal(R), V); } @@ -1376,12 +1376,12 @@ const GRState *RegionStoreManager::BindArray(const GRState *state, // Handle lazy compound values. if (nonloc::LazyCompoundVal *LCV = dyn_cast<nonloc::LazyCompoundVal>(&Init)) return CopyLazyBindings(*LCV, state, R); - - // Remaining case: explicit compound values. + + // Remaining case: explicit compound values. nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(Init); nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); uint64_t i = 0; - + for (; i < size; ++i, ++VI) { // The init list might be shorter than the array length. if (VI == VE) @@ -1411,10 +1411,10 @@ const GRState *RegionStoreManager::BindArray(const GRState *state, const GRState * RegionStoreManager::BindStruct(const GRState *state, const TypedRegion* R, SVal V) { - + if (!Features.supportsFields()) return state; - + QualType T = R->getValueType(getContext()); assert(T->isStructureType()); @@ -1427,7 +1427,7 @@ RegionStoreManager::BindStruct(const GRState *state, const TypedRegion* R, // Handle lazy compound values. if (const nonloc::LazyCompoundVal *LCV = dyn_cast<nonloc::LazyCompoundVal>(&V)) return CopyLazyBindings(*LCV, state, 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)) @@ -1447,7 +1447,7 @@ RegionStoreManager::BindStruct(const GRState *state, const TypedRegion* R, FieldRegion* FR = MRMgr.getFieldRegion(*FI, R); if (Loc::IsLocType(FTy) || FTy->isIntegerType()) - state = Bind(state, ValMgr.makeLoc(FR), *VI); + state = Bind(state, ValMgr.makeLoc(FR), *VI); else if (FTy->isArrayType()) state = BindArray(state, FR, *VI); else if (FTy->isStructureType()) @@ -1484,7 +1484,7 @@ const GRState *RegionStoreManager::setDefaultValue(const GRState *state, const MemRegion* R, SVal V) { return state->set<RegionDefaultValue>(R, V); } - + const GRState* RegionStoreManager::CopyLazyBindings(nonloc::LazyCompoundVal V, const GRState *state, @@ -1496,46 +1496,46 @@ RegionStoreManager::CopyLazyBindings(nonloc::LazyCompoundVal V, RegionDefaultBindings::Factory &DVMFactory = state->get_context<RegionDefaultValue>(); - llvm::OwningPtr<RegionStoreSubRegionMap> + llvm::OwningPtr<RegionStoreSubRegionMap> SubRegions(getRegionStoreSubRegionMap(state)); - // B and DVM are updated after the call to RemoveSubRegionBindings. + // B and DVM are updated after the call to RemoveSubRegionBindings. RemoveSubRegionBindings(B, DVM, DVMFactory, R, *SubRegions.get()); - + // Now copy the bindings. This amounts to just binding 'V' to 'R'. This // results in a zero-copy algorithm. return state->makeWithStore(RBFactory.Add(B, R, V).getRoot()); } - + //===----------------------------------------------------------------------===// // State pruning. //===----------------------------------------------------------------------===// - + static void UpdateLiveSymbols(SVal X, SymbolReaper& SymReaper) { if (loc::MemRegionVal *XR = dyn_cast<loc::MemRegionVal>(&X)) { const MemRegion *R = XR->getRegion(); - + while (R) { if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) { SymReaper.markLive(SR->getSymbol()); return; } - + if (const SubRegion *SR = dyn_cast<SubRegion>(R)) { R = SR->getSuperRegion(); continue; } - + break; } - + return; } - + for (SVal::symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end();SI!=SE;++SI) SymReaper.markLive(*SI); } - + namespace { class VISIBILITY_HIDDEN TreeScanner { RegionBindings B; @@ -1558,71 +1558,71 @@ public: : B(b), DB(db), SymReaper(symReaper), Marked(marked), ScannedLazyVals(scannedLazyVals), M(m), RS(rs), RegionRoots(regionRoots), MarkKeys(markKeys) {} - + void scanTree(const MemRegion *R); }; } // end anonymous namespace - - + + void TreeScanner::scanTree(const MemRegion *R) { if (MarkKeys) { if (Marked.count(R)) - return; - + return; + Marked.insert(R); } - + // 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()); - + // Get the data binding for R (if any). const SVal* Xptr = B.lookup(R); - + // Check for lazy bindings. if (const nonloc::LazyCompoundVal *V = dyn_cast_or_null<nonloc::LazyCompoundVal>(Xptr)) { - - const LazyCompoundValData *D = V->getCVData(); + + const LazyCompoundValData *D = V->getCVData(); if (!ScannedLazyVals.count(D)) { // Scan the bindings in the LazyCompoundVal. ScannedLazyVals.insert(D); - + // FIXME: Cache subregion maps. const GRState *lazyState = D->getState(); llvm::OwningPtr<RegionStoreSubRegionMap> lazySM(RS.getRegionStoreSubRegionMap(lazyState)); - + Store lazyStore = lazyState->getStore(); RegionBindings lazyB = RS.GetRegionBindings(lazyStore); - + RegionDefaultBindings lazyDB = lazyState->get<RegionDefaultValue>(); - + // Scan the bindings. TreeScanner scan(lazyB, lazyDB, SymReaper, Marked, ScannedLazyVals, *lazySM.get(), RS, RegionRoots, false); - + scan.scanTree(D->getRegion()); } } - else { - // No direct binding? Get the default binding for R (if any). + else { + // No direct binding? Get the default binding for R (if any). if (!Xptr) Xptr = DB.lookup(R); - + // Direct or default binding? if (Xptr) { SVal X = *Xptr; UpdateLiveSymbols(X, SymReaper); // Update the set of live symbols. - + // If X is a region, then add it to the RegionRoots. if (const MemRegion *RX = X.getAsRegion()) { RegionRoots.push_back(RX); // Mark the super region of the RX as live. - // e.g.: int x; char *y = (char*) &x; if (*y) ... + // e.g.: int x; char *y = (char*) &x; if (*y) ... // 'y' => element region. 'x' is its super region. if (const SubRegion *SR = dyn_cast<SubRegion>(RX)) { RegionRoots.push_back(SR->getSuperRegion()); @@ -1630,39 +1630,39 @@ void TreeScanner::scanTree(const MemRegion *R) { } } } - - RegionStoreSubRegionMap::iterator I, E; + + RegionStoreSubRegionMap::iterator I, E; for (llvm::tie(I, E) = M.begin_end(R); I != E; ++I) scanTree(*I); } -void RegionStoreManager::RemoveDeadBindings(GRState &state, Stmt* Loc, +void RegionStoreManager::RemoveDeadBindings(GRState &state, Stmt* Loc, SymbolReaper& SymReaper, llvm::SmallVectorImpl<const MemRegion*>& RegionRoots) -{ +{ Store store = state.getStore(); RegionBindings B = GetRegionBindings(store); - + // Lazily constructed backmap from MemRegions to SubRegions. typedef llvm::ImmutableSet<const MemRegion*> SubRegionsTy; typedef llvm::ImmutableMap<const MemRegion*, SubRegionsTy> SubRegionsMapTy; - + // The backmap from regions to subregions. llvm::OwningPtr<RegionStoreSubRegionMap> SubRegions(getRegionStoreSubRegionMap(&state)); - + // 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. + // 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(); IntermediateRoots.push_back(R); } - + // Scan the default bindings for "intermediate" roots. RegionDefaultBindings DVM = state.get<RegionDefaultValue>(); for (RegionDefaultBindings::iterator I = DVM.begin(), E = DVM.end(); @@ -1672,18 +1672,18 @@ void RegionStoreManager::RemoveDeadBindings(GRState &state, Stmt* Loc, } // Process the "intermediate" roots to find if they are referenced by - // real roots. + // real roots. while (!IntermediateRoots.empty()) { const MemRegion* R = IntermediateRoots.back(); IntermediateRoots.pop_back(); - + if (const VarRegion* VR = dyn_cast<VarRegion>(R)) { if (SymReaper.isLive(Loc, VR->getDecl())) { RegionRoots.push_back(VR); // This is a live "root". } continue; } - + if (const SymbolicRegion* SR = dyn_cast<SymbolicRegion>(R)) { if (SymReaper.isLive(SR->getSymbol())) RegionRoots.push_back(SR); @@ -1695,9 +1695,9 @@ void RegionStoreManager::RemoveDeadBindings(GRState &state, Stmt* Loc, dyn_cast<SubRegion>(cast<SubRegion>(R)->getSuperRegion())) IntermediateRoots.push_back(superR); } - + // Process the worklist of RegionRoots. This performs a "mark-and-sweep" - // of the store. We want to find all live symbols and dead regions. + // of the store. We want to find all live symbols and dead regions. llvm::DenseSet<const MemRegion*> Marked; llvm::DenseSet<const LazyCompoundValData*> LazyVals; TreeScanner TS(B, DVM, SymReaper, Marked, LazyVals, *SubRegions.get(), @@ -1707,59 +1707,59 @@ void RegionStoreManager::RemoveDeadBindings(GRState &state, Stmt* Loc, const MemRegion *R = RegionRoots.back(); RegionRoots.pop_back(); TS.scanTree(R); - } - + } + // 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. + // as well as update DSymbols with the set symbols that are now dead. for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) { const MemRegion* R = I.getKey(); // If this region live? Is so, none of its symbols are dead. if (Marked.count(R)) continue; - + // Remove this dead region from the store. store = Remove(store, ValMgr.makeLoc(R)); - + // 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); } - - // Remove dead 'default' bindings. + + // Remove dead 'default' bindings. RegionDefaultBindings NewDVM = DVM; - RegionDefaultBindings::Factory &DVMFactory = + RegionDefaultBindings::Factory &DVMFactory = state.get_context<RegionDefaultValue>(); - + for (RegionDefaultBindings::iterator I = DVM.begin(), E = DVM.end(); I != E; ++I) { const MemRegion *R = I.getKey(); - + // If this region live? Is so, none of its symbols are dead. if (Marked.count(R)) continue; - + // Remove this dead region. NewDVM = DVMFactory.Remove(NewDVM, R); - + // 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); } - + // Write the store back. state.setStore(store); - + // Write the updated default bindings back. // FIXME: Right now this involves a fetching of a persistent state. // We can do better. @@ -1775,7 +1775,7 @@ void RegionStoreManager::print(Store store, llvm::raw_ostream& OS, const char* nl, const char *sep) { RegionBindings B = GetRegionBindings(store); OS << "Store (direct bindings):" << nl; - + for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) - OS << ' ' << I.getKey() << " : " << I.getData() << nl; + OS << ' ' << I.getKey() << " : " << I.getData() << nl; } |
