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

Michael Kruse via llvm-dev <llvm-dev at lists.llvm.org> writes:
> AFAIK they are independent developments. LoopAccessAnalysis was
> extracted out of the LoopVectorizer in 2015, and first developed in
> 2013
(https://github.com/llvm/llvm-project/commit/d517976758c8674bdcd4c74457f7a83f20e432c5)
>
> DependenceAnalysis was a from-scratch implementation from 2012
>
(https://github.com/llvm/llvm-project/commit/59b61b9e2c549956b1094417a72c3943c20c9234)
>
> I do not know why LoopVectorize would not make use of
> DependenceAnalysis in 2013.
Is anyone looking at unifying these?  It's super confusing as things
stand.

                      -David
> Am Mo., 6. Juli 2020 um 09:51 Uhr schrieb David Greene <david.greene at
hpe.com>:
>>
>> Michael Kruse via llvm-dev <llvm-dev at lists.llvm.org> writes:
>>
>> > LLVM has multiple dependence analyses, each with its up- and
downsides:
>> >
>> >  * llvm::DependenceAnalysis
>> >  * llvm::LoopAccessAnalysis
>>
>> Can someone explain the differences between these?  As far as I can
tell
>> they essentially do the same thing (though perhaps one is more
>> precise?).  LAA seems to be used by vectorization (what else?) while DA
>> seems to be used by loop transformations (what else?).
>>
>> I am not a loop opt guy so while I'm familiar with the basic ideas,
the
>> details are somewhat lost on me.  Is there a reason to have two passes
>> or should they be combined and maintained as one pass?  If I have need
>> of dependence analysis it's not clear which I should use and the
>> comments are not much help.
>>
>>                    -David
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

Hi,

It happens that I'm working on dependence analysis this summer for outer
loop vectorization. I have studied a bit both LAA and DA.

Their most important difference is that DA is used for compile-time /
static checks while LAA is mainly used for generating run-time checks.

Now, more to their core, DA is based on strong theoretical background and
has a phenomenally clean implementation
(basically, if you have understood the paper, which itself is written as a
textbook chapter, since it kind of is, you have understood
almost all DA).
LAA on the other hand is a very hacky implementation and takes quite some
time just to understand what it tries to do.
It's hard to read. Note though that I know too little to criticize. This is
just how it seems to me.

It doesn't seem that strange to me that LAA had to be developed since if
you see its test-suite, i.e. the problems it had to solve,
for a lot of them, DA just gives up while LAA generates run-time checks.
Now, as to why it had to be implemented
in the way it was done, I would very much like to learn.

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.

Kind regards,
Stefanos

Στις Τρί, 7 Ιουλ 2020 στις 6:16 μ.μ., ο/η David Greene via llvm-dev <
llvm-dev at lists.llvm.org> έγραψε:
> Michael Kruse via llvm-dev <llvm-dev at lists.llvm.org> writes:
>
> > AFAIK they are independent developments. LoopAccessAnalysis was
> > extracted out of the LoopVectorizer in 2015, and first developed in
> > 2013 (
>
https://github.com/llvm/llvm-project/commit/d517976758c8674bdcd4c74457f7a83f20e432c5
> )
> >
> > DependenceAnalysis was a from-scratch implementation from 2012
> > (
>
https://github.com/llvm/llvm-project/commit/59b61b9e2c549956b1094417a72c3943c20c9234
> )
> >
> > I do not know why LoopVectorize would not make use of
> > DependenceAnalysis in 2013.
>
> Is anyone looking at unifying these?  It's super confusing as things
> stand.
>
>                       -David
>
> > Am Mo., 6. Juli 2020 um 09:51 Uhr schrieb David Greene <
> david.greene at hpe.com>:
> >>
> >> Michael Kruse via llvm-dev <llvm-dev at lists.llvm.org>
writes:
> >>
> >> > LLVM has multiple dependence analyses, each with its up- and
> downsides:
> >> >
> >> >  * llvm::DependenceAnalysis
> >> >  * llvm::LoopAccessAnalysis
> >>
> >> Can someone explain the differences between these?  As far as I
can tell
> >> they essentially do the same thing (though perhaps one is more
> >> precise?).  LAA seems to be used by vectorization (what else?)
while DA
> >> seems to be used by loop transformations (what else?).
> >>
> >> I am not a loop opt guy so while I'm familiar with the basic
ideas, the
> >> details are somewhat lost on me.  Is there a reason to have two
passes
> >> or should they be combined and maintained as one pass?  If I have
need
> >> of dependence analysis it's not clear which I should use and
the
> >> comments are not much help.
> >>
> >>                    -David
> > _______________________________________________
> > LLVM Developers mailing list
> > llvm-dev at lists.llvm.org
> > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200707/b4debe90/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

Am Di., 7. Juli 2020 um 10:39 Uhr schrieb Stefanos Baziotis
<stefanos.baziotis at gmail.com>:
> Their most important difference is that DA is used for compile-time /
static checks while LAA is mainly used for generating run-time checks.
Note that when the development of LAA started
(https://github.com/llvm/llvm-project/commit/d517976758c8674bdcd4c74457f7a83f20e432c5)
it also did static checks only, even though DA already existed in the
code base
(https://github.com/llvm/llvm-project/blob/d517976758c8674bdcd4c74457f7a83f20e432c5/llvm/lib/Analysis/DependenceAnalysis.cpp).
> Now, more to their core, DA is based on strong theoretical background and
has a phenomenally clean implementation
> (basically, if you have understood the paper, which itself is written as a
textbook chapter, since it kind of is, you have understood
> almost all DA).
> LAA on the other hand is a very hacky implementation and takes quite some
time just to understand what it tries to do.
> It's hard to read. Note though that I know too little to criticize.
This is just how it seems to me.
>
> It doesn't seem that strange to me that LAA had to be developed since
if you see its test-suite, i.e. the problems it had to solve,
> for a lot of them, DA just gives up while LAA generates run-time checks.
Now, as to why it had to be implemented
> in the way it was done, I would very much like to learn.
>
> 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.
Thanks for sharing your analysis.

Michael