[InstCombine] allow more min/max with 'not' folds for intrinsics

[spatel]

Summary

isFreeToInvert allows min/max with 'not' on both operands, so easing the argument restriction catches the case where that operand has one use.

We already handle the sub-patterns when there are less uses:
https://alive2.llvm.org/ce/z/8Jatm_

...but this is another step towards parity with the equivalent icmp+select idioms ( D98152 ).

[spatel]

For reference/remaining steps - to avoid regressions on some important benchmarks, we probably need min/max intrinsics patches that give us functionality like:
D45317
D51398
D52177

It took several folds to see through patterns in cmyk code where the instructions have multi-uses.

[nikic]

LG

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

case Intrinsic::smin: {
     }
 
     // If we can eliminate ~A and Y is free to invert:
     // max ~A, Y --> ~(min A, ~Y)
     //
     // Examples:
     // max ~A, ~Y --> ~(min A, Y)
     // max ~A, C --> ~(min A, ~C)
+    // max ~A, (max ~Y, ~Z) --> ~min( A, (min Y, Z))
     auto moveNotAfterMinMax = [&](Value *X, Value *Y) -> Instruction * {
       Value *A;
       if (match(X, m_OneUse(m_Not(m_Value(A)))) &&
           !isFreeToInvert(A, A->hasOneUse()) &&
-          // Passing false to only consider m_Not and constants.
-          // TODO: Allow Y to match other patterns by checking use count.
-          isFreeToInvert(Y, false)) {
+          isFreeToInvert(Y, Y->hasOneUse())) {
         Value *NotY = Builder.CreateNot(Y);
         Intrinsic::ID InvID = getInverseMinMaxIntrinsic(IID);
         Value *InvMaxMin = Builder.CreateBinaryIntrinsic(InvID, A, NotY);
         return BinaryOperator::CreateNot(InvMaxMin);
       }
       return nullptr;
     };
 

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

 ;
   %notx = xor i8 %x, -1
   %m = call i8 @llvm.umin.i8(i8 -45, i8 %notx)
   ret i8 %m
 }
 
 define i8 @umin_of_not_and_smax(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @umin_of_not_and_smax(
-; CHECK-NEXT:    [[NOTX:%.*]] = xor i8 [[X:%.*]], -1
 ; CHECK-NEXT:    [[NOTY:%.*]] = xor i8 [[Y:%.*]], -1
 ; CHECK-NEXT:    call void @use(i8 [[NOTY]])
 ; CHECK-NEXT:    [[NOTZ:%.*]] = xor i8 [[Z:%.*]], -1
 ; CHECK-NEXT:    call void @use(i8 [[NOTZ]])
-; CHECK-NEXT:    [[M1:%.*]] = call i8 @llvm.smax.i8(i8 [[NOTY]], i8 [[NOTZ]])
-; CHECK-NEXT:    [[M2:%.*]] = call i8 @llvm.umin.i8(i8 [[M1]], i8 [[NOTX]])
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.smin.i8(i8 [[Y]], i8 [[Z]])
+; CHECK-NEXT:    [[TMP2:%.*]] = call i8 @llvm.umax.i8(i8 [[X:%.*]], i8 [[TMP1]])
+; CHECK-NEXT:    [[M2:%.*]] = xor i8 [[TMP2]], -1
 ; CHECK-NEXT:    ret i8 [[M2]]
 ;
   %notx = xor i8 %x, -1
   %noty = xor i8 %y, -1
   call void @use(i8 %noty)
   %notz = xor i8 %z, -1
   call void @use(i8 %notz)
   %m1 = call i8 @llvm.smax.i8(i8 %noty, i8 %notz)
   %m2 = call i8 @llvm.umin.i8(i8 %m1, i8 %notx)
   ret i8 %m2
 }
 
 define i8 @smin_of_umax_and_not(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @smin_of_umax_and_not(
-; CHECK-NEXT:    [[NOTX:%.*]] = xor i8 [[X:%.*]], -1
 ; CHECK-NEXT:    [[NOTY:%.*]] = xor i8 [[Y:%.*]], -1
 ; CHECK-NEXT:    call void @use(i8 [[NOTY]])
 ; CHECK-NEXT:    [[NOTZ:%.*]] = xor i8 [[Z:%.*]], -1
 ; CHECK-NEXT:    call void @use(i8 [[NOTZ]])
-; CHECK-NEXT:    [[M1:%.*]] = call i8 @llvm.umax.i8(i8 [[NOTY]], i8 [[NOTZ]])
-; CHECK-NEXT:    [[M2:%.*]] = call i8 @llvm.smin.i8(i8 [[NOTX]], i8 [[M1]])
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.umin.i8(i8 [[Y]], i8 [[Z]])
+; CHECK-NEXT:    [[TMP2:%.*]] = call i8 @llvm.smax.i8(i8 [[X:%.*]], i8 [[TMP1]])
+; CHECK-NEXT:    [[M2:%.*]] = xor i8 [[TMP2]], -1
 ; CHECK-NEXT:    ret i8 [[M2]]
 ;
   %notx = xor i8 %x, -1
   %noty = xor i8 %y, -1
   call void @use(i8 %noty)
   %notz = xor i8 %z, -1
   call void @use(i8 %notz)
   %m1 = call i8 @llvm.umax.i8(i8 %noty, i8 %notz)