[InstCombine] push constant operand down/outside in sequence of min/max intrinsics

[spatel]

Summary

A generalization like this was suggested in D119754. This is the inverse direction of D119851, and we get all of the folds there plus the one that was missed.

There is precedence for this kind of transform in instcombine with "or" instructions (but strangely only with that one opcode AFAICT).

Similar justification as in the other patch:
The line between instcombine and reassociate for these kinds of folds is blurry. This doesn't appear to have much cost and gives us the expected wins from repeated folds as seen in the last set of test diffs.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

924

Constant or ImmConstant?

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

924

I figured any constant would be safer. I'm not sure what happens if we put constant expressions in these patterns, so just give up?

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

924

This fold only hoists an immconstant, so there indeed is a chance of looping iff x or y is a immconstant,
but i don't see why non-imm constant would be dangerous.

[spatel]

Patch updated:
Allow constant expression transform (test added).

[lebedev.ri]

LGTM, thank you!

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

static Instruction *reassociateMinMaxWithConstants(IntrinsicInst *II) {
   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});
 }
 
+/// If this min/max has a matching min/max operand with a constant, try to push
+/// the constant operand into this instruction. This can enable more folds.
+static Instruction *
+reassociateMinMaxWithConstantInOperand(IntrinsicInst *II,
+                                       InstCombiner::BuilderTy &Builder) {
+  // Match and capture a min/max operand candidate.
+  Value *X, *Y;
+  Constant *C;
+  Instruction *Inner;
+  if (!match(II, m_c_MaxOrMin(m_OneUse(m_CombineAnd(
+                                  m_Instruction(Inner),
+                                  m_MaxOrMin(m_Value(X), m_ImmConstant(C)))),
+                              m_Value(Y))))
+    return nullptr;
+
+  // The inner op must match. Check for constants to avoid infinite loops.
+  Intrinsic::ID MinMaxID = II->getIntrinsicID();
+  auto *InnerMM = dyn_cast<IntrinsicInst>(Inner);
+  if (!InnerMM || InnerMM->getIntrinsicID() != MinMaxID ||
+      match(X, m_ImmConstant()) || match(Y, m_ImmConstant()))
+    return nullptr;
+
+  // max (max X, C), Y --> max (max X, Y), C
+  Function *MinMax =
+      Intrinsic::getDeclaration(II->getModule(), MinMaxID, II->getType());
+  Value *NewInner = Builder.CreateBinaryIntrinsic(MinMaxID, X, Y);
+  NewInner->takeName(Inner);
+  return CallInst::Create(MinMax, {NewInner, C});
+}
+
 /// 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 (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 *R = reassociateMinMaxWithConstantInOperand(II, Builder))
+      return R;
+
     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

