[InstCombine] Improve transforms for (icmp uPred X * Z, Y * Z) -> (icmp uPred X, Y)

[goldstein.w.n]

Summary

Several cases where missing.

1. (icmp eq/ne X*Z, Y*Z) [if Z % 2 != 0] -> (icmp eq/ne X, Y) EQ: https://alive2.llvm.org/ce/z/6_HPZ5 NE: https://alive2.llvm.org/ce/z/c34qSU
   
   There was previously an implementation of this that work of Y was non-constant, but it was missing if Y*Z evaluated to a constant and/or nsw/nuw where both false. As well it only worked if Z was a constant but we can check 1s bit of KnownBits to cover more cases.

2. (icmp eq/ne X*Z, Y*Z) [if Z != 0 and nsw(X*Y) and nsw(Y*Z)] -> (icmp eq/ne X, Y) EQ: https://alive2.llvm.org/ce/z/6SdAG6 NE: https://alive2.llvm.org/ce/z/fjsq_b
   
   This was previously implemented only to work if Z was constant, but we can use isKnownNonZero to cover more cases.

3. (icmp uPred X*Y, Y*Z) [if Z != 0 and nuw(X*Y) and nuw(X*Y)] -> (icmp uPred X, Y) EQ: https://alive2.llvm.org/ce/z/FqWQLX NE: https://alive2.llvm.org/ce/z/2gHrd2 ULT: https://alive2.llvm.org/ce/z/MUAWgZ ULE: https://alive2.llvm.org/ce/z/szQQ2L UGT: https://alive2.llvm.org/ce/z/McVUdu UGE: https://alive2.llvm.org/ce/z/95uyC8
   
   This was previously implemented only for eq/ne cases. As well only if Z was constant, but again we can use isKnownNonZero to cover more cases.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4432

Is there a better way to do this?

[spatel]

If the 3 improvements are independent, it would be better to make this into 3 small patches. That makes it easier to review and reduces risk.

[goldstein.w.n]

In D142786#4093976, @spatel wrote:

If the 3 improvements are independent, it would be better to make this into 3 small patches. That makes it easier to review and reduces risk.

I"ll split case 1, but case 2/3 are basically in the same new code block.

[goldstein.w.n]

Rebase + Split

[goldstein.w.n]

In D142786#4093976, @spatel wrote:

If the 3 improvements are independent, it would be better to make this into 3 small patches. That makes it easier to review and reduces risk.

I split the constant case too D143026.

My preference is too keep the rest of this together, its three cases, but those three cases where what was covered in the previous
code block and I couldn't find a clean way to only partially insert this patch w.o causing regressions from missing cases b.c the old
code was removed.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4432

AFAIK, there's no direct way to specify/capture a common operand like that, but this way is shorter and easier to read since it doesn't need any extra operand names:

