[cfe-dev] [Patch] add KillStruct() to RegionStore

[Zhongxing Xu]

On Fri, Jan 9, 2009 at 9:02 AM, Ted Kremenek <kremenek at apple.com> wrote:

>
> On Jan 8, 2009, at 9:21 PM, Zhongxing Xu wrote:
>
>  This patch adds KillStruct() to region store. When we assign UnknownVal to
>> a struct, we set the region's default value to Unknown, and remove bindings
>> for all subregions of the struct region.
>>
>
> Hi Zhongxing,
>
> This is nice.  Could you include a test case that would trigger KillStruct?
>  More comments below:
>
>
> Index: lib/Analysis/RegionStore.cpp
> ===================================================================
> --- lib/Analysis/RegionStore.cpp        （版本 61900）
> +++ lib/Analysis/RegionStore.cpp        （工作副本）
> @@ -234,6 +234,9 @@
>
>   const GRState* BindStruct(const GRState* St, const TypedRegion* R, SVal
> V);
>
> +  /// KillStruct - Set the entire struct to unknown.
> +  const GRState* KillStruct(const GRState* St, const TypedRegion* R);
> +
>   // Utility methods.
>   BasicValueFactory& getBasicVals() { return StateMgr.getBasicVals(); }
>   ASTContext& getContext() { return StateMgr.getContext(); }
> @@ -910,6 +913,9 @@
>   RecordDecl* RD = RT->getDecl();
>   assert(RD->isDefinition());
>
> +  if (V.isUnknown())
> +    return KillStruct(St, R);
> +
>
> When precisely can V.isUnknown() be true when the value is a struct?  (test
> case please).


We already have that test case. It is the f5() in
test/Analysis/array-struct.c.


>
>
>
> +const GRState* RegionStoreManager::KillStruct(const GRState* St,
> +                                              const TypedRegion* R){
> +  GRStateRef state(St, StateMgr);
> +  // Set the default value of the struct region to UnknownVal.
> +  St = state.set<RegionDefaultValue>(R, UnknownVal());
>
> Interesting.  Do we need the killset anymore, or are we going to model
> "killed values" in this way?


I think we still need killset. The regions in killset are ones we query its
binding directly. The regions in RegionDefaultValue are ones whose
subregions we query bindings for. I haven't had a way to combine them.


>
>
> +
> +  Store store = St->getStore();
> +  RegionBindingsTy B = GetRegionBindings(store);
> +
> +  std::vector<const MemRegion*> ToBeKilled;
>
> In general, please use a llvm::SmallVector<> so that we can optimize for
> the case when the number of items fits on the stack.  Using std::vector
> forces us to malloc() memory every time this method is called (which is
> slow).  My comment below, however, illustrates why we don't need to use
> either in this case.


OK.


>
>
> +
> +  // Remove all bindings for the subregions of the struct.
> +  for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I)
> {
> +    const MemRegion* r = I.getKey();
> +    if (const SubRegion* sr = dyn_cast<SubRegion>(r))
> +      if (sr->isSubRegionOf(R))
> +        ToBeKilled.push_back(R);
>
> I think the region to be killed is 'r', not 'R' (since we just bound a
> value to it up above).


Yes, my mistake (typo).


>
>
> +  }
> +
> +  for (std::vector<const MemRegion*>::iterator I = ToBeKilled.begin(),
> +         E = ToBeKilled.end(); I != E; ++I)
> +    store = Remove(store, Loc::MakeVal(*I));
>
> You don't need to build a vector of killed regions and then iterate through
> vector because 'B' is a purely functional data structure.  That is, removing
> entries from store just creates a new store, and 'B' will continue have the
> same values and the iterator won't be invalidated.  The following will do
> just fine:
>
>  for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
>    const MemRegion* r = I.getKey();
>    if (const SubRegion* sr = dyn_cast<SubRegion>(r))
>      if (sr->isSubRegionOf(R))
>        store = Remove(store, Loc::MakeVal(r));
>
> +  return StateMgr.MakeStateWithStore(St, store);


Ah, I forgot that point. Is this also known as persistent data structure?


>
>
> Do we also need to remove region views for the regions that are killed, or
> should we dispense with that GDM entry entirely?


I think region views are orthogonal to this one. Region views are used to
cast region back and forth between typed and untyped ones. Here we only
handle the region bindings.


>
> +}
> +
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20090109/41ef4c05/attachment.html>