[ExpandReductions] Add lowering for minimum/maximum reductions

[anna]

Summary

This patch adds the lowering for these minimum/maximum reduction intrinsics in the expand reductions pass.
If the nnan/nsz flags are present, these are propagated as well. The reduction is done as a series of shuffles
with vectorized minimum/maximum intrinsics.

This patch adds the lowering for the intrinsic introduced in https://reviews.llvm.org/D152370.

[anna]

Done directly through SelectionDAG lowering. Closing this off.

llvm/include/llvm/Analysis/IVDescriptors.h

enum class RecurKind {
   SMin,       ///< Signed integer min implemented in terms of select(cmp()).
   SMax,       ///< Signed integer max implemented in terms of select(cmp()).
   UMin,       ///< Unisgned 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,    ///< Fused multiply-add of floats (a * b + c).
   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
 };
 
 /// The RecurrenceDescriptor is used to identify recurrences variables in a
public:
   /// Returns true if the recurrence kind is an integer min/max kind.
   static bool isIntMinMaxRecurrenceKind(RecurKind Kind) {
     return Kind == RecurKind::UMin || Kind == RecurKind::UMax ||
            Kind == RecurKind::SMin || Kind == RecurKind::SMax;
   }
 
   /// Returns true if the recurrence kind is a floating-point min/max kind.
   static bool isFPMinMaxRecurrenceKind(RecurKind Kind) {
-    return Kind == RecurKind::FMin || Kind == RecurKind::FMax;
+    return Kind == RecurKind::FMin || Kind == RecurKind::FMax ||
+           Kind == RecurKind::FMinimum || Kind == RecurKind::FMaximum;
   }
 
   /// 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

llvm/lib/CodeGen/ExpandReductions.cpp

case Intrinsic::vector_reduce_xor:
     return Instruction::Xor;
   case Intrinsic::vector_reduce_smax:
   case Intrinsic::vector_reduce_smin:
   case Intrinsic::vector_reduce_umax:
   case Intrinsic::vector_reduce_umin:
     return Instruction::ICmp;
   case Intrinsic::vector_reduce_fmax:
   case Intrinsic::vector_reduce_fmin:
+  case Intrinsic::vector_reduce_fmaximum:
+  case Intrinsic::vector_reduce_fminimum:
     return Instruction::FCmp;
   default:
     llvm_unreachable("Unexpected ID");
   }
 }
 
 RecurKind getRK(Intrinsic::ID ID) {
   switch (ID) {
   case Intrinsic::vector_reduce_smax:
     return RecurKind::SMax;
   case Intrinsic::vector_reduce_smin:
     return RecurKind::SMin;
   case Intrinsic::vector_reduce_umax:
     return RecurKind::UMax;
   case Intrinsic::vector_reduce_umin:
     return RecurKind::UMin;
   case Intrinsic::vector_reduce_fmax:
     return RecurKind::FMax;
   case Intrinsic::vector_reduce_fmin:
     return RecurKind::FMin;
+  case Intrinsic::vector_reduce_fmaximum:
+    return RecurKind::FMaximum;
+  case Intrinsic::vector_reduce_fminimum:
+    return RecurKind::FMinimum;
   default:
     return RecurKind::None;
   }
 }
 
 bool expandReductions(Function &F, const TargetTransformInfo *TTI) {
   bool Changed = false;
   SmallVector<IntrinsicInst *, 4> Worklist;
if (auto *II = dyn_cast<IntrinsicInst>(&I)) {
       case Intrinsic::vector_reduce_or:
       case Intrinsic::vector_reduce_xor:
       case Intrinsic::vector_reduce_smax:
       case Intrinsic::vector_reduce_smin:
       case Intrinsic::vector_reduce_umax:
       case Intrinsic::vector_reduce_umin:
       case Intrinsic::vector_reduce_fmax:
       case Intrinsic::vector_reduce_fmin:
+      case Intrinsic::vector_reduce_fminimum:
+      case Intrinsic::vector_reduce_fmaximum:
         if (TTI->shouldExpandReduction(II))
           Worklist.push_back(II);
 
         break;
       }
     }
   }
 
case Intrinsic::vector_reduce_fmin: {
       if (!isPowerOf2_32(
               cast<FixedVectorType>(Vec->getType())->getNumElements()) ||
           !FMF.noNaNs())
         continue;
 
       Rdx = getShuffleReduction(Builder, Vec, getOpcode(ID), RK);
       break;
     }
