[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

4217–4223

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

4217–4223

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

4217–4223

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.

4217–4223

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

4217–4223

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

4218–4220

No need to spell out one-use in comments.

4230

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

4193

Rebase mistake?

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4222

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

4193

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

4189

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

4197

No "else" after "return"

4210

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

4203

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

getKnownSign(Value *Op, Instruction *CxtI, const DataLayout &DL,
   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
+    //    if (X | Y).hasOneUse()
+    //        --> (X & ~~Y) eq/ne 0
+    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()));
+    // icmp (X | noundef Y) eq/ne X
+    //    if (X | noundef Y).hasOneUse()
+    //        --> (X & noundef Y) eq/ne noundef Y
+    else if (isGuaranteedNotToBeUndefOrPoison(A, Q.AC, Q.CxtI, Q.DT,
+                                              /*Depth*/ 0))
+      return new ICmpInst(Pred, IC.Builder.CreateAnd(Op1, A), A);
+  }
+  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 (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))
+  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 sle i8 %xn1, %x
   ret i1 %r
 }
 
 define i1 @or_eq_noundef(i8 %x, i8 noundef %y) {
 ; CHECK-LABEL: @or_eq_noundef(
-; CHECK-NEXT:    [[XN1:%.*]] = or i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[XN1]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[TMP1]], [[Y]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %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) {
 ; CHECK-LABEL: @or_eq_fail_maybe_undef(
 ; CHECK-NEXT:    [[XN1:%.*]] = or i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[XN1]], [[X]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %xn1 = or i8 %x, %y
   %r = icmp eq i8 %xn1, %x
   ret i1 %r
 }
 
 define <2 x i1> @or_ne_noundef(<2 x i8> %x, <2 x i8> noundef %y) {
 ; CHECK-LABEL: @or_ne_noundef(
-; CHECK-NEXT:    [[XN1:%.*]] = or <2 x i8> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ne <2 x i8> [[XN1]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i8> [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ne <2 x i8> [[TMP1]], [[Y]]
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %xn1 = or <2 x i8> %x, %y
   %r = icmp ne <2 x i8> %xn1, %x
   ret <2 x i1> %r
 }
 
 define <2 x i1> @or_ne_noundef_fail_reuse(<2 x i8> %x, <2 x i8> noundef %y) {