[InstCombine] Canonicalize (A & B_Pow2) eq/ne B_Pow2 patterns

[goldstein.w.n]

Summary

1. A & B_Pow2 != B_Pow2 -> A & B_Pow2 == 0 https://alive2.llvm.org/ce/z/KVUej4

2. A & B_Pow2 == B_Pow2 -> A & B_Pow2 != 0 https://alive2.llvm.org/ce/z/PVv9FR

This allows the patterns to more easily be analyzed elsewhere.

[nikic]

LGTM

Simpler proof: https://alive2.llvm.org/ce/z/JQMH7m Canonical pattern for pow2 check is ctpop==1.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4791

[spatel]

llvm/test/Transforms/InstCombine/icmp-and-shift.ll

511

I like to have "negative test" comments on examples like these, so it's clear that if they somehow do change in the future, that wasn't supposed to happen.

The transform could be extended to at least some non-equality predicates in a follow-up patch:
https://alive2.llvm.org/ce/z/eig49D

[goldstein.w.n]

Make non-zero more clean

llvm/test/Transforms/InstCombine/icmp-and-shift.ll

511

I like to have "negative test" comments on examples like these, so it's clear that if they somehow do change in the future, that wasn't supposed to happen.

The transform could be extended to at least some non-equality predicates in a follow-up patch:
https://alive2.llvm.org/ce/z/eig49D

Agreed, also makes it easier to make future improvements as getting new test deps through is a pain

[goldstein.w.n]

In D141090#4030742, @nikic wrote:

LGTM

Simpler proof: https://alive2.llvm.org/ce/z/JQMH7m Canonical pattern for pow2 check is ctpop==1.

In D141090#4030742, @nikic wrote:

LGTM

Simpler proof: https://alive2.llvm.org/ce/z/JQMH7m Canonical pattern for pow2 check is ctpop==1.

Do you want me to update the commit message with link to this proof instead?

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (match(Op0, m_AShr(m_Trunc(m_Value(A)), m_SpecificInt(BitWidth - 1))) &&
       (I.getOperand(0)->hasOneUse() || I.getOperand(1)->hasOneUse())) {
     APInt C = APInt::getOneBitSet(BitWidth * 2, BitWidth - 1);
     Value *Add = Builder.CreateAdd(A, ConstantInt::get(A->getType(), C));
     return new ICmpInst(Pred == ICmpInst::ICMP_EQ ? ICmpInst::ICMP_ULT
                                                   : ICmpInst::ICMP_UGE,
                         Add, ConstantInt::get(A->getType(), C.shl(1)));
   }
 
+  // Canonicalize:
+  // Assume B_Pow2 != 0
+  // 1. A & B_Pow2 != B_Pow2 -> A & B_Pow2 == 0
+  // 2. A & B_Pow2 == B_Pow2 -> A & B_Pow2 != 0
+  if (match(Op0, m_c_And(m_Specific(Op1), m_Value())) &&
+      isKnownToBeAPowerOfTwo(Op1, /* OrZero */ false, 0, &I))
+    return new ICmpInst(CmpInst::getInversePredicate(Pred), Op0,
+                        ConstantInt::getNullValue(Op0->getType()));
+
+  if (match(Op1, m_c_And(m_Specific(Op0), m_Value())) &&
+      isKnownToBeAPowerOfTwo(Op0, /* OrZero */ false, 0, &I))
+    return new ICmpInst(CmpInst::getInversePredicate(Pred), Op1,
+                        ConstantInt::getNullValue(Op1->getType()));
+
   return nullptr;
 }
 
 static Instruction *foldICmpWithTrunc(ICmpInst &ICmp,
                                       InstCombiner::BuilderTy &Builder) {
   ICmpInst::Predicate Pred = ICmp.getPredicate();
   Value *Op0 = ICmp.getOperand(0), *Op1 = ICmp.getOperand(1);
 

llvm/test/Transforms/InstCombine/icmp-and-shift.ll

;
   %conv = zext i1 %cmp to i32
   ret i32 %conv
 }
 
 define i1 @eq_and_shl_one(i8 %x, i8 %y) {
 ; CHECK-LABEL: @eq_and_shl_one(
 ; CHECK-NEXT:    [[POW2:%.*]] = shl nuw i8 1, [[Y:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[POW2]], [[X:%.*]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[AND]], [[POW2]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[AND]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %pow2 = shl i8 1, %y
   %and = and i8 %pow2, %x
   %cmp = icmp eq i8 %and, %pow2
   ret i1 %cmp
 }
 
 define <2 x i1> @ne_and_shl_one_commute(<2 x i8> %x, <2 x i8> %y) {
 ; CHECK-LABEL: @ne_and_shl_one_commute(
 ; CHECK-NEXT:    [[POW2:%.*]] = shl nuw <2 x i8> <i8 1, i8 poison>, [[Y:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and <2 x i8> [[POW2]], [[X:%.*]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne <2 x i8> [[POW2]], [[AND]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <2 x i8> [[AND]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
   %pow2 = shl <2 x i8> <i8 1, i8 poison>, %y
   %and = and <2 x i8> %pow2, %x
   %cmp = icmp ne <2 x i8> %pow2, %and
   ret <2 x i1> %cmp
 }
 
 define i1 @ne_and_lshr_minval(i8 %px, i8 %y) {
 ; CHECK-LABEL: @ne_and_lshr_minval(
 ; CHECK-NEXT:    [[X:%.*]] = mul i8 [[PX:%.*]], [[PX]]
 ; CHECK-NEXT:    [[POW2:%.*]] = lshr i8 -128, [[Y:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X]], [[POW2]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[AND]], [[POW2]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[AND]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %x = mul i8 %px, %px ; thwart complexity-based canonicalization
   %pow2 = lshr i8 -128, %y
   %and = and i8 %x, %pow2
   %cmp = icmp ne i8 %and, %pow2
   ret i1 %cmp
 }
 
 define i1 @eq_and_lshr_minval_commute(i8 %px, i8 %y) {
 ; CHECK-LABEL: @eq_and_lshr_minval_commute(
 ; CHECK-NEXT:    [[X:%.*]] = mul i8 [[PX:%.*]], [[PX]]
 ; CHECK-NEXT:    [[POW2:%.*]] = lshr i8 -128, [[Y:%.*]]
 ; CHECK-NEXT:    call void @use(i8 [[POW2]])
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X]], [[POW2]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[POW2]], [[AND]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[AND]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %x = mul i8 %px, %px ; thwart complexity-based canonicalization
   %pow2 = lshr i8 -128, %y
   call void @use(i8 %pow2)
   %and = and i8 %x, %pow2
   call void @use(i8 %and)
   %cmp = icmp eq i8 %pow2, %and
   ret i1 %cmp
 }
 
+; Negative test: May be power of two or zero.
 define i1 @eq_and_shl_two(i8 %x, i8 %y) {
 ; CHECK-LABEL: @eq_and_shl_two(
 ; CHECK-NEXT:    [[POW2_OR_ZERO:%.*]] = shl i8 2, [[Y:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[POW2_OR_ZERO]], [[X:%.*]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[AND]], [[POW2_OR_ZERO]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %pow2_or_zero = shl i8 2, %y
   %and = and i8 %x, %pow2_or_zero
   %cmp = icmp eq i8 %and, %pow2_or_zero
   ret i1 %cmp
 }
 
+; Negative test: Wrong predicate.
 define i1 @slt_and_shl_one(i8 %x, i8 %y) {
 ; CHECK-LABEL: @slt_and_shl_one(
 ; CHECK-NEXT:    [[POW2:%.*]] = shl nuw i8 1, [[Y:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[POW2]], [[X:%.*]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[AND]], [[POW2]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %pow2 = shl i8 1, %y
   %and = and i8 %x, %pow2
   %cmp = icmp slt i8 %and, %pow2
   ret i1 %cmp
 }