On Mon, Jun 12, 2017 at 11:46 AM, Bin.Cheng <amker.ch...@gmail.com> wrote:
> On Mon, Jun 12, 2017 at 10:15 AM, Richard Biener
> <richard.guent...@gmail.com> wrote:
>> On Mon, Jun 12, 2017 at 11:02 AM, Bin.Cheng <amker.ch...@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
