[LLVMdev] alias analysis library

[Thomas Lenherr]

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