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

[Reid Spencer]

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.