[llvm-dev] How to get information about data dependencies?

[Florian Hahn via llvm-dev]

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