llvm dev - Jul 2020 - How to get information about data dependencies?

Stefanos Baziotis via llvm-dev <llvm-dev at lists.llvm.org> writes:
> Well... I tried that and it doesn't seem to be very useful
> unfortunately.  The C/C++ way that arrays are defined is probably why
> DA is not that useful. Namely that a row can alias with another row in
> 2D arrays. The theory behind DA is quite powerful if we knew that they
> don't alias. Right now, it just gives up.
Note that the situation is very different in flang, where good
dependence analysis becomes much more critical.

                      -David

>From what I know about Fortran (which is next to nothing), it provides
aliasing guarantees, e.g. that different rows
don't alias so yes this is important there.

A note regarding C/C++ that I was assuming, but only confirmed recently.

Any serious multi-dimensional performance code (e.g. benchmarks) is not
written with indirect pointers. E.g. if you want to do operations
on a 3-D array, the function won't get a ***A. It will get *A and then
index like A[i*n + j*m + k] (this is the same if you
take a multi-dim static array, in which indexing is lowered into the same
thing - single pointer and GEPs).

Probably the reason is what we're discussing. Because you get one pointer,
that you also mark _restrict_, and you're done.

I'm (partly) in the middle of investigating DA's role in LLVM, hopefully
something good will come out.

- Stefanos

Στις Τετ, 15 Ιουλ 2020 στις 10:17 μ.μ., ο/η David Greene <
david.greene at hpe.com> έγραψε:
> Stefanos Baziotis via llvm-dev <llvm-dev at lists.llvm.org> writes:
>
> > Well... I tried that and it doesn't seem to be very useful
> > unfortunately.  The C/C++ way that arrays are defined is probably why
> > DA is not that useful. Namely that a row can alias with another row in
> > 2D arrays. The theory behind DA is quite powerful if we knew that they
> > don't alias. Right now, it just gives up.
>
> Note that the situation is very different in flang, where good
> dependence analysis becomes much more critical.
>
>                       -David
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200715/e835e128/attachment.html>

Thanks for the info. Let me clarify something that might have caused
confusion: When I said 2D arrays above, I meant
double pointers, which is another beast on its own. Basically my example
states that e.g. a[0][1] and a[0][2] could easily
point to the same exact memory.

Now, returning the discussion to _static arrays_, which is more realistic
anyway in high-performance code, I think I would
be very happy to see GEP with dynamic sizes. In my current work, I depend
on SCEV Delinearization to recover the
indices (I guess many people have had to do that, for no actual reason).
> We also had a discussion whether `A[i][j]` can be lowered to a
> GetElementPtr with `inrange` keyword for the subscripts, including for
> statically sized arrays.
To lower it to _one_ GEP, wouldn't that require GEPs with dynamic sizes?

Also, to be sure we're on the same page, this is beneficial because, as in
the RFC example, if we have
A[x1][y1] and A[x2][y2] and x1 != x2 and y1 != y2, then the two don't
alias. Actually, if `inrange` works
as expected, even if one of the conditions holds, the two don't alias.

- Stefanos

Στις Τρί, 21 Ιουλ 2020 στις 12:18 π.μ., ο/η Michael Kruse <
llvmdev at meinersbur.de> έγραψε:
> Am Mi., 15. Juli 2020 um 14:18 Uhr schrieb David Greene via llvm-dev
> <llvm-dev at lists.llvm.org>:
> > Stefanos Baziotis via llvm-dev <llvm-dev at lists.llvm.org>
writes:
> >
> > > Well... I tried that and it doesn't seem to be very useful
> > > unfortunately.  The C/C++ way that arrays are defined is probably
why
> > > DA is not that useful. Namely that a row can alias with another
row in
> > > 2D arrays. The theory behind DA is quite powerful if we knew that
they
> > > don't alias. Right now, it just gives up.
> >
> > Note that the situation is very different in flang, where good
> > dependence analysis becomes much more critical.
>
> There was an RFC on the mailing list to support a GetElementPtr with
> dynamic array sizes:
> http://lists.llvm.org/pipermail/llvm-dev/2019-July/134063.html
>
> We also had a discussion whether `A[i][j]` can be lowered to a
> GetElementPtr with `inrange` keyword for the subscripts, including for
> statically sized arrays.
>
> Michael
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200720/a51bc571/attachment.html>

Am Mi., 15. Juli 2020 um 14:18 Uhr schrieb David Greene via llvm-dev
<llvm-dev at lists.llvm.org>:
> Stefanos Baziotis via llvm-dev <llvm-dev at lists.llvm.org> writes:
>
> > Well... I tried that and it doesn't seem to be very useful
> > unfortunately.  The C/C++ way that arrays are defined is probably why
> > DA is not that useful. Namely that a row can alias with another row in
> > 2D arrays. The theory behind DA is quite powerful if we knew that they
> > don't alias. Right now, it just gives up.
>
> Note that the situation is very different in flang, where good
> dependence analysis becomes much more critical.
There was an RFC on the mailing list to support a GetElementPtr with
dynamic array sizes:
http://lists.llvm.org/pipermail/llvm-dev/2019-July/134063.html

We also had a discussion whether `A[i][j]` can be lowered to a
GetElementPtr with `inrange` keyword for the subscripts, including for
statically sized arrays.

Michael