[InstCombine] push constant operand up/inside in sequence of min/max intrinsics

[spatel]

Summary

A generalization like this was suggested in D119754, but I'm proposing to move the constant up rather than down.

If these operations ever graduate to become real instructions rather than intrinsics, then this would not conflict with the reassociate pass because it has the same transform in its set of tricks for binop instructions.

The line between the passes on these kinds of folds is blurry, but this doesn't appear to have much cost and gives us the expected wins from repeated folds as seen in the last pair of test diffs.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

899

I'd move the first check into the first if, because it doesn't match the comment on this one.

906

C1 -> C now

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

2268

What would happen if you swapped the operands on this smax? Unless I'm missing something, in the case of non-constant arguments, we're going to make a pretty arbitrary reassociation choice, which will depend on non-canonicalized argument order to produce a good result.

[spatel]

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

2268

Nice catch! I'll add a test.

We don't do the more elaborate complexity-based canonicalization for intrinsics that we do for commutative instructions, so the operand order on the middle max is not fixed.

We could pick another matching intrinsic if it exists, but there's no complete solution within the scope of instcombine AFAIK.

[lebedev.ri]

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

2268

That is one of the reasons why i'm suggesting sinking :)

[spatel]

Patch updated:

1. Improved order of matching.
2. Fixed code comment.
3. Added TODO comment/test for possible enhancement.

[spatel]

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

2268

Yes, that does seem better. I don't see any real downside other than inverting the theoretical transform from -reassociate.

Maybe we can justify that because we increase the chance of finding the optimal sequence by trying both directions. :)

[spatel]

Patch to go in the other direction:
D119955

[spatel]

Abandoning - pushed the transform in the other direction with 58df2da0540c

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

