[cfe-dev] Generic abstract interpretation

[Jiří Zárevúcky]

That is not what I mean.

"Abstract interpretation" is a generic framework for expressing static
analyzers, it has nothing to do with the language being analyzed.
In essence, the analysis has its information bound to edges in CFG, and for
each kind of CFG node there is a callback that changes information on one
side of the node according to information on the other side. For example in
variable liveness analysis, you have code that says "the variable is live
before an assignment iff it is live after the assignment and is not
assigned by it, or it is used by the rhs of the assignment". With this, you
compute a fixed point over the entire CFG. The evaluation strategy is
important for performance, but not for correctness, and every analysis
expressed as abstract interpretation is simply a bunch of short visitors
that get called repeatedly by a generic framework until the analysis
stabilizes.

Now to answer my own question, I looked at the liveness analysis in Clang
in particular (LiveVariables.cpp) and it seems to me it implements all the
responsibilities of a generic framework all within itself. As a result,
there is much more code than there need be, and that code is difficult to
understand. Therefore, either I am reading the code wrong, or there is no
generic framework in clang for abstract interpretation-based analyzers, the
existence of which I was asking about.

-- Jiří Zárevúcky


On 9 July 2014 15:59, Jordan Rose <jordan_rose at apple.com> wrote:

> I'm not quite sure what you mean here. If what you're asking is whether
> the static analyzer is a generic virtual machine, then no—it operates on
> Clang CFGs and ASTs, meaning it's "limited" to C, C++, and Objective-C.
> (And in theory OpenCL and CUDA.) The downside of this is that it can't
> handle arbitrary LLVM IR, from other languages or even from C-family
> language constructs that are hard to model. The upside is that it has a
> much stronger understanding of the intent of the user's code, and can do a
> better job presenting issues it finds.
>
> The general design of the analyzer (graph traversal exploring a state
> space, informed by callbacks) could apply to any language, but the current
> implementation is not immediately reusable.
>
> Jordan
>
>
> On Jul 8, 2014, at 16:00 , Jiří Zárevúcky <zarevucky.jiri at gmail.com>
> wrote:
>
> >
> > Hi, I am new here and I am wondering... does the frontend or the static
> analyzer have any support for generic abstract interpretation?
> >
> > I would imagine most of the static analysis done in the frontend is
> abstract interpretation in some form, but I am utterly lost in the code so
> I have no clue how much of it may be generic and how much is just hardcoded
> special cases.
> >
> >
> > -- Jiří Zárevúcky
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20140710/1401b67f/attachment.html>