[InstCombine] Add support for max(a,b) + min(a,b) => a + b.

[skatkov]

Summary

The same optimization for

max(a,b) * min(a,b) => a * b

is added.

Correctness check:
uadd: https://alive2.llvm.org/ce/z/2rXDek
sadd: https://alive2.llvm.org/ce/z/zNu_er
uadd + nuw/nsw: https://alive2.llvm.org/ce/z/EaiNjB
sadd + nuw/nsw: https://alive2.llvm.org/ce/z/w_2Nrs

umul: https://alive2.llvm.org/ce/z/dgXRLr
smul: https://alive2.llvm.org/ce/z/hBjGzz
umul + nuw/nsw: https://alive2.llvm.org/ce/z/EaiNjB
smul + nuw/nsw: https://alive2.llvm.org/ce/z/87MNeS

[skatkov]

remove redundant m_c to safe a compile time a bit.

[goldstein.w.n]

Please add alive2 links for the proofs for {mul, add} x {smin/smax, umin/umax}.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1604

Can you move this to before nuw/nsw flags are set (L1557).

1610

I think you can also preserve nuw and nsw flags.
https://alive2.llvm.org/ce/z/EaiNjB

likewise in the mul case:
https://alive2.llvm.org/ce/z/sV3tnG

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

494

Can you move this before I is potentially modified and Changed is set (before L474).

llvm/test/Transforms/InstCombine/add-min-max.ll

1

Can you split the tests into a seperate patch so we can see the diff this patch results in?

llvm/test/Transforms/InstCombine/mul-min-max.ll

9

This (along with other tests) are misnamed. ('add' -> 'mul')

[skatkov]

Thank you very much for review.

[skatkov]

ping

[goldstein.w.n]

LGTM.

I'm not a maintainer so give it a day or so before pushing so others have a chance to look it over if they want.

[skatkov]

In D147296#4244914, @goldstein.w.n wrote:

LGTM.

I'm not a maintainer so give it a day or so before pushing so others have a chance to look it over if they want.

Sure, Thank a lot for review.

[skatkov]

NFC update - use of BinaryOperator::CreateWithCopiedFlags utility instead of manually copying flags.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (match(LHS, m_AShr(m_Value(A), m_SpecificIntAllowUndef(BitWidth - 1))) &&
     Value *NotZero = Builder.CreateIsNotNull(A, "isnotnull");
     Value *Zext = Builder.CreateZExt(NotZero, Ty, "isnotnull.zext");
     return BinaryOperator::CreateOr(LHS, Zext);
   }
 
   if (Instruction *Ashr = foldAddToAshr(I))
     return Ashr;
 
+  // min(A, B) + max(A, B) => A + B.
+  if (match(&I,
+            match_combine_or(m_c_Add(m_SMax(m_Value(A), m_Value(B)),
+                                     m_c_SMin(m_Deferred(A), m_Deferred(B))),
+                             m_c_Add(m_UMax(m_Value(A), m_Value(B)),
+                                     m_c_UMin(m_Deferred(A), m_Deferred(B))))))
+    return BinaryOperator::CreateWithCopiedFlags(Instruction::Add, A, B, &I);
+
   // TODO(jingyue): Consider willNotOverflowSignedAdd and
   // willNotOverflowUnsignedAdd to reduce the number of invocations of
   // computeKnownBits.
   bool Changed = false;
   if (!I.hasNoSignedWrap() && willNotOverflowSignedAdd(LHS, RHS, I)) {
     Changed = true;
     I.setHasNoSignedWrap(true);
   }
