[LLVMdev] alias analysis library

[Dan Gohman]

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