[InstCombine] Improve mask detection in `foldICmpWithLowBitMaskedVal`

[goldstein.w.n]

Summary

Make recursive matcher that is able to detect a lot more patterns.
Proofs for all supported patterns: https://alive2.llvm.org/ce/z/fSQ3nZ

[nikic]

I thin this patch does too many changes at the same time. Can we separate support for the zero pattern from the recursive mask recognition?

[goldstein.w.n]

Make this commit masks only

[goldstein.w.n]

Rebase

[goldstein.w.n]

Abandoning and resubmitting on GH

llvm/include/llvm/IR/PatternMatch.h

 /// For vectors, this includes constants with undefined elements.
 inline cst_pred_ty<is_negated_power2> m_NegatedPower2() {
   return cst_pred_ty<is_negated_power2>();
 }
 inline api_pred_ty<is_negated_power2> m_NegatedPower2(const APInt *&V) {
   return V;
 }
 
+struct is_negated_power2_or_zero {
+  bool isValue(const APInt &C) { return !C || C.isNegatedPowerOf2(); }
+};
+/// Match a integer or vector negated power-of-2.
+/// For vectors, this includes constants with undefined elements.
+inline cst_pred_ty<is_negated_power2_or_zero> m_NegatedPower2OrZero() {
+  return cst_pred_ty<is_negated_power2_or_zero>();
+}
+inline api_pred_ty<is_negated_power2_or_zero>
+m_NegatedPower2OrZero(const APInt *&V) {
+  return V;
+}
+
 struct is_power2_or_zero {
   bool isValue(const APInt &C) { return !C || C.isPowerOf2(); }
 };
 /// Match an integer or vector of 0 or power-of-2 values.
 /// For vectors, this includes constants with undefined elements.
 inline cst_pred_ty<is_power2_or_zero> m_Power2OrZero() {
   return cst_pred_ty<is_power2_or_zero>();
 }

 };
 /// Match an integer or vector with only the low bit(s) set.
 /// For vectors, this includes constants with undefined elements.
 inline cst_pred_ty<is_lowbit_mask> m_LowBitMask() {
   return cst_pred_ty<is_lowbit_mask>();
 }
 inline api_pred_ty<is_lowbit_mask> m_LowBitMask(const APInt *&V) { return V; }
 
+struct is_lowbit_mask_or_zero {
+  bool isValue(const APInt &C) { return !C || C.isMask(); }
+};
+/// Match an integer or vector with only the low bit(s) set.
+/// For vectors, this includes constants with undefined elements.
+inline cst_pred_ty<is_lowbit_mask_or_zero> m_LowBitMaskOrZero() {
+  return cst_pred_ty<is_lowbit_mask_or_zero>();
+}
+inline api_pred_ty<is_lowbit_mask_or_zero> m_LowBitMaskOrZero(const APInt *&V) {
+  return V;
+}
+
 struct icmp_pred_with_threshold {
   ICmpInst::Predicate Pred;
   const APInt *Thr;
   bool isValue(const APInt &C) { return ICmpInst::compare(C, *Thr, Pred); }
 };
 /// Match an integer or vector with every element comparing 'pred' (eg/ne/...)
 /// to Threshold. For vectors, this includes constants with undefined elements.
 inline cst_pred_ty<icmp_pred_with_threshold>

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (Transform) {
     if (!Op2)
       Op2 = Builder.CreateICmp(Pred, SI->getOperand(2), RHS, I.getName());
     return SelectInst::Create(SI->getOperand(0), Op1, Op2);
   }
 
   return nullptr;
 }
 
+// Returns of V is a Mask ((X + 1) & X == 0) or ~Mask (-Pow2OrZero)
+static bool isMaskOrZero(const Value *V, bool Not, const SimplifyQuery &Q,
+                         unsigned Depth = 0) {
+  if (Not ? match(V, m_NegatedPower2OrZero()) : match(V, m_LowBitMaskOrZero()))
+    return true;
+  if (V->getType()->getScalarSizeInBits() == 1)
+    return true;
+  if (Depth++ >= MaxAnalysisRecursionDepth)
+    return false;
+  Value *X;
+  if (match(V, m_Not(m_Value(X))))
+    return isMaskOrZero(X, !Not, Q, Depth);
+  const Operator *I = dyn_cast<Operator>(V);
+  if (I == nullptr)
+    return false;
+  switch (I->getOpcode()) {
+  case Instruction::ZExt:
+    // ZExt(Mask) is a Mask.
+    return !Not && isMaskOrZero(I->getOperand(0), Not, Q, Depth);
+  case Instruction::SExt:
+    // SExt(Mask) is a Mask.
+    // SExt(~Mask) is a ~Mask.
+    return isMaskOrZero(I->getOperand(0), Not, Q, Depth);
+  case Instruction::And:
+  case Instruction::Or:
+    // Mask0 | Mask1 is a Mask.
+    // Mask0 & Mask1 is a Mask.
+    // ~Mask0 | ~Mask1 is a ~Mask.
+    // ~Mask0 & ~Mask1 is a ~Mask.
+    return isMaskOrZero(I->getOperand(1), Not, Q, Depth) &&
+           isMaskOrZero(I->getOperand(0), Not, Q, Depth);
+  case Instruction::Xor:
+    // (X ^ (X - 1)) is a Mask
+    return match(V, m_c_Xor(m_Value(X), m_Add(m_Deferred(X), m_AllOnes())));
+  case Instruction::Select:
+    // c ? Mask0 : Mask1 is a Mask.
+    return isMaskOrZero(I->getOperand(1), Not, Q, Depth) &&
+           isMaskOrZero(I->getOperand(2), Not, Q, Depth);
+  case Instruction::Shl:
+    if (Not) {
+      // (-1 >> X) << X is ~Mask
+      if (match(I->getOperand(0),
+                m_Shr(m_AllOnes(), m_Specific(I->getOperand(1)))))
+        return true;
+
+      // (~Mask) << X is a ~Mask.
+      return isMaskOrZero(I->getOperand(0), Not, Q, Depth);
+    }
+    break;
+  case Instruction::LShr:
+    if (!Not) {
+      // (-1 << X) >> X is a Mask
+      if (match(I->getOperand(0),
+                m_Shl(m_AllOnes(), m_Specific(I->getOperand(1)))))
+        return true;
+      // Mask >> X is a Mask.
+      return isMaskOrZero(I->getOperand(0), Not, Q, Depth);
+    }
+    return false;
+  case Instruction::AShr:
+    // Mask s>> X is a Mask.
+    // ~Mask s>> X is a ~Mask.
+    return isMaskOrZero(I->getOperand(0), Not, Q, Depth);
+  case Instruction::Add:
+    // Pow2 - 1 is a Mask.
+    if (!Not && match(I->getOperand(1), m_AllOnes()))
+      return isKnownToBeAPowerOfTwo(I->getOperand(0), Q.DL, /*OrZero*/ true,
+                                    Depth, Q.AC, Q.CxtI, Q.DT);
+    break;
+  case Instruction::Sub:
+    // -Pow2 is a ~Mask.
+    if (Not && match(I->getOperand(0), m_Zero()))
+      return isKnownToBeAPowerOfTwo(I->getOperand(1), Q.DL, /*OrZero*/ true,
+                                    Depth, Q.AC, Q.CxtI, Q.DT);
+    break;
+  case Instruction::Invoke:
+  case Instruction::Call: {
+    if (auto *II = dyn_cast<IntrinsicInst>(I)) {
+      switch (II->getIntrinsicID()) {
+        // min/max(Mask0, Mask1) is a Mask.
+        // min/max(~Mask0, ~Mask1) is a ~Mask.
+      case Intrinsic::umax:
+      case Intrinsic::smax:
+      case Intrinsic::umin:
+      case Intrinsic::smin:
+        return isMaskOrZero(II->getArgOperand(1), Not, Q, Depth) &&
+               isMaskOrZero(II->getArgOperand(0), Not, Q, Depth);
+
+        // In the context of masks, bitreverse(Mask) == ~Mask
+      case Intrinsic::bitreverse:
+        return isMaskOrZero(II->getArgOperand(0), !Not, Q, Depth);
+      default:
+        break;
+      }
+    }
+    break;
+  }
+  default:
+    break;
+  }
+  return false;
+}
+
 /// Some comparisons can be simplified.
 /// In this case, we are looking for comparisons that look like
 /// a check for a lossy truncation.
 /// Folds:
 ///   icmp SrcPred (x & Mask), x    to    icmp DstPred x, Mask
 /// Where Mask is some pattern that produces all-ones in low bits:
 ///    (-1 >> y)
 ///    ((-1 << y) >> y)     <- non-canonical, has extra uses
 ///   ~(-1 << y)
 ///    ((1 << y) + (-1))    <- non-canonical, has extra uses
 /// The Mask can be a constant, too.
 /// For some predicates, the operands are commutative.
 /// For others, x can only be on a specific side.
-static Value *foldICmpWithLowBitMaskedVal(ICmpInst &I,
-                                          InstCombiner::BuilderTy &Builder) {
+static Value *foldICmpWithLowBitMaskedVal(ICmpInst &I, const SimplifyQuery &Q,
+                                          InstCombiner &IC) {
+
+  Value *X, *M;
+  ICmpInst::Predicate Pred = I.getPredicate();
   ICmpInst::Predicate SrcPred;
-  Value *X, *M, *Y;
-  auto m_VariableMask = m_CombineOr(
-      m_CombineOr(m_Not(m_Shl(m_AllOnes(), m_Value())),
-                  m_Add(m_Shl(m_One(), m_Value()), m_AllOnes())),
-      m_CombineOr(m_LShr(m_AllOnes(), m_Value()),
-                  m_LShr(m_Shl(m_AllOnes(), m_Value(Y)), m_Deferred(Y))));
-  auto m_Mask = m_CombineOr(m_VariableMask, m_LowBitMask());
-  if (!match(&I, m_c_ICmp(SrcPred,
-                          m_c_And(m_CombineAnd(m_Mask, m_Value(M)), m_Value(X)),
-                          m_Deferred(X))))
-    return nullptr;
+  bool NeedsNot = false;
 
+  auto CheckMask = [&](Value *V, bool Not) {
+    if (!ICmpInst::isSigned(Pred))
+      return isMaskOrZero(V, Not, Q);
+    return Not ? match(V, m_NegatedPower2OrZero())
+               : match(V, m_LowBitMaskOrZero());
+  };
+
+  auto TryMatch = [&](unsigned OpNo) {
+    SrcPred = Pred;
+    if (match(I.getOperand(OpNo),
+              m_c_And(m_Specific(I.getOperand(1 - OpNo)), m_Value(M)))) {
+      X = I.getOperand(1 - OpNo);
+      if (OpNo)
+        SrcPred = ICmpInst::getSwappedPredicate(Pred);
+      return CheckMask(M, /*Not*/ false);
+    }
+    return false;
+  };
+
+  if (!TryMatch(0) && !TryMatch(1))
+    return nullptr;
   ICmpInst::Predicate DstPred;
   switch (SrcPred) {
   case ICmpInst::Predicate::ICMP_EQ:
     //  x & (-1 >> y) == x    ->    x u<= (-1 >> y)
     DstPred = ICmpInst::Predicate::ICMP_ULE;
     break;
   case ICmpInst::Predicate::ICMP_NE:
     //  x & (-1 >> y) != x    ->    x u> (-1 >> y)
for (unsigned i = 0, e = OpVTy->getNumElements(); i != e; ++i) {
         SafeReplacementConstant = VecC->getAggregateElement(i);
         break;
       }
     }
     assert(SafeReplacementConstant && "Failed to find undef replacement");
     M = Constant::replaceUndefsWith(VecC, SafeReplacementConstant);
   }
 
-  return Builder.CreateICmp(DstPred, X, M);
+  if (NeedsNot)
+    M = IC.Builder.CreateNot(M);
+  return IC.Builder.CreateICmp(DstPred, X, M);
 }
 
 /// Some comparisons can be simplified.
 /// In this case, we are looking for comparisons that look like
 /// a check for a lossy signed truncation.
 /// Folds:   (MaskedBits is a constant.)
 ///   ((%x << MaskedBits) a>> MaskedBits) SrcPred %x
 /// Into:
if (!ICmpInst::isSigned(Pred)) {
     else if (match(Op1, m_Shl(m_Specific(Op0), m_One())))
       return new ICmpInst(ICmpInst::getSignedPredicate(Pred),
                           Constant::getNullValue(Op0->getType()), Op0);
   }
 
   if (Value *V = foldMultiplicationOverflowCheck(I))
     return replaceInstUsesWith(I, V);
 
