[Dependence Analysis] Fix ExactSIV producing wrong analysis

[artemrad]

Summary

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.

[artemrad]

Fixed clang-format issues

[Meinersbur]

This change reverses almost all directions in the test cases. Was the implementation that terribly wrong?

Not having studies the used algorithms myself, I assumed the DA result to be correct and when using it as analysis assumed that flow [<] and anti [>] are anti-dependences (WAR).

llvm/lib/Analysis/DependenceAnalysis.cpp

1968–1970

[style] Don’t Use Braces on Simple Single-Statement Bodies of if/else/loop Statements

[artemrad]

In D100331#2696167, @Meinersbur wrote:

This change reverses almost all directions in the test cases. Was the implementation that terribly wrong?

Not having studies the used algorithms myself, I assumed the DA result to be correct and when using it as analysis assumed that flow [<] and anti [>] are anti-dependences (WAR).

Hi Michael,

Was the implementation that terribly wrong?

No, but there is a pretty bad bug.

As for the assumption it is incorrect. In literature, when talking about two statements src and dst, [<] indicates src occurs before dst, and [>] indicates dst occurs before src. Which further implies the following statements:
• flow [<] is RAW
• anti [>] is RAW
• flow [>] is WAR
• anti [<] is WAR
This is corroborated by https://dl.acm.org/doi/pdf/10.1145/113446.113448 (see section 1.3)

Now this is also not just a case of LLVM differing from the academic community in its definitions. Let me demonstrate:

