<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<p><br>
</p>
<div class="moz-cite-prefix">On 03/09/2017 03:14 PM, Alexandre
Isoard wrote:<br>
</div>
<blockquote
cite="mid:CANLM5LfBD3HJb5WDh3Xo6Bgtds6K6S4r193x=CytwD-+yMaY2g@mail.gmail.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<div dir="ltr"><br>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Thu, Mar 9, 2017 at 8:03 PM, Hal
Finkel <span dir="ltr"><<a moz-do-not-send="true"
href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</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"><span class="">
<p><br>
</p>
<div class="m_-5978761729718775768moz-cite-prefix">On
03/09/2017 01:39 PM, Alexandre Isoard via llvm-dev
wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">Hello fellow LLVM developers,
<div><br>
</div>
<div>I was wondering about the semantic of
aliasing.</div>
<div>Here are some examples where I am not sure if
the two stores aliases:</div>
<div><br>
</div>
<div>Example 1:</div>
<div><br>
</div>
<div>for (int i = 2; i < n; ++i) {</div>
<div> store A[i];</div>
<div> store A[i-2];</div>
<div>}</div>
<div><br>
</div>
<div>Example 2:</div>
<div><br>
</div>
<div>for (int i = 2; i < n; ++i)</div>
<div> store A[i];</div>
<div>
<div>for (int i = 2; i < n; ++i)</div>
<div> store A[i-2];</div>
<div><br>
</div>
<div>In the example 1, they do not alias in a
single iteration, but they do alias at some
point if n > 4.</div>
</div>
</div>
</blockquote>
<br>
</span> If you ask LLVM's AA whether 'store A[i]' and
'store A[i-2]' alias, it should say NoAlias. When two
memory accesses have addresses that depend on common SSA
values (the PHI node %i in this case), then it is
interpreted as having the same value in both
instructions.<br>
<br>
In example 2, you should get a MayAlias result, the PHI
in both loops will be distinct SSA values (even though
you've given them the same name in your example), and we
can't prove that the memory accessed by the first store
is disjoint from the memory accessed by the second.<br>
<br>
In any case, please don't confuse our AA for a loop
dependence analysis. Are you looking for a loop
dependence analysis?<br>
</div>
</blockquote>
<div><br>
</div>
<div>That is most certainly what I am looking for.</div>
<div>I was wrongly assuming that AliasAnalysis would be a
cheap over-approximation, I was wrong.</div>
</div>
</div>
</div>
</blockquote>
<br>
Not in that sense. If you construct a MemoryLocation object from
both accesses, set both sizes to UnknownSize, and then check
AA->alias(L1, L2) != NoAlias && AA->alias(L2, L1) !=
NoAlias, then you can essentially get this kind of cheap
over-approximation.<br>
<br>
You can also use the dependence analysis if you'd like
(LoopAccessAnalysis, which is what the loop vectorizer uses). There
is also an DependenceAnalysis analysis, which is more powerful in
some ways.<br>
<br>
-Hal<br>
<br>
<blockquote
cite="mid:CANLM5LfBD3HJb5WDh3Xo6Bgtds6K6S4r193x=CytwD-+yMaY2g@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div><br>
</div>
<div>Thanks.</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"> -Hal<br>
<br>
<blockquote type="cite"><span class="">
<div dir="ltr">
<div>
<div>That is, there is an execution path from
one instance of the store to an instance of
the other store such that they access the same
memory cell.</div>
<div><br>
</div>
<div>In example 2 it is easier to see the
difference.</div>
<div><br>
</div>
<div>I am somewhat in the fog here.</div>
<div><br>
</div>
<div>Best regard.</div>
<div><br>
</div>
-- <br>
<div
class="m_-5978761729718775768gmail_signature">
<div dir="ltr"><b>Alexandre Isoard</b><br>
</div>
</div>
</div>
</div>
<br>
<fieldset
class="m_-5978761729718775768mimeAttachmentHeader"></fieldset>
<br>
</span>
<pre>______________________________<wbr>_________________
LLVM Developers mailing list
<a moz-do-not-send="true" class="m_-5978761729718775768moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>
<a moz-do-not-send="true" class="m_-5978761729718775768moz-txt-link-freetext" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><span class="HOEnZb"><font color="#888888">
</font></span></pre><span class="HOEnZb"><font color="#888888">
</font></span></blockquote><span class="HOEnZb"><font color="#888888">
<pre class="m_-5978761729718775768moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</font></span></div>
</blockquote></div>
<div>
</div>--
<div class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><b>Alexandre Isoard</b>
</div></div>
</div></div>
</blockquote>
<pre class="moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre></body></html>