Caching a unified ParentMap in the ASTContext?

Clang Frontend
1

Hi,

after some initial probing on IRC it seems like we might want a unified parent map (lazily) cached in the ASTContext.

** Context **

For the ASTMatchers we have come up with a 2nd implementation of a ParentMap in clang [1], which has slightly different requirements from the first one [2].

The lifetime of the ASTMatcher’s map is currently bound to the lifetime of the MatchFinder - the map is lazily created, if we have any matchers that need it, and re-used for all subsequent matches.

Recently we added support to match on arbitrary nodes, which has led to a pattern where one uses the ASTMatchers to find nodes to refactor, and then uses the match-on-node functionality to figure out what’s going on around that node.

The problem is that currently we don’t have a way to re-use the ParentMap that was already built between those calls, leading to an N^2 algorithm in the number of AST nodes.

When thinking about where this information would fit best, we thought it’s strongly coupled to the ASTContext, so before running off and creating an ASTMatchContext that contains an ASTContext and a ParentMap, I thought I’d through out the idea of using a unified ParentMap in the ASTContext.

** Proposal **

The proposal would be to add methods to the ASTContext that allow querying the parents of a node.

Knowing that this might not at all be what we want, I’m proposing a straw-man:

/// \brief Returns an iterator to the parents of the given node.
///
/// Note that this will lazily compute the parents of all nodes
/// and store them for later retrieval. Thus, the first call is O(n)
/// in the number of AST nodes.
///
/// ‘NodeT’ can be one of Decl, Stmt, Type, TypeLoc,
/// NestedNameSpecifier or NestedNameSpecifierLoc.
template
ParentIterator ASTContext::parents_begin(const NodeT &Node);

template
ParentIterator ASTContext::parents_end(const NodeT &Node);

An alternative would be to use DynTypedNode in the interface instead of templating the method and hiding it, but I’m not sure how much exposure to that we want in general.

I’m also fine with putting up a solution just for the matchers, but wanted to make sure to pursue a more generally useful solution if there’s interest…

Thoughts?
/Manuel

[1] http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/ASTMatchers/ASTMatchFinder.cpp?view=markup
[2] http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/AST/ParentMap.h?view=markup

2

I’m still pretty new to this and haven’t plumbed the depths of the matcher internals yet but how can an AST node have multiple parents? Also, when matching is underway and the AST is being recursively visited couldn’t we piggy-back this process to get the parent map for free or is storage of such a map something we want to avoid if possible?

3

I’m still pretty new to this and haven’t plumbed the depths of the
matcher internals yet but how can an AST node have multiple parents? Also,
when matching is

For example Stmt nodes can have parents that are generated during template
specializations...

underway and the AST is being recursively visited couldn’t we piggy-back
this process to get the parent map for free or is storage of such a map
something we want to avoid if possible?

Yep, we want to avoid it if possible...

Cheers,
/Manuel

4

Could we still piggy-back the matching process if we provided a flag to the constructor of MatchFinder? Then we’d incur storage only when we wanted and save that extra O(N) overhead.

5

(+Olaf Krzikalla, a known external user of the classic ParentMap)

The analyzer seems to be the primary user of the “classic” ParentMap; it’s also scattered over the rewriters, but I’m not sure it’s ever actually used there. All of the uses of our ParentMap seem like they could easily be implemented on top of ASTMatcher’s DenseMap implementation, though I’m a little concerned about (a) the ability to update parents, which Olaf uses, and (b) the careful handling of PseudoObjectExprs and OpaqueValueExprs used for proper source locations in the analyzer.

I also don’t like the idea that building a ParentMap traverses the entire AST. That includes everything pulled in in every header file, when usually the analyzer only needs to deal with a single function at a time. I’m not sure what to say about this, though; making ParentMaps specific to Decls seems problematic in a different way: you can’t match across everything as easily. And if you allow both per-function and global parent maps, you’re doing redundant work.

Hm. I’m not sure what I think yet, but I’m leaning towards using your lazily constructed global map on ASTContext and yet still keeping the per-function maps on AnalysisDeclContext. Unifying the two types is fine, though.

