[LLVMdev] Work in progress patch to speed up andersen's implementation

[Daniel Berlin]

Thanks.
I'll try to pick it back up in a month or so if no one beats me to it.

On 4/25/07, Reid Spencer <rspencer at reidspencer.com> wrote:
> Hi Danny,
>
> I captured this as PR359: http://llvm.org/PR1359
>
> Reid.
>
> On Wed, 25 Apr 2007 14:09:14 -0400
>   "Daniel Berlin" <dberlin at dberlin.org> wrote:
> > Hi guys, i'm not going to have time to work on this for
> >a month or
> > two, so i figured i'd post it.
> >
> > This patch
> >
> > 1. reworks the andersen's implementation to support
> >field sensitivity
> > (though field-sensitive constraints are not generated
> >directly yet),
> > and uses it to do indirect function call support.
> > 2. Rewrites the solver to be state of the art in terms
> >of speed.
> > kimwitu++ used to take <i stopped it after a few hours>
> >to solve, and
> > now it takes < 2 seconds.
> > 3. Reworks the rest of the implementation to make it
> >easy to support
> > offline variable substitution.
> >
> > There are still more improvements to be made, and in
> >particular
> > implementing ovs.  This is not more than a couple
> >hundred lines of
> > code, and would speed it up by another few orders of
> >magnitude (as
> > well as reduce memory usage greatly).
> >
> > The main thing blocking this patch, however, is that
> >someone needs to
> > rewrite bitmap.c/bitmap.h, obstack.c and obstack.h, into
> >C++.  They
> > are currently just modified versions of what gcc is
> >using.
> > You can get rid of the obstacks, of course.
> >
> > Using set<u32> or BitVector or something like it will
> >result in a
> > slowdown of mammoth proporations, and about a 10x memory
> >increase.
> > Trust me here, you don't want to use a non-sparse
> >bitmap.
> > BDD's are acceptable, but are about a 2x slowdown.  With
> >various
> > optimizations that are going to be published in the next
> >few months,
> > you can get bitmaps to use just as little memory as BDDs
> >would, while
> > being much faster.
> >
> > Anyway, i've attached the patch.
> > The two new .h files go  include/llvm/ADT
> > the two new .cc files go into lib/VMCore
> >
> > Of course, you can put them wherever you really want.
>
>