[LLVMdev] Google Summer of Code Idea
dberlin at dberlin.org
Tue Mar 4 13:28:44 PST 2008
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
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.
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.
More information about the llvm-dev