[LLVMdev] Google Summer of Code Idea

[Richard Warburton]

This email is written on the premise that LLVM will be involved in
GSOC again this year.  I noted that the wiki's open projects page [0]
has several possible projects, that seem suitable for a summer of code
project.  I am writing this email to this list with the hope of
getting some feedback on specifics for a GSOC application, and also
wondering if any potential mentors are interested in these ideas.

The Idea:

I would be looking to implement a context-sensitive alias analysis.
Whilst I accept that this isn't the most efficient category of alias
analysis, I think the implementation of such an analysis, that trades
off computational efficiency for a more precise computation of
aliasing would be a beneficial addition to the LLVM project.  In terms
of which algorithm to actually implement, I am considering
implementing a BDD based algorithm, possible candidate include:

Whaley + Lam [2] which simply clones points on the call-graph to
generate different contexts and then performs a context insensitive
analysis.  This uses BDDs to reduce memory consumption.
Zhu [3] Which utilises a BDD base approach for a custom context
sensitive, flow insenstitive algorithm,

Were I to use a BDD based approach, I would undoubtedly rely on an
existing implementation, for example buddy[4], rather than
implementing my own. The opinions of any experienced LLVM hackers
would be helpful on algorithm choice.  I am reasonably flexible about
choosing a different .  At the moment I am personally undecided.  I am
interested to hear any feedback on these ideas, specifically, but in
no particular order, with regards the following points:

1. Is this too ambitious for a google summer of code project?
2. Would implementing any of these algorithms be tricky due to some
peculiarity of LLVM?
3. Do existing optimisations and DFAs that depend on aliasing
information interface with the alias analysis in a context sensitive
manner, or do they require rewriting?
4. Is anyone willing to mentor this project?

Me:

I am PhD student at the University of Warwick, England, where my
current research is focused on specifying compiler optimisations in a
domain specification programming language and formally verifying the
soundness of those optimisations.  As part of this project I am in the
process of implementing a tool for optimising Java Byte code by
compiling optimising phases from these specifications.  During a final
year project I also co-wrote a compiler that worked on parallelising
Java source code.  I am also well versed in traditional compiler
design literature, including lattice based data flow analysis.

Any feedback on the aforementioned ideas would be welcome.  Regards,

  Richard Warburton

[0] http://llvm.org/OpenProjects.html
[1] http://llvm.org/docs/AliasAnalysis.html
[2] Whaley & Lam, Cloning based Context-Sensitive Pointer Alias
Analysis Using Binary Decision Diagrams, Programming Language Design &
Implementation 2004
[3] Jianwen Zhu, Symbolic Pointer Analysis, International Conference
on Computer Aided Design, 2002
[4] http://sourceforge.net/projects/buddy