[cfe-dev] Analyzer: Extract region-walking behavior from CallAndMessageChecker

[Jordy Rose]

On Wed, 23 Jun 2010 16:30:29 -0700, Ted Kremenek <kremenek at apple.com>
wrote:
> On Jun 23, 2010, at 12:05 AM, Jordy Rose wrote:
> 
>> CallAndMessageChecker currently has a simple check to see if any of the
>> members of a pass-by-value struct are uninitialized. It handles nested
>> structs, but not structs containing arrays.
>> 
>> I propose to extract this region-walking behavior out into a new class,
>> RegionWalker. This would then be the basis for the current
pass-by-value
>> check and a possible new one (see below). My implementation of
>> RegionWalker
>> is loosely modeled after RecursiveASTVisitor (see attached patch), and
>> supports both structs and arrays, and both nested.
> 
> Hi Jordy,
> 
> I think in principle the addition of RegionWalker is a nice refactoring,
> but I'm really concerned about the following:
> 
> +    const ElementRegion *ER = MemMgr.getElementRegion(EleTy, IndexVal,
R,
> Ctx);
> 
> This call means that we will create a new ElementRegion for accessing
> every single element of an array.  This is really expensive.  Not only
will
> this be really slow for large constant-sized arrays, it will cause a
bunch
> of ElementRegion objects to get generated that will stay around for the
> entire lifetime of the GRExprEngine object.
> 
> As is, I don't think this can go in.

I was concerned about this too, but couldn't think of another way to
actually visit every scalar element of a complicated nesting of structs and
arrays. On the face of it, this could be solved with stack-based
ElementRegion and FieldRegion objects...apart from being the only such case
of stack-based regions, and a slightly distasteful idea. *grin*

But due to your other objections, perhaps it is not a useful finding.
Perhaps if a pass-by-value struct had /no/ initialized members, it'd be
worth warning...but again, there, the effort to actually walk all the
subregions might not be worth it.


> My high-level question is what is the purpose of this API?  Is to
iterate
> over "direct" bindings, or all the values in memory?  The StoreManager
does
> support an API to iterate over bindings, but the behavior will be highly
> dependent on the implementation of the StoreManager.  We really need to
> design these APIs with algorithmic efficiency in mind. If we need to add
> more high-level APIs to StoreManager to make the kind of queries we want
to
> do more efficient than I prefer we do that.  RegionWalker right now
defeats
> all the laziness of RegionStore by instantiation regions on-the-fly. 
This
> is going to be a huge performance killer.

Huh. I had originally thought that RegionStore's subregion map was flat,
that /any/ subregion showed up under the main one. Which wouldn't allow for
the nice "field chain" in CallAndMessageChecker. But this isn't the case.

So perhaps I could rewrite RegionWalker to make use of this, though your
points make it seem much less useful than I had thought.

The original motivation was to avoid duplicating code between
CallAndMessageChecker, and this new const buffer checker idea. None of the
other checkers yet have the same behavior. I'm feeling cautious about the
new check as well -- there /are/ cases where a const pointer is never
dereferenced, and so it doesn't matter if its pointee is completely
uninitialized.

Perhaps this should be put on hold in favor of work with a clearer payoff.
Thanks for pointing out the problems with this.