[InstCombine] Canonicalize `(icmp eq/ne (and x, C), x)` -> `(icmp eq/ne (and x, ~C), 0)`

[goldstein.w.n]

Summary

This increases the likelyhood x is single-use and is typically
easier to analyze.

Proofs: https://alive2.llvm.org/ce/z/8ZpS2W

[nikic]

LGTM. Note that there is a conjugate or fold (same but with -1 instead of 0) that should be implemented for symmetry as well.

[goldstein.w.n]

In D154004#4458568, @nikic wrote:

LGTM. Note that there is a conjugate or fold (same but with -1 instead of 0) that should be implemented for symmetry as well.

Or better yet (icmp eq/ne (or x, C), x) -> (icmp eq/ne (and x, C), C): https://alive2.llvm.org/ce/z/m2R2jo
Then we get to reuse C instead of creating a new constant (and and is typically the easiest to analyze).

Works generically as well (I actually have it implemented in: D144610).
If you think this is enough motivation for D144610 I can rebase the series, otherwise I'll just implement here along side the current and code. LMK.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (match(Op1, m_Xor(m_Value(C), m_Value(D)))) {
         return new ICmpInst(Pred, B, C);
       if (B == C)
         return new ICmpInst(Pred, A, D);
       if (B == D)
         return new ICmpInst(Pred, A, C);
     }
   }
 
+  // canoncalize:
+  // (icmp eq/ne (and X, C), X)
+  //    -> (icmp eq/ne (and X, ~C), 0)
+  {
+    Constant *CMask;
+    A = nullptr;
+    if (match(Op0, m_OneUse(m_And(m_Specific(Op1), m_ImmConstant(CMask)))))
+      A = Op1;
+    else if (match(Op1, m_OneUse(m_And(m_Specific(Op0), m_ImmConstant(CMask)))))
+      A = Op0;
+    if (A)
+      return new ICmpInst(Pred, Builder.CreateAnd(A, Builder.CreateNot(CMask)),
+                          Constant::getNullValue(A->getType()));
+  }
+
   if (match(Op1, m_Xor(m_Value(A), m_Value(B))) && (A == Op0 || B == Op0)) {
     // A == (A^B)  ->  B == 0
     Value *OtherVal = A == Op0 ? B : A;
     return new ICmpInst(Pred, OtherVal, Constant::getNullValue(A->getType()));
   }
 
   // (X&Z) == (Y&Z) -> (X^Y) & Z == 0
   if (match(Op0, m_OneUse(m_And(m_Value(A), m_Value(B)))) &&

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

 ;
   %tmp0 = and <2 x i8> %x, <i8 3, i8 15> ; doesn't have to be splat.
   %ret = icmp eq <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 eq <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 eq <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 eq 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 eq 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 eq i8 [[TMP0]], [[NOTX:%.*]]
 ; CHECK-NEXT:    ret i1 [[RET]]
 ;
   %tmp0 = and i8 %x, 3
   %ret = icmp eq 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 eq <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 eq <2 x i8> %tmp0, %x
   ret <2 x i1> %ret
 }

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

 ;
   %tmp0 = and <2 x i8> %x, <i8 3, i8 15> ; doesn't have to be splat.
   %ret = icmp ne <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 ne <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 ne <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 ne 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 ne 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 ne i8 [[TMP0]], [[NOTX:%.*]]
 ; CHECK-NEXT:    ret i1 [[RET]]
 ;
   %tmp0 = and i8 %x, 3
   %ret = icmp ne 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 ne <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 ne <2 x i8> %tmp0, %x
   ret <2 x i1> %ret
 }

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

