[InstCombine] Add transforms for `(icmp {u|s}ge/le (xor X, Y), X)`

[goldstein.w.n]

Summary

If Y is non-zero we can simplify the ge/le -> gt/lt

(X ^ Y_NonZero) u>= X --> (X ^ Y_NonZero) u> X

• https://alive2.llvm.org/ce/z/k482NQ

(X ^ Y_NonZero) u<= X --> (X ^ Y_NonZero) u< X

• https://alive2.llvm.org/ce/z/TuUDGy

(X ^ Y_NonZero) s>= X --> (X ^ Y_NonZero) s> X

• https://alive2.llvm.org/ce/z/vXQypR

(X ^ Y_NonZero) s<= X --> (X ^ Y_NonZero) s< X

• https://alive2.llvm.org/ce/z/fbUq-z

[goldstein.w.n]

Rebase

[spatel]

This is adding a lot of code to a function that's already too big. A helper function will make it easier to read.

This seems like 2 or 3 independent patches? I just looked at the first group of 4 Alive proofs, and those seem fine.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4421

Use isNonStrictPredicate() / getStrictPredicate() ?

[goldstein.w.n]

In D144608#4158566, @spatel wrote:

This is adding a lot of code to a function that's already too big. A helper function will make it easier to read.

This seems like 2 or 3 independent patches? I just looked at the first group of 4 Alive proofs, and those seem fine.

Sorry just saw this, will do so, likewise for the or patch.

[goldstein.w.n]

Split into two patch + move to helper

[goldstein.w.n]

Use getstrictpred

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4091–4093

Can we canonicalize the xor as operand 0?
It shouldn't make much difference on this patch, but that would make the next one smaller.

// Normalize xor operand as operand 0.
CmpInst::Predicate Pred = I.getPredicate();
if (match(Op1, m_c_Xor(m_Specific(Op0), m_Value()))) {
  std::swap(Op0, Op1);
  Pred = ICmpInst::getSwappedPredicate(Pred);
}
if (!match(Op0, m_c_Xor(m_Specific(Op1), m_Value(A))))
  return nullptr;

llvm/test/Transforms/InstCombine/icmp-of-xor-x.ll

41

This is testing the commuted xor, so that's good - but it would be better to commute the xor operands in the original test, so we are not relying on some other transform to get to canonical form.

73–74

Similar to above, it would be better if the xor operands are swapped originally.
But we need another instruction to make this test provide coverage for the pattern where the xor is operand 1 of the icmp. Ie, %x needs to be generated by a binop similar to the test just above this one.

[goldstein.w.n]

llvm/test/Transforms/InstCombine/icmp-of-xor-x.ll

41

This is testing the commuted xor, so that's good - but it would be better to commute the xor operands in the original test, so we are not relying on some other transform to get to canonical form.

Sorry not sure I understand what you mean by "in the original test" or what you want changed.

