[LLVMdev] Static slicer and other useful stuff

[Chris Lattner]

On Feb 14, 2012, at 9:32 AM, Jiri Slaby wrote:
>>> The question I would like to ask is, would you accept this library into
>>> the core LLVM if we send patches or is it too off for LLVM's purposes?
>>> If the latter is the case, would it be possible to create a page at llvm
>>> dot org with stuff like this?
>> 
>> Before we can discuss this, please first provide a more complicate description of your work and its applications.
> 
> The package contains several parts:

Hi Jiri,

This is definitely interesting functionality.  I'd start by proposing specific pieces (e.g. Andersen's) instead of the whole thing at once.  The most important thing is that the code be up to the quality standards of the project.  This means that a) it works, b) its documented well, c) has testcases, d) has an active maintainer, etc.  Also, LLVM has callgraph, mod/ref and alias interfaces, so your work should tie into/extend the appropriate existing APIs.

I'll note that we have had some of this functionality in-tree before and it got removed, because it wasn't maintained and was buggy.

-Chris


> 
> * Andersen's points-to analysis -- precise, fast analysis to say at
> which objects a pointer can point to. It's an over-approximation, so it
> doesn't have false-negatives. But, as such, may have false positives. We
> have also implemented Steensgaard's analysis, however it is not a part
> of this suite. It it slower and less precise in most cases.
> 
> * modifies analysis -- relation of what objects can be modified by each
> of LLVM statements. It leverages the points-to analysis above.
> 
> * callgraph -- again, an over-approximation. It contains everything what
> can be possibly called from a particular function. Including indirect
> calls; that's one of reasons why point's to analysis is used.  It
> computes a transitive closure, but one can ask only for immediate calls...
> 
> * static slicer -- intra-procedural static slicer [1] for LLVM. You
> define what variables at which point you are interested and the rest
> which doesn't change the variables is just deleted.
> 
> * inter-procedural static slicer -- extension to the former, it
> considers function calls and transfers parameters between functions. The
> same as the previous, it computes fix-point.
> 
> All this has been tested on the Linux Kernel and works for our purposes
> of kernel bug-finding.
> 
> [1] as defined by Weiser. Should I elaborate or is it widely known?
> 
> Are you interested in details of any of those?
> 
> thanks,
> -- 
> js
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev