Page MenuHomePhabricator

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

Authored by lebedev.ri on Aug 5 2018, 3:23 AM.

Details

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:


But now we are able to completely get rid of it:
(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?

Diff Detail

Repository
rL LLVM

Event Timeline

lebedev.ri created this revision.Aug 5 2018, 3:23 AM

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.

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

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?)

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 added inline comments.Aug 7 2018, 10:26 AM
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 updated this revision to Diff 159652.Aug 8 2018, 1:49 AM
lebedev.ri marked 4 inline comments as done.

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

spatel accepted this revision.Aug 8 2018, 5:41 AM

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

This revision is now accepted and ready to land.Aug 8 2018, 5:41 AM
lebedev.ri added inline comments.Aug 8 2018, 6:24 AM
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
 }
This revision was automatically updated to reflect the committed changes.