This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] try to canonicalize xor-of-icmps to and-of-icmps
ClosedPublic

Authored by spatel on May 18 2017, 4:41 PM.

Details

Summary

We have a large portfolio of folds for and-of-icmps and or-of-icmps in InstSimplify and InstCombine, but hardly anything for xor-of-icmps.
Rather than trying to rethink and translate all of those folds, we can use the truth table definition of xor:

X ^ Y --> (X | Y) & !(X & Y)

...to see if we can convert the xor to and/or and then use the existing folds.

I find that visualizing the sets for xor (https://en.wikipedia.org/wiki/Symmetric_difference) is just plain harder than and/or...and maybe that's why these folds don't exist yet. :)

I've been using Alive to verify that we're doing the correct transforms in these cases:
http://rise4fun.com/Alive/J9v

Diff Detail

Event Timeline

spatel created this revision.May 18 2017, 4:41 PM
efriedma edited edge metadata.May 30 2017, 4:08 PM

This approach seems relatively expensive and not very flexible... e.g. we can't even transform "(x < 5) ^ (x == 4)". Is there really no better way to catch simple cases?

spatel added a comment.Jun 2 2017, 7:12 AM

This approach seems relatively expensive and not very flexible... e.g. we can't even transform "(x < 5) ^ (x == 4)". Is there really no better way to catch simple cases?

Can you provide an IR example of the case you're thinking of? Did I mistranslate the comment above?

$ cat xoricmps.ll 
define i1 @xor_icmps_signed(i8 %x) {
  %cmp1 = icmp slt i8 %x, 5
  %cmp2 = icmp eq i8 %x, 4
  %r = xor i1 %cmp1, %cmp2
  ret i1 %r
}

define i1 @xor_icmps_unsigned(i8 %x) {
  %cmp1 = icmp ult i8 %x, 5
  %cmp2 = icmp eq i8 %x, 4
  %r = xor i1 %cmp1, %cmp2
  ret i1 %r
}

$ ./opt -instcombine xoricmps.ll -S

define i1 @xor_icmps_signed(i8 %x) {
  %1 = icmp slt i8 %x, 4
  ret i1 %1
}

define i1 @xor_icmps_unsigned(i8 %x) {
  %1 = icmp ult i8 %x, 4
  ret i1 %1
}
spatel updated this revision to Diff 101207.Jun 2 2017, 7:22 AM

Patch updated:
No code changes, but there was a bug in a code comment that might have caused confusion. Also, updated the 'FIXME' comments in the test file.

efriedma accepted this revision.Jun 19 2017, 1:39 PM

Sorry about the delayed review.

The particular case I cited works... I didn't really think it through.

This still seems like an expensive way to handle these transforms, but I guess that's unlikely to matter in practice.

LGTM.

This revision is now accepted and ready to land.Jun 19 2017, 1:39 PM

Sorry about the delayed review.

No problem - thanks for all of your help reviewing my patches!

The particular case I cited works... I didn't really think it through.

This still seems like an expensive way to handle these transforms, but I guess that's unlikely to matter in practice.

Yep - I can't imagine there's a whole lot of xor'ing of icmps out there, but since this showed up in a bug report, we know there's at least some in existence. I think the alternative would be to add specific matchers for the patterns seen here. In the end, I think that would either be more expensive (because we'd have to duplicate lots of the matcher code that exists for and/or) or have incomplete optimization powers vs. what we do for the other logic ops.

This revision was automatically updated to reflect the committed changes.