[LLVMdev] Static slicer and other useful stuff

[Jiri Slaby]

On 02/14/2012 07:26 AM, Evan Cheng wrote:
> Hi js,
> 
> On Feb 13, 2012, at 8:49 AM, Jiri Slaby <jirislaby at gmail.com> wrote:
> 
>> Hello,
>>
>> we, at the Masaryk University, have developed an interprocedural static
>> slicer with other useful stuff. This includes Andersen's points-to
>> analysis, accurate call-graph, modifies relations.
>>
>> The whole code is available in this repository:
>> https://github.com/jirislaby/LLVMSlicer
>>
>> 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:

* 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