Instruction *InstCombinerImpl::visitAdd(BinaryOperator &I) {
   // ctpop(A) + ctpop(B) => ctpop(A | B) if A and B have no bits set in common.
   if (match(LHS, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(A)))) &&
       match(RHS, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(B)))) &&
       haveNoCommonBitsSet(A, B, DL, &AC, &I, &DT))
     return replaceInstUsesWith(
         I, Builder.CreateIntrinsic(Intrinsic::ctpop, {I.getType()},
                                    {Builder.CreateOr(A, B)}));
 
   return Changed ? &I : nullptr;
 }
 
 /// Eliminate an op from a linear interpolation (lerp) pattern.
 static Instruction *factorizeLerp(BinaryOperator &I,
                                   InstCombiner::BuilderTy &Builder) {
   Value *X, *Y, *Z;
   if (!match(&I, m_c_FAdd(m_OneUse(m_c_FMul(m_Value(Y),
                                             m_OneUse(m_FSub(m_FPOne(),
                                                             m_Value(Z))))),
                           m_OneUse(m_c_FMul(m_Value(X), m_Deferred(Z))))))
     return nullptr;
 
   // (Y * (1.0 - Z)) + (X * Z) --> Y + Z * (X - Y) [8 commuted variants]
   Value *XY = Builder.CreateFSubFMF(X, Y, &I);

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

Value *Abs = Builder.CreateBinaryIntrinsic(
         Intrinsic::abs, X, ConstantInt::getBool(I.getContext(), HasNSW));
     Abs->takeName(&I);
     return replaceInstUsesWith(I, Abs);
   }
 
   if (Instruction *Ext = narrowMathIfNoOverflow(I))
     return Ext;
 
+  // min(X, Y) * max(X, Y) => X * Y.
+  if (match(&I,
+            match_combine_or(m_c_Mul(m_SMax(m_Value(X), m_Value(Y)),
+                                     m_c_SMin(m_Deferred(X), m_Deferred(Y))),
+                             m_c_Mul(m_UMax(m_Value(X), m_Value(Y)),
+                                     m_c_UMin(m_Deferred(X), m_Deferred(Y))))))
+    return BinaryOperator::CreateWithCopiedFlags(Instruction::Mul, X, Y, &I);
+
   bool Changed = false;
   if (!HasNSW && willNotOverflowSignedMul(Op0, Op1, I)) {
     Changed = true;
     I.setHasNoSignedWrap(true);
   }
 
   if (!HasNUW && willNotOverflowUnsignedMul(Op0, Op1, I)) {
     Changed = true;
     I.setHasNoUnsignedWrap(true);
   }
 
   return Changed ? &I : nullptr;
 }
 
 Instruction *InstCombinerImpl::foldFPSignBitOps(BinaryOperator &I) {
   BinaryOperator::BinaryOps Opcode = I.getOpcode();
   assert((Opcode == Instruction::FMul || Opcode == Instruction::FDiv) &&
          "Expected fmul or fdiv");
 
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
   Value *X, *Y;

llvm/test/Transforms/InstCombine/add-min-max.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 declare i32 @llvm.smax.i32(i32 %a, i32 %b)
 declare i32 @llvm.smin.i32(i32 %a, i32 %b)
 declare i32 @llvm.umax.i32(i32 %a, i32 %b)
 declare i32 @llvm.umin.i32(i32 %a, i32 %b)
 
 define i32 @uadd_min_max(i32 %a, i32 %b) {
 ; CHECK-LABEL: @uadd_min_max(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MAX:%.*]] = call i32 @llvm.umax.i32(i32 [[A:%.*]], i32 [[B:%.*]])
-; CHECK-NEXT:    [[MIN:%.*]] = call i32 @llvm.umin.i32(i32 [[A]], i32 [[B]])
-; CHECK-NEXT:    [[RES:%.*]] = add i32 [[MIN]], [[MAX]]
+; CHECK-NEXT:    [[RES:%.*]] = add i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
 entry:
   %max = call i32 @llvm.umax.i32(i32 %a, i32 %b)
   %min = call i32 @llvm.umin.i32(i32 %a, i32 %b)
   %res = add i32 %min, %max
   ret i32 %res
 }
 
 define i32 @uadd_min_max_comm(i32 %a, i32 %b) {
 ; CHECK-LABEL: @uadd_min_max_comm(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MAX:%.*]] = call i32 @llvm.umax.i32(i32 [[B:%.*]], i32 [[A:%.*]])
-; CHECK-NEXT:    [[MIN:%.*]] = call i32 @llvm.umin.i32(i32 [[A]], i32 [[B]])
-; CHECK-NEXT:    [[RES:%.*]] = add i32 [[MIN]], [[MAX]]
+; CHECK-NEXT:    [[RES:%.*]] = add i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
 entry:
   %max = call i32 @llvm.umax.i32(i32 %b, i32 %a)
   %min = call i32 @llvm.umin.i32(i32 %a, i32 %b)
   %res = add i32 %min, %max
   ret i32 %res
 }
 
 define i32 @uadd_min_max_nuw_nsw(i32 %a, i32 %b) {
 ; CHECK-LABEL: @uadd_min_max_nuw_nsw(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MAX:%.*]] = call i32 @llvm.umax.i32(i32 [[A:%.*]], i32 [[B:%.*]])
-; CHECK-NEXT:    [[MIN:%.*]] = call i32 @llvm.umin.i32(i32 [[A]], i32 [[B]])
-; CHECK-NEXT:    [[RES:%.*]] = add nuw nsw i32 [[MIN]], [[MAX]]
+; CHECK-NEXT:    [[RES:%.*]] = add nuw nsw i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
 entry:
   %max = call i32 @llvm.umax.i32(i32 %a, i32 %b)
   %min = call i32 @llvm.umin.i32(i32 %a, i32 %b)
   %res = add nuw nsw i32 %min, %max
   ret i32 %res
 }
 
 define i32 @sadd_min_max(i32 %a, i32 %b) {
 ; CHECK-LABEL: @sadd_min_max(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MAX:%.*]] = call i32 @llvm.smax.i32(i32 [[A:%.*]], i32 [[B:%.*]])
-; CHECK-NEXT:    [[MIN:%.*]] = call i32 @llvm.smin.i32(i32 [[A]], i32 [[B]])
-; CHECK-NEXT:    [[RES:%.*]] = add i32 [[MIN]], [[MAX]]
+; CHECK-NEXT:    [[RES:%.*]] = add i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
 entry:
   %max = call i32 @llvm.smax.i32(i32 %a, i32 %b)
   %min = call i32 @llvm.smin.i32(i32 %a, i32 %b)
   %res = add i32 %min, %max
   ret i32 %res
 }
 
 define i32 @sadd_min_max_comm(i32 %a, i32 %b) {
 ; CHECK-LABEL: @sadd_min_max_comm(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MAX:%.*]] = call i32 @llvm.smax.i32(i32 [[B:%.*]], i32 [[A:%.*]])
-; CHECK-NEXT:    [[MIN:%.*]] = call i32 @llvm.smin.i32(i32 [[A]], i32 [[B]])
-; CHECK-NEXT:    [[RES:%.*]] = add i32 [[MIN]], [[MAX]]
+; CHECK-NEXT:    [[RES:%.*]] = add i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
 entry:
   %max = call i32 @llvm.smax.i32(i32 %b, i32 %a)
   %min = call i32 @llvm.smin.i32(i32 %a, i32 %b)
   %res = add i32 %min, %max
   ret i32 %res
 }
 
 define i32 @sadd_min_max_nuw_nsw(i32 %a, i32 %b) {
 ; CHECK-LABEL: @sadd_min_max_nuw_nsw(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MAX:%.*]] = call i32 @llvm.smax.i32(i32 [[A:%.*]], i32 [[B:%.*]])
-; CHECK-NEXT:    [[MIN:%.*]] = call i32 @llvm.smin.i32(i32 [[A]], i32 [[B]])
-; CHECK-NEXT:    [[RES:%.*]] = add nuw nsw i32 [[MIN]], [[MAX]]
+; CHECK-NEXT:    [[RES:%.*]] = add nuw nsw i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
 entry:
   %max = call i32 @llvm.smax.i32(i32 %a, i32 %b)
   %min = call i32 @llvm.smin.i32(i32 %a, i32 %b)
   %res = add nuw nsw i32 %min, %max
   ret i32 %res
 }

llvm/test/Transforms/InstCombine/mul-min-max.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 declare i32 @llvm.smax.i32(i32 %a, i32 %b)
 declare i32 @llvm.smin.i32(i32 %a, i32 %b)
 declare i32 @llvm.umax.i32(i32 %a, i32 %b)
 declare i32 @llvm.umin.i32(i32 %a, i32 %b)
 
 define i32 @umul_min_max(i32 %a, i32 %b) {
 ; CHECK-LABEL: @umul_min_max(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MAX:%.*]] = call i32 @llvm.umax.i32(i32 [[A:%.*]], i32 [[B:%.*]])
-; CHECK-NEXT:    [[MIN:%.*]] = call i32 @llvm.umin.i32(i32 [[A]], i32 [[B]])
-; CHECK-NEXT:    [[RES:%.*]] = mul i32 [[MIN]], [[MAX]]
+; CHECK-NEXT:    [[RES:%.*]] = mul i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
 entry:
   %max = call i32 @llvm.umax.i32(i32 %a, i32 %b)
   %min = call i32 @llvm.umin.i32(i32 %a, i32 %b)
   %res = mul i32 %min, %max
   ret i32 %res
 }
 
 define i32 @umul_min_max_comm(i32 %a, i32 %b) {
 ; CHECK-LABEL: @umul_min_max_comm(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MAX:%.*]] = call i32 @llvm.umax.i32(i32 [[B:%.*]], i32 [[A:%.*]])
