[LV] Rename the Select[I|F]Cmp reduction pattern to [I|F]AnyOf. (NFC)

[Mel-Chen]

Summary

Regarding this NFC change, please refer to the discussion in this thread. https://reviews.llvm.org/D150851#4467261

[artagnon]

LGTM, but I'd wait for @Ayal's comments.

[Ayal]

Thanks for following-up on this! Adding various minors nits.

llvm/include/llvm/Analysis/IVDescriptors.h

44

52

nit: while we're here, worth clarifying that FMulAdd is essentially an FAdd reduction whose reduced values are products fused with the add in fmuladd, as in a dot-product sum(a[i]*b[i]).

53–54

239–240

Would it make (more) sense to rename this isAnyOfRecurrenceKind()?

llvm/include/llvm/Transforms/Utils/LoopUtils.h

399–400

createAnyOfTargetReduction()?

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

3287

nit: while we're here, worth placing these last - after FMulAdd, as they appear in RecurKind definition?

llvm/lib/Target/RISCV/RISCVTargetTransformInfo.h

291

ditto

llvm/test/Transforms/LoopVectorize/smax-idx.ll

58–59

nit: MMI - Min-or-Max-with-Index?

(nit: if index is not used outside the loop, best eliminate its computation as dead code.)

61–64

Indeed not an any_of reduction, but an SMax one.
Would be good to clarify this TODO comment, also grammatically (exitInstruction? SelectCmp?).

92–93

Indeed not an any_of reduction, but an SMax one.
Would be good to clarify this TODO comment (Combination pass?)

[Mel-Chen]

llvm/include/llvm/Analysis/IVDescriptors.h

44

LG, this change will push directly to llvm-project repo.

52

LG, this change will push directly to llvm-project repo.

53–54

Since currently we only have implemented the integer version of any_of, would it be better to retain it specifically for integers?

239–240

I suggest this:

static bool isAnyOfRecurrenceKind(RecurKind Kind) {
  return Kind == RecurKind::IAnyOf || Kind == RecurKind::FAnyOf;
}

static bool isSelectCmpRecurrenceKind(RecurKind Kind) {
  return isAnyOfRecurrenceKind(Kind);
}

llvm/test/Transforms/LoopVectorize/smax-idx.ll

58–59

nit: MMI - Min-or-Max-with-Index?

Yes, it's min/max with index. I think I should put the full name before the short name.

(nit: if index is not used outside the loop, best eliminate its computation as dead code.)

This case checks if the maximum result is not used outside the loop. Regarding the index, if I recall correctly, the vectorizer should be able to perform dead code elimination for values that are not used outside the loop.

61–64

How do you feel about the following version?

; Check if it is a min/max with index (MMI) pattern when the
; min/max value is not used outside the loop.
;
; Currently, the vectorizer checks if smax value is used outside
; the loop. However, even if only the index part has external users,
; and smax itself does not have external users, it can still form a 
; MMI pattern.

92–93

Currently, all the reductions of the form select(cmp()) do not support cmp with more than one user, including min/max reductions.
However, FP min/max with index encounters the situation where cmp has more than one user.
Since the transformation of integer select(cmp(x, y), x, y) to [s|u]min/max appears to be done in the Combination pass, my plan is to refer to how multiple users of cmp are handled in that pass to relax the limitation for select(cmp()) reductions.

[Mel-Chen]

Update the patch according to the comments.

[Ayal]

llvm/include/llvm/Analysis/IVDescriptors.h

53–54

Since currently we only have implemented the integer version of any_of, would it be better to retain it specifically for integers?

Ah, good clarification, worth a TODO somewhere, possibly attached to a negative test: this pattern is easily applicable to x,y of any type. How about:

IAnyOf,   ///< any_of reduction with select(icmp(),t,f) and invariant t or f (both integers)
IAnyOf    ///< any_of reduction with select(fcmp(),t,f) and invariant t or f (both integers)

AnyOf is essentially a boolean OR reduction, so should apply to both integer and floating point return values. The predicate producing the reduced values can be provided via icmp or fcmp. The end boolean result could be converted to a {true-value, false value} pair of any type, preferably after the loop. The types of true-value and false-value must match each other, but are independent of the type of comparison.

239–240

Will isSelectCmpRecurrenceKind() still be needed?
Min/max may also uses a compare-select pattern, leading to potential confusion of "isSelectCmpRecurrenceKind()".

llvm/lib/Analysis/IVDescriptors.cpp

804–806

?

llvm/lib/Transforms/Utils/LoopUtils.cpp

1123–1124

?

llvm/test/Transforms/LoopVectorize/smax-idx.ll

58–59

Ah, right, thanks for clarifying.

61–64

How do you feel about the following version?

LGTM.

Just noting that in some cases it suffices to report the index alone, e.g., when the smax value can be easily retrieved/recomputed using its index.

92–93

However, FP min/max with index encounters the situation where cmp has more than one user.

If min/max is computed with a cmp/select, this cmp will be reused to select its index.
If min is computed with an llvm.[smin|umin|minnum|minimum] intrinsic, and likewise for max, its index can be selected with its own cmp.

By Combination pass you mean instcombine? Anyhow, worth prefixing with TODO.

92–93

(All reductions require all operations along their chain to have a single user, except for a single live-out. But this test focuses on MMI, which would need to handle cmp feeding two selects as part of its chain.)

[Mel-Chen]

llvm/include/llvm/Analysis/IVDescriptors.h

239–240

