[IR] New function llvm::createMinMaxSelectCmpOp for creating min/max operation in select-cmp form

[Mel-Chen]

Summary

This patch preserves the ability to represent min max operations in select-cmp form. This provides flexibility in choosing between intrinsic or select-cmp form for generating min max operations, depending on the optimization requirements.

[xbolva00]

llvm/lib/Transforms/Utils/LoopUtils.cpp

943

We have intrinsics for min and max. Do not emit cmp select form..

952

Why we dont use intrinsic in all cases?

[Mel-Chen]

llvm/lib/Transforms/Utils/LoopUtils.cpp

943

I am aware that we can use intrinsic to represent min max operations, but this patch aims to preserve the ability to express min max operations in select-cmp form. This is necessary for the vectorization feature I am currently developing. It is important to emphasize that this patch does not enforce the use of select-cmp form for min max operations, but rather provides an additional option.

952

Refer to D148221.
My understanding is that for fp min max there are still some FMF issues to be handled.
@RKSimon

[nikic]

llvm/lib/Transforms/Utils/LoopUtils.cpp

943

Why does your patch require the non-canonical select-cmp form? Please explain this in the patch description.

[xbolva00]

llvm/lib/Transforms/Utils/LoopUtils.cpp

943

This is necessary for the vectorization feature I am currently developing.

Can you please share so we can check it and possibly suggest some tips?

[Mel-Chen]

Update commit log.

[Mel-Chen]

llvm/lib/Transforms/Utils/LoopUtils.cpp

943

@nikic @xbolva00 Sure. Here is the WIP patch: D143465
In short, we are developing a new reduction pattern, min max with index, for the vectorizer. In the function fixReduction process for interleaving, we need to generate the following IR in middle.block:

middle.block:                                     ; preds = %vector.body
  ;; Start to fix minmax reduction
  %rdx.minmax.cmp = icmp sgt i64 %12, %13
  %rdx.minmax.select = select i1 %rdx.minmax.cmp, i64 %12, i64 %13
  %rdx.minmax.cmp8 = icmp sgt i64 %rdx.minmax.select, %14
  %rdx.minmax.select9 = select i1 %rdx.minmax.cmp8, i64 %rdx.minmax.select, i64 %14
  %rdx.minmax.cmp10 = icmp sgt i64 %rdx.minmax.select9, %15
  %rdx.minmax.select11 = select i1 %rdx.minmax.cmp10, i64 %rdx.minmax.select9, i64 %15
   ;; Start to fix index reduction
  %rdx.select = select i1 %rdx.minmax.cmp, i64 %20, i64 %21
  %rdx.select12 = select i1 %rdx.minmax.cmp8, i64 %rdx.select, i64 %22
  %rdx.select13 = select i1 %rdx.minmax.cmp10, i64 %rdx.select12, i64 %23

For the handling of index reduction, we require the cmp part of the min max operation. This is the reason why I need this patch.

[RKSimon]

llvm/lib/Transforms/Utils/LoopUtils.cpp

952

maxnum/minnum reductions are sensitive to ordering if the values might be nan

[fhahn]

llvm/lib/Transforms/Utils/LoopUtils.cpp

943

To clarify, is the sequence below could be expressed using intrinsics,

%rdx.minmax.cmp = icmp sgt i64 %12, %13
%rdx.minmax.select = select i1 %rdx.minmax.cmp, i64 %12, i64 %13
%rdx.minmax.cmp8 = icmp sgt i64 %rdx.minmax.select, %14
%rdx.minmax.select9 = select i1 %rdx.minmax.cmp8, i64 %rdx.minmax.select, i64 %14
%rdx.minmax.cmp10 = icmp sgt i64 %rdx.minmax.select9, %15
%rdx.minmax.select11 = select i1 %rdx.minmax.cmp10, i64 %rdx.minmax.select9, i64 %15

but you would like to re-use the compares from above for the selcets below:

 ;; Start to fix index reduction
%rdx.select = select i1 %rdx.minmax.cmp, i64 %20, i64 %21
%rdx.select12 = select i1 %rdx.minmax.cmp8, i64 %rdx.select, i64 %22
%rdx.select13 = select i1 %rdx.minmax.cmp10, i64 %rdx.select12, i64 %23

If that's the case it would probably be better to just keep the min/max select generation code local to the code that generates the 2nd chain of selects, instead of exposing this as general API

943

but you would like to re-use the compares from above for the selcets below:

@Mel-Chen is the comment above an accurate summary?

[Mel-Chen]

llvm/lib/Transforms/Utils/LoopUtils.cpp

943

@fhahn
Exactly, that's correct. I also believe there are better ways to address it, such as changing to generate the CmpInst during fixing index reduction, or generating an additional CmpInst during fixing min max reduction. Once I fix the issue you described, this patch will be abandoned. However, until it is fixed, we will temporarily rely on this patch.

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

 /// 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);
 
+/// Returns a Min/Max operation in select-cmp form corresponding to
+/// MinMaxRecurrenceKind.
+///   Select(Cmp(strict min max predicate, Left, Right), Left, Right)
+/// The Builder's fast-math-flags must be set to propagate the expected values.
+Value *createMinMaxSelectCmpOp(IRBuilderBase &Builder, RecurKind RK,
+                               Value *Left, Value *Right);
+
 /// 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,
                            unsigned Op, RecurKind MinMaxKind = RecurKind::None);

llvm/lib/Transforms/Utils/LoopUtils.cpp

Value *llvm::createSelectCmpOp(IRBuilderBase &Builder, Value *StartVal,
                                RecurKind RK, Value *Left, Value *Right) {
   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::createMinMaxSelectCmpOp(IRBuilderBase &Builder, RecurKind RK,
+                                     Value *Left, Value *Right) {
+  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");
+  return Select;
+}
+
 Value *llvm::createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left,
                             Value *Right) {
   Type *Ty = Left->getType();
   if (Ty->isIntOrIntVectorTy()) {
     // 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");
-  return Select;
+  return createMinMaxSelectCmpOp(Builder, RK, Left, Right);
 }
 
 // Helper to generate an ordered reduction.
 Value *llvm::getOrderedReduction(IRBuilderBase &Builder, Value *Acc, Value *Src,
                                  unsigned Op, RecurKind RdxKind) {
   unsigned VF = cast<FixedVectorType>(Src->getType())->getNumElements();
 
   // Extract and apply reduction ops in ascending order: