[InstCombine] Add transforms for `(max/min (xor X, Pow2), X)` -> `(and/or X, Pow2/~Pow2)`

[goldstein.w.n]

Summary

X ^ Pow2 is guranteed to flip one bit. We can use this to speedup
max/min by just selecting X with/without (or/andnot) the flipped bit
respectively.

Alive2 Links:
smax-neg: https://alive2.llvm.org/ce/z/j3QYFs
smin-neg: https://alive2.llvm.org/ce/z/bFYnQW
smax-pos: https://alive2.llvm.org/ce/z/4xYSxR
smin-pos: https://alive2.llvm.org/ce/z/H3RPKj
umax : https://alive2.llvm.org/ce/z/P4oRcX
umin : https://alive2.llvm.org/ce/z/vWZG6p

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

1498–1500

If we can prove that some value is a constant, then shouldn't we have zapped it already?
The test example shows that we are missing a fold like this:
https://alive2.llvm.org/ce/z/z5xok2

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

1498–1500

If we can prove that some value is a constant, then shouldn't we have zapped it already?
The test example shows that we are missing a fold like this:
https://alive2.llvm.org/ce/z/z5xok2

It's one of the cases that falls through the cracks. IsPow2 && Negative implies int-min but we don't have an explicit check for that anywhere.

I considered adding it in computeKnownBits but it seems like an edge case that is not worth the significant amounts of extra analysis needed to cover it.
(similiar to how isKnownPowerOf2(X, /*OrZero*/false) misses alot of cases that could be covered if we just did isKnownPowerOf2(X, /*OrZero*/true) && isKnownNonZero(X) and isKnownNonZero(X) misses some cases that computeKnownBits(X) hits)

ValueTracking imo is a bit of a mess at the moment, but most of the easy fixes have compile time concerns.

[spatel]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

1498

Its -> It's

1498–1500

Yes, it's messy, and it's not clear what is worth generalizing vs. pattern matching directly.

I filed https://github.com/llvm/llvm-project/issues/60957 - if you're seeing BMI-related patterns like this in real code, then it's probably worth getting that one way or another.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

1498–1500

Yes, it's messy, and it's not clear what is worth generalizing vs. pattern matching directly.

I filed https://github.com/llvm/llvm-project/issues/60957 - if you're seeing BMI-related patterns like this in real code, then it's probably worth getting that one way or another.

[goldstein.w.n]

Fix misspel

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);
       }
     }
 
+    // (umax X, (xor X, Pow2))
+    //      -> (or X, Pow2)
+    // (umin X, (xor X, Pow2))
+    //      -> (and X, ~Pow2)
+    // (smax X, (xor X, Pos_Pow2))
+    //      -> (or X, Pos_Pow2)
+    // (smin X, (xor X, Pos_Pow2))
+    //      -> (and X, ~Pos_Pow2)
+    // (smax X, (xor X, Neg_Pow2))
+    //      -> (and X, ~Neg_Pow2)
+    // (smin X, (xor X, Neg_Pow2))
+    //      -> (or X, Neg_Pow2)
+    if ((match(I0, m_c_Xor(m_Specific(I1), m_Value(X))) ||
+         match(I1, m_c_Xor(m_Specific(I0), m_Value(X)))) &&
+        isKnownToBeAPowerOfTwo(X, /* OrZero */ true)) {
+      bool UseOr = IID == Intrinsic::smax || IID == Intrinsic::umax;
+      bool UseAndN = IID == Intrinsic::smin || IID == Intrinsic::umin;
+
+      if (IID == Intrinsic::smax || IID == Intrinsic::smin) {
+        auto KnownSign = getKnownSign(X, II, DL, &AC, &DT);
+        if (KnownSign == std::nullopt) {
+          UseOr = false;
+          UseAndN = false;
+        } else if (*KnownSign /* true is Signed. */) {
+          UseOr ^= true;
+          UseAndN ^= true;
+          Type *Ty = I0->getType();
+          // Negative power of 2 must be IntMin. It's possible to be able to
+          // prove negative / power of 2 without actually having known bits, so
+          // just get the value by hand.
+          X = Constant::getIntegerValue(
+              Ty, APInt::getSignedMinValue(Ty->getScalarSizeInBits()));
+        }
+      }
+      if (UseOr)
+        return BinaryOperator::CreateOr(I0, X);
+      else if (UseAndN)
+        return BinaryOperator::CreateAnd(I0, Builder.CreateNot(X));
+    }
+
     // 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 * {

