[InstCombine] Add transforms `(icmp spred (and X, Y), X)` if `X` or `Y` are known signed/unsigned

[goldstein.w.n]

Summary

Several transforms:

1. If known Y < 0:
   • slt -> ult: https://alive2.llvm.org/ce/z/unpsxu
   • sle -> ule: https://alive2.llvm.org/ce/z/a5cpmr
   • sgt -> ugt: https://alive2.llvm.org/ce/z/qgsgya
   • sge -> uge: https://alive2.llvm.org/ce/z/ek_3ls
2. If known Y > 0:
   • (X & PosY) s> X --> X s< 0
     • https://alive2.llvm.org/ce/z/drewij
   • (X & PosY) s> X --> X s< 0
     • https://alive2.llvm.org/ce/z/9arL3D
3. If known X < 0:
   • (NegX & Y) s> NegX --> Y s>= 0
     • https://alive2.llvm.org/ce/z/ApkaEh
   • (NegX & Y) s<= NegX --> Y s< 0
     • https://alive2.llvm.org/ce/z/oRnfHp

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[goldstein.w.n]

Abandoning and resubmitting on GH

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (match(&I, m_c_ICmp(Pred, m_OneUse(m_Neg(m_Value(X))), m_Deferred(X))) &&
     Value *And = Builder.CreateAnd(X, MaxSignedVal);
     Constant *Zero = Constant::getNullValue(Ty);
     return CmpInst::Create(Instruction::ICmp, Pred, And, Zero);
   }
 
   return nullptr;
 }
 
-static Instruction *foldICmpAndXX(ICmpInst &I, const SimplifyQuery &Q,
+static Instruction *foldICmpAndXX(ICmpInst &I, const SimplifyQuery &,
                                   InstCombinerImpl &IC) {
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1), *A;
   // Normalize and operand as operand 0.
   CmpInst::Predicate Pred = I.getPredicate();
   if (match(Op1, m_c_And(m_Specific(Op0), m_Value()))) {
     std::swap(Op0, Op1);
     Pred = ICmpInst::getSwappedPredicate(Pred);
   }
if (!match(Op1, m_ImmConstant()) &&
                           Constant::getAllOnesValue(Op1->getType()));
     // icmp (X & Y) eq/ne Y --> (~X & Y) eq/ne 0 if X  is freely invertible.
     if (IC.isFreeToInvert(A, A->hasOneUse()))
       return new ICmpInst(Pred,
                           IC.Builder.CreateAnd(Op1, IC.Builder.CreateNot(A)),
                           Constant::getNullValue(Op1->getType()));
   }
 
+  if (ICmpInst::isEquality(Pred) || ICmpInst::getSignedPredicate(Pred) != Pred)
+    return nullptr;
+
+  auto IsTrue = [](std::optional<bool> OptBool) {
+    return OptBool.has_value() && OptBool.value();
+  };
+
+  auto IsFalse = [](std::optional<bool> OptBool) {
+    return OptBool.has_value() && !OptBool.value();
+  };
+
+  auto KnownSignY = IC.getKnownSign(A, &I);
+
+  // (X & NegY) spred X --> (icmp (X & NegY) upred X
+  if (IsTrue(KnownSignY))
+    return new ICmpInst(ICmpInst::getUnsignedPredicate(Pred), Op0, Op1);
+
+  if (Pred != ICmpInst::ICMP_SLE && Pred != ICmpInst::ICMP_SGT)
+    return nullptr;
+
+  if (IsFalse(KnownSignY)) {
+    // (X & PosY) s<= X --> X s>= 0
+    if (Pred == ICmpInst::ICMP_SLE)
+      return new ICmpInst(ICmpInst::ICMP_SGE, Op1,
+                          Constant::getNullValue(Op1->getType()));
+    // (X & PosY) s> X --> X s< 0
+    if (Pred == ICmpInst::ICMP_SGT)
+      return new ICmpInst(ICmpInst::ICMP_SLT, Op1,
+                          Constant::getNullValue(Op1->getType()));
+  }
+
+  if (IsTrue(IC.getKnownSign(Op1, &I))) {
+    // (NegX & Y) s> NegX --> Y s>= 0
+    if (Pred == ICmpInst::ICMP_SGT)
+      return new ICmpInst(ICmpInst::ICMP_SGE, A,
+                          Constant::getNullValue(A->getType()));
+
+    // (NegX & Y) s<= NegX --> Y s< 0
+    if (Pred == ICmpInst::ICMP_SLE)
+      return new ICmpInst(ICmpInst::ICMP_SLT, A,
+                          Constant::getNullValue(A->getType()));
+  }
+
   return nullptr;
 }
 
 static Instruction *foldICmpOrXX(ICmpInst &I, const SimplifyQuery &Q,
                                  InstCombinerImpl &IC) {
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1), *A;
 
   // Normalize or operand as operand 0.

