<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<br>
<br>
<div class="moz-cite-prefix">On 03/21/2016 08:56 AM, Jia Chen via
llvm-dev wrote:<br>
</div>
<blockquote cite="mid:56F0199C.9010807@cs.utexas.edu" type="cite">
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
Hi Christian,<br>
<br>
Thank you so much for the reply! Please see my comments inline.<br>
<br>
<div class="moz-cite-prefix">On 03/21/2016 09:32 AM, Christian
Convey wrote:<br>
</div>
<blockquote
cite="mid:CAPfS4Zy+Jf-pwaQmh=1p-8C_X_efWO+7uqUMR9KfnBAxPg-nVg@mail.gmail.com"
type="cite">
<div dir="ltr">Hi Jia,
<div><br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px
0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span
style="font-size:12.8px">If one looks at existing research
literatures, there are even more algorithm to consider for
doing pointer analysis.</span></blockquote>
<div><br>
</div>
<div>For at least some published AA algorithms, there may be
some uncertainty about software patents and/or copyright. </div>
<div><br>
</div>
<div>At one point I was interested in the status of <a
moz-do-not-send="true"
href="https://dl.acm.org/citation.cfm?id=2466483">this AA
implementation</a> 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.</div>
</div>
</blockquote>
This is news to me. Thanks for sharing it.<br>
<blockquote
cite="mid:CAPfS4Zy+Jf-pwaQmh=1p-8C_X_efWO+7uqUMR9KfnBAxPg-nVg@mail.gmail.com"
type="cite">
<div dir="ltr">
<div><br>
</div>
<div>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. </div>
<div><br>
</div>
<div>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.)</div>
</div>
</blockquote>
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. <br>
<blockquote
cite="mid:CAPfS4Zy+Jf-pwaQmh=1p-8C_X_efWO+7uqUMR9KfnBAxPg-nVg@mail.gmail.com"
type="cite">
<div dir="ltr">
<div><br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px
0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span
style="font-size:12.8px">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?</span><br>
</blockquote>
<div><br>
</div>
<div>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 <i>full</i> context-sensitive AA on some software,
and the speedup he observed in the resulting program as
underwhelming (10-15%?). <br>
</div>
</div>
</blockquote>
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. <br>
<br>
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. <br>
</blockquote>
Just to chime in here, your results match my experience and
expectations with LICM as well. Between basic-aa, and TBAA
(specifically LLVM's implementation thereof), I haven't seen a lot
of cases where an imprecision in the alias analysis prevents
hoisting.<br>
<br>
*However*, if you're interested in LICM specifically, I have
*definitely* seen cases where the precision of AliasSetTracker (our
grouping of AA results to prevent O(n^2) queries) prevents hoisting
in spurious cases. AST could use some serious attention, both from
an engineering standpoint and from (possibly) a theoretically one.
<br>
<blockquote cite="mid:56F0199C.9010807@cs.utexas.edu" type="cite">
<blockquote
cite="mid:CAPfS4Zy+Jf-pwaQmh=1p-8C_X_efWO+7uqUMR9KfnBAxPg-nVg@mail.gmail.com"
type="cite">
<div dir="ltr">
<div><br>
</div>
<div>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.</div>
</div>
</blockquote>
<blockquote
cite="mid:CAPfS4Zy+Jf-pwaQmh=1p-8C_X_efWO+7uqUMR9KfnBAxPg-nVg@mail.gmail.com"
type="cite">
<div dir="ltr">
<div><br>
</div>
<div class="gmail_extra">Cheers,</div>
<div class="gmail_extra">Christian</div>
<div class="gmail_extra"><br>
</div>
</div>
</blockquote>
<br>
-- <br>
Best Regards,<br>
<br>
--<br>
Jia Chen<br>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<a class="moz-txt-link-freetext" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<br>
</body>
</html>