[cfe-dev] Possible bug in check::RegionChanges

[Anna Zaks via cfe-dev]

Thanks for the investigations everyone!

Here is some history that I could dig up.

We used to have wantsRegionChangeUpdate and checkRegionChanges callbacks that were used as a pair. They were called on any change in the regions. Most checkers need to know when a symbol escapes since the information they store about it is no longer valid. I've introduced checkPointerEscape to make it easier for checkers to register for that event.

Looks like I  have not converted all checkers to use the new API. The CStringChecker and RetainCountChecker still use old callbacks. Here is an exchange discussing that. 

A: "I’ve converted Malloc checker to use the new callback. I'll convert the SimpleStreamChecker as well. From what I recall, the RetainRelease checker does not handle escape through struct fields and this is why it cannot be immediately converted. (I did not look into it into too much detail lately.)"

J: "You’re right that RetainReleaseChecker also considers binding to struct fields to be an escape (actually, anything but VarRegions). I think it still makes sense to use checkBind and checkPointerEscape rather than checkBind, evalAssume, and checkRegionChanges, but it's up to you."

A: "Did not think about it, but if partial substitution is possible, I'll definitely do that! Cannot wait to remove all that code."

I might have gotten busy with other stuff and did not finish the conversion after all.

> On Sep 20, 2016, at 8:53 AM, Artem Dergachev via cfe-dev <cfe-dev at lists.llvm.org> wrote:
> 
> Aha, so i was wondering what's so expensive about computing the lists of changed regions if they need to be computed for pointer escape anyway. That explains: when the doc was written, there used to be no pointer escape callback at all.
> 
> From now, we may:
> 
> (1) Remove the callback completely and lose nothing.

This would definitely simplify the checker API.

> 
> (2) Try to gain performance by fixing this callback.

I have no history on how important of a performance improvement the extra call back was. There is a chance that it was a premature optimization and this was just how the code was written when we had only one checker (the retain count) and it was interleaved with the engine code.

> 
> (3) Try to gain even more performance by adding wantsPointerEscapeUpdate() callback.

Found this comment from Jordan on my patch that removes the wantsRegionChangeUpdate:

-  if (Eng && Eng->wantsRegionChangeUpdate(this)) {
+  if (Eng) {

J: *sigh* If we are running this all the time, we should eventually consider removing wantsRegionChangeUpdate; conversely, we could add a similar thing for symbolEscape, or combine the two. (The idea is that we don't need all this extra info if no checkers are tracking any regions or symbols at the moment.)

> 
> Because performance is good for us, it'd probably be great if someone (me(?)) tries to measure the actual performance impact of approaches (1)-(3).
> 
> That said, from reading the code i'm still not convinced that there's much performance gain. Lists of changed regions are filled automatically alongside with traversing the store, does anybody know what's the hard part here anyway? Or was it a premature optimization from the very beginning?
> 
> On 9/20/16 3:00 AM, Devin Coughlin via cfe-dev wrote:
>> 
>>> On Sep 19, 2016, at 10:33 AM, Krzysztof Wiśniewski via cfe-dev <cfe-dev at lists.llvm.org <mailto:cfe-dev at lists.llvm.org>> wrote:
>>> 
>>> Hello,
>>> 
>>> I've been working on new checker that registers for region change update. Together with Artem Dergachev, we noticed that the function
>>> /wantsRegionChangeUpdate /never seems to be called. The heavy work necessary to fill data structures for /checkRegionChanges /is being done regardless of it in /ProgramState::invalidateRegionsImpl./ The documentation for /checkRegionChanges/ says the following:
>>> "Note that this callback will not be invoked unless wantsRegionChangeUpdate returns true"
>>> and for /wantsRegionChangeUpdate:/
>>> "Since it is not necessarily cheap to compute which regions are being changed, this allows the analyzer core to skip the more expensive /checkRegionChanges/ when no checkers are tracking any state." /
>>> /
>>> 
>>> My question is whether someone can confirm that this is indeed an invalid behavior? For me it looks like it used to work differently and at some point someone changed the logic rendering /wantsRegionChangeUpdate /useless.
>> 
>> Interesting. It looks like Anna removed the call in to wantsRegionChangeUpdate() in r170625 when adding the checkPointerEscape callback. It also looks to me like the code path in ProgramState::invalidateRegionsImpl that doesn’t call processRegionChanges() may be completely dead.
>> 
>>> If this indeed is a bug, I suggest we might wish to consult /CheckerManager / in /ProgramState::invalidateRegionsImpl/ //whether there is some one checker registered for an update and only then prepare the input data in order to improve performance.
>> 
>> I think we would still need to call invalidateRegions() on the store manager to actually invalidate the transitively reachable regions, so any savings would be in not filling in the ‘out’ parameters TopLevelInvalidated and Invalidated. I’m not sure skipping this will actually result in any significant performance gains. You could try it and see — but I wonder if the better thing to do here might be to remove the wantsRegionChangeUpdate callback from the checker API.
>> 

It seems we should just remove the callback and the dead code. Maybe we should also set up a performance bot?

Krzysztof,

Do you need to use processRegionChanges or is checkPointerEscape enough for you?

>> Devin
>> 
>> 
>> _______________________________________________
>> cfe-dev mailing list
>> cfe-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
> 
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at lists.llvm.org <mailto:cfe-dev at lists.llvm.org>
> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev <http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20160923/ab8a6254/attachment.html>