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

[goldstein.w.n]

Summary

We can simplify ule/ugt -> eq/ne and we can remove the Or in some
cases of eq/ne.

icmp (X | Y) u<= X --> (X | Y) == X

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

icmp (X | Y) u> X --> (X | Y) != X

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

icmp (X | Y) eq/ne X

• --> (~X & Y) eq/ne 0 iff X is freely invertible
• --> (X & ~Y) eq/ne -1 iff Y is freely invertible
  • https://alive2.llvm.org/ce/z/cpPV_W

[goldstein.w.n]

Rebase

[goldstein.w.n]

Split into two patch + helper

[goldstein.w.n]

Rebase

[goldstein.w.n]

Swap operands so op0 is always or for cleaner logic

[goldstein.w.n]

Rebase

[goldstein.w.n]

Fix typo

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4455–4461

I'm somewhat skeptical about this fold. I can see where you're coming from here, in terms of picking a canonical form between and/or for this pattern, but the fact that we need the undef limitation here (so the canonicalization will be fairly unreliable) and that and/or are generally always handled in conjugate patterns (i.e. we shouldn't have cases where one optimizes better than the other) makes this fold not very compelling to me.

The more obvious canonicalization choice would be X & ~Y == 0, but that adds an extra instruction. We do canonicalize this for the case where Y is a constant, but don't do it even if Y is freely invertable (https://llvm.godbolt.org/z/7MWefMbP9).

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4455–4461

I'm somewhat skeptical about this fold. I can see where you're coming from here, in terms of picking a canonical form between and/or for this pattern, but the fact that we need the undef limitation here (so the canonicalization will be fairly unreliable) and that and/or are generally always handled in conjugate patterns (i.e. we shouldn't have cases where one optimizes better than the other) makes this fold not very compelling to me.

Agreed that is a limitation, but seems to me be better than nothing no?

The more obvious canonicalization choice would be X & ~Y == 0, but that adds an extra instruction. We do canonicalize this for the case where Y is a constant, but don't do it even if Y is freely invertable (https://llvm.godbolt.org/z/7MWefMbP9).

Although if Y is constant then it will be no undef so it will reach X & Y == Y -> X & ~Y == 0 either way.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4455–4461

I'm somewhat skeptical about this fold. I can see where you're coming from here, in terms of picking a canonical form between and/or for this pattern, but the fact that we need the undef limitation here (so the canonicalization will be fairly unreliable) and that and/or are generally always handled in conjugate patterns (i.e. we shouldn't have cases where one optimizes better than the other) makes this fold not very compelling to me.

Agreed that is a limitation, but seems to me be better than nothing no?

The more obvious canonicalization choice would be X & ~Y == 0, but that adds an extra instruction. We do canonicalize this for the case where Y is a constant, but don't do it even if Y is freely invertable (https://llvm.godbolt.org/z/7MWefMbP9).

Although if Y is constant then it will be no undef so it will reach X & Y == Y -> X & ~Y == 0 either way.

4455–4461

I'm somewhat skeptical about this fold. I can see where you're coming from here, in terms of picking a canonical form between and/or for this pattern, but the fact that we need the undef limitation here (so the canonicalization will be fairly unreliable) and that and/or are generally always handled in conjugate patterns (i.e. we shouldn't have cases where one optimizes better than the other) makes this fold not very compelling to me.

Agreed that is a limitation, but seems to me be better than nothing no?

The more obvious canonicalization choice would be X & ~Y == 0, but that adds an extra instruction. We do canonicalize this for the case where Y is a constant, but don't do it even if Y is freely invertable (https://llvm.godbolt.org/z/7MWefMbP9).

Although if Y is constant then it will be no undef so it will reach X & Y == Y -> X & ~Y == 0 either way.

I'm wrong about this. Okay ill update to make only for constants and do the ~Y version.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4455–4461

Added X & ~Y versions. Kept noundef version. It generally the norm for functions signitures so think it likely still has value. LMK, however, if you want me to remove it.

[goldstein.w.n]

Add X & ~Y == 0 transform

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4456–4458

No need to spell out one-use in comments.

4468

As said previously, I don't think this canonicalization makes sense. Please drop it so we can land the rest of this patch.

[goldstein.w.n]

Cleanup comment + remove noundef fold

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4448

Rebase mistake?

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4477

The proofs in the patch description need an update.

Worth noting that there is also a similar fold for the case where X is freely invertible: https://alive2.llvm.org/ce/z/cpPV_W

This case might actually be the more common one, because it covers (X | C) == X.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4448

Ah, yeah that should be with the following patch. Will update.

[goldstein.w.n]

Add another freely invertible fold

[foad]

We can simplify ule/ugt -> eq/ne and we can remove the xor in some
cases of eq/ne.

What does "the xor" refer to? Description needs updating?

[foad]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4444

"else if" to avoid doing the match twice if we swapped?

4452

No "else" after "return"

4465

The comments say "X" but the code says "A". Can you change one or the other so they match?

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4458

You can replace this with isFreeToInvert(Op1, Op1->hasOneUse()). This will also handle some additional cases if the operand only has one use.

[goldstein.w.n]

In D144610#4584068, @foad wrote:

We can simplify ule/ugt -> eq/ne and we can remove the xor in some
cases of eq/ne.

What does "the xor" refer to? Description needs updating?

Mistype, fixed.

[goldstein.w.n]

Fix up some nits

[nikic]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (match(&I, m_c_ICmp(Pred, m_OneUse(m_Neg(m_Value(X))), m_Deferred(X))) &&
     Value *And = Builder.CreateAnd(X, MaxSignedVal);
     Constant *Zero = Constant::getNullValue(Ty);
     return CmpInst::Create(Instruction::ICmp, Pred, And, Zero);
   }
 
   return nullptr;
 }
 
+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 *foldICmpOrXX(ICmpInst &I, const SimplifyQuery &Q,
+                                 InstCombinerImpl &IC) {
+  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1), *A;
+
+  // Normalize or operand as operand 0.
+  CmpInst::Predicate Pred = I.getPredicate();
+  if (match(Op1, m_c_Or(m_Specific(Op0), m_Value()))) {
+    std::swap(Op0, Op1);
+    Pred = ICmpInst::getSwappedPredicate(Pred);
+  }
+
+  if (!match(Op0, m_c_Or(m_Specific(Op1), m_Value(A))))
+    return nullptr;
+
+  // icmp (X | Y) u<= X --> (X | Y) == X
+  if (Pred == ICmpInst::ICMP_ULE)
+    return new ICmpInst(ICmpInst::ICMP_EQ, Op0, Op1);
+
+  // icmp (X | Y) u> X --> (X | Y) != X
+  else if (Pred == ICmpInst::ICMP_UGT)
+    return new ICmpInst(ICmpInst::ICMP_NE, Op0, Op1);
+
+  if (ICmpInst::isEquality(Pred) && Op0->hasOneUse()) {
+    // icmp (X | Y) eq/ne Y --> (X & ~Y) eq/ne 0 if Y is freely invertible
+    if (match(Op1, m_Not(m_Value())) || match(Op1, m_ImmConstant()))
+      return new ICmpInst(Pred,
+                          IC.Builder.CreateAnd(A, IC.Builder.CreateNot(Op1)),
+                          Constant::getNullValue(Op1->getType()));
+  }
+  return nullptr;
+}
+
 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(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;
+  if (Instruction *R = foldICmpOrXX(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)))) ||

llvm/test/Transforms/InstCombine/icmp-of-or-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()
 declare void @use.v2i8(<2 x i8>)
 
 define i1 @or_ugt(i8 %x, i8 %y) {
 ; CHECK-LABEL: @or_ugt(
 ; CHECK-NEXT:    [[XN1:%.*]] = or i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[XN1]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[XN1]], [[X]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %xn1 = or i8 %x, %y
   %r = icmp ugt i8 %xn1, %x
   ret i1 %r
 }
 
 define <2 x i1> @or_ule(<2 x i8> %x, <2 x i8> %y) {
 ; CHECK-LABEL: @or_ule(
 ; CHECK-NEXT:    [[XN1:%.*]] = or <2 x i8> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ule <2 x i8> [[XN1]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = icmp eq <2 x i8> [[XN1]], [[X]]
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %xn1 = or <2 x i8> %x, %y
   %r = icmp ule <2 x i8> %xn1, %x
   ret <2 x i1> %r
 }
 
 define <2 x i1> @or_slt_pos(<2 x i8> %xx, <2 x i8> %yy, <2 x i8> %z) {

 ;
   %xn1 = or i8 %x, %y
   %r = icmp eq i8 %xn1, %x
   ret i1 %r
 }
 
 define i1 @or_eq_notY(i8 %x, i8 %y) {
 ; CHECK-LABEL: @or_eq_notY(
-; CHECK-NEXT:    [[NY:%.*]] = xor i8 [[Y:%.*]], -1
-; CHECK-NEXT:    [[OR:%.*]] = or i8 [[NY]], [[X:%.*]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[OR]], [[NY]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %ny = xor i8 %y, -1
   %or = or i8 %x, %ny
   %cmp = icmp eq i8 %or, %ny
   ret i1 %cmp
 }
 
 define i1 @or_eq_notY_fail_eq_X(i8 %x, i8 %y) {
 ; CHECK-LABEL: @or_eq_notY_fail_eq_X(
 ; CHECK-NEXT:    [[NY:%.*]] = xor i8 [[Y:%.*]], -1
 ; CHECK-NEXT:    [[OR:%.*]] = or i8 [[NY]], [[X:%.*]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[OR]], [[X]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %ny = xor i8 %y, -1
   %or = or i8 %x, %ny
   %cmp = icmp eq i8 %or, %x
   ret i1 %cmp
 }
 
 define <2 x i1> @or_ne_vecC(<2 x i8> %x) {
 ; CHECK-LABEL: @or_ne_vecC(
-; CHECK-NEXT:    [[OR:%.*]] = or <2 x i8> [[X:%.*]], <i8 9, i8 42>
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne <2 x i8> [[OR]], <i8 9, i8 42>
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i8> [[X:%.*]], <i8 -10, i8 -43>
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne <2 x i8> [[TMP1]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
   %or = or <2 x i8> %x, <i8 9, i8 42>
   %cmp = icmp ne <2 x i8> %or, <i8 9, i8 42>
   ret <2 x i1> %cmp
 }
 
 define i1 @or_eq_fail_maybe_undef(i8 %x, i8 %y) {
;
   %r = icmp ult i8 %rhs, %lbo
   ret i1 %r
 }
 
 define i1 @or_simplify_ugt_fail(i8 %y_in, i8 %rhs_in) {
 ; CHECK-LABEL: @or_simplify_ugt_fail(
 ; CHECK-NEXT:    [[RHS:%.*]] = or i8 [[RHS_IN:%.*]], 1
 ; CHECK-NEXT:    [[LBO:%.*]] = or i8 [[RHS]], [[Y_IN:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[LBO]], [[RHS]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[LBO]], [[RHS]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %y = and i8 %y_in, -2
   %rhs = or i8 %rhs_in, 1
   %lbo = or i8 %y, %rhs
   %r = icmp ugt i8 %lbo, %rhs
   ret i1 %r
 }
 
 define i1 @pr64610(ptr %b) {
 ; CHECK-LABEL: @pr64610(
-; CHECK-NEXT:    [[V:%.*]] = load i1, ptr [[B:%.*]], align 2
-; CHECK-NEXT:    [[S:%.*]] = select i1 [[V]], i32 74, i32 0
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[S]], 1
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt i32 [[OR]], [[S]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 true
 ;
   %v = load i1, ptr %b, align 2
   %s = select i1 %v, i32 74, i32 0
   %or = or i32 %s, 1
   %r = icmp ugt i32 %or, %s
   ret i1 %r
 }