;
   %mask2 = and i32 %A, 39
   %tst2 = icmp eq i32 %mask2, 39
   %res = select i1 %tst1, i1 true, i1 %tst2
   ret i1 %res
 }
 
 define i1 @masked_and_notA(i32 %A) {
 ; CHECK-LABEL: @masked_and_notA(
-; CHECK-NEXT:    [[MASK2:%.*]] = and i32 [[A:%.*]], 78
-; CHECK-NEXT:    [[TST2:%.*]] = icmp ne i32 [[MASK2]], [[A]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A:%.*]], -79
+; CHECK-NEXT:    [[TST2:%.*]] = icmp ne i32 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[TST2]]
 ;
   %mask1 = and i32 %A, 14
   %tst1 = icmp ne i32 %mask1, %A
   %mask2 = and i32 %A, 78
   %tst2 = icmp ne i32 %mask2, %A
   %res = and i1 %tst1, %tst2
   ret i1 %res
 }
 
 define i1 @masked_and_notA_logical(i32 %A) {
 ; CHECK-LABEL: @masked_and_notA_logical(
-; CHECK-NEXT:    [[MASK2:%.*]] = and i32 [[A:%.*]], 78
-; CHECK-NEXT:    [[TST2:%.*]] = icmp ne i32 [[MASK2]], [[A]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A:%.*]], -79
+; CHECK-NEXT:    [[TST2:%.*]] = icmp ne i32 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[TST2]]
 ;
   %mask1 = and i32 %A, 14
   %tst1 = icmp ne i32 %mask1, %A
   %mask2 = and i32 %A, 78
   %tst2 = icmp ne i32 %mask2, %A
   %res = select i1 %tst1, i1 %tst2, i1 false
   ret i1 %res
 }
 
 define i1 @masked_and_notA_slightly_optimized(i32 %A) {
 ; CHECK-LABEL: @masked_and_notA_slightly_optimized(
-; CHECK-NEXT:    [[T0:%.*]] = icmp ugt i32 [[A:%.*]], 7
-; CHECK-NEXT:    [[MASK2:%.*]] = and i32 [[A]], 39
-; CHECK-NEXT:    [[TST2:%.*]] = icmp ne i32 [[MASK2]], [[A]]
-; CHECK-NEXT:    [[RES:%.*]] = and i1 [[T0]], [[TST2]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A:%.*]], -40
+; CHECK-NEXT:    [[TST2:%.*]] = icmp ne i32 [[TMP1]], 0
+; CHECK-NEXT:    ret i1 [[TST2]]
 ;
   %t0 = icmp uge i32 %A, 8
   %mask2 = and i32 %A, 39
   %tst2 = icmp ne i32 %mask2, %A
   %res = and i1 %t0, %tst2
   ret i1 %res
 }
 
 define i1 @masked_and_notA_slightly_optimized_logical(i32 %A) {
 ; CHECK-LABEL: @masked_and_notA_slightly_optimized_logical(
-; CHECK-NEXT:    [[T0:%.*]] = icmp ugt i32 [[A:%.*]], 7
-; CHECK-NEXT:    [[MASK2:%.*]] = and i32 [[A]], 39
-; CHECK-NEXT:    [[TST2:%.*]] = icmp ne i32 [[MASK2]], [[A]]
-; CHECK-NEXT:    [[RES:%.*]] = and i1 [[T0]], [[TST2]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A:%.*]], -40
+; CHECK-NEXT:    [[TST2:%.*]] = icmp ne i32 [[TMP1]], 0
+; CHECK-NEXT:    ret i1 [[TST2]]
 ;
   %t0 = icmp uge i32 %A, 8
   %mask2 = and i32 %A, 39
   %tst2 = icmp ne i32 %mask2, %A
   %res = select i1 %t0, i1 %tst2, i1 false
   ret i1 %res
 }
 
 define i1 @masked_or_A(i32 %A) {
 ; CHECK-LABEL: @masked_or_A(
-; CHECK-NEXT:    [[MASK2:%.*]] = and i32 [[A:%.*]], 78
-; CHECK-NEXT:    [[TST2:%.*]] = icmp eq i32 [[MASK2]], [[A]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A:%.*]], -79
+; CHECK-NEXT:    [[TST2:%.*]] = icmp eq i32 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[TST2]]
 ;
   %mask1 = and i32 %A, 14
   %tst1 = icmp eq i32 %mask1, %A
   %mask2 = and i32 %A, 78
   %tst2 = icmp eq i32 %mask2, %A
   %res = or i1 %tst1, %tst2
   ret i1 %res
 }
 
 define i1 @masked_or_A_logical(i32 %A) {
 ; CHECK-LABEL: @masked_or_A_logical(
-; CHECK-NEXT:    [[MASK2:%.*]] = and i32 [[A:%.*]], 78
-; CHECK-NEXT:    [[TST2:%.*]] = icmp eq i32 [[MASK2]], [[A]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A:%.*]], -79
+; CHECK-NEXT:    [[TST2:%.*]] = icmp eq i32 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[TST2]]
 ;
   %mask1 = and i32 %A, 14
   %tst1 = icmp eq i32 %mask1, %A
   %mask2 = and i32 %A, 78
   %tst2 = icmp eq i32 %mask2, %A
   %res = select i1 %tst1, i1 true, i1 %tst2
   ret i1 %res
 }
 
 define i1 @masked_or_A_slightly_optimized(i32 %A) {
 ; CHECK-LABEL: @masked_or_A_slightly_optimized(
-; CHECK-NEXT:    [[T0:%.*]] = icmp ult i32 [[A:%.*]], 8
-; CHECK-NEXT:    [[MASK2:%.*]] = and i32 [[A]], 39
-; CHECK-NEXT:    [[TST2:%.*]] = icmp eq i32 [[MASK2]], [[A]]
-; CHECK-NEXT:    [[RES:%.*]] = or i1 [[T0]], [[TST2]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A:%.*]], -40
+; CHECK-NEXT:    [[TST2:%.*]] = icmp eq i32 [[TMP1]], 0
+; CHECK-NEXT:    ret i1 [[TST2]]
 ;
   %t0 = icmp ult i32 %A, 8
   %mask2 = and i32 %A, 39
   %tst2 = icmp eq i32 %mask2, %A
   %res = or i1 %t0, %tst2
   ret i1 %res
 }
 
 define i1 @masked_or_A_slightly_optimized_logical(i32 %A) {
 ; CHECK-LABEL: @masked_or_A_slightly_optimized_logical(
-; CHECK-NEXT:    [[T0:%.*]] = icmp ult i32 [[A:%.*]], 8
-; CHECK-NEXT:    [[MASK2:%.*]] = and i32 [[A]], 39
-; CHECK-NEXT:    [[TST2:%.*]] = icmp eq i32 [[MASK2]], [[A]]
-; CHECK-NEXT:    [[RES:%.*]] = or i1 [[T0]], [[TST2]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A:%.*]], -40
+; CHECK-NEXT:    [[TST2:%.*]] = icmp eq i32 [[TMP1]], 0
+; CHECK-NEXT:    ret i1 [[TST2]]
 ;
   %t0 = icmp ult i32 %A, 8
   %mask2 = and i32 %A, 39
   %tst2 = icmp eq i32 %mask2, %A
   %res = select i1 %t0, i1 true, i1 %tst2
   ret i1 %res
 }
 

llvm/test/Transforms/InstCombine/select.ll

;
   %storemerge = select i1 %cmp, i32 %., i32 %add
   ret i32 %storemerge
 }
 
 ; PR9454
 
 define i32 @test53(i32 %x) {
 ; CHECK-LABEL: @test53(
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 2
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[X:%.*]], -3
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP1]], 0
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i32 2, i32 1
 ; CHECK-NEXT:    ret i32 [[SEL]]
 ;
   %and = and i32 %x, 2
   %cmp = icmp eq i32 %and, %x
   %sel = select i1 %cmp, i32 2, i32 1
   ret i32 %sel
 }