[InstCombine] reassociate min/max intrinsics with constant operands

[spatel]

Summary

Integer min/max operations are associative:
max (max X, C0), C1 --> max X, (max C0, C1) --> max X, NewC

https://alive2.llvm.org/ce/z/wW5HVM

This would avoid a regression when we canonicalize to min/max intrinsics (see D98152 ).

[lebedev.ri]

For this to work in practice, we also need: https://alive2.llvm.org/ce/z/XC3JqP

[spatel]

In D119754#3320296, @lebedev.ri wrote:

For this to work in practice, we also need: https://alive2.llvm.org/ce/z/XC3JqP

You mean to enable more general reassociation to cascade?

If the reassociate pass handled intrinsics, it would go the other direction (pull the constant higher up in the instruction sequence). I suspect it wouldn't be a small patch to generalize that pass to handle intrinsics instead of just true binop instructions.

I didn't think instcombine inverted that, but it does do that for 'or' instructions at least:
https://github.com/llvm/llvm-project/blob/cccef321096c20825fe8738045c1d91d3b9fd57d/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp#L2938

[lebedev.ri]

In D119754#3320662, @spatel wrote:

In D119754#3320296, @lebedev.ri wrote:

For this to work in practice, we also need: https://alive2.llvm.org/ce/z/XC3JqP

You mean to enable more general reassociation to cascade?

That was the idea, yes.

If the reassociate pass handled intrinsics, it would go the other direction (pull the constant higher up in the instruction sequence). I suspect it wouldn't be a small patch to generalize that pass to handle intrinsics instead of just true binop instructions.

I didn't think instcombine inverted that, but it does do that for 'or' instructions at least:
https://github.com/llvm/llvm-project/blob/cccef321096c20825fe8738045c1d91d3b9fd57d/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp#L2938

[nikic]

LGTM

I think additional reassociation is not really a requirement here, and probably InstCombine is not the right place to reassociate large chains.

[spatel]

In D119754#3322285, @nikic wrote:

LGTM

I think additional reassociation is not really a requirement here, and probably InstCombine is not the right place to reassociate large chains.

I think it's good to make that an incremental improvement. It's not a lot of work to implement a variation of the suggested generalization -- I already drafted it. :)

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

if (Pred == CmpInst::BAD_ICMP_PREDICATE)
     return nullptr;
 
   // max (min X, 42), 41 --> X > 41 ? 42 : 41
   // min (max X, 42), 43 --> X < 43 ? 42 : 43
   Value *Cmp = Builder.CreateICmp(Pred, X, I1);
   return SelectInst::Create(Cmp, ConstantInt::get(II->getType(), *C0), I1);
 }
 
