[InstCombine] add fold (X > C - 1) ^ (X < C + 1) --> X != C

[Chenbing.Zheng]

Summary

https://alive2.llvm.org/ce/z/c_rBaq

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

3216

Did you make a general proof for this on alive2? Please add a link to the patch summary. I don't think this will be correct if the "+2" overflows?

[Chenbing.Zheng]

address comments and add tests
https://alive2.llvm.org/ce/z/c_rBaq

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

3226

There is no check that LHS0 is the same as RHS0. Please correct that and add a test similar to this:

define i1 @xor_of_icmps_to_ne_no_common_operand(i64 %a, i64 %z) {
  %b = icmp sgt i64 %z, 4
  %c = icmp slt i64 %a, 6
  %xor = xor i1 %b, %c
  ret i1 %xor
}

llvm/test/Transforms/InstCombine/set.ll

259

Similar to my comment from D129726:
You may pre-commit tests in "NFC" patches. You can push that kind of patch without pre-commit review on Phabricator. It would be good to test at least 2 more code patterns:

1. Use a vector type with "splat" constants.
2. Add extra uses of the icmps.

[Chenbing.Zheng]

address comment

[spatel]

LGTM - I think this could be implemented more generally using ConstantRange, but we already get the inverted pattern because the constants are equal in that case, so handling this specific pattern is ok.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (match(LHS1, m_APInt(LC)) && match(RHS1, m_APInt(RC)) &&
       LHS0->getType()->isIntOrIntVectorTy() &&
       (LHS->hasOneUse() || RHS->hasOneUse())) {
     // Convert xor of signbit tests to signbit test of xor'd values:
     // (X > -1) ^ (Y > -1) --> (X ^ Y) < 0
     // (X <  0) ^ (Y <  0) --> (X ^ Y) < 0
     // (X > -1) ^ (Y <  0) --> (X ^ Y) > -1
     // (X <  0) ^ (Y > -1) --> (X ^ Y) > -1
     bool TrueIfSignedL, TrueIfSignedR;
     if (isSignBitCheck(PredL, *LC, TrueIfSignedL) &&
         isSignBitCheck(PredR, *RC, TrueIfSignedR)) {
       Value *XorLR = Builder.CreateXor(LHS0, RHS0);
       return TrueIfSignedL == TrueIfSignedR ? Builder.CreateIsNeg(XorLR) :
                                               Builder.CreateIsNotNeg(XorLR);
     }
+
+    // (X > C) ^ (X < C + 2) --> X != C + 1
+    // (X < C + 2) ^ (X > C) --> X != C + 1
+    // Considering the correctness of this pattern, we should avoid that C is
+    // non-negative and C + 2 is negative, although it will be matched by other
+    // patterns.
+    const APInt *C1, *C2;
+    if ((PredL == CmpInst::ICMP_SGT && match(LHS1, m_APInt(C1)) &&
+         PredR == CmpInst::ICMP_SLT && match(RHS1, m_APInt(C2))) ||
+        (PredL == CmpInst::ICMP_SLT && match(LHS1, m_APInt(C2)) &&
+         PredR == CmpInst::ICMP_SGT && match(RHS1, m_APInt(C1))))
+      if (LHS0 == RHS0 && *C1 + 2 == *C2 &&
+          (C1->isNegative() || C2->isNonNegative()))
+        return Builder.CreateICmpNE(LHS0,
+                                    ConstantInt::get(LHS0->getType(), *C1 + 1));
   }
 
   // Instead of trying to imitate the folds for and/or, decompose this 'xor'
   // into those logic ops. That is, 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)

llvm/test/Transforms/InstCombine/set.ll

 ; 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).
