[llvm-dev] Existing studies on the benefits of pointer analysis

[Daniel Berlin via llvm-dev]

On Mon, Mar 21, 2016 at 7:32 AM, Christian Convey via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

> Hi Jia,
>
> If one looks at existing research literatures, there are even more
>> algorithm to consider for doing pointer analysis.
>
>
> For at least some published AA algorithms, there may be some uncertainty
> about software patents and/or copyright.
>
> At one point I was interested in the status of this AA implementation
> <https://dl.acm.org/citation.cfm?id=2466483> by Lian Li et al.  IIRC,
> when I contacted Lian to ask if there was any chance of getting it into
> LLVM, IIRC she said that her employer wouldn't promise to relinquish all
> possible claims it had on that algorithm's IP.  So unfortunately, at least
> in the U.S., an algorithm being published in an academic journal doesn't
> remove all legal risk associated with using it.
>

I wouldn't worry about this part.  I'm a pointer analysis guy and an IP
lawyer.
I'm pretty careful about what algorithms we end up with in LLVM :)


>
> Also, speaking from my own experience, even when an AA algorithm seems to
> be described in great detail in some piece of literature (e.g., a phd
> thesis), there can still be a lot of details which are glossed over, or
> which seem clear when reading the document but which get a lot more
> confusing when one tries to actually implement it.
>


Yes, i had a blog post on this one, which was basically titled "most
pointer analysis research is bullshit".  People mostly do research
implementations, and ignore little things like "the effect of external
function calls" (or worse "stub all of them"), and yes, implementing those
things significantly changes the time bounds.  Or they do things like tell
me that field-sensitivity slows nothing down because they are working on
java, where you can't take the address of fields :)

Over the years, you get a good eye for what will end up practical.

GCC's implementation of andersen's, which uses hardekopf's research and
work, is *very* fast in both Intra and inter procedural mode, field
sensitive, and handles all issues.

Adding context sensitivity to it would be expensive, however.


> That can make implementing such an algorithm take far longer than one
> would expect based on just reading the document.  (It's also an argument in
> favor of requiring academic papers which describe the behavior of a
> software implementation to actually include a working copy of the source
> code, IMHO.)
>

Yes.
This is one of the reasons's i always liked ben's research so much. He
published all code and benchmarks.

Note also that you a lot of them do have source code, you just have to look
really hard ;)


>
> So my question here is: what kind(s) of precision really justify the cost
>> and what kinds do not? Has anybody done any study in the past to evaluate
>> what kinds of features in pointer analyses will benefit what kinds of
>> optimization passes?
>>
>
> At one point I discussed this with Daniel Berlin, but I'm having trouble
> find a record of the conversation.  IIRC, he says that he once threw a huge
> amount of computing power at doing a *full* context-sensitive AA on some
> software, and the speedup he observed in the resulting program as
> underwhelming (10-15%?).
>
Yes.  But see below.


>
> I can't remember if that was with GCC or LLVM.  That result is a data
> point, although it may not say much about how much additional speedup could
> be realized if the algorithms which use the AA results were themselves
> adapted to capitalize on fully context-sensitive, flow-sensitive,
> hula-dancer-on-the-dashboard AA results.
>

Note however that this is going to be true of any new AA algorithm.   You
have to have the infrastructure necessary to make use of it, you have to
tune optimizations to use the information well, etc.

Realistically, getting the infrastructure ready and tuning it is a year or
two of work, at least (for one person).

As i mentioned, at this point, there is still much lower hanging fruit.
When there isn't, i suspect we'll get back to AA.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160321/aa131944/attachment.html>