1. In the first test of StrongSIV.ll (Note: I did not modify this test)

	;;  for (int i = 0; i < n; i++) {
	;;    A[i + 2] = i;
	;;    *B++ = A[i];

We get the following result from DA:

	Src:  store i32 %1, i32* %arrayidx, align 4 --> Dst:  %2 = load i32, i32* %arrayidx3, align 4
	  da analyze - consistent flow [2]!

Which shows that (+) positive distance in LLVM means src happens before dst

2. From the following lines in DependenceAnalysis.cpp

	    if (Distance.sgt(0))
	      Result.DV[Level].Direction &= Dependence::DVEntry::LT;
	    else if (Distance.slt(0))
	      Result.DV[Level].Direction &= Dependence::DVEntry::GT;
	    else
	      Result.DV[Level].Direction &= Dependence::DVEntry::EQ;

We see that DA establishes the following relationship positive values -> [<], and negative values -> [>]. Combining this with (1), we see that LLVM's definition aligns with the literature's definition.

3. Now let's take a look at one of the lit tests that were modified by my change, say exact3 from ExactSIV.ll

	;;  for (long unsigned i = 0; i <= 10; i++) {
	;;    A[6*i] = i;
	;;    *B++ = A[i + 60];
	
	Src:  store i32 %conv, i32* %arrayidx, align 4 --> Dst:  %0 = load i32, i32* %arrayidx1, align 4
	  da analyze - flow [>]!

Here we can clearly see that the load in dst (i=0) comes before the store in src(i=10), hence [>].

Hopefully this shows that there is a bug in Dependence Analysis.

[bmahjour]

Most of the changes in DA results look good to me, except a few I've noted. Perhaps those can be improved in the future, since this patch is making an improvement overall.

llvm/test/Analysis/DependenceAnalysis/Coupled.ll

253

this one was wrong before, and is still wrong but in a different way....same thing with couple14.

llvm/test/Analysis/DependenceAnalysis/ExactSIV.ll

19

The <= part is correct, but I'm not sure about the |< part. The dependence is loop carried for the most part (except when i = 9). I think this might be because we treat the existence of an EQ as signifying loop independent dependence, which should probably be reconsidered in a separate patch.

[Meinersbur]

Than you for pointing this out. It would explain my confusion, as I would also would have expected the direction to follow the literature but the tests in ExactSIV.ll seemed to use the opposite direction.

I will need to review the UnrollAndJam legality check again since I may have (helped) writing it using my wrong assumption. Its tests do not fail with this change they might have been corrected by extensive testing.

[artemrad]

Fixed the style comments, and updated the academic reference for the algorithm to more closely match the implementation.

[Meinersbur]

llvm/test/Analysis/DependenceAnalysis/Coupled.ll

253

This is marked as done, but I don't see being it addressed.

llvm/test/Analysis/DependenceAnalysis/ExactSIV.ll

19

This is marked as done, but I don't see being it addressed.

[artemrad]

Sorry @Meinersbur, I responded to the comments but forgot to submit them. I am a new to Phabricator. Here they are now.

llvm/test/Analysis/DependenceAnalysis/Coupled.ll

253

There is only one index in which we are accessing the same memory location i=3, so the [=] is correct.

As for the |<, please see my response to your other comment.

llvm/test/Analysis/DependenceAnalysis/ExactSIV.ll

19

You are correct, that is exactly the reason for |<. I have another patch down the line to fix this confusing notation.

[Meinersbur]

I am approving this patch seeing that it is a significant improvement.

For exact0, you both seem to agree that it should be handled in a separate patch.

llvm/test/Analysis/DependenceAnalysis/Coupled.ll

554

Looks correct. Only intersection of accessed elements is when 3*i-18 = 18-i = i, which solves to i = 9.

llvm/test/Analysis/DependenceAnalysis/ExactSIV.ll

19

|< is printed when isLoopIndependent() returns true. If "loop independent" means the absence of loop-carried dependences, then |< is wrong; i=5..8 are loop-carried.

What is your improved notation?

llvm/lib/Analysis/DependenceAnalysis.cpp

static bool findGCD(unsigned Bits, const APInt &AM, const APInt &BM,
   APInt G0 = AM.abs();
   APInt G1 = BM.abs();
   APInt Q = G0; // these need to be initialized
   APInt R = G0;
   APInt::sdivrem(G0, G1, Q, R);
   while (R != 0) {
     APInt A2 = A0 - Q*A1; A0 = A1; A1 = A2;
     APInt B2 = B0 - Q*B1; B0 = B1; B1 = B2;
-    G0 = G1; G1 = R;
+    G0 = G1; G1 = R; // R = G0 - QG1 
     APInt::sdivrem(G0, G1, Q, R);
   }
   G = G1;
   LLVM_DEBUG(dbgs() << "\t    GCD = " << G << "\n");
   X = AM.slt(0) ? -A1 : A1;
   Y = BM.slt(0) ? B1 : -B1;
 
   // make sure gcd divides Delta
   R = Delta.srem(G);
   if (R != 0)
     return true; // gcd doesn't divide Delta, no dependence
   Q = Delta.sdiv(G);
-  X *= Q;
-  Y *= Q;
   return false;
 }
 
 static APInt floorOfQuotient(const APInt &A, const APInt &B) {
   APInt Q = A; // these need to be initialized
   APInt R = A;
   APInt::sdivrem(A, B, Q, R);
   if (R == 0)

 //        Michael Wolfe
 //        MIT Press, 1989
 //
 // It's slower than the specialized tests (strong SIV, weak-zero SIV, etc),
 // so use them if possible. They're also a bit better with symbolics and,
 // in the case of the strong SIV test, can compute Distances.
 //
 // Return true if dependence disproved.
+//
+// This is a modified version of the original Banerjee algorithm. The original
+// only tested whether Dst depends on Src. This algorithm extends that and
+// returns all the dependencies that exist between Dst and Src.
 bool DependenceInfo::exactSIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff,
                                   const SCEV *SrcConst, const SCEV *DstConst,
                                   const Loop *CurLoop, unsigned Level,
                                   FullDependence &Result,
                                   Constraint &NewConstraint) const {
   LLVM_DEBUG(dbgs() << "\tExact SIV test\n");
   LLVM_DEBUG(dbgs() << "\t    SrcCoeff = " << *SrcCoeff << " = AM\n");
   LLVM_DEBUG(dbgs() << "\t    DstCoeff = " << *DstCoeff << " = BM\n");
   LLVM_DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst << "\n");
   LLVM_DEBUG(dbgs() << "\t    DstConst = " << *DstConst << "\n");
   ++ExactSIVapplications;
   assert(0 < Level && Level <= CommonLevels && "Level out of range");
   Level--;
   Result.Consistent = false;
   const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
   LLVM_DEBUG(dbgs() << "\t    Delta = " << *Delta << "\n");
-  NewConstraint.setLine(SrcCoeff, SE->getNegativeSCEV(DstCoeff),
-                        Delta, CurLoop);
+  NewConstraint.setLine(SrcCoeff, SE->getNegativeSCEV(DstCoeff), Delta,
+                        CurLoop);
   const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);
   const SCEVConstant *ConstSrcCoeff = dyn_cast<SCEVConstant>(SrcCoeff);
   const SCEVConstant *ConstDstCoeff = dyn_cast<SCEVConstant>(DstCoeff);
   if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff)
     return false;
 
   // find gcd
   APInt G, X, Y;
   APInt AM = ConstSrcCoeff->getAPInt();
   APInt BM = ConstDstCoeff->getAPInt();