llvm/test/Transforms/InstCombine/canonicalize-constant-low-bit-mask-and-icmp-sge-to-icmp-sle.ll

 
 ; Commutativity tests.
 
 declare i8 @gen8()
 
 define i1 @c0() {
 ; CHECK-LABEL: @c0(
 ; CHECK-NEXT:    [[X:%.*]] = call i8 @gen8()
-; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[X]], 3
-; CHECK-NEXT:    [[RET:%.*]] = icmp sge i8 [[X]], [[TMP0]]
+; CHECK-NEXT:    [[RET:%.*]] = icmp sgt i8 [[X]], -1
 ; CHECK-NEXT:    ret i1 [[RET]]
 ;
   %x = call i8 @gen8()
   %tmp0 = and i8 %x, 3
   %ret = icmp sge i8 %x, %tmp0 ; swapped order
   ret i1 %ret
 }
 

llvm/test/Transforms/InstCombine/canonicalize-constant-low-bit-mask-and-icmp-sgt-to-icmp-sgt.ll

 ; ============================================================================ ;
 ; Negative tests
 ; ============================================================================ ;
 
 ; Commutativity tests.
 
 define i1 @c0(i8 %x) {
 ; CHECK-LABEL: @c0(
-; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[X:%.*]], 3
-; CHECK-NEXT:    [[RET:%.*]] = icmp sgt i8 [[TMP0]], [[X]]
+; CHECK-NEXT:    [[RET:%.*]] = icmp slt i8 [[X:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[RET]]
 ;
   %tmp0 = and i8 %x, 3
   %ret = icmp sgt i8 %tmp0, %x ; swapped order
   ret i1 %ret
 }
 
 ; ============================================================================ ;

llvm/test/Transforms/InstCombine/canonicalize-constant-low-bit-mask-and-icmp-sle-to-icmp-sle.ll

 ; ============================================================================ ;
 ; Negative tests
 ; ============================================================================ ;
 
 ; Commutativity tests.
 
 define i1 @c0(i8 %x) {
 ; CHECK-LABEL: @c0(
-; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[X:%.*]], 3
-; CHECK-NEXT:    [[RET:%.*]] = icmp sle i8 [[TMP0]], [[X]]
+; CHECK-NEXT:    [[RET:%.*]] = icmp sgt i8 [[X:%.*]], -1
 ; CHECK-NEXT:    ret i1 [[RET]]
 ;
   %tmp0 = and i8 %x, 3
   %ret = icmp sle i8 %tmp0, %x ; swapped order
   ret i1 %ret
 }
 
 ; ============================================================================ ;

llvm/test/Transforms/InstCombine/canonicalize-constant-low-bit-mask-and-icmp-slt-to-icmp-sgt.ll

 
 ; Commutativity tests.
 
 declare i8 @gen8()
 
 define i1 @c0() {
 ; CHECK-LABEL: @c0(
 ; CHECK-NEXT:    [[X:%.*]] = call i8 @gen8()
-; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[X]], 3
-; CHECK-NEXT:    [[RET:%.*]] = icmp slt i8 [[X]], [[TMP0]]
+; CHECK-NEXT:    [[RET:%.*]] = icmp slt i8 [[X]], 0
 ; CHECK-NEXT:    ret i1 [[RET]]
 ;
   %x = call i8 @gen8()
   %tmp0 = and i8 %x, 3
   %ret = icmp slt i8 %x, %tmp0 ; swapped order
   ret i1 %ret
 }
 

llvm/test/Transforms/InstCombine/icmp-and-lowbit-mask.ll

;
   %notmask = sub i8 0, %p2
   %and = and i8 %notmask, %x
   %r = icmp eq i8 0, %and
   ret i1 %r
 }
 
 define i1 @src_is_mask_const_slt(i8 %x_in) {
 ; CHECK-LABEL: @src_is_mask_const_slt(
-; CHECK-NEXT:    [[X:%.*]] = xor i8 [[X_IN:%.*]], 123
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X]], 7
-; CHECK-NEXT:    [[R:%.*]] = icmp slt i8 [[X]], [[AND]]
+; CHECK-NEXT:    [[R:%.*]] = icmp slt i8 [[X_IN:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = xor i8 %x_in, 123
   %and = and i8 %x, 7
   %r = icmp slt i8 %x, %and
   ret i1 %r
 }
 
 define i1 @src_is_mask_const_sgt(i8 %x_in) {
 ; CHECK-LABEL: @src_is_mask_const_sgt(
 ; CHECK-NEXT:    [[X:%.*]] = xor i8 [[X_IN:%.*]], 123
 ; CHECK-NEXT:    [[R:%.*]] = icmp sgt i8 [[X]], 7
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = xor i8 %x_in, 123
   %and = and i8 %x, 7
   %r = icmp sgt i8 %x, %and
   ret i1 %r
 }
 
 define i1 @src_is_mask_const_sle(i8 %x_in) {
 ; CHECK-LABEL: @src_is_mask_const_sle(
-; CHECK-NEXT:    [[X:%.*]] = xor i8 [[X_IN:%.*]], 123
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X]], 31
-; CHECK-NEXT:    [[R:%.*]] = icmp sle i8 [[AND]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i8 [[X_IN:%.*]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = xor i8 %x_in, 123
   %and = and i8 %x, 31
   %r = icmp sle i8 %and, %x
   ret i1 %r
 }
 

llvm/test/Transforms/InstCombine/icmp-of-and-x.ll

;
   ret i1 %z
 }
 
 define i1 @icmp_sge_x_negy(i8 %x, i8 %y) {
 ; CHECK-LABEL: @icmp_sge_x_negy(
 ; CHECK-NEXT:    [[CY:%.*]] = icmp slt i8 [[Y:%.*]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CY]])
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X:%.*]], [[Y]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp sge i8 [[AND]], [[X]]
+; CHECK-NEXT:    [[Z:%.*]] = icmp eq i8 [[AND]], [[X]]
 ; CHECK-NEXT:    ret i1 [[Z]]
 ;
   %cy = icmp slt i8 %y, 0
   call void @llvm.assume(i1 %cy)
   %and = and i8 %x, %y
   %z = icmp sge i8 %and, %x
   ret i1 %z
 }
 
 define i1 @icmp_slt_x_negy(i8 %x, i8 %y) {
 ; CHECK-LABEL: @icmp_slt_x_negy(
 ; CHECK-NEXT:    [[CY:%.*]] = icmp slt i8 [[Y:%.*]], 0
 ; CHECK-NEXT:    br i1 [[CY]], label [[NEGY:%.*]], label [[POSY:%.*]]
 ; CHECK:       negy:
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X:%.*]], [[Y]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp slt i8 [[AND]], [[X]]
+; CHECK-NEXT:    [[Z:%.*]] = icmp ne i8 [[AND]], [[X]]
 ; CHECK-NEXT:    ret i1 [[Z]]
 ; CHECK:       posy:
 ; CHECK-NEXT:    [[R:%.*]] = call i1 @barrier()
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %cy = icmp slt i8 %y, 0
   br i1 %cy, label %negy, label %posy
 negy:
negy:
   ret i1 %z
 posy:
   %r = call i1 @barrier()
   ret i1 %r
 }
 
 define i1 @icmp_sle_x_negy(i8 %x, i8 %yy) {
 ; CHECK-LABEL: @icmp_sle_x_negy(
-; CHECK-NEXT:    [[Y:%.*]] = or i8 [[YY:%.*]], -128
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[Y]], [[X:%.*]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp sle i8 [[AND]], [[X]]
-; CHECK-NEXT:    ret i1 [[Z]]
+; CHECK-NEXT:    ret i1 true
 ;
   %y = or i8 %yy, 128
   %and = and i8 %y, %x
   %z = icmp sle i8 %and, %x
   ret i1 %z
 }
 
 define <2 x i1> @icmp_sgt_x_negy(<2 x i8> %x, <2 x i8> %yy) {
 ; CHECK-LABEL: @icmp_sgt_x_negy(
-; CHECK-NEXT:    [[Y:%.*]] = or <2 x i8> [[YY:%.*]], <i8 -128, i8 -128>
-; CHECK-NEXT:    [[AND:%.*]] = and <2 x i8> [[Y]], [[X:%.*]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp sgt <2 x i8> [[AND]], [[X]]
-; CHECK-NEXT:    ret <2 x i1> [[Z]]
+; CHECK-NEXT:    ret <2 x i1> zeroinitializer
 ;
   %y = or <2 x i8> %yy, <i8 128, i8 128>
   %and = and <2 x i8> %y, %x
   %z = icmp sgt <2 x i8> %and, %x
   ret <2 x i1> %z
 }
 
 define <2 x i1> @icmp_sgt_x_negy_fail_partial(<2 x i8> %x, <2 x i8> %yy) {
 ; CHECK-LABEL: @icmp_sgt_x_negy_fail_partial(
 ; CHECK-NEXT:    [[Y:%.*]] = or <2 x i8> [[YY:%.*]], <i8 -128, i8 4>
 ; CHECK-NEXT:    [[AND:%.*]] = and <2 x i8> [[Y]], [[X:%.*]]
 ; CHECK-NEXT:    [[Z:%.*]] = icmp sgt <2 x i8> [[AND]], [[X]]
 ; CHECK-NEXT:    ret <2 x i1> [[Z]]
 ;
   %y = or <2 x i8> %yy, <i8 128, i8 4>
   %and = and <2 x i8> %y, %x
   %z = icmp sgt <2 x i8> %and, %x
   ret <2 x i1> %z
 }
 
 define <2 x i1> @icmp_sle_x_posy(<2 x i8> %x, <2 x i8> %yy) {
 ; CHECK-LABEL: @icmp_sle_x_posy(
-; CHECK-NEXT:    [[Y:%.*]] = and <2 x i8> [[YY:%.*]], <i8 127, i8 127>
-; CHECK-NEXT:    [[AND:%.*]] = and <2 x i8> [[Y]], [[X:%.*]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp sle <2 x i8> [[AND]], [[X]]
+; CHECK-NEXT:    [[Z:%.*]] = icmp sgt <2 x i8> [[X:%.*]], <i8 -1, i8 -1>
 ; CHECK-NEXT:    ret <2 x i1> [[Z]]
 ;
   %y = and <2 x i8> %yy, <i8 127, i8 127>
   %and = and <2 x i8> %y, %x
   %z = icmp sle <2 x i8> %and, %x
   ret <2 x i1> %z
 }
 
;
   %z = icmp sle <2 x i8> %and, %x
   ret <2 x i1> %z
 }
 
 define i1 @icmp_sgt_x_posy(i8 %x, i8 %y) {
 ; CHECK-LABEL: @icmp_sgt_x_posy(
 ; CHECK-NEXT:    [[CY:%.*]] = icmp sgt i8 [[Y:%.*]], -1
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CY]])
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X:%.*]], [[Y]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp sgt i8 [[AND]], [[X]]
+; CHECK-NEXT:    [[Z:%.*]] = icmp slt i8 [[X:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[Z]]
 ;
   %cy = icmp sge i8 %y, 0
   call void @llvm.assume(i1 %cy)
   %and = and i8 %x, %y
   %z = icmp sgt i8 %and, %x
   ret i1 %z
 }
 
 define <2 x i1> @icmp_sgt_negx_y(<2 x i8> %xx, <2 x i8> %y) {
 ; CHECK-LABEL: @icmp_sgt_negx_y(
-; CHECK-NEXT:    [[X:%.*]] = or <2 x i8> [[XX:%.*]], <i8 -128, i8 -128>
-; CHECK-NEXT:    [[AND:%.*]] = and <2 x i8> [[X]], [[Y:%.*]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp sgt <2 x i8> [[AND]], [[X]]
+; CHECK-NEXT:    [[Z:%.*]] = icmp sgt <2 x i8> [[Y:%.*]], <i8 -1, i8 -1>
 ; CHECK-NEXT:    ret <2 x i1> [[Z]]
 ;
   %x = or <2 x i8> %xx, <i8 128, i8 128>
   %and = and <2 x i8> %x, %y
   %z = icmp sgt <2 x i8> %and, %x
   ret <2 x i1> %z
 }
 
 define i1 @icmp_sle_negx_y(i8 %x, i8 %y) {
 ; CHECK-LABEL: @icmp_sle_negx_y(
 ; CHECK-NEXT:    [[CX:%.*]] = icmp slt i8 [[X:%.*]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CX]])
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X]], [[Y:%.*]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp sle i8 [[AND]], [[X]]
+; CHECK-NEXT:    [[Z:%.*]] = icmp slt i8 [[Y:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[Z]]
 ;
   %cx = icmp slt i8 %x, 0
   call void @llvm.assume(i1 %cx)
   %and = and i8 %x, %y
   %z = icmp sle i8 %and, %x
   ret i1 %z
 }