[VectorCombine] Fold vector.reduce.OP(F(X)) == 0 -> OP(X) == 0 by SavchenkoValeriy · Pull Request #173069 · llvm/llvm-project

SavchenkoValeriy · 2025-12-19T18:10:43Z

This commit introduces a pattern to do the following fold:

vector.reduce.OP f(X_i) == 0 -> vector.reduce.OP X_i == 0

In order to decide on this fold, we use the following properties:

OP X_i == 0 <=> \forall i \in [1, N] X_i == 0 1'. OP X_i == 0 <=> \exists j \in [1, N] X_j == 0
f(x) == 0 <=> x == 0

From 1 and 2 (or 1' and 2), we can infer that

OP f(X_i) == 0 <=> OP X_i == 0.

For some of the OP's and f's, we need to have domain constraints on X to ensure properties 1 (or 1') and 2.

In this change we support the following operations f:

f(x) = shl nuw x, y for arbitrary y
f(x) = mul nuw x, c for defined c != 0
f(x) = zext x
f(x) = sext x
f(x) = neg x

And the following reductions OP:

a. OR X_i - has property 1 for every X
b. UMAX X_i - has property 1 for every X
c. UMIN X_i - has property 1' for every X
d. SMAX X_i - has property 1 for X >= 0
e. SMIN X_i - has property 1' for X >= 0
f. ADD X_i - has property 1 for X >= 0 && ADD X_i doesn't sign wrap

The matrix of Alive2 proofs for every pair of {f,OP}:

OP\f	zext	sext	neg	mul	shl
or	proof	proof	proof	proof	proof
umin	proof	proof	proof	proof	proof
umax	proof	proof	proof	proof	proof
smin	proof	proof	—	proof	proof
smax	proof	proof	—	proof	proof
add	proof	proof	—	proof	proof

Proofs for known bits:

Leading zeros - 4vi32, 16vi8
Leading ones - 4vi16, v16i8

llvmbot · 2025-12-19T18:11:13Z

@llvm/pr-subscribers-llvm-ir
@llvm/pr-subscribers-vectorizers
@llvm/pr-subscribers-llvm-analysis

@llvm/pr-subscribers-llvm-transforms

Author: Valeriy Savchenko (SavchenkoValeriy)

Changes

This commit introduces a pattern to do the following fold:

vector.reduce.OP f(X_i) == 0 -> vector.reduce.OP X_i == 0

In order to decide on this fold, we use the following properties:

OP X_i == 0 <=> \forall i \in [1, N] X_i == 0 1'. OP X_i == 0 <=> \exists j \in [1, N] X_j == 0
f(x) == 0 <=> x == 0

From 1 and 2 (or 1' and 2), we can infer that

OP f(X_i) == 0 <=> OP X_i == 0.

For some of the OP's and f's, we need to have domain constraints on X to ensure properties 1 (or 1') and 2.

In this change we support the following operations f:

f(x) = shl nuw x, y for arbitrary y
f(x) = mul nuw x, c for defined c != 0
f(x) = zext x
f(x) = sext x
f(x) = neg x

And the following reductions OP:

a. OR X_i - has property 1 for every X
b. UMAX X_i - has property 1 for every X
c. UMIN X_i - has property 1' for every X
d. SMAX X_i - has property 1 for X >= 0
e. SMIN X_i - has property 1' for X >= 0
f. ADD X_i - has property 1 for X >= 0 && ADD X_i doesn't sign wrap

The matrix of Alive2 proofs for every pair of {f,OP}:

OP\f	zext	sext	neg	mul	shl
or	proof	proof	proof	proof	proof
umin	proof	proof	proof	proof	proof
umax	proof	proof	proof	proof	proof
smin	proof	proof	—	proof	proof
smax	proof	proof	—	proof	proof
add	proof	proof	—	proof	proof

Proofs for known bits:

Leading zeros - 4vi32, 16vi8
Leading ones - 4vi16, v16i8

Patch is 41.25 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/173069.diff

5 Files Affected:

(modified) llvm/lib/Analysis/ValueTracking.cpp (+38)
(modified) llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp (+147)
(modified) llvm/lib/Transforms/InstCombine/InstCombineInternal.h (+1)
(added) llvm/test/Transforms/InstCombine/icmp-vector-reduce.ll (+600)
(modified) llvm/test/Transforms/PhaseOrdering/AArch64/udotabd.ll (+10-10)

diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp
index 9cb6f19b9340c..9a68df8d2b028 100644
--- a/llvm/lib/Analysis/ValueTracking.cpp
+++ b/llvm/lib/Analysis/ValueTracking.cpp
@@ -2132,6 +2132,44 @@ static void computeKnownBitsFromOperator(const Operator *I,
           Known.One.clearAllBits();
         break;
       }
+      case Intrinsic::vector_reduce_add: {
+        auto *VecTy = dyn_cast<FixedVectorType>(I->getOperand(0)->getType());
+        if (!VecTy)
+          break;
+        computeKnownBits(I->getOperand(0), Known, Q, Depth + 1);
+        unsigned NumElems = VecTy->getNumElements();
+        // The main idea is as follows.
+        //
+        // If KnownBits for vector.reduce.add has L leading zeros then
+        // X_i < 2^(W - L) for every i from [1, N].
+        //
+        //   ADD X_i <= ADD max(X_i) = N * max(X_i)
+        //           <  N * 2^(W - L)
+        //           <  2^(W - L + ceil(log2(N)))
+        //
+        // As the result, we can conclude that
+        //
+        //   L' = L - ceil(log2(N)) = L - bit_width(N - 1)
+        //
+        // Similar logic can be applied to leading ones.
+        unsigned LostBits = NumElems > 1 ? llvm::bit_width(NumElems - 1) : 0;
+        if (Known.isNonNegative()) {
+          unsigned LeadingZeros = Known.countMinLeadingZeros();
+          LeadingZeros = LeadingZeros > LostBits ? LeadingZeros - LostBits : 0;
+          Known.Zero.clearAllBits();
+          Known.Zero.setHighBits(LeadingZeros);
+          Known.One.clearAllBits();
+        } else if (Known.isNegative()) {
+          unsigned LeadingOnes = Known.countMinLeadingOnes();
+          LeadingOnes = LeadingOnes > LostBits ? LeadingOnes - LostBits : 0;
+          Known.One.clearAllBits();
+          Known.One.setHighBits(LeadingOnes);
+          Known.Zero.clearAllBits();
+        } else {
+          Known.resetAll();
+        }
+        break;
+      }
       case Intrinsic::umin:
         computeKnownBits(I->getOperand(0), DemandedElts, Known, Q, Depth + 1);
         computeKnownBits(I->getOperand(1), DemandedElts, Known2, Q, Depth + 1);
diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
index abf4381ebd794..ff1304d2bdee9 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
@@ -20,11 +20,14 @@
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/Loads.h"
+#include "llvm/Analysis/SimplifyQuery.h"
 #include "llvm/Analysis/Utils/Local.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Analysis/VectorUtils.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
+#include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
@@ -3790,6 +3793,139 @@ static Instruction *foldCtpopPow2Test(ICmpInst &I, IntrinsicInst *CtpopLhs,
   return nullptr;
 }
 
+static bool isNullOrPoison(Constant *C) {
+  const auto Pred = [](Constant *X) {
+    return X->isNullValue() || isa<UndefValue>(X) || isa<PoisonValue>(X);
+  };
+
+  if (auto *VecC = dyn_cast<ConstantVector>(C)) {
+    for (unsigned I = 0; I < VecC->getNumOperands(); ++I) {
+      if (Pred(VecC->getOperand(I)))
+        return true;
+    }
+    return false;
+  }
+
+  if (auto *DataVec = dyn_cast<ConstantDataVector>(C)) {
+    for (unsigned I = 0; I < DataVec->getNumElements(); ++I) {
+      if (Pred(DataVec->getElementAsConstant(I)))
+        return true;
+    }
+    return false;
+  }
+
+  return Pred(C);
+}
+
+Instruction *
+InstCombinerImpl::foldICmpEqZeroVectorReduceIntrinsic(ICmpInst &Cmp,
+                                                      IntrinsicInst *II) {
+  // vector.reduce.OP f(X_i) == 0 -> vector.reduce.OP X_i == 0
+  //
+  // We can prove it for cases when:
+  //
+  //   1.  OP X_i == 0 <=> \forall i \in [1, N] X_i == 0
+  //   1'. OP X_i == 0 <=> \exists j \in [1, N] X_j == 0
+  //   2.  f(x) == 0 <=> x == 0
+  //
+  // From 1 and 2 (or 1' and 2), we can infer that
+  //
+  //   OP f(X_i) == 0 <=> OP X_i == 0.
+  //
+  // For some of the OP's and f's, we need to have domain constraints on X
+  // to ensure properties 1 (or 1') and 2.
+  Value *InnerOp = II->getArgOperand(0);
+  const ICmpInst::Predicate Pred = Cmp.getPredicate();
+
+  // TODO: fixed vector type might be too restrictive
+  if (!II->hasOneUse() || !InnerOp->hasOneUse() ||
+      !isa<FixedVectorType>(InnerOp->getType()))
+    return nullptr;
+
+  Value *X = nullptr;
+  Constant *C = nullptr;
+
+  // Check for zero-preserving operations where f(x) = 0 <=> x = 0
+  //
+  //   1. f(x) = shl nuw x, y for arbitrary y
+  //   2. f(x) = mul nuw x, c for defined c != 0
+  //   3. f(x) = zext x
+  //   4. f(x) = sext x
+  //   5. f(x) = neg x
+  //
+  if (!(match(InnerOp, m_NUWShl(m_Value(X),
+                                m_Value())) || // Case 1
+        (match(InnerOp, m_NUWMul(m_Value(X), m_Constant(C))) &&
+         !isNullOrPoison(C)) ||               // Case 2
+        match(InnerOp, m_ZExt(m_Value(X))) || // Case 3
+        match(InnerOp, m_SExt(m_Value(X))) || // Case 4
+        match(InnerOp, m_Neg(m_Value(X)))     // Case 5
+        ))
+    return nullptr;
+
+  SimplifyQuery S = SQ.getWithInstruction(&Cmp);
+  assert(isa<FixedVectorType>(X->getType()) && "Unexpected type");
+  auto *XTy = cast<FixedVectorType>(X->getType());
+
+  // Check for domain constraints for all supported reductions.
+  //
+  //  a. OR X_i   - has property 1  for every X
+  //  b. UMAX X_i - has property 1  for every X
+  //  c. UMIN X_i - has property 1' for every X
+  //  d. SMAX X_i - has property 1  for X >= 0
+  //  e. SMIN X_i - has property 1' for X >= 0
+  //  f. ADD X_i  - has property 1  for X >= 0 && ADD X_i doesn't sign wrap
+  //
+  // In order, for the proof to work, we need 1 (or 1') to be true for both
+  // OP f(X_i) and OP X_i and that's why below we check constraints twice.
+  //
+  // NOTE: ADD X_i holds property 1 for a mirror case as well, i.e. when
+  //       X <= 0 && ADD X_i doesn't sign wrap. However, due to the nature
+  //       of known bits, we can't reasonably hold knowledge of "either 0
+  //       or negative".
+  switch (II->getIntrinsicID()) {
+  case Intrinsic::vector_reduce_add: {
+    // If we manage to prove that the result of ADD still has at least one
+    // leading zero, we can be positive that the wrapping didn't happen for
+    // ADD f(X_i)
+    if (!isKnownNonNegative(II, S))
+      return nullptr;
+
+    // We can't check isKnownNegative for ADD X_i because this operation is
+    // not materialized yet. Instead, we try to see if X has enough leading
+    // zeros to not overflow.
+    KnownBits Known = computeKnownBits(X, &Cmp);
+    unsigned NumElems = XTy->getNumElements();
+    // Adding N elements loses at most bit_width(N-1) leading bits.
+    unsigned LostBits = NumElems > 1 ? llvm::bit_width(NumElems - 1) : 0;
+    unsigned LeadingZeros = Known.countMinLeadingZeros();
+    // Need at least one leading zero left after summation to ensure no overflow
+    if (LeadingZeros <= LostBits)
+      return nullptr;
+
+    // We are not checking whether X or f(X) are positive explicitly because
+    // we implicitly checked for it when we checked if both cases have enough
+    // leading zeros to not wrap addition.
+    break;
+  }
+  case Intrinsic::vector_reduce_smin:
+  case Intrinsic::vector_reduce_smax:
+    // Check whether X >= 0 and f(X) >= 0
+    if (!isKnownNonNegative(InnerOp, S) || !isKnownNonNegative(X, S))
+      return nullptr;
+
+    break;
+  default:
+    break;
+  };
+
+  // Since we support zext and sext as f, we might change the scalar type
+  // of the intrinsic.
+  Type *Ty = XTy->getScalarType();
+  Value *NewReduce = Builder.CreateIntrinsic(Ty, II->getIntrinsicID(), {X});
+  return new ICmpInst(Pred, NewReduce, ConstantInt::getNullValue(Ty));
+}
+
 /// Fold an equality icmp with LLVM intrinsic and constant operand.
 Instruction *InstCombinerImpl::foldICmpEqIntrinsicWithConstant(
     ICmpInst &Cmp, IntrinsicInst *II, const APInt &C) {
@@ -3890,6 +4026,17 @@ Instruction *InstCombinerImpl::foldICmpEqIntrinsicWithConstant(
     }
     break;
   }
+  case Intrinsic::vector_reduce_add:
+  case Intrinsic::vector_reduce_or:
+  case Intrinsic::vector_reduce_umin:
+  case Intrinsic::vector_reduce_umax:
+  case Intrinsic::vector_reduce_smin:
+  case Intrinsic::vector_reduce_smax:
+    // vector.reduce.OP f(X_i) == 0 -> vector.reduce.OP X_i == 0
+    if (C.isZero())
+      return foldICmpEqZeroVectorReduceIntrinsic(Cmp, II);
+
+    break;
   default:
     break;
   }
diff --git a/llvm/lib/Transforms/InstCombine/InstCombineInternal.h b/llvm/lib/Transforms/InstCombine/InstCombineInternal.h
index 9bdd8cb71f7f3..5f8d6bf00ca0d 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineInternal.h
+++ b/llvm/lib/Transforms/InstCombine/InstCombineInternal.h
@@ -787,6 +787,7 @@ class LLVM_LIBRARY_VISIBILITY InstCombinerImpl final
                                              const APInt &C);
   Instruction *foldICmpEqIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
                                                const APInt &C);
+  Instruction *foldICmpEqZeroVectorReduceIntrinsic(ICmpInst &ICI, IntrinsicInst *II);
   Instruction *foldICmpBitCast(ICmpInst &Cmp);
   Instruction *foldICmpWithTrunc(ICmpInst &Cmp);
   Instruction *foldICmpCommutative(CmpPredicate Pred, Value *Op0, Value *Op1,
diff --git a/llvm/test/Transforms/InstCombine/icmp-vector-reduce.ll b/llvm/test/Transforms/InstCombine/icmp-vector-reduce.ll
new file mode 100644
index 0000000000000..7cc9191198e7c
--- /dev/null
+++ b/llvm/test/Transforms/InstCombine/icmp-vector-reduce.ll
@@ -0,0 +1,600 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 6
+; RUN: opt -passes=instcombine -S < %s | FileCheck %s
+
+define i1 @or_zext(<4 x i16> %x) {
+; CHECK-LABEL: define i1 @or_zext(
+; CHECK-SAME: <4 x i16> [[X:%.*]]) {
+; CHECK-NEXT:    [[TMP1:%.*]] = call i16 @llvm.vector.reduce.or.v4i16(<4 x i16> [[X]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[TMP1]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %zext = zext <4 x i16> %x to <4 x i32>
+  %red = call i32 @llvm.vector.reduce.or.v4i32(<4 x i32> %zext)
+  %cmp = icmp eq i32 %red, 0
+  ret i1 %cmp
+}
+
+define i1 @or_zext_i3(<4 x i3> %x) {
+; CHECK-LABEL: define i1 @or_zext_i3(
+; CHECK-SAME: <4 x i3> [[X:%.*]]) {
+; CHECK-NEXT:    [[TMP1:%.*]] = call i3 @llvm.vector.reduce.or.v4i3(<4 x i3> [[X]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i3 [[TMP1]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %zext = zext <4 x i3> %x to <4 x i32>
+  %red = call i32 @llvm.vector.reduce.or.v4i32(<4 x i32> %zext)
+  %cmp = icmp eq i32 %red, 0
+  ret i1 %cmp
+}
+
+define i1 @or_sext(<4 x i16> %x) {
+; CHECK-LABEL: define i1 @or_sext(
+; CHECK-SAME: <4 x i16> [[X:%.*]]) {
+; CHECK-NEXT:    [[TMP1:%.*]] = call i16 @llvm.vector.reduce.or.v4i16(<4 x i16> [[X]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[TMP1]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %sext = sext <4 x i16> %x to <4 x i32>
+  %red = call i32 @llvm.vector.reduce.or.v4i32(<4 x i32> %sext)
+  %cmp = icmp eq i32 %red, 0
+  ret i1 %cmp
+}
+
+define i1 @or_neg(<4 x i32> %x) {
+; CHECK-LABEL: define i1 @or_neg(
+; CHECK-SAME: <4 x i32> [[X:%.*]]) {
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.vector.reduce.or.v4i32(<4 x i32> [[X]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP1]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %neg = sub <4 x i32> zeroinitializer, %x
+  %red = call i32 @llvm.vector.reduce.or.v4i32(<4 x i32> %neg)
+  %cmp = icmp eq i32 %red, 0
+  ret i1 %cmp
+}
+
+define i1 @or_mul(<4 x i32> %x) {
+; CHECK-LABEL: define i1 @or_mul(
+; CHECK-SAME: <4 x i32> [[X:%.*]]) {
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.vector.reduce.or.v4i32(<4 x i32> [[X]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP1]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %mul = mul nuw <4 x i32> %x, splat (i32 7)
+  %red = call i32 @llvm.vector.reduce.or.v4i32(<4 x i32> %mul)
+  %cmp = icmp eq i32 %red, 0
+  ret i1 %cmp
+}
+
+define i1 @or_shl(<4 x i32> %x, <4 x i32> %y) {
+; CHECK-LABEL: define i1 @or_shl(
+; CHECK-SAME: <4 x i32> [[X:%.*]], <4 x i32> [[Y:%.*]]) {
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.vector.reduce.or.v4i32(<4 x i32> [[X]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP1]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %shl = shl nuw <4 x i32> %x, %y
+  %red = call i32 @llvm.vector.reduce.or.v4i32(<4 x i32> %shl)
+  %cmp = icmp eq i32 %red, 0
+  ret i1 %cmp
+}
+
+define i1 @umin_zext(<4 x i16> %x) {
+; CHECK-LABEL: define i1 @umin_zext(
+; CHECK-SAME: <4 x i16> [[X:%.*]]) {
+; CHECK-NEXT:    [[TMP1:%.*]] = call i16 @llvm.vector.reduce.umin.v4i16(<4 x i16> [[X]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[TMP1]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %zext = zext <4 x i16> %x to <4 x i32>
+  %red = call i32 @llvm.vector.reduce.umin.v4i32(<4 x i32> %zext)
+  %cmp = icmp eq i32 %red, 0
+  ret i1 %cmp
+}
+
+define i1 @umin_sext(<4 x i16> %x) {
+; CHECK-LABEL: define i1 @umin_sext(
+; CHECK-SAME: <4 x i16> [[X:%.*]]) {
+; CHECK-NEXT:    [[TMP1:%.*]] = call i16 @llvm.vector.reduce.umin.v4i16(<4 x i16> [[X]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[TMP1]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %sext = sext <4 x i16> %x to <4 x i32>
+  %red = call i32 @llvm.vector.reduce.umin.v4i32(<4 x i32> %sext)
+  %cmp = icmp eq i32 %red, 0
+  ret i1 %cmp
+}
+
+define i1 @umin_neg(<4 x i32> %x) {
+; CHECK-LABEL: define i1 @umin_neg(
+; CHECK-SAME: <4 x i32> [[X:%.*]]) {
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.vector.reduce.umin.v4i32(<4 x i32> [[X]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP1]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %neg = sub <4 x i32> zeroinitializer, %x
+  %red = call i32 @llvm.vector.reduce.umin.v4i32(<4 x i32> %neg)
+  %cmp = icmp eq i32 %red, 0
+  ret i1 %cmp
+}
+
+define i1 @umin_mul(<4 x i32> %x) {
+; CHECK-LABEL: define i1 @umin_mul(
+; CHECK-SAME: <4 x i32> [[X:%.*]]) {
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.vector.reduce.umin.v4i32(<4 x i32> [[X]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP1]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %mul = mul nuw <4 x i32> %x, splat (i32 7)
+  %red = call i32 @llvm.vector.reduce.umin.v4i32(<4 x i32> %mul)
+  %cmp = icmp eq i32 %red, 0
+  ret i1 %cmp
+}
+
+define i1 @umin_shl(<4 x i32> %x, <4 x i32> %y) {
+; CHECK-LABEL: define i1 @umin_shl(
+; CHECK-SAME: <4 x i32> [[X:%.*]], <4 x i32> [[Y:%.*]]) {
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.vector.reduce.umin.v4i32(<4 x i32> [[X]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP1]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %shl = shl nuw <4 x i32> %x, %y
+  %red = call i32 @llvm.vector.reduce.umin.v4i32(<4 x i32> %shl)
+  %cmp = icmp eq i32 %red, 0
+  ret i1 %cmp
+}
+
+define i1 @umax_zext(<4 x i16> %x) {
+; CHECK-LABEL: define i1 @umax_zext(
+; CHECK-SAME: <4 x i16> [[X:%.*]]) {
+; CHECK-NEXT:    [[TMP1:%.*]] = call i16 @llvm.vector.reduce.umax.v4i16(<4 x i16> [[X]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[TMP1]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %zext = zext <4 x i16> %x to <4 x i32>
+  %red = call i32 @llvm.vector.reduce.umax.v4i32(<4 x i32> %zext)
+  %cmp = icmp eq i32 %red, 0
+  ret i1 %cmp
+}
+
+define i1 @umax_sext(<4 x i16> %x) {
+; CHECK-LABEL: define i1 @umax_sext(
+; CHECK-SAME: <4 x i16> [[X:%.*]]) {
+; CHECK-NEXT:    [[TMP1:%.*]] = call i16 @llvm.vector.reduce.umax.v4i16(<4 x i16> [[X]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[TMP1]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %sext = sext <4 x i16> %x to <4 x i32>
+  %red = call i32 @llvm.vector.reduce.umax.v4i32(<4 x i32> %sext)
+  %cmp = icmp eq i32 %red, 0
+  ret i1 %cmp
+}
+
+define i1 @umax_neg(<4 x i32> %x) {
+; CHECK-LABEL: define i1 @umax_neg(
+; CHECK-SAME: <4 x i32> [[X:%.*]]) {
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.vector.reduce.umax.v4i32(<4 x i32> [[X]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP1]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %neg = sub <4 x i32> zeroinitializer, %x
+  %red = call i32 @llvm.vector.reduce.umax.v4i32(<4 x i32> %neg)
+  %cmp = icmp eq i32 %red, 0
+  ret i1 %cmp
+}
+
+define i1 @umax_mul(<4 x i32> %x) {
+; CHECK-LABEL: define i1 @umax_mul(
+; CHECK-SAME: <4 x i32> [[X:%.*]]) {
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.vector.reduce.umax.v4i32(<4 x i32> [[X]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP1]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %mul = mul nuw <4 x i32> %x, splat (i32 7)
+  %red = call i32 @llvm.vector.reduce.umax.v4i32(<4 x i32> %mul)
+  %cmp = icmp eq i32 %red, 0
+  ret i1 %cmp
+}
+
+define i1 @umax_shl(<4 x i32> %x, <4 x i32> %y) {
+; CHECK-LABEL: define i1 @umax_shl(
+; CHECK-SAME: <4 x i32> [[X:%.*]], <4 x i32> [[Y:%.*]]) {
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.vector.reduce.umax.v4i32(<4 x i32> [[X]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP1]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %shl = shl nuw <4 x i32> %x, %y
+  %red = call i32 @llvm.vector.reduce.umax.v4i32(<4 x i32> %shl)
+  %cmp = icmp eq i32 %red, 0
+  ret i1 %cmp
+}
+
+define i1 @smin_zext(<4 x i16> %x) {
+; CHECK-LABEL: define i1 @smin_zext(
+; CHECK-SAME: <4 x i16> [[X:%.*]]) {
+; CHECK-NEXT:    [[AND:%.*]] = and <4 x i16> [[X]], splat (i16 32767)
+; CHECK-NEXT:    [[TMP1:%.*]] = call i16 @llvm.vector.reduce.smin.v4i16(<4 x i16> [[AND]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[TMP1]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %and = and <4 x i16> %x, splat (i16 32767)
+  %zext = zext <4 x i16> %and to <4 x i32>
+  %red = call i32 @llvm.vector.reduce.smin.v4i32(<4 x i32> %zext)
+  %cmp = icmp eq i32 %red, 0
+  ret i1 %cmp
+}
+
+define i1 @smin_sext(<4 x i16> %x) {
+; CHECK-LABEL: define i1 @smin_sext(
+; CHECK-SAME: <4 x i16> [[X:%.*]]) {
+; CHECK-NEXT:    [[AND:%.*]] = and <4 x i16> [[X]], splat (i16 32767)
+; CHECK-NEXT:    [[TMP1:%.*]] = call i16 @llvm.vector.reduce.smin.v4i16(<4 x i16> [[AND]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[TMP1]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %and = and <4 x i16> %x, splat (i16 32767)
+  %sext = sext <4 x i16> %and to <4 x i32>
+  %red = call i32 @llvm.vector.reduce.smin.v4i32(<4 x i32> %sext)
+  %cmp = icmp eq i32 %red, 0
+  ret i1 %cmp
+}
+
+; neg is incompatible with smin constraints, expected not to combine
+define i1 @smin_neg(<4 x i16> %x) {
+; CHECK-LABEL: define i1 @smin_neg(
+; CHECK-SAME: <4 x i16> [[X:%.*]]) {
+; CHECK-NEXT:    [[ZEXT:%.*]] = zext <4 x i16> [[X]] to <4 x i32>
+; CHECK-NEXT:    [[NEG:%.*]] = sub nsw <4 x i32> zeroinitializer, [[ZEXT]]
+; CHECK-NEXT:    [[RED:%.*]] = call i32 @llvm.vector.reduce.smin.v4i32(<4 x i32> [[NEG]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[RED]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %zext = zext <4 x i16> %x to <4 x i32>
+  %neg = sub nsw <4 x i32> zeroinitializer, %zext
+  %red = call i32 @llvm.vector.reduce.smin.v4i32(<4 x i32> %neg)
+  %cmp = icmp eq i32 %red, 0
+  ret i1 %cmp
+}
+
+define i1 @smin_mul(<4 x i16> %x) {
+; CHECK-LABEL: define i1 @smin_mul(
+; CHECK-SAME: <4 x i16> [[X:%.*]]) {
+; CHECK-NEXT:    [[ZEXT:%.*]] = zext <4 x i16> [[X]] to <4 x i32>
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.vector.reduce.smin.v4i32(<4 x i32> [[ZEXT]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP1]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %zext = zext <4 x i16> %x to <4 x i32>
+  %mul = mul nuw nsw <4 x i32> %zext, splat (i32 7)
+  %red = call i32 @llvm.vector.reduce.smin.v4i32(<4 x i32> %mul)
+  %cmp = icmp eq i32 %red, 0
+  ret i1 %cmp
+}
+
+define i1 @smin_shl(<4 x i16> %x, <4 x i32> %y) {
+; CHECK-LABEL: define i1 @smin_shl(
+; CHECK-SAME: <4 x i16> [[X:%.*]], <4 x i32> [[Y:%.*]]) {
+; CHECK-NEXT:    [[ZEXT:%.*]] = zext <4 x i16> [[X]] to <4 x i32>
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.vector.reduce.smin.v4i32(<4 x i32> [[ZEXT]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP1]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %zext = zext <4 x i16> %x to <4 x i32>
+  %ymasked = and <4 x i32> %y, splat (i32 7)
+  %shl = shl nuw nsw <4 x i32> %zext, %ymasked
+  %red = call i32 @llvm.vector.reduce.smin.v4i32(<4 x i32> %shl)
+  %cmp = icmp eq i32 %red, 0
+  ret i1 %cmp
+}
+
+define i1 @smax...
[truncated]

github-actions · 2025-12-19T18:12:33Z

✅ With the latest revision this PR passed the C/C++ code formatter.

dtcxzyw · 2025-12-19T18:43:21Z

+  //
+  // From 1 and 2 (or 1' and 2), we can infer that
+  //
+  //   OP f(X_i) == 0 <=> OP X_i == 0.


Can we extend and reuse the stripNullTest helper in ValueTracking?

Oops, I see the extra range checking for some intrinsics below. So it may not be suitable.

It is actually a great point. When we check for property 2, this is exactly what we check. Properties 1 and 2 are checked independently in my function, so I can safely extract this logic into stripNullTest. Thanks!

After looking at it a bit more, it includes icmp matching and for our case f(x) is removed from direct comparison. This means that I can refactor that function to separate this logic out of it, but it's not a perfect fit otherwise. WDYT?

dtcxzyw · 2025-12-19T18:55:22Z

+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %zext = zext <4 x i3> %x to <4 x i32>
+  %red = call i32 @llvm.vector.reduce.or.v4i32(<4 x i32> %zext)


It is not always profitable to change the bitwidth of vector operations. It would be better to put the logic into VectorCombine.

I added a cost check and a test when it doesn't fire because of the cost check. Please see if that's what you had in mind

dtcxzyw

Do these patterns exist in real-world programs? Or it is just some kind of canonicalization after auto-vectorization.

SavchenkoValeriy · 2025-12-19T20:42:43Z

Do these patterns exist in real-world programs? Or it is just some kind of canonicalization after auto-vectorization.

They do! This is actually one step for generalization of one pattern that is quite prevalent and I didn't want to match it directly.

The pattern is:

a = x >> 32
b = a << <0, 1, 2, 3>
c = vector.reduce.add b
if (c == 0) ...

Getting rid of shl first and then recognizing the sigbit check later is consistent with non-reduction case.

This appears mainly in the manually vectorized code. But the patterns that I covered can appear in the auto-vectorized code as well.

SavchenkoValeriy · 2026-01-05T15:00:32Z

@fhahn WDYT about zext/sext handling here? Should I move this whole logic into VectorCombine, remove extension handling, or is it fine as it is?

RKSimon · 2026-01-06T12:39:57Z

@fhahn WDYT about zext/sext handling here? Should I move this whole logic into VectorCombine, remove extension handling, or is it fine as it is?

How much are you intending to develop this - are you just interested in the icmp(reduceop(*ext(x))) -> icmp(reduceop(x)) pattern or do you have more in mind? VectorCombine will give you the cost benefit test that you're missing here, but if you're wanting to do a lot more analysis its going to get trickier.

SavchenkoValeriy · 2026-01-06T13:20:09Z

@fhahn WDYT about zext/sext handling here? Should I move this whole logic into VectorCombine, remove extension handling, or is it fine as it is?

How much are you intending to develop this - are you just interested in the icmp(reduceop(*ext(x))) -> icmp(reduceop(x)) pattern or do you have more in mind? VectorCombine will give you the cost benefit test that you're missing here, but if you're wanting to do a lot more analysis its going to get trickier.

Essentially *ext operations were added here as part of the pattern generalization. They fall into the category of functions f that have the required property: f(x) == 0 <=> x == 0. So, I'm not particularly attached to extensions being a part of this combine. I do plan to add other cmp reduction combines to VectorCombine that actually require a cost model to choose the best option.

RKSimon · 2026-01-06T13:27:21Z

OK - if you have a good idea of what you're aiming to do I think vectorcombine will be the better approach - but bear in mind that apart from x86 I'm not very confident of the quality of cost data you will get for many of the reduction ops!

SavchenkoValeriy · 2026-01-06T13:31:08Z

OK - if you have a good idea of what you're aiming to do I think vectorcombine will be the better approach - but bear in mind that apart from x86 I'm not very confident of the quality of cost data you will get for many of the reduction ops!

Just to clarify, you mean moving this combine pattern to VectorCombine, correct?

RKSimon · 2026-01-06T14:08:47Z

Yes - if you're confident that you can do whatever you want to do in the fold in the future

SavchenkoValeriy · 2026-01-09T10:31:29Z

@RKSimon @dtcxzyw Hey folks! Do you have any other concerns about this change?

RKSimon · 2026-01-14T12:44:38Z

It might be beneficial to fold even if InnerOp has other uses - we just need to account for it in the cost calculations.

e.g. if the comparison is used to check for certain bound limits on the vector and the vector itself is then used somewhere else.

InnerOp is essentially the instruction that we remove, ie f(X). If it has other uses (unless those other uses can be folded away using this transformation as well), we don't remove it.
Which I guess is OK, we just remove this use possibly unlocking sinking and other optimizations. I actually now can't think of a case where I actually need to check for the cost here. Do you have a case for it in mind?

I removed the check for the number of uses on f(x) and added a trivial amendment to the *ext cost calculation for that situation. Please see if that's what you had in mind.

SavchenkoValeriy · 2026-01-20T15:40:30Z

@RKSimon mind taking another look here? I feel like we are almost there with this change 😅

SavchenkoValeriy · 2026-01-22T13:47:45Z

@RKSimon @dtcxzyw a gentle ping

SavchenkoValeriy · 2026-01-23T12:40:42Z

@RKSimon any input about this change?

dtcxzyw

LGTM

…7996) #175194, #177159, and #173069 introduced the code calling `TTI.getMinMaxReductionCost` with unexpected `Intrinsic::ID` causing RISC-V to fail with `llvm_unreachable` panic. Functionally, this is a small fix that also ports tests for the aforementioned folds to RISCV.

…m#177996) llvm#175194, llvm#177159, and llvm#173069 introduced the code calling `TTI.getMinMaxReductionCost` with unexpected `Intrinsic::ID` causing RISC-V to fail with `llvm_unreachable` panic. Functionally, this is a small fix that also ports tests for the aforementioned folds to RISCV.

SavchenkoValeriy requested a review from dtcxzyw December 19, 2025 18:10

SavchenkoValeriy requested a review from nikic as a code owner December 19, 2025 18:10

llvmbot added llvm:instcombine Covers the InstCombine, InstSimplify and AggressiveInstCombine passes llvm:analysis Includes value tracking, cost tables and constant folding llvm:transforms labels Dec 19, 2025

SavchenkoValeriy force-pushed the feat/instcombine/icmp-vector-reduce-eq-zero branch from 0dfb28c to 79b0c5d Compare December 19, 2025 18:13

dtcxzyw reviewed Dec 19, 2025

View reviewed changes

dtcxzyw requested a review from RKSimon December 19, 2025 18:56

dtcxzyw reviewed Dec 19, 2025

View reviewed changes

RKSimon requested a review from fhahn December 19, 2025 20:48

SavchenkoValeriy mentioned this pull request Jan 5, 2026

[ValueTracking] Support horizontal vector add in computeKnownBits #174410

Merged

SavchenkoValeriy force-pushed the feat/instcombine/icmp-vector-reduce-eq-zero branch from 79b0c5d to 41e982d Compare January 5, 2026 14:53

RKSimon mentioned this pull request Jan 6, 2026

Use pmovmskb instead of @llvm.vector.reduce.or.v16i8 where possible #174504

Open

SavchenkoValeriy force-pushed the feat/instcombine/icmp-vector-reduce-eq-zero branch from 41e982d to 51407de Compare January 7, 2026 12:39

llvmbot added vectorizers llvm:vectorcombine Cost-based vector combine pass labels Jan 7, 2026

SavchenkoValeriy force-pushed the feat/instcombine/icmp-vector-reduce-eq-zero branch from 51407de to 95eca90 Compare January 7, 2026 12:43

RKSimon reviewed Jan 7, 2026

View reviewed changes

Comment thread llvm/lib/Transforms/Vectorize/VectorCombine.cpp Outdated

SavchenkoValeriy force-pushed the feat/instcombine/icmp-vector-reduce-eq-zero branch from 95eca90 to 3271d6e Compare January 7, 2026 16:08

dtcxzyw changed the title ~~[InstCombine] Fold vector.reduce.OP(F(X)) == 0 -> OP(X) == 0~~ [VectorCombine] Fold vector.reduce.OP(F(X)) == 0 -> OP(X) == 0 Jan 7, 2026

dtcxzyw reviewed Jan 7, 2026

View reviewed changes

Comment thread llvm/lib/Transforms/Vectorize/VectorCombine.cpp Outdated

dtcxzyw reviewed Jan 11, 2026

View reviewed changes

Comment thread llvm/lib/Transforms/Vectorize/VectorCombine.cpp Outdated

Comment thread llvm/lib/Transforms/Vectorize/VectorCombine.cpp Outdated

Comment thread llvm/lib/Transforms/Vectorize/VectorCombine.cpp Outdated

SavchenkoValeriy mentioned this pull request Jan 11, 2026

[VectorCombine] Fold vector sign-bit checks #175194

Merged

SavchenkoValeriy force-pushed the feat/instcombine/icmp-vector-reduce-eq-zero branch 2 times, most recently from 6eeb41a to 2b5485c Compare January 13, 2026 11:56

SavchenkoValeriy requested a review from dtcxzyw January 14, 2026 12:20

RKSimon reviewed Jan 14, 2026

View reviewed changes

Comment thread llvm/lib/Transforms/Vectorize/VectorCombine.cpp Outdated

RKSimon reviewed Jan 14, 2026

View reviewed changes

SavchenkoValeriy force-pushed the feat/instcombine/icmp-vector-reduce-eq-zero branch from 2b5485c to b9bd16e Compare January 16, 2026 15:45

SavchenkoValeriy requested a review from RKSimon January 17, 2026 13:15

SavchenkoValeriy force-pushed the feat/instcombine/icmp-vector-reduce-eq-zero branch from b9bd16e to c449b58 Compare January 20, 2026 15:37

SavchenkoValeriy force-pushed the feat/instcombine/icmp-vector-reduce-eq-zero branch from c449b58 to 3c6f2a7 Compare January 23, 2026 18:09

dtcxzyw mentioned this pull request Jan 25, 2026

Fuzz PR173069 dtcxzyw/llvm-fuzz-service#171

Closed

dtcxzyw reviewed Jan 25, 2026

View reviewed changes

Comment thread llvm/lib/Transforms/Vectorize/VectorCombine.cpp

dtcxzyw approved these changes Jan 25, 2026

View reviewed changes

SavchenkoValeriy merged commit 9d6f011 into llvm:main Jan 25, 2026
11 checks passed

SavchenkoValeriy mentioned this pull request Jan 26, 2026

[VectorCombine] Call cost calculation with correct intrinsic IDs #177996

Merged

Uh oh!

Conversation

SavchenkoValeriy commented Dec 19, 2025

Uh oh!

llvmbot commented Dec 19, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

github-actions Bot commented Dec 19, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

dtcxzyw Dec 19, 2025

Choose a reason for hiding this comment

Uh oh!

dtcxzyw Dec 19, 2025

Choose a reason for hiding this comment

Uh oh!

SavchenkoValeriy Jan 5, 2026

Choose a reason for hiding this comment

Uh oh!

SavchenkoValeriy Jan 5, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

dtcxzyw Dec 19, 2025

Choose a reason for hiding this comment

Uh oh!

SavchenkoValeriy Jan 7, 2026

Choose a reason for hiding this comment

Uh oh!

dtcxzyw left a comment

Choose a reason for hiding this comment

Uh oh!

SavchenkoValeriy commented Dec 19, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

SavchenkoValeriy commented Jan 5, 2026

Uh oh!

RKSimon commented Jan 6, 2026

Uh oh!

SavchenkoValeriy commented Jan 6, 2026

Uh oh!

RKSimon commented Jan 6, 2026

Uh oh!

SavchenkoValeriy commented Jan 6, 2026

Uh oh!

RKSimon commented Jan 6, 2026

Uh oh!

Uh oh!

Uh oh!

SavchenkoValeriy commented Jan 9, 2026

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

RKSimon Jan 14, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

SavchenkoValeriy Jan 16, 2026

Choose a reason for hiding this comment

Uh oh!

SavchenkoValeriy Jan 20, 2026

Choose a reason for hiding this comment

Uh oh!

SavchenkoValeriy commented Jan 20, 2026

Uh oh!

SavchenkoValeriy commented Jan 22, 2026

Uh oh!

SavchenkoValeriy commented Jan 23, 2026

Uh oh!

Uh oh!

dtcxzyw left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Reviewers

Assignees

llvmbot commented Dec 19, 2025 •

edited

Loading

github-actions Bot commented Dec 19, 2025 •

edited

Loading

SavchenkoValeriy Jan 5, 2026 •

edited

Loading

SavchenkoValeriy commented Dec 19, 2025 •

edited

Loading

RKSimon Jan 14, 2026 •

edited

Loading