On Fri, Nov 9, 2012 at 5:16 PM, Shuxin Yang <span dir="ltr"><<a href="mailto:shuxin.llvm@gmail.com" target="_blank">shuxin.llvm@gmail.com</a>></span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000"><div class="im">
>what specifically you would like alias analysis to do?<br>
<br></div>
Quite honestly, I don't know what interface is convenient for
optimizer. I once implemented a flow-sensitive alias-analysis as a
hobby project, <br>
which was able to disambiguate the subscripted variables like a[i]
and a[i-1]. Unfortunately, the interface is pretty messy, that <br>
is why I solicit your insight on this issue. <br>
<br>
The problem is: in what situations, Alias(a[i], a[i-1]) is desirable
to return "alias", and in what situations, <br>
it is desirable to return "no alias". <br></div></blockquote><div><br></div><div>LLVM defines "AliasAnalysis" to be an API which never looks across loop iterations, so "no alias" is correct here.</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>
Example 1:<br>
===========<div class="im"><br>
<br>
for (i = 0; i < N; i++) {<br>
a[i] = ... /* s1 */<br>
sum += a[i-1];<br>
}<br>
<br></div>
In DCE, Alias(a[i], a[i-1]) is desirable to return "alias". S1
would otherwise be mistakenly deleted. <br></div></blockquote><div><br></div><div>LLVM's dead store elimination pass isn't smart enough to delete this kind of dead store, so its use of the AliasAnalysis API is fine. A more aggressive dead store elimination pass would need to use a higher-level API.</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>
Example 2:<br>
=========<br>
In following contrived example, Alias(a[i], a[i-1]) is desirable to
return "no alias" in order to enable the propagation between S1 and
S3.<br>
<br>
for (i ...) { <br>
a[i] = /* S1 */<br>
a[i-1] = /* S2 */<br>
= a[i] /* S3*/<br>
}<br>
<br>
As you can see from the above two examples, both answers ("alias"
and "not alias") are correct, but in different context. <br><br>
Is passing both mem access to Alias() sufficient, or should we also
need to pass <br>
1) the common loop that tightly enclose two memory access, and<br>
2) boolean value indicate if the optimization is across loop or
not.<br>
<br>
We likely should, but it the the interface clunky to use. What is
your insight into this problem?<br></div></blockquote><div><br></div><div>One of LLVM's insights is that simple optimizations which don't look across loop boundaries, or which only do so in limited and careful ways, are "good enough" in many real-world situations. The AliasAnalysis API is designed to support this kind of use, and it benefits from this simplicity. The AliasAnalysis API can also serve as a base on which higher-level analyses can be built.</div>
<div><br></div><div>Dan</div><div> </div></div>