llvm/test/Transforms/InstCombine/minmax-of-xor-x.ll

 declare <2 x i8> @llvm.smax.v2i8(<2 x i8>, <2 x i8>)
 declare <2 x i8> @llvm.umax.v2i8(<2 x i8>, <2 x i8>)
 
 declare void @llvm.assume(i1)
 declare void @barrier()
 
 define <2 x i8> @umax_xor_Cpow2(<2 x i8> %x) {
 ; CHECK-LABEL: @umax_xor_Cpow2(
-; CHECK-NEXT:    [[X_XOR:%.*]] = xor <2 x i8> [[X:%.*]], <i8 -128, i8 -128>
-; CHECK-NEXT:    [[R:%.*]] = call <2 x i8> @llvm.umax.v2i8(<2 x i8> [[X]], <2 x i8> [[X_XOR]])
+; CHECK-NEXT:    [[R:%.*]] = or <2 x i8> [[X:%.*]], <i8 -128, i8 -128>
 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 ;
   %x_xor = xor <2 x i8> %x, <i8 128, i8 128>
   %r = call <2 x i8> @llvm.umax.v2i8(<2 x i8> %x, <2 x i8> %x_xor)
   ret <2 x i8> %r
 }
 
 define i8 @umin_xor_Cpow2(i8 %x) {
 ; CHECK-LABEL: @umin_xor_Cpow2(
-; CHECK-NEXT:    [[X_XOR:%.*]] = xor i8 [[X:%.*]], 64
-; CHECK-NEXT:    [[R:%.*]] = call i8 @llvm.umin.i8(i8 [[X]], i8 [[X_XOR]])
+; CHECK-NEXT:    [[R:%.*]] = and i8 [[X:%.*]], -65
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %x_xor = xor i8 %x, 64
   %r = call i8 @llvm.umin.i8(i8 %x, i8 %x_xor)
   ret i8 %r
 }
 
 define i8 @smax_xor_Cpow2_pos(i8 %x) {
 ; CHECK-LABEL: @smax_xor_Cpow2_pos(
-; CHECK-NEXT:    [[X_XOR:%.*]] = xor i8 [[X:%.*]], 32
-; CHECK-NEXT:    [[R:%.*]] = call i8 @llvm.smax.i8(i8 [[X]], i8 [[X_XOR]])
+; CHECK-NEXT:    [[R:%.*]] = or i8 [[X:%.*]], 32
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %x_xor = xor i8 %x, 32
   %r = call i8 @llvm.smax.i8(i8 %x, i8 %x_xor)
   ret i8 %r
 }
 
 define <2 x i8> @smin_xor_Cpow2_pos(<2 x i8> %x) {
 ; CHECK-LABEL: @smin_xor_Cpow2_pos(
-; CHECK-NEXT:    [[X_XOR:%.*]] = xor <2 x i8> [[X:%.*]], <i8 16, i8 16>
-; CHECK-NEXT:    [[R:%.*]] = call <2 x i8> @llvm.smin.v2i8(<2 x i8> [[X]], <2 x i8> [[X_XOR]])
+; CHECK-NEXT:    [[R:%.*]] = and <2 x i8> [[X:%.*]], <i8 -17, i8 -17>
 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 ;
   %x_xor = xor <2 x i8> %x, <i8 16, i8 16>
   %r = call <2 x i8> @llvm.smin.v2i8(<2 x i8> %x, <2 x i8> %x_xor)
   ret <2 x i8> %r
 }
 
 define <2 x i8> @smax_xor_Cpow2_neg(<2 x i8> %x) {
 ; CHECK-LABEL: @smax_xor_Cpow2_neg(
-; CHECK-NEXT:    [[X_XOR:%.*]] = xor <2 x i8> [[X:%.*]], <i8 -128, i8 -128>
-; CHECK-NEXT:    [[R:%.*]] = call <2 x i8> @llvm.smax.v2i8(<2 x i8> [[X]], <2 x i8> [[X_XOR]])
+; CHECK-NEXT:    [[R:%.*]] = and <2 x i8> [[X:%.*]], <i8 127, i8 127>
 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 ;
   %x_xor = xor <2 x i8> %x, <i8 128, i8 128>
   %r = call <2 x i8> @llvm.smax.v2i8(<2 x i8> %x, <2 x i8> %x_xor)
   ret <2 x i8> %r
 }
 
 define i8 @smin_xor_Cpow2_neg(i8 %x) {
 ; CHECK-LABEL: @smin_xor_Cpow2_neg(
-; CHECK-NEXT:    [[X_XOR:%.*]] = xor i8 [[X:%.*]], -128
-; CHECK-NEXT:    [[R:%.*]] = call i8 @llvm.smin.i8(i8 [[X]], i8 [[X_XOR]])
+; CHECK-NEXT:    [[R:%.*]] = or i8 [[X:%.*]], -128
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %x_xor = xor i8 %x, 128
   %r = call i8 @llvm.smin.i8(i8 %x, i8 %x_xor)
   ret i8 %r
 }
 
 define i8 @umax_xor_pow2(i8 %x, i8 %y) {
 ; CHECK-LABEL: @umax_xor_pow2(
 ; CHECK-NEXT:    [[NY:%.*]] = sub i8 0, [[Y:%.*]]
 ; CHECK-NEXT:    [[YP2:%.*]] = and i8 [[NY]], [[Y]]
-; CHECK-NEXT:    [[X_XOR:%.*]] = xor i8 [[YP2]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = call i8 @llvm.umax.i8(i8 [[X]], i8 [[X_XOR]])
+; CHECK-NEXT:    [[R:%.*]] = or i8 [[YP2]], [[X:%.*]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %ny = sub i8 0, %y
   %yp2 = and i8 %y, %ny
   %x_xor = xor i8 %x, %yp2
   %r = call i8 @llvm.umax.i8(i8 %x, i8 %x_xor)
   ret i8 %r
 }
 
 define <2 x i8> @umin_xor_pow2(<2 x i8> %x, <2 x i8> %y) {
 ; CHECK-LABEL: @umin_xor_pow2(
 ; CHECK-NEXT:    [[NY:%.*]] = sub <2 x i8> zeroinitializer, [[Y:%.*]]
 ; CHECK-NEXT:    [[YP2:%.*]] = and <2 x i8> [[NY]], [[Y]]
-; CHECK-NEXT:    [[X_XOR:%.*]] = xor <2 x i8> [[YP2]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = call <2 x i8> @llvm.umin.v2i8(<2 x i8> [[X]], <2 x i8> [[X_XOR]])
+; CHECK-NEXT:    [[TMP1:%.*]] = xor <2 x i8> [[YP2]], <i8 -1, i8 -1>
+; CHECK-NEXT:    [[R:%.*]] = and <2 x i8> [[TMP1]], [[X:%.*]]
 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 ;
   %ny = sub <2 x i8> <i8 0, i8 0>, %y
   %yp2 = and <2 x i8> %y, %ny
   %x_xor = xor <2 x i8> %x, %yp2
   %r = call <2 x i8> @llvm.umin.v2i8(<2 x i8> %x, <2 x i8> %x_xor)
   ret <2 x i8> %r
 }

 
 define i8 @smax_xor_pow2_neg(i8 %x, i8 %y) {
 ; CHECK-LABEL: @smax_xor_pow2_neg(
 ; CHECK-NEXT:    [[NY:%.*]] = sub i8 0, [[Y:%.*]]
 ; CHECK-NEXT:    [[YP2:%.*]] = and i8 [[NY]], [[Y]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[YP2]], 0
 ; CHECK-NEXT:    br i1 [[CMP]], label [[NEG:%.*]], label [[POS:%.*]]
 ; CHECK:       neg:
-; CHECK-NEXT:    [[X_XOR:%.*]] = xor i8 [[YP2]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = call i8 @llvm.smax.i8(i8 [[X]], i8 [[X_XOR]])
+; CHECK-NEXT:    [[R:%.*]] = and i8 [[X:%.*]], 127
 ; CHECK-NEXT:    ret i8 [[R]]
 ; CHECK:       pos:
 ; CHECK-NEXT:    call void @barrier()
 ; CHECK-NEXT:    ret i8 0
 ;
   %ny = sub i8 0, %y
   %yp2 = and i8 %y, %ny
   %cmp = icmp slt i8 %yp2, 0

 
 define i8 @smin_xor_pow2_pos(i8 %x, i8 %y) {
 ; CHECK-LABEL: @smin_xor_pow2_pos(
 ; CHECK-NEXT:    [[NY:%.*]] = sub i8 0, [[Y:%.*]]
 ; CHECK-NEXT:    [[YP2:%.*]] = and i8 [[NY]], [[Y]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i8 [[YP2]], 0
 ; CHECK-NEXT:    br i1 [[CMP]], label [[NEG:%.*]], label [[POS:%.*]]
 ; CHECK:       neg:
-; CHECK-NEXT:    [[X_XOR:%.*]] = xor i8 [[YP2]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = call i8 @llvm.smin.i8(i8 [[X]], i8 [[X_XOR]])
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i8 [[YP2]], -1
+; CHECK-NEXT:    [[R:%.*]] = and i8 [[TMP1]], [[X:%.*]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ; CHECK:       pos:
 ; CHECK-NEXT:    call void @barrier()
 ; CHECK-NEXT:    ret i8 0
 ;
   %ny = sub i8 0, %y
   %yp2 = and i8 %y, %ny
   %cmp = icmp sgt i8 %yp2, 0