[InstCombine] Fix InstCombinerImpl::foldICmpMulConstant for nsw and nuw mul with unsigned compare.

[craig.topper]

Summary

If we have both an nsw and nuw flag, we would see the nsw flag
first and only handle signed comparisons.

This patch ignores the nsw flag if the comparison isn't signed.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2083–2084

Does this need an ICmpInst::isUnsigned(Pred) check aswell?

llvm/test/Transforms/InstCombine/icmp-mul.ll

997

imo a few more tests (at least one with unsigned pred).

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2079–2081

I'm not sure this is correct w.o nuw:
nsw only: https://alive2.llvm.org/ce/z/xrrGmG
nsw nuw: https://alive2.llvm.org/ce/z/CCHqJ8

[craig.topper]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2083–2084

I didn't add isUnsigned because the body of else only checks unsigned predicates and leaves NewC null if it doesn't find an unsigned predicate. NewC being null is sufficient to make the function return null.

llvm/test/Transforms/InstCombine/icmp-mul.ll

997

Yes I'm going to find the tests for the unsigned code and see if I can copy them and add an nsw flag to expose the bug.

[craig.topper]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2079–2081

I think you need to correct the result of the sdiv to round down to match the RoundingSDiv call. sdiv rounds towards 0.

https://alive2.llvm.org/ce/z/c2BQVk

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2083–2084

Isn't that also true for the signed case? If so maybe drop that check aswell.

[craig.topper]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2083–2084

It is true, but I need it to still go to the else if the condition isn't signed.

Alternatively, I could remove the else and write.

if (NSW) {
  ....
}

if (!NewC && NUW) {

}

[craig.topper]

-Rebase on new pre-commit with tests.
-Convert else if to an assert since we already checked isSigned.
-Make unsigned code more similar to new signed code.

[craig.topper]

llvm/test/Transforms/InstCombine/icmp-mul.ll

137

Forgot to remove the FIXMEs. Will fix.

[craig.topper]

Update FIXMEs

[craig.topper]

This comment was removed by craig.topper.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2071

is this needed? Seems redundant given the nsw flag.

[craig.topper]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2071

I think this check is protecting the APIntOps::RoundingSDiv call. You can't pass those values to it. I'm not sure the nsw flag matters.

I suspect a signed comparison with INT_MIN on the RHS side would have already been converted to eq/ne compare or true/false before we got here.

[craig.topper]

Ping. This seems like a pretty straightforward bug fix. Is there anything I need to do?

[nikic]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (C.urem(*MulC).isZero()) {
       // (mul X, OddC) eq/ne N * C --> X eq/ne N
       if ((*MulC & 1).isOne() || Mul->hasNoUnsignedWrap()) {
         Constant *NewC = ConstantInt::get(MulTy, C.udiv(*MulC));
         return new ICmpInst(Pred, X, NewC);
       }
     }
   }
 
-  if (!Mul->hasNoSignedWrap() && !Mul->hasNoUnsignedWrap())
-    return nullptr;
-
   // With a matching no-overflow guarantee, fold the constants:
   // (X * MulC) < C --> X < (C / MulC)
   // (X * MulC) > C --> X > (C / MulC)
   // TODO: Assert that Pred is not equal to SGE, SLE, UGE, ULE?
   Constant *NewC = nullptr;
-  if (Mul->hasNoSignedWrap()) {
+  if (Mul->hasNoSignedWrap() && ICmpInst::isSigned(Pred)) {
     // MININT / -1 --> overflow.
     if (C.isMinSignedValue() && MulC->isAllOnes())
       return nullptr;
     if (MulC->isNegative())
       Pred = ICmpInst::getSwappedPredicate(Pred);
 
-    if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGE)
+    if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGE) {
       NewC = ConstantInt::get(
           MulTy, APIntOps::RoundingSDiv(C, *MulC, APInt::Rounding::UP));
-    if (Pred == ICmpInst::ICMP_SLE || Pred == ICmpInst::ICMP_SGT)
+    } else {
+      assert((Pred == ICmpInst::ICMP_SLE || Pred == ICmpInst::ICMP_SGT) &&
+             "Unexpected predicate");
       NewC = ConstantInt::get(
           MulTy, APIntOps::RoundingSDiv(C, *MulC, APInt::Rounding::DOWN));
-  } else {
-    assert(Mul->hasNoUnsignedWrap() && "Expected mul nuw");
-    if (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_UGE)
+    }
+  } else if (Mul->hasNoUnsignedWrap() && ICmpInst::isUnsigned(Pred)) {
+    if (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_UGE) {
       NewC = ConstantInt::get(
           MulTy, APIntOps::RoundingUDiv(C, *MulC, APInt::Rounding::UP));
-    if (Pred == ICmpInst::ICMP_ULE || Pred == ICmpInst::ICMP_UGT)
+    } else {
+      assert((Pred == ICmpInst::ICMP_ULE || Pred == ICmpInst::ICMP_UGT) &&
+             "Unexpected predicate");
       NewC = ConstantInt::get(
           MulTy, APIntOps::RoundingUDiv(C, *MulC, APInt::Rounding::DOWN));
     }
+  }
 
   return NewC ? new ICmpInst(Pred, X, NewC) : nullptr;
 }
 
 /// Fold icmp (shl 1, Y), C.
 static Instruction *foldICmpShlOne(ICmpInst &Cmp, Instruction *Shl,
                                    const APInt &C) {
   Value *Y;

llvm/test/Transforms/InstCombine/icmp-mul.ll

 ; CHECK-NEXT:    ret i1 [[B]]
 ;
   %a = mul nuw i8 %x, 7
   %b = icmp ult i8 %a, 21
   ret i1 %b
 }
 
 ; Same as above, but with nsw flag too.
