[cfe-dev] Two pass analysis framework: AST merging approach

[Gábor Horváth via cfe-dev]

On 5 May 2016 at 08:27, Artem Dergachev via cfe-dev <cfe-dev at lists.llvm.org>
wrote:

> > Can you explain what the "two pass analysis" does?
> > Ex: Does it loop through each of the TU second time and
> > “inline” every call from other TUs? In which order are the other
> > TUs loaded? In which order the call sites are processed? Do you
> > repeat until no change? Did you measure coverage in some way?
> > Did you perform path-sensitive checks? (The time of analysis of 4X
> > seems much lower than what I would expect, given that we now
> > explore much deeper paths and the analyzer has exponential
> > running time.)
>

Yes, path sensitive checks were running. I forget to mention: the number of
reports were about 3X. I did not have time to evaluate them yet though.


>
> On first pass we get a bunch of -emit-ast dumps, on second pass we go
> ahead and analyze each translation unit old-style, but whenever we find an
> inter-unit CallEvent during path-sensitive analysis, we import the section
> of the AST dump containing the function body and all dependent sections,
> and inline the call. The inlined call may later trigger more imports if
> there are inter-unit calls we'd end up wanting to model.
>
> Yeah, benchmarking is a bit more difficult than that. I think Alexey has
> some complicated numbers. I guess the slowdown is only-4x on path-sensitive
> checks simply because there are too many drops due to -analyzer-config
> max-nodes= limit. The most practical measurement would probably be to
> increase limits until the number of reports stops growing. It's also
> possible to count number of limit drops, number of exploded nodes
> constructed, number of bug reports with and without unification, we did
> some of this but not all.
>

It is not just the node limit. This solution also maintains a list which
functions were analyzed (during a call from another TU). This implies that
less functions are analyzed as top level functions.


>
> ________
>
> My best idea on reducing AST loads is to relax "typedness" requirements on
> SVal hierarchy. For example, if an inter-unit function references an
> inter-unit static global variable, this variable can probably be
> represented as some kind of "untyped VarRegion" (let's call this class
> "XTUVarRegion", and inherit it from SubRegion directly, rather than from
> TypedValueRegion), and then its type (which may be a complicated class or
> template-instantiation declaration) doesn't need to be imported. The
> XTUVarRegion should still be uniquely determined by the variable - we need
> to know that two different functions imported from that translation unit
> refer to the same variable. Not sure - maybe some MemSpace magic may be
> employed to control invalidation, maybe we could use separate memory spaces
> for different translation units.


I do not like the idea of ignoring type information. First it would be
worth to measure what portion of the ASTs are actually type related nodes
and not function bodies.


>
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at lists.llvm.org
> 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/20160505/aeaa7344/attachment.html>