[LLVMbugs] [Bug 1359] NEW: Finish Danny Berlin's Re-implementation of Andersen's AA

[bugzilla-daemon at cs.uiuc.edu]

http://llvm.org/bugs/show_bug.cgi?id=1359

           Summary: Finish Danny Berlin's Re-implementation of Andersen's AA
           Product: libraries
           Version: trunk
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Global Analyses
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: rspencer at reidspencer.com


>From Danny:

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.



------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.