llvm dev - Oct 2008 - [LLVMdev] alias analysis library

Hi

As part of my master's thesis at ETH Zurich I've been working on a
language-independent library to perform alias analysis. Two of the
design goals were to provide a simple interface (allowing a user with
only basic knowledge of the topic to perform alias analysis) and
extendability (allowing a professional in the field to implement new
and alternative analyses in a simple fashion). By creating the notion
of "function instances" the handling of context-sensitivity has been
completely decoupled, giving the possibility of combining arbitrary
(context-insensitive) analyses with a certain
context-sensitivity-handler.

To test my work I've implemented a basic frontend as an LLVM pass,
translating the given LLVM code to the intermediate representation
used by my library, and providing answers through the normal
AliasAnalysis interface as specified by LLVM. Getting this
frontend-code to a state adequate for production code would require
some work (*), so I'd like to know whether the LLVM group would be
interested in integrating such a pass (and the library) into the
standard framework or as additional module, once it reached a certain
degree.

The advantages for LLVM, as I see it, would be the following:
Implementing new analyses for this library is easier to do than
directly for LLVM, as the intermediate representation is restricted to
8 different instructions (SSA-ish form) and only one type (references)
is supported. This should make it possible to provide the users of
LLVM with a great variety of algorithms with different precision and
runtime to choose from. And as the library may be used by other
projects as well, LLVM could benefit from any effort put into this
library by other projects.

The main disadvantage for LLVM, as I see it, would be introduced by
the fact that it is an abstraction:
a) The translation from LLVM bytecode to the intermediate
representation requires some additional time and
b) the current abstraction does not allow the implementation of
*path*-sensitive algorithms in the library, as the conditions for
branching aren't represented. However, *flow*-sensitive algorithms are
possible.


As mentioned above, I'd like to know whether the LLVM group would be
interested in such a AA-pass based on this library, either as an
additional module, or as standard component for LLVM. If some basic
interest exists I'd provide this list with further informations as
soon as possible. Of course I don't need a definitive answer
immediately, just an indication whether I'm wasting my time would be
great ;-)

Thanks
 Thomas


(*): Handling of certain kinds of inputs is still missing, e.g.
vectors and exceptions

On Tue, 2008-10-07 at 22:31 +0200, Thomas Lenherr wrote:
> Hi
> 
> As part of my master's thesis at ETH Zurich I've been working on a
> language-independent library to perform alias analysis. Two of the
> design goals were to provide a simple interface (allowing a user with
> only basic knowledge of the topic to perform alias analysis) and
> extendability (allowing a professional in the field to implement new
> and alternative analyses in a simple fashion). By creating the notion
> of "function instances" the handling of context-sensitivity has
been
> completely decoupled, giving the possibility of combining arbitrary
> (context-insensitive) analyses with a certain
> context-sensitivity-handler.
> 
> To test my work I've implemented a basic frontend as an LLVM pass,
> translating the given LLVM code to the intermediate representation
> used by my library, and providing answers through the normal
> AliasAnalysis interface as specified by LLVM. Getting this
> frontend-code to a state adequate for production code would require
> some work (*), so I'd like to know whether the LLVM group would be
> interested in integrating such a pass (and the library) into the
> standard framework or as additional module, once it reached a certain
> degree.
I'd be interested.
> 
> The advantages for LLVM, as I see it, would be the following:
> Implementing new analyses for this library is easier to do than
> directly for LLVM, as the intermediate representation is restricted to
> 8 different instructions (SSA-ish form) and only one type (references)
> is supported. This should make it possible to provide the users of
> LLVM with a great variety of algorithms with different precision and
> runtime to choose from. And as the library may be used by other
> projects as well, LLVM could benefit from any effort put into this
> library by other projects.
There is some precedent in LLVM for analysis passes that build up
their own IR of sorts that's tailored to their needs, so this
wouldn't be entirely out of place.
> The main disadvantage for LLVM, as I see it, would be introduced by
> the fact that it is an abstraction:
> a) The translation from LLVM bytecode to the intermediate
> representation requires some additional time and
> b) the current abstraction does not allow the implementation of
> *path*-sensitive algorithms in the library, as the conditions for
> branching aren't represented. However, *flow*-sensitive algorithms are
> possible.
A nice thing about LLVM is it's designed to accomodate multiple
alias-analysis implementations. It sounds like we may not want to
enable your new analysis as the default alias analysis, but it would
still be interesting to have it available as an option.

The main concern I'd have is adding an external dependency, if you
would plan to maintain the source separately. In that case, if you can 
figure out some configure-time way of enabling/disabling use of the
library, it should be fine.

Dan