Because eventually, D150851 will need isSelectCmpRecurrenceKind(). Both AnyOf and FindLastIV share common characteristics, such as similar identification methods. Using isSelectCmpRecurrenceKind() to control similar behavior should be better than isAnyOfRecurrenceKind() || isFindLastIVRecurrenceKind(). However, I also agree that isSelectCmpRecurrenceKind() might lead to confusion since the format of min max reduction is really similar.

[Mel-Chen]

Rebase and update according to comments.

[Mel-Chen]

llvm/include/llvm/Analysis/IVDescriptors.h

44

Fixed https://github.com/llvm/llvm-project/commit/59629429028bfadccdf937436c0eb722bd556378

52

Fixed https://github.com/llvm/llvm-project/commit/59629429028bfadccdf937436c0eb722bd556378

239–240

Because eventually, D150851 will need isSelectCmpRecurrenceKind(). Both AnyOf and FindLastIV share common characteristics, such as similar identification methods. Using isSelectCmpRecurrenceKind() to control similar behavior should be better than isAnyOfRecurrenceKind() || isFindLastIVRecurrenceKind(). However, I also agree that isSelectCmpRecurrenceKind() might lead to confusion since the format of min max reduction is really similar.

llvm/lib/Analysis/IVDescriptors.cpp

804–806

I have not renamed isSelectCmpPattern() to isAnyOfPattern() yet. The reasons for this decision are explained in previous comment https://reviews.llvm.org/D155786/new/#inline-1515374.

llvm/test/Transforms/LoopVectorize/smax-idx.ll

92–93

Yes, it is instcombine pass.

[Mel-Chen]

llvm/include/llvm/Analysis/IVDescriptors.h

53–54

Re-write comments and added TODO.

[artagnon]

llvm/test/Transforms/LoopVectorize/smax-idx.ll

95

Typo: duplicated.

[Mel-Chen]

llvm/test/Transforms/LoopVectorize/smax-idx.ll

95

Nice catch.

[Mel-Chen]

Fixed typo.

[Ayal]

llvm/include/llvm/Analysis/IVDescriptors.h

53

55

57–58

Should in general apply to any type, including pointer etc.

239–240

Then let D150851 argue in favor of isSelectCmpRecurrenceKind() when it needs it, or be content with isAnyOfRecurrenceKind() || isFindLastIVRecurrenceKind() (which may be fine if used seldom). Here this appears redundant and useless?

llvm/lib/Analysis/IVDescriptors.cpp

804–806

Can this patch simply rename the existing code to read

if (isAnyOfRecurrenceKind(Kind))
  return isAnyOfPattern(L, OrigPhi, I, Prev);

leaving future support of FindLastIV in D150851 to add what it needs, e.g., possibly adding

if (isFindLastIVRecurrenceKind(Kind))
  return isFindLastIVPattern(L, OrigPhi, I, Prev);

?

llvm/lib/Transforms/Vectorize/VPlanRecipes.cpp

1272–1273

