InstCombine: Don't miscompile X % ((Pow2 << A) >>u B)

We assumed that A must be greater than B because the right hand side of
a remainder operator must be nonzero.

However, it is possible for A to be less than B if Pow2 is a power of
two greater than 1.

Take for example:
i32 %A = 0
i32 %B = 31
i32 Pow2 = 2147483648

((Pow2 << 0) >>u 31) is non-zero but A is less than B.

This fixes PR21274.

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

diff --git a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
index 530a66dab9c1a8e807d35ff050049fa1c91c5eb5..8c48dce81de71f446f3a62152bcf2f1dbf731a26 100644 (file)
--- a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
+++ b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
@@ -36,14 +36,11 @@ static Value *simplifyValueKnownNonZero(Value *V, InstCombiner &IC,
 
   // ((1 << A) >>u B) --> (1 << (A-B))
   // Because V cannot be zero, we know that B is less than A.
 
   // ((1 << A) >>u B) --> (1 << (A-B))
   // Because V cannot be zero, we know that B is less than A.

-  Value *A = nullptr, *B = nullptr, *PowerOf2 = nullptr;
-  if (match(V, m_LShr(m_OneUse(m_Shl(m_Value(PowerOf2), m_Value(A))),
-                      m_Value(B))) &&
-      // The "1" can be any value known to be a power of 2.
-      isKnownToBeAPowerOfTwo(PowerOf2, false, 0, IC.getAssumptionTracker(),
-                             CxtI, IC.getDominatorTree())) {
+  Value *A = nullptr, *B = nullptr, *One = nullptr;
+  if (match(V, m_LShr(m_OneUse(m_Shl(m_Value(One), m_Value(A))), m_Value(B))) &&
+      match(One, m_One())) {

     A = IC.Builder->CreateSub(A, B);
     A = IC.Builder->CreateSub(A, B);

-    return IC.Builder->CreateShl(PowerOf2, A);
+    return IC.Builder->CreateShl(One, A);

   }
 
   // (PowerOfTwo >>u B) --> isExact since shifting out the result would make it
   }
 
   // (PowerOfTwo >>u B) --> isExact since shifting out the result would make it

diff --git a/test/Transforms/InstCombine/div.ll b/test/Transforms/InstCombine/div.ll
index f2a70fd0f0d94c68b9c3bd91c8aa5d2e72fc095b..284104317d444e572fce76deef8d615352f72c78 100644 (file)
--- a/test/Transforms/InstCombine/div.ll
+++ b/test/Transforms/InstCombine/div.ll
@@ -265,7 +265,7 @@ define i32 @test30(i32 %a) {
 ; CHECK-NEXT: ret i32 %a
 }
 
 ; CHECK-NEXT: ret i32 %a
 }
 

-define <2 x i32> @test31(<2 x i32> %x) nounwind {
+define <2 x i32> @test31(<2 x i32> %x) {

   %shr = lshr <2 x i32> %x, <i32 31, i32 31>
   %div = udiv <2 x i32> %shr, <i32 2147483647, i32 2147483647>
   ret <2 x i32> %div
   %shr = lshr <2 x i32> %x, <i32 31, i32 31>
   %div = udiv <2 x i32> %shr, <i32 2147483647, i32 2147483647>
   ret <2 x i32> %div


@@ -274,3 +274,15 @@ define <2 x i32> @test31(<2 x i32> %x) nounwind {
 ; CHECK-NEXT: udiv <2 x i32> %[[shr]], <i32 2147483647, i32 2147483647>
 ; CHECK-NEXT: ret <2 x i32>
 }
 ; CHECK-NEXT: udiv <2 x i32> %[[shr]], <i32 2147483647, i32 2147483647>
 ; CHECK-NEXT: ret <2 x i32>
 }

+
+define i32 @test32(i32 %a, i32 %b) {
+  %shl = shl i32 2, %b
+  %div = lshr i32 %shl, 2
+  %div2 = udiv i32 %a, %div
+  ret i32 %div2
+; CHECK-LABEL: @test32(
+; CHECK-NEXT: %[[shl:.*]] = shl i32 2, %b
+; CHECK-NEXT: %[[shr:.*]] = lshr i32 %[[shl]], 2
+; CHECK-NEXT: %[[div:.*]] = udiv i32 %a, %[[shr]]
+; CHECK-NEXT: ret i32
+}