-
 define i1 @xor_of_icmps_to_ne(i64 %a) {
 ; CHECK-LABEL: @xor_of_icmps_to_ne(
-; CHECK-NEXT:    [[B:%.*]] = icmp sgt i64 [[A:%.*]], 4
-; CHECK-NEXT:    [[C:%.*]] = icmp slt i64 [[A]], 6
-; CHECK-NEXT:    [[XOR:%.*]] = xor i1 [[B]], [[C]]
-; CHECK-NEXT:    ret i1 [[XOR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i64 [[A:%.*]], 5
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %b = icmp sgt i64 %a, 4
   %c = icmp slt i64 %a, 6
   %xor = xor i1 %b, %c
   ret i1 %xor
 }
 
 define i1 @xor_of_icmps_to_ne_commute(i64 %a) {
 ; CHECK-LABEL: @xor_of_icmps_to_ne_commute(
-; CHECK-NEXT:    [[C:%.*]] = icmp sgt i64 [[A:%.*]], 4
-; CHECK-NEXT:    [[B:%.*]] = icmp slt i64 [[A]], 6
-; CHECK-NEXT:    [[XOR:%.*]] = xor i1 [[B]], [[C]]
-; CHECK-NEXT:    ret i1 [[XOR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i64 [[A:%.*]], 5
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %c = icmp sgt i64 %a, 4
   %b = icmp slt i64 %a, 6
   %xor = xor i1 %b, %c
   ret i1 %xor
 }
 
 define i1 @xor_of_icmps_neg_to_ne(i64 %a) {
 ; CHECK-LABEL: @xor_of_icmps_neg_to_ne(
-; CHECK-NEXT:    [[B:%.*]] = icmp sgt i64 [[A:%.*]], -6
-; CHECK-NEXT:    [[C:%.*]] = icmp slt i64 [[A]], -4
-; CHECK-NEXT:    [[XOR:%.*]] = xor i1 [[B]], [[C]]
-; CHECK-NEXT:    ret i1 [[XOR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i64 [[A:%.*]], -5
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %b = icmp sgt i64 %a, -6
   %c = icmp slt i64 %a, -4
   %xor = xor i1 %b, %c
   ret i1 %xor
 }
 
 define <2 x i1> @xor_of_icmps_to_ne_vector(<2 x i64> %a) {
 ; CHECK-LABEL: @xor_of_icmps_to_ne_vector(
-; CHECK-NEXT:    [[B:%.*]] = icmp sgt <2 x i64> [[A:%.*]], <i64 4, i64 4>
-; CHECK-NEXT:    [[C:%.*]] = icmp slt <2 x i64> [[A]], <i64 6, i64 6>
-; CHECK-NEXT:    [[XOR:%.*]] = xor <2 x i1> [[B]], [[C]]
-; CHECK-NEXT:    ret <2 x i1> [[XOR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne <2 x i64> [[A:%.*]], <i64 5, i64 5>
+; CHECK-NEXT:    ret <2 x i1> [[TMP1]]
 ;
   %b = icmp sgt <2 x i64> %a, <i64 4, i64 4>
   %c = icmp slt <2 x i64> %a, <i64 6, i64 6>
   %xor = xor <2 x i1> %b, %c
   ret <2 x i1> %xor
 }
 
 define i1 @xor_of_icmps_to_ne_no_common_operand(i64 %a, i64 %z) {
 ; CHECK-LABEL: @xor_of_icmps_to_ne_no_common_operand(
 ; CHECK-NEXT:    [[B:%.*]] = icmp sgt i64 [[Z:%.*]], 4
 ; CHECK-NEXT:    [[C:%.*]] = icmp slt i64 [[A:%.*]], 6
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i1 [[B]], [[C]]
 ; CHECK-NEXT:    ret i1 [[XOR]]
 ;
   %b = icmp sgt i64 %z, 4
   %c = icmp slt i64 %a, 6
   %xor = xor i1 %b, %c
   ret i1 %xor
 }
 
 define i1 @xor_of_icmps_to_ne_extra_use_one(i64 %a) {
 ; CHECK-LABEL: @xor_of_icmps_to_ne_extra_use_one(
 ; CHECK-NEXT:    [[B:%.*]] = icmp sgt i64 [[A:%.*]], 4
-; CHECK-NEXT:    [[C:%.*]] = icmp slt i64 [[A]], 6
 ; CHECK-NEXT:    call void @use(i1 [[B]])
-; CHECK-NEXT:    [[XOR:%.*]] = xor i1 [[B]], [[C]]
-; CHECK-NEXT:    ret i1 [[XOR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i64 [[A]], 5
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %b = icmp sgt i64 %a, 4
   %c = icmp slt i64 %a, 6
   call void @use(i1 %b)
   %xor = xor i1 %b, %c
   ret i1 %xor
 }