(While we're here.)

llvm/test/Transforms/LoopVectorize/smax-idx.ll

91

[Mel-Chen]

llvm/include/llvm/Analysis/IVDescriptors.h

57–58

Indeed!

239–240

Of course, we can remove isSelectCmpRecurrenceKind() in this patch. After rebasing D150851, I'll temporarily provide a restored implementation of isSelectCmpRecurrenceKind(). Then, we can discuss whether to keep it, rename it, or directly use isAnyOfRecurrenceKind() || isFindLastIVRecurrenceKind().

llvm/lib/Analysis/IVDescriptors.cpp

804–806

Sure, we can discuss later.

[Mel-Chen]

Change:

• Replaced all SelectCmp.* with AnyOf.*
• Fixed comments.

[Ayal]

This looks good to me, thanks for the cleanup!
Adding a couple of minor nits.

llvm/include/llvm/Transforms/Utils/LoopUtils.h

368–371

Fixing this original documentation, while we're updating it: there is no \p LoopExitInst here.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

3996–4001

[Mel-Chen]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

3996–4001

https://github.com/llvm/llvm-project/commit/97cccdd9f3c5d250cf0031c84ec363c96fa94321

[Mel-Chen]

Rebase, and update the comment.

llvm/include/llvm/Analysis/IVDescriptors.h

 class Loop;
 class PredicatedScalarEvolution;
 class ScalarEvolution;
 class SCEV;
 class StoreInst;
 
 /// These are the kinds of recurrences that we support.
 enum class RecurKind {
-  None,       ///< Not a recurrence.
-  Add,        ///< Sum of integers.
-  Mul,        ///< Product of integers.
-  Or,         ///< Bitwise or logical OR of integers.
-  And,        ///< Bitwise or logical AND of integers.
-  Xor,        ///< Bitwise or logical XOR of integers.
-  SMin,       ///< Signed integer min implemented in terms of select(cmp()).
-  SMax,       ///< Signed integer max implemented in terms of select(cmp()).
-  UMin,       ///< Unsigned integer min implemented in terms of select(cmp()).
-  UMax,       ///< Unsigned integer max implemented in terms of select(cmp()).
-  FAdd,       ///< Sum of floats.
-  FMul,       ///< Product of floats.
-  FMin,       ///< FP min implemented in terms of select(cmp()).
-  FMax,       ///< FP max implemented in terms of select(cmp()).
-  FMinimum,   ///< FP min with llvm.minimum semantics
-  FMaximum,   ///< FP max with llvm.maximum semantics
-  FMulAdd,    ///< Sum of float products with llvm.fmuladd(a * b + sum).
-  SelectICmp, ///< Integer select(icmp(),x,y) where one of (x,y) is loop
-              ///< invariant
-  SelectFCmp  ///< Integer select(fcmp(),x,y) where one of (x,y) is loop
-              ///< invariant
+  None,     ///< Not a recurrence.
+  Add,      ///< Sum of integers.
+  Mul,      ///< Product of integers.
+  Or,       ///< Bitwise or logical OR of integers.
+  And,      ///< Bitwise or logical AND of integers.
+  Xor,      ///< Bitwise or logical XOR of integers.
+  SMin,     ///< Signed integer min implemented in terms of select(cmp()).
+  SMax,     ///< Signed integer max implemented in terms of select(cmp()).
+  UMin,     ///< Unsigned integer min implemented in terms of select(cmp()).
+  UMax,     ///< Unsigned integer max implemented in terms of select(cmp()).
+  FAdd,     ///< Sum of floats.
+  FMul,     ///< Product of floats.
+  FMin,     ///< FP min implemented in terms of select(cmp()).
+  FMax,     ///< FP max implemented in terms of select(cmp()).
+  FMinimum, ///< FP min with llvm.minimum semantics
+  FMaximum, ///< FP max with llvm.maximum semantics
+  FMulAdd,  ///< Sum of float products with llvm.fmuladd(a * b + sum).
+  IAnyOf,   ///< Any_of reduction with select(icmp(),x,y) where one of (x,y) is
+            ///< loop invariant, and both x and y are integer type.
+  FAnyOf    ///< Any_of reduction with select(fcmp(),x,y) where one of (x,y) is
+            ///< loop invariant, and both x and y are integer type.
+  // TODO: Any_of reduction need not be restricted to integer type only.
 };
 
 /// The RecurrenceDescriptor is used to identify recurrences variables in a
 /// loop. Reduction is a special case of recurrence that has uses of the
 /// recurrence variable outside the loop. The method isReductionPHI identifies
 /// reductions that are basic recurrences.
 ///
 /// Basic recurrences are defined as the summation, product, OR, AND, XOR, min,
 /// or max of a set of terms. For example: for(i=0; i<n; i++) { total +=
static InstDesc isMinMaxPattern(Instruction *I, RecurKind Kind,
                                   const InstDesc &Prev);
 
   /// Returns a struct describing whether the instruction is either a
   ///   Select(ICmp(A, B), X, Y), or
   ///   Select(FCmp(A, B), X, Y)
   /// where one of (X, Y) is a loop invariant integer and the other is a PHI
   /// value. \p Prev specifies the description of an already processed select
   /// instruction, so its corresponding cmp can be matched to it.
-  static InstDesc isSelectCmpPattern(Loop *Loop, PHINode *OrigPhi,
-                                     Instruction *I, InstDesc &Prev);
+  static InstDesc isAnyOfPattern(Loop *Loop, PHINode *OrigPhi, Instruction *I,
+                                 InstDesc &Prev);
 
   /// Returns a struct describing if the instruction is a
   /// Select(FCmp(X, Y), (Z = X op PHINode), PHINode) instruction pattern.
   static InstDesc isConditionalRdxPattern(RecurKind Kind, Instruction *I);
 
   /// Returns identity corresponding to the RecurrenceKind.
   Value *getRecurrenceIdentity(RecurKind K, Type *Tp, FastMathFlags FMF) const;
 
public:
   }
 
   /// Returns true if the recurrence kind is any min/max kind.
   static bool isMinMaxRecurrenceKind(RecurKind Kind) {
     return isIntMinMaxRecurrenceKind(Kind) || isFPMinMaxRecurrenceKind(Kind);
   }
 
   /// Returns true if the recurrence kind is of the form
   ///   select(cmp(),x,y) where one of (x,y) is loop invariant.
-  static bool isSelectCmpRecurrenceKind(RecurKind Kind) {
-    return Kind == RecurKind::SelectICmp || Kind == RecurKind::SelectFCmp;
+  static bool isAnyOfRecurrenceKind(RecurKind Kind) {
+    return Kind == RecurKind::IAnyOf || Kind == RecurKind::FAnyOf;
   }
 
   /// Returns the type of the recurrence. This type can be narrower than the
   /// actual type of the Phi if the recurrence has been type-promoted.
   Type *getRecurrenceType() const { return RecurrenceType; }
 
   /// Returns a reference to the instructions used for type-promoting the
   /// recurrence.

llvm/include/llvm/Transforms/Utils/LoopUtils.h

bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
                         OptimizationRemarkEmitter *ORE = nullptr);
 
 /// Returns the min/max intrinsic used when expanding a min/max reduction.
 Intrinsic::ID getMinMaxReductionIntrinsicOp(RecurKind RK);
 
 /// Returns the comparison predicate used when expanding a min/max reduction.
 CmpInst::Predicate getMinMaxReductionPredicate(RecurKind RK);
 
