[InstCombine] Optimize shift+and+xor conversion pattern to simple comparison

[bcl5980]

Summary

if C1 and C2 are pow2:

((C1 << X) & C2) ^ C2 --> (X != (Log2(C2)-Log2(C1)) ? C2 : 0

https://alive2.llvm.org/ce/z/vU9o4C

if C1 and C2 are pow2:

((C1 >> X) & C2) ^ C2 --> (X != (Log2(C1)-Log2(C2)) ? C2 : 0

https://alive2.llvm.org/ce/z/kr6pbR

[spatel]

llvm/test/Transforms/InstCombine/and.ll

1893

I don't see a good reason to canonicalize this to icmp+select, but leave the previous test as shift+and.

We discussed transforming the simpler pattern starting with mask-by-power-of-2 in an earlier patch. I drafted a patch for that already and didn't notice any regressions. I will clean that up and post it for review.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (match(Op1, m_APInt(RHSC))) {
         return BinaryOperator::CreateLShr(NotX, ConstantInt::get(Ty, *C));
       }
       // TODO: We could handle 'ashr' here as well. That would be matching
       //       a 'not' op and moving it before the shift. Doing that requires
       //       preventing the inverse fold in canShiftBinOpWithConstantRHS().
     }
   }
 
+  if (match(Op1, m_Power2())) {
+    Constant *C1, *C2 = cast<Constant>(Op1);
+    Value *X;
+    // if C1 and C2 are pow2:
+    // ((C1 << X) & C2) ^ C2 --> (X != (Log2(C2)-Log2(C1)) ? C2 : 0
+    if (match(Op0, m_OneUse(m_And(m_Shl(m_ImmConstant(C1), m_Value(X)),
+                                  m_Specific(Op1)))) &&
+        match(C1, m_Power2())) {
+      Constant *CmpC = ConstantExpr::getSub(ConstantExpr::getExactLogBase2(C2),
+                                            ConstantExpr::getExactLogBase2(C1));
+      Value *ICmp = Builder.CreateICmpNE(X, CmpC);
+      return SelectInst::Create(ICmp, Op1, Constant::getNullValue(Ty));
+    }
+    // if C1 and C2 are pow2:
+    // ((C1 >> X) & C2) ^ C2 --> (X != (Log2(C1)-Log2(C2)) ? C2 : 0
+    if (match(Op0, m_OneUse(m_And(m_LShr(m_ImmConstant(C1), m_Value(X)),
+                                  m_Specific(Op1)))) &&
+        match(C1, m_Power2())) {
+      Constant *CmpC = ConstantExpr::getSub(ConstantExpr::getExactLogBase2(C1),
+                                            ConstantExpr::getExactLogBase2(C2));
+      Value *ICmp = Builder.CreateICmpNE(X, CmpC);
+      return SelectInst::Create(ICmp, Op1, Constant::getNullValue(Ty));
+    }
+  }
+
   // FIXME: This should not be limited to scalar (pull into APInt match above).
   {
     Value *X;
     ConstantInt *C1, *C2, *C3;
     // ((X^C1) >> C2) ^ C3 -> (X>>C2) ^ ((C1>>C2)^C3)
     if (match(Op1, m_ConstantInt(C3)) &&
         match(Op0, m_LShr(m_Xor(m_Value(X), m_ConstantInt(C1)),
                           m_ConstantInt(C2))) &&

llvm/test/Transforms/InstCombine/and.ll

 ; CHECK-NEXT:    ret i16 [[R]]
 ;
   %shl = shl i16 16, %x
   %lshr = lshr i16 %shl, 3
   %r = and i16 %lshr, 8
   ret i16 %r
 }
 
-; TODO: this pattern can be transform to icmp+select
-
 define i16 @shl_lshr_pow2_not_const_case2(i16 %x) {
 ; CHECK-LABEL: @shl_lshr_pow2_not_const_case2(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i16 2, [[X:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i16 [[TMP1]], 8
-; CHECK-NEXT:    [[R:%.*]] = xor i16 [[AND]], 8
+; CHECK-NEXT:    [[DOTNOT:%.*]] = icmp eq i16 [[X:%.*]], 2
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[DOTNOT]], i16 0, i16 8
 ; CHECK-NEXT:    ret i16 [[R]]
 ;
   %shl = shl i16 16, %x
   %lshr = lshr i16 %shl, 3
   %and = and i16 %lshr, 8
   %r   = xor i16 %and, 8
   ret i16 %r
 }

 ; CHECK-NEXT:    ret i16 [[R]]
 ;
   %lshr1 = lshr i16 256, %x
   %shl = shl i16 %lshr1, 2
   %r = and i16 %shl, 8
   ret i16 %r
 }
 
-; TODO: this pattern can be transform to icmp+select
-
 define i16 @lshr_shl_pow2_const_xor(i16 %x) {
 ; CHECK-LABEL: @lshr_shl_pow2_const_xor(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i16 1024, [[X:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i16 [[TMP1]], 8
-; CHECK-NEXT:    [[R:%.*]] = xor i16 [[AND]], 8
+; CHECK-NEXT:    [[DOTNOT:%.*]] = icmp eq i16 [[X:%.*]], 7
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[DOTNOT]], i16 0, i16 8
 ; CHECK-NEXT:    ret i16 [[R]]
 ;
   %lshr1 = lshr i16 256, %x
   %shl = shl i16 %lshr1, 2
   %and = and i16 %shl, 8
   %r = xor i16 %and, 8
   ret i16 %r
 }

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

;
   %and  = and <2 x i32> %lshr, <i32 4, i32 4>
   %cmp  = icmp ne <2 x i32> %and, <i32 0, i32 0>
   %conv = zext <2 x i1> %cmp to <2 x i32>
   ret <2 x i32> %conv
 }
 
 define i32 @icmp_eq_and_pow2_lshr_pow2(i32 %0) {
 ; CHECK-LABEL: @icmp_eq_and_pow2_lshr_pow2(
-; CHECK-NEXT:    [[AND:%.*]] = lshr i32 2, [[TMP0:%.*]]
-; CHECK-NEXT:    [[AND_LOBIT:%.*]] = and i32 [[AND]], 1
-; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[AND_LOBIT]], 1
+; CHECK-NEXT:    [[DOTNOT:%.*]] = icmp ne i32 [[TMP0:%.*]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i1 [[DOTNOT]] to i32
 ; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %lshr = lshr i32 8, %0
   %and  = and i32 %lshr, 4
   %cmp  = icmp eq i32 %and, 0
   %conv = zext i1 %cmp to i32
   ret i32 %conv
 }
 
 define i32 @icmp_eq_and_pow2_lshr_pow2_case2(i32 %0) {
 ; CHECK-LABEL: @icmp_eq_and_pow2_lshr_pow2_case2(
 ; CHECK-NEXT:    ret i32 1
 ;
   %lshr = lshr i32 4, %0
   %and  = and i32 %lshr, 8
   %cmp  = icmp eq i32 %and, 0
   %conv = zext i1 %cmp to i32
   ret i32 %conv
 }
 
 define <2 x i32> @icmp_eq_and_pow2_lshr_pow2_vec(<2 x i32> %0) {
 ; CHECK-LABEL: @icmp_eq_and_pow2_lshr_pow2_vec(
-; CHECK-NEXT:    [[AND:%.*]] = lshr <2 x i32> <i32 2, i32 2>, [[TMP0:%.*]]
-; CHECK-NEXT:    [[AND_LOBIT:%.*]] = and <2 x i32> [[AND]], <i32 1, i32 1>
-; CHECK-NEXT:    [[TMP2:%.*]] = xor <2 x i32> [[AND_LOBIT]], <i32 1, i32 1>
+; CHECK-NEXT:    [[DOTNOT:%.*]] = icmp ne <2 x i32> [[TMP0:%.*]], <i32 1, i32 1>
+; CHECK-NEXT:    [[TMP2:%.*]] = zext <2 x i1> [[DOTNOT]] to <2 x i32>
 ; CHECK-NEXT:    ret <2 x i32> [[TMP2]]
 ;
   %lshr = lshr <2 x i32> <i32 8, i32 8>, %0
   %and  = and <2 x i32> %lshr, <i32 4, i32 4>
   %cmp  = icmp eq <2 x i32> %and, <i32 0, i32 0>
   %conv = zext <2 x i1> %cmp to <2 x i32>
   ret <2 x i32> %conv
 }
 
 define i32 @icmp_ne_and_pow2_lshr_pow2(i32 %0) {
 ; CHECK-LABEL: @icmp_ne_and_pow2_lshr_pow2(
-; CHECK-NEXT:    [[AND:%.*]] = lshr i32 2, [[TMP0:%.*]]
-; CHECK-NEXT:    [[AND_LOBIT:%.*]] = and i32 [[AND]], 1
-; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[AND_LOBIT]], 1
+; CHECK-NEXT:    [[DOTNOT:%.*]] = icmp ne i32 [[TMP0:%.*]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i1 [[DOTNOT]] to i32
 ; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %lshr = lshr i32 8, %0
   %and  = and i32 %lshr, 4
   %cmp  = icmp eq i32 %and, 0
   %conv = zext i1 %cmp to i32
   ret i32 %conv
 }