[LLVMdev] Google Summer of Code Idea

[Daniel Berlin]

On Thu, Feb 28, 2008 at 1:43 PM, Richard Warburton
<richard.warburton at gmail.com> wrote:
> 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:
>
>  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?
No
I've got a BDD based version of andersen's around already (uncommitted).
It's slower in time (by a factor of 8 or so), but very slightly (1-2
megabytes of memory) more memory efficient on some cases. Nowadays,
the bitmap version is actually more memory efficient than the BDD
version, even if you turn off BDD caching, etc.

The thing you have to understand is that these context sensitive BDD
algorithms work okay on java, but fall down pretty badly on C/C++,
because it is a much bigger problem.   Whaley's is just brute force,
and Zhu's is pretty darn complex.

Both are amenable to the same style of offline variable optimizations
that Hardekopf, et al (Ben and a friend have been helping out with
implementation of andersen's in LLVM), and that may actually make them
usable for real world programs.

>  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?
It should work okay.

>  4. Is anyone willing to mentor this project?
I would.

I think you will be surprised how badly these algorithms work on even
moderate sized C++ programs :(