if (Pred == ICmpInst::getUnsignedPredicate(Pred) &&
    ((match(Op0, m_Mul(m_Value(X), m_Value(Z))) &&
      match(Op1, m_c_Mul(m_Specific(Z), m_Value(Y)))) ||
     (match(Op0, m_Mul(m_Value(Z), m_Value(X))) &&
      match(Op1, m_c_Mul(m_Specific(Z), m_Value(Y)))))) {

[goldstein.w.n]

Make X/Y/Z collection much better

[goldstein.w.n]

Done.

[spatel]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (NoOp0WrapProblem && ICmpInst::isSigned(Pred)) {
     if (match(BO0, m_Neg(m_Value(X))))
       if (Constant *RHSC = dyn_cast<Constant>(Op1))
         if (RHSC->isNotMinSignedValue())
           return new ICmpInst(I.getSwappedPredicate(), X,
                               ConstantExpr::getNeg(RHSC));
   }
 
   {
-    // Try to remove shared constant multiplier from equality comparison:
-    // X * C == Y * C (with no overflowing/aliasing) --> X == Y
-    Value *X, *Y;
-    const APInt *C;
-    if (match(Op0, m_Mul(m_Value(X), m_APInt(C))) && *C != 0 &&
-        match(Op1, m_Mul(m_Value(Y), m_SpecificInt(*C))) && I.isEquality())
-      if (!C->countTrailingZeros() ||
-          (BO0 && BO1 && BO0->hasNoSignedWrap() && BO1->hasNoSignedWrap()) ||
-          (BO0 && BO1 && BO0->hasNoUnsignedWrap() && BO1->hasNoUnsignedWrap()))
+    // Try to remove shared multiplier from comparison:
+    // X * Z u{lt/le/gt/ge}/eq/ne Y * Z
+    Value *X, *Y, *Z;
+    if (Pred == ICmpInst::getUnsignedPredicate(Pred) &&
+        ((match(Op0, m_Mul(m_Value(X), m_Value(Z))) &&
+          match(Op1, m_c_Mul(m_Specific(Z), m_Value(Y)))) ||
+         (match(Op0, m_Mul(m_Value(Z), m_Value(X))) &&
+          match(Op1, m_c_Mul(m_Specific(Z), m_Value(Y)))))) {
+      bool NonZero;
+      if (ICmpInst::isEquality(Pred)) {
+        KnownBits ZKnown = computeKnownBits(Z, 0, &I);
+        // if Z % 2 != 0
+        //    X * Z eq/ne Y * Z -> X eq/ne Y
+        if (ZKnown.countMaxTrailingZeros() == 0)
           return new ICmpInst(Pred, X, Y);
+        NonZero = !ZKnown.One.isZero() ||
+                  isKnownNonZero(Z, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT);
+        // if Z != 0 and nsw(X * Z) and nsw(Y * Z)
+        //    X * Z eq/ne Y * Z -> X eq/ne Y
+        if (NonZero && BO0 && BO1 && BO0->hasNoSignedWrap() &&
+            BO1->hasNoSignedWrap())
+          return new ICmpInst(Pred, X, Y);
+      } else
+        NonZero = isKnownNonZero(Z, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT);
+
+      // If Z != 0 and nuw(X * Z) and nuw(Y * Z)
+      //    X * Z u{lt/le/gt/ge}/eq/ne Y * Z -> X u{lt/le/gt/ge}/eq/ne Y
+      if (NonZero && BO0 && BO1 && BO0->hasNoUnsignedWrap() &&
+          BO1->hasNoUnsignedWrap())
+        return new ICmpInst(Pred, X, Y);
+    }
   }
 
   BinaryOperator *SRem = nullptr;
   // icmp (srem X, Y), Y
   if (BO0 && BO0->getOpcode() == Instruction::SRem && Op1 == BO0->getOperand(1))
     SRem = BO0;
   // icmp Y, (srem X, Y)
   else if (BO1 && BO1->getOpcode() == Instruction::SRem &&

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

;
   ret i1 %cmp
 }
 
 define i1 @mul_xy_z_assumeodd_eq(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @mul_xy_z_assumeodd_eq(
 ; CHECK-NEXT:    [[LB:%.*]] = and i8 [[Z:%.*]], 1
 ; CHECK-NEXT:    [[NZ:%.*]] = icmp ne i8 [[LB]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[NZ]])
-; CHECK-NEXT:    [[MULX:%.*]] = mul i8 [[X:%.*]], [[Z]]
-; CHECK-NEXT:    [[MULY:%.*]] = mul i8 [[Z]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[MULX]], [[MULY]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %lb = and i8 %z, 1
   %nz = icmp ne i8 %lb, 0
   call void @llvm.assume(i1 %nz)
   %mulx = mul i8 %x, %z
   %muly = mul i8 %z, %y
   %cmp = icmp eq i8 %mulx, %muly
   ret i1 %cmp
 }
 
 define <2 x i1> @reused_mul_nsw_xy_z_setnonzero_vec_ne(<2 x i8> %x, <2 x i8> %y, <2 x i8> %zi) {
 ; CHECK-LABEL: @reused_mul_nsw_xy_z_setnonzero_vec_ne(
 ; CHECK-NEXT:    [[Z:%.*]] = or <2 x i8> [[ZI:%.*]], <i8 4, i8 4>
-; CHECK-NEXT:    [[MULX:%.*]] = mul nsw <2 x i8> [[Z]], [[X:%.*]]
 ; CHECK-NEXT:    [[MULY:%.*]] = mul nsw <2 x i8> [[Z]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne <2 x i8> [[MULY]], [[MULX]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne <2 x i8> [[Y]], [[X:%.*]]
 ; CHECK-NEXT:    call void @usev2xi8(<2 x i8> [[MULY]])
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
   %z = or <2 x i8> %zi, <i8 4, i8 4>
   %mulx = mul nsw <2 x i8> %z, %x
   %muly = mul nsw <2 x i8> %y, %z
   %cmp = icmp ne <2 x i8> %muly, %mulx
   call void @usev2xi8(<2 x i8> %muly)
;
   ret i1 %cmp
 }
 
 define i1 @mul_nuw_xy_z_assumenonzero_uge(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @mul_nuw_xy_z_assumenonzero_uge(
 ; CHECK-NEXT:    [[NZ:%.*]] = icmp ne i8 [[Z:%.*]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[NZ]])
 ; CHECK-NEXT:    [[MULX:%.*]] = mul nuw i8 [[X:%.*]], [[Z]]
-; CHECK-NEXT:    [[MULY:%.*]] = mul nuw i8 [[Y:%.*]], [[Z]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp uge i8 [[MULY]], [[MULX]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp uge i8 [[Y:%.*]], [[X]]
 ; CHECK-NEXT:    call void @use(i8 [[MULX]])
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %nz = icmp ne i8 %z, 0
   call void @llvm.assume(i1 %nz)
   %mulx = mul nuw i8 %x, %z
   %muly = mul nuw i8 %y, %z
   %cmp = icmp uge i8 %muly, %mulx
   call void @use(i8 %mulx)
   ret i1 %cmp
 }
 
 define <2 x i1> @mul_nuw_xy_z_setnonzero_vec_eq(<2 x i8> %x, <2 x i8> %y, <2 x i8> %zi) {
 ; CHECK-LABEL: @mul_nuw_xy_z_setnonzero_vec_eq(
-; CHECK-NEXT:    [[Z:%.*]] = or <2 x i8> [[ZI:%.*]], <i8 41, i8 12>
-; CHECK-NEXT:    [[MULX:%.*]] = mul nuw <2 x i8> [[Z]], [[X:%.*]]
-; CHECK-NEXT:    [[MULY:%.*]] = mul nuw <2 x i8> [[Z]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <2 x i8> [[MULX]], [[MULY]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <2 x i8> [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
   %z = or <2 x i8> %zi, <i8 41, i8 12>
   %mulx = mul nuw <2 x i8> %z, %x
   %muly = mul nuw <2 x i8> %z, %y
   %cmp = icmp eq <2 x i8> %mulx, %muly
   ret <2 x i1> %cmp
 }
 
 define i1 @mul_nuw_xy_z_brnonzero_ult(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @mul_nuw_xy_z_brnonzero_ult(
 ; CHECK-NEXT:    [[NZ_NOT:%.*]] = icmp eq i8 [[Z:%.*]], 0
 ; CHECK-NEXT:    br i1 [[NZ_NOT]], label [[FALSE:%.*]], label [[TRUE:%.*]]
 ; CHECK:       true:
-; CHECK-NEXT:    [[MULX:%.*]] = mul nuw i8 [[X:%.*]], [[Z]]
-; CHECK-NEXT:    [[MULY:%.*]] = mul nuw i8 [[Y:%.*]], [[Z]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[MULY]], [[MULX]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ; CHECK:       false:
 ; CHECK-NEXT:    call void @use(i8 [[Z]])
 ; CHECK-NEXT:    ret i1 true
 ;
   %nz = icmp ne i8 %z, 0
   br i1 %nz, label %true, label %false
 true: