[LAA] Use BTC to rule out dependences if one ptr is loop invariant.

[fhahn]

Summary

isSafeDependenceDistance can also be used to rule out dependences
between loop invariant and loop-variant accesses if we ca prove the
distance between them is larger than the range the accesses will
travel through the execution of the loop.

This should help to avoid regressions after D126533.

[reames]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

1873

Not sure if this is a generalization, or a possible bug, but the fact you're dependent on the loop invariant bit here looks off.

My reasoning is as follows, if we know the stride of either access and the trip count, we can describe the region which that pointer can access. It shouldn't matter whether the other region is fixed size (i.e. pointer is loop invariant), or variably sized if we can prove that one region is before or after another.

Unless maybe we're trying to reason about the case where we don't know the sign of the distance between the start of the two regions?

Knowing that either operand is loop invariant does tell you that region is small. I could see how that might be useful when we can prove distance is far from zero (but potentially negative.)

However, in that case, I think there's a missing check to prove that the invariant region is smaller than abs(distance). That is, that the access type is smaller than distance. If it's not, we could have one varying region which starts with one byte offset into the loop invariant region.

Honestly, I think this code is made far more confusing by the fact that 0 is used an error value for stride. 0 is a valid stride; we really should be using Optional here instead.

1896

Please drop this below the constant check, and update the comment to note that the *following transforms* need matching strides. As written, it's unclear why the prior code is correct - if it is.

[fhahn]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

1873

Thanks, I don't think loop invariance is strictly necessary for correctness, just to limit the initial scope of the implementation. Let me look into writing up some test cases and see if it can be easily extended in this patch.

[Meinersbur]

It is a bit irritating that the current logic does not consider which direction the pointers are traveling. E.g. Src = &D[0] and Sink = %D[1+ i] never overlap (with non-negative i), but the code seems to consider Src before or after Sink symmetrically. But that's what the current code does. Changing that as @reames suggested computing memory regions relative to the base pointer might require more some effort, but this smaller change looks fine to me.

If Src and Sink don't use the same base pointer then getMinusSCEV(Sink, Src) will not return anything usable anyway.