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 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.