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

[spatel]

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

[spatel]

Ping.

[efriedma]

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]

In D33342#768301, @efriedma wrote:

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]

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.

[spatel]

Ping * 2.

[spatel]

Ping * 3.

[efriedma]

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.

[spatel]

In D33342#784553, @efriedma wrote:

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.

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (LHS->getOperand(0) == RHS->getOperand(0) &&
       // (icmp1 A, B) ^ (icmp2 A, B) --> (icmp3 A, B)
       Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1);
       unsigned Code = getICmpCode(LHS) ^ getICmpCode(RHS);
       bool isSigned = LHS->isSigned() || RHS->isSigned();
       return getNewICmpValue(isSigned, Code, Op0, Op1, Builder);
     }
   }
 
+  // Instead of trying to imitate the folds for and/or, decompose this 'xor'
+  // into those logic ops and try to turn this into an and-of-icmps because we
+  // have many folds for that pattern.
+  //
+  // This is based on a truth table definition of xor:
+  // X ^ Y --> (X | Y) & !(X & Y)
+  if (Value *OrICmp = SimplifyBinOp(Instruction::Or, LHS, RHS, SQ)) {
+    // TODO: If OrICmp is true, then the definition of xor simplifies to !(X&Y).
+    // TODO: If OrICmp is false, the whole thing is false (InstSimplify?).
+    if (Value *AndICmp = SimplifyBinOp(Instruction::And, LHS, RHS, SQ)) {
+      // TODO: Independently handle cases where the 'and' side is a constant.
+      if (OrICmp == LHS && AndICmp == RHS && RHS->hasOneUse()) {
+        // (LHS | RHS) & !(LHS & RHS) --> LHS & !RHS
+        RHS->setPredicate(RHS->getInversePredicate());
+        return Builder->CreateAnd(LHS, RHS);
+      }
+      if (OrICmp == RHS && AndICmp == LHS && LHS->hasOneUse()) {
+        // !(LHS & RHS) & (LHS | RHS) --> !LHS & !RHS
+        LHS->setPredicate(LHS->getInversePredicate());
+        return Builder->CreateAnd(LHS, RHS);
+      }
+    }
+  }
+
   return nullptr;
 }
 
 // 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) {
   bool Changed = SimplifyAssociativeOrCommutative(I);

test/Transforms/InstCombine/set.ll

;
   %and = and i1 %b, %notc
   ret i1 %and
 }
 
 ; FIXME: This is equivalent to the previous test.
 
 define i1 @xor_of_icmps(i64 %a) {
 ; CHECK-LABEL: @xor_of_icmps(
-; CHECK-NEXT:    [[B:%.*]] = icmp sgt i64 %a, 0
-; CHECK-NEXT:    [[C:%.*]] = icmp eq i64 %a, 1
-; CHECK-NEXT:    [[XOR:%.*]] = xor i1 [[C]], [[B]]
-; CHECK-NEXT:    ret i1 [[XOR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i64 %a, 1
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %b = icmp sgt i64 %a, 0
   %c = icmp eq i64 %a, 1
   %xor = xor i1 %c, %b
   ret i1 %xor
 }
 
 ; FIXME: This is also equivalent to the previous test.
 
 define i1 @xor_of_icmps_commute(i64 %a) {
 ; CHECK-LABEL: @xor_of_icmps_commute(
-; CHECK-NEXT:    [[B:%.*]] = icmp sgt i64 %a, 0
-; CHECK-NEXT:    [[C:%.*]] = icmp eq i64 %a, 1
-; CHECK-NEXT:    [[XOR:%.*]] = xor i1 [[B]], [[C]]
-; CHECK-NEXT:    ret i1 [[XOR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i64 %a, 1
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %b = icmp sgt i64 %a, 0
   %c = icmp eq i64 %a, 1
   %xor = xor i1 %b, %c
   ret i1 %xor
 }
 
 ; FIXME: This is (a != 5).
;
   %xor = xor i1 %b, %c
   ret i1 %xor
 }
 
 ; https://bugs.llvm.org/show_bug.cgi?id=2844
 
 define i32 @PR2844(i32 %x) {
 ; CHECK-LABEL: @PR2844(
-; CHECK-NEXT:    [[A:%.*]] = icmp eq i32 %x, 0
+; CHECK-NEXT:    [[A:%.*]] = icmp ne i32 %x, 0
 ; CHECK-NEXT:    [[B:%.*]] = icmp sgt i32 %x, -638208502
-; CHECK-NEXT:    [[NOT_OR:%.*]] = xor i1 [[A]], [[B]]
-; CHECK-NEXT:    [[SEL:%.*]] = zext i1 [[NOT_OR]] to i32
+; CHECK-NEXT:    [[TMP1:%.*]] = and i1 [[A]], [[B]]
+; CHECK-NEXT:    [[SEL:%.*]] = zext i1 [[TMP1]] to i32
 ; CHECK-NEXT:    ret i32 [[SEL]]
 ;
   %A = icmp eq i32 %x, 0
   %B = icmp slt i32 %x, -638208501
   %or = or i1 %A, %B
   %sel = select i1 %or, i32 0, i32 1
   ret i32 %sel
 }