-; CHECK-NEXT:    [[MIN:%.*]] = call i32 @llvm.umin.i32(i32 [[A]], i32 [[B]])
-; CHECK-NEXT:    [[RES:%.*]] = mul i32 [[MIN]], [[MAX]]
+; CHECK-NEXT:    [[RES:%.*]] = mul i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
 entry:
   %max = call i32 @llvm.umax.i32(i32 %b, i32 %a)
   %min = call i32 @llvm.umin.i32(i32 %a, i32 %b)
   %res = mul i32 %min, %max
   ret i32 %res
 }
 
 define i32 @umul_min_max_nuw_nsw(i32 %a, i32 %b) {
 ; CHECK-LABEL: @umul_min_max_nuw_nsw(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MAX:%.*]] = call i32 @llvm.umax.i32(i32 [[A:%.*]], i32 [[B:%.*]])
-; CHECK-NEXT:    [[MIN:%.*]] = call i32 @llvm.umin.i32(i32 [[A]], i32 [[B]])
-; CHECK-NEXT:    [[RES:%.*]] = mul nuw nsw i32 [[MIN]], [[MAX]]
+; CHECK-NEXT:    [[RES:%.*]] = mul nuw nsw i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
 entry:
   %max = call i32 @llvm.umax.i32(i32 %a, i32 %b)
   %min = call i32 @llvm.umin.i32(i32 %a, i32 %b)
   %res = mul nuw nsw i32 %min, %max
   ret i32 %res
 }
 
 define i32 @smul_min_max(i32 %a, i32 %b) {
 ; CHECK-LABEL: @smul_min_max(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MAX:%.*]] = call i32 @llvm.smax.i32(i32 [[A:%.*]], i32 [[B:%.*]])
-; CHECK-NEXT:    [[MIN:%.*]] = call i32 @llvm.smin.i32(i32 [[A]], i32 [[B]])
-; CHECK-NEXT:    [[RES:%.*]] = mul i32 [[MIN]], [[MAX]]
+; CHECK-NEXT:    [[RES:%.*]] = mul i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
 entry:
   %max = call i32 @llvm.smax.i32(i32 %a, i32 %b)
   %min = call i32 @llvm.smin.i32(i32 %a, i32 %b)
   %res = mul i32 %min, %max
   ret i32 %res
 }
 
 define i32 @smul_min_max_comm(i32 %a, i32 %b) {
 ; CHECK-LABEL: @smul_min_max_comm(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MAX:%.*]] = call i32 @llvm.smax.i32(i32 [[B:%.*]], i32 [[A:%.*]])
-; CHECK-NEXT:    [[MIN:%.*]] = call i32 @llvm.smin.i32(i32 [[A]], i32 [[B]])
-; CHECK-NEXT:    [[RES:%.*]] = mul i32 [[MIN]], [[MAX]]
+; CHECK-NEXT:    [[RES:%.*]] = mul i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
 entry:
   %max = call i32 @llvm.smax.i32(i32 %b, i32 %a)
   %min = call i32 @llvm.smin.i32(i32 %a, i32 %b)
   %res = mul i32 %min, %max
   ret i32 %res
 }
 
 define i32 @smul_min_max_nuw_nsw(i32 %a, i32 %b) {
 ; CHECK-LABEL: @smul_min_max_nuw_nsw(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MAX:%.*]] = call i32 @llvm.smax.i32(i32 [[A:%.*]], i32 [[B:%.*]])
-; CHECK-NEXT:    [[MIN:%.*]] = call i32 @llvm.smin.i32(i32 [[A]], i32 [[B]])
-; CHECK-NEXT:    [[RES:%.*]] = mul nuw nsw i32 [[MIN]], [[MAX]]
+; CHECK-NEXT:    [[RES:%.*]] = mul nuw nsw i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
 entry:
   %max = call i32 @llvm.smax.i32(i32 %a, i32 %b)
   %min = call i32 @llvm.smin.i32(i32 %a, i32 %b)
   %res = mul nuw nsw i32 %min, %max
   ret i32 %res
 }