<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
Hi Daniel,<br>
<br>
<div class="moz-cite-prefix">On 03/21/2016 11:05 AM, Daniel Berlin
wrote:<br>
</div>
<blockquote
cite="mid:CAF4BwTWVb7QQq7OGcpWcqSGru5dbmvdb79KpgZFK205Hnk6XJQ@mail.gmail.com"
type="cite">
<div dir="ltr"><br>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Tue, Mar 15, 2016 at 1:37 PM, Jia
Chen via llvm-dev <span dir="ltr"><<a
moz-do-not-send="true"
href="mailto:llvm-dev@lists.llvm.org" target="_blank"><a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a></a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000"> Dear llvm devs,<br>
<br>
tl;dr: What prevents llvm from switching to a fancier
pointer analysis?<br>
</div>
</blockquote>
<div><br>
</div>
<div>Nothing.</div>
<div> </div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000"> <br>
Currently, there exists a variety of general-purpose
alias analyses in the LLVM codebase: basic-aa,
globalsmodref-aa, tbaa, scev-aa, and cfl-aa. However,
only the first three are actually turned on when
invoking clang with -O2 or -O3 (please correct me if I'm
wrong about this).<br>
</div>
</blockquote>
<div><br>
</div>
<div>This is correct.</div>
<div>Eventually, i hope george will have time to get back to
CFL-AA and turn it on by default.</div>
<div> <br>
</div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000"> <br>
If one looks at existing research literatures, there are
even more algorithm to consider for doing pointer
analysis. Some are field-sensitive, some are
field-based, some are flow-sensitive, some are
context-sensitive. Even for flow-insensitive ones, they
could also be inclusion-style (-andersen-aa) and
equality-style (-steens-aa and -ds-aa). Those algorithms
are often backed up by rich theoretical framework as
well as preliminary evaluations which demonstrate their
superior precision and/or performance.<br>
</div>
</blockquote>
<div><br>
</div>
<div>CFL-AA is a middle ground between steens and anders,
can be easily made field and context sensitive, etc.</div>
<div> </div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000"> <br>
Given such an abundance choices of pointer analyses that
seem to be much better in the research land, why does
real-world compiler infrastructures like llvm still rely
on those three simple (and ad-hoc) ones to perform IR
optimization? </div>
</blockquote>
<div><br>
Time and energy.</div>
<div> <br>
</div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">Based on my
understanding (and again please correct me if I am
wrong):<br>
<br>
(1) The minor reason: those "better" algorithms are very
hard to implement in a robust way and nobody seems to be
interested in trying to write and maintain them.<br>
</div>
</blockquote>
<div><br>
</div>
<div>This is false. Heck, at the time i implemented it in
GCC, field-sensitive andersen's analysis was unknown in
production compilers. That's why i'm thanked in all the
papers - i did the engineering work to make it fast and
reliable.</div>
<div><br>
</div>
<div> </div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000"> (2) The major
reason: it's not clear whether those "better" algorithms
are actually better for llvm. More precise pointer
analyses tend to slow down compile time a lot while
contributing too little to the optimization passes that
use them. The benefit one gets from a more precise
analysis may not justify the compile-time or the
maintenance cost.<br>
</div>
</blockquote>
<div><br>
</div>
<div><br>
</div>
<div>CFL-AA is probably the right trade-off here. You can
stop at any time and have correct answers, you can be as
lazy as you like.</div>
<div>etc.</div>
</div>
</div>
</div>
</blockquote>
<br>
Regarding CFL-AA: in my understanding, cfl-aa does not introduce a
new precision tradeoff. It is merely a demand-driven way of
implementing existing analyses, by extending those algorithms to
track additional "pointed-to-by" information. Laziness may help with
the running time of the cfl analysis when only partial points-to
info is needed, but if the client wants to do a whole-program
analysis and require whole-program points-to info (which is usually
true for optimizing compilers since they will eventually examine and
touch every piece of the codes given to it), should cfl-aa be no
different than traditional whatever-sensitive pointer analysis?<br>
<br>
<blockquote
cite="mid:CAF4BwTWVb7QQq7OGcpWcqSGru5dbmvdb79KpgZFK205Hnk6XJQ@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div><br>
</div>
<div>The reality is i think you overlook the realistic
answer:<br>
<br>
</div>
<div>3. Nobody has had time or energy to fix up CFL-AA or
SCEV-AA. They spend their time on lower-hanging fruit
until that lower hanging fruit is gone.</div>
<div><br>
</div>
<div>IE For the moment, CFL-AA and SCEV-AA and ... are not
the thing holding llvm back.</div>
<div><br>
</div>
</div>
</div>
</div>
</blockquote>
I'd love to hear some examples of "lower-hanging fruit" in LLVM,
especially in the area of middle-end analyses and optimizations. I
thought LLVM is mature enough that any obvious chances of
improvement in analyses and optimization have already been taken,
no?<br>
<blockquote
cite="mid:CAF4BwTWVb7QQq7OGcpWcqSGru5dbmvdb79KpgZFK205Hnk6XJQ@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div> </div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000"> <br>
So my question here is: what kind(s) of precision really
justify the cost and what kinds do not?</div>
</blockquote>
<div><br>
</div>
<div>Depends entirely on your applications.</div>
<div> </div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000"> Has anybody done
any study in the past to evaluate what kinds of features
in pointer analyses will benefit what kinds of
optimization passes?</div>
</blockquote>
<div>Yes.</div>
<div>Chris did many years ago, and i've done one more
recently.</div>
</div>
</div>
</div>
</blockquote>
<br>
Great! Are they published somewhere? Can the data be shared somehow?<br>
<blockquote
cite="mid:CAF4BwTWVb7QQq7OGcpWcqSGru5dbmvdb79KpgZFK205Hnk6XJQ@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div> </div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000"> Could there
potentially be more improvement on pointer analysis
precision without adding too much
compile-time/maintenance cost? </div>
</blockquote>
<div>Yes.</div>
<div><br>
</div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">Has the
precision/performance tradeoffs got fully explored
before? <br>
</div>
</blockquote>
<div>Yes </div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000"> <br>
Any pointers will be much appreciated. No pun intended
:)<br>
<br>
PS1: To be more concrete, what I am looking for is not
some black-box information like "we switched from
basic-aa to cfl-aa and observed 1% improvement at
runtime". I believe white-box studies such as "the licm
pass failed to hoist x instructions because -tbaa is not
flow sensitive" are much more interesting for
understanding the problem here.<br>
</div>
</blockquote>
<div><br>
</div>
<div>White-box studies are very application specific, and
often very pass specific.</div>
</div>
</div>
</div>
</blockquote>
<br>
And I understand that. My goal is to look for commonalities among
passes and applications. However, if the existing studies you
mentioned above are extensive and conclusive enough to show that the
aas we have today have fully exploited almost all such
commonalities, then it's probably a better idea for me to find
something else to work on. But again, I'd like to see the data
first.<br>
<blockquote
cite="mid:CAF4BwTWVb7QQq7OGcpWcqSGru5dbmvdb79KpgZFK205Hnk6XJQ@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div> <br>
</div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000"> <br>
PS2: If no such evaluation exists in the past, I'd happy
to do that myself and report back my findings if anyone
here is interested.</div>
</blockquote>
<div>I don't think any of the world is set up to make that
valuable.</div>
<div><br>
</div>
<div>Nothing takes advantage of context sensitivity, flow
sensitivity, etc.</div>
</div>
</div>
</div>
</blockquote>
I agree that nothing takes advantage of context sensitivity. But I
would argue against flow sensitivity, field sensitivity, heap model
and external function models. Flow sensitivity is helpful when the
optimization pass itself is flow-sensitive (e.g. adce, gvn), and
field sensitivity is helpful when a struct contains multiple
pointers. Heap sensitivity is basically what motivates Chris
Lattner's PLDI'07 paper, and external function models are helpful
since without them the analysis has to be extremely conservative and
concludes everything that external functions touch all may-alias
each other. <br>
<br>
<blockquote
cite="mid:CAF4BwTWVb7QQq7OGcpWcqSGru5dbmvdb79KpgZFK205Hnk6XJQ@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div> </div>
</div>
</div>
</div>
</blockquote>
-- <br>
Best Regards,<br>
<br>
--<br>
Jia Chen<br>
</body>
</html>