[InstSimplify] Fold min/max intrinsic based on icmp of operands

[nikic]

Summary

This is a reboot of D84655, now performing the inner icmp simplification query without undef folds.

It should be possible to handle the current foldMinMaxSharedOp() fold based on this, by moving the logic into icmp of min/max instead, making it more general. We can't drop the folds for constant operands, because those also allow undef, which we exclude here.

[spatel]

I'm iffy about this. I was hoping that we could either remove the explicit folds or show more wins by using the general icmp simplification.
Based on the test diffs, we're only getting assume improvements, and that doesn't seem worth the effort of full icmp simplify.
It would be nice to show a more meaningful motivating case, but I doubt we will get that until we start canonicalizing to the intrinsics.
Thoughts?

[nikic]

In D85929#2218748, @spatel wrote:

I'm iffy about this. I was hoping that we could either remove the explicit folds or show more wins by using the general icmp simplification.
Based on the test diffs, we're only getting assume improvements, and that doesn't seem worth the effort of full icmp simplify.
It would be nice to show a more meaningful motivating case, but I doubt we will get that until we start canonicalizing to the intrinsics.
Thoughts?

I only used assume tests because that seemed like the most direct way to test the change. We also get all other folds that are implemented for icmp, e.g. we recognize that

%add = add nuw i8 %x, 1
%max = call i8 @llvm.umax.i8(i8 %x, i8 %add)
ret i8 %max

is the same as ret i8 %add. I'm not sure how valuable it would be to explicitly test these, as they are already covered by the icmp tests.

[spatel]

In D85929#2232639, @nikic wrote:

In D85929#2218748, @spatel wrote:

I'm iffy about this. I was hoping that we could either remove the explicit folds or show more wins by using the general icmp simplification.
Based on the test diffs, we're only getting assume improvements, and that doesn't seem worth the effort of full icmp simplify.
It would be nice to show a more meaningful motivating case, but I doubt we will get that until we start canonicalizing to the intrinsics.
Thoughts?

I only used assume tests because that seemed like the most direct way to test the change. We also get all other folds that are implemented for icmp, e.g. we recognize that

%add = add nuw i8 %x, 1
%max = call i8 @llvm.umax.i8(i8 %x, i8 %add)
ret i8 %max

is the same as ret i8 %add. I'm not sure how valuable it would be to explicitly test these, as they are already covered by the icmp tests.

I agree it's not worth duplicating everything, but a bit of variation in the test coverage would make the context/motivation clearer when others look back at the code change. One more test? :)
We're never going to recover tiny add-on costs like this until we rewrite instsimplify/instcombine pattern matching completely (part of the switch to MLIR?).
I don't think we can know at this point if it's worthwhile, but I can't really object, so LGTM.

llvm/lib/Analysis/InstructionSimplify.cpp

static APInt getMaxMinLimit(Intrinsic::ID IID, unsigned BitWidth) {
   case Intrinsic::smax: return APInt::getSignedMaxValue(BitWidth);
   case Intrinsic::smin: return APInt::getSignedMinValue(BitWidth);
   case Intrinsic::umax: return APInt::getMaxValue(BitWidth);
   case Intrinsic::umin: return APInt::getMinValue(BitWidth);
   default: llvm_unreachable("Unexpected intrinsic");
   }
 }
 