+    case Intrinsic::vector_reduce_fmaximum:
+    case Intrinsic::vector_reduce_fminimum: {
+      Value *Vec = II->getArgOperand(0);
+      if (!isPowerOf2_32(
+              cast<FixedVectorType>(Vec->getType())->getNumElements()))
+        continue;
+
+      Rdx = getShuffleReduction(Builder, Vec, getOpcode(ID), RK);
+      break;
+    }
     }
     II->replaceAllUsesWith(Rdx);
     II->eraseFromParent();
     Changed = true;
   }
   return Changed;
 }
 

llvm/lib/Transforms/Utils/LoopUtils.cpp

 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/IR/DIBuilder.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/MDBuilder.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/ProfDataUtils.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
Intrinsic::ID llvm::getMinMaxReductionIntrinsicOp(RecurKind RK) {
   case RecurKind::SMin:
     return Intrinsic::smin;
   case RecurKind::SMax:
     return Intrinsic::smax;
   case RecurKind::FMin:
     return Intrinsic::minnum;
   case RecurKind::FMax:
     return Intrinsic::maxnum;
+  case RecurKind::FMinimum:
+    return Intrinsic::minimum;
+  case RecurKind::FMaximum:
+    return Intrinsic::maximum;
   }
 }
 
 CmpInst::Predicate llvm::getMinMaxReductionPredicate(RecurKind RK) {
   switch (RK) {
   default:
     llvm_unreachable("Unknown min/max recurrence kind");
   case RecurKind::UMin:
Value *llvm::createSelectCmpOp(IRBuilderBase &Builder, Value *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,
                             Value *Right) {
   Type *Ty = Left->getType();
-  if (Ty->isIntOrIntVectorTy()) {
+  if (Ty->isIntOrIntVectorTy() ||
+      (RK == RecurKind::FMinimum || RK == RecurKind::FMaximum)) {
     // TODO: Add float minnum/maxnum support when FMF nnan is set.
     Intrinsic::ID Id = getMinMaxReductionIntrinsicOp(RK);
     return Builder.CreateIntrinsic(Ty, Id, {Left, Right}, nullptr,
                                    "rdx.minmax");
   }
   CmpInst::Predicate Pred = getMinMaxReductionPredicate(RK);
   Value *Cmp = Builder.CreateCmp(Pred, Left, Right, "rdx.minmax.cmp");
   Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select");

llvm/test/CodeGen/Generic/expand-experimental-reductions.ll

 declare i64 @llvm.vector.reduce.smax.v2i64(<2 x i64>)
 declare i64 @llvm.vector.reduce.smin.v2i64(<2 x i64>)
 declare i64 @llvm.vector.reduce.umax.v2i64(<2 x i64>)
 declare i64 @llvm.vector.reduce.umin.v2i64(<2 x i64>)
 
 declare double @llvm.vector.reduce.fmax.v2f64(<2 x double>)
 declare double @llvm.vector.reduce.fmin.v2f64(<2 x double>)
 
+declare double @llvm.vector.reduce.fmaximum.v2f64(<2 x double>)
+declare float @llvm.vector.reduce.fmaximum.v4f32(<4 x float>)
+declare double @llvm.vector.reduce.fminimum.v2f64(<2 x double>)
+
 declare i8 @llvm.vector.reduce.and.i8.v3i8(<3 x i8>)
 
 define i64 @add_i64(<2 x i64> %vec) {
 ; CHECK-LABEL: @add_i64(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[RDX_SHUF:%.*]] = shufflevector <2 x i64> [[VEC:%.*]], <2 x i64> poison, <2 x i32> <i32 1, i32 poison>
 ; CHECK-NEXT:    [[BIN_RDX:%.*]] = add <2 x i64> [[VEC]], [[RDX_SHUF]]
 ; CHECK-NEXT:    [[TMP0:%.*]] = extractelement <2 x i64> [[BIN_RDX]], i32 0

 ; CHECK-NEXT:    [[R:%.*]] = call double @llvm.vector.reduce.fmin.v2f64(<2 x double> [[VEC:%.*]])
 ; CHECK-NEXT:    ret double [[R]]
 ;
 entry:
   %r = call double @llvm.vector.reduce.fmin.v2f64(<2 x double> %vec)
   ret double %r
 }
 
+define double @fminimum_f64(<2 x double> %vec) {
+; CHECK-LABEL: @fminimum_f64(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[RDX_SHUF:%.*]] = shufflevector <2 x double> [[VEC:%.*]], <2 x double> poison, <2 x i32> <i32 1, i32 poison>
+; CHECK-NEXT:    [[RDX_MINMAX:%.*]] = call <2 x double> @llvm.minimum.v2f64(<2 x double> [[VEC]], <2 x double> [[RDX_SHUF]])
+; CHECK-NEXT:    [[TMP0:%.*]] = extractelement <2 x double> [[RDX_MINMAX]], i32 0
+; CHECK-NEXT:    ret double [[TMP0]]
+;
+entry:
+  %r = call double @llvm.vector.reduce.fminimum.v2f64(<2 x double> %vec)
+  ret double %r
+}
+
+define double @fmaximum_f64(<2 x double> %vec) {
+; CHECK-LABEL: @fmaximum_f64(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[RDX_SHUF:%.*]] = shufflevector <2 x double> [[VEC:%.*]], <2 x double> poison, <2 x i32> <i32 1, i32 poison>
+; CHECK-NEXT:    [[RDX_MINMAX:%.*]] = call <2 x double> @llvm.maximum.v2f64(<2 x double> [[VEC]], <2 x double> [[RDX_SHUF]])
+; CHECK-NEXT:    [[TMP0:%.*]] = extractelement <2 x double> [[RDX_MINMAX]], i32 0
+; CHECK-NEXT:    ret double [[TMP0]]
+;
+entry:
+  %r = call double @llvm.vector.reduce.fmaximum.v2f64(<2 x double> %vec)
+  ret double %r
+}
+
+define float @fmaximum_f32(<4 x float> %vec) {
+; CHECK-LABEL: @fmaximum_f32(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[RDX_SHUF:%.*]] = shufflevector <4 x float> [[VEC:%.*]], <4 x float> poison, <4 x i32> <i32 2, i32 3, i32 poison, i32 poison>
+; CHECK-NEXT:    [[RDX_MINMAX:%.*]] = call <4 x float> @llvm.maximum.v4f32(<4 x float> [[VEC]], <4 x float> [[RDX_SHUF]])
+; CHECK-NEXT:    [[RDX_SHUF1:%.*]] = shufflevector <4 x float> [[RDX_MINMAX]], <4 x float> poison, <4 x i32> <i32 1, i32 poison, i32 poison, i32 poison>
+; CHECK-NEXT:    [[RDX_MINMAX2:%.*]] = call <4 x float> @llvm.maximum.v4f32(<4 x float> [[RDX_MINMAX]], <4 x float> [[RDX_SHUF1]])
+; CHECK-NEXT:    [[TMP0:%.*]] = extractelement <4 x float> [[RDX_MINMAX2]], i32 0
+; CHECK-NEXT:    ret float [[TMP0]]
+;
+entry:
+  %r = call float @llvm.vector.reduce.fmaximum.v4f32(<4 x float> %vec)
+  ret float %r
+}
+
+define float @fmaximum_f32_nnan(<4 x float> %vec) {
+; CHECK-LABEL: @fmaximum_f32_nnan(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[RDX_SHUF:%.*]] = shufflevector <4 x float> [[VEC:%.*]], <4 x float> poison, <4 x i32> <i32 2, i32 3, i32 poison, i32 poison>
+; CHECK-NEXT:    [[RDX_MINMAX:%.*]] = call nnan <4 x float> @llvm.maximum.v4f32(<4 x float> [[VEC]], <4 x float> [[RDX_SHUF]])
+; CHECK-NEXT:    [[RDX_SHUF1:%.*]] = shufflevector <4 x float> [[RDX_MINMAX]], <4 x float> poison, <4 x i32> <i32 1, i32 poison, i32 poison, i32 poison>
+; CHECK-NEXT:    [[RDX_MINMAX2:%.*]] = call nnan <4 x float> @llvm.maximum.v4f32(<4 x float> [[RDX_MINMAX]], <4 x float> [[RDX_SHUF1]])
+; CHECK-NEXT:    [[TMP0:%.*]] = extractelement <4 x float> [[RDX_MINMAX2]], i32 0
+; CHECK-NEXT:    ret float [[TMP0]]
+;
+entry:
+  %r = call nnan float @llvm.vector.reduce.fmaximum.v4f32(<4 x float> %vec)
+  ret float %r
+}
+
 ; FIXME: Why is this not expanded?
 
 ; Test when the vector size is not power of two.
 define i8 @test_v3i8(<3 x i8> %a) nounwind {
 ; CHECK-LABEL: @test_v3i8(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[B:%.*]] = call i8 @llvm.vector.reduce.and.v3i8(<3 x i8> [[A:%.*]])
 ; CHECK-NEXT:    ret i8 [[B]]
 ;
 entry:
   %b = call i8 @llvm.vector.reduce.and.i8.v3i8(<3 x i8> %a)
   ret i8 %b
 }