[Dependence Analysis] Fix ExactSIV producing wrong analysis
authorAndy Kaylor <andrew.kaylor@intel.com>
Tue, 27 Apr 2021 19:15:26 +0000 (12:15 -0700)
committerAndy Kaylor <andrew.kaylor@intel.com>
Tue, 27 Apr 2021 19:24:00 +0000 (12:24 -0700)
commit0a82d885a4fc198395369e9ae75dfe175140df94
tree2da49b7b69c8630d026de238f0e4a89b2bbfb32e
parent12011b5217929ef8a56c2099c6f3233934ea4fbc
[Dependence Analysis] Fix ExactSIV producing wrong analysis

Patch by Artem Radzikhovskyy!

Symptom: ExactSIV test produced incorrect analysis of dependencies see LIT tests
Bug: At the end of the algorithm when determining dependence direction original author forgot to divide intermediate results by gcd and round result toward zero

Although this bug can be fixed with significantly fewer changes I opted to write the code in such a way that reflects the original algorithm that Banerjee proposed, for easier reference in the future. This surprisingly results in shorter code, and fewer quotient and max/min calculations.

Changes Summary:

- fixed findGCD to return valid x and y so that they match the function description where: ax - by = gcd(a,b)
- Fixed ExactSIV test, to produce proper results
- Documented the extension of Banerjee's algorithm that the original code author introduced. Banerjee's original algorithm only tested whether Dst depends on Src, the extension also allows us to test whether Src depends on Dst, in one pass.
- ExactRDIV test worked fine. Since it uses findGCD(), it needed to be updated.Since ExactRDIV test has very few changes from the core algorithm of ExactSIV I modified the test to have consistent format as ExactSIV.
- Updated the LIT tests to be testing for correct values.

Differential Revision: https://reviews.llvm.org/D100331
llvm/lib/Analysis/DependenceAnalysis.cpp
llvm/test/Analysis/DependenceAnalysis/Coupled.ll
llvm/test/Analysis/DependenceAnalysis/ExactSIV.ll