-; FIXME: This should be optimized like above.
+; This used to not optimize due to nsw being prioritized too much.
 define i1 @ult_rem_zero_nsw(i8 %x) {
 ; CHECK-LABEL: @ult_rem_zero_nsw(
-; CHECK-NEXT:    [[A:%.*]] = mul nuw nsw i8 [[X:%.*]], 7
-; CHECK-NEXT:    [[B:%.*]] = icmp ult i8 [[A]], 21
+; CHECK-NEXT:    [[B:%.*]] = icmp ult i8 [[X:%.*]], 3
 ; CHECK-NEXT:    ret i1 [[B]]
 ;
   %a = mul nuw nsw i8 %x, 7
   %b = icmp ult i8 %a, 21
   ret i1 %b
 }
 
 define i1 @ult_rem_nz(i8 %x) {
 ; CHECK-LABEL: @ult_rem_nz(
 ; CHECK-NEXT:    [[B:%.*]] = icmp ult i8 [[X:%.*]], 5
 ; CHECK-NEXT:    ret i1 [[B]]
 ;
   %a = mul nuw i8 %x, 5
   %b = icmp ult i8 %a, 21
   ret i1 %b
 }
 
 ; Same as above, but with nsw flag too.
-; FIXME: This should be optimized like above.
+; This used to not optimize due to nsw being prioritized too much.
 define i1 @ult_rem_nz_nsw(i8 %x) {
 ; CHECK-LABEL: @ult_rem_nz_nsw(
-; CHECK-NEXT:    [[A:%.*]] = mul nuw nsw i8 [[X:%.*]], 5
-; CHECK-NEXT:    [[B:%.*]] = icmp ult i8 [[A]], 21
+; CHECK-NEXT:    [[B:%.*]] = icmp ult i8 [[X:%.*]], 5
 ; CHECK-NEXT:    ret i1 [[B]]
 ;
   %a = mul nuw nsw i8 %x, 5
   %b = icmp ult i8 %a, 21
   ret i1 %b
 }
 
 ; Tests for sgt/ugt

 ; CHECK-NEXT:    ret i1 [[B]]
 ;
   %a = mul nuw i8 %x, 7
   %b = icmp ugt i8 %a, 21
   ret i1 %b
 }
 
 ; Same as above, but with nsw flag too.
-; FIXME: This should be optimized like above.
+; This used to not optimize due to nsw being prioritized too much.
 define i1 @ugt_rem_zero_nsw(i8 %x) {
 ; CHECK-LABEL: @ugt_rem_zero_nsw(
-; CHECK-NEXT:    [[A:%.*]] = mul nuw nsw i8 [[X:%.*]], 7
-; CHECK-NEXT:    [[B:%.*]] = icmp ugt i8 [[A]], 21
+; CHECK-NEXT:    [[B:%.*]] = icmp ugt i8 [[X:%.*]], 3
 ; CHECK-NEXT:    ret i1 [[B]]
 ;
   %a = mul nuw nsw i8 %x, 7
   %b = icmp ugt i8 %a, 21
   ret i1 %b
 }
 
 define i1 @ugt_rem_nz(i8 %x) {
 ; CHECK-LABEL: @ugt_rem_nz(
 ; CHECK-NEXT:    [[B:%.*]] = icmp ugt i8 [[X:%.*]], 4
 ; CHECK-NEXT:    ret i1 [[B]]
 ;
   %a = mul nuw i8 %x, 5
   %b = icmp ugt i8 %a, 21
   ret i1 %b
 }
 
 ; Same as above, but with nsw flag too.
-; FIXME: This should be optimized like above.
+; This used to not optimize due to nsw being prioritized too much.
 define i1 @ugt_rem_nz_nsw(i8 %x) {
 ; CHECK-LABEL: @ugt_rem_nz_nsw(
-; CHECK-NEXT:    [[A:%.*]] = mul nuw nsw i8 [[X:%.*]], 5
-; CHECK-NEXT:    [[B:%.*]] = icmp ugt i8 [[A]], 21
+; CHECK-NEXT:    [[B:%.*]] = icmp ugt i8 [[X:%.*]], 4
 ; CHECK-NEXT:    ret i1 [[B]]
 ;
   %a = mul nuw nsw i8 %x, 5
   %b = icmp ugt i8 %a, 21
   ret i1 %b
 }
 
 ; Tests for eq/ne
;
   %r = icmp eq i128 %s, 0
   ret i1 %r
 }
 
 ; The 33rd bit can only be set when MSB of x is set.
 
 define i1 @splat_mul_unknown_lz(i32 %x) {
 ; CHECK-LABEL: @splat_mul_unknown_lz(
-; CHECK-NEXT:    [[Z:%.*]] = zext i32 [[X:%.*]] to i128
-; CHECK-NEXT:    [[M:%.*]] = mul nuw nsw i128 [[Z]], 18446744078004518913
-; CHECK-NEXT:    [[R:%.*]] = icmp ult i128 [[M]], 39614081257132168796771975168
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i32 [[X:%.*]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %z = zext i32 %x to i128
   %m = mul i128 %z, 18446744078004518913 ; 0x00000000_00000001_00000001_00000001
   %s = lshr i128 %m, 95
   %r = icmp eq i128 %s, 0
   ret i1 %r
 }