[LLVMdev] Alias analysis interface

[Dan Gohman]

On Fri, Nov 9, 2012 at 5:16 PM, Shuxin Yang <shuxin.llvm at gmail.com> wrote:

>  >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".
>

LLVM defines "AliasAnalysis" to be an API which never looks across loop
iterations, so "no alias" is correct here.


>
> 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.
>

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.


>
> 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?
>

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.

Dan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121112/678edc18/attachment.html>