[LV] Recognize intrinsic min/max reductions

[dmgreen]

Summary

This extends the reduction logic in the vectorizer to handle intrinsic versions of min and max, both the floating point variants already created by instcombine under fastmath and the integer variants from D98152.

As a bonus this allows it to match a chain of min or max operations into a single reduction, similar to how add/mul/etc work.

[fhahn]

Looks reasonable. Could you recommit the tests?

[dmgreen]

In D109645#2996912, @fhahn wrote:

Looks reasonable. Could you recommit the tests?

Sure, I can do that. I'm not sure it helps much, the tests just go from "CHECK-NOT <2 x i32> @llvm.smin" to "CHECK: <2 x i32> @llvm.smin" :)

[dmgreen]

On second thoughts, added checks to "llvm.vector.reduce.smax.v2i32" too, to show the reductions. Also added some "fmin/max without fast" reduction test cases, to show they are not vectorized.

[spatel]

I didn't realize we were still missing vectorization of these intrinsics. What is the difference between the patterns here vs. the tests that are already vectorized in llvm/test/Transforms/LoopVectorize/intrinsic.ll ?

llvm/include/llvm/Analysis/IVDescriptors.h

134

Should this be called "isMinMaxPattern" now since it matches both intrinsics and select-cmp?

llvm/test/Transforms/LoopVectorize/minmax_reduction.ll

998

Either this test or the previous one could be just "nnan nsz" rather than "fast" so we are testing the minimum FMF (assuming that works as expected).

[dmgreen]

In D109645#2998195, @spatel wrote:

I didn't realize we were still missing vectorization of these intrinsics. What is the difference between the patterns here vs. the tests that are already vectorized in llvm/test/Transforms/LoopVectorize/intrinsic.ll ?

These ones are reductions (i.e https://godbolt.org/z/G9affdzsh, creating a llvm.vector.reduce.smax after the loop) as opposed to just plain vectorization (https://godbolt.org/z/K9jvT9rsv, which I believe are still working just fine). The code to match those reduction is what it changing here, requiring to look through the min/max intrinsics as opposed to a pair of icmp/select (which is actually a lot simpler, as you might imagine. The matching of reductions isn't the cleanest code in the world and I'm hoping that once min/max become canonical we can simplify it somewhat. At least in the meantime we have to match both though.)

[dmgreen]

Rename to IsMinMaxPattern and make a test more precise, as suggested.

[spatel]

llvm/test/Transforms/LoopVectorize/minmax_reduction.ll

985

Does this call (and also fmin above) have the expected FMF too?

[dmgreen]

Added FMF checks for reduction intrinsic.

[spatel]

LGTM

llvm/test/Transforms/LoopVectorize/minmax_reduction.ll

998

Sorry if I wasn't clear, but it would be better to have one of these tests have minimal FMF and one have extra FMF (ie, the original 'fast' was good) because that shows we are propagating all FMF as expected even if they are not required for the transform. Alternatively, we could add a 2nd test for maxnum with 'fast'.

llvm/include/llvm/Analysis/IVDescriptors.h

public:
   };
 
   /// Returns a struct describing if the instruction 'I' can be a recurrence
   /// variable of type 'Kind'. If the recurrence is a min/max pattern of
   /// select(icmp()) this function advances the instruction pointer 'I' from the
   /// compare instruction to the select instruction and stores this pointer in
   /// 'PatternLastInst' member of the returned struct.
   static InstDesc isRecurrenceInstr(Instruction *I, RecurKind Kind,
-                                    InstDesc &Prev, FastMathFlags FMF);
+                                    InstDesc &Prev, FastMathFlags FuncFMF);
 
   /// Returns true if instruction I has multiple uses in Insts
   static bool hasMultipleUsesOf(Instruction *I,
                                 SmallPtrSetImpl<Instruction *> &Insts,
                                 unsigned MaxNumUses);
 
   /// Returns true if all uses of the instruction I is within the Set.
   static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl<Instruction *> &Set);
 
