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

[Manuel Klimek]

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


>
> A reasonable approach to stage things would be to first move the current
> ParentMap to libStaticAnalyzerCore, and have the analyzer use that.  Manuel
> can then feel free to design a more generic data structure, and we can then
> evaluate whether or not to switch the analyzer over to using that.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20130103/c0e1357d/attachment.html>