Re: Lack of capability to represent arbitrary alias dependent information

["Bin.Cheng" <amker dot cheng at gmail dot com>]

On Mon, Jun 12, 2017 at 10:15 AM, Richard Biener
<richard.guenther@gmail.com> wrote:
> 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.
Yes, right.  I missed the base part.  In this case, the dependence
info can well model runtime alias information.

Thanks,
bin
>
> So it's not just SCCs but slightly more powerful (but only very
> slightly).
>
> Richard.
>
>> Thanks,
>> bin