[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

4409

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

4085–4087

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.

72

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 std::optional<bool> getKnownSign(Value *Op, Instruction *CxtI,
+                                        const DataLayout &DL,
+                                        AssumptionCache *AC, DominatorTree *DT,
+                                        KnownBits &Known) {
+  Known = computeKnownBits(Op, DL, 0, AC, CxtI, DT);
+  if (Known.isNonNegative())
+    return false;
+  if (Known.isNegative())
+    return true;
+
+  Value *X, *Y;
+  if (match(Op, m_NSWSub(m_Value(X), m_Value(Y))))
+    return isImpliedByDomCondition(ICmpInst::ICMP_SLT, X, Y, CxtI, DL);
+
+  return isImpliedByDomCondition(
+      ICmpInst::ICMP_SLT, Op, Constant::getNullValue(Op->getType()), CxtI, DL);
+}
+
 /// 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)) {
     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));
   }
 
   {
+    bool Op0IsXor = false, Op1IsXor = false;
+    if (match(Op0, m_c_Xor(m_Specific(Op1), m_Value(A))))
+      Op0IsXor = true;
+    else if (match(Op1, m_c_Xor(m_Specific(Op0), m_Value(A))))
+      Op1IsXor = true;
+    if (Op0IsXor || Op1IsXor) {
+
+      // 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 = Pred;
+      switch (Pred) {
+      case ICmpInst::ICMP_ULE:
+        PredOut = ICmpInst::ICMP_ULT;
+        break;
+      case ICmpInst::ICMP_UGE:
+        PredOut = ICmpInst::ICMP_UGT;
+        break;
+      case ICmpInst::ICMP_SLE:
+        PredOut = ICmpInst::ICMP_SLT;
+        break;
+      case ICmpInst::ICMP_SGE:
+        PredOut = ICmpInst::ICMP_SGT;
+        break;
+      default:
+        break;
+      }
+      if (PredOut != Pred &&
+          isKnownNonZero(A, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT))
+        return new ICmpInst(PredOut, Op0, Op1);
+
+      // icmp (X ^ Y) u> X --> X & MSB(Y) == 0
+      // icmp (X ^ Y) u< X --> X & MSB(Y) != 0
+      // icmp (X ^ Pos_Y) s> X --> X & MSB(Pow2_Y) == 0
+      // icmp (X ^ Pos_Y) s< X --> X & MSB(Pow2_Y) != 0
+      switch (Pred) {
+      case ICmpInst::ICMP_UGT:
+      case ICmpInst::ICMP_SGT:
+        PredOut = Op0IsXor ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE;
+        break;
+      case ICmpInst::ICMP_ULT:
+      case ICmpInst::ICMP_SLT:
+        PredOut = Op0IsXor ? ICmpInst::ICMP_NE : ICmpInst::ICMP_EQ;
+        break;
+      default:
+        break;
+      }
+
+      if (PredOut != Pred) {
+        Value *Xor = Op0IsXor ? Op0 : Op1;
+        Value *X = Op0IsXor ? Op1 : Op0;
+        bool Usable = true;
+        std::optional<KnownBits> KnownOpt;
+        // If signed version we need extra for negative / positive.
+        if (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SLT) {
+          KnownBits Known;
+          auto KnownSign = getKnownSign(A, &I, DL, &AC, &DT, Known);
+          KnownOpt = Known;
+          Usable = false;
+          if (KnownSign != std::nullopt) {
+            // icmp (X ^ Neg_Y) s> X --> X s< 0
+            // icmp (X ^ Neg_Y) s< X --> X s>= 0
+            if (*KnownSign /* true is Signed. */) {
+              // Negative power of 2 must be IntMin so this just a sign
+              // comparison.
+              if (Pred == ICmpInst::ICMP_SGT)
+                PredOut = Op0IsXor ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_SGE;
+              if (Pred == ICmpInst::ICMP_SLT)
+                PredOut = Op0IsXor ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_SLT;
+              return new ICmpInst(PredOut, X,
+                                  Constant::getNullValue(Op0->getType()));
+            }
+            Usable = !*KnownSign;
+          }
+        }
+
+        if (Usable && Xor->hasOneUse()) {
+          // If known power of 2, then MSB == A.
+          if (isKnownToBeAPowerOfTwo(A, /*OrZero*/ true, 0, &I))
+            return new ICmpInst(PredOut, Builder.CreateAnd(X, A),
+                                Constant::getNullValue(Op0->getType()));
+
+          // Otherwise try and find known MSB.
+          if (KnownOpt == std::nullopt)
+            KnownOpt = computeKnownBits(A, 0, &I);
+          unsigned MSBPos = KnownOpt->countMaxLeadingZeros();
+          unsigned BitWidth = KnownOpt->getBitWidth();
+          if (MSBPos == 0 || (MSBPos != BitWidth &&
+                              MSBPos == KnownOpt->countMinLeadingZeros())) {
+            Type *Ty = Op0->getType();
+            return new ICmpInst(
+                PredOut,
+                Builder.CreateAnd(
+                    X,
+                    ConstantInt::get(Ty, APInt::getOneBitSet(
+                                             BitWidth, BitWidth - MSBPos - 1))),
+                Constant::getNullValue(Ty));
+          }
+        }
+      }
+    }
+  }
+
+  {
     // 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)))))) {

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> %x, %y
   %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 slt i8 [[X]], [[XOR]]
 ; 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 %x, i8 %yy) {
 ; CHECK-LABEL: @xor_sge(
-; CHECK-NEXT:    [[Y:%.*]] = or i8 [[YY:%.*]], -128
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[Y]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp sge i8 [[XOR]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = icmp slt i8 [[X:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %y = or i8 %yy, 128
   %xor = xor i8 %x, %y
   %r = icmp sge i8 %xor, %x
   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
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[X]], [[Y1]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[X]], [[XOR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X]], 64
+; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = add i8 %xx, %z
   %yz = and i8 %y, 63
   %y1 = or i8 %yz, 64
   %xor = xor i8 %x, %y1
   %r = icmp ugt i8 %x, %xor
   ret i1 %r
 }
 
 define i1 @xor_ult(i8 %x) {
 ; CHECK-LABEL: @xor_ult(
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[X:%.*]], 123
-; CHECK-NEXT:    [[R:%.*]] = icmp ult i8 [[XOR]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X:%.*]], 64
+; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %xor = xor i8 %x, 123
   %r = icmp ult i8 %xor, %x
   ret i1 %r
 }
 
 define <2 x i1> @xor_sgt(<2 x i8> %x, <2 x i8> %y) {
 ; CHECK-LABEL: @xor_sgt(
-; CHECK-NEXT:    [[YZ:%.*]] = and <2 x i8> [[Y:%.*]], <i8 31, i8 31>
-; CHECK-NEXT:    [[Y1:%.*]] = or <2 x i8> [[YZ]], <i8 64, i8 64>
-; CHECK-NEXT:    [[XOR:%.*]] = xor <2 x i8> [[Y1]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp sgt <2 x i8> [[XOR]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i8> [[X:%.*]], <i8 64, i8 64>
+; CHECK-NEXT:    [[R:%.*]] = icmp eq <2 x i8> [[TMP1]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %yz = and <2 x i8> %y, <i8 31, i8 31>
   %y1 = or <2 x i8> %yz, <i8 64, i8 64>
   %xor = xor <2 x i8> %x, %y1
   %r = icmp sgt <2 x i8> %xor, %x
   ret <2 x i1> %r
 }
;
   %y1 = or <2 x i8> %yz, <i8 8, i8 8>
   %xor = xor <2 x i8> %x, %y1
   %r = icmp sgt <2 x i8> %xor, %x
   ret <2 x i1> %r
 }
 
 define i1 @xor_slt_2(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @xor_slt_2(
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[X:%.*]], 88
-; CHECK-NEXT:    [[R:%.*]] = icmp sgt i8 [[XOR]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X:%.*]], 64
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %xor = xor i8 %x, 88
   %r = icmp slt i8 %x, %xor
   ret i1 %r
 }
 
 define <2 x i1> @xor_sgt_intmin_2(<2 x i8> %xx, <2 x i8> %yy, <2 x i8> %z) {
 ; CHECK-LABEL: @xor_sgt_intmin_2(
 ; CHECK-NEXT:    [[X:%.*]] = add <2 x i8> [[XX:%.*]], [[Z:%.*]]
-; CHECK-NEXT:    [[Y:%.*]] = or <2 x i8> [[YY:%.*]], <i8 -128, i8 -128>
-; CHECK-NEXT:    [[XOR:%.*]] = xor <2 x i8> [[X]], [[Y]]
-; CHECK-NEXT:    [[R:%.*]] = icmp sgt <2 x i8> [[X]], [[XOR]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt <2 x i8> [[X]], <i8 -1, i8 -1>
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %x = add <2 x i8> %xx, %z
   %y = or <2 x i8> %yy, <i8 128, i8 128>
   %xor = xor <2 x i8> %x, %y
   %r = icmp sgt <2 x i8> %x, %xor
   ret <2 x i1> %r
 }
 
 define i1 @or_slt_intmin_indirect(i8 %x, i8 %C) {
 ; CHECK-LABEL: @or_slt_intmin_indirect(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[C:%.*]], 0
 ; CHECK-NEXT:    br i1 [[CMP]], label [[NEG:%.*]], label [[POS:%.*]]
 ; CHECK:       common.ret:
 ; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i1 [ [[R:%.*]], [[NEG]] ], [ false, [[POS]] ]
 ; CHECK-NEXT:    ret i1 [[COMMON_RET_OP]]
 ; CHECK:       neg:
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[C]], [[X:%.*]]
-; CHECK-NEXT:    [[R]] = icmp slt i8 [[XOR]], [[X]]
+; CHECK-NEXT:    [[R]] = icmp sgt i8 [[X:%.*]], -1
 ; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
 ; CHECK:       pos:
 ; CHECK-NEXT:    tail call void @barrier()
 ; CHECK-NEXT:    br label [[COMMON_RET]]
 ;
   %cmp = icmp slt i8 %C, 0
   br i1 %cmp, label %neg, label %pos
 common.ret: