[InstCombine] De Morgan: sink 'not' into 'xor' (PR38446)

[lebedev.ri]

Summary

https://rise4fun.com/Alive/IT3

Comes up in the [most ugliest] signed int -> signed char case of
-fsanitize=implicit-conversion (https://reviews.llvm.org/D50250)
Previously, we were stuck with not:

old.ll2 KBDownload

But now we are able to completely get rid of it:

new.ll2 KBDownload

(FIXME: why are we loosing the metadata? that seems wrong/strange.)

Not sure if we want to do it always, or only when it is free to invert?

[lebedev.ri]

Hmm, actually looking at that motivational IR (https://godbolt.org/g/4XqSJU) in souper,
it seems it should eventually fold down just into https://rise4fun.com/Alive/W1b
That will be fun.

[lebedev.ri]

And the unsigned int -> signed char case simplifies, too.
https://rise4fun.com/Alive/2W8 <- is that too specific for instcombine?

[spatel]

I may be starting a substantial yak shaving with the inline question, but I wonder if it wouldn't be better to canonicalize with the 'not' after the 'xor' (ie, the inverse of this patch). I don't have a motivating example yet, but that just seems more natural rather than semi-arbitralily choosing an operand to invert.

test/Transforms/InstCombine/set.ll

132–137 ↗

(On Diff #159203)

I don't see any value in this transform (either to the old version or the new).
Can we refine the existing canonicalization to avoid this?
(This may raise questions about whether the existing general canonicalizations are actually opposite of what they should be?)

[lebedev.ri]

In D50301#1191081, @spatel wrote:

I may be starting a substantial yak shaving with the inline question, but I wonder if it wouldn't be better to canonicalize with the 'not' after the 'xor' (ie, the inverse of this patch). I don't have a motivating example yet, but that just seems more natural rather than semi-arbitralily choosing an operand to invert.

Quite possibly. I don't know what the right thing to do here. See inline comments.

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2467–2469 ↗

(On Diff #159203)

If we do not want to do this always, then this can be:

if (IsFreeToInvert(X, X->hasOneUse()))
  // ok
else if (IsFreeToInvert(Y, Y->hasOneUse()))
  std::swap(X, Y);
else
  return nullptr; // Only transform if we will be able to get rid of 'not'.

test/Transforms/InstCombine/demorgan-sink-not-into-xor.ll

37–49 ↗

(On Diff #159203)

I don't know about the other cases, but do you agree that this is an improvement?
This is the motivational case here, the only one i care about here.

[spatel]

test/Transforms/InstCombine/demorgan-sink-not-into-xor.ll

37–49 ↗

(On Diff #159203)

Yes, that's obviously better since it folds the 'not' into the cmp. If you want to limit the transform, so we just get that case, that works for me. We can open the can of worms another day. :)

[lebedev.ri]

Limit transform to only the free-to-invert cases.

[spatel]

LGTM

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2464 ↗

(On Diff #159652)

The one-use here is not strictly necessary? There are questions about how to best deal with inverted compares, so I don't think it needs to hold this patch up, but it's worth a code comment if I'm seeing it correctly.

This reminded me of the still open:
D35182

[lebedev.ri]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2464 ↗

(On Diff #159652)

Hm. I think it is needed, else we get:

diff --git a/test/Transforms/InstCombine/demorgan-sink-not-into-xor.ll b/test/Transforms/InstCombine/demorgan-sink-not-into-xor.ll
index c378033eef7..c5809b7726b 100644
--- a/test/Transforms/InstCombine/demorgan-sink-not-into-xor.ll
+++ b/test/Transforms/InstCombine/demorgan-sink-not-into-xor.ll
@@ -85,19 +85,20 @@ define i1 @oneuse_easyinvert_0(i8 %y) {
   ret i1 %tmp4
 }
 
 define i1 @oneuse_easyinvert_1(i8 %y) {
 ; CHECK-LABEL: @oneuse_easyinvert_1(
 ; CHECK-NEXT:    [[TMP1:%.*]] = call i1 @gen1()
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp slt i8 [[Y:%.*]], 0
 ; CHECK-NEXT:    [[TMP3:%.*]] = xor i1 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    call void @use1(i1 [[TMP3]])
-; CHECK-NEXT:    [[TMP4:%.*]] = xor i1 [[TMP3]], true
+; CHECK-NEXT:    [[TMP2_NOT:%.*]] = xor i1 [[TMP2]], true
+; CHECK-NEXT:    [[TMP4:%.*]] = xor i1 [[TMP1]], [[TMP2_NOT]]
 ; CHECK-NEXT:    ret i1 [[TMP4]]
 ;
   %tmp1 = call i1 @gen1()
   %tmp2 = icmp slt i8 %y, 0
   %tmp3 = xor i1 %tmp1, %tmp2
   call void @use1(i1 %tmp3)
   %tmp4 = xor i1 %tmp3, true
   ret i1 %tmp4
 }

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

if (D->hasOneUse() && match(M, m_Constant(C))) {
     Value *NotC = Builder.CreateNot(C);
     Value *RHS = Builder.CreateAnd(B, NotC);
     return BinaryOperator::CreateOr(LHS, RHS);
   }
 
   return nullptr;
 }
 
+// Transform
+//   ~(x ^ y)
+// into:
+//   (~x) ^ y
+// or into
+//   x ^ (~y)
+static Instruction *sinkNotIntoXor(BinaryOperator &I,
+                                   InstCombiner::BuilderTy &Builder) {
+  Value *X, *Y;
+  // FIXME: one-use check is not needed in general, but currently we are unable
+  // to fold 'not' into 'icmp', if that 'icmp' has multiple uses. (D35182)
+  if (!match(&I, m_Not(m_OneUse(m_Xor(m_Value(X), m_Value(Y))))))
+    return nullptr;
+
+  // We only want to do the transform if it is free to do.
+  if (IsFreeToInvert(X, X->hasOneUse())) {
+    // Ok, good.
+  } else if (IsFreeToInvert(Y, Y->hasOneUse())) {
+    std::swap(X, Y);
+  } else
+    return nullptr;
+
+  Value *NotX = Builder.CreateNot(X, X->getName() + ".not");
+  return BinaryOperator::CreateXor(NotX, Y, I.getName() + ".demorgan");
+}
+
 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
 // here. We should standardize that construct where it is needed or choose some
 // other way to ensure that commutated variants of patterns are not missed.
 Instruction *InstCombiner::visitXor(BinaryOperator &I) {
   if (Value *V = SimplifyXorInst(I.getOperand(0), I.getOperand(1),
                                  SQ.getWithInstruction(&I)))
     return replaceInstUsesWith(I, V);
 
if (Op0->hasOneUse() && SelectPatternResult::isMinOrMax(SPF) &&
       if (match(LHS, m_Not(m_Value(X)))) {
         Value *NotY = Builder.CreateNot(RHS);
         return SelectInst::Create(
             Builder.CreateICmp(getInverseMinMaxPred(SPF), X, NotY), X, NotY);
       }
     }
   }
 
+  if (Instruction *NewXor = sinkNotIntoXor(I, Builder))
+    return NewXor;
+
   return nullptr;
 }

llvm/trunk/test/Transforms/InstCombine/demorgan-sink-not-into-xor.ll

 ; ============================================================================ ;
 
 ; If the operand is easily-invertible, fold into it.
 declare i1 @gen1()
 
 define i1 @positive_easyinvert(i16 %x, i8 %y) {
 ; CHECK-LABEL: @positive_easyinvert(
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i16 [[X:%.*]], 0
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp slt i8 [[Y:%.*]], 0
-; CHECK-NEXT:    [[TMP3:%.*]] = xor i1 [[TMP2]], [[TMP1]]
-; CHECK-NEXT:    [[TMP4:%.*]] = xor i1 [[TMP3]], true
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt i8 [[Y:%.*]], -1
+; CHECK-NEXT:    [[TMP4:%.*]] = xor i1 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret i1 [[TMP4]]
 ;
   %tmp1 = icmp slt i16 %x, 0
   %tmp2 = icmp slt i8 %y, 0
   %tmp3 = xor i1 %tmp2, %tmp1
   %tmp4 = xor i1 %tmp3, true
   ret i1 %tmp4
 }
 
 define i1 @positive_easyinvert0(i8 %y) {
 ; CHECK-LABEL: @positive_easyinvert0(
 ; CHECK-NEXT:    [[TMP1:%.*]] = call i1 @gen1()
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp slt i8 [[Y:%.*]], 0
-; CHECK-NEXT:    [[TMP3:%.*]] = xor i1 [[TMP2]], [[TMP1]]
-; CHECK-NEXT:    [[TMP4:%.*]] = xor i1 [[TMP3]], true
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt i8 [[Y:%.*]], -1
+; CHECK-NEXT:    [[TMP4:%.*]] = xor i1 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret i1 [[TMP4]]
 ;
   %tmp1 = call i1 @gen1()
   %tmp2 = icmp slt i8 %y, 0
   %tmp3 = xor i1 %tmp2, %tmp1
   %tmp4 = xor i1 %tmp3, true
   ret i1 %tmp4
 }
 
 define i1 @positive_easyinvert1(i8 %y) {
 ; CHECK-LABEL: @positive_easyinvert1(
 ; CHECK-NEXT:    [[TMP1:%.*]] = call i1 @gen1()
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp slt i8 [[Y:%.*]], 0
-; CHECK-NEXT:    [[TMP3:%.*]] = xor i1 [[TMP1]], [[TMP2]]
-; CHECK-NEXT:    [[TMP4:%.*]] = xor i1 [[TMP3]], true
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt i8 [[Y:%.*]], -1
+; CHECK-NEXT:    [[TMP4:%.*]] = xor i1 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret i1 [[TMP4]]
 ;
   %tmp1 = call i1 @gen1()
   %tmp2 = icmp slt i8 %y, 0
   %tmp3 = xor i1 %tmp1, %tmp2
   %tmp4 = xor i1 %tmp3, true
   ret i1 %tmp4
 }