[cfe-dev] Proposed: change tracking for RegionStore

[Jordy Rose]

On Fri, 30 Jul 2010 11:43:51 -0700, Ted Kremenek <kremenek at apple.com>
wrote:
> Hi Jordy,
> 
> I'm really concerned about the potential scalability cost this will
impugn
> on RegionStore.  Adding change markers will cause the store to record
> information that is highly specific to a given path.  In this case,
stores
> would retain memory of the previous store, which transforms them from
being
> memoryless (aside from LazyCompoundVals) to retaining a bunch of extra
> state that is specific to a given path.  This can cause states not to
merge
> when they are otherwise identical, which could possibly have huge
> algorithmic implications with how well the analyzer scales, as far fewer
> paths will get merged.

This is true; I hadn't thought of that. Of course, it's only a problem
when the checkers request that information, but it could be a big deal for
a large function (or function net with IPA) dealing with lots of C strings.


> I think there is a higher-order API problem here as well.  The internal
> model that a StoreManager uses for managing memory bindings might not be
> the same as a Checker's view of memory.  Checkers reason about memory
using
> MemoryRegions, but a store could model them using MemRegions+offsets,
etc. 
> Checkers wishing to know about changes to memory would want to know
about
> those changes in terms of how they reason about memory, not how the
> StoreManager reasons about them.

I don't think that's true. If I'm watching a[0][4] of an int[][], and it
get casted to an int[] and the fourth element changes, I still want to
know.


> In your opinion, why is the callback idea not so hot?

It's mainly an API problem as well. A StoreManager may do multiple Add()
or Remove() calls as part of a single action, and between those actions the
store isn't exactly in a reasonable state. For example, the old code for
initializing an array with a string would copy each element of the string
into the array. All that happens here is that change markers get
redundantly cleared, but with callbacks the observer might be able to see
the store with undefined values, or whatever.

(I haven't looked through RegionStore to see if that's actually true.)

Moving the callback up to Bind or Invalidate might work, but then the
stores would have to keep track of every region touched during the call --
annoying, but not impossible. This could still show up during a larger
operation, since the StoreManager doesn't know who's modifying the store.
(It could be part of modeling a function's behavior, for example.)

If we can work out the right API for that, I'd be happy to switch over.
First pass: any call that returns a new Store will call

void RegionWatcher::RegionChanged(Store NewStore, const MemRegion *MR)

for each region, and it's up to the RegionWatcher to traverse
superclasses. This would probably be using the logical view of regions
rather than the internal view, which I'm still not sure is better.