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

>  Ah, that's important information I didn't have.  Thank you!
No problem, glad to help!

To the rest of your thoughts, I certainly agree. One interesting question
is why LAA
didn't use DA at all. Other than that, note that LAA is quite specialized,
namely for
loop vectorization. Actually, it's even more specific. For innermost loop
vectorization.
That affects the design. It might had been easier to create this
specialized tool than
extending a general one (if that was a good path to follow is another
topic).
> But yet they are intimately related in that the kind of information you
> want to know statically and dynamically is the same.  I wonder what it
> would take to extend DA to generate runtime checks if it can't prove
> independence.
Indeed, but again, IMHO unifying them is neither easy nor does it make
sense.
They do fundamentally the same thing but their directions are very
different.

So, I see two options:

a) As you said
>  I wonder what it would take to extend DA to generate runtime checks if
it can't prove independence.

Personally, I see potential but neither do I know what it would take. Since
this is something that I'm
currently thinking of, I would be more than interested to discuss it
extensively.

In any case, I would strongly prefer that we don't follow the LAA path,
since I don't think it has potential
anyway. I think that we should try to find a way to extend it that is also
based on strong theoretical foundation
and maintains the high quality of code.

b) Extend LAA to do static checks

The question here is though: Why do that? As I said, it doesn't seem to
have potential and I believe that people
working on vectorizers (either LLVM's current one or external like e.g. RV
and VPlan) don't do either.

Tell me what you think and I'm looking forward to more people jumping in.

- Stefanos

Στις Τρί, 7 Ιουλ 2020 στις 11:11 μ.μ., ο/η David Greene <
david.greene at hpe.com> έγραψε:
> Stefanos Baziotis via llvm-dev <llvm-dev at lists.llvm.org> writes:
>
> > Their most important difference is that DA is used for compile-time /
> > static checks while LAA is mainly used for generating run-time checks.
>
> Ah, that's important information I didn't have.  Thank you!
>
> > Now, as for unifying them, if we mean something other than just
putting
> > them in the same file, I don't think it can happen.
> > IMHO they're way more apart than it initially seems.
>
> But yet they are intimately related in that the kind of information you
> want to know statically and dynamically is the same.  I wonder what it
> would take to extend DA to generate runtime checks if it can't prove
> independence.
>
> The thing I fear is one or the other being enhanced to resolve more
> things statically without the other getting the same improvements.  Then
> some passes benefit and others don't and it won't be clear why. 
The
> same could happen with enhancement to dynamic checking (if it were added
> to DA).
>
>                        -David
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200707/4b31c73b/attachment.html>

Stefanos Baziotis via llvm-dev <llvm-dev at lists.llvm.org> writes:
> Their most important difference is that DA is used for compile-time /
> static checks while LAA is mainly used for generating run-time checks.
Ah, that's important information I didn't have.  Thank you!
> Now, as for unifying them, if we mean something other than just putting
> them in the same file, I don't think it can happen.
> IMHO they're way more apart than it initially seems.
But yet they are intimately related in that the kind of information you
want to know statically and dynamically is the same.  I wonder what it
would take to extend DA to generate runtime checks if it can't prove
independence.

The thing I fear is one or the other being enhanced to resolve more
things statically without the other getting the same improvements.  Then
some passes benefit and others don't and it won't be clear why.  The
same could happen with enhancement to dynamic checking (if it were added
to DA).

                       -David

Stefanos Baziotis via llvm-dev <llvm-dev at lists.llvm.org> writes:
> In any case, I would strongly prefer that we don't follow the LAA
> path, since I don't think it has potential anyway. I think that we
> should try to find a way to extend it that is also based on strong
> theoretical foundation and maintains the high quality of code.
Just to be clear, you don't think it has potential because it's been
disgned into an inner-loop corner and would take extensive rewriting to
handle OLV?
> Tell me what you think and I'm looking forward to more people jumping
in.
If my supposition above is correct, it certainly seems like extending DA
is the way to go but I'd like to hear from the current vectorizer
maintainers because I don't have enough knowledge to make an informed
judgment.

There's the VPlan infrastructure which I have not heard much about for
several months.  What is going on with that?  Yes, that's a vector
codegen issue but it may be useful to have a more complete picture of
how all this works or will work.

                   -David

Hi,
> On Jul 7, 2020, at 18:37, Stefanos Baziotis via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> >  Ah, that's important information I didn't have.  Thank you!
> 
> No problem, glad to help! 
> 
> To the rest of your thoughts, I certainly agree. One interesting question
is why LAA
> didn't use DA at all. Other than that, note that LAA is quite
specialized, namely for
> loop vectorization. Actually, it's even more specific. For innermost
loop vectorization.
> That affects the design. It might had been easier to create this
specialized tool than
> extending a general one (if that was a good path to follow is another
topic).
> 
> > But yet they are intimately related in that the kind of information
you
> > want to know statically and dynamically is the same.  I wonder what it
> > would take to extend DA to generate runtime checks if it can't
prove
> > independence.
> 
> Indeed, but again, IMHO unifying them is neither easy nor does it make
sense.
> They do fundamentally the same thing but their directions are very
different.
> 
> So, I see two options:
> 
> a) As you said
> 
> >  I wonder what it would take to extend DA to generate runtime checks
if it can't prove independence.
> 
> Personally, I see potential but neither do I know what it would take. Since
this is something that I'm
> currently thinking of, I would be more than interested to discuss it
extensively.
> 
> In any case, I would strongly prefer that we don't follow the LAA path,
since I don't think it has potential
> anyway. I think that we should try to find a way to extend it that is also
based on strong theoretical foundation
> and maintains the high quality of code.
I am not sure if that is an entirely fair characterization of LAA. LAA is being
used by the vectorizer (and other passes) in production for a few years now.
None of the in-tree users of DA seem to be enabled by default and therefore LAA
probably has an order of magnitude more testing, bug fixes & tuning.

DA’s implementation might be cleaner, but as mentioned earlier, DA handles only
a small subset of things LAA handles and hence I am not sure comparing the
code-complexity is too helpful.
IMO a lot of LAA complexity comes from things DA does not handle, in particular
runtime check generation. LAA also analyses & processes a whole loop whereas
DA only checks dependences between 2 memory accesses, as well as decides whether
it is profitable to generate runtime checks.

There is definitely potential for improving the structure & organization of
LAA, as well as improving the documentation. Happy to collaborate on that.

I am not convinced it makes sense to add runtime check generating to DA
directly, because I don’t think the static dependence checks really need to be
strongly coupled with runtime-check generation.
> b) Extend LAA to do static checks
> 
> The question here is though: Why do that? As I said, it doesn't seem to
have potential and I believe that people
> working on vectorizers (either LLVM's current one or external like e.g.
RV and VPlan) don't do either.
> 
To clarify, LAA does static checks and only generate runtime checks if it cannot
prove that the dependence is safe for vectorization statically. Granted, the
static checks mostly boil down to distance computations on SCEV expressions, but
for the current use cases it seems to work well enough.

It might be feasible to use DA for the static checks in LAA. That might help for
a few multi-dimensional cases, but in practice generating proper runtime-checks
for multi-dimensional cases is probably more important, due to aliasing issues.

Cheers,
Florian