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

Authored by fhahn on Aug 25 2022, 1:39 PM.

# Details

Reviewers
 Ayal anemet Meinersbur
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.

# Unit TestsFailed

### Event Timeline

fhahn created this revision.Aug 25 2022, 1:39 PM
Herald added a project: Restricted Project. Aug 25 2022, 1:39 PM
Herald added subscribers: frasercrmck, luismarques, apazos and 19 others.
fhahn requested review of this revision.Aug 25 2022, 1:39 PM
Herald added a project: Restricted Project. Aug 25 2022, 1:39 PM
reames added a subscriber: reames.Aug 25 2022, 2:45 PM
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.