[cfe-dev] Caching a unified ParentMap in the ASTContext?

[Manuel Klimek]

Patch sent.
Mail:
http://lists.cs.uiuc.edu/pipermail/cfe-commits/Week-of-Mon-20130107/071072.html
Phab: http://llvm-reviews.chandlerc.com/D267

Let's talk about code :)

Cheers,
/Manuel


On Sat, Jan 5, 2013 at 3:17 AM, Jordan Rose <jordan_rose at apple.com> wrote:

>
> On Jan 4, 2013, at 2:04 , Manuel Klimek <klimek at google.com> wrote:
>
> On Thu, Jan 3, 2013 at 6:06 PM, Ted Kremenek <kremenek at apple.com> wrote:
>
>> On Jan 3, 2013, at 7:37 AM, Manuel Klimek <klimek at google.com> wrote:
>>
>> On Wed, Jan 2, 2013 at 8:08 PM, Ted Kremenek <kremenek at apple.com> wrote:
>>
>>> On Jan 2, 2013, at 9:58 AM, Jordan Rose <jordan_rose at apple.com> wrote:
>>>
>>> I'm not so worried about the cost of *building* the map; the analyzer
>>> run tends to dwarf any linear-time operations anyway. I just don't want to
>>> build it for the entire translation unit, since we won't use most of it and
>>> we're already caching the per-function ones. I don't think that's a design
>>> issue, though.
>>>
>>>
>>> Agreed.  It would be great if a "generic" parent map would just build
>>> the parts of the map on demand as necessary.  Then all clients could
>>> benefit from the optimization of only paying for what you use.
>>>
>>
>> The basic problem I see here is a trade-off in "saved time" when only a
>> subset is needed vs. how often we need to run over the whole AST:
>> - as far as I can tell, we need to run over *all* of the AST at least
>> once at the moment at which we need the first parent (or am I missing
>> something?) - we can most certainly only *store* parts of it, but we at
>> least need to iterate over everything
>> - every time we run into an access that needs parent information we did
>> not store, we'll need to re-run over everything (right?)
>>
>> One way I see to mitigate the problem would be the following: have
>> getParent() on the ASTContext take a node and a "AncestorHint" node, which
>> basically tells getParent(), that AncestorHint *should usually* be enough
>> to figure out the request - in the context of the static analyzer that
>> might be the current FunctionDecl (we could also use that to speed up lots
>> of our refactoring cases actually).
>>
>> If the parent cannot be found within the AncestorHint, the whole AST
>> would be visited (or we assert unless the AncestorHint is NULL or something
>> similar).
>>
>> Thoughts?
>> /Manuel
>>
>>
>>
>> Hi Manuel,
>>
>> The AncestorHint approach sounds reasonable to me.  It would capture the
>> workflow of currently clients of ParentMap like the static analyzer fairly
>> well.  Usually we know what function or method we are looking at, and that
>> can bound the scope of the AST walk.
>>
>
> Hi Ted,
>
> one more thing, I'm curious what the exact requirements for the static
> analyzer are here:
> A node can have multiple parents - for example, if I have a template
> function and an instantiation of that template function, some of the
> statements in the function will be reachable both via the template
> declaration and the instantiation - both are important contexts of the
> statement. Does this matter for the static analyzer? Or is the static
> analyzer only interested in the non-instantiation parts of the AST?
>
> One problem I currently have is that I don't know enough about which nodes
> get reused during template instantiation, so I'm not sure yet in whether
> there might be simple solutions to figure out how to resolve those issues...
>
>
> Interesting. The analyzer core uses the parent of an expression to tell
> if/how the value of the expression is going to be used; for that I suppose
> we'd actually want the instantiation. The diagnostics use the parents to
> determine where to attach notes (and arrows for Xcode); in that case we're
> mostly interested in the source locations, which should be the same for
> both.
>
> I would guess we don't handle recursive templates very well if any of the
> leaf nodes are reused; the behavior of ParentMap in that case is always to
> prefer the last visit!
>
> But we're not doing anything special to deal with instantiations vs.
> non-instantiations, so I doubt we'd regress much here whatever you end up
> doing.
>
> Jordan
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20130108/34bb2d14/attachment.html>