+  APInt CM = ConstDelta->getAPInt();
   unsigned Bits = AM.getBitWidth();
-  if (findGCD(Bits, AM, BM, ConstDelta->getAPInt(), G, X, Y)) {
+  if (findGCD(Bits, AM, BM, CM, G, X, Y)) {
     // gcd doesn't divide Delta, no dependence
     ++ExactSIVindependence;
     ++ExactSIVsuccesses;
     return true;
   }
 
   LLVM_DEBUG(dbgs() << "\t    X = " << X << ", Y = " << Y << "\n");
 
   // since SCEV construction normalizes, LM = 0
   APInt UM(Bits, 1, true);
-  bool UMvalid = false;
+  bool UMValid = false;
   // UM is perhaps unavailable, let's check
   if (const SCEVConstant *CUB =
           collectConstantUpperBound(CurLoop, Delta->getType())) {
     UM = CUB->getAPInt();
     LLVM_DEBUG(dbgs() << "\t    UM = " << UM << "\n");
-    UMvalid = true;
+    UMValid = true;
   }
 
   APInt TU(APInt::getSignedMaxValue(Bits));
   APInt TL(APInt::getSignedMinValue(Bits));
-
-  // test(BM/G, LM-X) and test(-BM/G, X-UM)
-  APInt TMUL = BM.sdiv(G);
-  if (TMUL.sgt(0)) {
-    TL = APIntOps::smax(TL, ceilingOfQuotient(-X, TMUL));
-    LLVM_DEBUG(dbgs() << "\t    TL = " << TL << "\n");
-    if (UMvalid) {
-      TU = APIntOps::smin(TU, floorOfQuotient(UM - X, TMUL));
-      LLVM_DEBUG(dbgs() << "\t    TU = " << TU << "\n");
-    }
+  APInt TC = CM.sdiv(G);
+  APInt TX = X * TC;
+  APInt TY = Y * TC;
+  LLVM_DEBUG(dbgs() << "\t    TC = " << TC << "\n");
+  LLVM_DEBUG(dbgs() << "\t    TX = " << TX << "\n");
+  LLVM_DEBUG(dbgs() << "\t    TY = " << TY << "\n");
+
+  SmallVector<APInt, 2> TLVec, TUVec;
+  APInt TB = BM.sdiv(G);
+  if (TB.sgt(0)) {
+    TLVec.push_back(ceilingOfQuotient(-TX, TB));
+    LLVM_DEBUG(dbgs() << "\t    Possible TL = " << TLVec.back() << "\n");
+    // New bound check - modification to Banerjee's e3 check
+    if (UMValid) {
+      TUVec.push_back(floorOfQuotient(UM - TX, TB));
+      LLVM_DEBUG(dbgs() << "\t    Possible TU = " << TUVec.back() << "\n");
+    }
+  } else {
+    TUVec.push_back(floorOfQuotient(-TX, TB));
+    LLVM_DEBUG(dbgs() << "\t    Possible TU = " << TUVec.back() << "\n");
+    // New bound check - modification to Banerjee's e3 check
+    if (UMValid) {
+      TLVec.push_back(ceilingOfQuotient(UM - TX, TB));
+      LLVM_DEBUG(dbgs() << "\t    Possible TL = " << TLVec.back() << "\n");
     }
-  else {
-    TU = APIntOps::smin(TU, floorOfQuotient(-X, TMUL));
-    LLVM_DEBUG(dbgs() << "\t    TU = " << TU << "\n");
-    if (UMvalid) {
-      TL = APIntOps::smax(TL, ceilingOfQuotient(UM - X, TMUL));
-      LLVM_DEBUG(dbgs() << "\t    TL = " << TL << "\n");
-    }
+
+  APInt TA = AM.sdiv(G);
+  if (TA.sgt(0)) {
+    if (UMValid) {
+      TUVec.push_back(floorOfQuotient(UM - TY, TA));
+      LLVM_DEBUG(dbgs() << "\t    Possible TU = " << TUVec.back() << "\n");
+    }
+    // New bound check - modification to Banerjee's e3 check
+    TLVec.push_back(ceilingOfQuotient(-TY, TA));
+    LLVM_DEBUG(dbgs() << "\t    Possible TL = " << TLVec.back() << "\n");
+  } else {
+    if (UMValid) {
+      TLVec.push_back(ceilingOfQuotient(UM - TY, TA));
+      LLVM_DEBUG(dbgs() << "\t    Possible TL = " << TLVec.back() << "\n");
+    }
+    // New bound check - modification to Banerjee's e3 check
+    TUVec.push_back(floorOfQuotient(-TY, TA));
+    LLVM_DEBUG(dbgs() << "\t    Possible TU = " << TUVec.back() << "\n");
   }
 
-  // test(AM/G, LM-Y) and test(-AM/G, Y-UM)
-  TMUL = AM.sdiv(G);
-  if (TMUL.sgt(0)) {
-    TL = APIntOps::smax(TL, ceilingOfQuotient(-Y, TMUL));
-    LLVM_DEBUG(dbgs() << "\t    TL = " << TL << "\n");
-    if (UMvalid) {
-      TU = APIntOps::smin(TU, floorOfQuotient(UM - Y, TMUL));
-      LLVM_DEBUG(dbgs() << "\t    TU = " << TU << "\n");
-    }
-  }
-  else {
-    TU = APIntOps::smin(TU, floorOfQuotient(-Y, TMUL));
-    LLVM_DEBUG(dbgs() << "\t    TU = " << TU << "\n");
-    if (UMvalid) {
-      TL = APIntOps::smax(TL, ceilingOfQuotient(UM - Y, TMUL));
-      LLVM_DEBUG(dbgs() << "\t    TL = " << TL << "\n");
-    }
-  }
+  LLVM_DEBUG(dbgs() << "\t    TA = " << TA << "\n");
+  LLVM_DEBUG(dbgs() << "\t    TB = " << TB << "\n");
+
+  if (TLVec.empty() || TUVec.empty())
+    return false;
+  TL = APIntOps::smax(TLVec.front(), TLVec.back());
+  TU = APIntOps::smin(TUVec.front(), TUVec.back());
+
   if (TL.sgt(TU)) {
     ++ExactSIVindependence;
     ++ExactSIVsuccesses;
     return true;
   }
 
   // explore directions
   unsigned NewDirection = Dependence::DVEntry::NONE;
-
-  // less than
-  APInt SaveTU(TU); // save these
-  APInt SaveTL(TL);
-  LLVM_DEBUG(dbgs() << "\t    exploring LT direction\n");
-  TMUL = AM - BM;
-  if (TMUL.sgt(0)) {
-    TL = APIntOps::smax(TL, ceilingOfQuotient(X - Y + 1, TMUL));
-    LLVM_DEBUG(dbgs() << "\t\t    TL = " << TL << "\n");
-  }
-  else {
-    TU = APIntOps::smin(TU, floorOfQuotient(X - Y + 1, TMUL));
-    LLVM_DEBUG(dbgs() << "\t\t    TU = " << TU << "\n");
-  }
-  if (TL.sle(TU)) {
-    NewDirection |= Dependence::DVEntry::LT;
-    ++ExactSIVsuccesses;
+  APInt LowerDistance, UpperDistance;
+  if (TA.sgt(TB)) {
+    LowerDistance = (TY - TX) + (TA - TB) * TL;
+    UpperDistance = (TY - TX) + (TA - TB) * TU;
+  } else {
+    LowerDistance = (TY - TX) + (TA - TB) * TU;
+    UpperDistance = (TY - TX) + (TA - TB) * TL;
   }
 
-  // equal
-  TU = SaveTU; // restore
-  TL = SaveTL;
-  LLVM_DEBUG(dbgs() << "\t    exploring EQ direction\n");
-  if (TMUL.sgt(0)) {
-    TL = APIntOps::smax(TL, ceilingOfQuotient(X - Y, TMUL));
-    LLVM_DEBUG(dbgs() << "\t\t    TL = " << TL << "\n");
-  }
-  else {
-    TU = APIntOps::smin(TU, floorOfQuotient(X - Y, TMUL));
-    LLVM_DEBUG(dbgs() << "\t\t    TU = " << TU << "\n");
-  }
-  TMUL = BM - AM;
-  if (TMUL.sgt(0)) {
-    TL = APIntOps::smax(TL, ceilingOfQuotient(Y - X, TMUL));
-    LLVM_DEBUG(dbgs() << "\t\t    TL = " << TL << "\n");
-  }
-  else {
-    TU = APIntOps::smin(TU, floorOfQuotient(Y - X, TMUL));
-    LLVM_DEBUG(dbgs() << "\t\t    TU = " << TU << "\n");
-  }
-  if (TL.sle(TU)) {
+  LLVM_DEBUG(dbgs() << "\t    LowerDistance = " << LowerDistance << "\n");
+  LLVM_DEBUG(dbgs() << "\t    UpperDistance = " << UpperDistance << "\n");
+
+  APInt Zero(Bits, 0, true);
+  if (LowerDistance.sle(Zero) && UpperDistance.sge(Zero)) {
     NewDirection |= Dependence::DVEntry::EQ;
     ++ExactSIVsuccesses;
   }
-
-  // greater than
-  TU = SaveTU; // restore
-  TL = SaveTL;
-  LLVM_DEBUG(dbgs() << "\t    exploring GT direction\n");
-  if (TMUL.sgt(0)) {
-    TL = APIntOps::smax(TL, ceilingOfQuotient(Y - X + 1, TMUL));
-    LLVM_DEBUG(dbgs() << "\t\t    TL = " << TL << "\n");
-  }
-  else {
-    TU = APIntOps::smin(TU, floorOfQuotient(Y - X + 1, TMUL));
-    LLVM_DEBUG(dbgs() << "\t\t    TU = " << TU << "\n");
-  }
-  if (TL.sle(TU)) {
+  if (LowerDistance.slt(0)) {
     NewDirection |= Dependence::DVEntry::GT;
     ++ExactSIVsuccesses;
   }
+  if (UpperDistance.sgt(0)) {
+    NewDirection |= Dependence::DVEntry::LT;
+    ++ExactSIVsuccesses;
+  }
 
   // finished
   Result.DV[Level].Direction &= NewDirection;
   if (Result.DV[Level].Direction == Dependence::DVEntry::NONE)
     ++ExactSIVindependence;
+  LLVM_DEBUG(dbgs() << "\t    Result = ");
+  LLVM_DEBUG(Result.dump(dbgs()));
   return Result.DV[Level].Direction == Dependence::DVEntry::NONE;
 }
 
 
-
 // Return true if the divisor evenly divides the dividend.
 static
 bool isRemainderZero(const SCEVConstant *Dividend,
                      const SCEVConstant *Divisor) {
   const APInt &ConstDividend = Dividend->getAPInt();
   const APInt &ConstDivisor = Divisor->getAPInt();
   return ConstDividend.srem(ConstDivisor) == 0;
 }
if (isa<SCEVConstant>(Delta) &&
       !isRemainderZero(cast<SCEVConstant>(Delta), ConstCoeff)) {
     ++WeakZeroSIVindependence;
     ++WeakZeroSIVsuccesses;
     return true;
   }
   return false;
 }
 
 
 // exactRDIVtest - Tests the RDIV subscript pair for dependence.
 // Things of the form [c1 + a*i] and [c2 + b*j],
 // where i and j are induction variable, c1 and c2 are loop invariant,
 // and a and b are constants.
 // Returns true if any possible dependence is disproved.
 // Marks the result as inconsistent.
 // Works in some cases that symbolicRDIVtest doesn't, and vice versa.
+//
 bool DependenceInfo::exactRDIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff,
                                    const SCEV *SrcConst, const SCEV *DstConst,
                                    const Loop *SrcLoop, const Loop *DstLoop,
                                    FullDependence &Result) const {
   LLVM_DEBUG(dbgs() << "\tExact RDIV test\n");
   LLVM_DEBUG(dbgs() << "\t    SrcCoeff = " << *SrcCoeff << " = AM\n");
   LLVM_DEBUG(dbgs() << "\t    DstCoeff = " << *DstCoeff << " = BM\n");
   LLVM_DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst << "\n");
   LLVM_DEBUG(dbgs() << "\t    DstConst = " << *DstConst << "\n");
   ++ExactRDIVapplications;
   Result.Consistent = false;
   const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
   LLVM_DEBUG(dbgs() << "\t    Delta = " << *Delta << "\n");
   const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);
   const SCEVConstant *ConstSrcCoeff = dyn_cast<SCEVConstant>(SrcCoeff);
   const SCEVConstant *ConstDstCoeff = dyn_cast<SCEVConstant>(DstCoeff);
   if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff)
     return false;
 
   // find gcd
   APInt G, X, Y;
   APInt AM = ConstSrcCoeff->getAPInt();
   APInt BM = ConstDstCoeff->getAPInt();
+  APInt CM = ConstDelta->getAPInt();
   unsigned Bits = AM.getBitWidth();
-  if (findGCD(Bits, AM, BM, ConstDelta->getAPInt(), G, X, Y)) {
+  if (findGCD(Bits, AM, BM, CM, G, X, Y)) {
     // gcd doesn't divide Delta, no dependence
     ++ExactRDIVindependence;
     return true;
   }
 
   LLVM_DEBUG(dbgs() << "\t    X = " << X << ", Y = " << Y << "\n");
 
   // since SCEV construction seems to normalize, LM = 0
   APInt SrcUM(Bits, 1, true);
   bool SrcUMvalid = false;
   // SrcUM is perhaps unavailable, let's check
   if (const SCEVConstant *UpperBound =
           collectConstantUpperBound(SrcLoop, Delta->getType())) {
     SrcUM = UpperBound->getAPInt();
     LLVM_DEBUG(dbgs() << "\t    SrcUM = " << SrcUM << "\n");
     SrcUMvalid = true;
   }
 
   APInt DstUM(Bits, 1, true);
   bool DstUMvalid = false;
   // UM is perhaps unavailable, let's check
   if (const SCEVConstant *UpperBound =
           collectConstantUpperBound(DstLoop, Delta->getType())) {
     DstUM = UpperBound->getAPInt();
     LLVM_DEBUG(dbgs() << "\t    DstUM = " << DstUM << "\n");
     DstUMvalid = true;
   }
 
   APInt TU(APInt::getSignedMaxValue(Bits));
   APInt TL(APInt::getSignedMinValue(Bits));
-
-  // test(BM/G, LM-X) and test(-BM/G, X-UM)
-  APInt TMUL = BM.sdiv(G);
-  if (TMUL.sgt(0)) {
-    TL = APIntOps::smax(TL, ceilingOfQuotient(-X, TMUL));
-    LLVM_DEBUG(dbgs() << "\t    TL = " << TL << "\n");
+  APInt TC = CM.sdiv(G);
+  APInt TX = X * TC;
+  APInt TY = Y * TC;
+  LLVM_DEBUG(dbgs() << "\t    TC = " << TC << "\n");
+  LLVM_DEBUG(dbgs() << "\t    TX = " << TX << "\n");
+  LLVM_DEBUG(dbgs() << "\t    TY = " << TY << "\n");
+
+  SmallVector<APInt, 2> TLVec, TUVec;
+  APInt TB = BM.sdiv(G);
+  if (TB.sgt(0)) {
+    TLVec.push_back(ceilingOfQuotient(-TX, TB));
+    LLVM_DEBUG(dbgs() << "\t    Possible TL = " << TLVec.back() << "\n");
     if (SrcUMvalid) {
-      TU = APIntOps::smin(TU, floorOfQuotient(SrcUM - X, TMUL));
-      LLVM_DEBUG(dbgs() << "\t    TU = " << TU << "\n");
-    }
+      TUVec.push_back(floorOfQuotient(SrcUM - TX, TB));
+      LLVM_DEBUG(dbgs() << "\t    Possible TU = " << TUVec.back() << "\n");
     }
-  else {
-    TU = APIntOps::smin(TU, floorOfQuotient(-X, TMUL));
-    LLVM_DEBUG(dbgs() << "\t    TU = " << TU << "\n");
+  } else {
+    TUVec.push_back(floorOfQuotient(-TX, TB));
+    LLVM_DEBUG(dbgs() << "\t    Possible TU = " << TUVec.back() << "\n");
     if (SrcUMvalid) {
-      TL = APIntOps::smax(TL, ceilingOfQuotient(SrcUM - X, TMUL));
-      LLVM_DEBUG(dbgs() << "\t    TL = " << TL << "\n");
+      TLVec.push_back(ceilingOfQuotient(SrcUM - TX, TB));
+      LLVM_DEBUG(dbgs() << "\t    Possible TL = " << TLVec.back() << "\n");
     }
   }
 
-  // test(AM/G, LM-Y) and test(-AM/G, Y-UM)
-  TMUL = AM.sdiv(G);
-  if (TMUL.sgt(0)) {
-    TL = APIntOps::smax(TL, ceilingOfQuotient(-Y, TMUL));
-    LLVM_DEBUG(dbgs() << "\t    TL = " << TL << "\n");
+  APInt TA = AM.sdiv(G);
+  if (TA.sgt(0)) {
+    TLVec.push_back(ceilingOfQuotient(-TY, TA));
+    LLVM_DEBUG(dbgs() << "\t    Possible TL = " << TLVec.back() << "\n");
     if (DstUMvalid) {
-      TU = APIntOps::smin(TU, floorOfQuotient(DstUM - Y, TMUL));
-      LLVM_DEBUG(dbgs() << "\t    TU = " << TU << "\n");
-    }
+      TUVec.push_back(floorOfQuotient(DstUM - TY, TA));
+      LLVM_DEBUG(dbgs() << "\t    Possible TU = " << TUVec.back() << "\n");
     }
-  else {
-    TU = APIntOps::smin(TU, floorOfQuotient(-Y, TMUL));
-    LLVM_DEBUG(dbgs() << "\t    TU = " << TU << "\n");
+  } else {
+    TUVec.push_back(floorOfQuotient(-TY, TA));
+    LLVM_DEBUG(dbgs() << "\t    Possible TU = " << TUVec.back() << "\n");
     if (DstUMvalid) {
-      TL = APIntOps::smax(TL, ceilingOfQuotient(DstUM - Y, TMUL));
-      LLVM_DEBUG(dbgs() << "\t    TL = " << TL << "\n");
+      TLVec.push_back(ceilingOfQuotient(DstUM - TY, TA));
+      LLVM_DEBUG(dbgs() << "\t    Possible TL = " << TLVec.back() << "\n");
     }
   }
+
+  if (TLVec.empty() || TUVec.empty()) {
+    return false;
+  }
+
+  LLVM_DEBUG(dbgs() << "\t    TA = " << TA << "\n");
+  LLVM_DEBUG(dbgs() << "\t    TB = " << TB << "\n");
+
+  TL = APIntOps::smax(TLVec.front(), TLVec.back());
+  TU = APIntOps::smin(TUVec.front(), TUVec.back());
+  LLVM_DEBUG(dbgs() << "\t    TL = " << TL << "\n");
+  LLVM_DEBUG(dbgs() << "\t    TU = " << TU << "\n");
+
   if (TL.sgt(TU))
     ++ExactRDIVindependence;
   return TL.sgt(TU);
 }
 
 
 // symbolicRDIVtest -
 // In Section 4.5 of the Practical Dependence Testing paper,the authors

llvm/test/Analysis/DependenceAnalysis/Coupled.ll

 ;;    *B++ = A[i][i];
 
 define void @couple2([100 x i32]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
 entry:
   br label %for.body
 
 ; CHECK-LABEL: couple2
 ; CHECK: da analyze - none!
-; CHECK: da analyze - flow [<]!
+; CHECK: da analyze - flow [*|<]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.body:                                         ; preds = %entry, %for.body
   %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
   %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]

 ;;    *B++ = A[i][i];
 
 define void @couple6([100 x i32]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
 entry:
   br label %for.body
 
 ; CHECK-LABEL: couple6
 ; CHECK: da analyze - none!
-; CHECK: da analyze - flow [<]!
+; CHECK: da analyze - flow [=|<]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.body:                                         ; preds = %entry, %for.body
   %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
   %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]

 ;;    *B++ = A[i][i];
 
 define void @couple11([100 x i32]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
 entry:
   br label %for.body
 
 ; CHECK-LABEL: couple11
 ; CHECK: da analyze - none!
-; CHECK: da analyze - flow [>]!
+; CHECK: da analyze - flow [=|<]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.body:                                         ; preds = %entry, %for.body
   %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
   %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]

 ;;    *B++ = A[i][i];
 
 define void @couple12([100 x i32]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
 entry:
   br label %for.body
 
 ; CHECK-LABEL: couple12
 ; CHECK: da analyze - none!
-; CHECK: da analyze - flow [>]!
+; CHECK: da analyze - flow [<]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.body:                                         ; preds = %entry, %for.body
   %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
   %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]

 ;;    *B++ = A[i][i][i];
 
 define void @couple14([100 x [100 x i32]]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
 entry:
   br label %for.body
 
 ; CHECK-LABEL: couple14
 ; CHECK: da analyze - none!
-; CHECK: da analyze - flow [<]!
+; CHECK: da analyze - flow [=|<]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.body:                                         ; preds = %entry, %for.body
   %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
   %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]

llvm/test/Analysis/DependenceAnalysis/ExactSIV.ll

 ;;    *B++ = A[2*i + 1];
 
 define void @exact0(i32* %A, i32* %B) nounwind uwtable ssp {
 entry:
   br label %for.body
 
 ; CHECK-LABEL: exact0
 ; CHECK: da analyze - none!
-; CHECK: da analyze - flow [>]!
+; CHECK: da analyze - flow [<=|<]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.body:                                         ; preds = %entry, %for.body
   %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
   %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]

 ;;    *B++ = A[i + 60];
 
 define void @exact3(i32* %A, i32* %B) nounwind uwtable ssp {
 entry:
   br label %for.body
 
 ; CHECK-LABEL: exact3
 ; CHECK: da analyze - none!
-; CHECK: da analyze - flow [<]!
+; CHECK: da analyze - flow [>]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.body:                                         ; preds = %entry, %for.body
   %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
   %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]

 ;;    *B++ = A[i + 60];
 
 define void @exact4(i32* %A, i32* %B) nounwind uwtable ssp {
 entry:
   br label %for.body
 
 ; CHECK-LABEL: exact4
 ; CHECK: da analyze - none!
-; CHECK: da analyze - flow [<]!
+; CHECK: da analyze - flow [>]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.body:                                         ; preds = %entry, %for.body
   %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
   %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]

 ;;    *B++ = A[i + 60];
 
 define void @exact5(i32* %A, i32* %B) nounwind uwtable ssp {
 entry:
   br label %for.body
 
 ; CHECK-LABEL: exact5
 ; CHECK: da analyze - none!
-; CHECK: da analyze - flow [<]!
+; CHECK: da analyze - flow [=>|<]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.body:                                         ; preds = %entry, %for.body
   %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
   %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]

 ;;    *B++ = A[i + 60];
 
 define void @exact6(i32* %A, i32* %B) nounwind uwtable ssp {
 entry:
   br label %for.body
 
 ; CHECK-LABEL: exact6
 ; CHECK: da analyze - none!
-; CHECK: da analyze - flow [<]!
+; CHECK: da analyze - flow [=>|<]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.body:                                         ; preds = %entry, %for.body
   %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
   %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]

 ;;    *B++ = A[i + 60];
 
 define void @exact7(i32* %A, i32* %B) nounwind uwtable ssp {
 entry:
   br label %for.body
 
 ; CHECK-LABEL: exact7
 ; CHECK: da analyze - none!
-; CHECK: da analyze - flow [<]!
+; CHECK: da analyze - flow [*|<]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.body:                                         ; preds = %entry, %for.body
   %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
   %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]

 ;;    *B++ = A[-i - 60];
 
 define void @exact9(i32* %A, i32* %B) nounwind uwtable ssp {
 entry:
   br label %for.body
 
 ; CHECK-LABEL: exact9
 ; CHECK: da analyze - none!
-; CHECK: da analyze - flow [<]!
+; CHECK: da analyze - flow [>]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.body:                                         ; preds = %entry, %for.body
   %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
   %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]

 ;;    *B++ = A[-i - 60];
 
 define void @exact10(i32* %A, i32* %B) nounwind uwtable ssp {
 entry:
   br label %for.body
 
 ; CHECK-LABEL: exact10
 ; CHECK: da analyze - none!
-; CHECK: da analyze - flow [<]!
+; CHECK: da analyze - flow [>]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.body:                                         ; preds = %entry, %for.body
   %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
   %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]

 ;;    *B++ = A[-i - 60];
 
 define void @exact11(i32* %A, i32* %B) nounwind uwtable ssp {
 entry:
   br label %for.body
 
 ; CHECK-LABEL: exact11
 ; CHECK: da analyze - none!
-; CHECK: da analyze - flow [<]!
+; CHECK: da analyze - flow [=>|<]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.body:                                         ; preds = %entry, %for.body
   %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
   %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]

 ;;    *B++ = A[-i - 60];
 
 define void @exact12(i32* %A, i32* %B) nounwind uwtable ssp {
 entry:
   br label %for.body
 
 ; CHECK-LABEL: exact12
 ; CHECK: da analyze - none!
-; CHECK: da analyze - flow [<]!
+; CHECK: da analyze - flow [=>|<]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.body:                                         ; preds = %entry, %for.body
   %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
   %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]

 ;;    *B++ = A[-i - 60];
 
 define void @exact13(i32* %A, i32* %B) nounwind uwtable ssp {
 entry:
   br label %for.body
 
 ; CHECK-LABEL: exact13
 ; CHECK: da analyze - none!
-; CHECK: da analyze - flow [<]!
+; CHECK: da analyze - flow [*|<]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 for.body:                                         ; preds = %entry, %for.body
   %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
   %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]