Jordan

6

(+Olaf Krzikalla, a known external user of the classic ParentMap)

The analyzer seems to be the primary user of the "classic" ParentMap; it's
also scattered over the rewriters, but I'm not sure it's ever actually used
there. All of the uses of our ParentMap seem like they could easily be
implemented on top of ASTMatcher's DenseMap implementation, though I'm a
little concerned about (a) the ability to *update* parents, which Olaf
uses, and (b) the careful handling of PseudoObjectExprs and
OpaqueValueExprs used for proper source locations in the analyzer.

I also don't like the idea that building a ParentMap traverses the *entire
* AST. That includes everything pulled in in every header file, when
usually the analyzer only needs to deal with a single function at a time.
I'm not sure what to say about this, though; making ParentMaps specific to
Decls seems problematic in a different way: you can't match across *
everything* as easily. And if you allow both per-function and global
parent maps, you're doing redundant work.

Hm. I'm not sure what I think yet, but I'm leaning towards using your
lazily constructed global map on ASTContext and yet still keeping the
per-function maps on AnalysisDeclContext. Unifying the two types is fine,
though.

One thing I'm concerned about is how performance critical the parent map
for the analyzer is - we'll need to expand ours to work for at least all
types of nodes that have pointer identity (including TypeLoc and
NestedNameSpecifierLoc, as those are crucial for refactorings), while the
analyzer (currently) seems to only need statements.

Before trying to come up with a patch I'd be interested whether you expect
the analyzer to need parents for different node types anyway, and whether
you think the additional performance hit of building a more generic parent
map would be prohibitive.

Thanks!
/Manuel

7

(+Olaf Krzikalla, a known external user of the classic ParentMap)

The analyzer seems to be the primary user of the "classic" ParentMap;
it's also scattered over the rewriters, but I'm not sure it's ever actually
used there. All of the uses of our ParentMap seem like they could easily be
implemented on top of ASTMatcher's DenseMap implementation, though I'm a
little concerned about (a) the ability to *update* parents, which Olaf
uses, and (b) the careful handling of PseudoObjectExprs and
OpaqueValueExprs used for proper source locations in the analyzer.

I also don't like the idea that building a ParentMap traverses the *
entire* AST. That includes everything pulled in in every header file,
when usually the analyzer only needs to deal with a single function at a
time. I'm not sure what to say about this, though; making ParentMaps
specific to Decls seems problematic in a different way: you can't match
across *everything* as easily. And if you allow both per-function and
global parent maps, you're doing redundant work.

Hm. I'm not sure what I think yet, but I'm leaning towards using your
lazily constructed global map on ASTContext and yet still keeping the
per-function maps on AnalysisDeclContext. Unifying the two types is fine,
though.

One thing I'm concerned about is how performance critical the parent map
for the analyzer is - we'll need to expand ours to work for at least all
types of nodes that have pointer identity (including TypeLoc and
NestedNameSpecifierLoc, as those are crucial for refactorings), while the
analyzer (currently) seems to only need statements.

Before trying to come up with a patch I'd be interested whether you expect
the analyzer to need parents for different node types anyway, and whether
you think the additional performance hit of building a more generic parent
map would be prohibitive.

Ping :slight_smile: Or should I just come up with a patch so we have something concrete
to look at?

Cheers,
/Manuel

8

Whoops, sorry I missed this. Unfortunately, ParentMap is indeed in the analyzer’s hot path, which is probably already not a great thing. I’m not sure how much making it more generic will cost, though. The way we use it, every statement’s parent should be another statement or NULL; that would change to being another statement, a CXXInitializer, or the enclosing function Decl. Slightly more expensive to check the “expression is consumed” during the analyzer run; we’re okay with taking the hit during the diagnostics emission for finding good path note locations.

I can think of uses outside of just statement->statement mappings, but obviously we’ve gotten this far with only that.

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.

So, okay, let’s see a patch. :slight_smile:
Jordan

9

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.

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.

10

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

11

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.

Ted

12

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...

Cheers,
/Manuel

13

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

14

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 :slight_smile:

Cheers,
/Manuel