+static ICmpInst::Predicate getMaxMinPredicate(Intrinsic::ID IID) {
+  switch (IID) {
+  case Intrinsic::smax: return ICmpInst::ICMP_SGE;
+  case Intrinsic::smin: return ICmpInst::ICMP_SLE;
+  case Intrinsic::umax: return ICmpInst::ICMP_UGE;
+  case Intrinsic::umin: return ICmpInst::ICMP_ULE;
+  default: llvm_unreachable("Unexpected intrinsic");
+  }
+}
+
 /// Given a min/max intrinsic, see if it can be removed based on having an
 /// operand that is another min/max intrinsic with shared operand(s). The caller
 /// is expected to swap the operand arguments to handle commutation.
 static Value *foldMinMaxSharedOp(Intrinsic::ID IID, Value *Op0, Value *Op1) {
   Value *X, *Y;
   if (!match(Op0, m_MaxOrMin(m_Value(X), m_Value(Y))))
     return nullptr;
 
if (match(Op1, m_APIntAllowUndef(C))) {
       }
     }
 
     if (Value *V = foldMinMaxSharedOp(IID, Op0, Op1))
       return V;
     if (Value *V = foldMinMaxSharedOp(IID, Op1, Op0))
       return V;
 
+    ICmpInst::Predicate Pred = getMaxMinPredicate(IID);
+    if (isICmpTrue(Pred, Op0, Op1, Q.getWithoutUndef(), RecursionLimit))
+      return Op0;
+    if (isICmpTrue(Pred, Op1, Op0, Q.getWithoutUndef(), RecursionLimit))
+      return Op1;
+
     break;
   }
   case Intrinsic::usub_with_overflow:
   case Intrinsic::ssub_with_overflow:
     // X - X -> { 0, false }
     if (Op0 == Op1)
       return Constant::getNullValue(ReturnType);
     LLVM_FALLTHROUGH;

llvm/test/Transforms/InstSimplify/maxmin_intrinsics.ll

;
   %c = icmp sgt i8 %m, 5
   ret i1 %c
 }
 
 define i8 @umin_assume_uge(i8 %x, i8 %y) {
 ; CHECK-LABEL: @umin_assume_uge(
 ; CHECK-NEXT:    [[C:%.*]] = icmp uge i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C]])
-; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.umin.i8(i8 [[X]], i8 [[Y]])
-; CHECK-NEXT:    ret i8 [[M]]
+; CHECK-NEXT:    ret i8 [[Y]]
 ;
   %c = icmp uge i8 %x, %y
   call void @llvm.assume(i1 %c)
   %m = call i8 @llvm.umin.i8(i8 %x, i8 %y)
   ret i8 %m
 }
 
 define i8 @umin_assume_ugt(i8 %x, i8 %y) {
 ; CHECK-LABEL: @umin_assume_ugt(
 ; CHECK-NEXT:    [[C:%.*]] = icmp ugt i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C]])
-; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.umin.i8(i8 [[X]], i8 [[Y]])
-; CHECK-NEXT:    ret i8 [[M]]
+; CHECK-NEXT:    ret i8 [[Y]]
 ;
   %c = icmp ugt i8 %x, %y
   call void @llvm.assume(i1 %c)
   %m = call i8 @llvm.umin.i8(i8 %x, i8 %y)
   ret i8 %m
 }
 
 define i8 @umin_assume_ule(i8 %x, i8 %y) {
 ; CHECK-LABEL: @umin_assume_ule(
 ; CHECK-NEXT:    [[C:%.*]] = icmp ule i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C]])
-; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.umin.i8(i8 [[X]], i8 [[Y]])
-; CHECK-NEXT:    ret i8 [[M]]
+; CHECK-NEXT:    ret i8 [[X]]
 ;
   %c = icmp ule i8 %x, %y
   call void @llvm.assume(i1 %c)
   %m = call i8 @llvm.umin.i8(i8 %x, i8 %y)
   ret i8 %m
 }
 
 define i8 @umin_assume_ult(i8 %x, i8 %y) {
 ; CHECK-LABEL: @umin_assume_ult(
 ; CHECK-NEXT:    [[C:%.*]] = icmp ult i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C]])
-; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.umin.i8(i8 [[X]], i8 [[Y]])
-; CHECK-NEXT:    ret i8 [[M]]
+; CHECK-NEXT:    ret i8 [[X]]
 ;
   %c = icmp ult i8 %x, %y
   call void @llvm.assume(i1 %c)
   %m = call i8 @llvm.umin.i8(i8 %x, i8 %y)
   ret i8 %m
 }
 
 define i8 @umax_assume_uge(i8 %x, i8 %y) {
 ; CHECK-LABEL: @umax_assume_uge(
 ; CHECK-NEXT:    [[C:%.*]] = icmp uge i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C]])
-; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.umax.i8(i8 [[X]], i8 [[Y]])
-; CHECK-NEXT:    ret i8 [[M]]
+; CHECK-NEXT:    ret i8 [[X]]
 ;
   %c = icmp uge i8 %x, %y
   call void @llvm.assume(i1 %c)
   %m = call i8 @llvm.umax.i8(i8 %x, i8 %y)
   ret i8 %m
 }
 
 define i8 @umax_assume_ugt(i8 %x, i8 %y) {
 ; CHECK-LABEL: @umax_assume_ugt(
 ; CHECK-NEXT:    [[C:%.*]] = icmp ugt i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C]])
-; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.umax.i8(i8 [[X]], i8 [[Y]])
-; CHECK-NEXT:    ret i8 [[M]]
+; CHECK-NEXT:    ret i8 [[X]]
 ;
   %c = icmp ugt i8 %x, %y
   call void @llvm.assume(i1 %c)
   %m = call i8 @llvm.umax.i8(i8 %x, i8 %y)
   ret i8 %m
 }
 
 define i8 @umax_assume_ule(i8 %x, i8 %y) {
 ; CHECK-LABEL: @umax_assume_ule(
 ; CHECK-NEXT:    [[C:%.*]] = icmp ule i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C]])
-; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.umax.i8(i8 [[X]], i8 [[Y]])
-; CHECK-NEXT:    ret i8 [[M]]
+; CHECK-NEXT:    ret i8 [[Y]]
 ;
   %c = icmp ule i8 %x, %y
   call void @llvm.assume(i1 %c)
   %m = call i8 @llvm.umax.i8(i8 %x, i8 %y)
   ret i8 %m
 }
 
 define i8 @umax_assume_ult(i8 %x, i8 %y) {
 ; CHECK-LABEL: @umax_assume_ult(
 ; CHECK-NEXT:    [[C:%.*]] = icmp ult i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C]])
-; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.umax.i8(i8 [[X]], i8 [[Y]])
-; CHECK-NEXT:    ret i8 [[M]]
+; CHECK-NEXT:    ret i8 [[Y]]
 ;
   %c = icmp ult i8 %x, %y
   call void @llvm.assume(i1 %c)
   %m = call i8 @llvm.umax.i8(i8 %x, i8 %y)
   ret i8 %m
 }
 
 define i8 @smin_assume_sge(i8 %x, i8 %y) {
 ; CHECK-LABEL: @smin_assume_sge(
 ; CHECK-NEXT:    [[C:%.*]] = icmp sge i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C]])
-; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.smin.i8(i8 [[X]], i8 [[Y]])
-; CHECK-NEXT:    ret i8 [[M]]
+; CHECK-NEXT:    ret i8 [[Y]]
 ;
   %c = icmp sge i8 %x, %y
   call void @llvm.assume(i1 %c)
   %m = call i8 @llvm.smin.i8(i8 %x, i8 %y)
   ret i8 %m
 }
 
 define i8 @smin_assume_sgt(i8 %x, i8 %y) {
 ; CHECK-LABEL: @smin_assume_sgt(
 ; CHECK-NEXT:    [[C:%.*]] = icmp sgt i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C]])
-; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.smin.i8(i8 [[X]], i8 [[Y]])
-; CHECK-NEXT:    ret i8 [[M]]
+; CHECK-NEXT:    ret i8 [[Y]]
 ;
   %c = icmp sgt i8 %x, %y
   call void @llvm.assume(i1 %c)
   %m = call i8 @llvm.smin.i8(i8 %x, i8 %y)
   ret i8 %m
 }
 
 define i8 @smin_assume_sle(i8 %x, i8 %y) {
 ; CHECK-LABEL: @smin_assume_sle(
 ; CHECK-NEXT:    [[C:%.*]] = icmp sle i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C]])
-; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.smin.i8(i8 [[X]], i8 [[Y]])
-; CHECK-NEXT:    ret i8 [[M]]
+; CHECK-NEXT:    ret i8 [[X]]
 ;
   %c = icmp sle i8 %x, %y
   call void @llvm.assume(i1 %c)
   %m = call i8 @llvm.smin.i8(i8 %x, i8 %y)
   ret i8 %m
 }
 
 define i8 @smin_assume_slt(i8 %x, i8 %y) {
 ; CHECK-LABEL: @smin_assume_slt(
 ; CHECK-NEXT:    [[C:%.*]] = icmp slt i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C]])
-; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.smin.i8(i8 [[X]], i8 [[Y]])
-; CHECK-NEXT:    ret i8 [[M]]
+; CHECK-NEXT:    ret i8 [[X]]
 ;
   %c = icmp slt i8 %x, %y
   call void @llvm.assume(i1 %c)
   %m = call i8 @llvm.smin.i8(i8 %x, i8 %y)
   ret i8 %m
 }
 
 define i8 @smax_assume_sge(i8 %x, i8 %y) {
 ; CHECK-LABEL: @smax_assume_sge(
 ; CHECK-NEXT:    [[C:%.*]] = icmp sge i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C]])
-; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.smax.i8(i8 [[X]], i8 [[Y]])
-; CHECK-NEXT:    ret i8 [[M]]
+; CHECK-NEXT:    ret i8 [[X]]
 ;
   %c = icmp sge i8 %x, %y
   call void @llvm.assume(i1 %c)
   %m = call i8 @llvm.smax.i8(i8 %x, i8 %y)
   ret i8 %m
 }
 
 define i8 @smax_assume_sgt(i8 %x, i8 %y) {
 ; CHECK-LABEL: @smax_assume_sgt(
 ; CHECK-NEXT:    [[C:%.*]] = icmp sgt i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C]])
-; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.smax.i8(i8 [[X]], i8 [[Y]])
-; CHECK-NEXT:    ret i8 [[M]]
+; CHECK-NEXT:    ret i8 [[X]]
 ;
   %c = icmp sgt i8 %x, %y
   call void @llvm.assume(i1 %c)
   %m = call i8 @llvm.smax.i8(i8 %x, i8 %y)
   ret i8 %m
 }
 
 define i8 @smax_assume_sle(i8 %x, i8 %y) {
 ; CHECK-LABEL: @smax_assume_sle(
 ; CHECK-NEXT:    [[C:%.*]] = icmp sle i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C]])
-; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.smax.i8(i8 [[X]], i8 [[Y]])
-; CHECK-NEXT:    ret i8 [[M]]
+; CHECK-NEXT:    ret i8 [[Y]]
 ;
   %c = icmp sle i8 %x, %y
   call void @llvm.assume(i1 %c)
   %m = call i8 @llvm.smax.i8(i8 %x, i8 %y)
   ret i8 %m
 }
 
 define i8 @smax_assume_slt(i8 %x, i8 %y) {
 ; CHECK-LABEL: @smax_assume_slt(
 ; CHECK-NEXT:    [[C:%.*]] = icmp slt i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C]])
-; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.smax.i8(i8 [[X]], i8 [[Y]])
-; CHECK-NEXT:    ret i8 [[M]]
+; CHECK-NEXT:    ret i8 [[Y]]
 ;
   %c = icmp slt i8 %x, %y
   call void @llvm.assume(i1 %c)
   %m = call i8 @llvm.smax.i8(i8 %x, i8 %y)
   ret i8 %m
 }
 
 define i8 @umax_add_nuw_1(i8 %x) {
 ; CHECK-LABEL: @umax_add_nuw_1(
 ; CHECK-NEXT:    [[ADD:%.*]] = add nuw i8 [[X:%.*]], 1
-; CHECK-NEXT:    [[MAX:%.*]] = call i8 @llvm.umax.i8(i8 [[ADD]], i8 [[X]])
-; CHECK-NEXT:    ret i8 [[MAX]]
+; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %add = add nuw i8 %x, 1
   %max = call i8 @llvm.umax.i8(i8 %add, i8 %x)
   ret i8 %max
 }
 
 define i8 @umax_add_nuw_2(i8 %x) {
 ; CHECK-LABEL: @umax_add_nuw_2(
 ; CHECK-NEXT:    [[ADD:%.*]] = add nuw i8 [[X:%.*]], 42
-; CHECK-NEXT:    [[MAX:%.*]] = call i8 @llvm.umax.i8(i8 [[ADD]], i8 42)
-; CHECK-NEXT:    ret i8 [[MAX]]
+; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %add = add nuw i8 %x, 42
   %max = call i8 @llvm.umax.i8(i8 %add, i8 42)
   ret i8 %max
 }
 
 define i8 @umax_range_metadata(i8* %p1, i8* %p2) {
 ; CHECK-LABEL: @umax_range_metadata(
-; CHECK-NEXT:    [[X:%.*]] = load i8, i8* [[P1:%.*]], align 1, [[RNG0:!range !.*]]
-; CHECK-NEXT:    [[Y:%.*]] = load i8, i8* [[P2:%.*]], align 1, [[RNG1:!range !.*]]
-; CHECK-NEXT:    [[MAX:%.*]] = call i8 @llvm.umax.i8(i8 [[X]], i8 [[Y]])
-; CHECK-NEXT:    ret i8 [[MAX]]
+; CHECK-NEXT:    [[Y:%.*]] = load i8, i8* [[P2:%.*]], align 1, [[RNG0:!range !.*]]
+; CHECK-NEXT:    ret i8 [[Y]]
 ;
   %x = load i8, i8* %p1, !range !{i8 0, i8 10}
   %y = load i8, i8* %p2, !range !{i8 20, i8 30}
   %max = call i8 @llvm.umax.i8(i8 %x, i8 %y)
   ret i8 %max
 }
 
 define i8 @umax_zext_sext(i4 %x) {
 ; CHECK-LABEL: @umax_zext_sext(
-; CHECK-NEXT:    [[ZEXT:%.*]] = zext i4 [[X:%.*]] to i8
-; CHECK-NEXT:    [[SEXT:%.*]] = sext i4 [[X]] to i8
-; CHECK-NEXT:    [[MAX:%.*]] = call i8 @llvm.umax.i8(i8 [[ZEXT]], i8 [[SEXT]])
-; CHECK-NEXT:    ret i8 [[MAX]]
+; CHECK-NEXT:    [[SEXT:%.*]] = sext i4 [[X:%.*]] to i8
+; CHECK-NEXT:    ret i8 [[SEXT]]
 ;
   %zext = zext i4 %x to i8
   %sext = sext i4 %x to i8
   %max = call i8 @llvm.umax.i8(i8 %zext, i8 %sext)
   ret i8 %max
 }
 
 define i8 @umax_lshr(i8 %x, i8 %y) {
 ; CHECK-LABEL: @umax_lshr(
-; CHECK-NEXT:    [[SHR:%.*]] = lshr i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[MAX:%.*]] = call i8 @llvm.umax.i8(i8 [[X]], i8 [[SHR]])
-; CHECK-NEXT:    ret i8 [[MAX]]
+; CHECK-NEXT:    ret i8 [[X:%.*]]
 ;
   %shr = lshr i8 %x, %y
   %max = call i8 @llvm.umax.i8(i8 %x, i8 %shr)
   ret i8 %max
 }