[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

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

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

test/Transforms/InstCombine/sub.ll

1061

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

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

lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (match(Op1, m_AShr(m_Value(A), m_APInt(ShAmt))) &&
     // --> (A < 0) ? -A : A
     Value *Cmp = Builder.CreateICmpSLT(A, ConstantInt::getNullValue(Ty));
     // Copy the nuw/nsw flags from the sub to the negate.
     Value *Neg = Builder.CreateNeg(A, "", I.hasNoUnsignedWrap(),
                                    I.hasNoSignedWrap());
     return SelectInst::Create(Cmp, Neg, A);
   }
 
+  // Fold (neg (min/max ~X, C)) -> (add (min/max X, ~C), 1)
+  if (match(Op0, m_ZeroInt()) && Op1->hasOneUse()) {
+    Value *LHS, *RHS;
+    SelectPatternFlavor SPF = matchSelectPattern(Op1, LHS, RHS).Flavor;
+    if (SelectPatternResult::isMinOrMax(SPF)) {
+      Value *X;
+      if (match(LHS, m_Not(m_Value(X))) &&
+          IsFreeToInvert(RHS, RHS->hasOneUse())) {
+        Value *NotY = Builder.CreateNot(RHS);
+        Value *MinMax = Builder.CreateSelect(
+            Builder.CreateICmp(getInverseMinMaxPred(SPF), X, NotY), X, NotY);
+        Value *One = ConstantInt::get(MinMax->getType(), 1);
+        return BinaryOperator::CreateAdd(MinMax, One);
+      }
+      if (match(RHS, m_Not(m_Value(X))) &&
+          IsFreeToInvert(LHS, LHS->hasOneUse())) {
+        Value *NotY = Builder.CreateNot(RHS);
+        Value *MinMax = Builder.CreateSelect(
+            Builder.CreateICmp(getInverseMinMaxPred(SPF), X, NotY), X, NotY);
+        Value *One = ConstantInt::get(MinMax->getType(), 1);
+        return BinaryOperator::CreateAdd(MinMax, One);
+      }
+    }
+  }
+
   bool Changed = false;
   if (!I.hasNoSignedWrap() && willNotOverflowSignedSub(Op0, Op1, I)) {
     Changed = true;
     I.setHasNoSignedWrap(true);
   }
   if (!I.hasNoUnsignedWrap() && willNotOverflowUnsignedSub(Op0, Op1, I)) {
     Changed = true;
     I.setHasNoUnsignedWrap(true);

test/Transforms/InstCombine/sub.ll

 ; CHECK-NEXT:    [[B:%.*]] = shl <2 x i32> [[A:%.*]], <i32 1, i32 1>
 ; CHECK-NEXT:    ret <2 x i32> [[B]]
 ;
   %B = sub <2 x i32> <i32 1, i32 1>, %A
   %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
 }
+
+; Tests for (neg (max ~X, C)) -> ((min X, ~C) + 1). Same for min.
+define i32 @test64(i32 %x) {
+; CHECK-LABEL: @test64(
+; 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:%.*]] = 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:%.*]] = 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:%.*]] = 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:%.*]] = 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
+}
+
+; Don't transform if the select has an additional use.
+define i32 @test69(i32 %x, i32* %y) {
+; CHECK-LABEL: @test69(
+; 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:    store i32 [[TMP3]], i32* [[Y:%.*]], align 4
+; 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
+  store i32 %3, i32* %y
+  ret i32 %res
+}