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>