<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 06:53 PM, Daniel Berlin
wrote:<br>
</div>
<blockquote
cite="mid:CAF4BwTUUtKUPTo1yfxhG1mefkv+tMYY9ZOfkUidRiCxKeefvvQ@mail.gmail.com"
type="cite">
<div dir="ltr"><br>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Mon, Mar 21, 2016 at 6:28 PM,
Philip Reames 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 text="#000000" bgcolor="#FFFFFF"><span class=""> <br>
<br>
<div>On 03/21/2016 08:56 AM, Jia Chen via llvm-dev
wrote:<br>
</div>
<blockquote type="cite"> <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>
</span> 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>
</div>
</blockquote>
<div><br>
Yeah, at best, for LICM, it's just going to tell you the
best place to insert runtime checks. LICM has a specific
goal, and it's usually not AA that prevents proving
something loop invariant. Most loads/stores are also
either trivially loop invariant, or impossible to prove
loop invariant.</div>
</div>
</div>
</div>
</blockquote>
Side note: The key limiting factor for load hoisting is most often
being able to prove dereferenceability. I only mention that because
the OP had asked for where other optimizer changes might help. <br>
<blockquote
cite="mid:CAF4BwTUUtKUPTo1yfxhG1mefkv+tMYY9ZOfkUidRiCxKeefvvQ@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF"> <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.
</div>
</blockquote>
<div><br>
</div>
<div><br>
</div>
<div>You already know my view on this one: It's going to be
remarkably hard to make AST work the way folks want it and
have it be incremental and completely agnostic of anything
but the AA API.</div>
<div><br>
</div>
<div>It's just really hard if not provably impossible to do
this incrementally and avoid duplicate work, and get
precise results and ...</div>
<div><br>
</div>
<div><br>
</div>
<div>On the other hand, it's pretty easy if you basically
say "i provide list of all pointers and statements i care
about, you make me some sets", and you let it figure out
the answers upfront.</div>
</div>
</div>
</div>
</blockquote>
Er, this is actually fairly close to what the code does. It just
does it in a really oddly structured manner. But yes, I agree, this
code could be radically improved. <br>
<blockquote
cite="mid:CAF4BwTUUtKUPTo1yfxhG1mefkv+tMYY9ZOfkUidRiCxKeefvvQ@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div><br>
</div>
<div>(it's also not clear to me why AST is the right
abstraction for LICM to work on top of, but that's neither
here nor there :P)</div>
</div>
</div>
</div>
</blockquote>
Out of curiosity, what would you suggest instead?<br>
<br>
For context, I have a patch in my tree which falls back to O(n^2)
queries for small loops. We found this to be rather important for
the optimization of IR derived from our Java frontend. <br>
<br>
Philip<br>
</body>
</html>