+/// If this min/max has a constant operand and an operand that is a matching
+/// min/max with a constant operand, constant-fold the 2 constant operands.
+static Instruction *reassociateMinMaxWithConstants(IntrinsicInst *II) {
+  Intrinsic::ID MinMaxID = II->getIntrinsicID();
+  auto *LHS = dyn_cast<IntrinsicInst>(II->getArgOperand(0));
+  if (!LHS || LHS->getIntrinsicID() != MinMaxID)
+    return nullptr;
+
+  Constant *C0, *C1;
+  if (!match(LHS->getArgOperand(1), m_ImmConstant(C0)) ||
+      !match(II->getArgOperand(1), m_ImmConstant(C1)))
+    return nullptr;
+
+  // max (max X, C0), C1 --> max X, (max C0, C1) --> max X, NewC
+  ICmpInst::Predicate Pred = MinMaxIntrinsic::getPredicate(MinMaxID);
+  Constant *CondC = ConstantExpr::getICmp(Pred, C0, C1);
+  Constant *NewC = ConstantExpr::getSelect(CondC, C0, C1);
+
+  Module *Mod = II->getModule();
+  Function *MinMax = Intrinsic::getDeclaration(Mod, MinMaxID, II->getType());
+  return CallInst::Create(MinMax, { LHS->getArgOperand(0), NewC });
+}
+
 /// Reduce a sequence of min/max intrinsics with a common operand.
 static Instruction *factorizeMinMaxTree(IntrinsicInst *II) {
   // Match 3 of the same min/max ops. Example: umin(umin(), umin()).
   auto *LHS = dyn_cast<IntrinsicInst>(II->getArgOperand(0));
   auto *RHS = dyn_cast<IntrinsicInst>(II->getArgOperand(1));
   Intrinsic::ID MinMaxID = II->getIntrinsicID();
   if (!LHS || !RHS || LHS->getIntrinsicID() != MinMaxID ||
       RHS->getIntrinsicID() != MinMaxID ||
case Intrinsic::smin: {
     if (Instruction *SAdd = matchSAddSubSat(*II))
       return SAdd;
 
     if (match(I1, m_ImmConstant()))
       if (auto *Sel = dyn_cast<SelectInst>(I0))
         if (Instruction *R = FoldOpIntoSelect(*II, Sel))
           return R;
 
+    if (Instruction *NewMinMax = reassociateMinMaxWithConstants(II))
+      return NewMinMax;
+
     if (Instruction *NewMinMax = factorizeMinMaxTree(II))
        return NewMinMax;
 
     break;
   }
   case Intrinsic::bswap: {
     Value *IIOperand = II->getArgOperand(0);
     Value *X = nullptr;

llvm/test/Transforms/InstCombine/minmax-intrinsics.ll

 ;
   %1 = add nuw nsw i8 50, %x
   %m = call i8 @llvm.smax.i8(i8 %1, i8 -124)
   ret i8 %m
 }
 
 define <3 x i8> @smax_smax_reassoc_constants(<3 x i8> %x) {
 ; CHECK-LABEL: @smax_smax_reassoc_constants(
-; CHECK-NEXT:    [[M1:%.*]] = call <3 x i8> @llvm.smax.v3i8(<3 x i8> [[X:%.*]], <3 x i8> <i8 42, i8 43, i8 44>)
-; CHECK-NEXT:    [[M2:%.*]] = call <3 x i8> @llvm.smax.v3i8(<3 x i8> [[M1]], <3 x i8> <i8 43, i8 -43, i8 0>)
+; CHECK-NEXT:    [[M2:%.*]] = call <3 x i8> @llvm.smax.v3i8(<3 x i8> [[X:%.*]], <3 x i8> <i8 43, i8 43, i8 44>)
 ; CHECK-NEXT:    ret <3 x i8> [[M2]]
 ;
   %m1 = call <3 x i8> @llvm.smax.v3i8(<3 x i8> %x, <3 x i8> <i8 42, i8 43, i8 44>)
   %m2 = call <3 x i8> @llvm.smax.v3i8(<3 x i8> %m1, <3 x i8> <i8 43, i8 -43, i8 0>)
   ret <3 x i8> %m2
 }
 
 define i8 @smin_smin_reassoc_constants(i8 %x) {
 ; CHECK-LABEL: @smin_smin_reassoc_constants(
-; CHECK-NEXT:    [[M1:%.*]] = call i8 @llvm.smin.i8(i8 [[X:%.*]], i8 97)
-; CHECK-NEXT:    [[M2:%.*]] = call i8 @llvm.smin.i8(i8 [[M1]], i8 -3)
+; CHECK-NEXT:    [[M2:%.*]] = call i8 @llvm.smin.i8(i8 [[X:%.*]], i8 -3)
 ; CHECK-NEXT:    ret i8 [[M2]]
 ;
   %m1 = call i8 @llvm.smin.i8(i8 %x, i8 97)
   %m2 = call i8 @llvm.smin.i8(i8 -3, i8 %m1)
   ret i8 %m2
 }
 
 define <3 x i8> @umax_umax_reassoc_constants(<3 x i8> %x) {
 ; CHECK-LABEL: @umax_umax_reassoc_constants(
-; CHECK-NEXT:    [[M1:%.*]] = call <3 x i8> @llvm.umax.v3i8(<3 x i8> [[X:%.*]], <3 x i8> <i8 42, i8 43, i8 44>)
-; CHECK-NEXT:    [[M2:%.*]] = call <3 x i8> @llvm.umax.v3i8(<3 x i8> [[M1]], <3 x i8> <i8 43, i8 -113, i8 poison>)
+; CHECK-NEXT:    [[M2:%.*]] = call <3 x i8> @llvm.umax.v3i8(<3 x i8> [[X:%.*]], <3 x i8> <i8 43, i8 -113, i8 poison>)
 ; CHECK-NEXT:    ret <3 x i8> [[M2]]
 ;
   %m1 = call <3 x i8> @llvm.umax.v3i8(<3 x i8> %x, <3 x i8> <i8 42, i8 43, i8 44>)
   %m2 = call <3 x i8> @llvm.umax.v3i8(<3 x i8> %m1, <3 x i8> <i8 43, i8 143, i8 poison>)
   ret <3 x i8> %m2
 }
 
+; extra use is ok
+
 define i8 @umin_umin_reassoc_constants(i8 %x) {
 ; CHECK-LABEL: @umin_umin_reassoc_constants(
 ; CHECK-NEXT:    [[M1:%.*]] = call i8 @llvm.umin.i8(i8 [[X:%.*]], i8 -116)
 ; CHECK-NEXT:    call void @use(i8 [[M1]])
-; CHECK-NEXT:    [[M2:%.*]] = call i8 @llvm.umin.i8(i8 [[M1]], i8 42)
+; CHECK-NEXT:    [[M2:%.*]] = call i8 @llvm.umin.i8(i8 [[X]], i8 42)
 ; CHECK-NEXT:    ret i8 [[M2]]
 ;
   %m1 = call i8 @llvm.umin.i8(i8 140, i8 %x)
   call void @use(i8 %m1)
   %m2 = call i8 @llvm.umin.i8(i8 %m1, i8 42)
   ret i8 %m2
 }
 
+; negative test - must have matching intrinsics
+
 define i8 @smin_smax_reassoc_constants(i8 %x) {
 ; CHECK-LABEL: @smin_smax_reassoc_constants(
 ; CHECK-NEXT:    [[M1:%.*]] = call i8 @llvm.smin.i8(i8 [[X:%.*]], i8 97)
 ; CHECK-NEXT:    [[M2:%.*]] = call i8 @llvm.smax.i8(i8 [[M1]], i8 -3)
 ; CHECK-NEXT:    ret i8 [[M2]]
 ;
   %m1 = call i8 @llvm.smin.i8(i8 %x, i8 97)
   %m2 = call i8 @llvm.smax.i8(i8 %m1, i8 -3)
   ret i8 %m2
 }