<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 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><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 class="m_-5978761729718775768moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>
<a 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">
    <br>
    <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><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><b>Alexandre Isoard</b><br></div></div>
</div></div>