[cfe-dev] Lazy bindings
Ted Kremenek
kremenek at apple.com
Thu Dec 18 18:50:37 PST 2008
On Dec 17, 2008, at 4:22 AM, Zhongxing Xu wrote:
> Hi Ted,
>
> This is the patch for lazy binding.
I have some specific comments on the patch below. Two main comments:
1) Aside from Bind() returning a GRState* instead of Store, let's keep
BasicStoreManager the same. It works just fine for what it was
intended to do. The reason I get scared about large patches is the
huge functionality changes. BasicStoreManager just keeps binding for
the VarDecls that are referenced within a function. I haven't
encountered any scalability issues with it. We don't need to use a
killset. By keeping it the same we preserve its stability. New
functionality should go into RegionStoreManager. BasicStoreManager
doesn't need to be lazy in the same way.
2) Rename GRStateManager::getState() to MakeStateWithStore() (or
something similar). It makes it clear what it is doing.
'get'State()' is so short and ambiguous that it has no real meaning,
and such an important function shouldn't be ambiguous.
> * failed C test cases are due to bugs in RemoveDeadBindings(),
> which removes constraints that is still alive. I plan to fix this
> in a later patch. This patch is already messy enough.
Let's temporarily disable those tests (if necessary) for region store
and then fix them in later patches. Since there won't be any
fundamental changes to BasicStoreManager all tests should pass for it.
>
> * I wish you could help fix failed ObjC test cases, since I have
> no access to the Mac development platform. It'll take some time for me
> to learn basic things.
Sure thing. Same as the above comment (disable tests for region store
and fix in later patch).
> * default value of array and struct regions are not implemented
> yet, because the GDM of the same type of ImmutableMap<const
> Region*, SVal> is already used for region extents.
In a later patch we'll use the "tag class" approach I mentioned in my
other email.
> * Now Bind() methods take and return GRState* because binding could
> also alter GDM.
Looks great. As I said before, have BasicStoreManager use the new
interface (return a state) but don't change its functionality.
> * No variables are initialized except those declared with initial
> values.
Okay!
Here are specific comments:
Index: include/clang/Analysis/PathSensitive/Store.h
===================================================================
--- include/clang/Analysis/PathSensitive/Store.h （版本 61131）
+++ include/clang/Analysis/PathSensitive/Store.h （工作副本）
@@ -49,16 +49,17 @@
SVal GetRegionSVal(const GRState* state, const MemRegion* R) {
return Retrieve(state, loc::MemRegionVal(R));
}
-
- virtual Store Bind(Store St, Loc LV, SVal V) = 0;
+
+ virtual const GRState* Bind(const GRState* St, Loc LV, SVal V) = 0;
Looks good. Let's take the opportunity to add a comment about what
this method does.
/// BindCompoundLiteral - Return the store that has the bindings
currently
/// in 'store' plus the bindings for the CompoundLiteral. 'R' is
the region
/// for the compound literal and 'BegInit' and 'EndInit'
represent an
/// array of initializer values.
- virtual Store BindCompoundLiteral(Store store, const
CompoundLiteralExpr* CL,
- SVal V) = 0;
+ virtual const GRState* BindCompoundLiteral(const GRState* St,
+ const
CompoundLiteralExpr* CL,
+ SVal V) = 0;
Looks great.
llvm::SmallVectorImpl<const MemRegion*>&
RegionRoots,
LiveSymbolsTy& LSymbols, DeadSymbolsTy&
DSymbols) = 0;
- virtual Store BindDecl(Store store, const VarDecl* VD, SVal* InitVal,
- unsigned Count) = 0;
+ virtual const GRState* BindDecl(const GRState* St, const VarDecl* VD,
+ SVal InitVal) = 0;
Looks great. A natural change of interface.
Index: include/clang/Analysis/PathSensitive/SymbolManager.h
===================================================================
--- include/clang/Analysis/PathSensitive/SymbolManager.h （版本
61131）
+++ include/clang/Analysis/PathSensitive/SymbolManager.h （工作副
本）
@@ -104,15 +104,15 @@
};
class SymbolDataParmVar : public SymbolData {
- ParmVarDecl *VD;
+ const ParmVarDecl *VD;
public:
- SymbolDataParmVar(SymbolRef MySym, ParmVarDecl* vd)
+ SymbolDataParmVar(SymbolRef MySym, const ParmVarDecl* vd)
: SymbolData(ParmKind, MySym), VD(vd) {}
- ParmVarDecl* getDecl() const { return VD; }
+ const ParmVarDecl* getDecl() const { return VD; }
- static void Profile(llvm::FoldingSetNodeID& profile, ParmVarDecl*
VD) {
+ static void Profile(llvm::FoldingSetNodeID& profile, const
ParmVarDecl* VD) {
profile.AddInteger((unsigned) ParmKind);
profile.AddPointer(VD);
}
@@ -128,15 +128,15 @@
};
Nice constification.
class SymbolDataGlobalVar : public SymbolData {
- VarDecl *VD;
+ const VarDecl *VD;
public:
- SymbolDataGlobalVar(SymbolRef MySym, VarDecl* vd) :
+ SymbolDataGlobalVar(SymbolRef MySym, const VarDecl* vd) :
SymbolData(GlobalKind, MySym), VD(vd) {}
- VarDecl* getDecl() const { return VD; }
+ const VarDecl* getDecl() const { return VD; }
- static void Profile(llvm::FoldingSetNodeID& profile, VarDecl* VD) {
+ static void Profile(llvm::FoldingSetNodeID& profile, const VarDecl*
VD) {
profile.AddInteger((unsigned) GlobalKind);
profile.AddPointer(VD);
}
Again, nice constification.
@@ -275,8 +275,9 @@
: SymbolCounter(0), BPAlloc(bpalloc) {}
~SymbolManager();
-
- SymbolRef getSymbol(VarDecl* D);
+
+ SymbolRef getSymbol(const MemRegion* R);
Please add a comment about what getSymbol : MemRegion* -> SymbolRef
does.
+ SymbolRef getSymbol(const VarDecl* D);
SymbolRef getElementSymbol(const MemRegion* R, const llvm::APSInt*
Idx);
SymbolRef getFieldSymbol(const MemRegion* R, const FieldDecl* D);
SymbolRef getConjuredSymbol(Stmt* E, QualType T, unsigned
VisitCount);
Index: include/clang/Analysis/PathSensitive/GRState.h
===================================================================
--- include/clang/Analysis/PathSensitive/GRState.h （版本 61131）
+++ include/clang/Analysis/PathSensitive/GRState.h （工作副本）
@@ -335,8 +335,9 @@
typedef StoreManager::DeadSymbolsTy DeadSymbolsTy;
- const GRState* BindDecl(const GRState* St, const VarDecl* VD, SVal*
IVal,
- unsigned Count);
+ const GRState* BindDecl(const GRState* St, const VarDecl* VD, SVal
IVal) {
+ return StoreMgr->BindDecl(St, VD, IVal);
+ }
Okay. Here the assumption is that StoreManager::BindDecl will return
a persistent GRState. Can you add a comment above the call to
StoreMgr->BindDecl() that states that assumption?
/// BindCompoundLiteral - Return the state that has the bindings
currently
/// in 'state' plus the bindings for the CompoundLiteral. 'R' is
the region
@@ -467,9 +468,9 @@
return StoreMgr->GetRegionSVal(state, R);
}
- void BindLoc(GRState& St, Loc LV, SVal V) {
- St.St = StoreMgr->Bind(St.St, LV, V);
- }
+// void BindLoc(GRState& St, Loc LV, SVal V) {
+// St.St = StoreMgr->Bind(St.St, LV, V);
+// }
Don't comment it out. Just remove it if it is no longer used.
Getting rid of garbage code is a good thing.
const GRState* BindLoc(const GRState* St, Loc LV, SVal V);
@@ -480,6 +481,9 @@
const GRState* Unbind(const GRState* St, Loc LV);
const GRState* getPersistentState(GRState& Impl);
+
+ // getState - get a persistent state with the new store.
+ const GRState* getState(const GRState* St, Store store);
Let's use a different name. I know you like to keep things succinct,
but this is such an important method that we should make it unambiguous.
+
template <typename T>
+ const GRState* add(const GRState* st,
+ typename GRStateTrait<T>::key_type K,
+ typename GRStateTrait<T>::context_type C) {
+ return addGDM(st, GRStateTrait<T>::GDMIndex(),
+ GRStateTrait<T>::MakeVoidPtr(GRStateTrait<T>::Add(st-
>get<T>(), K, C)));
+ }
Looks good.
- GRStateRef BindDecl(const VarDecl* VD, SVal* InitVal, unsigned
Count) {
- return GRStateRef(Mgr->BindDecl(St, VD, InitVal, Count), *Mgr);
+ GRStateRef BindDecl(const VarDecl* VD, SVal InitVal) {
+ return GRStateRef(Mgr->BindDecl(St, VD, InitVal), *Mgr);
}
Looks good.
GRStateRef BindLoc(Loc LV, SVal V) {
- GRState StImpl = *St;
- Mgr->BindLoc(StImpl, LV, V);
- return GRStateRef(Mgr->getPersistentState(StImpl), *Mgr);
+ St = Mgr->BindLoc(St, LV, V);
+ return GRStateRef(St, *Mgr);
}
Looks good. You can also make it more succinct:
return GRStateRef(Mgr->BindLoc(St, LV, V), *Mgr);
-
+
+ // For ImmutableSet specialization.
template<typename T>
+ GRStateRef add(typename GRStateTrait<T>::key_type K) {
+ return GRStateRef(Mgr->add<T>(St, K, get_context<T>()), *Mgr);
+ }
The comment does really go to the generality of the interface. It
really has to do with any GDM entry where the key type is the same as
the data. Right now that is ImmutableSet<.>, but it could be anything
with a similar interface.
+
+ template<typename T>
GRStateRef remove(typename GRStateTrait<T>::key_type K,
typename GRStateTrait<T>::context_type C) {
return GRStateRef(Mgr->remove<T>(St, K, C), *Mgr);
@@ -657,7 +674,7 @@
template<typename T>
bool contains(typename GRStateTrait<T>::key_type key) const {
- return St->contains(key);
+ return St->contains<T>(key);
}
Okay.
// Lvalue methods.
Index: include/clang/Analysis/PathSensitive/GRStateTrait.h
===================================================================
--- include/clang/Analysis/PathSensitive/GRStateTrait.h （版本
61131）
+++ include/clang/Analysis/PathSensitive/GRStateTrait.h （工作副
本）
@@ -83,7 +83,11 @@
static inline void* MakeVoidPtr(data_type B) {
return B.getRoot();
- }
+ }
+
+ static data_type Add(data_type B, key_type K, context_type F) {
+ return F.Add(B, K);
+ }
Nice.
Index: include/clang/Analysis/PathSensitive/MemRegion.h
===================================================================
--- include/clang/Analysis/PathSensitive/MemRegion.h （版本 61131）
+++ include/clang/Analysis/PathSensitive/MemRegion.h （工作副本）
@@ -99,7 +99,7 @@
const MemRegion* getSuperRegion() const {
return superRegion;
}
-
+
static bool classof(const MemRegion* R) {
return R->getKind() > SymbolicRegionKind;
}
@@ -464,6 +464,9 @@
assert(R);
return R == globals;
}
+
+ bool onStack(const MemRegion* R);
+ bool onHeap(const MemRegion* R);
Looks good. Doxygen comments please!
/// getAllocaRegion - Retrieve a region associated with a call to
alloca().
AllocaRegion* getAllocaRegion(const Expr* Ex, unsigned Cnt);
Index: include/clang/Analysis/PathSensitive/SVals.h
===================================================================
--- include/clang/Analysis/PathSensitive/SVals.h （版本 61131）
+++ include/clang/Analysis/PathSensitive/SVals.h （工作副本）
@@ -71,7 +71,8 @@
inline bool operator!=(const SVal& R) const {
return !(*this == R);
}
-
+ static SVal MakeSymbolValue(SymbolManager& SymMgr, const MemRegion*
R,
+ QualType T);
What does this method do? Does it create a symbol value that has the
rvalue type of 'R' and ... ? (a couple comments should suffice).
What about arrays? structs? Basically, what is the interface of this
function?
static SVal GetSymbolValue(SymbolManager& SymMgr, VarDecl *D);
static SVal getSymbolValue(SymbolManager& SymMgr, const MemRegion*
R,
const llvm::APSInt* Idx, QualType T);
@@ -171,6 +172,8 @@
// Utility methods to create NonLocs.
+ static NonLoc MakeVal(SymbolRef sym);
+
Looks good.
static NonLoc MakeVal(BasicValueFactory& BasicVals, unsigned X,
bool isUnsigned);
@@ -212,6 +215,8 @@
static Loc MakeVal(const MemRegion* R);
static Loc MakeVal(AddrLabelExpr* E);
+
+ static Loc MakeVal(SymbolRef sym);
Looks good.
Index: lib/Analysis/GRState.cpp
===================================================================
--- lib/Analysis/GRState.cpp （版本 61131）
+++ lib/Analysis/GRState.cpp （工作副本）
@@ -60,48 +60,17 @@
}
const GRState* GRStateManager::BindLoc(const GRState* St, Loc LV,
SVal V) {
-
- Store OldStore = St->getStore();
- Store NewStore = StoreMgr->Bind(OldStore, LV, V);
-
- if (NewStore == OldStore)
- return St;
-
- GRState NewSt = *St;
- NewSt.St = NewStore;
- return getPersistentState(NewSt);
+ return StoreMgr->Bind(St, LV, V);
}
Since it is a one liner, we can just inline this in GRState.h.
-const GRState* GRStateManager::BindDecl(const GRState* St, const
VarDecl* VD,
- SVal* InitVal, unsigned
Count) {
- Store OldStore = St->getStore();
- Store NewStore = StoreMgr->BindDecl(OldStore, VD, InitVal, Count);
-
- if (NewStore == OldStore)
- return St;
-
- GRState NewSt = *St;
- NewSt.St = NewStore;
- return getPersistentState(NewSt);
-}
Right, this is now in GRState.h (and a one liner).
-
/// BindCompoundLiteral - Return the store that has the bindings
currently
/// in 'store' plus the bindings for the CompoundLiteral. 'R' is
the region
/// for the compound literal and 'BegInit' and 'EndInit' represent an
/// array of initializer values.
const GRState*
-GRStateManager::BindCompoundLiteral(const GRState* state,
+GRStateManager::BindCompoundLiteral(const GRState* St,
const CompoundLiteralExpr* CL,
SVal ILV) {
-
- Store oldStore = state->getStore();
- Store newStore = StoreMgr->BindCompoundLiteral(oldStore, CL, ILV);
-
- if (newStore == oldStore)
- return state;
-
- GRState newState = *state;
- newState.St = newStore;
- return getPersistentState(newState);
+ return StoreMgr->BindCompoundLiteral(St, CL, ILV);
}
This too can probably just go into GRState.h (one liner).
+const GRState* GRStateManager::getState(const GRState* St, Store
store) {
+ GRState NewSt = *St;
+ NewSt.St = store;
+ return getPersistentState(NewSt);
+}
Needs a better name.
Index: lib/Analysis/MemRegion.cpp
===================================================================
--- lib/Analysis/MemRegion.cpp （版本 61131）
+++ lib/Analysis/MemRegion.cpp （工作副本）
@@ -209,6 +209,20 @@
return LazyAllocate(unknown);
}
+bool MemRegionManager::onStack(const MemRegion* R) {
+ while (const SubRegion* SR = dyn_cast<SubRegion>(R))
+ R = SR->getSuperRegion();
+
+ return (R != 0) && (R == stack);
+}
+
+bool MemRegionManager::onHeap(const MemRegion* R) {
+ while (const SubRegion* SR = dyn_cast<SubRegion>(R))
+ R = SR->getSuperRegion();
+
+ return (R != 0) && (R == heap);
+}
Looks good.
Index: lib/Analysis/SVals.cpp
===================================================================
--- lib/Analysis/SVals.cpp （版本 61131）
+++ lib/Analysis/SVals.cpp （工作副本）
@@ -242,6 +242,11 @@
//
=
=
=----------------------------------------------------------------------
===//
// Utility methods for constructing Non-Locs.
//
=
=
=----------------------------------------------------------------------
===//
+
+NonLoc NonLoc::MakeVal(SymbolRef sym) {
+ return nonloc::SymbolVal(sym);
+}
+
Looks good.
+SVal SVal::MakeSymbolValue(SymbolManager& SymMgr, const MemRegion* R,
+ QualType T) {
+ if (Loc::IsLocType(T))
+ return Loc::MakeVal(SymMgr.getSymbol(R));
+ else
+ return NonLoc::MakeVal(SymMgr.getSymbol(R));
+}
Looks good, but it would be great to specify in SVals.h what this
method does.
Index: lib/Analysis/BasicStore.cpp
===================================================================
--- lib/Analysis/BasicStore.cpp （版本 61131）
+++ lib/Analysis/BasicStore.cpp （工作副本）
@@ -13,6 +13,7 @@
High level comment: don't change this file except to conform to the
new API for Bind(). We want to keep its functionality the same. No
killset or lazy fetching of values in 'Retrieve'. By keeping it the
same we have an anchor of stability to compare against RegionStore.
It doesn't need to do lazy binding because it has no known scalability
issues with its current approach and it is tested and is reliable.
The goal is to get RegionStore to the point where it is more reliable
and scalable than BasicStore and then we just switch over to using
RegionStore by default.
Index: lib/Analysis/SymbolManager.cpp
===================================================================
--- lib/Analysis/SymbolManager.cpp （版本 61131）
+++ lib/Analysis/SymbolManager.cpp （工作副本）
@@ -13,6 +13,7 @@
//
=
=
=----------------------------------------------------------------------
===//
#include "clang/Analysis/PathSensitive/SymbolManager.h"
+#include "clang/Analysis/PathSensitive/MemRegion.h"
#include "llvm/Support/raw_ostream.h"
using namespace clang;
@@ -21,14 +22,35 @@
os << getNumber();
}
-SymbolRef SymbolManager::getSymbol(VarDecl* D) {
+SymbolRef SymbolManager::getSymbol(const MemRegion* R) {
+ switch (R->getKind()) {
+ case MemRegion::VarRegionKind:
+ return getSymbol(cast<VarRegion>(R)->getDecl());
+
+ case MemRegion::ElementRegionKind: {
+ const ElementRegion* ER = cast<ElementRegion>(R);
+ const llvm::APSInt& Idx =
+ cast<nonloc::ConcreteInt>(ER->getIndex()).getValue();
+ return getElementSymbol(ER->getSuperRegion(), &Idx);
+ }
+ case MemRegion::FieldRegionKind: {
+ const FieldRegion* FR = cast<FieldRegion>(R);
+ return getFieldSymbol(FR->getSuperRegion(), FR->getDecl());
+ }
+ default:
+ assert(0 && "unprocessed region");
+ }
+}
At some point we won't need a FieldSymbol or an ElementSymbol, since
all of that information should be in the region.
Index: lib/Analysis/RegionStore.cpp
===================================================================
--- lib/Analysis/RegionStore.cpp （版本 61131）
+++ lib/Analysis/RegionStore.cpp （工作副本）
@@ -62,6 +62,16 @@
};
}
+// Regions that have default value zero.
+// FIXME: redefinition!
+// typedef llvm::ImmutableMap<const MemRegion*, SVal>
RegionDefaultValue;
+// static int RegionDefaultValueIndex = 0;
+// namespace clang {
+// template<> struct GRStateTrait<RegionDefaultValue>
+// : public GRStatePartialTrait<RegionDefaultValue> {
+// static void* GDMIndex() { return &RegionDefaultValueIndex; }
+// };
+// }
Gotcha. This will be worked on in a future patch.
- Store BindCompoundLiteral(Store store, const CompoundLiteralExpr*
CL, SVal V);
+ const GRState* BindCompoundLiteral(const GRState* St,
+ const CompoundLiteralExpr* CL,
SVal V);
Good.
- Store Bind(Store St, Loc LV, SVal V);
+ const GRState* Bind(const GRState* St, Loc LV, SVal V);
Good.
- Store getInitialStore();
+ Store getInitialStore() { return RBFactory.GetEmptyMap().getRoot(); }
Great. Nice and simple!
- Store BindDecl(Store store, const VarDecl* VD, SVal* InitVal,
unsigned Count);
+ const GRState* BindDecl(const GRState* St, const VarDecl* VD, SVal
InitVal);
Good.
- Store InitializeArray(Store store, const TypedRegion* R, SVal Init);
- Store BindArrayToVal(Store store, const TypedRegion* BaseR, SVal V);
- Store BindArrayToSymVal(Store store, const TypedRegion* BaseR);
+ //Store InitializeArray(Store store, const TypedRegion* R, SVal
Init);
+ // Store BindArrayToVal(Store store, const TypedRegion* BaseR, SVal
V);
+ // Store BindArrayToSymVal(Store store, const TypedRegion* BaseR);
Are these going to reimplemented or removed? If reimplemented, add a
FIXME above the commented out prototypes. If removed, just remove them.
- Store InitializeStruct(Store store, const TypedRegion* R, SVal Init);
- Store BindStructToVal(Store store, const TypedRegion* BaseR, SVal V);
- Store BindStructToSymVal(Store store, const TypedRegion* BaseR);
+ //Store InitializeStruct(Store store, const TypedRegion* R, SVal
Init);
+ //Store BindStructToVal(Store store, const TypedRegion* BaseR, SVal
V);
+ //Store BindStructToSymVal(Store store, const TypedRegion* BaseR);
Same thing.
- SVal RetrieveStruct(Store store, const TypedRegion* R);
+ SVal RetrieveStruct(const GRState* St, const TypedRegion* R);
Good.
- Store BindStruct(Store store, const TypedRegion* R, SVal V);
+ const GRState* BindStruct(const GRState* St, const TypedRegion* R,
SVal V);
Good.
-SVal RegionStoreManager::Retrieve(const GRState* state, Loc L,
QualType T) {
+SVal RegionStoreManager::Retrieve(const GRState* St, Loc L, QualType
T) {
assert(!isa<UnknownVal>(L) && "location unknown");
assert(!isa<UndefinedVal>(L) && "location undefined");
- Store S = state->getStore();
- switch (L.getSubKind()) {
- case loc::MemRegionKind: {
- const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion();
- assert(R && "bad region");
+ if (isa<loc::SymbolVal>(L))
+ return UnknownVal();
- if (const TypedRegion* TR = dyn_cast<TypedRegion>(R))
- if (TR->getRValueType(getContext())->isStructureType())
- return RetrieveStruct(S, TR);
+ if (isa<loc::ConcreteInt>(L))
+ return UndefinedVal();
- RegionBindingsTy B(static_cast<const
RegionBindingsTy::TreeTy*>(S));
- RegionBindingsTy::data_type* V = B.lookup(R);
- return V ? *V : UnknownVal();
- }
+ if (isa<loc::FuncVal>(L))
+ return L;
- case loc::SymbolValKind:
- return UnknownVal();
+ const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion();
+ assert(R && "bad region");
- case loc::ConcreteIntKind:
- return UndefinedVal(); // As in BasicStoreManager.
+ if (const TypedRegion* TR = dyn_cast<TypedRegion>(R))
+ if (TR->getRValueType(getContext())->isStructureType())
+ return RetrieveStruct(St, TR);
+
+ RegionBindingsTy B = GetRegionBindings(St->getStore());
+ RegionBindingsTy::data_type* V = B.lookup(R);
- case loc::FuncValKind:
- return L;
+ // Check if the region has a binding.
+ if (V)
+ return *V;
+
+ // Check if the region is in killset.
+ GRStateRef state(St, StateMgr);
+ if (state.contains<RegionKills>(R))
+ return UnknownVal();
- default:
- assert(false && "Invalid Location");
- return L;
- }
+ // The location is not initialized.
+
+ // We treat parameters as symbolic values.
+ if (const VarRegion* VR = dyn_cast<VarRegion>(R))
+ if (isa<ParmVarDecl>(VR->getDecl()))
+ return SVal::MakeSymbolValue(getSymbolManager(), VR,
+ VR->getRValueType(getContext()));
+
+ if (MRMgr.onStack(R) || MRMgr.onHeap(R))
+ return UndefinedVal();
+ else
+ return SVal::MakeSymbolValue(getSymbolManager(), R,
+ cast<TypedRegion>(R)-
>getRValueType(getContext()));
+
+ // FIXME: consider default values for elements and fields.
}
It's obvious that much of the guts of RegionStore has been moved to
this function. Please add some comments within its implementation
saying what it is doing (at a high-level). For example, the pseudo-
code you presented in an earlier email provides a nice executive
summary. From inspection this code looks like it is doing the right
thing, but I wouldn't be surprised if there were some subtle corner
cases. Those can be fixed in a later patch.
-SVal RegionStoreManager::RetrieveStruct(Store store, const
TypedRegion* R) {
+SVal RegionStoreManager::RetrieveStruct(const GRState* St,const
TypedRegion* R){
+
+ Store store = St->getStore();
+ GRStateRef state(St, StateMgr);
+
// FIXME: Verify we want getRValueType instead of getLValueType.
QualType T = R->getRValueType(getContext());
assert(T->isStructureType());
@@ -447,10 +478,21 @@
FieldEnd =
Fields.rend();
Field != FieldEnd; ++Field) {
FieldRegion* FR = MRMgr.getFieldRegion(*Field, R);
- RegionBindingsTy B(static_cast<const
RegionBindingsTy::TreeTy*>(store));
+ RegionBindingsTy B = GetRegionBindings(store);
RegionBindingsTy::data_type* data = B.lookup(FR);
- SVal FieldValue = data ? *data : UnknownVal();
+ SVal FieldValue;
+ if (data)
+ FieldValue = *data;
+ else if (state.contains<RegionKills>(FR))
+ FieldValue = UnknownVal();
+ else {
+ if (MRMgr.onStack(FR) || MRMgr.onHeap(FR))
+ FieldValue = UndefinedVal();
+ else
+ FieldValue = SVal::MakeSymbolValue(getSymbolManager(), FR,
+ FR-
>getRValueType(getContext()));
+ }
Looks good to me.
-Store RegionStoreManager::Bind(Store store, Loc LV, SVal V) {
- if (LV.getSubKind() == loc::SymbolValKind)
- return store;
+const GRState* RegionStoreManager::Bind(const GRState* St, Loc L,
SVal V) {
+ if (isa<loc::SymbolVal>(L))
+ return St;
Please add a comment for this check. It's not obvious to me why
Bind() aborts on this case.
- assert(LV.getSubKind() == loc::MemRegionKind);
-
- const MemRegion* R = cast<loc::MemRegionVal>(LV).getRegion();
-
+ const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion();
assert(R);
Is Bind() always passed a region?
+ // Check if the region is a struct region.
if (const TypedRegion* TR = dyn_cast<TypedRegion>(R))
// FIXME: Verify we want getRValueType().
if (TR->getRValueType(getContext())->isStructureType())
- return BindStruct(store, TR, V);
+ return BindStruct(St, TR, V);
+ Store store = St->getStore();
RegionBindingsTy B = GetRegionBindings(store);
- return V.isUnknown()
- ? RBFactory.Remove(B, R).getRoot()
- : RBFactory.Add(B, R, V).getRoot();
+
+ if (V.isUnknown()) {
+ // Remove the binding.
+ store = RBFactory.Remove(B, R).getRoot();
+
+ // Add the region to the killset.
+ GRStateRef state(St, StateMgr);
+ St = state.add<RegionKills>(R);
+ }
+ else
+ store = RBFactory.Add(B, R, V).getRoot();
+
+ return StateMgr.getState(St, store);
}
It's probably just cleaner to create 'GRStateRef state' at the
beginning of this method and use it everywhere rather just on one code
path.
-Store RegionStoreManager::BindStruct(Store store, const TypedRegion*
R, SVal V){
- // Verify we want getRValueType.
- QualType T = R->getRValueType(getContext());
- assert(T->isStructureType());
+const GRState* RegionStoreManager::BindDecl(const GRState* St,
+ const VarDecl* VD, SVal
InitVal) {
+ // All static variables are treated as symbolic values.
+ if (VD->hasGlobalStorage())
+ return St;
- const RecordType* RT = cast<RecordType>(T.getTypePtr());
- RecordDecl* RD = RT->getDecl();
+ // Process local variables.
- if (!RD->isDefinition()) {
- // This can only occur when a pointer of incomplete struct type
is used as a
- // function argument.
- assert(V.isUnknown());
- return store;
- }
+ QualType T = VD->getType();
+
+ VarRegion* VR = MRMgr.getVarRegion(VD);
+
+ if (Loc::IsLocType(T) || T->isIntegerType())
+ return Bind(St, Loc::MakeVal(VR), InitVal);
- RegionBindingsTy B = GetRegionBindings(store);
+ else if (T->isArrayType())
+ return BindArray(St, VR, InitVal);
- if (isa<UnknownVal>(V))
- return BindStructToVal(store, R, UnknownVal());
+ else if (T->isStructureType())
+ return BindStruct(St, VR, InitVal);
Good.
-
-Store RegionStoreManager::BindCompoundLiteral(Store store,
- const
CompoundLiteralExpr* CL,
- SVal V) {
+// FIXME: this method should be merged into Bind().
+const GRState*
+RegionStoreManager::BindCompoundLiteral(const GRState* St,
+ const CompoundLiteralExpr*
CL, SVal V) {
CompoundLiteralRegion* R = MRMgr.getCompoundLiteralRegion(CL);
- store = Bind(store, loc::MemRegionVal(R), V);
- return store;
+ return Bind(St, loc::MemRegionVal(R), V);
}
Good.
-Store RegionStoreManager::InitializeArray(Store store, const
TypedRegion* R,
- SVal Init) {
+const GRState* RegionStoreManager::BindArray(const GRState* St,
+ const TypedRegion* R,
SVal Init) {
// FIXME: Verify we should use getLValueType or getRValueType.
QualType T = R->getRValueType(getContext());
assert(T->isArrayType());
+ // When we are binding the whole array, it always has default value
0.
+ GRStateRef state(St, StateMgr);
+ // St = state.set<RegionDefaultValue>(R,
NonLoc::MakeVal(getBasicVals(), 0,
+ // false));
+
+ Store store = St->getStore();
+
ConstantArrayType* CAT = cast<ConstantArrayType>(T.getTypePtr());
llvm::APSInt Size(CAT->getSize(), false);
+ llvm::APSInt i = getBasicVals().getZeroWithPtrWidth(false);
- llvm::APSInt i = getBasicVals().getValue(0, Size.getBitWidth(),
- Size.isUnsigned());
-
// Check if the init expr is a StringLiteral.
if (isa<loc::MemRegionVal>(Init)) {
const MemRegion* InitR =
cast<loc::MemRegionVal>(Init).getRegion();
@@ -803,21 +746,21 @@
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.
for (; i < Size; ++i, ++j) {
+ if (j >= len)
+ break;
+
SVal Idx = NonLoc::MakeVal(getBasicVals(), i);
ElementRegion* ER = MRMgr.getElementRegion(Idx, R);
- // 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.
- SVal V = (j < len)
- ? NonLoc::MakeVal(getBasicVals(), str[j], sizeof(char)*8, true)
- : NonLoc::MakeVal(getBasicVals(), 0, sizeof(char)*8, true);
-
- store = Bind(store, loc::MemRegionVal(ER), V);
+ SVal V = NonLoc::MakeVal(getBasicVals(), str[j],
sizeof(char)*8, true);
+ St = Bind(St, loc::MemRegionVal(ER), V);
}
nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
- for (; i < Size; ++i) {
+ for (; i < Size; ++i, ++VI) {
+ // The init list might be shorter than the array decl.
+ if (VI == VE)
+ break;
+
SVal Idx = NonLoc::MakeVal(getBasicVals(), i);
ElementRegion* ER = MRMgr.getElementRegion(Idx, R);
-
- store = Bind(store, loc::MemRegionVal(ER), (VI!=VE) ? *VI :
UndefinedVal());
- // The init list might be shorter than the array decl.
- if (VI != VE) ++VI;
- }
- return store;
-}
This all looks reasonable, at least for an initial patch.
-Store Region
+const GRState*
+RegionStoreManager::BindStruct(const GRState* St, const TypedRegion*
R, SVal V){
// FIXME: Verify that we should use getRValueType or getLValueType.
QualType T = R->getRValueType(getContext());
assert(T->isStructureType());
@@ -906,104 +795,37 @@
RecordDecl* RD = RT->getDecl();
assert(RD->isDefinition());
- nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(Init);
+ nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V);
nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
RecordDecl::field_iterator FI = RD->field_begin(), FE = RD-
>field_end();
- for (; FI != FE; ++FI) {
- QualType FTy = (*FI)->getType();
- FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);
+ for (; FI != FE; ++FI, ++VI) {
- if (Loc::IsLocType(FTy) || FTy->isIntegerType()) {
- if (VI != VE) {
- store = Bind(store, loc::MemRegionVal(FR), *VI);
- ++VI;
- } else
- store = Bind(store, loc::MemRegionVal(FR), UndefinedVal());
- }
- else if (FTy->isArrayType()) {
- if (VI != VE) {
- store = InitializeArray(store, FR, *VI);
- ++VI;
- } else
- store = BindArrayToVal(store, FR, UndefinedVal());
+ // There may be fewer values than fields only when we are
initializing a
+ // struct decl. In this case, mark the region as having default
value.
+ if (VI == VE) {
+ // GRStateRef state(St, StateMgr);
+ //St = state.set<RegionDefaultValue>(R,
NonLoc::MakeVal(getBasicVals(), 0,
+ // false));
+ break;
}
- else if (FTy->isStructureType()) {
- if (VI != VE) {
- store = InitializeStruct(store, FR, *VI);
- ++VI;
- } else
- store = BindStructToVal(store, FR, UndefinedVal());
- }
- }
- return store;
-}
Looks reasonable.
-// Bind all fields of the struct to some value.
-Store RegionStoreManager::BindStructToVal(Store store, const
TypedRegion* BaseR,
- SVal V) {
-
- // FIXME: Verify that we should use getLValueType or getRValueType.
- QualType T = BaseR->getRValueType(getContext());
- assert(T->isStructureType());
+ QualType FTy = (*FI)->getType();
+ FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);
- const RecordType* RT = cast<RecordType>(T.getTypePtr());
- RecordDecl* RD = RT->getDecl();
- assert(RD->isDefinition());
-
- RecordDecl::field_iterator I = RD->field_begin(), E = RD-
>field_end();
-
- for (; I != E; ++I) {
+ if (Loc::IsLocType(FTy) || FTy->isIntegerType())
+ St = Bind(St, Loc::MakeVal(FR), *VI);
- QualType FTy = (*I)->getType();
- FieldRegion* FR = MRMgr.getFieldRegion(*I, BaseR);
-
- if (Loc::IsLocType(FTy) || FTy->isIntegerType()) {
- store = Bind(store, loc::MemRegionVal(FR), V);
+ else if (FTy->isArrayType())
+ St = BindArray(St, FR, *VI);
- } else if (FTy->isArrayType()) {
- store = BindArrayToVal(store, FR, V);
-
- } else if (FTy->isStructureType()) {
- store = BindStructToVal(store, FR, V);
- }
+ else if (FTy->isStructureType())
+ St = BindStruct(St, FR, *VI);
}
- return store;
+ return St;
}
-Store RegionStoreManager::BindStructToSymVal(Store store,
- const TypedRegion*
BaseR) {
-
- // FIXME: Verify that we should use getLValueType or getRValueType
- QualType T = BaseR->getRValueType(getContext());
- assert(T->isStructureType());
-
- const RecordType* RT = cast<RecordType>(T.getTypePtr());
- RecordDecl* RD = RT->getDecl();
- assert(RD->isDefinition());
-
- RecordDecl::field_iterator I = RD->field_begin(), E = RD-
>field_end();
-
- for (; I != E; ++I) {
- QualType FTy = (*I)->getType();
- FieldRegion* FR = MRMgr.getFieldRegion(*I, BaseR);
-
- if (Loc::IsLocType(FTy) || FTy->isIntegerType()) {
- store = Bind(store, loc::MemRegionVal(FR),
- SVal::getSymbolValue(getSymbolManager(), BaseR,
*I, FTy));
- }
- else if (FTy->isArrayType()) {
- store = BindArrayToSymVal(store, FR);
- }
- else if (FTy->isStructureType()) {
- store = BindStructToSymVal(store, FR);
- }
- }
-
- return store;
-}
Looks good.
-
const GRState* RegionStoreManager::AddRegionView(const GRState* St,
const MemRegion*
View,
const MemRegion*
Base) {
Index: lib/Analysis/GRExprEngine.cpp
===================================================================
--- lib/Analysis/GRExprEngine.cpp （版本 61131）
+++ lib/Analysis/GRExprEngine.cpp （工作副本）
@@ -1811,7 +1811,8 @@
for (NodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
const GRState* St = GetState(*I);
unsigned Count = Builder->getCurrentBlockCount();
-
+
+ // Decls without InitExpr are not initialized explicitly.
if (InitEx) {
SVal InitVal = GetSVal(St, InitEx);
QualType T = VD->getType();
@@ -1829,12 +1830,9 @@
}
}
- St = StateMgr.BindDecl(St, VD, &InitVal, Count);
+ St = StateMgr.BindDecl(St, VD, InitVal);
}
- else
- St = StateMgr.BindDecl(St, VD, 0, Count);
-
// Check if 'VD' is a VLA and if so check if has a non-zero size.
QualType T = getContext().getCanonicalType(VD->getType());
if (VariableArrayType* VLA = dyn_cast<VariableArrayType>(T)) {
Looks good.
All in all there are so many changes here that it is a little hard for
me to take it all in, but it looks like a good start. My high level
thoughts are to keep the basic functionality of GRExprEngine, GRState
and BasicStoreManager the same in this patch (modulo some interface
changes). That way nothing breaks, and the main functionality change
is in RegionStore. Once the big changes to RegionStore are in we can
iterate on its implementation.
Great work!
More information about the cfe-dev
mailing list