This is the fix to PR56275 (https://github.com/llvm/llvm-project/issues/56275) which is a missed opportunity, where a perfrectly valid case for loop interchange failed interchange legality. More specifically, loop interchange does not interpret the direction vector correctly.
As we discussed on the PR page as well as in the loopopt meeting, the root problem is that the distance/direction vector produced by dependence analysis (DA) needs to be normalized (reversed), if the vector is negative. We've determined to provide helper functions in DA that does the normalization, and clients can ask DA to do normalization if needed.
In this patch I've added the helper functions isDirectionNegative() and normalize() such that DA results can get normalized if the direction is negative. Whether we call those function or not is based on a flag newly introduced, i.e., NeedsNormalization. Client passes (loop interchange for example) can set this flag to true (like the following) when they query DA, if they want DA results to be normalized. Please also refer to the follow-up loop interchange patch https://reviews.llvm.org/D130189 where DA is queried in loop interchange. It looks to me that this is the most clean way to do so, after experimenting with several alternatives.
DependenceInfo DI(&F, &AR.AA, &AR.SE, &AR.LI, /*NeedsNormalize=*/true); // use DI anywhere in client passes.
I've also added an opt option -da-normalize-results such that we can run DA directly with NeedsNormalization being true, and update DA test cases to make sure of test coverage. The test cases added in Banerjee.ll shows that negative vectors are normalized with -da-normalize-results=true.