;
   %m1 = call i8 @llvm.umin.i8(i8 %x, i8 %y)
   call void @use(i8 %m1)
   %m2 = call i8 @llvm.umin.i8(i8 %m1, i8 42)
   ret i8 %m2
 }
 
 define i8 @smax_smax_reassoc_constant_sink(i8 %x, i8 %y) {
 ; CHECK-LABEL: @smax_smax_reassoc_constant_sink(
-; CHECK-NEXT:    [[M1:%.*]] = call i8 @llvm.smax.i8(i8 [[X:%.*]], i8 42)
-; CHECK-NEXT:    [[M2:%.*]] = call i8 @llvm.smax.i8(i8 [[M1]], i8 [[Y:%.*]])
+; CHECK-NEXT:    [[M1:%.*]] = call i8 @llvm.smax.i8(i8 [[X:%.*]], i8 [[Y:%.*]])
+; CHECK-NEXT:    [[M2:%.*]] = call i8 @llvm.smax.i8(i8 [[M1]], i8 42)
 ; CHECK-NEXT:    ret i8 [[M2]]
 ;
   %m1 = call i8 @llvm.smax.i8(i8 %x, i8 42)
   %m2 = call i8 @llvm.smax.i8(i8 %m1, i8 %y)
   ret i8 %m2
 }
 
 define <3 x i8> @smin_smin_reassoc_constant_sink(<3 x i8> %x, <3 x i8> %y) {
 ; CHECK-LABEL: @smin_smin_reassoc_constant_sink(
-; CHECK-NEXT:    [[M1:%.*]] = call <3 x i8> @llvm.smin.v3i8(<3 x i8> [[X:%.*]], <3 x i8> <i8 43, i8 -43, i8 0>)
-; CHECK-NEXT:    [[M2:%.*]] = call <3 x i8> @llvm.smin.v3i8(<3 x i8> [[M1]], <3 x i8> [[Y:%.*]])
+; CHECK-NEXT:    [[M1:%.*]] = call <3 x i8> @llvm.smin.v3i8(<3 x i8> [[X:%.*]], <3 x i8> [[Y:%.*]])
+; CHECK-NEXT:    [[M2:%.*]] = call <3 x i8> @llvm.smin.v3i8(<3 x i8> [[M1]], <3 x i8> <i8 43, i8 -43, i8 0>)
 ; CHECK-NEXT:    ret <3 x i8> [[M2]]
 ;
   %m1 = call <3 x i8> @llvm.smin.v3i8(<3 x i8> %x, <3 x i8> <i8 43, i8 -43, i8 0>)
   %m2 = call <3 x i8> @llvm.smin.v3i8(<3 x i8> %m1, <3 x i8> %y)
   ret <3 x i8> %m2
 }
 
 define i8 @umax_umax_reassoc_constant_sink(i8 %x, i8 %y) {
 ; CHECK-LABEL: @umax_umax_reassoc_constant_sink(
-; CHECK-NEXT:    [[M1:%.*]] = call i8 @llvm.umax.i8(i8 [[X:%.*]], i8 42)
-; CHECK-NEXT:    [[M2:%.*]] = call i8 @llvm.umax.i8(i8 [[M1]], i8 [[Y:%.*]])
+; CHECK-NEXT:    [[M1:%.*]] = call i8 @llvm.umax.i8(i8 [[X:%.*]], i8 [[Y:%.*]])
+; CHECK-NEXT:    [[M2:%.*]] = call i8 @llvm.umax.i8(i8 [[M1]], i8 42)
 ; CHECK-NEXT:    ret i8 [[M2]]
 ;
   %m1 = call i8 @llvm.umax.i8(i8 %x, i8 42)
   %m2 = call i8 @llvm.umax.i8(i8 %m1, i8 %y)
   ret i8 %m2
 }
 
 define <3 x i8> @umin_umin_reassoc_constant_sink(<3 x i8> %x, <3 x i8> %y) {
 ; CHECK-LABEL: @umin_umin_reassoc_constant_sink(
-; CHECK-NEXT:    [[M1:%.*]] = call <3 x i8> @llvm.umin.v3i8(<3 x i8> [[X:%.*]], <3 x i8> <i8 43, i8 -43, i8 0>)
-; CHECK-NEXT:    [[M2:%.*]] = call <3 x i8> @llvm.umin.v3i8(<3 x i8> [[M1]], <3 x i8> [[Y:%.*]])
+; CHECK-NEXT:    [[M1:%.*]] = call <3 x i8> @llvm.umin.v3i8(<3 x i8> [[X:%.*]], <3 x i8> [[Y:%.*]])
+; CHECK-NEXT:    [[M2:%.*]] = call <3 x i8> @llvm.umin.v3i8(<3 x i8> [[M1]], <3 x i8> <i8 43, i8 -43, i8 0>)
 ; CHECK-NEXT:    ret <3 x i8> [[M2]]
 ;
   %m1 = call <3 x i8> @llvm.umin.v3i8(<3 x i8> %x, <3 x i8> <i8 43, i8 -43, i8 0>)
   %m2 = call <3 x i8> @llvm.umin.v3i8(<3 x i8> %m1, <3 x i8> %y)
   ret <3 x i8> %m2
 }
 
 define i8 @umin_umin_reassoc_constant_sink_use(i8 %x, i8 %y) {
 ; CHECK-LABEL: @umin_umin_reassoc_constant_sink_use(
 ; CHECK-NEXT:    [[M1:%.*]] = call i8 @llvm.umin.i8(i8 [[X:%.*]], i8 42)
 ; CHECK-NEXT:    call void @use(i8 [[M1]])
 ; CHECK-NEXT:    [[M2:%.*]] = call i8 @llvm.umin.i8(i8 [[M1]], i8 [[Y:%.*]])
 ; CHECK-NEXT:    ret i8 [[M2]]
 ;
   %m1 = call i8 @llvm.umin.i8(i8 %x, i8 42)
   call void @use(i8 %m1)
   %m2 = call i8 @llvm.umin.i8(i8 %m1, i8 %y)
   ret i8 %m2
 }
 
 define i8 @smax_smax_smax_reassoc_constants(i8 %x, i8 %y) {
 ; CHECK-LABEL: @smax_smax_smax_reassoc_constants(
-; CHECK-NEXT:    [[M1:%.*]] = call i8 @llvm.smax.i8(i8 [[X:%.*]], i8 42)
-; CHECK-NEXT:    [[M2:%.*]] = call i8 @llvm.smax.i8(i8 [[Y:%.*]], i8 [[M1]])
-; CHECK-NEXT:    [[M3:%.*]] = call i8 @llvm.smax.i8(i8 [[M2]], i8 126)
+; CHECK-NEXT:    [[M1:%.*]] = call i8 @llvm.smax.i8(i8 [[X:%.*]], i8 [[Y:%.*]])
+; CHECK-NEXT:    [[M3:%.*]] = call i8 @llvm.smax.i8(i8 [[M1]], i8 126)
 ; CHECK-NEXT:    ret i8 [[M3]]
 ;
   %m1 = call i8 @llvm.smax.i8(i8 %x, i8 42)
   %m2 = call i8 @llvm.smax.i8(i8 %y, i8 %m1)
   %m3 = call i8 @llvm.smax.i8(i8 %m2, i8 126)
   ret i8 %m3
 }
 
 define i8 @smax_smax_smax_reassoc_constants_swap(i8 %x, i8 %y) {
 ; CHECK-LABEL: @smax_smax_smax_reassoc_constants_swap(
-; CHECK-NEXT:    [[M1:%.*]] = call i8 @llvm.smax.i8(i8 [[X:%.*]], i8 42)
-; CHECK-NEXT:    [[M2:%.*]] = call i8 @llvm.smax.i8(i8 [[M1]], i8 [[Y:%.*]])
-; CHECK-NEXT:    [[M3:%.*]] = call i8 @llvm.smax.i8(i8 [[M2]], i8 126)
+; CHECK-NEXT:    [[M1:%.*]] = call i8 @llvm.smax.i8(i8 [[X:%.*]], i8 [[Y:%.*]])
+; CHECK-NEXT:    [[M3:%.*]] = call i8 @llvm.smax.i8(i8 [[M1]], i8 126)
 ; CHECK-NEXT:    ret i8 [[M3]]
 ;
   %m1 = call i8 @llvm.smax.i8(i8 %x, i8 42)
   %m2 = call i8 @llvm.smax.i8(i8 %m1, i8 %y)
   %m3 = call i8 @llvm.smax.i8(i8 %m2, i8 126)
   ret i8 %m3
 }
 
 define i8 @smin_smin_smin_reassoc_constants(i8 %x, i8 %y) {
 ; CHECK-LABEL: @smin_smin_smin_reassoc_constants(
-; CHECK-NEXT:    [[M1:%.*]] = call i8 @llvm.smin.i8(i8 [[X:%.*]], i8 42)
-; CHECK-NEXT:    [[M2:%.*]] = call i8 @llvm.smin.i8(i8 [[Y:%.*]], i8 [[M1]])
-; CHECK-NEXT:    [[M3:%.*]] = call i8 @llvm.smin.i8(i8 [[M2]], i8 126)
-; CHECK-NEXT:    ret i8 [[M3]]
+; CHECK-NEXT:    [[M1:%.*]] = call i8 @llvm.smin.i8(i8 [[X:%.*]], i8 [[Y:%.*]])
+; CHECK-NEXT:    [[M2:%.*]] = call i8 @llvm.smin.i8(i8 [[M1]], i8 42)
+; CHECK-NEXT:    ret i8 [[M2]]
 ;
   %m1 = call i8 @llvm.smin.i8(i8 %x, i8 42)
   %m2 = call i8 @llvm.smin.i8(i8 %y, i8 %m1)
   %m3 = call i8 @llvm.smin.i8(i8 %m2, i8 126)
   ret i8 %m3
 }
 
 define i8 @umax_umax_reassoc_constantexpr_sink(i8 %x, i8 %y) {
 ; CHECK-LABEL: @umax_umax_reassoc_constantexpr_sink(
-; CHECK-NEXT:    [[M1:%.*]] = call i8 @llvm.umax.i8(i8 [[X:%.*]], i8 42)
-; CHECK-NEXT:    [[M2:%.*]] = call i8 @llvm.umax.i8(i8 [[M1]], i8 ptrtoint (i8 (i8, i8)* @umax_umax_reassoc_constantexpr_sink to i8))
+; CHECK-NEXT:    [[M1:%.*]] = call i8 @llvm.umax.i8(i8 [[X:%.*]], i8 ptrtoint (i8 (i8, i8)* @umax_umax_reassoc_constantexpr_sink to i8))
+; CHECK-NEXT:    [[M2:%.*]] = call i8 @llvm.umax.i8(i8 [[M1]], i8 42)
 ; CHECK-NEXT:    ret i8 [[M2]]
 ;
   %m1 = call i8 @llvm.umax.i8(i8 %x, i8 42)
   %m2 = call i8 @llvm.umax.i8(i8 %m1, i8 ptrtoint (i8 (i8, i8)* @umax_umax_reassoc_constantexpr_sink to i8))
   ret i8 %m2
 }