Work in progress patch to speed up andersen's implementation

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. (35.1 KB) (16 KB)

bitmap.h (17.5 KB)

obstack.h (20.4 KB)

andersens.diff (57.5 KB)

Hi Danny,

I captured this as PR359:


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