llvm dev - Feb 2012 - [LLVMdev] Static slicer and other useful stuff

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?

thanks,
-- 
js

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.

Thanks,

Evan
> 
> thanks,
> -- 
> js
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

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