static Instruction *foldClampRangeOfTwo(IntrinsicInst *II,
 
   // 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) {
+/// min/max, try to push the constant operand into the inner (first) min/max.
+/// This may enable simplifications.
+static Instruction *
+reassociateMinMaxWithConstant(IntrinsicInst *II,
+                              InstCombiner::BuilderTy &Builder) {
   Intrinsic::ID MinMaxID = II->getIntrinsicID();
   auto *LHS = dyn_cast<IntrinsicInst>(II->getArgOperand(0));
-  if (!LHS || LHS->getIntrinsicID() != MinMaxID)
+  Constant *C;
+  if (!LHS || LHS->getIntrinsicID() != MinMaxID ||
+      !match(II->getArgOperand(1), m_ImmConstant(C)))
     return nullptr;
 
-  Constant *C0, *C1;
-  if (!match(LHS->getArgOperand(1), m_ImmConstant(C0)) ||
-      !match(II->getArgOperand(1), m_ImmConstant(C1)))
+  // Avoid infinite loop if the inner min/max is not in canonical form yet.
+  Value *X = LHS->getArgOperand(0);
+  Value *Y = LHS->getArgOperand(1);
+  if (match(X, m_Constant()))
     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);
+  // If the inner min/max has a constant operand, it will constant-fold with
+  // the outer constant operand, so an extra use is fine in that case.
+  if (!LHS->hasOneUse() && !match(Y, m_ImmConstant()))
+    return nullptr;
 
+  // max (max X, Y), C --> max (max Y, C), X
+  // This may allow the inner op to be simplified.
+  // TODO: This always chooses X (operand 0 of the inner instruction) as the
+  //       the operand to swap, but we may want to choose Y instead to enable
+  //       more folds (in the case where Y is not a constant).
+  Value *NewInner = Builder.CreateBinaryIntrinsic(MinMaxID, Y, C);
+  NewInner->takeName(LHS);
   Module *Mod = II->getModule();
   Function *MinMax = Intrinsic::getDeclaration(Mod, MinMaxID, II->getType());
-  return CallInst::Create(MinMax, {LHS->getArgOperand(0), NewC});
+  return CallInst::Create(MinMax, {NewInner, X});
 }
 
 /// 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();
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))
+    if (Instruction *NewMinMax = reassociateMinMaxWithConstant(II, Builder))
       return NewMinMax;
 
     if (Instruction *NewMinMax = factorizeMinMaxTree(II))
        return NewMinMax;
 
     break;
   }
   case Intrinsic::bswap: {

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

;
   %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:    [[TMP1:%.*]] = call i8 @llvm.umin.i8(i8 [[X:%.*]], i8 -116)
+; CHECK-NEXT:    call void @use(i8 [[TMP1]])
 ; 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
 }
 
 define i8 @smax_smax_reassoc_constant(i8 %x, i8 %y) {
 ; CHECK-LABEL: @smax_smax_reassoc_constant(
-; 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:    [[M1:%.*]] = call i8 @llvm.smax.i8(i8 [[Y:%.*]], i8 42)
+; CHECK-NEXT:    [[M2:%.*]] = call i8 @llvm.smax.i8(i8 [[M1]], i8 [[X:%.*]])
 ; CHECK-NEXT:    ret i8 [[M2]]
 ;
   %m1 = call i8 @llvm.smax.i8(i8 %x, i8 %y)
   %m2 = call i8 @llvm.smax.i8(i8 %m1, i8 42)
   ret i8 %m2
 }
 
 define <3 x i8> @smin_smin_reassoc_constant(<3 x i8> %x, <3 x i8> %y) {
 ; CHECK-LABEL: @smin_smin_reassoc_constant(
-; 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:    [[M1:%.*]] = call <3 x i8> @llvm.smin.v3i8(<3 x i8> [[Y:%.*]], <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> [[X:%.*]])
 ; CHECK-NEXT:    ret <3 x i8> [[M2]]
 ;
   %m1 = call <3 x i8> @llvm.smin.v3i8(<3 x i8> %x, <3 x i8> %y)
   %m2 = call <3 x i8> @llvm.smin.v3i8(<3 x i8> %m1, <3 x i8> <i8 43, i8 -43, i8 0>)
   ret <3 x i8> %m2
 }
 
 define i8 @umax_umax_reassoc_constant(i8 %x, i8 %y) {
 ; CHECK-LABEL: @umax_umax_reassoc_constant(
-; 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:    [[M1:%.*]] = call i8 @llvm.umax.i8(i8 [[Y:%.*]], i8 42)
+; CHECK-NEXT:    [[M2:%.*]] = call i8 @llvm.umax.i8(i8 [[M1]], i8 [[X:%.*]])
 ; CHECK-NEXT:    ret i8 [[M2]]
 ;
   %m1 = call i8 @llvm.umax.i8(i8 %x, i8 %y)
   %m2 = call i8 @llvm.umax.i8(i8 %m1, i8 42)
   ret i8 %m2
 }
 
 define <3 x i8> @umin_smin_reassoc_constant(<3 x i8> %x, <3 x i8> %y) {
 ; CHECK-LABEL: @umin_smin_reassoc_constant(
-; 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:    [[M1:%.*]] = call <3 x i8> @llvm.umin.v3i8(<3 x i8> [[Y:%.*]], <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> [[X:%.*]])
 ; CHECK-NEXT:    ret <3 x i8> [[M2]]
 ;
   %m1 = call <3 x i8> @llvm.umin.v3i8(<3 x i8> %x, <3 x i8> %y)
   %m2 = call <3 x i8> @llvm.umin.v3i8(<3 x i8> %m1, <3 x i8> <i8 43, i8 -43, i8 0>)
   ret <3 x i8> %m2
 }
 
 define i8 @umin_umin_reassoc_constant_use(i8 %x, i8 %y) {
 ; CHECK-LABEL: @umin_umin_reassoc_constant_use(
 ; CHECK-NEXT:    [[M1:%.*]] = call i8 @llvm.umin.i8(i8 [[X:%.*]], i8 [[Y:%.*]])
 ; CHECK-NEXT:    call void @use(i8 [[M1]])
 ; CHECK-NEXT:    [[M2:%.*]] = call i8 @llvm.umin.i8(i8 [[M1]], i8 42)
 ; CHECK-NEXT:    ret i8 [[M2]]
 ;
   %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_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:    [[M2:%.*]] = call i8 @llvm.smax.i8(i8 [[X:%.*]], i8 126)
+; CHECK-NEXT:    [[M3:%.*]] = call i8 @llvm.smax.i8(i8 [[M2]], i8 [[Y:%.*]])
 ; 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:    [[M2:%.*]] = call i8 @llvm.smax.i8(i8 [[Y:%.*]], i8 126)
+; CHECK-NEXT:    [[M3:%.*]] = call i8 @llvm.smax.i8(i8 [[M2]], i8 [[M1]])
 ; 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:    [[M3:%.*]] = call i8 @llvm.smin.i8(i8 [[M1]], i8 [[Y:%.*]])
 ; CHECK-NEXT:    ret i8 [[M3]]
 ;
   %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
 }