Did update this patch (along with follow / or to swap op0/op1 so op0 is always the xor.

[goldstein.w.n]

Swap ops to cannonicalize and cleanup logic

[spatel]

llvm/test/Transforms/InstCombine/icmp-of-xor-x.ll

41

I posted comments directly in D144607 to hopefully make it clearer.

[goldstein.w.n]

Rebase

[spatel]

LGTM

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[goldstein.w.n]

This doesn't appear to have been related to PR62175 so repushing.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

static Instruction *foldICmpXNegX(ICmpInst &I) {
   else if (ICmpInst::isUnsigned(Pred))
     Pred = ICmpInst::getSignedPredicate(Pred);
   // else for equality-comparisons just keep the predicate.
 
   return ICmpInst::Create(Instruction::ICmp, Pred, X,
                           Constant::getNullValue(X->getType()), I.getName());
 }
 
+static Instruction *foldICmpXorXX(ICmpInst &I, const SimplifyQuery &Q,
+                                  InstCombinerImpl &IC) {
+  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1), *A;
+  // Normalize xor operand as operand 0.
+  CmpInst::Predicate Pred = I.getPredicate();
+  if (match(Op1, m_c_Xor(m_Specific(Op0), m_Value()))) {
+    std::swap(Op0, Op1);
+    Pred = ICmpInst::getSwappedPredicate(Pred);
+  }
+  if (!match(Op0, m_c_Xor(m_Specific(Op1), m_Value(A))))
+    return nullptr;
+
+  // icmp (X ^ Y_NonZero) u>= X --> icmp (X ^ Y_NonZero) u> X
+  // icmp (X ^ Y_NonZero) u<= X --> icmp (X ^ Y_NonZero) u< X
+  // icmp (X ^ Y_NonZero) s>= X --> icmp (X ^ Y_NonZero) s> X
+  // icmp (X ^ Y_NonZero) s<= X --> icmp (X ^ Y_NonZero) s< X
+  CmpInst::Predicate PredOut = CmpInst::getStrictPredicate(Pred);
+  if (PredOut != Pred &&
+      isKnownNonZero(A, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT))
+    return new ICmpInst(PredOut, Op0, Op1);
+
+  return nullptr;
+}
+
 /// Try to fold icmp (binop), X or icmp X, (binop).
 /// TODO: A large part of this logic is duplicated in InstSimplify's
 /// simplifyICmpWithBinOp(). We should be able to share that and avoid the code
 /// duplication.
 Instruction *InstCombinerImpl::foldICmpBinOp(ICmpInst &I,
                                              const SimplifyQuery &SQ) {
   const SimplifyQuery Q = SQ.getWithInstruction(&I);
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
if (NoOp0WrapProblem && ICmpInst::isSigned(Pred)) {
     Value *X;
     if (match(BO0, m_Neg(m_Value(X))))
       if (Constant *RHSC = dyn_cast<Constant>(Op1))
         if (RHSC->isNotMinSignedValue())
           return new ICmpInst(I.getSwappedPredicate(), X,
                               ConstantExpr::getNeg(RHSC));
   }
 
+  if (Instruction * R = foldICmpXorXX(I, Q, *this))
+    return R;
+
   {
     // Try to remove shared multiplier from comparison:
     // X * Z u{lt/le/gt/ge}/eq/ne Y * Z
     Value *X, *Y, *Z;
     if (Pred == ICmpInst::getUnsignedPredicate(Pred) &&
         ((match(Op0, m_Mul(m_Value(X), m_Value(Z))) &&
           match(Op1, m_c_Mul(m_Specific(Z), m_Value(Y)))) ||
          (match(Op0, m_Mul(m_Value(Z), m_Value(X))) &&
           match(Op1, m_c_Mul(m_Specific(Z), m_Value(Y)))))) {
       bool NonZero;
       if (ICmpInst::isEquality(Pred)) {
         KnownBits ZKnown = computeKnownBits(Z, 0, &I);
         // if Z % 2 != 0
         //    X * Z eq/ne Y * Z -> X eq/ne Y
         if (ZKnown.countMaxTrailingZeros() == 0)
           return new ICmpInst(Pred, X, Y);
         NonZero = !ZKnown.One.isZero() ||
                   isKnownNonZero(Z, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT);
         // if Z != 0 and nsw(X * Z) and nsw(Y * Z)

llvm/test/Transforms/InstCombine/icmp-of-xor-x.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 declare void @llvm.assume(i1)
 declare void @barrier()
 
 define i1 @xor_uge(i8 %x, i8 %y) {
 ; CHECK-LABEL: @xor_uge(
 ; CHECK-NEXT:    [[YNZ:%.*]] = icmp ne i8 [[Y:%.*]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[YNZ]])
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[X:%.*]], [[Y]]
-; CHECK-NEXT:    [[R:%.*]] = icmp uge i8 [[XOR]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[XOR]], [[X]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %ynz = icmp ne i8 %y, 0
   call void @llvm.assume(i1 %ynz)
   %xor = xor i8 %x, %y
   %r = icmp uge i8 %xor, %x
   ret i1 %r
 }
 
 define i1 @xor_uge_fail_maybe_zero(i8 %x, i8 %y) {
 ; CHECK-LABEL: @xor_uge_fail_maybe_zero(
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[R:%.*]] = icmp uge i8 [[XOR]], [[X]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %xor = xor i8 %x, %y
   %r = icmp uge i8 %xor, %x
   ret i1 %r
 }
 
 define <2 x i1> @xor_ule_2(<2 x i8> %x, <2 x i8> %yy) {
 ; CHECK-LABEL: @xor_ule_2(
 ; CHECK-NEXT:    [[Y:%.*]] = or <2 x i8> [[YY:%.*]], <i8 9, i8 8>
 ; CHECK-NEXT:    [[XOR:%.*]] = xor <2 x i8> [[Y]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ule <2 x i8> [[XOR]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ult <2 x i8> [[XOR]], [[X]]
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %y = or <2 x i8> %yy, <i8 9, i8 8>
   %xor = xor <2 x i8> %y, %x
   %r = icmp ule <2 x i8> %xor, %x
   ret <2 x i1> %r
 }
 
 define i1 @xor_sle_2(i8 %xx, i8 %y, i8 %z) {
 ; CHECK-LABEL: @xor_sle_2(
 ; CHECK-NEXT:    [[X:%.*]] = add i8 [[XX:%.*]], [[Z:%.*]]
 ; CHECK-NEXT:    [[YNZ:%.*]] = icmp ne i8 [[Y:%.*]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[YNZ]])
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[X]], [[Y]]
-; CHECK-NEXT:    [[R:%.*]] = icmp sle i8 [[X]], [[XOR]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i8 [[XOR]], [[X]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = add i8 %xx, %z
   %ynz = icmp ne i8 %y, 0
   call void @llvm.assume(i1 %ynz)
   %xor = xor i8 %x, %y
   %r = icmp sle i8 %x, %xor
   ret i1 %r
 }
 
 define i1 @xor_sge(i8 %xx, i8 %yy) {
 ; CHECK-LABEL: @xor_sge(
 ; CHECK-NEXT:    [[X:%.*]] = mul i8 [[XX:%.*]], [[XX]]
 ; CHECK-NEXT:    [[Y:%.*]] = or i8 [[YY:%.*]], -128
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[Y]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp sge i8 [[X]], [[XOR]]
+; CHECK-NEXT:    [[R:%.*]] = icmp slt i8 [[XOR]], [[X]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = mul i8 %xx, %xx
   %y = or i8 %yy, 128
   %xor = xor i8 %y, %x
   %r = icmp sge i8 %x, %xor
   ret i1 %r
 }
 
 define i1 @xor_ugt_2(i8 %xx, i8 %y, i8 %z) {
 ; CHECK-LABEL: @xor_ugt_2(
 ; CHECK-NEXT:    [[X:%.*]] = add i8 [[XX:%.*]], [[Z:%.*]]
 ; CHECK-NEXT:    [[YZ:%.*]] = and i8 [[Y:%.*]], 63
 ; CHECK-NEXT:    [[Y1:%.*]] = or i8 [[YZ]], 64