[InstCombine] use isFreeToInvert to generalize min/max with 'not'

[spatel]

Summary

This mimics the code for the corresponding cmp-select idiom.

This also prevents an infinite loop because isFreeToInvert does not match constant expressions.

So this patch solves the same problem as D108814 and would overwrite it, but my main motivation is to enhance the pattern matching to allow more invertible ops. I'll post that change as a follow-up patch on top of this one.

[nikic]

LG

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

if (IID == Intrinsic::smax || IID == Intrinsic::smin) {
       if (match(I0, m_NSWNeg(m_Value(X))) && match(I1, m_NSWNeg(m_Value(Y))) &&
           (I0->hasOneUse() || I1->hasOneUse())) {
         Intrinsic::ID InvID = getInverseMinMaxIntrinsic(IID);
         Value *InvMaxMin = Builder.CreateBinaryIntrinsic(InvID, X, Y);
         return BinaryOperator::CreateNSWNeg(InvMaxMin);
       }
     }
 
-    if (match(I0, m_Not(m_Value(X)))) {
-      // max (not X), (not Y) --> not (min X, Y)
+    // 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)
+    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)) {
+        Value *NotY = Builder.CreateNot(Y);
         Intrinsic::ID InvID = getInverseMinMaxIntrinsic(IID);
-      if (match(I1, m_Not(m_Value(Y))) &&
-          (I0->hasOneUse() || I1->hasOneUse())) {
-        Value *InvMaxMin = Builder.CreateBinaryIntrinsic(InvID, X, Y);
+        Value *InvMaxMin = Builder.CreateBinaryIntrinsic(InvID, A, NotY);
         return BinaryOperator::CreateNot(InvMaxMin);
       }
-      // max (not X), C --> not(min X, ~C)
-      if (match(I1, m_Constant(C)) && I0->hasOneUse()) {
-        Constant *NotC = ConstantExpr::getNot(C);
-        Value *InvMaxMin = Builder.CreateBinaryIntrinsic(InvID, X, NotC);
-        return BinaryOperator::CreateNot(InvMaxMin);
-      }
-    }
+      return nullptr;
+    };
+
+    if (Instruction *I = moveNotAfterMinMax(I0, I1))
+      return I;
+    if (Instruction *I = moveNotAfterMinMax(I1, I0))
+      return I;
 
     // smax(X, -X) --> abs(X)
     // smin(X, -X) --> -abs(X)
     // umax(X, -X) --> -abs(X)
     // umin(X, -X) --> abs(X)
     if (isKnownNegation(I0, I1)) {
       // We can choose either operand as the input to abs(), but if we can
       // eliminate the only use of a value, that's better for subsequent

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

 }
 
 ; An extra use is ok.
 
 define i8 @umax_of_nots(i8 %x, i8 %y) {
 ; CHECK-LABEL: @umax_of_nots(
 ; CHECK-NEXT:    [[NOTX:%.*]] = xor i8 [[X:%.*]], -1
 ; CHECK-NEXT:    call void @use(i8 [[NOTX]])
-; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.umin.i8(i8 [[X]], i8 [[Y:%.*]])
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.umin.i8(i8 [[Y:%.*]], i8 [[X]])
 ; CHECK-NEXT:    [[M:%.*]] = xor i8 [[TMP1]], -1
 ; CHECK-NEXT:    ret i8 [[M]]
 ;
   %notx = xor i8 %x, -1
   call void @use(i8 %notx)
   %noty = xor i8 %y, -1
   %m = call i8 @llvm.umax.i8(i8 %notx, i8 %noty)
   ret i8 %m
;
   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)
   %m2 = call i8 @llvm.smin.i8(i8 %notx, i8 %m1)
   ret i8 %m2
 }
 
+; Negative test - don't infinite loop on constant expression
+
+define i8 @umin_of_not_and_nontrivial_const(i8 %x) {
+; CHECK-LABEL: @umin_of_not_and_nontrivial_const(
+; CHECK-NEXT:    [[NOTX:%.*]] = xor i8 [[X:%.*]], -1
+; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.umin.i8(i8 [[NOTX]], i8 ptrtoint (i8 (i8)* @umin_of_not_and_nontrivial_const to i8))
+; CHECK-NEXT:    ret i8 [[M]]
+;
+  %notx = xor i8 %x, -1
+  %m = call i8 @llvm.umin.i8(i8 ptrtoint (i8(i8)* @umin_of_not_and_nontrivial_const to i8), i8 %notx)
+  ret i8 %m
+}
+
 ; Negative test - too many uses
 
 define i8 @umin_of_not_and_const_uses(i8 %x) {
 ; CHECK-LABEL: @umin_of_not_and_const_uses(
 ; CHECK-NEXT:    [[NOTX:%.*]] = xor i8 [[X:%.*]], -1
 ; CHECK-NEXT:    call void @use(i8 [[NOTX]])
 ; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.umin.i8(i8 [[NOTX]], i8 -45)
 ; CHECK-NEXT:    ret i8 [[M]]