This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: Lack of capability to represent arbitrary alias dependent information
On Mon, Jun 12, 2017 at 2:00 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
> 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.
I expect we can exactly handle the cases you could map to restrict.
The model was really developed for restrict and with the goal to have
O(n) size complexity to store non-dependences for n references
(which is quite ambitious ;)). Inside the loop pipeline we'd in theory
have the option to keep computed data dependences, at least
across a few passes. OTOH we basically gave up doing that for SCEV
and thus most passes clear the SCEV cache for the fear of corrupting it.
Richard.
> Thanks,
> bin
>>
>> Thanks,
>> bin
>>>
>>> So it's not just SCCs but slightly more powerful (but only very
>>> slightly).
>>>
>>> Richard.
>>>
>>>> Thanks,
>>>> bin