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

[Jia Chen via llvm-dev]

Hi Christian,

Thank you so much for the reply! Please see my comments inline.

On 03/21/2016 09:32 AM, Christian Convey 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.
This is news to me. Thanks for sharing 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.)
My personal experience also coincides. And even if the paper does come 
with an artifact or source codes, they are usually proof-of-concept 
implementations with lots of important real-world corner cases ignored.
>
>     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 kind of expect that. As you mentioned later, most optimization passes 
work in a context-insensitive manner (i.e. they won't clone a function 
and optimize differently on different clones). Context sensitivity on 
the pointer analysis side is probably not going to help a lot if the 
client cannot fully capitalize on it. In the settings of compiler 
optimization, my guess is that flow sensitivity, field sensitivity, heap 
model and external library annotations are the four aspects that are 
likely to matter.

I did some preliminary experiments with licm on c programs over the last 
weekend. I chose licm because intuitively that's the optimization that 
could have the biggest performance impact. The result suggested that 
tbaa, cfl-aa, scev-aa and globals-aa yields very little additional 
benefits over basic-aa. Again, both the methodology and benchmark 
selection are very immature and the results need to be double-checked, 
but my hope is that by looking at how aa algorithms and their clients 
interact I may be able to get some hints on what kind of aa a compiler 
really wants.
>
> 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
>

-- 
Best Regards,

--
Jia Chen
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160321/6adf397c/attachment.html>