Re: Lack of capability to represent arbitrary alias dependent information

[Richard Biener <richard dot guenther at gmail dot com>]

On Mon, Jun 12, 2017 at 11:02 AM, Bin.Cheng <amker.cheng@gmail.com> wrote:
> HI,
> GCC adds runtime alias checks for data references in passes like
> vectorizer, it would be very useful to pass along the runtime alias
> dependent information to later passes.  Given below expample:
>
> int foo (int *a, int *b, int *c, int *d, int *e, int len, int v)
> {
>   int k, x;
>   for (k = 0; k < len; k++)
>     {
>       c[k] = a[k-1] + b[k-1];
>       if ((x = d[k-1] + e[k-1]) > c[k]) c[k] = x;
>       if (c[k] < v) c[k] = v;
>     }
>
>   return 0;
> }
> After vectorizer's runtime alias check, we know that c doesn't alias
> to a/b/d/e arrays.  This enables dead store elimination for c array.
> The question is how to pass the information to dse (or predcom, etc.).
> So far MR_DEPENDENCE_* is suggested, but I found it's not capable of
> that.  The fundamental issue is MR_DEPENDENCE_* can only represent
> alias relations between references in a strong connected component of
> dependence graph, while in most cases (like this one) the dependence
> graph is not SCC.  In general, if we have below dependence graph:
> Dependence Graph: G<V, E>
> V: {x(write), y(write), a(read), b(read)}
> E: <x, a>
>      <x, b>
>      <y, a>
>      <y, b>
> Since a and b are reads, we don't need to know the relations between a
> and b;  also it's possible to have any dependence relation between x
> and y.  In this case, we can't assign x, a and b into one clique.  We
> can't assign x and y into different clique either because they both
> are not-aliasing to a/b.  As a matter of fact, we need a way to
> represent arbitrary dependence graph, rather than SCC only.
> So any suggestions?

The "simplest" solution is to assign the same BASE to those.

This is how restrict works to record dependence on not restrict
marked pointers or decls.

So it's not just SCCs but slightly more powerful (but only very
slightly).

Richard.

> Thanks,
> bin