[InstCombine] Generalize and-reduce pattern to handle `ne` case as well as `eq`

[mkazantsev]

Summary

Following Sanjay's proposal from discussion in D118317, this patch
generalizes and-reduce handling to fold the following pattern

icmp ne (bitcast(icmp ne (lhs, rhs)), 0)

into

icmp ne (bitcast(lhs), bitcast(rhs))

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

[mkazantsev]

Sanity check: https://alive2.llvm.org/ce/z/rDeaif

[lebedev.ri]

In D118431#3278342, @mkazantsev wrote:

Sanity check: https://alive2.llvm.org/ce/z/rDeaif

That's a yet another pattern ((x == y) != -1 --> x != y), while here you have (x != y) != 0 --> x != y,
i.e. https://alive2.llvm.org/ce/z/WDcuJ_

[lebedev.ri]

LG modulo wrong proof :)
I believe there are some more patterns like that, let me know if can't come up with them.

[mkazantsev]

I'm sure there should be more of this kind. Interestingly, analogous test for reduction-and-sext-zext-i1.ll works even w/o this change, which means we might have some other transform missing something.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

static Instruction *foldReductionIdiom(ICmpInst &I,
   if (I.getType()->isVectorTy())
     return nullptr;
   ICmpInst::Predicate OuterPred, InnerPred;
   Value *LHS, *RHS;
 
   // Match lowering of @llvm.vector.reduce.and. Turn
   ///   %vec_ne = icmp ne <8 x i8> %lhs, %rhs
   ///   %scalar_ne = bitcast <8 x i1> %vec_ne to i8
-  ///   %all_eq = icmp eq i8 %scalar_ne, 0
+  ///   %res = icmp <pred> i8 %scalar_ne, 0
   ///
   /// into
   ///
   ///   %lhs.scalar = bitcast <8 x i8> %lhs to i64
   ///   %rhs.scalar = bitcast <8 x i8> %rhs to i64
-  ///   %all_eq = icmp eq i64 %lhs.scalar, %rhs.scalar
+  ///   %res = icmp <pred> i64 %lhs.scalar, %rhs.scalar
+  ///
+  /// for <pred> in {ne, eq}.
   if (!match(&I, m_ICmp(OuterPred,
                         m_OneUse(m_BitCast(m_OneUse(
                             m_ICmp(InnerPred, m_Value(LHS), m_Value(RHS))))),
                         m_Zero())))
     return nullptr;
   auto *LHSTy = dyn_cast<FixedVectorType>(LHS->getType());
   if (!LHSTy || !LHSTy->getElementType()->isIntegerTy())
     return nullptr;
   unsigned NumBits =
       LHSTy->getNumElements() * LHSTy->getElementType()->getIntegerBitWidth();
   // TODO: Relax this to "not wider than max legal integer type"?
   if (!DL.isLegalInteger(NumBits))
     return nullptr;
 
-  // TODO: Generalize to isEquality and support other patterns.
-  if (OuterPred == ICmpInst::ICMP_EQ && InnerPred == ICmpInst::ICMP_NE) {
+  if (ICmpInst::isEquality(OuterPred) && InnerPred == ICmpInst::ICMP_NE) {
     auto *ScalarTy = Builder.getIntNTy(NumBits);
     LHS = Builder.CreateBitCast(LHS, ScalarTy, LHS->getName() + ".scalar");
     RHS = Builder.CreateBitCast(RHS, ScalarTy, RHS->getName() + ".scalar");
-    return ICmpInst::Create(Instruction::ICmp, ICmpInst::ICMP_EQ, LHS, RHS,
+    return ICmpInst::Create(Instruction::ICmp, OuterPred, LHS, RHS,
                             I.getName());
   }
 
   return nullptr;
 }
 
 Instruction *InstCombinerImpl::visitICmpInst(ICmpInst &I) {
   bool Changed = false;

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

;
   %ic = icmp eq <2 x i7> %x, %y
   %b = bitcast <2 x i1> %ic to i2
   %r = icmp ne i2 %b, -1
   ret i1 %r
 }
 
 define i1 @eq_cast_ne-1-legal-scalar(<2 x i8> %x, <2 x i8> %y) {
 ; CHECK-LABEL: @eq_cast_ne-1-legal-scalar(
-; CHECK-NEXT:    [[IC:%.*]] = icmp ne <2 x i8> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = bitcast <2 x i1> [[IC]] to i2
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i2 [[TMP1]], 0
+; CHECK-NEXT:    [[X_SCALAR:%.*]] = bitcast <2 x i8> [[X:%.*]] to i16
+; CHECK-NEXT:    [[Y_SCALAR:%.*]] = bitcast <2 x i8> [[Y:%.*]] to i16
+; CHECK-NEXT:    [[R:%.*]] = icmp ne i16 [[X_SCALAR]], [[Y_SCALAR]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %ic = icmp eq <2 x i8> %x, %y
   %b = bitcast <2 x i1> %ic to i2
   %r = icmp ne i2 %b, -1
   ret i1 %r
 }
 

llvm/test/Transforms/InstCombine/reduction-or-sext-zext-i1.ll

bb:
   %all_eq = xor i1 %any_ne, 1
   ret i1 %all_eq
 }
 
 
 define i1 @reduce_or_pointer_cast_ne(i8* %arg, i8* %arg1) {
 ; CHECK-LABEL: @reduce_or_pointer_cast_ne(
 ; CHECK-NEXT:  bb:
-; CHECK-NEXT:    [[PTR1:%.*]] = bitcast i8* [[ARG1:%.*]] to <8 x i8>*
-; CHECK-NEXT:    [[PTR2:%.*]] = bitcast i8* [[ARG:%.*]] to <8 x i8>*
-; CHECK-NEXT:    [[LHS:%.*]] = load <8 x i8>, <8 x i8>* [[PTR1]], align 8
-; CHECK-NEXT:    [[RHS:%.*]] = load <8 x i8>, <8 x i8>* [[PTR2]], align 8
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne <8 x i8> [[LHS]], [[RHS]]
-; CHECK-NEXT:    [[TMP0:%.*]] = bitcast <8 x i1> [[CMP]] to i8
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i8 [[TMP0]], 0
-; CHECK-NEXT:    ret i1 [[TMP1]]
+; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i8* [[ARG1:%.*]] to i64*
+; CHECK-NEXT:    [[LHS1:%.*]] = load i64, i64* [[TMP0]], align 8
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i8* [[ARG:%.*]] to i64*
+; CHECK-NEXT:    [[RHS2:%.*]] = load i64, i64* [[TMP1]], align 8
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i64 [[LHS1]], [[RHS2]]
+; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
 bb:
   %ptr1 = bitcast i8* %arg1 to <8 x i8>*
   %ptr2 = bitcast i8* %arg to <8 x i8>*
   %lhs = load <8 x i8>, <8 x i8>* %ptr1
   %rhs = load <8 x i8>, <8 x i8>* %ptr2
   %cmp = icmp ne <8 x i8> %lhs, %rhs
   %any_ne = call i1 @llvm.vector.reduce.or.v8i32(<8 x i1> %cmp)