From a5e81f1240bcc5b9b0721fc6275075ad7cadaf5e Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Thu, 6 Aug 2009 01:20:57 +0000 Subject: [PATCH] Implement lazy "copying" of structures and arrays in RegionStore. While RegionStore already lazily abstracted the contents of arrays and structs, when doing an assignment from one array/struct to another we did an explicit element-wise copy, which resulted in a loss of laziness and huge performance problem when analyzing many code bases. Now RegionStoreManager handles such assignments using a new SVal could 'LazyCompoundSVal', which basically means the value of a given struct or array (a MemRegion*) in a specific state (GRState). When we do a load from a field whose encompassing struct binds to a LazyCompoundSVal, we essentially do a field lookup in the original structure. This means we have essentially zero copying of data for structs/arrays and everything stays lazy. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@78268 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../PathSensitive/BasicValueFactory.h | 24 +- .../clang/Analysis/PathSensitive/MemRegion.h | 15 +- include/clang/Analysis/PathSensitive/SVals.h | 23 +- .../Analysis/PathSensitive/ValueManager.h | 4 + lib/Analysis/BasicValueFactory.cpp | 26 +++ lib/Analysis/RegionStore.cpp | 205 ++++++++++++++---- lib/Analysis/SVals.cpp | 16 +- 7 files changed, 271 insertions(+), 42 deletions(-) diff --git a/include/clang/Analysis/PathSensitive/BasicValueFactory.h b/include/clang/Analysis/PathSensitive/BasicValueFactory.h index 71a705d2d7..74d08e8410 100644 --- a/include/clang/Analysis/PathSensitive/BasicValueFactory.h +++ b/include/clang/Analysis/PathSensitive/BasicValueFactory.h @@ -25,6 +25,8 @@ namespace clang { + class GRState; + class CompoundValData : public llvm::FoldingSetNode { QualType T; llvm::ImmutableList L; @@ -43,6 +45,22 @@ public: void Profile(llvm::FoldingSetNodeID& ID) { Profile(ID, T, L); } }; +class LazyCompoundValData : public llvm::FoldingSetNode { + const GRState *state; + const TypedRegion *region; +public: + LazyCompoundValData(const GRState *st, const TypedRegion *r) + : state(st), region(r) {} + + const GRState *getState() const { return state; } + const TypedRegion *getRegion() const { return region; } + + static void Profile(llvm::FoldingSetNodeID& ID, const GRState *state, + const TypedRegion *region); + + void Profile(llvm::FoldingSetNodeID& ID) { Profile(ID, state, region); } +}; + class BasicValueFactory { typedef llvm::FoldingSet > APSIntSetTy; @@ -56,6 +74,7 @@ class BasicValueFactory { llvm::ImmutableList::Factory SValListFactory; llvm::FoldingSet CompoundValDataSet; + llvm::FoldingSet LazyCompoundValDataSet; public: BasicValueFactory(ASTContext& ctx, llvm::BumpPtrAllocator& Alloc) @@ -138,9 +157,12 @@ public: return getTruthValue(b, Ctx.IntTy); } - const CompoundValData* getCompoundValData(QualType T, + const CompoundValData *getCompoundValData(QualType T, llvm::ImmutableList Vals); + const LazyCompoundValData *getLazyCompoundValData(const GRState *state, + const TypedRegion *region); + llvm::ImmutableList getEmptySValList() { return SValListFactory.GetEmptyList(); } diff --git a/include/clang/Analysis/PathSensitive/MemRegion.h b/include/clang/Analysis/PathSensitive/MemRegion.h index 5d4c6137bc..cfa9498d7d 100644 --- a/include/clang/Analysis/PathSensitive/MemRegion.h +++ b/include/clang/Analysis/PathSensitive/MemRegion.h @@ -638,16 +638,27 @@ public: /// getElementRegion - Retrieve the memory region associated with the /// associated element type, index, and super region. - ElementRegion* getElementRegion(QualType elementType, SVal Idx, + ElementRegion *getElementRegion(QualType elementType, SVal Idx, const MemRegion* superRegion,ASTContext &Ctx); + + ElementRegion *getElementRegionWithSuper(const ElementRegion *ER, + const MemRegion *superRegion) { + return getElementRegion(ER->getElementType(), ER->getIndex(), + superRegion, ER->getContext()); + } /// getFieldRegion - Retrieve or create the memory region associated with /// a specified FieldDecl. 'superRegion' corresponds to the containing /// memory region (which typically represents the memory representing /// a structure or class). - FieldRegion* getFieldRegion(const FieldDecl* fd, + FieldRegion *getFieldRegion(const FieldDecl* fd, const MemRegion* superRegion); + FieldRegion *getFieldRegionWithSuper(const FieldRegion *FR, + const MemRegion *superRegion) { + return getFieldRegion(FR->getDecl(), superRegion); + } + /// getObjCObjectRegion - Retrieve or create the memory region associated with /// the instance of a specified Objective-C class. ObjCObjectRegion* getObjCObjectRegion(const ObjCInterfaceDecl* ID, diff --git a/include/clang/Analysis/PathSensitive/SVals.h b/include/clang/Analysis/PathSensitive/SVals.h index 63110c6fac..79b7316547 100644 --- a/include/clang/Analysis/PathSensitive/SVals.h +++ b/include/clang/Analysis/PathSensitive/SVals.h @@ -30,8 +30,11 @@ namespace llvm { namespace clang { class CompoundValData; +class LazyCompoundValData; +class GRState; class BasicValueFactory; class MemRegion; +class TypedRegion; class MemRegionManager; class GRStateManager; class ValueManager; @@ -211,7 +214,7 @@ public: namespace nonloc { enum Kind { ConcreteIntKind, SymbolValKind, SymExprValKind, - LocAsIntegerKind, CompoundValKind }; + LocAsIntegerKind, CompoundValKind, LazyCompoundValKind }; class SymbolVal : public NonLoc { public: @@ -334,6 +337,24 @@ public: } }; +class LazyCompoundVal : public NonLoc { + friend class clang::ValueManager; + + LazyCompoundVal(const LazyCompoundValData *D) + : NonLoc(LazyCompoundValKind, D) {} +public: + const GRState *getState() const; + const TypedRegion *getRegion() const; + + static bool classof(const SVal *V) { + return V->getBaseKind() == NonLocKind && + V->getSubKind() == LazyCompoundValKind; + } + static bool classof(const NonLoc *V) { + return V->getSubKind() == LazyCompoundValKind; + } +}; + } // end namespace clang::nonloc //==------------------------------------------------------------------------==// diff --git a/include/clang/Analysis/PathSensitive/ValueManager.h b/include/clang/Analysis/PathSensitive/ValueManager.h index cc4fe9fc63..8aa7a7711b 100644 --- a/include/clang/Analysis/PathSensitive/ValueManager.h +++ b/include/clang/Analysis/PathSensitive/ValueManager.h @@ -113,6 +113,10 @@ public: NonLoc makeCompoundVal(QualType T, llvm::ImmutableList Vals) { return nonloc::CompoundVal(BasicVals.getCompoundValData(T, Vals)); } + + NonLoc makeLazyCompoundVal(const GRState *state, const TypedRegion *R) { + return nonloc::LazyCompoundVal(BasicVals.getLazyCompoundValData(state, R)); + } NonLoc makeZeroArrayIndex() { return nonloc::ConcreteInt(BasicVals.getValue(0, ArrayIndexTy)); diff --git a/lib/Analysis/BasicValueFactory.cpp b/lib/Analysis/BasicValueFactory.cpp index 72ad0a5ed8..5ed6d22769 100644 --- a/lib/Analysis/BasicValueFactory.cpp +++ b/lib/Analysis/BasicValueFactory.cpp @@ -23,6 +23,13 @@ void CompoundValData::Profile(llvm::FoldingSetNodeID& ID, QualType T, ID.AddPointer(L.getInternalPointer()); } +void LazyCompoundValData::Profile(llvm::FoldingSetNodeID& ID, + const GRState *state, + const TypedRegion *region) { + ID.AddPointer(state); + ID.AddPointer(region); +} + typedef std::pair SValData; typedef std::pair SValPair; @@ -116,6 +123,25 @@ BasicValueFactory::getCompoundValData(QualType T, return D; } +const LazyCompoundValData* +BasicValueFactory::getLazyCompoundValData(const GRState *state, + const TypedRegion *region) { + llvm::FoldingSetNodeID ID; + LazyCompoundValData::Profile(ID, state, region); + void* InsertPos; + + LazyCompoundValData *D = + LazyCompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos); + + if (!D) { + D = (LazyCompoundValData*) BPAlloc.Allocate(); + new (D) LazyCompoundValData(state, region); + LazyCompoundValDataSet.InsertNode(D, InsertPos); + } + + return D; +} + const llvm::APSInt* BasicValueFactory::EvaluateAPSInt(BinaryOperator::Opcode Op, const llvm::APSInt& V1, const llvm::APSInt& V2) { diff --git a/lib/Analysis/RegionStore.cpp b/lib/Analysis/RegionStore.cpp index 398babc9d7..d556aed73a 100644 --- a/lib/Analysis/RegionStore.cpp +++ b/lib/Analysis/RegionStore.cpp @@ -28,6 +28,7 @@ using namespace clang; #define HEAP_UNDEFINED 0 +#define USE_EXPLICIT_COMPOUND 0 // Actual Store type. typedef llvm::ImmutableMap RegionBindingsTy; @@ -130,6 +131,8 @@ public: I->second = F.Add(I->second, SubRegion); return false; } + + void process(llvm::SmallVectorImpl &WL, const SubRegion *R); ~RegionStoreSubRegionMap() {} @@ -246,9 +249,11 @@ public: const Expr *E, unsigned Count); private: - RegionBindingsTy RemoveSubRegionBindings(RegionBindingsTy B, - const MemRegion *R, - RegionStoreSubRegionMap &M); + void RemoveSubRegionBindings(RegionBindingsTy &B, + RegionDefaultValue::MapTy &DVM, + RegionDefaultValue::MapTy::Factory &DVMFactory, + const MemRegion *R, + RegionStoreSubRegionMap &M); public: const GRState *Bind(const GRState *state, Loc LV, SVal V); @@ -313,6 +318,13 @@ public: SVal RetrieveStruct(const GRState *St, const TypedRegion* R); SVal RetrieveArray(const GRState *St, const TypedRegion* R); + + std::pair + GetLazyBinding(RegionBindingsTy B, const MemRegion *R); + + const GRState* CopyLazyBindings(nonloc::LazyCompoundVal V, + const GRState *state, + const TypedRegion *R); //===------------------------------------------------------------------===// // State pruning. @@ -381,37 +393,38 @@ StoreManager *clang::CreateFieldsOnlyRegionStoreManager(GRStateManager &StMgr) { return new RegionStoreManager(StMgr, F); } +void +RegionStoreSubRegionMap::process(llvm::SmallVectorImpl &WL, + const SubRegion *R) { + const MemRegion *superR = R->getSuperRegion(); + if (add(superR, R)) + if (const SubRegion *sr = dyn_cast(superR)) + WL.push_back(sr); +} + RegionStoreSubRegionMap* RegionStoreManager::getRegionStoreSubRegionMap(const GRState *state) { RegionBindingsTy B = GetRegionBindings(state->getStore()); RegionStoreSubRegionMap *M = new RegionStoreSubRegionMap(); - llvm::SmallPtrSet Marked; llvm::SmallVector WL; for (RegionBindingsTy::iterator I=B.begin(), E=B.end(); I!=E; ++I) - if (const SubRegion* R = dyn_cast(I.getKey())) - WL.push_back(R); - + if (const SubRegion *R = dyn_cast(I.getKey())) + M->process(WL, R); + RegionDefaultValue::MapTy DVM = state->get(); for (RegionDefaultValue::MapTy::iterator I = DVM.begin(), E = DVM.end(); - I != E; ++I) - if (const SubRegion* R = dyn_cast(I.getKey())) - WL.push_back(R); + I != E; ++I) + if (const SubRegion *R = dyn_cast(I.getKey())) + 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(); - - if (Marked.count(R)) - continue; - - const MemRegion *superR = R->getSuperRegion(); - if (M->add(superR, R)) - if (const SubRegion *sr = dyn_cast(superR)) - WL.push_back(sr); + M->process(WL, R); } return M; @@ -425,17 +438,20 @@ SubRegionMap *RegionStoreManager::getSubRegionMap(const GRState *state) { // Binding invalidation. //===----------------------------------------------------------------------===// -RegionBindingsTy -RegionStoreManager::RemoveSubRegionBindings(RegionBindingsTy B, - const MemRegion *R, - RegionStoreSubRegionMap &M) { +void +RegionStoreManager::RemoveSubRegionBindings(RegionBindingsTy &B, + RegionDefaultValue::MapTy &DVM, + RegionDefaultValue::MapTy::Factory &DVMFactory, + const MemRegion *R, + RegionStoreSubRegionMap &M) { RegionStoreSubRegionMap::iterator I, E; for (llvm::tie(I, E) = M.begin_end(R); I != E; ++I) - B = RemoveSubRegionBindings(B, *I, M); + RemoveSubRegionBindings(B, DVM, DVMFactory, *I, M); - return RBFactory.Remove(B, R); + B = RBFactory.Remove(B, R); + DVM = DVMFactory.Remove(DVM, R); } @@ -448,15 +464,21 @@ const GRState *RegionStoreManager::InvalidateRegion(const GRState *state, // Strip away casts. R = R->getBaseRegion(); - // Get the mapping of regions -> subregions. - llvm::OwningPtr - SubRegions(getRegionStoreSubRegionMap(state)); - // Remove the bindings to subregions. - RegionBindingsTy B = GetRegionBindings(state->getStore()); - B = RemoveSubRegionBindings(B, R, *SubRegions.get()); - state = state->makeWithStore(B.getRoot()); - + { + // Get the mapping of regions -> subregions. + llvm::OwningPtr + SubRegions(getRegionStoreSubRegionMap(state)); + + RegionBindingsTy B = GetRegionBindings(state->getStore()); + RegionDefaultValue::MapTy DVM = state->get(); + RegionDefaultValue::MapTy::Factory &DVMFactory = + state->get_context(); + + RemoveSubRegionBindings(B, DVM, DVMFactory, R, *SubRegions.get()); + state = state->makeWithStore(B.getRoot())->set(DVM); + } + if (!R->isBoundable()) return state; @@ -975,7 +997,32 @@ RegionStoreManager::Retrieve(const GRState *state, Loc L, QualType T) { ValMgr.getRegionValueSymbolValOrUnknown(R, RTy)); } +std::pair +RegionStoreManager::GetLazyBinding(RegionBindingsTy B, const MemRegion *R) { + + if (const nonloc::LazyCompoundVal *V = + dyn_cast_or_null(B.lookup(R))) + return std::make_pair(V->getState(), V->getRegion()); + + if (const ElementRegion *ER = dyn_cast(R)) { + const std::pair &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(R)) { + const std::pair &X = + GetLazyBinding(B, FR->getSuperRegion()); + + if (X.first) + return std::make_pair(X.first, + MRMgr.getFieldRegionWithSuper(FR, X.second)); + } + return std::make_pair((const GRState*) 0, (const MemRegion *) 0); +} SVal RegionStoreManager::RetrieveElement(const GRState* state, const ElementRegion* R) { @@ -1039,10 +1086,30 @@ SVal RegionStoreManager::RetrieveElement(const GRState* state, if (V->isUnknownOrUndef()) return *V; + // Handle LazyCompoundVals below. + if (const nonloc::LazyCompoundVal *LVC = + dyn_cast(V)) { + return RetrieveElement(LVC->getState(), + MRMgr.getElementRegionWithSuper(R, + LVC->getRegion())); + } + // Other cases: give up. return UnknownVal(); } + // 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"); + return RetrieveElement(lazyBindingState, + cast(LazyBindingRegion)); + } + + // Default value cases. #if 0 if (R->hasHeapStorage()) { // FIXME: If the region has heap storage and we know nothing special @@ -1093,12 +1160,25 @@ SVal RegionStoreManager::RetrieveField(const GRState* state, if (D->isZeroConstant()) return ValMgr.makeZeroVal(Ty); + + if (const nonloc::LazyCompoundVal *LCV = + dyn_cast(D)) { + const FieldRegion *FR = + MRMgr.getFieldRegionWithSuper(R, LCV->getRegion()); + return RetrieveField(LCV->getState(), FR); + } if (D->isUnknown()) return *D; assert(0 && "Unknown default value"); } + + if (const SVal *V = B.lookup(superR)) { + // Handle LazyCompoundVals below. + if (isa(*V)) + break; + } // 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. @@ -1108,7 +1188,18 @@ SVal RegionStoreManager::RetrieveField(const GRState* state, } 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"); + return RetrieveField(lazyBindingState, + cast(LazyBindingRegion)); + } #if HEAP_UNDEFINED // FIXME: Is this correct? Should it be UnknownVal? @@ -1206,7 +1297,7 @@ SVal RegionStoreManager::RetrieveStruct(const GRState *state, const RecordType* RT = T->getAsStructureType(); RecordDecl* RD = RT->getDecl(); assert(RD->isDefinition()); - +#if USE_EXPLICIT_COMPOUND llvm::ImmutableList StructVal = getBasicVals().getEmptySValList(); // FIXME: We shouldn't use a std::vector. If RecordDecl doesn't have a @@ -1223,11 +1314,14 @@ SVal RegionStoreManager::RetrieveStruct(const GRState *state, } return ValMgr.makeCompoundVal(T, StructVal); +#else + return ValMgr.makeLazyCompoundVal(state, R); +#endif } SVal RegionStoreManager::RetrieveArray(const GRState *state, const TypedRegion * R) { - +#if USE_EXPLICIT_COMPOUND QualType T = R->getValueType(getContext()); ConstantArrayType* CAT = cast(T.getTypePtr()); @@ -1243,6 +1337,10 @@ SVal RegionStoreManager::RetrieveArray(const GRState *state, } return ValMgr.makeCompoundVal(T, ArrayVal); +#else + assert(isa(R->getValueType(getContext()))); + return ValMgr.makeLazyCompoundVal(state, R); +#endif } SValuator::CastResult RegionStoreManager::CastRetrievedVal(SVal V, @@ -1311,8 +1409,7 @@ const GRState *RegionStoreManager::Bind(const GRState *state, Loc L, SVal V) { // Perform the binding. RegionBindingsTy B = GetRegionBindings(state->getStore()); - B = RBFactory.Add(B, R, V); - return state->makeWithStore(B.getRoot()); + return state->makeWithStore(RBFactory.Add(B, R, V).getRoot()); } const GRState *RegionStoreManager::BindDecl(const GRState *state, @@ -1375,6 +1472,11 @@ const GRState *RegionStoreManager::BindArray(const GRState *state, return state; } + // Handle lazy compound values. + if (nonloc::LazyCompoundVal *LCV = dyn_cast(&Init)) + return CopyLazyBindings(*LCV, state, R); + + // Remaining case: explicit compound values. nonloc::CompoundVal& CV = cast(Init); nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); uint64_t i = 0; @@ -1421,6 +1523,10 @@ RegionStoreManager::BindStruct(const GRState *state, const TypedRegion* R, if (!RD->isDefinition()) return state; + // Handle lazy compound values. + if (const nonloc::LazyCompoundVal *LCV = dyn_cast(&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(V)) @@ -1477,7 +1583,29 @@ const GRState *RegionStoreManager::setDefaultValue(const GRState *state, const MemRegion* R, SVal V) { return state->set(R, V); } + +const GRState* +RegionStoreManager::CopyLazyBindings(nonloc::LazyCompoundVal V, + const GRState *state, + const TypedRegion *R) { + + // Nuke the old bindings stemming from R. + RegionBindingsTy B = GetRegionBindings(state->getStore()); + RegionDefaultValue::MapTy DVM = state->get(); + RegionDefaultValue::MapTy::Factory &DVMFactory = + state->get_context(); + llvm::OwningPtr + SubRegions(getRegionStoreSubRegionMap(state)); + + // 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. //===----------------------------------------------------------------------===// @@ -1666,6 +1794,9 @@ void RegionStoreManager::RemoveDeadBindings(GRState &state, Stmt* Loc, SymReaper.maybeDead(*SI); } + // FIXME: Do a pass over nonloc::LazyCompoundVals and the symbols + // that they reference. + // Write the store back. state.setStore(store); diff --git a/lib/Analysis/SVals.cpp b/lib/Analysis/SVals.cpp index 5ac18a1506..c597ba459e 100644 --- a/lib/Analysis/SVals.cpp +++ b/lib/Analysis/SVals.cpp @@ -158,6 +158,14 @@ void SVal::symbol_iterator::expand() { assert(false && "unhandled expansion case"); } +const GRState *nonloc::LazyCompoundVal::getState() const { + return static_cast(Data)->getState(); +} + +const TypedRegion *nonloc::LazyCompoundVal::getRegion() const { + return static_cast(Data)->getRegion(); +} + //===----------------------------------------------------------------------===// // Other Iterators. //===----------------------------------------------------------------------===// @@ -289,7 +297,13 @@ void NonLoc::dumpToStream(llvm::raw_ostream& os) const { } os << "}"; break; - } + } + case nonloc::LazyCompoundValKind: { + const nonloc::LazyCompoundVal &C = *cast(this); + os << "lazyCompoundVal{" << (void*) C.getState() << ',' << C.getRegion() + << '}'; + break; + } default: assert (false && "Pretty-printed not implemented for this NonLoc."); break; -- 2.40.0