[LLVMdev] Google Summer of Code Idea

[Daniel Berlin]

On Mon, Mar 3, 2008 at 5:55 AM, Richard Warburton
<richard.warburton at gmail.com> wrote:
> >  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.
>
>  I was interested to see whether Whaley's algorithm really works
>  particularly, given its simplicity and the claims made in the papers.

Certainly, it works, and is not hard to implement.

All you need to do is to add a context number to each constraint, and
then you can clone them at every call and increment context number
fairly easily.
Storing constraint graphs in BDD's is also trivial (ben's source has a
few solvers that do this, IIRC).

>
>
>  >  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.
>
>  Are you referring to both the PLDI and the SAS papers?
Yes, as well as some other optimizations that have not been presented.

>
>
>  >  >  4. Is anyone willing to mentor this project?
>  >  I would.
>
>  Thanks ;)
>
>
>  >  I think you will be surprised how badly these algorithms work on even
>  >  moderate sized C++ programs :(
>
>  I'm slightly confused here as to whether you mean in terms of
>  precision of analysis, or compute time taken by running the algorithm.
>

Compute time.
None of these algorithms are useful at all in the real world if it
takes 3 years to compute the answer.

Precision of them, is of course, great, assuming you use a sane heap model.

--Dan