-/// See RecurrenceDescriptor::isSelectCmpPattern for a description of the
-/// pattern we are trying to match. In this pattern we are only ever selecting
-/// between two values: 1) an initial PHI start value, and 2) a loop invariant
-/// value. This function uses \p LoopExitInst to determine 2), which we then use
-/// to select between \p Left and \p Right. Any lane value in \p Left that
-/// matches 2) will be merged into \p Right.
-Value *createSelectCmpOp(IRBuilderBase &Builder, Value *StartVal, RecurKind RK,
-                         Value *Left, Value *Right);
+/// See RecurrenceDescriptor::isAnyOfPattern for a description of the pattern we
+/// are trying to match. In this pattern, we are only ever selecting between two
+/// values: 1) an initial start value \p StartVal of the reduction PHI, and 2) a
+/// loop invariant value. If any of lane value in \p Left, \p Right is not equal
+/// to \p StartVal, select the loop invariant value. This is done by selecting
+/// \p Right iff \p Left is equal to \p StartVal.
+Value *createAnyOfOp(IRBuilderBase &Builder, Value *StartVal, RecurKind RK,
 
 /// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
 /// The Builder's fast-math-flags must be set to propagate the expected values.
 Value *createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left,
                       Value *Right);
 
 /// Generates an ordered vector reduction using extracts to reduce the value.
 Value *getOrderedReduction(IRBuilderBase &Builder, Value *Acc, Value *Src,

 /// additional information supplied in \p RdxKind.
 /// The target is queried to determine if intrinsics or shuffle sequences are
 /// required to implement the reduction.
 /// Fast-math-flags are propagated using the IRBuilder's setting.
 Value *createSimpleTargetReduction(IRBuilderBase &B,
                                    const TargetTransformInfo *TTI, Value *Src,
                                    RecurKind RdxKind);
 
 /// Create a target reduction of the given vector \p Src for a reduction of the
-/// kind RecurKind::SelectICmp or RecurKind::SelectFCmp. The reduction operation
-/// is described by \p Desc.
-Value *createSelectCmpTargetReduction(IRBuilderBase &B,
-                                      const TargetTransformInfo *TTI,
-                                      Value *Src,
-                                      const RecurrenceDescriptor &Desc,
-                                      PHINode *OrigPhi);
+/// kind RecurKind::IAnyOf or RecurKind::FAnyOf. The reduction operation is
+/// described by \p Desc.
+Value *createAnyOfTargetReduction(IRBuilderBase &B,
+                                  const TargetTransformInfo *TTI, Value *Src,
 
 /// Create a generic target reduction using a recurrence descriptor \p Desc
 /// The target is queried to determine if intrinsics or shuffle sequences are
 /// required to implement the reduction.
 /// Fast-math-flags are propagated using the RecurrenceDescriptor.
 Value *createTargetReduction(IRBuilderBase &B, const TargetTransformInfo *TTI,
                              const RecurrenceDescriptor &Desc, Value *Src,
                              PHINode *OrigPhi = nullptr);

llvm/lib/Analysis/IVDescriptors.cpp

bool RecurrenceDescriptor::isIntegerRecurrenceKind(RecurKind Kind) {
   case RecurKind::Mul:
   case RecurKind::Or:
   case RecurKind::And:
   case RecurKind::Xor:
   case RecurKind::SMax:
   case RecurKind::SMin:
   case RecurKind::UMax:
   case RecurKind::UMin:
-  case RecurKind::SelectICmp:
-  case RecurKind::SelectFCmp:
+  case RecurKind::IAnyOf:
+  case RecurKind::FAnyOf:
     return true;
   }
   return false;
 }
 
 bool RecurrenceDescriptor::isFloatingPointRecurrenceKind(RecurKind Kind) {
   return (Kind != RecurKind::None) && !isIntegerRecurrenceKind(Kind);
 }
while (!Worklist.empty()) {
     // A conditional reduction operation must only have 2 or less uses in
     // VisitedInsts.
     if (IsASelect && (Kind == RecurKind::FAdd || Kind == RecurKind::FMul) &&
         hasMultipleUsesOf(Cur, VisitedInsts, 2))
       return false;
 
     // A reduction operation must only have one use of the reduction value.
     if (!IsAPhi && !IsASelect && !isMinMaxRecurrenceKind(Kind) &&
-        !isSelectCmpRecurrenceKind(Kind) &&
-        hasMultipleUsesOf(Cur, VisitedInsts, 1))
+        !isAnyOfRecurrenceKind(Kind) && hasMultipleUsesOf(Cur, VisitedInsts, 1))
       return false;
 
     // All inputs to a PHI node must be a reduction value.
     if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts))
       return false;
 
-    if ((isIntMinMaxRecurrenceKind(Kind) || Kind == RecurKind::SelectICmp) &&
+    if ((isIntMinMaxRecurrenceKind(Kind) || Kind == RecurKind::IAnyOf) &&
         (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur)))
       ++NumCmpSelectPatternInst;
-    if ((isFPMinMaxRecurrenceKind(Kind) || Kind == RecurKind::SelectFCmp) &&
+    if ((isFPMinMaxRecurrenceKind(Kind) || Kind == RecurKind::FAnyOf) &&
         (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur)))
       ++NumCmpSelectPatternInst;
 
     // Check  whether we found a reduction operator.
     FoundReduxOp |= !IsAPhi && Cur != Start;
 
     // Process users of current instruction. Push non-PHI nodes after PHI nodes
     // onto the stack. This way we are going to have seen all inputs to PHI
for (User *U : Cur->users()) {
             return false;
           }
           NonPHIs.push_back(UI);
         }
       } else if (!isa<PHINode>(UI) &&
                  ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
                    !isa<SelectInst>(UI)) ||
                   (!isConditionalRdxPattern(Kind, UI).isRecurrence() &&
-                   !isSelectCmpPattern(TheLoop, Phi, UI, IgnoredVal)
+                   !isAnyOfPattern(TheLoop, Phi, UI, IgnoredVal)
                         .isRecurrence() &&
                    !isMinMaxPattern(UI, Kind, IgnoredVal).isRecurrence())))
         return false;
 
       // Remember that we completed the cycle.
       if (UI == Phi)
         FoundStartPHI = true;
     }
     Worklist.append(PHIs.begin(), PHIs.end());
     Worklist.append(NonPHIs.begin(), NonPHIs.end());
   }
 
   // This means we have seen one but not the other instruction of the
   // pattern or more than just a select and cmp. Zero implies that we saw a
   // llvm.min/max intrinsic, which is always OK.
   if (isMinMaxRecurrenceKind(Kind) && NumCmpSelectPatternInst != 2 &&
       NumCmpSelectPatternInst != 0)
     return false;
 
-  if (isSelectCmpRecurrenceKind(Kind) && NumCmpSelectPatternInst != 1)
+  if (isAnyOfRecurrenceKind(Kind) && NumCmpSelectPatternInst != 1)
     return false;
 
   if (IntermediateStore) {
     // Check that stored value goes to the phi node again. This way we make sure
     // that the value stored in IntermediateStore is indeed the final reduction
     // value.
     if (!is_contained(Phi->operands(), IntermediateStore->getValueOperand())) {
       LLVM_DEBUG(dbgs() << "Not a final reduction value stored: "

 // In general we can support vectorization of loops where 'r' flips between
 // any two non-constants, provided they are loop invariant. The only thing
 // we actually care about at the end of the loop is whether or not any lane
 // in the selected vector is different from the start value. The final
 // across-vector reduction after the loop simply involves choosing the start
 // value if nothing changed (0 in the example above) or the other selected
 // value (3 in the example above).
 RecurrenceDescriptor::InstDesc
-RecurrenceDescriptor::isSelectCmpPattern(Loop *Loop, PHINode *OrigPhi,
-                                         Instruction *I, InstDesc &Prev) {
+RecurrenceDescriptor::isAnyOfPattern(Loop *Loop, PHINode *OrigPhi,
   // We must handle the select(cmp(),x,y) as a single instruction. Advance to
   // the select.
   CmpInst::Predicate Pred;
   if (match(I, m_OneUse(m_Cmp(Pred, m_Value(), m_Value())))) {
     if (auto *Select = dyn_cast<SelectInst>(*I->user_begin()))
       return InstDesc(Select, Prev.getRecKind());
   }
 
else
     return InstDesc(false, I);
 
   // We are looking for selects of the form:
   //   select(cmp(), phi, loop_invariant) or
   //   select(cmp(), loop_invariant, phi)
   if (!Loop->isLoopInvariant(NonPhi))
     return InstDesc(false, I);
 
-  return InstDesc(I, isa<ICmpInst>(I->getOperand(0)) ? RecurKind::SelectICmp
-                                                     : RecurKind::SelectFCmp);
+  return InstDesc(I, isa<ICmpInst>(I->getOperand(0)) ? RecurKind::IAnyOf
+                                                     : RecurKind::FAnyOf);
 }
 
 RecurrenceDescriptor::InstDesc
 RecurrenceDescriptor::isMinMaxPattern(Instruction *I, RecurKind Kind,
                                       const InstDesc &Prev) {
   assert((isa<CmpInst>(I) || isa<SelectInst>(I) || isa<CallInst>(I)) &&
          "Expected a cmp or select or call instruction");
   if (!isMinMaxRecurrenceKind(Kind))
return InstDesc(Kind == RecurKind::FAdd, I,
                     I->hasAllowReassoc() ? nullptr : I);
   case Instruction::Select:
     if (Kind == RecurKind::FAdd || Kind == RecurKind::FMul ||
         Kind == RecurKind::Add || Kind == RecurKind::Mul)
       return isConditionalRdxPattern(Kind, I);
     [[fallthrough]];
   case Instruction::FCmp:
   case Instruction::ICmp:
   case Instruction::Call:
-    if (isSelectCmpRecurrenceKind(Kind))
-      return isSelectCmpPattern(L, OrigPhi, I, Prev);
+    if (isAnyOfRecurrenceKind(Kind))
+      return isAnyOfPattern(L, OrigPhi, I, Prev);
     auto HasRequiredFMF = [&]() {
      if (FuncFMF.noNaNs() && FuncFMF.noSignedZeros())
        return true;
      if (isa<FPMathOperator>(I) && I->hasNoNaNs() && I->hasNoSignedZeros())
        return true;
      // minimum and maximum intrinsics do not require nsz and nnan flags since
      // NaN and signed zeroes are propagated in the intrinsic implementation.
      return match(I, m_Intrinsic<Intrinsic::minimum>(m_Value(), m_Value())) ||
if (AddReductionVar(Phi, RecurKind::UMax, TheLoop, FMF, RedDes, DB, AC, DT,
     LLVM_DEBUG(dbgs() << "Found a UMAX reduction PHI." << *Phi << "\n");
     return true;
   }
   if (AddReductionVar(Phi, RecurKind::UMin, TheLoop, FMF, RedDes, DB, AC, DT,
                       SE)) {
     LLVM_DEBUG(dbgs() << "Found a UMIN reduction PHI." << *Phi << "\n");
     return true;
   }
-  if (AddReductionVar(Phi, RecurKind::SelectICmp, TheLoop, FMF, RedDes, DB, AC,
-                      DT, SE)) {
+  if (AddReductionVar(Phi, RecurKind::IAnyOf, TheLoop, FMF, RedDes, DB, AC, DT,
+                      SE)) {
     LLVM_DEBUG(dbgs() << "Found an integer conditional select reduction PHI."
                       << *Phi << "\n");
     return true;
   }
   if (AddReductionVar(Phi, RecurKind::FMul, TheLoop, FMF, RedDes, DB, AC, DT,
                       SE)) {
     LLVM_DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n");
     return true;
   }
   if (AddReductionVar(Phi, RecurKind::FAdd, TheLoop, FMF, RedDes, DB, AC, DT,
                       SE)) {
     LLVM_DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n");
     return true;
   }
   if (AddReductionVar(Phi, RecurKind::FMax, TheLoop, FMF, RedDes, DB, AC, DT,
                       SE)) {
     LLVM_DEBUG(dbgs() << "Found a float MAX reduction PHI." << *Phi << "\n");
     return true;
   }
   if (AddReductionVar(Phi, RecurKind::FMin, TheLoop, FMF, RedDes, DB, AC, DT,
                       SE)) {
     LLVM_DEBUG(dbgs() << "Found a float MIN reduction PHI." << *Phi << "\n");
     return true;
   }
-  if (AddReductionVar(Phi, RecurKind::SelectFCmp, TheLoop, FMF, RedDes, DB, AC,
-                      DT, SE)) {
+  if (AddReductionVar(Phi, RecurKind::FAnyOf, TheLoop, FMF, RedDes, DB, AC, DT,
+                      SE)) {
     LLVM_DEBUG(dbgs() << "Found a float conditional select reduction PHI."
                       << " PHI." << *Phi << "\n");
     return true;
   }
   if (AddReductionVar(Phi, RecurKind::FMulAdd, TheLoop, FMF, RedDes, DB, AC, DT,
                       SE)) {
     LLVM_DEBUG(dbgs() << "Found an FMulAdd reduction PHI." << *Phi << "\n");
     return true;
Value *RecurrenceDescriptor::getRecurrenceIdentity(RecurKind K, Type *Tp,
   case RecurKind::FMax:
     assert((FMF.noNaNs() && FMF.noSignedZeros()) &&
            "nnan, nsz is expected to be set for FP max reduction.");
     return ConstantFP::getInfinity(Tp, true /*Negative*/);
   case RecurKind::FMinimum:
     return ConstantFP::getInfinity(Tp, false /*Negative*/);
   case RecurKind::FMaximum:
     return ConstantFP::getInfinity(Tp, true /*Negative*/);
-  case RecurKind::SelectICmp:
-  case RecurKind::SelectFCmp:
+  case RecurKind::IAnyOf:
+  case RecurKind::FAnyOf:
     return getRecurrenceStartValue();
     break;
   default:
     llvm_unreachable("Unknown recurrence kind");
   }
 }
 
 unsigned RecurrenceDescriptor::getOpcode(RecurKind Kind) {
case RecurKind::FMul:
     return Instruction::FMul;
   case RecurKind::FMulAdd:
   case RecurKind::FAdd:
     return Instruction::FAdd;
   case RecurKind::SMax:
   case RecurKind::SMin:
   case RecurKind::UMax:
   case RecurKind::UMin:
-  case RecurKind::SelectICmp:
+  case RecurKind::IAnyOf:
     return Instruction::ICmp;
   case RecurKind::FMax:
   case RecurKind::FMin:
   case RecurKind::FMaximum:
   case RecurKind::FMinimum:
-  case RecurKind::SelectFCmp:
+  case RecurKind::FAnyOf:
     return Instruction::FCmp;
   default:
     llvm_unreachable("Unknown recurrence operation");
   }
 }
 
 SmallVector<Instruction *, 4>
 RecurrenceDescriptor::getReductionOpChain(PHINode *Phi, Loop *L) const {

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

bool AArch64TTIImpl::isLegalToVectorizeReduction(
   case RecurKind::Or:
   case RecurKind::Xor:
   case RecurKind::SMin:
   case RecurKind::SMax:
   case RecurKind::UMin:
   case RecurKind::UMax:
   case RecurKind::FMin:
   case RecurKind::FMax:
-  case RecurKind::SelectICmp:
-  case RecurKind::SelectFCmp:
   case RecurKind::FMulAdd:
+  case RecurKind::IAnyOf:
+  case RecurKind::FAnyOf:
     return true;
   default:
     return false;
   }
 }
 
 InstructionCost
 AArch64TTIImpl::getMinMaxReductionCost(Intrinsic::ID IID, VectorType *Ty,

llvm/lib/Target/RISCV/RISCVTargetTransformInfo.h

bool isLegalToVectorizeReduction(const RecurrenceDescriptor &RdxDesc,
     case RecurKind::Or:
     case RecurKind::Xor:
     case RecurKind::SMin:
     case RecurKind::SMax:
     case RecurKind::UMin:
     case RecurKind::UMax:
     case RecurKind::FMin:
     case RecurKind::FMax:
-    case RecurKind::SelectICmp:
-    case RecurKind::SelectFCmp:
     case RecurKind::FMulAdd:
+    case RecurKind::IAnyOf:
+    case RecurKind::FAnyOf:
       return true;
     default:
       return false;
     }
   }
 
   unsigned getMaxInterleaveFactor(ElementCount VF) {
     // Don't interleave if the loop has been vectorized with scalable vectors.

llvm/lib/Transforms/Utils/LoopUtils.cpp

CmpInst::Predicate llvm::getMinMaxReductionPredicate(RecurKind RK) {
   case RecurKind::FMax:
     return CmpInst::FCMP_OGT;
   // We do not add FMinimum/FMaximum recurrence kind here since there is no
   // equivalent predicate which compares signed zeroes according to the
   // semantics of the intrinsics (llvm.minimum/maximum).
   }
 }
 
-Value *llvm::createSelectCmpOp(IRBuilderBase &Builder, Value *StartVal,
-                               RecurKind RK, Value *Left, Value *Right) {
+Value *llvm::createAnyOfOp(IRBuilderBase &Builder, Value *StartVal,
   if (auto VTy = dyn_cast<VectorType>(Left->getType()))
     StartVal = Builder.CreateVectorSplat(VTy->getElementCount(), StartVal);
   Value *Cmp =
       Builder.CreateCmp(CmpInst::ICMP_NE, Left, StartVal, "rdx.select.cmp");
   return Builder.CreateSelect(Cmp, Left, Right, "rdx.select");
 }
 
 Value *llvm::createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left,
if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
              "Invalid min/max");
       TmpVec = createMinMaxOp(Builder, RdxKind, TmpVec, Shuf);
     }
   }
   // The result is in the first element of the vector.
   return Builder.CreateExtractElement(TmpVec, Builder.getInt32(0));
 }
 
-Value *llvm::createSelectCmpTargetReduction(IRBuilderBase &Builder,
-                                            const TargetTransformInfo *TTI,
-                                            Value *Src,
-                                            const RecurrenceDescriptor &Desc,
-                                            PHINode *OrigPhi) {
-  assert(RecurrenceDescriptor::isSelectCmpRecurrenceKind(
-             Desc.getRecurrenceKind()) &&
-         "Unexpected reduction kind");
+Value *llvm::createAnyOfTargetReduction(IRBuilderBase &Builder,
+  assert(
+      RecurrenceDescriptor::isAnyOfRecurrenceKind(Desc.getRecurrenceKind()) &&
   Value *InitVal = Desc.getRecurrenceStartValue();
   Value *NewVal = nullptr;
 
   // First use the original phi to determine the new value we're trying to
   // select from in the loop.
   SelectInst *SI = nullptr;
   for (auto *U : OrigPhi->users()) {
     if ((SI = dyn_cast<SelectInst>(U)))
Value *llvm::createTargetReduction(IRBuilderBase &B,
                                    const RecurrenceDescriptor &Desc, Value *Src,
                                    PHINode *OrigPhi) {
   // TODO: Support in-order reductions based on the recurrence descriptor.
   // All ops in the reduction inherit fast-math-flags from the recurrence
   // descriptor.
   IRBuilderBase::FastMathFlagGuard FMFGuard(B);
   B.setFastMathFlags(Desc.getFastMathFlags());
 
   RecurKind RK = Desc.getRecurrenceKind();
-  if (RecurrenceDescriptor::isSelectCmpRecurrenceKind(RK))
-    return createSelectCmpTargetReduction(B, TTI, Src, Desc, OrigPhi);
+  if (RecurrenceDescriptor::isAnyOfRecurrenceKind(RK))
+    return createAnyOfTargetReduction(B, TTI, Src, Desc, OrigPhi);
 
   return createSimpleTargetReduction(B, TTI, Src, RK);
 }
 
 Value *llvm::createOrderedReduction(IRBuilderBase &B,
                                     const RecurrenceDescriptor &Desc,
                                     Value *Src, Value *Start) {
   assert((Desc.getRecurrenceKind() == RecurKind::FAdd ||

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

void InnerLoopVectorizer::fixReduction(VPReductionPHIRecipe *PhiR,
   if (PhiR->isOrdered())
     ReducedPartRdx = State.get(LoopExitInstDef, UF - 1);
   else {
     // Floating-point operations should have some FMF to enable the reduction.
     IRBuilderBase::FastMathFlagGuard FMFG(Builder);
     Builder.setFastMathFlags(RdxDesc.getFastMathFlags());
     for (unsigned Part = 1; Part < UF; ++Part) {
       Value *RdxPart = State.get(LoopExitInstDef, Part);
       if (Op != Instruction::ICmp && Op != Instruction::FCmp)
         ReducedPartRdx = Builder.CreateBinOp(
             (Instruction::BinaryOps)Op, RdxPart, ReducedPartRdx, "bin.rdx");
-      else if (RecurrenceDescriptor::isSelectCmpRecurrenceKind(RK))
-        ReducedPartRdx = createSelectCmpOp(Builder, ReductionStartValue, RK,
-                                           ReducedPartRdx, RdxPart);
+      else if (RecurrenceDescriptor::isAnyOfRecurrenceKind(RK))
+        ReducedPartRdx = createAnyOfOp(Builder, ReductionStartValue, RK,
       else
         ReducedPartRdx = createMinMaxOp(Builder, RK, ReducedPartRdx, RdxPart);
     }
   }
 
   // Create the reduction after the loop. Note that inloop reductions create the
   // target reduction in the loop using a Reduction recipe.
   if (VF.isVector() && !PhiR->isInLoop()) {
if (!ScalarInterleavingRequiresRuntimePointerCheck &&
     // There is little point in interleaving for reductions containing selects
     // and compares when VF=1 since it may just create more overhead than it's
     // worth for loops with small trip counts. This is because we still have to
     // do the final reduction after the loop.
     bool HasSelectCmpReductions =
         HasReductions &&
         any_of(Legal->getReductionVars(), [&](auto &Reduction) -> bool {
           const RecurrenceDescriptor &RdxDesc = Reduction.second;
-          return RecurrenceDescriptor::isSelectCmpRecurrenceKind(
+          return RecurrenceDescriptor::isAnyOfRecurrenceKind(
               RdxDesc.getRecurrenceKind());
         });
     if (HasSelectCmpReductions) {
       LLVM_DEBUG(dbgs() << "LV: Not interleaving select-cmp reductions.\n");
       return 1;
     }
 
     // If we have a scalar reduction (vector reductions are already dealt with
for (VPRecipeBase &R :
     if (!PhiR || !PhiR->isInLoop() || (MinVF.isScalar() && !PhiR->isOrdered()))
       continue;
     InLoopReductionPhis.push_back(PhiR);
   }
 
   for (VPReductionPHIRecipe *PhiR : InLoopReductionPhis) {
     const RecurrenceDescriptor &RdxDesc = PhiR->getRecurrenceDescriptor();
     RecurKind Kind = RdxDesc.getRecurrenceKind();
-    assert(!RecurrenceDescriptor::isSelectCmpRecurrenceKind(Kind) &&
-           "select/cmp reductions are not allowed for in-loop reductions");
+    assert(!RecurrenceDescriptor::isAnyOfRecurrenceKind(Kind) &&
+           "AnyOf reductions are not allowed for in-loop reductions");
 
     // Collect the chain of "link" recipes for the reduction starting at PhiR.
     SetVector<VPRecipeBase *> Worklist;
     Worklist.insert(PhiR);
     for (unsigned I = 0; I != Worklist.size(); ++I) {
       VPRecipeBase *Cur = Worklist[I];
       for (VPUser *U : Cur->getVPSingleValue()->users()) {
         auto *UserRecipe = dyn_cast<VPRecipeBase>(U);

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

Value *emitScaleForReusedOps(Value *VectorizedValue, IRBuilderBase &Builder,
     case RecurKind::FMin:
     case RecurKind::FMaximum:
     case RecurKind::FMinimum:
       // res = vv
       return VectorizedValue;
     case RecurKind::Mul:
     case RecurKind::FMul:
     case RecurKind::FMulAdd:
-    case RecurKind::SelectICmp:
-    case RecurKind::SelectFCmp:
+    case RecurKind::IAnyOf:
+    case RecurKind::FAnyOf:
     case RecurKind::None:
       llvm_unreachable("Unexpected reduction kind for repeated scalar.");
     }
     return nullptr;
   }
 
   /// Emits actual operation for the scalar identity values, found during
   /// horizontal reduction analysis.
case RecurKind::FAdd: {
         Vals.push_back(ConstantFP::get(V->getType(), Cnt));
       }
       auto *Scale = ConstantVector::get(Vals);
       return Builder.CreateFMul(VectorizedValue, Scale);
     }
     case RecurKind::Mul:
     case RecurKind::FMul:
     case RecurKind::FMulAdd:
-    case RecurKind::SelectICmp:
-    case RecurKind::SelectFCmp:
+    case RecurKind::IAnyOf:
+    case RecurKind::FAnyOf:
     case RecurKind::None:
       llvm_unreachable("Unexpected reduction kind for reused scalars.");
     }
     return nullptr;
   }
 };
 } // end anonymous namespace
 

llvm/lib/Transforms/Vectorize/VPlanRecipes.cpp

void VPReductionPHIRecipe::execute(VPTransformState &State) {
   // Reductions do not have to start at zero. They can start with
   // any loop invariant values.
   VPValue *StartVPV = getStartValue();
   Value *StartV = StartVPV->getLiveInIRValue();
 
   Value *Iden = nullptr;
   RecurKind RK = RdxDesc.getRecurrenceKind();
   if (RecurrenceDescriptor::isMinMaxRecurrenceKind(RK) ||
-      RecurrenceDescriptor::isSelectCmpRecurrenceKind(RK)) {
-    // MinMax reduction have the start value as their identify.
+      RecurrenceDescriptor::isAnyOfRecurrenceKind(RK)) {
+    // MinMax and AnyOf reductions have the start value as their identity.
     if (ScalarPHI) {
       Iden = StartV;
     } else {
       IRBuilderBase::InsertPointGuard IPBuilder(Builder);
       Builder.SetInsertPoint(VectorPH->getTerminator());
       StartV = Iden =
           Builder.CreateVectorSplat(State.VF, StartV, "minmax.ident");
     }

llvm/test/Transforms/LoopVectorize/smax-idx.ll

for.body:
   %exitcond.not = icmp eq i64 %indvars.iv.next, %n
   br i1 %exitcond.not, label %exit, label %for.body
 
 exit:
   store i64 %1, ptr %res_max
   ret i64 %spec.select7
 }
 
-; Check if it is a MMI when smax is not used outside the loop.
+; Check if it is a min/max with index (MMI) pattern when the
+; min/max value is not used outside the loop.
 ;
-; Currently at the end, it will check if smax has exitInstruction.
-; But in fact MMI should be possible to use the exitInstruction of
-; SelectICmp be the exitInstruction.
+; Currently, the vectorizer checks if smax value is used outside
+; the loop. However, even if only the index part has external users,
+; and smax itself does not have external users, it can still form a
+; MMI pattern.
 ;
 define i64 @smax_idx_max_no_exit_user(ptr nocapture readonly %a, i64 %mm, i64 %ii, i64 %n) {
 ; CHECK-LABEL: @smax_idx_max_no_exit_user(
 ; CHECK-NOT:   vector.body:
 ;
 entry:
   br label %for.body
 
for.body:
   %exitcond.not = icmp eq i64 %indvars.iv.next, %n
   br i1 %exitcond.not, label %exit, label %for.body
 
 exit:
   ; %1 has no external users
   ret i64 %spec.select7
 }
 
-; Check smax implemented in terms of select(cmp()).
+; Check smax implemented by select(cmp()).
 ;
-; Currently SelectICmp does not support icmp with multiple users.
-; It may be possible to reuse some of the methods in Combination pass to check
-; whether icmp can be copied.
+; Currently, MMI pattern does not support icmp with multiple users.
+; TODO: It may be possible to reuse some of the methods in instcombine pass to
+; check whether icmp can be duplicated.
 ;
 define i64 @smax_idx_select_cmp(ptr nocapture readonly %a, i64 %mm, i64 %ii, ptr nocapture writeonly %res_max, i64 %n) {
 ; CHECK-LABEL: @smax_idx_select_cmp(
 ; CHECK-NOT:   vector.body:
 ;
 entry:
   br label %for.body