-  /// Returns a struct describing if the instruction is a
-  /// Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y)
-  /// or max(X, Y). \p Prev specifies the description of an already processed
-  /// select instruction, so its corresponding cmp can be matched to it.
-  static InstDesc isMinMaxSelectCmpPattern(Instruction *I,
-                                           const InstDesc &Prev);
+  /// Returns a struct describing if the instruction is a llvm.(s/u)(min/max),
+  /// llvm.minnum/maxnum or a Select(ICmp(X, Y), X, Y) pair of instructions
+  /// corresponding to a min(X, Y) or max(X, Y), matching the recurrence kind \p
+  /// Kind. \p Prev specifies the description of an already processed select
+  /// instruction, so its corresponding cmp can be matched to it.
+  static InstDesc isMinMaxPattern(Instruction *I, RecurKind Kind,
 
   /// 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.
   static Constant *getRecurrenceIdentity(RecurKind K, Type *Tp,
                                          FastMathFlags FMF);
 
   /// Returns the opcode corresponding to the RecurrenceKind.
   static unsigned getOpcode(RecurKind Kind);
 
   /// Returns true if Phi is a reduction of type Kind and adds it to the
   /// RecurrenceDescriptor. If either \p DB is non-null or \p AC and \p DT are
   /// non-null, the minimal bit width needed to compute the reduction will be
   /// computed.
   static bool AddReductionVar(PHINode *Phi, RecurKind Kind, Loop *TheLoop,
-                              FastMathFlags FMF,
+                              FastMathFlags FuncFMF,
                               RecurrenceDescriptor &RedDes,
                               DemandedBits *DB = nullptr,
                               AssumptionCache *AC = nullptr,
                               DominatorTree *DT = nullptr);
 
   /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor
   /// is returned in RedDes. If either \p DB is non-null or \p AC and \p DT are
   /// non-null, the minimal bit width needed to compute the reduction will be

llvm/lib/Analysis/IVDescriptors.cpp

for (User *U : Cur->users()) {
         if (isa<PHINode>(UI))
           PHIs.push_back(UI);
         else
           NonPHIs.push_back(UI);
       } else if (!isa<PHINode>(UI) &&
                  ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
                    !isa<SelectInst>(UI)) ||
                   (!isConditionalRdxPattern(Kind, UI).isRecurrence() &&
-                   !isMinMaxSelectCmpPattern(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.
-  if (isMinMaxRecurrenceKind(Kind) && NumCmpSelectPatternInst != 2)
+  // pattern or more than just a select and cmp. Zero implies that we saw a
+  // llvm.min/max instrinsic, which is always OK.
+  if (isMinMaxRecurrenceKind(Kind) && NumCmpSelectPatternInst != 2 &&
+      NumCmpSelectPatternInst != 0)
     return false;
 
   if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
     return false;
 
   const bool IsOrdered = checkOrderedReduction(
       Kind, ReduxDesc.getExactFPMathInst(), ExitInstruction, Phi);
 
RecurrenceDescriptor RD(RdxStart, ExitInstruction, Kind, FMF,
                           ReduxDesc.getExactFPMathInst(), RecurrenceType,
                           IsSigned, IsOrdered, CastInsts);
   RedDes = RD;
 
   return true;
 }
 
 RecurrenceDescriptor::InstDesc
-RecurrenceDescriptor::isMinMaxSelectCmpPattern(Instruction *I,
-                                               const InstDesc &Prev) {
-  assert((isa<CmpInst>(I) || isa<SelectInst>(I)) &&
-         "Expected a cmp or select instruction");
+RecurrenceDescriptor::isMinMaxPattern(Instruction *I, RecurKind Kind,
+  assert((isa<CmpInst>(I) || isa<SelectInst>(I) || isa<CallInst>(I)) &&
+         "Expected a cmp or select or call instruction");
+  if (!isMinMaxRecurrenceKind(Kind))
+    return InstDesc(false, I);
 
   // We must handle the select(cmp()) 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());
   }
 
-  // Only match select with single use cmp condition.
-  if (!match(I, m_Select(m_OneUse(m_Cmp(Pred, m_Value(), m_Value())), m_Value(),
+  // Only match select with single use cmp condition, or a min/max intrinsic.
+  if (!isa<IntrinsicInst>(I) &&
+      !match(I, m_Select(m_OneUse(m_Cmp(Pred, m_Value(), m_Value())), m_Value(),
                          m_Value())))
     return InstDesc(false, I);
 
   // Look for a min/max pattern.
   if (match(I, m_UMin(m_Value(), m_Value())))
-    return InstDesc(I, RecurKind::UMin);
+    return InstDesc(Kind == RecurKind::UMin, I);
   if (match(I, m_UMax(m_Value(), m_Value())))
-    return InstDesc(I, RecurKind::UMax);
+    return InstDesc(Kind == RecurKind::UMax, I);
   if (match(I, m_SMax(m_Value(), m_Value())))
-    return InstDesc(I, RecurKind::SMax);
+    return InstDesc(Kind == RecurKind::SMax, I);
   if (match(I, m_SMin(m_Value(), m_Value())))
-    return InstDesc(I, RecurKind::SMin);
+    return InstDesc(Kind == RecurKind::SMin, I);
   if (match(I, m_OrdFMin(m_Value(), m_Value())))
-    return InstDesc(I, RecurKind::FMin);
+    return InstDesc(Kind == RecurKind::FMin, I);
   if (match(I, m_OrdFMax(m_Value(), m_Value())))
-    return InstDesc(I, RecurKind::FMax);
+    return InstDesc(Kind == RecurKind::FMax, I);
   if (match(I, m_UnordFMin(m_Value(), m_Value())))
-    return InstDesc(I, RecurKind::FMin);
+    return InstDesc(Kind == RecurKind::FMin, I);
   if (match(I, m_UnordFMax(m_Value(), m_Value())))
-    return InstDesc(I, RecurKind::FMax);
+    return InstDesc(Kind == RecurKind::FMax, I);
+  if (match(I, m_Intrinsic<Intrinsic::minnum>(m_Value(), m_Value())))
+    return InstDesc(Kind == RecurKind::FMin, I);
+  if (match(I, m_Intrinsic<Intrinsic::maxnum>(m_Value(), m_Value())))
+    return InstDesc(Kind == RecurKind::FMax, I);
 
   return InstDesc(false, I);
 }
 
 /// Returns true if the select instruction has users in the compare-and-add
 /// reduction pattern below. The select instruction argument is the last one
 /// in the sequence.
 ///
RecurrenceDescriptor::isConditionalRdxPattern(RecurKind Kind, Instruction *I) {
   if (m_FMul(m_Value(Op1), m_Value(Op2)).match(I1) && (I1->isFast()))
     return InstDesc(Kind == RecurKind::FMul, SI);
 
   return InstDesc(false, I);
 }
 
 RecurrenceDescriptor::InstDesc
 RecurrenceDescriptor::isRecurrenceInstr(Instruction *I, RecurKind Kind,
-                                        InstDesc &Prev, FastMathFlags FMF) {
+                                        InstDesc &Prev, FastMathFlags FuncFMF) {
+  assert(Prev.getRecKind() == RecurKind::None || Prev.getRecKind() == Kind);
   switch (I->getOpcode()) {
   default:
     return InstDesc(false, I);
   case Instruction::PHI:
     return InstDesc(I, Prev.getRecKind(), Prev.getExactFPMathInst());
   case Instruction::Sub:
   case Instruction::Add:
     return InstDesc(Kind == RecurKind::Add, I);
case Instruction::FAdd:
     return InstDesc(Kind == RecurKind::FAdd, I,
                     I->hasAllowReassoc() ? nullptr : I);
   case Instruction::Select:
     if (Kind == RecurKind::FAdd || Kind == RecurKind::FMul)
       return isConditionalRdxPattern(Kind, I);
     LLVM_FALLTHROUGH;
   case Instruction::FCmp:
   case Instruction::ICmp:
+  case Instruction::Call:
     if (isIntMinMaxRecurrenceKind(Kind) ||
-        (FMF.noNaNs() && FMF.noSignedZeros() && isFPMinMaxRecurrenceKind(Kind)))
-      return isMinMaxSelectCmpPattern(I, Prev);
+        (((FuncFMF.noNaNs() && FuncFMF.noSignedZeros()) ||
+          (isa<FPMathOperator>(I) && I->hasNoNaNs() &&
+           I->hasNoSignedZeros())) &&
+         isFPMinMaxRecurrenceKind(Kind)))
+      return isMinMaxPattern(I, Kind, Prev);
     return InstDesc(false, I);
   }
 }
 
 bool RecurrenceDescriptor::hasMultipleUsesOf(
     Instruction *I, SmallPtrSetImpl<Instruction *> &Insts,
     unsigned MaxNumUses) {
   unsigned NumUses = 0;

llvm/test/Transforms/LoopVectorize/minmax_reduction.ll

for.body:
   %exitcond = icmp eq i64 %indvars.iv.next, 1024
   br i1 %exitcond, label %for.end, label %for.body
 
 for.end:
   ret float %max.red.0
 }
 
 ; CHECK-LABEL: @smin_intrinsic(
-; CHECK-NOT: <2 x i32> @llvm.smin.v2i32
+; CHECK: <2 x i32> @llvm.smin.v2i32
+; CHECK: i32 @llvm.vector.reduce.smin.v2i32
 define i32 @smin_intrinsic(i32* nocapture readonly %x) {
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %entry, %for.body
   %i.012 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
   %s.011 = phi i32 [ 100, %entry ], [ %1, %for.body ]
   %arrayidx = getelementptr inbounds i32, i32* %x, i32 %i.012
   %0 = load i32, i32* %arrayidx, align 4
   %1 = tail call i32 @llvm.smin.i32(i32 %s.011, i32 %0)
   %inc = add nuw nsw i32 %i.012, 1
   %exitcond.not = icmp eq i32 %inc, 1024
   br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
 
 for.cond.cleanup:                                 ; preds = %for.body
   ret i32 %1
 }
 
 ; CHECK-LABEL: @smax_intrinsic(
-; CHECK-NOT: <2 x i32> @llvm.smax.v2i32
+; CHECK: <2 x i32> @llvm.smax.v2i32
+; CHECK: i32 @llvm.vector.reduce.smax.v2i32
 define i32 @smax_intrinsic(i32* nocapture readonly %x) {
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %entry, %for.body
   %i.012 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
   %s.011 = phi i32 [ 100, %entry ], [ %1, %for.body ]
   %arrayidx = getelementptr inbounds i32, i32* %x, i32 %i.012
   %0 = load i32, i32* %arrayidx, align 4
   %1 = tail call i32 @llvm.smax.i32(i32 %s.011, i32 %0)
   %inc = add nuw nsw i32 %i.012, 1
   %exitcond.not = icmp eq i32 %inc, 1024
   br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
 
 for.cond.cleanup:                                 ; preds = %for.body
   ret i32 %1
 }
 
 ; CHECK-LABEL: @umin_intrinsic(
-; CHECK-NOT: <2 x i32> @llvm.umin.v2i32
+; CHECK: <2 x i32> @llvm.umin.v2i32
+; CHECK: i32 @llvm.vector.reduce.umin.v2i32
 define i32 @umin_intrinsic(i32* nocapture readonly %x) {
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %entry, %for.body
   %i.012 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
   %s.011 = phi i32 [ 100, %entry ], [ %1, %for.body ]
   %arrayidx = getelementptr inbounds i32, i32* %x, i32 %i.012
   %0 = load i32, i32* %arrayidx, align 4
   %1 = tail call i32 @llvm.umin.i32(i32 %s.011, i32 %0)
   %inc = add nuw nsw i32 %i.012, 1
   %exitcond.not = icmp eq i32 %inc, 1024
   br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
 
 for.cond.cleanup:                                 ; preds = %for.body
   ret i32 %1
 }
 
 ; CHECK-LABEL: @umax_intrinsic(
-; CHECK-NOT: <2 x i32> @llvm.umax.v2i32
+; CHECK: <2 x i32> @llvm.umax.v2i32
+; CHECK: i32 @llvm.vector.reduce.umax.v2i32
 define i32 @umax_intrinsic(i32* nocapture readonly %x) {
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %entry, %for.body
   %i.012 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
   %s.011 = phi i32 [ 100, %entry ], [ %1, %for.body ]
   %arrayidx = getelementptr inbounds i32, i32* %x, i32 %i.012
   %0 = load i32, i32* %arrayidx, align 4
   %1 = tail call i32 @llvm.umax.i32(i32 %s.011, i32 %0)
   %inc = add nuw nsw i32 %i.012, 1
   %exitcond.not = icmp eq i32 %inc, 1024
   br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
 
 for.cond.cleanup:                                 ; preds = %for.body
   ret i32 %1
 }
 
 ; CHECK-LABEL: @fmin_intrinsic(
-; CHECK-NOT: nnan nsz <2 x float> @llvm.minnum.v2f32
+; CHECK: nnan nsz <2 x float> @llvm.minnum.v2f32
+; CHECK: nnan nsz float @llvm.vector.reduce.fmin.v2f32
 define float @fmin_intrinsic(float* nocapture readonly %x) {
 entry:
   br label %for.body
 
 for.cond.cleanup:                                 ; preds = %for.body
   ret float %1
 
 for.body:                                         ; preds = %entry, %for.body
   %i.012 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
   %s.011 = phi float [ 0.000000e+00, %entry ], [ %1, %for.body ]
   %arrayidx = getelementptr inbounds float, float* %x, i32 %i.012
   %0 = load float, float* %arrayidx, align 4
   %1 = tail call nnan nsz float @llvm.minnum.f32(float %s.011, float %0)
   %inc = add nuw nsw i32 %i.012, 1
   %exitcond.not = icmp eq i32 %inc, 1024
   br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
 }
 
 ; CHECK-LABEL: @fmax_intrinsic(
-; CHECK-NOT: fast <2 x float> @llvm.maxnum.v2f32
+; CHECK: fast <2 x float> @llvm.maxnum.v2f32
+; CHECK: fast float @llvm.vector.reduce.fmax.v2f32
 define float @fmax_intrinsic(float* nocapture readonly %x) {
 entry:
   br label %for.body
 
 for.cond.cleanup:                                 ; preds = %for.body
   ret float %1
 
 for.body:                                         ; preds = %entry, %for.body
   %i.012 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
   %s.011 = phi float [ 0.000000e+00, %entry ], [ %1, %for.body ]
   %arrayidx = getelementptr inbounds float, float* %x, i32 %i.012
   %0 = load float, float* %arrayidx, align 4
   %1 = tail call fast float @llvm.maxnum.f32(float %s.011, float %0)
   %inc = add nuw nsw i32 %i.012, 1
   %exitcond.not = icmp eq i32 %inc, 1024
   br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
 }
 
 ; CHECK-LABEL: @fmin_intrinsic_nofast(
 ; CHECK-NOT: <2 x float> @llvm.minnum.v2f32
 define float @fmin_intrinsic_nofast(float* nocapture readonly %x) {
for.body:                                         ; preds = %entry, %for.body
   %1 = load i32, i32* %arrayidx3, align 4
   %cond9 = tail call i32 @llvm.smax.i32(i32 %s.0., i32 %1)
   %inc = add nuw nsw i32 %i.025, 1
   %exitcond.not = icmp eq i32 %inc, 1024
   br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
 }
 
 ; CHECK-LABEL: @sminmin(
-; CHECK-NOT: <2 x i32> @llvm.smin.v2i32
-; CHECK-NOT: <2 x i32> @llvm.smin.v2i32
+; CHECK: <2 x i32> @llvm.smin.v2i32
+; CHECK: <2 x i32> @llvm.smin.v2i32
+; CHECK: i32 @llvm.vector.reduce.smin.v2i32
 define i32 @sminmin(i32* nocapture readonly %x, i32* nocapture readonly %y) {
 entry:
   br label %for.body
 
 for.cond.cleanup:                                 ; preds = %for.body
   ret i32 %cond9
 
 for.body:                                         ; preds = %entry, %for.body