[DependenceAnalysis][PR56275] Normalize negative dependence analysis results
authorCongzhe Cao <congzhe.cao@huawei.com>
Wed, 3 Aug 2022 23:37:30 +0000 (19:37 -0400)
committerCongzheUalberta <congzhecao@gmail.com>
Wed, 3 Aug 2022 23:59:00 +0000 (19:59 -0400)
commit76be5549318a9e5aa3bdc2b3e0ae8ed5a16bfe59
tree9bb70c69498692163fb5cc604e166edd20d1ed95
parenta243af52bb6660d2abdc8eacfa287de5c3d28dfa
[DependenceAnalysis][PR56275] Normalize negative dependence analysis results

This patch is the first of the two-patch series (D130188, D130179) that
resolve 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.

If the distance/direction vector produced by dependence analysis (DA) is
negative, it needs to be normalized (reversed). This patch provides helper
functions `isDirectionNegative()` and `normalize()` in DA that does the
normalization, and clients can query DA to do normalization if needed.

A pass option `<normalized-results>` is added to DependenceAnalysisPrinterPass,
and we leverage it to update DA test cases to make sure of test coverage. The
test cases added in `Banerjee.ll` shows that negative vectors are normalized
with `print<da><normalized-results>`.

Reviewed By: bmahjour, Meinersbur, #loopoptwg

Differential Revision: https://reviews.llvm.org/D130188
llvm/include/llvm/Analysis/DependenceAnalysis.h
llvm/lib/Analysis/DependenceAnalysis.cpp
llvm/lib/Passes/PassBuilder.cpp
llvm/lib/Passes/PassRegistry.def
llvm/test/Analysis/DependenceAnalysis/Banerjee.ll