[InstCombine] Add support for maximum(a,b) + minimum(a,b) => a + b

[skatkov]

Summary

Unfortunately alive2 cannot prove the correctness due to fails by timeout even for
float type half.

However it should be correct. If a and b are not NaN, maximum and minimum will just
return different values (a and b) and take into account a + b == b + a this is the same.
If a or b is NaN, than maximum and minimum are equal to NaN and NaN + NaN is NaN.
a + b is also a NaN.

In terms of preserving fast flags, we cannot preserve ninf due to
minimum(NaN, Infinity) == maximum(NaN, Infinity) == NaN,
minimum(NaN, Infinity) +ninf maximum(NaN, Infinity) == NaN +ninf NaN = NaN
However transformation will change
minimum(NaN, Infinity) + maximum(NaN, Infinity) to NaN +ninf Infinity == poison.

But if fadd is marked as nnan, we can preserve because NaN +ninf/nnan NaN = poison as well.

The same optimization for

maximum(a,b) * minimum(a,b) => a * b

is added.
All said above for fadd is correct for fmul.

[RKSimon]

maximum/minimum propagate nan if present in either argument - I think that's OK here but could do with a second opinion

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1814

minumin -> minimum

1820

Its it worth adding a m_c_Intrinsic matcher?

llvm/test/Transforms/InstCombine/fmul-maximum-minimum.ll

18

vector tests? more commute tests?

[skatkov]

Added new tests and pre-land them.
Fix fast math flags copying.
Introduced m_c_Intrinsic.

[skatkov]

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

775

Hrrrr, minimum again. Will update before landing or next iteration.

[mkazantsev]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1818

We could also match min(a, b) + max(b, a)

[skatkov]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1818

we do, see the test @test_comm2.
Actually it was m_c versus m_ does.

[mkazantsev]

llvm/test/Transforms/InstCombine/fadd-maximum-minimum.ll

14

Add test on (MAX + MIN)?

[mkazantsev]

llvm/test/Transforms/InstCombine/fadd-maximum-minimum.ll

14

Ah ok, its there already.

[mkazantsev]

Maybe it makes sense to add alive2 links into test or code comments to demonstrate correctness.

[skatkov]

In D147299#4247852, @mkazantsev wrote:

Maybe it makes sense to add alive2 links into test or code comments to demonstrate correctness.

As I wrote in description, alive2 ends with timeout on these tests.

llvm/include/llvm/IR/PatternMatch.h

match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>,
                      MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>>,
     match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>,
                      MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>>>
 m_c_MaxOrMin(const LHS &L, const RHS &R) {
   return m_CombineOr(m_CombineOr(m_c_SMax(L, R), m_c_SMin(L, R)),
                      m_CombineOr(m_c_UMax(L, R), m_c_UMin(L, R)));
 }
 
+template <Intrinsic::ID IntrID, typename T0, typename T1>
+inline match_combine_or<typename m_Intrinsic_Ty<T0, T1>::Ty,
+                        typename m_Intrinsic_Ty<T1, T0>::Ty>
+m_c_Intrinsic(const T0 &Op0, const T1 &Op1) {
+  return m_CombineOr(m_Intrinsic<IntrID>(Op0, Op1),
+                     m_Intrinsic<IntrID>(Op1, Op0));
+}
+
 /// Matches FAdd with LHS and RHS in either order.
 template <typename LHS, typename RHS>
 inline BinaryOp_match<LHS, RHS, Instruction::FAdd, true>
 m_c_FAdd(const LHS &L, const RHS &R) {
   return BinaryOp_match<LHS, RHS, Instruction::FAdd, true>(L, R);
 }
 
 /// Matches FMul with LHS and RHS in either order.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (I.hasAllowReassoc() && I.hasNoSignedZeros()) {
     if (match(&I, m_c_FAdd(m_FSub(m_FNeg(m_Value(X)), m_Value(Y)),
                            m_c_FAdd(m_Deferred(X), m_Value(Z)))))
       return BinaryOperator::CreateFSubFMF(Z, Y, &I);
 
     if (Value *V = FAddCombine(Builder).simplify(&I))
       return replaceInstUsesWith(I, V);
   }
 
+  // minumum(X, Y) + maximum(X, Y) => X + Y.
+  if (match(&I,
+            m_c_FAdd(m_Intrinsic<Intrinsic::maximum>(m_Value(X), m_Value(Y)),
+                     m_c_Intrinsic<Intrinsic::minimum>(m_Deferred(X),
+                                                       m_Deferred(Y))))) {
+    BinaryOperator *Result = BinaryOperator::CreateFAddFMF(X, Y, &I);
+    // We cannot preserve ninf if nnan flag is not set.
+    // If X is NaN and Y is Inf then in original program we had NaN + NaN,
+    // while in optimized version NaN + Inf and this is a poison with ninf flag.
+    if (!Result->hasNoNaNs())
+      Result->setHasNoInfs(false);
+    return Result;
+  }
+
   return nullptr;
 }
 
 /// Optimize pointer differences into the same array into a size.  Consider:
 ///  &A[10] - &A[0]: we should compile this to "10".  LHS/RHS are the pointer
 /// operands to the ptrtoint instructions for the LHS/RHS of the subtract.
 Value *InstCombinerImpl::OptimizePointerDifference(Value *LHS, Value *RHS,
                                                    Type *Ty, bool IsNUW) {

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

Instruction *InstCombinerImpl::visitFMul(BinaryOperator &I) {
   // Given a phi node with entry value as 0 and it used in fmul operation,
   // we can replace fmul with 0 safely and eleminate loop operation.
   PHINode *PN = nullptr;
   Value *Start = nullptr, *Step = nullptr;
   if (matchSimpleRecurrence(&I, PN, Start, Step) && I.hasNoNaNs() &&
       I.hasNoSignedZeros() && match(Start, m_Zero()))
     return replaceInstUsesWith(I, Start);
 
+  // minimun(X, Y) * maximum(X, Y) => X * Y.
+  if (match(&I,
+            m_c_FMul(m_Intrinsic<Intrinsic::maximum>(m_Value(X), m_Value(Y)),
+                     m_c_Intrinsic<Intrinsic::minimum>(m_Deferred(X),
+                                                       m_Deferred(Y))))) {
+    BinaryOperator *Result = BinaryOperator::CreateFMulFMF(X, Y, &I);
+    // We cannot preserve ninf if nnan flag is not set.
+    // If X is NaN and Y is Inf then in original program we had NaN * NaN,
+    // while in optimized version NaN * Inf and this is a poison with ninf flag.
+    if (!Result->hasNoNaNs())
+      Result->setHasNoInfs(false);
+    return Result;
+  }
+
   return nullptr;
 }
 
 /// Fold a divide or remainder with a select instruction divisor when one of the
 /// select operands is zero. In that case, we can use the other select operand
 /// because div/rem by zero is undefined.
 bool InstCombinerImpl::simplifyDivRemOfSelectWithZeroOp(BinaryOperator &I) {
   SelectInst *SI = dyn_cast<SelectInst>(I.getOperand(1));

llvm/test/Transforms/InstCombine/fadd-maximum-minimum.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 declare float    @llvm.minimum.f32(float %Val0, float %Val1)
 declare float    @llvm.maximum.f32(float %Val0, float %Val1)
 declare <4 x float>    @llvm.minimum.v4f32(<4 x float> %Val0, <4 x float> %Val1)
 declare <4 x float>    @llvm.maximum.v4f32(<4 x float> %Val0, <4 x float> %Val1)
 
 define float @test(float %a, float %b) {
 ; CHECK-LABEL: @test(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MIN:%.*]] = call float @llvm.minimum.f32(float [[A:%.*]], float [[B:%.*]])
-; CHECK-NEXT:    [[MAX:%.*]] = call float @llvm.maximum.f32(float [[A]], float [[B]])
-; CHECK-NEXT:    [[RES:%.*]] = fadd float [[MIN]], [[MAX]]
+; CHECK-NEXT:    [[RES:%.*]] = fadd float [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    ret float [[RES]]
 ;
 entry:
   %min = call float @llvm.minimum.f32(float %a, float %b)
   %max = call float @llvm.maximum.f32(float %a, float %b)
   %res = fadd float %min, %max
   ret float %res
 }
 
 define float @test_comm1(float %a, float %b) {
 ; CHECK-LABEL: @test_comm1(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MIN:%.*]] = call float @llvm.minimum.f32(float [[A:%.*]], float [[B:%.*]])
-; CHECK-NEXT:    [[MAX:%.*]] = call float @llvm.maximum.f32(float [[A]], float [[B]])
-; CHECK-NEXT:    [[RES:%.*]] = fadd float [[MAX]], [[MIN]]
+; CHECK-NEXT:    [[RES:%.*]] = fadd float [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    ret float [[RES]]
 ;
 entry:
   %min = call float @llvm.minimum.f32(float %a, float %b)
   %max = call float @llvm.maximum.f32(float %a, float %b)
   %res = fadd float %max, %min
   ret float %res
 }
 
 define float @test_comm2(float %a, float %b) {
 ; CHECK-LABEL: @test_comm2(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MIN:%.*]] = call float @llvm.minimum.f32(float [[A:%.*]], float [[B:%.*]])
-; CHECK-NEXT:    [[MAX:%.*]] = call float @llvm.maximum.f32(float [[B]], float [[A]])
-; CHECK-NEXT:    [[RES:%.*]] = fadd float [[MIN]], [[MAX]]
+; CHECK-NEXT:    [[RES:%.*]] = fadd float [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    ret float [[RES]]
 ;
 entry:
   %min = call float @llvm.minimum.f32(float %a, float %b)
   %max = call float @llvm.maximum.f32(float %b, float %a)
   %res = fadd float %min, %max
   ret float %res
 }
 
 define float @test_comm3(float %a, float %b) {
 ; CHECK-LABEL: @test_comm3(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MIN:%.*]] = call float @llvm.minimum.f32(float [[A:%.*]], float [[B:%.*]])
-; CHECK-NEXT:    [[MAX:%.*]] = call float @llvm.maximum.f32(float [[B]], float [[A]])
-; CHECK-NEXT:    [[RES:%.*]] = fadd float [[MAX]], [[MIN]]
+; CHECK-NEXT:    [[RES:%.*]] = fadd float [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    ret float [[RES]]
 ;
 entry:
   %min = call float @llvm.minimum.f32(float %a, float %b)
   %max = call float @llvm.maximum.f32(float %b, float %a)
   %res = fadd float %max, %min
   ret float %res
 }
 
 define <4 x float> @test_vect(<4 x float> %a, <4 x float> %b) {
 ; CHECK-LABEL: @test_vect(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MIN:%.*]] = call <4 x float> @llvm.minimum.v4f32(<4 x float> [[A:%.*]], <4 x float> [[B:%.*]])
-; CHECK-NEXT:    [[MAX:%.*]] = call <4 x float> @llvm.maximum.v4f32(<4 x float> [[B]], <4 x float> [[A]])
-; CHECK-NEXT:    [[RES:%.*]] = fadd <4 x float> [[MIN]], [[MAX]]
+; CHECK-NEXT:    [[RES:%.*]] = fadd <4 x float> [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    ret <4 x float> [[RES]]
 ;
 entry:
   %min = call <4 x float> @llvm.minimum.v4f32(<4 x float> %a, <4 x float> %b)
   %max = call <4 x float> @llvm.maximum.v4f32(<4 x float> %b, <4 x float> %a)
   %res = fadd <4 x float> %min, %max
   ret <4 x float> %res
 }
 
 define float @test_flags(float %a, float %b) {
 ; CHECK-LABEL: @test_flags(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MIN:%.*]] = call float @llvm.minimum.f32(float [[A:%.*]], float [[B:%.*]])
-; CHECK-NEXT:    [[MAX:%.*]] = call float @llvm.maximum.f32(float [[A]], float [[B]])
-; CHECK-NEXT:    [[RES:%.*]] = fadd fast float [[MIN]], [[MAX]]
+; CHECK-NEXT:    [[RES:%.*]] = fadd fast float [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    ret float [[RES]]
 ;
 entry:
   %min = call float @llvm.minimum.f32(float %a, float %b)
   %max = call float @llvm.maximum.f32(float %a, float %b)
   %res = fadd fast float %min, %max
   ret float %res
 }
 
 define float @test_flags2(float %a, float %b) {
 ; CHECK-LABEL: @test_flags2(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MIN:%.*]] = call float @llvm.minimum.f32(float [[A:%.*]], float [[B:%.*]])
-; CHECK-NEXT:    [[MAX:%.*]] = call float @llvm.maximum.f32(float [[A]], float [[B]])
-; CHECK-NEXT:    [[RES:%.*]] = fadd reassoc ninf nsz arcp contract afn float [[MIN]], [[MAX]]
+; CHECK-NEXT:    [[RES:%.*]] = fadd reassoc nsz arcp contract afn float [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    ret float [[RES]]
 ;
 entry:
   %min = call float @llvm.minimum.f32(float %a, float %b)
   %max = call float @llvm.maximum.f32(float %a, float %b)
   %res = fadd reassoc ninf nsz arcp contract afn float %min, %max
   ret float %res
 }

llvm/test/Transforms/InstCombine/fmul-maximum-minimum.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 declare float    @llvm.minimum.f32(float %Val0, float %Val1)
 declare float    @llvm.maximum.f32(float %Val0, float %Val1)
 declare <4 x float>    @llvm.minimum.v4f32(<4 x float> %Val0, <4 x float> %Val1)
 declare <4 x float>    @llvm.maximum.v4f32(<4 x float> %Val0, <4 x float> %Val1)
 
 define float @test(float %a, float %b) {
 ; CHECK-LABEL: @test(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MIN:%.*]] = call float @llvm.minimum.f32(float [[A:%.*]], float [[B:%.*]])
-; CHECK-NEXT:    [[MAX:%.*]] = call float @llvm.maximum.f32(float [[A]], float [[B]])
-; CHECK-NEXT:    [[RES:%.*]] = fmul float [[MIN]], [[MAX]]
+; CHECK-NEXT:    [[RES:%.*]] = fmul float [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    ret float [[RES]]
 ;
 entry:
   %min = call float @llvm.minimum.f32(float %a, float %b)
   %max = call float @llvm.maximum.f32(float %a, float %b)
   %res = fmul float %min, %max
   ret float %res
 }
 
 define float @test_comm1(float %a, float %b) {
 ; CHECK-LABEL: @test_comm1(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MIN:%.*]] = call float @llvm.minimum.f32(float [[A:%.*]], float [[B:%.*]])
-; CHECK-NEXT:    [[MAX:%.*]] = call float @llvm.maximum.f32(float [[A]], float [[B]])
-; CHECK-NEXT:    [[RES:%.*]] = fmul float [[MAX]], [[MIN]]
+; CHECK-NEXT:    [[RES:%.*]] = fmul float [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    ret float [[RES]]
 ;
 entry:
   %min = call float @llvm.minimum.f32(float %a, float %b)
   %max = call float @llvm.maximum.f32(float %a, float %b)
   %res = fmul float %max, %min
   ret float %res
 }
 
 define float @test_comm2(float %a, float %b) {
 ; CHECK-LABEL: @test_comm2(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MIN:%.*]] = call float @llvm.minimum.f32(float [[A:%.*]], float [[B:%.*]])
-; CHECK-NEXT:    [[MAX:%.*]] = call float @llvm.maximum.f32(float [[B]], float [[A]])
-; CHECK-NEXT:    [[RES:%.*]] = fmul float [[MIN]], [[MAX]]
+; CHECK-NEXT:    [[RES:%.*]] = fmul float [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    ret float [[RES]]
 ;
 entry:
   %min = call float @llvm.minimum.f32(float %a, float %b)
   %max = call float @llvm.maximum.f32(float %b, float %a)
   %res = fmul float %min, %max
   ret float %res
 }
 
 
 define float @test_comm3(float %a, float %b) {
 ; CHECK-LABEL: @test_comm3(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MIN:%.*]] = call float @llvm.minimum.f32(float [[A:%.*]], float [[B:%.*]])
-; CHECK-NEXT:    [[MAX:%.*]] = call float @llvm.maximum.f32(float [[B]], float [[A]])
-; CHECK-NEXT:    [[RES:%.*]] = fmul float [[MAX]], [[MIN]]
+; CHECK-NEXT:    [[RES:%.*]] = fmul float [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    ret float [[RES]]
 ;
 entry:
   %min = call float @llvm.minimum.f32(float %a, float %b)
   %max = call float @llvm.maximum.f32(float %b, float %a)
   %res = fmul float %max, %min
   ret float %res
 }
 
 define <4 x float> @test_vect(<4 x float> %a, <4 x float> %b) {
 ; CHECK-LABEL: @test_vect(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MIN:%.*]] = call <4 x float> @llvm.minimum.v4f32(<4 x float> [[A:%.*]], <4 x float> [[B:%.*]])
-; CHECK-NEXT:    [[MAX:%.*]] = call <4 x float> @llvm.maximum.v4f32(<4 x float> [[B]], <4 x float> [[A]])
-; CHECK-NEXT:    [[RES:%.*]] = fmul <4 x float> [[MIN]], [[MAX]]
+; CHECK-NEXT:    [[RES:%.*]] = fmul <4 x float> [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    ret <4 x float> [[RES]]
 ;
 entry:
   %min = call <4 x float> @llvm.minimum.v4f32(<4 x float> %a, <4 x float> %b)
   %max = call <4 x float> @llvm.maximum.v4f32(<4 x float> %b, <4 x float> %a)
   %res = fmul <4 x float> %min, %max
   ret <4 x float> %res
 }
 
 define float @test_flags(float %a, float %b) {
 ; CHECK-LABEL: @test_flags(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MIN:%.*]] = call float @llvm.minimum.f32(float [[A:%.*]], float [[B:%.*]])
-; CHECK-NEXT:    [[MAX:%.*]] = call float @llvm.maximum.f32(float [[A]], float [[B]])
-; CHECK-NEXT:    [[RES:%.*]] = fmul fast float [[MIN]], [[MAX]]
+; CHECK-NEXT:    [[RES:%.*]] = fmul fast float [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    ret float [[RES]]
 ;
 entry:
   %min = call float @llvm.minimum.f32(float %a, float %b)
   %max = call float @llvm.maximum.f32(float %a, float %b)
   %res = fmul fast float %min, %max
   ret float %res
 }
 
 define float @test_flags2(float %a, float %b) {
 ; CHECK-LABEL: @test_flags2(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MIN:%.*]] = call float @llvm.minimum.f32(float [[A:%.*]], float [[B:%.*]])
-; CHECK-NEXT:    [[MAX:%.*]] = call float @llvm.maximum.f32(float [[A]], float [[B]])
-; CHECK-NEXT:    [[RES:%.*]] = fmul reassoc ninf nsz arcp contract afn float [[MIN]], [[MAX]]
+; CHECK-NEXT:    [[RES:%.*]] = fmul reassoc nsz arcp contract afn float [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    ret float [[RES]]
 ;
 entry:
   %min = call float @llvm.minimum.f32(float %a, float %b)
   %max = call float @llvm.maximum.f32(float %a, float %b)
   %res = fmul reassoc ninf nsz arcp contract afn float %min, %max
   ret float %res
 }