[cfe-dev] Generic abstract interpretation

[Jordan Rose]

Ah, thanks for the clarification. You are correct; the infrastructure in LiveVariables, CFG, and CoreEngine is not really generic enough at the moment to be used as the basis of another analysis engine, and ExprEngine, RegionStore, and SVal are very intricately related to the C family of languages.

Patches to make parts of the analyzer more general would probably be accepted as long as they didn't regress on performance.

Jordan


On Jul 9, 2014, at 23:45 , Jiří Zárevúcky <zarevucky.jiri at gmail.com> wrote:

> 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/ca3bc52c/attachment.html>