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

[Zhongxing Xu]

On Tue, Jan 13, 2009 at 7:23 AM, Ted Kremenek <kremenek at apple.com> wrote:

> This looks great!  Two comments:
> +const GRState* RegionStoreManager::KillStruct(const GRState* St,
> +                                              const TypedRegion* R){
> +  GRStateRef state(St, StateMgr);
> +
> +  // Kill the struct region because it is assigned "unknown".
> +  St = state.add<RegionKills>(R);
> +
> +  // Set the default value of the struct region to "unknown".
> +  St = state.set<RegionDefaultValue>(R, UnknownVal());
> +
> +  // Remove the struct region from the RegionViews. It could only be a
> "view" of
> +  // its super region.
> +  St = RemoveRegionView(St, R, R->getSuperRegion());
>
> Hmm.  I'm looking at this again, I guess removing the view of 'R' from its
> super region doesn't make sense.  It's just the values bound to 'R' that
> change, not the fact that 'R' is a view of its super region.
>

Yes, that was my initial thought. :-)


>
> +
> +  Store store = St->getStore();
> +  RegionBindingsTy B = GetRegionBindings(store);
> +
> +  // 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))
> +        store = Remove(store, Loc::MakeVal(sr));
>
> I am wondering if we also need to remove bindings for views of 'sr'.  That
> is, iterate over the views of 'sr' and remove any bindings from state.  What
> do you think?  I guess it depends on how we decide to bind values in weird
> cases where people abuse the type system.
>

I am afraid the cost would be too high, and the logic be too complex for an
initial implementation. After all we are doing an approximate simulation,
not an exhaustive one. I suggest we leave a FIXME here and fix it when we
see a real bug caused by this simplification.


>
> +  }
> +
> +  return StateMgr.MakeStateWithStore(St, store);
> +}
> +
>
>
>
> On Jan 10, 2009, at 3:12 AM, Zhongxing Xu wrote:
>
>
>
> On Sat, Jan 10, 2009 at 3:46 PM, Ted Kremenek <kremenek at apple.com> wrote:
>
>> On Jan 8, 2009, at 5:36 PM, Zhongxing Xu wrote:
>>
>>  Index: lib/Analysis/RegionStore.cpp
>>> ===================================================================
>>> --- lib/Analysis/RegionStore.cpp        （版本 61900）
>>>
>>>
>>> +  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.
>>>
>>
>> Great!  We should add a comment to that test case the says what part of
>> the analyzer/region store is getting tested.
>
>
> Done.
>
>
>>
>>
>>  +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.
>>>
>>
>> I believe I might be confused about some basic concepts.  Here is how I
>> interpreted things.
>>
>> The "killset" is part of the state, and represents those regions whose
>> values have been changed (via direct assignment) after the entry to the
>> analyzed function.  This way we don't need to explicitly bind initial values
>> to regions and instead lazily infer their bindings.
>>
>> According to comments in RegionStore, the "default value" map
>> (RegionDefaultValue) is used to track "what regions have a default value of
>> 0 if they have no bound value and have not been killed."
>>
>> From the patch I see 'KillStruct' being used in the following way:
>>
>> 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());
>>
>>  RecordType* RT = cast<RecordType>(T.getTypePtr());
>>  RecordDecl* RD = RT->getDecl();
>>  assert(RD->isDefinition());
>>
>>  if (V.isUnknown())
>>    return KillStruct(St, R)
>>  ...
>>
>> Two things occur to me:
>>
>> (1) We should always be adding any region directly assigned to the
>> killset.  Doesn't that include structs?
>
>
> Yes. I thought we would never query a struct region's binding like we never
> do it to an array region. But later I realized I was wrong. I've done this
> step in the new patch.
>
> And, I think we should add a region to the killset *only* when it is
> assigned "unknown" directly. Because if it is assigned other value, we would
> have its binding in the region bindings. It is redundant to add it to the
> killset.
>
>
>>
>>
>> (2) After assigning the value "unknown" to the struct, the values of its
>> fields should not be 0 (as indicated by the comments for
>> RegionDefaultValue).  That doesn't make sense to me.  Shouldn't they just be
>> "unknown"?
>>
>> In other words, regardless of whether V.isUnknown() == true (in the above
>> code snippet) we should always do (1) and then just remove any bindings to
>> struct and it's fields.  Adding entries to RegionDefaultValue (i.e., (2))
>> doesn't make sense to me, so I think I'm just missing something and don't
>> really understand the overall design.
>
>
> RegionDefaultValue was originally designed to include regions which have
> default values of 0. But later I find we could have default values other
> than 0. This is just a case that we need it, since we would query the
> bindings of the subregions of the struct region that is killed (assigned
> "unknown"). If we don't set the struct region's default value, we would have
> to add all subregions of the struct region to the killset. Now that we set
> the struct region's default value, we can just remove the subregions of the
> struct region from RegionBindings.
>
>
>>
>>
>>  Ah, I forgot that point. Is this also known as persistent data structure?
>>>
>>
>> Yes it is.  The term "purely functional data structures" comes from the
>> functional programming mindset.  Okasaki has an excellent book on that
>> topic:
>>
>>
>> http://books.google.com/books?id=SxPzSTcTalAC&dq=purely+functional+data+structures&printsec=frontcover&source=bn&hl=en&sa=X&oi=book_result&resnum=4&ct=result
>
>
> Thanks.
>
>
>>
>> <http://books.google.com/books?id=SxPzSTcTalAC&dq=purely+functional+data+structures&printsec=frontcover&source=bn&hl=en&sa=X&oi=book_result&resnum=4&ct=result>
>>
>>
>>> 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.
>>>
>>
>> "Views" are just a specific type of subregions (whose bindings are all
>> getting nuked by KillStruct).  The GDM entry "RegionViews" is just a
>> back-mapping from a region to its subregions.  If we remove all of those
>> bindings why do we need to keep that backmapping around since none of them
>> bind to any value?  Removing stale data from the state allows better
>> caching.
>
>
> Yes, I've done this in the new patch.
>
>
>>
>>
>> As a meta comment, it would probably be good to add comments to the top of
>> RegionStore that documents the overall design. More specifically, we should
>> mention how the different GDM pieces are used, what's the overall
>> abstraction of how regions bind to values, how we model "views" of regions
>> (i.e., what they are and what purpose they serve) and so forth.  I feel that
>> some of my confusion is stemming from not completely understanding the
>> design as well as I thought I did.
>
>
> Yes. I should have done that. But I didn't do it because I feel some
> designs are not fixed.
> <killstruct2.patch>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20090113/bb73dc99/attachment.html>