[InstCombine] Fold (min/max ~X, Y) -> ~(max/min X, ~Y) when Y is freely invertible

[craig.topper]

Summary

If the ~X wasn't able to simplify above the max/min, we might be able to simplify it by moving it below the max/min.

I had to modify the ~(min/max ~X, Y) transform to prevent getting stuck in a loop when we saw the new ~(max/min X, ~Y) before the ~Y had been folded away to remove the new not.

I've left the subtract tests from my previous patch because that's the pattern I want to get optimized. I've added an additional non splat test and dropped the multiple use of the select test since it no longer applied.

[spatel]

https://rise4fun.com/Alive/pAh
Since we know this isn't limited to negate, there should be a 'TODO' about that...or just allow for that possibility in this patch? Not difficult to make the match() account for an arbitrary constant.
Also, whether we use IsFreeToInvert or m_Constant(), I think this fold will work for an arbitrary vector constant, not just a splat. Adding a test for that will make @RKSimon happier. :)

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1771 ↗

(On Diff #163002)

The formula suggests that we have a constant, but the code allows for a variable operand. Either the comment should change to match code (C becomes Y) and add a test for that possibility or change the code to match the comment.

Also, we're inverting min/max, so the result in the formula should read (max/min X, ~C)?

1787 ↗

(On Diff #163002)

That should be CreateNot(LHS)? Guessing there's no test coverage for this clause.

test/Transforms/InstCombine/sub.ll

1061 ↗

(On Diff #163002)

As usual, I'd prefer that the tests are committed first with baseline checks.

[spatel]

On 2nd thought...
This is a missed general canonicalization:
https://rise4fun.com/Alive/vTag

If we add that, then we see that this isn't really a subtract fold - any trailing op for the min/max could get simplified when we push the 'not' through the min/max.

[craig.topper]

Looking into the more general fold. Trying to figure out the right magic to avoid an infinite loop.

[lebedev.ri]

Looks ok to me. A note and a remark

• The code is now doing the same thing but either for the LHS or RHS. Is there any way to deduplicate it?
• It looks like we want to more thoroughly (read: in all cases possible) hoist the not ops out like this? @spatel did bring that up before https://reviews.llvm.org/D50301#1191081

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2926–2927 ↗

(On Diff #163158)

We are checking !IsFreeToInvert() because we might be called before we try to actually fold the not into X?
Should probably be a comment.

[craig.topper]

Add comment. Use existing createMinMax helper to shorten some code.

[craig.topper]

I did briefly look at always hoisting it, but it potentially changes the critical path so I'm playing it safe.

[lebedev.ri]

In D51398#1218200, @craig.topper wrote:

I did briefly look at always hoisting it, but it potentially changes the critical path so I'm playing it safe.

I wasn't talking about this case specifically, but more in general.

[spatel]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2926 ↗

(On Diff #163168)

simplied -> simplified

2934 ↗

(On Diff #163168)

simplied -> simplified

lib/Transforms/InstCombine/InstCombineSelect.cpp

1821–1822 ↗

(On Diff #163168)

Update this comment to match the new logic.

1842 ↗

(On Diff #163168)

Extra whitespace?

test/Transforms/InstCombine/select.ll

1332 ↗

(On Diff #163168)

Update comment for new form.

test/Transforms/InstCombine/select_meta.ll

197 ↗

(On Diff #163168)

cc @davidxl
This is the same compare that we started with, so I think branch weight metadata should transfer as-is.
If we drop metadata in this patch, it's possible we could see perf regressions, so we should try to get this right.

test/Transforms/InstCombine/sub.ll

1061 ↗

(On Diff #163002)

Given the inf-loop potential, there's even more reason to get these committed before the code patch - don't want to lose those in case of revert.

[davidxl]

test/Transforms/InstCombine/select_meta.ll

197 ↗

(On Diff #163168)

correct, the profile data should not change and be transferred as is.

[craig.topper]

Address review comments.

Not sure about the metadata copying. I'm not sure if I can rely on LHS and RHS to be in the same order as the original select.

[spatel]

In D51398#1218774, @craig.topper wrote:

Address review comments.

Not sure about the metadata copying. I'm not sure if I can rely on LHS and RHS to be in the same order as the original select.

I think that will always be true because LHS/RHS are set based on the original cmp, and we create the new min/max with A/B mapped to LHS/RHS...but some asserts would help (dis)prove it.

Also, repeating Roman's earlier request - we could eliminate the code duplication by making a helper/lambda and reversing the operands in the call?
Something like:

if (Instruction *Not = moveNotAfterMinMax(LHS, RHS))
  return Not;
if (Instruction *Not = moveNotAfterMinMax(RHS, LHS))
  return Not;

But I think that wouldn't preserve the A/B mapping mentioned above. If you see a way to resolve that, that would be nice. LGTM.

[craig.topper]

LHS/RHS are set based on the select operands not the compare operands aren't they?

[craig.topper]

Now with lamdba

[spatel]

In D51398#1219689, @craig.topper wrote:

LHS/RHS are set based on the select operands not the compare operands aren't they?

Yes - sorry, I was looking at the start of matchSelectPattern() rather than matchMinMax(). Do you see a case where we would get the metadata wrong?

We should be canonicalizing harder and maybe that would bypass the question.
Ie, we shouldn't end up with a non-canonical min/max predicate like this:
%c = icmp ult i32 %x, %y
%max = select i1 %c, i32 %y, i32 %x

[davidxl]

the meta data on select tracks the probability the predicate value is 'true'. As long as the predicate expression is not changed, the meta data does not change. Is the transformation doing something else?

[craig.topper]

@davidxl, this transform doesn't really know if its changing the compare predicate because the min/max matching considers (select (icmp slt X, ~C), ~X, C) to be equivalent to (select (icmp sgt ~X, C), ~X, C). And it only returns the select operands to the calling code. So this transform rewrites the icmp, but doesn't know which form the original compare took.

[davidxl]

thanks. In this case, checking if LHS/RHS 's order is swapped is probably needed.

[craig.topper]

So does this look ok?

[davidxl]

The meta data update code looks fine to me.

lib/Transforms/InstCombine/InstCombineSelect.cpp

1825 ↗

(On Diff #163384)

Can the operands_swapped passed as an argument?

[craig.topper]

Pass a parameter to the lambda to indicate the LHS/RHS are swapped. Check this with an assert.

[davidxl]

The MD part LGTM

[spatel]

LGTM

llvm/trunk/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

Instruction *InstCombiner::visitXor(BinaryOperator &I) {
   //   %cmp2 = icmp slt %x, %noty
   //   %res = select i1 %cmp2, i32 %x, i32 %noty
   //
   // Same is applicable for smin/umax/umin.
   if (match(Op1, m_AllOnes()) && Op0->hasOneUse()) {
     Value *LHS, *RHS;
     SelectPatternFlavor SPF = matchSelectPattern(Op0, LHS, RHS).Flavor;
     if (SelectPatternResult::isMinOrMax(SPF)) {
-      Value *X;
-      if (match(RHS, m_Not(m_Value(X))))
-        std::swap(RHS, LHS);
-
-      if (match(LHS, m_Not(m_Value(X)))) {
+      // It's possible we get here before the not has been simplified, so make
+      // sure the input to the not isn't freely invertible.
+      if (match(LHS, m_Not(m_Value(X))) && !IsFreeToInvert(X, X->hasOneUse())) {
         Value *NotY = Builder.CreateNot(RHS);
         return SelectInst::Create(
             Builder.CreateICmp(getInverseMinMaxPred(SPF), X, NotY), X, NotY);
       }
+
+      // It's possible we get here before the not has been simplified, so make
+      // sure the input to the not isn't freely invertible.
+      if (match(RHS, m_Not(m_Value(Y))) && !IsFreeToInvert(Y, Y->hasOneUse())) {
+        Value *NotX = Builder.CreateNot(LHS);
+        return SelectInst::Create(
+            Builder.CreateICmp(getInverseMinMaxPred(SPF), NotX, Y), NotX, Y);
+      }
     }
   }
 
   if (Instruction *NewXor = sinkNotIntoXor(I, Builder))
     return NewXor;
 
   return nullptr;
 }

llvm/trunk/lib/Transforms/InstCombine/InstCombineSelect.cpp

if (SelectPatternResult::isMinOrMax(SPF)) {
         if (!IsCastNeeded)
           return replaceInstUsesWith(SI, NewSI);
 
         Value *NewCast = Builder.CreateCast(CastOp, NewSI, SelType);
         return replaceInstUsesWith(SI, NewCast);
       }
 
       // MAX(~a, ~b) -> ~MIN(a, b)
+      // MAX(~a, C)  -> ~MIN(a, ~C)
       // MIN(~a, ~b) -> ~MAX(a, b)
-      Value *A, *B;
-      if (match(LHS, m_Not(m_Value(A))) && match(RHS, m_Not(m_Value(B))) &&
-          (!LHS->hasNUsesOrMore(3) || !RHS->hasNUsesOrMore(3))) {
-        CmpInst::Predicate InvertedPred = getInverseMinMaxPred(SPF);
-        Value *InvertedCmp = Builder.CreateICmp(InvertedPred, A, B);
-        Value *NewSel = Builder.CreateSelect(InvertedCmp, A, B);
-        return BinaryOperator::CreateNot(NewSel);
+      // MIN(~a, C)  -> ~MAX(a, ~C)
+      auto moveNotAfterMinMax = [&](Value *X, Value *Y,
+                                    bool Swapped) -> Instruction * {
+        Value *A;
+        if (match(X, m_Not(m_Value(A))) && !X->hasNUsesOrMore(3) &&
+            // Passing false to only consider m_Not and constants.
+            IsFreeToInvert(Y, false)) {
+          Value *B = Builder.CreateNot(Y);
+          Value *NewMinMax = createMinMax(Builder, getInverseMinMaxFlavor(SPF),
+                                          A, B);
+          // Copy the profile metadata.
+          if (MDNode *MD = SI.getMetadata(LLVMContext::MD_prof)) {
+            cast<SelectInst>(NewMinMax)->setMetadata(LLVMContext::MD_prof, MD);
+            // Swap the metadata if the operands are swapped.
+            if (Swapped) {
+              assert(X == SI.getFalseValue() && Y == SI.getTrueValue() &&
+                     "Unexpected operands.");
+              cast<SelectInst>(NewMinMax)->swapProfMetadata();
+            } else {
+              assert(X == SI.getTrueValue() && Y == SI.getFalseValue() &&
+                     "Unexpected operands.");
+            }
           }
 
+          return BinaryOperator::CreateNot(NewMinMax);
+        }
+
+        return nullptr;
+      };
+
+      if (Instruction *I = moveNotAfterMinMax(LHS, RHS, /*Swapped*/false))
+        return I;
+      if (Instruction *I = moveNotAfterMinMax(RHS, LHS, /*Swapped*/true))
+        return I;
+
       if (Instruction *I = factorizeMinMaxTree(SPF, LHS, RHS, Builder))
         return I;
     }
 
     if (SPF) {
       // MAX(MAX(a, b), a) -> MAX(a, b)
       // MIN(MIN(a, b), a) -> MIN(a, b)
       // MAX(MIN(a, b), a) -> a

llvm/trunk/test/Transforms/InstCombine/max-of-nots.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -instcombine < %s | FileCheck %s
 
 define <2 x i32> @umin_of_nots(<2 x i32> %x, <2 x i32> %y) {
 ; CHECK-LABEL: @umin_of_nots(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt <2 x i32> [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult <2 x i32> [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = select <2 x i1> [[TMP1]], <2 x i32> [[X]], <2 x i32> [[Y]]
 ; CHECK-NEXT:    [[MIN:%.*]] = xor <2 x i32> [[TMP2]], <i32 -1, i32 -1>
 ; CHECK-NEXT:    ret <2 x i32> [[MIN]]
 ;
   %notx = xor <2 x i32> %x, <i32 -1, i32 -1>
   %noty = xor <2 x i32> %y, <i32 -1, i32 -1>
   %cmp = icmp ult <2 x i32> %notx, %noty
   %min = select <2 x i1> %cmp, <2 x i32> %notx, <2 x i32> %noty
   ret <2 x i32> %min
 }
 
 define <2 x i32> @smin_of_nots(<2 x i32> %x, <2 x i32> %y) {
 ; CHECK-LABEL: @smin_of_nots(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt <2 x i32> [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt <2 x i32> [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = select <2 x i1> [[TMP1]], <2 x i32> [[X]], <2 x i32> [[Y]]
 ; CHECK-NEXT:    [[MIN:%.*]] = xor <2 x i32> [[TMP2]], <i32 -1, i32 -1>
 ; CHECK-NEXT:    ret <2 x i32> [[MIN]]
 ;
   %notx = xor <2 x i32> %x, <i32 -1, i32 -1>
   %noty = xor <2 x i32> %y, <i32 -1, i32 -1>
   %cmp = icmp sle <2 x i32> %notx, %noty
   %min = select <2 x i1> %cmp, <2 x i32> %notx, <2 x i32> %noty
   ret <2 x i32> %min
 }
 
 define i32 @compute_min_2(i32 %x, i32 %y) {
 ; CHECK-LABEL: @compute_min_2(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i32 [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i32 [[X]], i32 [[Y]]
 ; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %not_x = sub i32 -1, %x
   %not_y = sub i32 -1, %y
   %cmp = icmp sgt i32 %not_x, %not_y
   %not_min = select i1 %cmp, i32 %not_x, i32 %not_y
   %min = sub i32 -1, %not_min
   ret i32 %min
 }
 
 declare void @extra_use(i8)
 define i8 @umin_not_1_extra_use(i8 %x, i8 %y) {
 ; CHECK-LABEL: @umin_not_1_extra_use(
 ; CHECK-NEXT:    [[NX:%.*]] = xor i8 [[X:%.*]], -1
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i8 [[X]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i8 [[X]], i8 [[Y]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i8 [[X]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i8 [[Y]], i8 [[X]]
 ; CHECK-NEXT:    [[MINXY:%.*]] = xor i8 [[TMP2]], -1
 ; CHECK-NEXT:    call void @extra_use(i8 [[NX]])
 ; CHECK-NEXT:    ret i8 [[MINXY]]
 ;
   %nx = xor i8 %x, -1
   %ny = xor i8 %y, -1
   %cmpxy = icmp ult i8 %nx, %ny
   %minxy = select i1 %cmpxy, i8 %nx, i8 %ny
;
   call void @extra_use(i8 %ny)
   ret i8 %minxy
 }
 
 ; PR35834 - https://bugs.llvm.org/show_bug.cgi?id=35834
 
 define i8 @umin3_not(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @umin3_not(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i8 [[X:%.*]], [[Z:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i8 [[Z:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i8 [[X]], i8 [[Z]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp ugt i8 [[TMP2]], [[Y:%.*]]
 ; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[TMP3]], i8 [[TMP2]], i8 [[Y]]
 ; CHECK-NEXT:    [[R:%.*]] = xor i8 [[R_V]], -1
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %nx = xor i8 %x, -1
   %ny = xor i8 %y, -1
   %nz = xor i8 %z, -1
   %cmpyx = icmp ult i8 %y, %x
   %cmpxz = icmp ult i8 %nx, %nz
   %minxz = select i1 %cmpxz, i8 %nx, i8 %nz
   %cmpyz = icmp ult i8 %ny, %nz
   %minyz = select i1 %cmpyz, i8 %ny, i8 %nz
   %r = select i1 %cmpyx, i8 %minxz, i8 %minyz
   ret i8 %r
 }
 
 ; PR35875 - https://bugs.llvm.org/show_bug.cgi?id=35875
 
 define i8 @umin3_not_more_uses(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @umin3_not_more_uses(
 ; CHECK-NEXT:    [[NX:%.*]] = xor i8 [[X:%.*]], -1
 ; CHECK-NEXT:    [[NY:%.*]] = xor i8 [[Y:%.*]], -1
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i8 [[X]], [[Z:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i8 [[X]], i8 [[Z]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i8 [[X]], [[Z:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i8 [[Z]], i8 [[X]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp ugt i8 [[TMP2]], [[Y]]
 ; CHECK-NEXT:    [[TMP4:%.*]] = select i1 [[TMP3]], i8 [[TMP2]], i8 [[Y]]
 ; CHECK-NEXT:    [[R:%.*]] = xor i8 [[TMP4]], -1
 ; CHECK-NEXT:    call void @extra_use(i8 [[NX]])
 ; CHECK-NEXT:    call void @extra_use(i8 [[NY]])
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %nx = xor i8 %x, -1
;
   call void @use8(i8 %xmin)
   call void @use8(i8 %ymin)
   call void @use8(i8 %zmin)
   ret void
 }
 
 define i32 @compute_min_3(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @compute_min_3(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i32 [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i32 [[X]], i32 [[Y]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp slt i32 [[TMP2]], [[Z:%.*]]
 ; CHECK-NEXT:    [[TMP4:%.*]] = select i1 [[TMP3]], i32 [[TMP2]], i32 [[Z]]
 ; CHECK-NEXT:    ret i32 [[TMP4]]
 ;
   %not_x = sub i32 -1, %x
   %not_y = sub i32 -1, %y
   %not_z = sub i32 -1, %z

 
 declare void @fake_use(i32)
 
 define i32 @compute_min_pessimization(i32 %x, i32 %y) {
 ; CHECK-LABEL: @compute_min_pessimization(
 ; CHECK-NEXT:    [[NOT_VALUE:%.*]] = sub i32 3, [[X:%.*]]
 ; CHECK-NEXT:    call void @fake_use(i32 [[NOT_VALUE]])
 ; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[X]], -4
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt i32 [[TMP1]], [[Y:%.*]]
-; CHECK-NEXT:    [[MIN:%.*]] = select i1 [[TMP2]], i32 [[Y]], i32 [[TMP1]]
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp slt i32 [[TMP1]], [[Y:%.*]]
+; CHECK-NEXT:    [[MIN:%.*]] = select i1 [[TMP2]], i32 [[TMP1]], i32 [[Y]]
 ; CHECK-NEXT:    ret i32 [[MIN]]
 ;
   %not_value = sub i32 3, %x
   call void @fake_use(i32 %not_value)
   %not_y = sub i32 -1, %y
   %cmp = icmp sgt i32 %not_value, %not_y
   %not_min = select i1 %cmp, i32 %not_value, i32 %not_y
   %min = sub i32 -1, %not_min

llvm/trunk/test/Transforms/InstCombine/select.ll

 ; CHECK-NEXT:    ret i32 [[SEL]]
 ;
   %cmp = icmp eq i32 %x, 2147483647
   %add = add nsw i32 %x, 1
   %sel = select i1 %cmp, i32 -2147483648, i32 %add
   ret i32 %sel
 }
 
-; max(max(~a, -1), -1) --> max(~a, -1)
+; max(max(~a, -1), -1) --> ~min(a, 0)
 
 define i32 @PR27137(i32 %a) {
 ; CHECK-LABEL: @PR27137(
-; CHECK-NEXT:    [[NOT_A:%.*]] = xor i32 [[A:%.*]], -1
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i32 [[NOT_A]], -1
-; CHECK-NEXT:    [[S1:%.*]] = select i1 [[TMP1]], i32 [[NOT_A]], i32 -1
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i32 [[A:%.*]], 0
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i32 [[A]], i32 0
+; CHECK-NEXT:    [[S1:%.*]] = xor i32 [[TMP2]], -1
 ; CHECK-NEXT:    ret i32 [[S1]]
 ;
   %not_a = xor i32 %a, -1
   %c0 = icmp slt i32 %a, 0
   %s0 = select i1 %c0, i32 %not_a, i32 -1
   %c1 = icmp sgt i32 %s0, -1
   %s1 = select i1 %c1, i32 %s0, i32 -1
   ret i32 %s1

llvm/trunk/test/Transforms/InstCombine/select_meta.ll

 ;
   %cmp = icmp slt i32 %x, 36
   %cond = select i1 %cmp, i32 36, i32 %x, !prof !1
   %cmp3 = icmp slt i32 %cond, 75
   %retval = select i1 %cmp3, i32 75, i32 %cond, !prof !2
   ret i32 %retval
 }
 
-; The compare should change, but the metadata remains the same because the select operands are not swapped.
+; The xor is moved after the select. The metadata remains the same because the select operands are not swapped only inverted.
 define i32 @smin1(i32 %x) {
 ; CHECK-LABEL: @smin1(
-; CHECK-NEXT:    [[NOT_X:%.*]] = xor i32 %x, -1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[NOT_X]], -1
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i32 [[NOT_X]], i32 -1, !prof ![[$MD1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i32 [[X:%.*]], 0
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i32 [[X]], i32 0, !prof ![[$MD1]]
+; CHECK-NEXT:    [[SEL:%.*]] = xor i32 [[TMP2]], -1
 ; CHECK-NEXT:    ret i32 [[SEL]]
 ;
   %not_x = xor i32 %x, -1
   %cmp = icmp sgt i32 %x, 0
   %sel = select i1 %cmp, i32 %not_x, i32 -1, !prof !1
   ret i32 %sel
 }
 
-; The compare should change, and the metadata is swapped because the select operands are swapped.
+; The compare should change, and the metadata is swapped because the select operands are swapped and inverted.
 define i32 @smin2(i32 %x) {
 ; CHECK-LABEL: @smin2(
-; CHECK-NEXT:    [[NOT_X:%.*]] = xor i32 %x, -1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[NOT_X]], -1
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i32 [[NOT_X]], i32 -1, !prof ![[$MD3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i32 [[X:%.*]], 0
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i32 [[X]], i32 0, !prof ![[$MD3]]
+; CHECK-NEXT:    [[SEL:%.*]] = xor i32 [[TMP2]], -1
 ; CHECK-NEXT:    ret i32 [[SEL]]
 ;
   %not_x = xor i32 %x, -1
   %cmp = icmp slt i32 %x, 0
   %sel = select i1 %cmp, i32 -1, i32 %not_x, !prof !1
   ret i32 %sel
 }
 
-; The compare should change, but the metadata remains the same because the select operands are not swapped.
+; The xor is moved after the select. The metadata remains the same because the select operands are not swapped only inverted.
 define i32 @smax1(i32 %x) {
 ; CHECK-LABEL: @smax1(
-; CHECK-NEXT:    [[NOT_X:%.*]] = xor i32 %x, -1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[NOT_X]], -1
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i32 [[NOT_X]], i32 -1, !prof ![[$MD1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i32 [[X:%.*]], 0
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i32 [[X]], i32 0, !prof ![[$MD1]]
+; CHECK-NEXT:    [[SEL:%.*]] = xor i32 [[TMP2]], -1
 ; CHECK-NEXT:    ret i32 [[SEL]]
 ;
   %not_x = xor i32 %x, -1
   %cmp = icmp slt i32 %x, 0
   %sel = select i1 %cmp, i32 %not_x, i32 -1, !prof !1
   ret i32 %sel
 }
 
-; The compare should change, and the metadata is swapped because the select operands are swapped.
+; The compare should change, and the metadata is swapped because the select operands are swapped and inverted.
 define i32 @smax2(i32 %x) {
 ; CHECK-LABEL: @smax2(
-; CHECK-NEXT:    [[NOT_X:%.*]] = xor i32 %x, -1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[NOT_X]], -1
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i32 [[NOT_X]], i32 -1, !prof ![[$MD3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i32 [[X:%.*]], 0
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i32 [[X]], i32 0, !prof ![[$MD3]]
+; CHECK-NEXT:    [[SEL:%.*]] = xor i32 [[TMP2]], -1
 ; CHECK-NEXT:    ret i32 [[SEL]]
 ;
   %not_x = xor i32 %x, -1
   %cmp = icmp sgt i32 %x, 0
   %sel = select i1 %cmp, i32 -1, i32 %not_x, !prof !1
   ret i32 %sel
 }
 

llvm/trunk/test/Transforms/InstCombine/sub.ll

;
   %C = shl <2 x i32> %B, <i32 1, i32 1>
   %D = sub <2 x i32> <i32 2, i32 2>, %C
   ret <2 x i32> %D
 }
 
 ; FIXME: Transform (neg (max ~X, C)) -> ((min X, ~C) + 1). Same for min.
 define i32 @test64(i32 %x) {
 ; CHECK-LABEL: @test64(
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[X:%.*]], -1
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt i32 [[TMP1]], -256
-; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i32 [[TMP1]], i32 -256
-; CHECK-NEXT:    [[RES:%.*]] = sub i32 0, [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i32 [[X:%.*]], 255
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i32 [[X]], i32 255
+; CHECK-NEXT:    [[RES:%.*]] = add i32 [[TMP2]], 1
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
   %1 = xor i32 %x, -1
   %2 = icmp sgt i32 %1, -256
   %3 = select i1 %2, i32 %1, i32 -256
   %res = sub i32 0, %3
   ret i32 %res
 }
 
 define i32 @test65(i32 %x) {
 ; CHECK-LABEL: @test65(
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[X:%.*]], -1
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp slt i32 [[TMP1]], 255
-; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i32 [[TMP1]], i32 255
-; CHECK-NEXT:    [[RES:%.*]] = sub i32 0, [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i32 [[X:%.*]], -256
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i32 [[X]], i32 -256
+; CHECK-NEXT:    [[RES:%.*]] = add i32 [[TMP2]], 1
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
   %1 = xor i32 %x, -1
   %2 = icmp slt i32 %1, 255
   %3 = select i1 %2, i32 %1, i32 255
   %res = sub i32 0, %3
   ret i32 %res
 }
 
 define i32 @test66(i32 %x) {
 ; CHECK-LABEL: @test66(
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[X:%.*]], -1
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ugt i32 [[TMP1]], 100
-; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i32 [[TMP1]], i32 100
-; CHECK-NEXT:    [[RES:%.*]] = sub i32 0, [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[X:%.*]], -101
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i32 [[X]], i32 -101
+; CHECK-NEXT:    [[RES:%.*]] = add i32 [[TMP2]], 1
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
   %1 = xor i32 %x, -1
   %2 = icmp ugt i32 %1, 100
   %3 = select i1 %2, i32 %1, i32 100
   %res = sub i32 0, %3
   ret i32 %res
 }
 
 define i32 @test67(i32 %x) {
 ; CHECK-LABEL: @test67(
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[X:%.*]], -1
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i32 [[TMP1]], -101
-; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i32 [[TMP1]], i32 -101
-; CHECK-NEXT:    [[RES:%.*]] = sub i32 0, [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i32 [[X:%.*]], 100
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i32 [[X]], i32 100
+; CHECK-NEXT:    [[RES:%.*]] = add i32 [[TMP2]], 1
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
   %1 = xor i32 %x, -1
   %2 = icmp ult i32 %1, -101
   %3 = select i1 %2, i32 %1, i32 -101
   %res = sub i32 0, %3
   ret i32 %res
 }
 
 ; Check splat vectors too
 define <2 x i32> @test68(<2 x i32> %x) {
 ; CHECK-LABEL: @test68(
-; CHECK-NEXT:    [[TMP1:%.*]] = xor <2 x i32> [[X:%.*]], <i32 -1, i32 -1>
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt <2 x i32> [[TMP1]], <i32 -256, i32 -256>
-; CHECK-NEXT:    [[TMP3:%.*]] = select <2 x i1> [[TMP2]], <2 x i32> [[TMP1]], <2 x i32> <i32 -256, i32 -256>
-; CHECK-NEXT:    [[RES:%.*]] = sub <2 x i32> zeroinitializer, [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt <2 x i32> [[X:%.*]], <i32 255, i32 255>
+; CHECK-NEXT:    [[TMP2:%.*]] = select <2 x i1> [[TMP1]], <2 x i32> [[X]], <2 x i32> <i32 255, i32 255>
+; CHECK-NEXT:    [[RES:%.*]] = add <2 x i32> [[TMP2]], <i32 1, i32 1>
 ; CHECK-NEXT:    ret <2 x i32> [[RES]]
 ;
   %1 = xor <2 x i32> %x, <i32 -1, i32 -1>
   %2 = icmp sgt <2 x i32> %1, <i32 -256, i32 -256>
   %3 = select <2 x i1> %2, <2 x i32> %1, <2 x i32> <i32 -256, i32 -256>
   %res = sub <2 x i32> zeroinitializer, %3
   ret <2 x i32> %res
 }
 
 ; And non-splat constant vectors.
 define <2 x i32> @test69(<2 x i32> %x) {
 ; CHECK-LABEL: @test69(
-; CHECK-NEXT:    [[TMP1:%.*]] = xor <2 x i32> [[X:%.*]], <i32 -1, i32 -1>
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt <2 x i32> [[TMP1]], <i32 -256, i32 -128>
-; CHECK-NEXT:    [[TMP3:%.*]] = select <2 x i1> [[TMP2]], <2 x i32> [[TMP1]], <2 x i32> <i32 -256, i32 -128>
-; CHECK-NEXT:    [[RES:%.*]] = sub <2 x i32> zeroinitializer, [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt <2 x i32> [[X:%.*]], <i32 255, i32 127>
+; CHECK-NEXT:    [[TMP2:%.*]] = select <2 x i1> [[TMP1]], <2 x i32> [[X]], <2 x i32> <i32 255, i32 127>
+; CHECK-NEXT:    [[RES:%.*]] = add <2 x i32> [[TMP2]], <i32 1, i32 1>
 ; CHECK-NEXT:    ret <2 x i32> [[RES]]
 ;
   %1 = xor <2 x i32> %x, <i32 -1, i32 -1>
   %2 = icmp sgt <2 x i32> %1, <i32 -256, i32 -128>
   %3 = select <2 x i1> %2, <2 x i32> %1, <2 x i32> <i32 -256, i32 -128>
   %res = sub <2 x i32> zeroinitializer, %3
   ret <2 x i32> %res
 }

llvm/trunk/test/Transforms/InstCombine/xor.ll

;
   %umin = select i1 %cmp1, i32 %notx, i32 %y
   %res = xor i32 %umin, -1
   ret i32 %res
 }
 
 define i32 @test44(i32 %x, i32 %y) {
 ; CHECK-LABEL: @test44(
 ; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 -4, [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i32 [[TMP1]], [[X:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[TMP2]], i32 [[X]], i32 [[TMP1]]
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ugt i32 [[TMP1]], [[X:%.*]]
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[TMP2]], i32 [[TMP1]], i32 [[X]]
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
   %z = add i32 %y, 3 ; thwart complexity-based canonicalization
   %notx = xor i32 %x, -1
   %cmp1 = icmp ult i32 %z, %notx
   %umin = select i1 %cmp1, i32 %z, i32 %notx
   %res = xor i32 %umin, -1
   ret i32 %res
 }
 
 define i32 @test45(i32 %x, i32 %y) {
 ; CHECK-LABEL: @test45(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i32 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i32 [[Y]], i32 [[X]]
 ; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %z = xor i32 %y, -1
   %notx = xor i32 %x, -1
   %cmp1 = icmp ult i32 %z, %notx
   %umin = select i1 %cmp1, i32 %z, i32 %notx
   %res = xor i32 %umin, -1