[LLVMdev] Alias analysis interface

[Shuxin Yang]

 >what specifically you would like alias analysis to do?

Quite honestly, I don't know what interface is convenient for optimizer. 
I once implemented a flow-sensitive alias-analysis as a hobby project,
which was able to disambiguate the subscripted variables like a[i] and 
a[i-1]. Unfortunately, the interface is pretty messy, that
is why I solicit your insight on this issue.

The problem is: in what situations, Alias(a[i], a[i-1]) is desirable to 
return "alias", and in what situations,
it is desirable to return "no alias".

Example 1:
===========

   for (i = 0; i < N; i++) {
         a[i] = ... /* s1 */
        sum += a[i-1];
    }

   In DCE, Alias(a[i], a[i-1]) is desirable to return "alias". S1 would 
otherwise be mistakenly deleted.

Example 2:
=========
  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.

    for (i ...) {
           a[i] =    /* S1 */
           a[i-1]  = /* S2 */
                 = a[i] /* S3*/
    }

   As you can see from the above two examples, both answers ("alias" and 
"not alias") are correct, but in different context.

Is passing both mem access to Alias() sufficient, or should we also need 
to pass
     1) the common loop that tightly enclose two memory access, and
     2) boolean value indicate if the optimization is across loop or not.

  We likely should, but it the the interface clunky to use. What is your 
insight into this problem?

  Thanks
Shuxin







On 11/9/12 4:44 PM, Dan Gohman wrote:
> Hello,
>
> I'm afraid I don't understand your question. Could you restate your 
> example and your question, and say what specifically you would like 
> alias analysis to do?
>
> Dan
>
> On Fri, Nov 9, 2012 at 9:31 AM, Shuxin Yang <shuxin.llvm at gmail.com 
> <mailto:shuxin.llvm at gmail.com>> wrote:
>
>     Sorry the 1st example I gave it bit lame, it is changed to following:
>
>        // a[] is local array, no addr taken. die right after the loop
>
>        for (i = 0; i < N; i++) {
>            a[i] = ... /* s1 */
>            sum += a[i-1];
>        }
>
>      S1 could be easily deleted if alias analyizer say a[i] and a[i-1].
>
>
>
>     On 11/8/12 6:07 PM, Shuxin Yang wrote:
>
>         Hi,
>
>             In today meeting, Dan gave a very impressive talk about
>         alias analysis.
>         I had a question about the example in his slide, something like:
>
>           for (i = 0; i < N; i++) a[i] = a[i-1] + 1;
>
>          For the sake of convenience, let A1, A2 be a[i] and a[i-1]
>         respectively.
>         In Dan's design, Alias(A1, A2) would give "no alias", and in
>         order to
>         prevent A2 from being mistakenly moved out of loop, the optimizer
>         needs to query dependence test as well.
>
>           The problems is how optimizer combine the results from alias
>         analysis
>         and dependence test?
>
>           If I change the code little bit, into following, then
>         combining the
>         querying dependence testing would prevent hosting *q.
>
>           // points-to(p) = { a, b }
>           // points-to(q) = { c, d }
>           for (i = 0; i < N; i++) *p += *q + 1;
>
>         Thanks
>         Shuxin
>
>
>
>
>
>
>
>
>
>
>
>
>
>     _______________________________________________
>     LLVM Developers mailing list
>     LLVMdev at cs.uiuc.edu <mailto:LLVMdev at cs.uiuc.edu>
>     http://llvm.cs.uiuc.edu
>     http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121109/2bee877b/attachment.html>