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

[Christian Convey via llvm-dev]

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.

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.

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

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%?).

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.

Cheers,
Christian
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160321/0f683fa7/attachment-0001.html>