[InstCombine] Add transforms for `(icmp (xor X, Y), X)`

[goldstein.w.n]

Summary

There are a variety of cases we can simplify either saving
instructions are creating sequences that are easier to optimize
elsewhere.

(X ^ Y) u> X --> X & MSB(Y) == 0

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

(X ^ Y) u< X --> X & MSB(Y) != 0

• https://alive2.llvm.org/ce/z/5s9SWj

(X ^ Pos_Y) s> X --> X & MSB(Pow2_Y) == 0

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

(X ^ Pos_Y) s< X --> X & MSB(Pow2_Y) != 0

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

(X ^ Neg_Y) s> X --> X s< 0

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

(X ^ Neg_Y) s< X --> X s>= 0

• https://alive2.llvm.org/ce/z/36iZDw

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[nikic]

Is there any real-world motivation for these xor transforms (and also the signed predicate variants in this patch stack)? If not, I'm not sure this is worthwhile.

[goldstein.w.n]

In D145280#4182474, @nikic wrote:

Is there any real-world motivation for these xor transforms (and also the signed predicate variants in this patch stack)? If not, I'm not sure this is worthwhile.

None handy, but doesn't seem like unreasonably obscure codes. You think this is unreasonably unlikely?

[goldstein.w.n]

Rebase

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, const 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);
+}
+
 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);
 
+  // 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 = ICmpInst::ICMP_EQ;
+    break;
+  case ICmpInst::ICMP_ULT:
+  case ICmpInst::ICMP_SLT:
+    PredOut = ICmpInst::ICMP_NE;
+    break;
+  default:
+    break;
+  }
+
+  if (PredOut == Pred)
+    return nullptr;
+
+  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, Q.DL, Q.AC, Q.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 = ICmpInst::ICMP_SLT;
+        if (Pred == ICmpInst::ICMP_SLT)
+          PredOut = ICmpInst::ICMP_SGE;
+        return new ICmpInst(PredOut, Op1,
+                            Constant::getNullValue(Op0->getType()));
+      }
+      Usable = !*KnownSign;
+    }
+  }
+
+  if (Usable && Op0->hasOneUse()) {
+    // If known power of 2, then MSB == A.
+    if (IC.isKnownToBeAPowerOfTwo(A, /*OrZero*/ true, 0, &I))
+      return new ICmpInst(PredOut, IC.Builder.CreateAnd(Op1, A),
+                          Constant::getNullValue(Op0->getType()));
+
+    // Otherwise try and find known MSB.
+    if (KnownOpt == std::nullopt)
+      KnownOpt = IC.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,
+          IC.Builder.CreateAnd(
+              Op1, ConstantInt::get(Ty, APInt::getOneBitSet(
+                                            BitWidth, BitWidth - MSBPos - 1))),
+          Constant::getNullValue(Ty));
+    }
+  }
+
   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,

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

;
   %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 slt i8 [[XOR]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i8 [[X]], -1
 ; 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
-; 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: