ScalarEvolution: HowFarToZero was wrongly using signed division

HowFarToZero was supposed to use unsigned division in order to calculate
the backedge taken count.  However, SCEVDivision::divide performs signed
division.  Unless I am mistaken, no users of SCEVDivision actually want
signed arithmetic: switch to udiv and urem.

This fixes PR21578.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@222093 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index 55472ecb6671f6b9291749fc053f902219043d74..2026f8aa79cf089b30977444c05c10b1f064b449 100644 (file)
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -675,32 +675,32 @@ static void GroupByComplexity(SmallVectorImpl<const SCEV *> &Ops,
   }
 }
 
-static const APInt srem(const SCEVConstant *C1, const SCEVConstant *C2) {
+static const APInt urem(const SCEVConstant *C1, const SCEVConstant *C2) {
   APInt A = C1->getValue()->getValue();
   APInt B = C2->getValue()->getValue();
   uint32_t ABW = A.getBitWidth();
   uint32_t BBW = B.getBitWidth();
 
   if (ABW > BBW)
-    B = B.sext(ABW);
+    B = B.zext(ABW);
   else if (ABW < BBW)
-    A = A.sext(BBW);
+    A = A.zext(BBW);
 
-  return APIntOps::srem(A, B);
+  return APIntOps::urem(A, B);
 }
 
-static const APInt sdiv(const SCEVConstant *C1, const SCEVConstant *C2) {
+static const APInt udiv(const SCEVConstant *C1, const SCEVConstant *C2) {
   APInt A = C1->getValue()->getValue();
   APInt B = C2->getValue()->getValue();
   uint32_t ABW = A.getBitWidth();
   uint32_t BBW = B.getBitWidth();
 
   if (ABW > BBW)
-    B = B.sext(ABW);
+    B = B.zext(ABW);
   else if (ABW < BBW)
-    A = A.sext(BBW);
+    A = A.zext(BBW);
 
-  return APIntOps::sdiv(A, B);
+  return APIntOps::udiv(A, B);
 }
 
 namespace {
@@ -803,8 +803,8 @@ public:
 
   void visitConstant(const SCEVConstant *Numerator) {
     if (const SCEVConstant *D = dyn_cast<SCEVConstant>(Denominator)) {
-      Quotient = SE.getConstant(sdiv(Numerator, D));
-      Remainder = SE.getConstant(srem(Numerator, D));
+      Quotient = SE.getConstant(udiv(Numerator, D));
+      Remainder = SE.getConstant(urem(Numerator, D));
       return;
     }
   }

diff --git a/test/Analysis/ScalarEvolution/trip-count-pow2.ll b/test/Analysis/ScalarEvolution/trip-count-pow2.ll
index 12d89ae4b6547218af7d7fbf224801e635d33657..2c5b72e49daf485e069ee12fcf59f586070a74a6 100644 (file)
--- a/test/Analysis/ScalarEvolution/trip-count-pow2.ll
+++ b/test/Analysis/ScalarEvolution/trip-count-pow2.ll
@@ -48,6 +48,6 @@ exit:
   ret void
 
 ; CHECK-LABEL: @test3
-; CHECK: Loop %loop: backedge-taken count is ((-96 + (96 * %n)) /u 96)
-; CHECK: Loop %loop: max backedge-taken count is ((-96 + (96 * %n)) /u 96)
+; CHECK: Loop %loop: Unpredictable backedge-taken count.
+; CHECK: Loop %loop: Unpredictable max backedge-taken count.
 }