<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<br>
<br>
<div class="moz-cite-prefix">On 03/22/2016 01:51 PM, Philip Reames
wrote:<br>
</div>
<blockquote cite="mid:56F1942D.5070409@philipreames.com" type="cite">
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
<br>
<br>
<div class="moz-cite-prefix">On 03/21/2016 06:53 PM, Daniel Berlin
wrote:<br>
</div>
</blockquote>
<blockquote cite="mid:56F1942D.5070409@philipreames.com" type="cite">
<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>
</blockquote>
<br>
Also out of curiosity, why LLVM choose to expose pointer analysis
information as alias-query APIs rather than APIs that let the client
query points-to sets? This question has bothered me ever since I
started to look into LLVM's alias analysis framework.<br>
<br>
It seems to me that alias queries may yield less precise results
than points-to queries. To put it in another way, it is easy to
convert points-to information to aliasing information (just check
for emptiness of points-to set intersection), but the reverse is
much harder and may not be possible sometimes. The alias set tracker
also introduce an additional source of imprecision: if a may alias b
and b may alias c, it is not necessary that a may alias c but the
AST would merge them all into one set.<br>
<br>
It also doesn't seem like alias information is cheaper to compute
(e.g. andersen) and is cheaper to query (e.g. the O(n^2) query
problem). <br>
<br>
-- <br>
Best Regards,<br>
<br>
--<br>
Jia Chen<br>
</body>
</html>