[InstCombine] Transform `(icmp ult/uge (and X, Y), X)` -> `(icmp ne/eq (and X, Y), X)`

[goldstein.w.n]

Summary

eq/ne are generally easier to reason about elsewhere.

ult -> ne: https://alive2.llvm.org/ce/z/5wxXGt
uge -> eq: https://alive2.llvm.org/ce/z/Dw6kqG

[nikic]

LGTM

[goldstein.w.n]

Rebase

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4449

For symmetry with the or fold, I think we want X & Y == Y to X | ~Y == -1 for freely invertible Y (https://alive2.llvm.org/ce/z/wt3Cg6).

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4449

And X & Y == Y to ~X & Y == 0 as well, based on what the final version of D144610 implemented.

IIRC one of those folds also got implemented for constants previously, so we can drop that then.

[goldstein.w.n]

Rebase

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4449

Done, although (as you can see from the stack) that actually had fairly large implications for: foldICmpWithLowBitMaskedVal so added patches for that as well.

But the logic is there in: D159059

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4449

Also note just about no compile time blowback for any of the changes (was a bit concerned as implemented two recursive functions):
https://llvm-compile-time-tracker.com/compare.php?from=692344d87357ded619d216b265a9375f4326d8fb&to=facaede5ae43806d3123c18823cc173a4b3970ec&stat=instructions%3Au

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

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,
+                                  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(Op0, m_c_And(m_Specific(Op1), m_Value(A))))
+    return nullptr;
+
+  // (icmp (X & Y) u< X --> (X & Y) != X
+  if (Pred == ICmpInst::ICMP_ULT)
+    return new ICmpInst(ICmpInst::ICMP_NE, Op0, Op1);
+
+  // (icmp (X & Y) u>= X --> (X & Y) == X
+  if (Pred == ICmpInst::ICMP_UGE)
+    return new ICmpInst(ICmpInst::ICMP_EQ, Op0, Op1);
+
+  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.
   CmpInst::Predicate Pred = I.getPredicate();
   if (match(Op1, m_c_Or(m_Specific(Op0), m_Value(A)))) {
     std::swap(Op0, Op1);
Instruction *InstCombinerImpl::foldICmpBinOp(ICmpInst &I,
   }
 
   if (Value *V = foldMultiplicationOverflowCheck(I))
     return replaceInstUsesWith(I, V);
 
   if (Value *V = foldICmpWithLowBitMaskedVal(I, Builder))
     return replaceInstUsesWith(I, V);
 
+  if (Instruction *R = foldICmpAndXX(I, Q, *this))
+    return R;
+
   if (Value *V = foldICmpWithTruncSignExtendedVal(I, Builder))
     return replaceInstUsesWith(I, V);
 
   if (Value *V = foldShiftIntoShiftInAnotherHandOfAndInICmp(I, SQ, Builder))
     return replaceInstUsesWith(I, V);
 
   return nullptr;
 }

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

 ;
   %tmp0 = and <2 x i8> %x, <i8 3, i8 15> ; doesn't have to be splat.
   %ret = icmp uge <2 x i8> %tmp0, %x
   ret <2 x i1> %ret
 }
 
 define <2 x i1> @p2_vec_nonsplat_edgecase0(<2 x i8> %x) {
 ; CHECK-LABEL: @p2_vec_nonsplat_edgecase0(
-; CHECK-NEXT:    [[TMP0:%.*]] = and <2 x i8> [[X:%.*]], <i8 3, i8 0>
-; CHECK-NEXT:    [[RET:%.*]] = icmp uge <2 x i8> [[TMP0]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i8> [[X:%.*]], <i8 -4, i8 -1>
+; CHECK-NEXT:    [[RET:%.*]] = icmp eq <2 x i8> [[TMP1]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[RET]]
 ;
   %tmp0 = and <2 x i8> %x, <i8 3, i8 0>
   %ret = icmp uge <2 x i8> %tmp0, %x
   ret <2 x i1> %ret
 }
 define <2 x i1> @p2_vec_nonsplat_edgecase1(<2 x i8> %x) {
 ; CHECK-LABEL: @p2_vec_nonsplat_edgecase1(

 }
 
 ; ============================================================================ ;
 ; Negative tests
 ; ============================================================================ ;
 
 define i1 @n0(i8 %x) {
 ; CHECK-LABEL: @n0(
-; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[X:%.*]], 4
-; CHECK-NEXT:    [[RET:%.*]] = icmp uge i8 [[TMP0]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X:%.*]], -5
+; CHECK-NEXT:    [[RET:%.*]] = icmp eq i8 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[RET]]
 ;
   %tmp0 = and i8 %x, 4 ; power-of-two, but invalid.
   %ret = icmp uge i8 %tmp0, %x
   ret i1 %ret
 }
 
 define i1 @n1(i8 %x, i8 %y, i8 %notx) {
 ; CHECK-LABEL: @n1(
 ; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[X:%.*]], 3
 ; CHECK-NEXT:    [[RET:%.*]] = icmp uge i8 [[TMP0]], [[NOTX:%.*]]
 ; CHECK-NEXT:    ret i1 [[RET]]
 ;
   %tmp0 = and i8 %x, 3
   %ret = icmp uge i8 %tmp0, %notx ; not %x
   ret i1 %ret
 }
 
 define <2 x i1> @n2(<2 x i8> %x) {
 ; CHECK-LABEL: @n2(
-; CHECK-NEXT:    [[TMP0:%.*]] = and <2 x i8> [[X:%.*]], <i8 3, i8 16>
-; CHECK-NEXT:    [[RET:%.*]] = icmp uge <2 x i8> [[TMP0]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i8> [[X:%.*]], <i8 -4, i8 -17>
+; CHECK-NEXT:    [[RET:%.*]] = icmp eq <2 x i8> [[TMP1]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[RET]]
 ;
   %tmp0 = and <2 x i8> %x, <i8 3, i8 16> ; only the first one is valid.
   %ret = icmp uge <2 x i8> %tmp0, %x
   ret <2 x i1> %ret
 }

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

;
   %tmp0 = and <2 x i8> %x, <i8 3, i8 15> ; doesn't have to be splat.
   %ret = icmp ugt <2 x i8> %x, %tmp0
   ret <2 x i1> %ret
 }
 
 define <2 x i1> @p2_vec_nonsplat_edgecase0() {
 ; CHECK-LABEL: @p2_vec_nonsplat_edgecase0(
 ; CHECK-NEXT:    [[X:%.*]] = call <2 x i8> @gen2x8()
-; CHECK-NEXT:    [[TMP0:%.*]] = and <2 x i8> [[X]], <i8 3, i8 0>
-; CHECK-NEXT:    [[RET:%.*]] = icmp ugt <2 x i8> [[X]], [[TMP0]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i8> [[X]], <i8 -4, i8 -1>
+; CHECK-NEXT:    [[RET:%.*]] = icmp ne <2 x i8> [[TMP1]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[RET]]
 ;
   %x = call <2 x i8> @gen2x8()
   %tmp0 = and <2 x i8> %x, <i8 3, i8 0>
   %ret = icmp ugt <2 x i8> %x, %tmp0
   ret <2 x i1> %ret
 }
 define <2 x i1> @p2_vec_nonsplat_edgecase1() {

 
 ; ============================================================================ ;
 ; Negative tests
 ; ============================================================================ ;
 
 define i1 @n0() {
 ; CHECK-LABEL: @n0(
 ; CHECK-NEXT:    [[X:%.*]] = call i8 @gen8()
-; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[X]], 4
-; CHECK-NEXT:    [[RET:%.*]] = icmp ugt i8 [[X]], [[TMP0]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X]], -5
+; CHECK-NEXT:    [[RET:%.*]] = icmp ne i8 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[RET]]
 ;
   %x = call i8 @gen8()
   %tmp0 = and i8 %x, 4 ; power-of-two, but invalid.
   %ret = icmp ugt i8 %x, %tmp0
   ret i1 %ret
 }
 
 define i1 @n1(i8 %y, i8 %notx) {
 ; CHECK-LABEL: @n1(
 ; CHECK-NEXT:    [[X:%.*]] = call i8 @gen8()
 ; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[X]], 3
 ; CHECK-NEXT:    [[RET:%.*]] = icmp ugt i8 [[TMP0]], [[NOTX:%.*]]
 ; CHECK-NEXT:    ret i1 [[RET]]
 ;
   %x = call i8 @gen8()
   %tmp0 = and i8 %x, 3
   %ret = icmp ugt i8 %tmp0, %notx ; not %x
   ret i1 %ret
 }
 
 define <2 x i1> @n2() {
 ; CHECK-LABEL: @n2(
 ; CHECK-NEXT:    [[X:%.*]] = call <2 x i8> @gen2x8()
-; CHECK-NEXT:    [[TMP0:%.*]] = and <2 x i8> [[X]], <i8 3, i8 16>
-; CHECK-NEXT:    [[RET:%.*]] = icmp ugt <2 x i8> [[X]], [[TMP0]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i8> [[X]], <i8 -4, i8 -17>
+; CHECK-NEXT:    [[RET:%.*]] = icmp ne <2 x i8> [[TMP1]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[RET]]
 ;
   %x = call <2 x i8> @gen2x8()
   %tmp0 = and <2 x i8> %x, <i8 3, i8 16> ; only the first one is valid.
   %ret = icmp ugt <2 x i8> %x, %tmp0
   ret <2 x i1> %ret
 }

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

;
   %tmp0 = and <2 x i8> %x, <i8 3, i8 15> ; doesn't have to be splat.
   %ret = icmp ule <2 x i8> %x, %tmp0
   ret <2 x i1> %ret
 }
 
 define <2 x i1> @p2_vec_nonsplat_edgecase0() {
 ; CHECK-LABEL: @p2_vec_nonsplat_edgecase0(
 ; CHECK-NEXT:    [[X:%.*]] = call <2 x i8> @gen2x8()
-; CHECK-NEXT:    [[TMP0:%.*]] = and <2 x i8> [[X]], <i8 3, i8 0>
-; CHECK-NEXT:    [[RET:%.*]] = icmp ule <2 x i8> [[X]], [[TMP0]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i8> [[X]], <i8 -4, i8 -1>
+; CHECK-NEXT:    [[RET:%.*]] = icmp eq <2 x i8> [[TMP1]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[RET]]
 ;
   %x = call <2 x i8> @gen2x8()
   %tmp0 = and <2 x i8> %x, <i8 3, i8 0>
   %ret = icmp ule <2 x i8> %x, %tmp0
   ret <2 x i1> %ret
 }
 define <2 x i1> @p2_vec_nonsplat_edgecase1() {

 
 ; ============================================================================ ;
 ; Negative tests
 ; ============================================================================ ;
 
 define i1 @n0() {
 ; CHECK-LABEL: @n0(
 ; CHECK-NEXT:    [[X:%.*]] = call i8 @gen8()
-; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[X]], 4
-; CHECK-NEXT:    [[RET:%.*]] = icmp ule i8 [[X]], [[TMP0]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X]], -5
+; CHECK-NEXT:    [[RET:%.*]] = icmp eq i8 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[RET]]
 ;
   %x = call i8 @gen8()
   %tmp0 = and i8 %x, 4 ; power-of-two, but invalid.
   %ret = icmp ule i8 %x, %tmp0
   ret i1 %ret
 }
 
 define i1 @n1(i8 %y, i8 %notx) {
 ; CHECK-LABEL: @n1(
 ; CHECK-NEXT:    [[X:%.*]] = call i8 @gen8()
 ; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[X]], 3
 ; CHECK-NEXT:    [[RET:%.*]] = icmp ule i8 [[TMP0]], [[NOTX:%.*]]
 ; CHECK-NEXT:    ret i1 [[RET]]
 ;
   %x = call i8 @gen8()
   %tmp0 = and i8 %x, 3
   %ret = icmp ule i8 %tmp0, %notx ; not %x
   ret i1 %ret
 }
 
 define <2 x i1> @n2() {
 ; CHECK-LABEL: @n2(
 ; CHECK-NEXT:    [[X:%.*]] = call <2 x i8> @gen2x8()
-; CHECK-NEXT:    [[TMP0:%.*]] = and <2 x i8> [[X]], <i8 3, i8 16>
-; CHECK-NEXT:    [[RET:%.*]] = icmp ule <2 x i8> [[X]], [[TMP0]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i8> [[X]], <i8 -4, i8 -17>
+; CHECK-NEXT:    [[RET:%.*]] = icmp eq <2 x i8> [[TMP1]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[RET]]
 ;
   %x = call <2 x i8> @gen2x8()
   %tmp0 = and <2 x i8> %x, <i8 3, i8 16> ; only the first one is valid.
   %ret = icmp ule <2 x i8> %x, %tmp0
   ret <2 x i1> %ret
 }

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

 ;
   %tmp0 = and <2 x i8> %x, <i8 3, i8 15> ; doesn't have to be splat.
   %ret = icmp ult <2 x i8> %tmp0, %x
   ret <2 x i1> %ret
 }
 
 define <2 x i1> @p2_vec_nonsplat_edgecase0(<2 x i8> %x) {
 ; CHECK-LABEL: @p2_vec_nonsplat_edgecase0(
-; CHECK-NEXT:    [[TMP0:%.*]] = and <2 x i8> [[X:%.*]], <i8 3, i8 0>
-; CHECK-NEXT:    [[RET:%.*]] = icmp ult <2 x i8> [[TMP0]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i8> [[X:%.*]], <i8 -4, i8 -1>
+; CHECK-NEXT:    [[RET:%.*]] = icmp ne <2 x i8> [[TMP1]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[RET]]
 ;
   %tmp0 = and <2 x i8> %x, <i8 3, i8 0>
   %ret = icmp ult <2 x i8> %tmp0, %x
   ret <2 x i1> %ret
 }
 
 define <2 x i1> @p2_vec_nonsplat_edgecase1(<2 x i8> %x) {

 }
 
 ; ============================================================================ ;
 ; Negative tests
 ; ============================================================================ ;
 
 define i1 @n0(i8 %x) {
 ; CHECK-LABEL: @n0(
-; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[X:%.*]], 4
-; CHECK-NEXT:    [[RET:%.*]] = icmp ult i8 [[TMP0]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X:%.*]], -5
+; CHECK-NEXT:    [[RET:%.*]] = icmp ne i8 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[RET]]
 ;
   %tmp0 = and i8 %x, 4 ; power-of-two, but invalid.
   %ret = icmp ult i8 %tmp0, %x
   ret i1 %ret
 }
 
 define i1 @n1(i8 %x, i8 %y, i8 %notx) {
 ; CHECK-LABEL: @n1(
 ; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[X:%.*]], 3
 ; CHECK-NEXT:    [[RET:%.*]] = icmp ult i8 [[TMP0]], [[NOTX:%.*]]
 ; CHECK-NEXT:    ret i1 [[RET]]
 ;
   %tmp0 = and i8 %x, 3
   %ret = icmp ult i8 %tmp0, %notx ; not %x
   ret i1 %ret
 }
 
 define <2 x i1> @n2(<2 x i8> %x) {
 ; CHECK-LABEL: @n2(
-; CHECK-NEXT:    [[TMP0:%.*]] = and <2 x i8> [[X:%.*]], <i8 3, i8 16>
-; CHECK-NEXT:    [[RET:%.*]] = icmp ult <2 x i8> [[TMP0]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i8> [[X:%.*]], <i8 -4, i8 -17>
+; CHECK-NEXT:    [[RET:%.*]] = icmp ne <2 x i8> [[TMP1]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[RET]]
 ;
   %tmp0 = and <2 x i8> %x, <i8 3, i8 16> ; only the first one is valid.
   %ret = icmp ult <2 x i8> %tmp0, %x
   ret <2 x i1> %ret
 }

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 declare i1 @barrier()
 declare void @llvm.assume(i1)
 
 define i1 @icmp_ult_x_y(i8 %x, i8 %y) {
 ; CHECK-LABEL: @icmp_ult_x_y(
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp ult i8 [[AND]], [[X]]
+; CHECK-NEXT:    [[Z:%.*]] = icmp ne i8 [[AND]], [[X]]
 ; CHECK-NEXT:    ret i1 [[Z]]
 ;
   %and = and i8 %x, %y
   %z = icmp ult i8 %and, %x
   ret i1 %z
 }
 
 define i1 @icmp_ult_x_y_2(i8 %xx, i8 %y) {
 ; CHECK-LABEL: @icmp_ult_x_y_2(
 ; CHECK-NEXT:    [[X:%.*]] = mul i8 [[XX:%.*]], [[XX]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X]], [[Y:%.*]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp ugt i8 [[X]], [[AND]]
+; CHECK-NEXT:    [[Z:%.*]] = icmp ne i8 [[AND]], [[X]]
 ; CHECK-NEXT:    ret i1 [[Z]]
 ;
   %x = mul i8 %xx, %xx
   %and = and i8 %x, %y
   %z = icmp ugt i8 %x, %and
   ret i1 %z
 }
 
 define <2 x i1> @icmp_uge_x_y(<2 x i8> %x, <2 x i8> %y) {
 ; CHECK-LABEL: @icmp_uge_x_y(
 ; CHECK-NEXT:    [[AND:%.*]] = and <2 x i8> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp uge <2 x i8> [[AND]], [[X]]
+; CHECK-NEXT:    [[Z:%.*]] = icmp eq <2 x i8> [[AND]], [[X]]
 ; CHECK-NEXT:    ret <2 x i1> [[Z]]
 ;
   %and = and <2 x i8> %x, %y
   %z = icmp uge <2 x i8> %and, %x
   ret <2 x i1> %z
 }
 
 define i1 @icmp_uge_x_y_2(i8 %xx, i8 %y) {
 ; CHECK-LABEL: @icmp_uge_x_y_2(
 ; CHECK-NEXT:    [[X:%.*]] = mul i8 [[XX:%.*]], [[XX]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X]], [[Y:%.*]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp ule i8 [[X]], [[AND]]
+; CHECK-NEXT:    [[Z:%.*]] = icmp eq i8 [[AND]], [[X]]
 ; CHECK-NEXT:    ret i1 [[Z]]
 ;
   %x = mul i8 %xx, %xx
   %and = and i8 %x, %y
   %z = icmp ule i8 %x, %and
   ret i1 %z
 }