This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Lack of capability to represent arbitrary alias dependent information


On Mon, Jun 12, 2017 at 11:46 AM, Bin.Cheng <amker.cheng@gmail.com> wrote:
> 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.
Hmm, my bad being over-optimistic.  So here is the mode: After fusing
all SCCs, the condition to model fused dependence graph using
clique/base is below:
For each connected component of the fused graph, the diameter of the
connected component is no larger than 2.  I believe this is true for
majority cases, but full proof is complicated.  Specially, it might be
not always true in case of restrict pointers.  I will think about if
we can only handle simplest cases.

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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]