-  if (Value *V = foldICmpWithLowBitMaskedVal(I, Builder))
+  if (Value *V = foldICmpWithLowBitMaskedVal(I, Q, *this))
     return replaceInstUsesWith(I, V);
 
   if (Instruction *R = foldICmpAndXX(I, Q, *this))
     return R;
 
   if (Value *V = foldICmpWithTruncSignExtendedVal(I, Builder))
     return replaceInstUsesWith(I, V);
 

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:    [[TMP1:%.*]] = and <2 x i8> [[X:%.*]], <i8 -4, i8 -1>
-; CHECK-NEXT:    [[RET:%.*]] = icmp eq <2 x i8> [[TMP1]], zeroinitializer
+; CHECK-NEXT:    [[RET:%.*]] = icmp ult <2 x i8> [[X:%.*]], <i8 4, i8 1>
 ; 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(

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:    [[TMP1:%.*]] = and <2 x i8> [[X:%.*]], <i8 -4, i8 -1>
-; CHECK-NEXT:    [[RET:%.*]] = icmp ne <2 x i8> [[TMP1]], zeroinitializer
+; CHECK-NEXT:    [[RET:%.*]] = icmp ugt <2 x i8> [[X:%.*]], <i8 3, i8 0>
 ; 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(

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

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

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

;
   %tmp0 = and <2 x i8> %x, <i8 3, i8 15> ; doesn't have to be splat.
   %ret = icmp sgt <2 x i8> %x, %tmp0
   ret <2 x i1> %ret
 }
 
 define <2 x i1> @p2_vec_nonsplat_edgecase() {
 ; CHECK-LABEL: @p2_vec_nonsplat_edgecase(
 ; CHECK-NEXT:    [[X:%.*]] = call <2 x i8> @gen2x8()
-; CHECK-NEXT:    [[TMP0:%.*]] = and <2 x i8> [[X]], <i8 3, i8 0>
-; CHECK-NEXT:    [[RET:%.*]] = icmp sgt <2 x i8> [[X]], [[TMP0]]
+; CHECK-NEXT:    [[RET:%.*]] = icmp sgt <2 x i8> [[X]], <i8 3, i8 0>
 ; 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 sgt <2 x i8> %x, %tmp0
   ret <2 x i1> %ret
 }
 

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

;
   %tmp0 = and <2 x i8> %x, <i8 3, i8 15> ; doesn't have to be splat.
   %ret = icmp sle <2 x i8> %x, %tmp0
   ret <2 x i1> %ret
 }
 
 define <2 x i1> @p2_vec_nonsplat_edgecase() {
 ; CHECK-LABEL: @p2_vec_nonsplat_edgecase(
 ; CHECK-NEXT:    [[X:%.*]] = call <2 x i8> @gen2x8()
-; CHECK-NEXT:    [[TMP0:%.*]] = and <2 x i8> [[X]], <i8 3, i8 0>
-; CHECK-NEXT:    [[RET:%.*]] = icmp sle <2 x i8> [[X]], [[TMP0]]
+; CHECK-NEXT:    [[RET:%.*]] = icmp slt <2 x i8> [[X]], <i8 4, i8 1>
 ; 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 sle <2 x i8> %x, %tmp0
   ret <2 x i1> %ret
 }
 

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

 ;
   %tmp0 = and <2 x i8> %x, <i8 3, i8 15> ; doesn't have to be splat.
   %ret = icmp slt <2 x i8> %tmp0, %x
   ret <2 x i1> %ret
 }
 
 define <2 x i1> @p2_vec_nonsplat_edgecase(<2 x i8> %x) {
 ; CHECK-LABEL: @p2_vec_nonsplat_edgecase(
-; CHECK-NEXT:    [[TMP0:%.*]] = and <2 x i8> [[X:%.*]], <i8 3, i8 0>
-; CHECK-NEXT:    [[RET:%.*]] = icmp slt <2 x i8> [[TMP0]], [[X]]
+; CHECK-NEXT:    [[RET:%.*]] = icmp sgt <2 x i8> [[X:%.*]], <i8 3, i8 0>
 ; CHECK-NEXT:    ret <2 x i1> [[RET]]
 ;
   %tmp0 = and <2 x i8> %x, <i8 3, i8 0>
   %ret = icmp slt <2 x i8> %tmp0, %x
   ret <2 x i1> %ret
 }
 
 define <3 x i1> @p3_vec_splat_undef(<3 x i8> %x) {

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:    [[TMP1:%.*]] = and <2 x i8> [[X:%.*]], <i8 -4, i8 -1>
-; CHECK-NEXT:    [[RET:%.*]] = icmp eq <2 x i8> [[TMP1]], zeroinitializer
+; CHECK-NEXT:    [[RET:%.*]] = icmp ult <2 x i8> [[X:%.*]], <i8 4, i8 1>
 ; 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(

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:    [[TMP1:%.*]] = and <2 x i8> [[X]], <i8 -4, i8 -1>
-; CHECK-NEXT:    [[RET:%.*]] = icmp ne <2 x i8> [[TMP1]], zeroinitializer
+; CHECK-NEXT:    [[RET:%.*]] = icmp ugt <2 x i8> [[X]], <i8 3, i8 0>
 ; 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() {

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:    [[TMP1:%.*]] = and <2 x i8> [[X]], <i8 -4, i8 -1>
-; CHECK-NEXT:    [[RET:%.*]] = icmp eq <2 x i8> [[TMP1]], zeroinitializer
+; CHECK-NEXT:    [[RET:%.*]] = icmp ult <2 x i8> [[X]], <i8 4, i8 1>
 ; 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() {

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:    [[TMP1:%.*]] = and <2 x i8> [[X:%.*]], <i8 -4, i8 -1>
-; CHECK-NEXT:    [[RET:%.*]] = icmp ne <2 x i8> [[TMP1]], zeroinitializer
+; CHECK-NEXT:    [[RET:%.*]] = icmp ugt <2 x i8> [[X:%.*]], <i8 3, i8 0>
 ; 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) {

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

 declare i8 @llvm.bitreverse.i8(i8)
 declare void @use.i8(i8)
 declare void @use.i16(i16)
 define i1 @src_is_mask_zext(i16 %x_in, i8 %y) {
 ; CHECK-LABEL: @src_is_mask_zext(
 ; CHECK-NEXT:    [[X:%.*]] = xor i16 [[X_IN:%.*]], 123
 ; CHECK-NEXT:    [[M_IN:%.*]] = lshr i8 -1, [[Y:%.*]]
 ; CHECK-NEXT:    [[MASK:%.*]] = zext i8 [[M_IN]] to i16
-; CHECK-NEXT:    [[AND:%.*]] = and i16 [[X]], [[MASK]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i16 [[AND]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ule i16 [[X]], [[MASK]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = xor i16 %x_in, 123
   %m_in = lshr i8 -1, %y
   %mask = zext i8 %m_in to i16
 
   %and = and i16 %x, %mask
   %r = icmp eq i16 %and, %x

 }
 
 define i1 @src_is_mask_and(i8 %x_in, i8 %y, i8 %z) {
 ; CHECK-LABEL: @src_is_mask_and(
 ; CHECK-NEXT:    [[X:%.*]] = xor i8 [[X_IN:%.*]], 123
 ; CHECK-NEXT:    [[MY:%.*]] = lshr i8 7, [[Y:%.*]]
 ; CHECK-NEXT:    [[MZ:%.*]] = lshr i8 -1, [[Z:%.*]]
 ; CHECK-NEXT:    [[MASK:%.*]] = and i8 [[MY]], [[MZ]]
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X]], [[MASK]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[X]], [[AND]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ule i8 [[X]], [[MASK]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = xor i8 %x_in, 123
   %my = ashr i8 7, %y
   %mz = lshr i8 -1, %z
   %mask = and i8 %my, %mz
 
   %and = and i8 %x, %mask
;
   ret i1 %r
 }
 
 define i1 @src_is_mask_or(i8 %x_in, i8 %y) {
 ; CHECK-LABEL: @src_is_mask_or(
 ; CHECK-NEXT:    [[X:%.*]] = xor i8 [[X_IN:%.*]], 123
 ; CHECK-NEXT:    [[MY:%.*]] = lshr i8 -1, [[Y:%.*]]
 ; CHECK-NEXT:    [[MASK:%.*]] = and i8 [[MY]], 7
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[MASK]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[X]], [[AND]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ule i8 [[X]], [[MASK]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = xor i8 %x_in, 123
   %my = lshr i8 -1, %y
   %mask = and i8 %my, 7
 
   %and = and i8 %mask, %x
   %r = icmp eq i8 %x, %and
   ret i1 %r
 }
 
 define i1 @src_is_mask_xor(i8 %x_in, i8 %y) {
 ; CHECK-LABEL: @src_is_mask_xor(
 ; CHECK-NEXT:    [[X:%.*]] = xor i8 [[X_IN:%.*]], 123
 ; CHECK-NEXT:    [[Y_M1:%.*]] = add i8 [[Y:%.*]], -1
 ; CHECK-NEXT:    [[MASK:%.*]] = xor i8 [[Y_M1]], [[Y]]
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X]], [[MASK]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[AND]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[X]], [[MASK]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = xor i8 %x_in, 123
   %y_m1 = add i8 %y, -1
   %mask = xor i8 %y, %y_m1
   %and = and i8 %x, %mask
   %r = icmp ne i8 %and, %x
   ret i1 %r

 }
 
 define i1 @src_is_mask_select(i8 %x_in, i8 %y, i1 %cond) {
 ; CHECK-LABEL: @src_is_mask_select(
 ; CHECK-NEXT:    [[X:%.*]] = xor i8 [[X_IN:%.*]], 123
 ; CHECK-NEXT:    [[Y_M1:%.*]] = add i8 [[Y:%.*]], -1
 ; CHECK-NEXT:    [[YMASK:%.*]] = xor i8 [[Y_M1]], [[Y]]
 ; CHECK-NEXT:    [[MASK:%.*]] = select i1 [[COND:%.*]], i8 [[YMASK]], i8 15
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[MASK]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[AND]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[X]], [[MASK]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = xor i8 %x_in, 123
   %y_m1 = add i8 %y, -1
   %ymask = xor i8 %y, %y_m1
   %mask = select i1 %cond, i8 %ymask, i8 15
 
   %and = and i8 %mask, %x

 
 define i1 @src_is_mask_lshr(i8 %x_in, i8 %y, i8 %z, i1 %cond) {
 ; CHECK-LABEL: @src_is_mask_lshr(
 ; CHECK-NEXT:    [[X:%.*]] = xor i8 [[X_IN:%.*]], 123
 ; CHECK-NEXT:    [[Y_M1:%.*]] = add i8 [[Y:%.*]], -1
 ; CHECK-NEXT:    [[YMASK:%.*]] = xor i8 [[Y_M1]], [[Y]]
 ; CHECK-NEXT:    [[SMASK:%.*]] = select i1 [[COND:%.*]], i8 [[YMASK]], i8 15
 ; CHECK-NEXT:    [[MASK:%.*]] = lshr i8 [[SMASK]], [[Z:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[MASK]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[X]], [[AND]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[X]], [[MASK]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = xor i8 %x_in, 123
   %y_m1 = add i8 %y, -1
   %ymask = xor i8 %y, %y_m1
   %smask = select i1 %cond, i8 %ymask, i8 15
   %mask = lshr i8 %smask, %z
   %and = and i8 %mask, %x
   %r = icmp ne i8 %x, %and
   ret i1 %r
 }
 
 define i1 @src_is_mask_ashr(i8 %x_in, i8 %y, i8 %z, i1 %cond) {
 ; CHECK-LABEL: @src_is_mask_ashr(
 ; CHECK-NEXT:    [[X:%.*]] = xor i8 [[X_IN:%.*]], 123
 ; CHECK-NEXT:    [[Y_M1:%.*]] = add i8 [[Y:%.*]], -1
 ; CHECK-NEXT:    [[YMASK:%.*]] = xor i8 [[Y_M1]], [[Y]]
 ; CHECK-NEXT:    [[SMASK:%.*]] = select i1 [[COND:%.*]], i8 [[YMASK]], i8 15
 ; CHECK-NEXT:    [[MASK:%.*]] = ashr i8 [[SMASK]], [[Z:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X]], [[MASK]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[AND]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[X]], [[MASK]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = xor i8 %x_in, 123
   %y_m1 = add i8 %y, -1
   %ymask = xor i8 %y, %y_m1
   %smask = select i1 %cond, i8 %ymask, i8 15
   %mask = ashr i8 %smask, %z
   %and = and i8 %x, %mask
   %r = icmp ult i8 %and, %x
   ret i1 %r
 }
 
 define i1 @src_is_mask_p2_m1(i8 %x_in, i8 %y) {
 ; CHECK-LABEL: @src_is_mask_p2_m1(
 ; CHECK-NEXT:    [[X:%.*]] = xor i8 [[X_IN:%.*]], 123
 ; CHECK-NEXT:    [[P2ORZ:%.*]] = shl i8 2, [[Y:%.*]]
 ; CHECK-NEXT:    [[MASK:%.*]] = add i8 [[P2ORZ]], -1
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[MASK]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[AND]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[X]], [[MASK]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = xor i8 %x_in, 123
   %p2orz = shl i8 2, %y
   %mask = add i8 %p2orz, -1
   %and = and i8 %mask, %x
   %r = icmp ult i8 %and, %x
   ret i1 %r
 }
 
 define i1 @src_is_mask_umax(i8 %x_in, i8 %y) {
 ; CHECK-LABEL: @src_is_mask_umax(
 ; CHECK-NEXT:    [[X:%.*]] = xor i8 [[X_IN:%.*]], 123
 ; CHECK-NEXT:    [[Y_M1:%.*]] = add i8 [[Y:%.*]], -1
 ; CHECK-NEXT:    [[YMASK:%.*]] = xor i8 [[Y_M1]], [[Y]]
 ; CHECK-NEXT:    [[MASK:%.*]] = call i8 @llvm.umax.i8(i8 [[YMASK]], i8 3)
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X]], [[MASK]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[AND]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[X]], [[MASK]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = xor i8 %x_in, 123
   %y_m1 = add i8 %y, -1
   %ymask = xor i8 %y, %y_m1
   %mask = call i8 @llvm.umax.i8(i8 %ymask, i8 3)
 
   %and = and i8 %x, %mask
   %r = icmp ugt i8 %x, %and
   ret i1 %r
 }
 
 define i1 @src_is_mask_umin(i8 %x_in, i8 %y, i8 %z) {
 ; CHECK-LABEL: @src_is_mask_umin(
 ; CHECK-NEXT:    [[X:%.*]] = xor i8 [[X_IN:%.*]], 123
 ; CHECK-NEXT:    [[Y_M1:%.*]] = add i8 [[Y:%.*]], -1
 ; CHECK-NEXT:    [[YMASK:%.*]] = xor i8 [[Y_M1]], [[Y]]
 ; CHECK-NEXT:    [[ZMASK:%.*]] = lshr i8 15, [[Z:%.*]]
 ; CHECK-NEXT:    [[MASK:%.*]] = call i8 @llvm.umin.i8(i8 [[YMASK]], i8 [[ZMASK]])
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[MASK]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[AND]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[X]], [[MASK]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = xor i8 %x_in, 123
   %y_m1 = add i8 %y, -1
   %ymask = xor i8 %y, %y_m1
   %zmask = lshr i8 15, %z
   %mask = call i8 @llvm.umin.i8(i8 %ymask, i8 %zmask)
 

 }
 
 define i1 @src_is_mask_smax(i8 %x_in, i8 %y) {
 ; CHECK-LABEL: @src_is_mask_smax(
 ; CHECK-NEXT:    [[X:%.*]] = xor i8 [[X_IN:%.*]], 123
 ; CHECK-NEXT:    [[Y_M1:%.*]] = add i8 [[Y:%.*]], -1
 ; CHECK-NEXT:    [[YMASK:%.*]] = xor i8 [[Y_M1]], [[Y]]
 ; CHECK-NEXT:    [[MASK:%.*]] = call i8 @llvm.smax.i8(i8 [[YMASK]], i8 -1)
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X]], [[MASK]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[AND]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ule i8 [[X]], [[MASK]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = xor i8 %x_in, 123
   %y_m1 = add i8 %y, -1
   %ymask = xor i8 %y, %y_m1
   %mask = call i8 @llvm.smax.i8(i8 %ymask, i8 -1)
 
   %and = and i8 %x, %mask
   %r = icmp uge i8 %and, %x
   ret i1 %r
 }
 
 define i1 @src_is_mask_smin(i8 %x_in, i8 %y) {
 ; CHECK-LABEL: @src_is_mask_smin(
 ; CHECK-NEXT:    [[X:%.*]] = xor i8 [[X_IN:%.*]], 123
 ; CHECK-NEXT:    [[Y_M1:%.*]] = add i8 [[Y:%.*]], -1
 ; CHECK-NEXT:    [[YMASK:%.*]] = xor i8 [[Y_M1]], [[Y]]
 ; CHECK-NEXT:    [[MASK:%.*]] = call i8 @llvm.smin.i8(i8 [[YMASK]], i8 0)
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[MASK]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[AND]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ule i8 [[X]], [[MASK]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = xor i8 %x_in, 123
   %y_m1 = add i8 %y, -1
   %ymask = xor i8 %y, %y_m1
   %mask = call i8 @llvm.smin.i8(i8 %ymask, i8 0)
 
   %and = and i8 %mask, %x
   %r = icmp uge i8 %and, %x
   ret i1 %r
 }
 
 define i1 @src_is_mask_bitreverse_not_mask(i8 %x_in, i8 %y) {
 ; CHECK-LABEL: @src_is_mask_bitreverse_not_mask(
 ; CHECK-NEXT:    [[X:%.*]] = xor i8 [[X_IN:%.*]], 123
 ; CHECK-NEXT:    [[NMASK:%.*]] = shl i8 -1, [[Y:%.*]]
 ; CHECK-NEXT:    [[MASK:%.*]] = call i8 @llvm.bitreverse.i8(i8 [[NMASK]])
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X]], [[MASK]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[AND]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ule i8 [[X]], [[MASK]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = xor i8 %x_in, 123
   %nmask = shl i8 -1, %y
   %mask = call i8 @llvm.bitreverse.i8(i8 %nmask)
 
   %and = and i8 %x, %mask
   %r = icmp ule i8 %x, %and
   ret i1 %r
 }
 
 define i1 @src_is_notmask_sext(i16 %x_in, i8 %y) {
 ; CHECK-LABEL: @src_is_notmask_sext(
 ; CHECK-NEXT:    [[X:%.*]] = xor i16 [[X_IN:%.*]], 123
 ; CHECK-NEXT:    [[M_IN:%.*]] = shl i8 -8, [[Y:%.*]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i8 [[M_IN]], -1
 ; CHECK-NEXT:    [[MASK:%.*]] = sext i8 [[TMP1]] to i16
-; CHECK-NEXT:    [[AND:%.*]] = and i16 [[X]], [[MASK]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i16 [[AND]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ule i16 [[X]], [[MASK]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = xor i16 %x_in, 123
   %m_in = shl i8 -8, %y
   %nmask = sext i8 %m_in to i16
   %mask = xor i16 %nmask, -1
   %and = and i16 %mask, %x
   %r = icmp ule i16 %x, %and

 
 define i1 @src_is_notmask_ashr(i16 %x_in, i8 %y, i16 %z) {
 ; CHECK-LABEL: @src_is_notmask_ashr(
 ; CHECK-NEXT:    [[X:%.*]] = xor i16 [[X_IN:%.*]], 123
 ; CHECK-NEXT:    [[M_IN:%.*]] = shl i8 -32, [[Y:%.*]]
 ; CHECK-NEXT:    [[NMASK:%.*]] = sext i8 [[M_IN]] to i16
 ; CHECK-NEXT:    [[NMASK_SHR:%.*]] = ashr i16 [[NMASK]], [[Z:%.*]]
 ; CHECK-NEXT:    [[MASK:%.*]] = xor i16 [[NMASK_SHR]], -1
-; CHECK-NEXT:    [[AND:%.*]] = and i16 [[X]], [[MASK]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i16 [[X]], [[AND]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ule i16 [[X]], [[MASK]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = xor i16 %x_in, 123
   %m_in = shl i8 -32, %y
   %nmask = sext i8 %m_in to i16
   %nmask_shr = ashr i16 %nmask, %z
   %mask = xor i16 %nmask_shr, -1
   %and = and i16 %x, %mask